Выражение импликации через другие операции.

В справедливости этих формул можно убедиться, построив таблицы истинности этих формул.

Функция  называется двойственной функции .

Если , то функция  называется самодвойственной.

Разложение вида , называется совершенной дизъюнктивной нормальной формой(СДНФ).

Разложение вида , называется совершенной конъюнктивной нормальной формой (СКНФ).

Полиномом Жегалкина (сокращенно - ПЖ) от переменных  называется сумма по модулю 2: . Например, для функции от двух переменных ПЖ= .

    Система функций {f ₁ ,..., f_s} называется полной (функционально полной), если любая булева функция может быть записана в виде формул через функции этой системы.

    Замыканием М (обозначается [М]) называется множество функций, являющихся суперпозицией функций из М. Класс (множество) М называется замкнутым (функционально замкнутым), если М=[М].

    Важнейшие замкнутые классы алгебры логики – T ₀ , T ₁ , S , M , L .

T ₀ – класс булевых функций , сохраняющих константу 0.

T ₁ - класс булевых функций , сохраняющих константу 1.

S – класс самодвойственных функций.

М – класс монотонных функций , то есть таких функций, для которых при любой паре наборов , находящихся в отношении предшествования ( ), имеет место неравенство: .

L – класс линейных функций, то есть таких функций полиномы Жегалкина для которых не содержат конъюнкций.

    Лемма о несамодвойственной функции. Если булева функция  не является самодвойственной, то из нее путем подстановки функций  можно получить константу.

    Лемма о немонотонной функции. Если булева функция  не является монотонной, то из нее путем подстановки констант «0» и «1» и функции x можно получить .

    Лемма о нелинейной функции. Если булева функция  не является линейной, то из нее путем подстановки констант «0» и «1» и функций , а также путем навешивания отрицаний над функцией f, можно получить конъюнкцию.

    Критерий полноты системы булевых функций (Теорема Поста о функциональной полноте).Система булевых функций F является полной тогда и только тогда, когда она целиком не содержится ни в одном из пяти замкнутых классов.

Пример 1. По заданной суперпозиции составить формулу, реализующую булеву функцию.

Решение:

-формула

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

Решение:

Пример 3 . Составить таблицу истинности булевой функции:

Решение:

000	0	0	0	0	0
001	1	0	0	0	0
010	1	0	0	0	0
011	0	0	0	0	0
100	0	0	0	0	0
101	1	1	0	1	1
110	1	1	1	0	1
111	0	0	1	1	0

.

Пример 4. Построить полином Жегалкина методом неопределенных коэффициентов.

  Пример 5.  Определить какие переменные являются фиктивными.

000	0	1
001	1	1
010	0	0
011	1	0
100	1	1
101	0	1
110	1	1
111	0	1

Пример 6. Построить СДНФ и СКНФ для заданной функции:

Построим таблицу истинности:

				f
000	1	0	0	1
001	1	0	1	1
010	0	1	0	0
011	0	1	1	1
100	1	1	1	1
101	1	1	0	0
110	0	0	1	1
111	0	0	0	1

__________________________________________

Пример 7. Доказать полноту системы функций и выразить константы, отрицание и конъюнкцию через функции системы F :

Решение:

Система функций является полной.

Комбинаторика.