2

Алгоритм получения СДНФ

Алгоритм получения СКНФ
привести формулу с помощью равносильных преобразований к КНФ.
удалить члены конъюнкции, содержащие переменную вместе с ее отрицанием (если такие окажутся);
из одинаковых членов конъюнкции (если такие окажутся) удалить все, кроме одного;
из одинаковых членов каждой дизъюнкции (если такие окажутся) удалить все, кроме одного;
если в какой-нибудь дизъюнкции не содержится переменной xi из числа переменных, входящих в исходную формулу, добавить к этой дизъюнкции член и применить закон дистрибутивности дизъюнкции относительно конъюнкции;
если в полученной конъюнкции окажутся одинаковые члены, воспользоваться предписанием из п. 3.

Алгоритм получения СКНФ

Булевы функции одной переменной
ϕ0≡ 0 — функция константа 0,
ϕ1 = x — функция повторения аргумента,
ϕ2 = — функция инверсии или отрицания аргумента,
ϕ3 ≡ 1 — функция константа 1.

Булевы функции двух переменных
0
константа 0
x∧y
x
y
x∨y
1

Булевы функции двух переменных
x→y
y→x

Булевы функции двух переменных
отрицание импликации
отрицание обратной импликации
x⊕y
исключающее «или»
(сумма по модулю 2)
x~y
x↓y
отрицание дизъюнкции
(стрелка Пирса)
x | y
отрицание конъюнкции
(штрих Шеффера)

Двойственные булевы функции
Функция f*(x1,…,xn) называется двойственной к функции f(x1,…,xn), если
Пример
Найти двойственные функции

Самодвойственные булевы функции
Функция, равная своей двойственной, называется самодвойственной.
f = f*

Является ли функция f(x,y,z) самодвойственной?
Пример
f(x,y,z) —
несамодвойственная

Монотонные булевы функции

Монотонные булевы функции

Линейные булевы функции
Многочленами Жегалкина назваются формулы над множеством функций FJ={ 0, 1, ^, +}

Линейные булевы функции
Всякую булеву функцию можно представить единственным полиномом Жегалкина.

Алгоритм построения полинома Жегалкина по СДНФ
Начало. Задана совершенная ДНФ функции f(x1, …, xn).
Шаг 1. Заменяем каждый символ дизъюнкции на символ дизюнкции с исключением.
Шаг 2. Заменяем каждую переменную с инверсией x равносильной формулой x 1.
Шаг 3. Раскрываем скобки.
Шаг 4. Вычеркиваем из формулы пары одинаковых слагаемых.
Конец. Получен полином Жегалкина функции f(x1, …, xn).

Линейные булевы функции

Алгоритм построения полинома Жегалкина
Треугольнику Паскаля

T0, T1, L, M, S

Теорема Поста о функциональной полноте
Одна из сфер применения булевых функций -- синтез логических схем; при этом булевым функциям соответствуют определённые функциональные элементы (детали). Полнота системы функций означает, что, пользуясь только элементами соответствующих этим функциям типов, можно собрать любую логическую схему.