Представление функций формулами. Равносильные формулы

Пусть F={ f_1, f_2,…, f_m}- множество булевых функций.

Формулой над F называется выражение вида f(t_1, t_2,…, t_n), где t_i либо переменная, либо формула над F.

Всякой формуле однозначно соответствует некоторая булева функция, но не наоборот.

Одна и та же функция может быть представлена различными формулами.

Зная таблицы истинности для функций множества F можно вычислить таблицу истинности той функции, которую реализует данная формула.

1.	,
2.
3.	,
4.	,
5.
6.
7.
8.	;	;
9.
10.
11.
12.
13.
14.
15.

Различные формулы могут иметь одинаковые таблицы истинности, но не наоборот.

Формулы называются равносильными, если совпадают их таблицы истинности.

Основные эквивалентности между формулами:

Формула называется тождественно истинной или тавтологией (тождественно ложной или противоречием), если эта формула принимает значение 1 (соот­ветственно 0) при всех наборах значений переменных.

Формула называется выполнимой (опровержимой), если существует такой набор значений переменных, при котором формула принимает значение 1 (соответственно 0).