Булева алгебра

Пример 1.

Составить таблицу истинности функции трех переменных, заданной формулой:

Существуют такие наборы логических функций (операций), с помощью которых можно выразить любые другие логические функции.

Функционально полной системой (базисом) называют набор логических функций при помощи которого можно выразить любые другие логические функции.

Примеры функционально полных систем логических функций:

и другие.

Основополагающим и наиболее хорошо изученным является базис {&, v, -}.

Булева формула – это формула, которая содержит кроме переменных и скобок только знаки функций конъюнкции, дизъюнкции и отрицания.

Теорема 1. Всякая логическая функция может быть представлена булевой формулой, т.е. как суперпозиция дизъюнкции, конъюнкции и отрицания.

Следовательно система булевых функций (операций) {&, v, -} функционально полна.

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

Система операций булевой алгебры { &, v, - } функционально полна. Это означает, что переход от табличного задания любой логической функции к формуле булевой алгебры, или булевой формуле, всегда возможен.

Переход от табличного задания логической функции к булевой формуле осуществляется в 3 этапа:

1. для каждого набора значений переменных х1, х2,..., х_n на котором функция f(х1, х2,..., х_n) равна 1, выписываются конъюнкции всех переменных;

2. над теми переменными, которые на этом наборе равны 0, ставятся отрицания;

3. все такие конъюнкции соединяются знаками дизъюнкции.

Полученная таким образом формула называется совершенной дизъюнктивной нормальной формой (СДНФ) логической функции f(х1, х2,..., х_n).

Для каждой функции СДНФ единственна (с точностью до перестановок переменных или конъюнкций).