Применение алгебры, логики в информатике

Введение.

1. Введение                                                                   
2. Теоретическая часть                                                
3. Практическая часть                                                  
4. Список используемой литературы                         

 

  
  
  
  
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
                                

Введение.

В теме: «Применение  алгебры, логики в информатике» мы рассмотрим такие вопросы как, что такое алгебра логики, функция в алгебре логики (и её примеры), рассмотрим устройство процессора. А также решим задачу: в бухгалтерии производится расчёт налоговых вычетов, предоставляемых сотрудникам, и формирование платёжных ведомостей. Стандартный налоговый вычет предоставляется каждому сотруднику в размере 400,00 руб. до тех пор, пока совокупный доход с начала года не превысит 50 000,00 руб., налоговый вычет на ребёнка предоставляется в размере 600,00 руб. НДФЛ – налог на доходы физических лиц (13%) рассчитывается с начисленной суммы за минусом размера налогового вычета, в которой требуется построить таблицы; выполнить расчёт размера налогового вычета, предоставляемого сотрудникам в текущем месяце и результаты этих вычислений представить в виде таблицы; сформировать и заполнить форму расчётной ведомости по заработной плате за текущий месяц и результаты расчёта представить в графическом виде.

Свою курсовую я выполнила и оформила с помощью:

• текстового редактора Word, который обеспечивает следующие функции: набор текста, хранение его на магнитных носителях, просмотр и печать. Также в нём реализованы функции проверки орфографии, выбора шрифта, центровки заголовка, перемещения кусков текста. С помощью средств форматирования создают внешний вид документа.
• графического процессора – инструментальные средства, позволяющие создавать и модифицировать графические образы с использованием иллюстративной, коммерческой и научной графики. В свое работе я использовала коммерческую (деловую) графику, которая обеспечивает отображение информации, хранящейся в табличных процессорах, круговой диаграммы и т.д. и научную графику, предназначенную для оформления научных расчётов, содержащих формулы.
• табличного процессора – комплекс программных средств, реализующих создание, регистрацию, редактирование, хранение и обработку электронных таблиц, и выдачу их на печать. Электронная таблица – это двумерный массив строк и столбцов, размещённый в памяти ЭВМ. Широкое распространение получили такие табличные процессоры, как SuperCalk, Visicalk, Lotus 1-2-3, Quattro Pro. Для Windows был создан процессор Excel, который я и использовала при написании работы. Основной единицей электронной таблицы является рабочий лист, имеющий имя, где он располагается. Ширина столбца и высота строки даются по умолчанию. Однако имеется возможность форматирования ячейки, столбца, строки, листа. Можно изменить стиль текста, что позволяет улучшить внешний вид документа без применения текстового редактора. Данные в виде чисел, текста или формул вводятся в ту ячейку, которая отмечена текстовым курсором… редактирование таблиц позволяет копировать, удалять, очищать ячейку, блок, лист и выполнять другие функции, перечисленные в меню действий «правка» и «вставка». При выполнении всех функций в процессоре Excel можно использовать многооконную систему, позволяющую выполнять параллельные действия. Все объекты, созданные пользователем (сформированные таблицы, выборки из БД, диаграммы и графики), можно сохранить на диске, в виде файла или распечатать. 

 

    
  
  
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 
  
  
  
                 

      Теоретическая часть. 

 ЭВМ и  другие цифровые электронные  устройства работают в строгом  соответствии с чёткими логическими  законами, поскольку компьютеры  – это автоматические устройства, принципы, работы которых базируются на элементарных законах двоичной логики. Знание и понимание этих законов помогает в общении с компьютером. 

 Для иллюстрации  рассмотрим следующий пример: один незадачливый бизнесмен подал в компьютерную фирму жалобу на приобретённый компьютер. По словам бизнесмена, компьютер неверно отвечал на поставленные вопросы. Прибывший для проверки жалобы специалист предложил бизнесмену продемонстрировать один из ошибочных ответов. Тот потребовал вывести список клиентов, проживающих в штатах Теннеси и Кентукки, на что компьютер объявил, что таковых не имеется. «Вот видите!» - кипятился бизнесмен. – «А я точно знаю, что и в том, и в другом штате есть множество клиентов!». Консультант попытался объяснить, что машина по-своему права и что человек не может жить одновременно в обоих штатах. Консультант повторил запрос, заменив единственное слово (список клиентов, проживающих в штатах Теннеси ИЛИ Кентукки), и через полминуты вручил распечатку требуемого списка.

