Пусть — множество булевых функций. Формулой над F называется выражение либо переменная, либо формула над F.
F называется базисом формулы, f – главной (внешней) операцией, ti – подформулами.
Всякой формуле однозначно соответствует некоторая функция f. Это соответствие задается алгоритмом интерпретации, который позволяет вычислить значение функции при заданных значениях переменных.
Зная таблицы истинности для функций базиса можно вычислить таблицу той функции, которую реализует данная формула.
Примеры.
1.
|
x1 |
x2 |
x1 x2 |
|||
|
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
1 |
0 |
0 |
1 |
1 |
|
1 |
0 |
0 |
1 |
0 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
Функция реализует дизъюнкцию на базисе .
2.
|
x1 |
x2 |
x1~ x2 |
||
|
0 |
0 |
1 |
0 |
0 |
|
0 |
1 |
0 |
1 |
1 |
|
1 |
0 |
0 |
0 |
1 |
|
1 |
1 |
1 |
0 |
0 |
Функция реализует дизъюнкцию на базисе .
Таким образом каждая формула определяет некоторую логическую функцию, которую можно представить в виде таблицы истинности для этой формулы. Если в формуле имеется n переменных, то возможны 2n различных истинностных значений для этой формулы. Следовательно, таблица истинности будет иметь 2n строк.