Основы алгебры логики

ЛОГИЧЕСКИЕ ОСНОВЫ ПОСТРОЕНИЯ ПК

Для анализа и синтеза схем в ЭВМ при алгоритмизации и программировании решения задач широко используется математический аппарат алгебры логики.

Алгебра логики — это раздел математической логики, значения всех эле­ментов (функций и аргументов) которой определены в двухэлементном множестве: 0 и 1. Алгебра логики оперирует с логическими высказыва­ниями.

Высказывание — это любое предложение, в отношении которого имеет смысл утверждение о его истинности или ложности. При этом считается, что высказывание удовлетворяет закону исключенного третьего, т.е. каж­дое высказывание или истинно, или ложно и не может быть одновременно и истинным, и ложным.

Пример 4.11. Высказывания: "Сейчас идет снег" — это утверждение может быть ис­тинным или ложным; "Вашингтон — столица США" — истинное утверждение; "Частное от деления 10 на 2 равно 3" — ложное утверждение.

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

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

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

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

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

(а + b) + с = а + (b + с);

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

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

а + b = b + а;

а * b = b * а;

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

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

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

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

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

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

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

a + b = a, если а > Ь; и др.

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

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

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

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

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

f(a,b,c) = а + а*b*с + а+с;

f(a,b,c) = а*b + *с + *b*с

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

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

f(a,b) = f(1,b)*a + f(0,b)* = f( 1,1 )*a*a + f( 1,0 )*a*+ f( 0,1 )* *b + f( 0,0 )* *

и т.д.

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

Дата добавления: 2014-01-06