Главной причиной возникшего курьёза послужило незнание трёх основных логических операций, лежащих  в основе всех выводов компьютера: И, ИЛИ, НЕ. 

 При записи  логических выражений используется  специальный язык, который принят  в математической логике. Основоположником  математической логики (математической дисциплины, изучающей технику доказательств) является немецкий математикГотфрид Вильгельм Лейбниц. Он сделал попытку построить универсальный язык, с помощью которого споры между людьми модно было бы решать посредством вычислений. На заложенном Лейбницем фундаменте ирландский математик Джордж Буль построил здание новой науки – математической логики, - которая в отличии от обычной алгебры оперирует не

числами, а высказываниями. В честь Буля логические переменные в языке программирования Паскаль впоследствии назвали булевскими.  

 Высказывание  – это любое утверждение, относительно  которого можно сказать истинно  оно или ложно, т. е. соответствует  оно действительности или нет.  Таким образом высказывания являются  двоичными объектами, и поэтому истинному значению высказывания ставят в соответствии 1, а ложному – 0.

Высказывания  могут быть простыми и сложными. Простые соответствуют алгебраическим переменным, а сложные являются аналогом алгебраических функций.  

 Простейшими  операциями в алгебре логики являются операции логического сложения (иначе, операция ИЛИ, операция дизъюнкции) и логического умножения(иначе, операция И, операция конъюнкции). Для обозначения операции логического сложения используют символы +  или \/, а логического умножения – символы * или /\. Составное высказывание, образованное в результате операции логического сложения, истинно тогда, когда истинно хотя бы одно из входящих в него простых высказываний. Составное высказывание, образованное в результате операции логического умножения, истинно тогда и только тогда, когда истинны все входящие в него простые высказывания.   

 Правила  выполнения операций в алгебре  логики определяются рядом аксиом, теорем и следствий.   

 В частности,  для алгебры логики выполняются  законы:

1. сочетательный:

 

              (a + b) + c = a + (b + c);              

(a * b) * c = a * (b * c);

2. переместительный:

 

               a + b = b + a;              

 a * b = b * a;

3. распределительный:

 

                   a * (b + c)=a * b + a * c;                   

 a + b * c = a * b + a * c.

Справедливы соотношения:         

 а + а = а;  

 а * а = а; 

 a + a * b = a; 

 a + b = a, если a >= b; 

 a + b = b, если a < =b; 

 a * b = a, если a < =b;  

a + b = b, если a >=b и т.д.   

Наименьшим элементом алгебры логики является 0, наибольшим элементом – 1.

В алгебре логики также вводится ещё одна операция – операция отрицания (иначе, операция НЕ, операция инверсии), обозначаемая чертой над элементом. Логическое отрицание делает истинное высказывание ложным, и, наоборот, ложное – истинным.   

 По  определению: a + a = 1, a * a = 0, 0 = 1, 1 = 0. 

Справедливы такие  соотношения: a = a, a + b = a * b, a * b = a + b.

Существует  шесть вариантов  отношений:

1. =   равно
2. <>  не равно
3. >  больше
4. <  меньше
5. >= больше или равно
6. <= меньше или равно

 

  Отношение « равно»  истинно для двух  символьных величин,  если их длина  одинакова и все  соответствующие  символы совпадают. (Следует учитывать, что пробел  - это тоже символ).

Символьные  величины можно сопоставлять и в отношениях <, >, <=, >=. Сравниваются между собой не сами символы, а их внутренние коды.

Функция в алгебре логики – это алгебраическое выражение, содержащее элементы алгебры логики a, b, c …, связанные между собой операциями, определёнными в этой алгебре.     

Примеры логических функций:               

(a,b,c) = a + a*b*c + a+c;              

 (a,b,c) = a*b + a*c + a*b*c.  

 Согласно теоремам разложения функций на составляющие любая функция может быть разложена на конституэнты “1” :

