Глава 20. Формулы

Пусть F = {F1, …, Fm} – множество булевых функций. Формулой над F называется выражение вида F(T1, …, Tn), где T1, …, Tn либо переменные, либо формулы. Множество F называется базисом, функция F называется главной (внешней) операцией формулы.

Обычно для элементарных булевых функций используется инфиксная форма записи, устанавливается приоритет (Ø, &, Å, , ®, «) и лишние скобки опускаются.

Одна функция может иметь множество реализаций (над данным базисом). Фор­мулы, реализующие одну и ту же функцию, называются Равносильными. Отношение равносильности формул является эквивалентностью. Имеют место следующие равносильности:

1. , ;

2.

3. ,

4.

5.

6.

7.

8.

9.

10.

< Предыдущая		Следующая >