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