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

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

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

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

В основе булевой алгебры лежат 16 основных функций. Наиболее часто применяемые из них:

 

Логическое отрицание (инверсия) – НЕ;

Логическое сложение (дизъюнкция) – ИЛИ; (+,v)

Логическое умножение (конъюнкция) –И; (^,*)

Функция Вебба (отрицание дизъюнкции) –ИЛИ-НЕ;

Функция Шеффера (отрицание конъюнкции) – И-НЕ;

Сложение по модулю 2(М2).

 

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

Аргументы	Ф У Н К Ц И И
Х2	Х1	НЕ-Х2	НЕ Х1	ИЛИ	И	ИЛИ-НЕ	И-НЕ	М2

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

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

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

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

(а * b) * с = а * (b * с);

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

а + b = b + а;

а * b = b * а;

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

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

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

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

а + а = а; а * а = а;

а+а* b=а; 1\/0=1

0\/1=1 0/\1=0;

1/\1=1 1\/1=1 и др.

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

По определению:

Справедливы, например, такие соотношения(Закон Де Моргана):

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