(2)          (a) =   (1)*a +   (0)*a;    

       (a,b) =   (1,b)*a +   (0,b)*a =   (1,1)*a*a +   (1,0)*a*b +   (0,1)*a*b +  (0,0)*a*b и т.д.      

 Эти соотношения используются для синтеза логических функций и вычислительных схем.

Логическое  следование (импликация) образуется соединением двух высказываний в одно с помощью оборота речи «если…, то…». Составное высказывание, образованное с помощью операции импликации, ложно тогда и только тогда, когда из истинной предпосылки (первого высказывания) следует ложный вывод (второе высказывание).

Логическое  равенство (эквивалентность) образуется соединением двух высказываний в одно с помощью оборота речи «… тогда и только тогда, когда…». Составное высказывание, образованное с помощью операции эквивалентности истинно тогда и только тогда, когда оба высказывания одновременно либо ложны, либо истинны.

Логический  синтез вычислительных схем.

Рассмотрим логический синтез (создание) вычислительных схем на примере одноразрядного двоичного  сумматора, имеющего два входа ( “a” и “b”) и два выхода (“S” и “P”) и выполняющего операцию сложения в соответствии с заданной таблицей:

a	b	(a,b) = S		(a,b) = P
0	0	0		0
0	1	1	0
1	0	1	0
1	1	0	1

 

      где      (a,b) = S – значение цифры суммы в данном разряде;                 

(a,b) = P – цифра переноса в следующий (старший) разряд.  

 Согласно соотношению (2), можно записать:       

S =    (a,b) = 0*a*b +  1*a*b + 1*a*b + 0*a*b = a*b + a*b;       

P =     (a,b) = 1*a*b + 0*a*b + 0*a*b + 0*a*b = a*b. 

Самой простой  логической операцией является операция НЕ (по-другому отрицание, дополнение или инверсия; обозначают NOT X). Результат отрицания всегда противоположен значению аргумента. Операция Не является унарной, т.е. имеет всего один операнд. В отличии от неё операции И (AND) и ИЛИ (OR) являются бинарными, так как представляют собой результаты действий над двумя логическими величинами. 

 Логическое И называют конъюнкцией, или логическим умножением, а ИЛИ – дизъюнкцией, или логическим сложением.  

 Операция  И имеет результат «истина»  только в том случае, если оба  её операнда истинны. Например, рассмотрим высказывание «Для установки ОС “Windows’95” требуется процессор не ниже 80386 и не менее 4 Мбайт оперативной памяти». Из него следует, что установка будет успешной только при одновременном выполнении обоих условий: даже если у вас в машине Pentium, но мало ОЗУ, «Windows’95» работать откажется. 

 Операция  ИЛИ «менее привередлива» к  исходным данным. Она даёт истину, если значение «истина» имеет  хотя бы один из операндов.  Разумеется, в случае, когда справедливы  оба аргумента одновременно, результат по-прежнему истинный. 

 Приведённые  ниже таблицы значений переменных  для логических операций называются  таблицами истинности. В них указываются  всевозможные

комбинации логических переменных X и Y, а также соответствующие им результаты операций.                                       

Основные  логические операции                                        

   

X	Y	X AND Y	X OR Y
0	0	0	0
0	1	0	1
1	0	0	1
1	1	1	1

X	NOT X
0	1
1	0

 

  
Таблица истинности может рассматриваться  в качестве одного из способов задания  логической функции. 

 Операции  И, ИЛИ, НЕ образуют полную  систему логических операций, из  которой можно построить сколь  угодно сложное логическое выражение. 

В вычислительной  технике также часто используется операция, исключающая ИЛИ (XOR), которая отличается от обыкновенного ИЛИ только при X=1 и Y=1.

 

 

 

 

                             Дополнительные  логические операции

X	Y	X XOR Y	NOT (X AND Y)
0	0	0	1
0	1	1	1
1	0	1	1
1	1	0	0

 

 

      
 Как видно из таблицы, операция XOR фактически сравнивает на совпадение два двоичных разряда. Хотя теоретически основными базовыми логическими операциями называют именно И, ИЛИ, НЕ, на практике по технологическим причинам в качестве основного логического элемента используется элемент И-НЕ, на базе которого могут быть скомпонованы все базовые логические элементы (И, ИЛИ, НЕ), а значит и любые другие, более сложные.