Алгебра логики устанавливает основные законы формирования и
преобразования логических функций. АЛ позволяет представить любую
сложную функцию в виде композиции простых функций.
Базовым понятием АЛ является логическая переменная.
В АЛ над ллогическими переменными выполняются логические операции.
Каждая логическая операция задается таблицей истинности.Существует 16
логических операций.
В АЛ существуют также законы, позволяющие преобразовать сложные логические функции:
1)X
1•X
2=X
2•X
1
X
1+X
2=X
2+X
1
2)(X
1•X
2)•X
3=X
1•(X
2•X
3)
(X
1+X
2)+X
3=X
1+(X
2+X
3)
3)X
1•(X
2+X
3)=X
1•X
2+X
1•X
3
4)X
1+X
1•X
2=X
1
X
1•(X
1+X
2)=X
1
5)X
1•X
2+X
1•¬X
2=X
1
(X
1+X
2)•(X
1+¬X
2)=X
1
6)X+¬X•F=X+F
X•(¬X+F)=X•F
F - логическая функция общего вида, не зависящая от переменной Х
7)¬(X
1+X
2)=¬X
1•¬X
2 Правило Де Моргана
Система булевых функций (W) называется функционально полной, если для
любой булевой функции (любой сложности) может быть построена равная ей
функция путем суперпозиции функций из W от аргументов X1..Xn
Доказываются следующие 2 утверждения:
1)Если W содержит •, + и ¬, то такая система является функционально полной.
2)Функционально полными являются также системы вида:
+,¬ - Пирс
•,¬ -Шеффер