Булевы функции
Булева функция ƒ(X1, Х2,…,Хn) — n-местная функция, аргументы и значения которой принадлежат множеству {0,1}.
Если логические высказывания могут принимать значения истинно или ложно, то для булевой функции аналогами этих значений будут значения 1 или 0. Для булевых функций справедливы таблицы истинности и основные равносильности алгебры высказываний. Дополнительно вводятся операции: Х1|Х2=Х1∧Х2 — штрих Шеффера и X1↓X2=X1vX2- стрелка Пирса.
| Х1 | X2 | ¬X1 | Х1∧Х2 | X1vX2 | X1⇒X2 | Х1⇔Х2 | X1| X2 | Х1 ↓ X2 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 |
Формы представления булевых функций
| Совершенные формы | Формула |
|---|---|
| Совершенная конъюнктивная нормальная форма (СКНФ)— конъюнкция конституент нуля | |
| Совершенная дизъюнктивная нормальная форма (СДНФ) -дизъюнкция конституент единицы |
Пример:
