Лекция п Булевы функции. Существенная и фиктивная переменная

Выражения являются формулами над , а выражение формулой не является.



Для формул над множеством функциональных символов (логических связок)  принимаются некоторые соглашения:

1) внешние скобки у формул опускаются;

2) формула (AB) записывается в виде (AB) или (AB);

3) считается, что связка  сильнее любой двуместной связки из множества ;

4) связка  считается сильнее, чем любая другая двуместная связка из множества .

Сопоставим теперь каждой формуле G некоторую функцию f_G. Понятие булевой функции f_G, реализуемой формулой G, вводится рекурсивно следующим образом:

1) Формуле G=x, где xX, сопоставляется функция ;

2) если G равна одной из формул , где A, B – это формулы над , то f_G равно соответствующей элементарной булевой функции . Если , то значение ее на произвольном наборе , совпадает со значением на этом наборе для соответствующей ей элементарной булевой функции.

Таким образом, зная таблицы истинности элементарных функций (