можно комбинировать булевы переменные с помощью булевых операций, получая булевы выражения, которые называются формулами.
Всякой формуле однозначно соответствует некоторая функция, при этом говорят, что формула реализует функцию.
ПРИМЕР:
Построить таблицу истинности для формулы
.
| x1
| x2
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таким образом, формула
реализует функцию
(тождественная единица).
ПРИМЕР:
Построить таблицу истинности для формулы
.
Таким образом, формула
реализует функцию
(дизъюнкция).
Равносильные формулы
Формулы называются равносильными, если реализуют одну и ту же функцию.
Формула называется тождественно-истинной или тавтологией, если она реализует тождественную единицу.
Формула называется тождественно-ложной, если она реализует тождественный ноль.