Нормальные формы. Сднф. Скнф.

СДНФ (Совершенная Дизъюнктивная Нормальная Форма) — это такая ДНФ, которая удовлетворяет трём условиям:

§ в ней нет одинаковых элементарных конъюнкций

§ в каждой конъюнкции нет одинаковых пропозициональных букв

§ каждая элементарная конъюнкция содержит каждую пропозициональную букву из входящих в данную ДНФ пропозициональных букв, причем в одинаковом порядке.

Для любой функции алгебры логики существует своя СДНФ, причем единственная.

Пример нахождения СДНФ

Для того, чтобы получить СДНФ функции, требуется составить её таблицу истинности.

В ячейках строки́ отмечаются лишь те комбинации, которые приводят логическое выражение в состояние единицы.
Далее рассматриваются значения переменных при которых функция равна 1. Если значение переменной равно 0, то она записывается с инверсией. Если значение переменной равно 1, то без инверсии.

Первый столбец содержит 1 в указанном поле. Отмечаются значения всех четырёх переменных, это:

§ = 0

§ = 0

§ = 0

§ = 0

Нулевые значения — тут все переменные представлены нулями — записываются в конечном выражении инверсией этой переменной. Первый член СДНФ рассматриваемой функции выглядит так:
Переменные второго члена:

§ = 0

§ = 0

§ = 0

§ = 1

в этом случае будет представлен без инверсии:

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

Совершенная ДНФ этой функции:

СКНФ (Совершенная Конъюнктивная Нормальная Форма) — это такая КНФ, которая удовлетворяет трём условиям:

§ в ней нет одинаковых элементарных дизъюнкций

§ в каждой дизъюнкции нет одинаковых пропозициональных букв

§ каждая элементарная дизъюнкция содержит каждую пропозициональную букву из входящих в данную КНФ пропозициональных букв.

Пример нахождения СКНФ

Для того, чтобы получить СКНФ функции, требуется составить её таблицу истинности

В ячейках строки́ отмечаются лишь те комбинации, которые приводят логическое выражение в состояние нуля.

Четвертый столбец содержит 0 в указанном поле. Отмечаются значения всех четырёх переменных, это:

§ = 0

§ = 0

§ = 1

§ = 1

В дизъюнкцию записывается переменная без инверсии если она в наборе равна 0 и с инверсией если она равна 1. Первый член СКНФ рассматриваемой функции выглядит так:

Остальные члены СКНФ составляются по аналогии.

 

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

СДНФ (Совершенная Дизъюнктивная Нормальная Форма) — это такая ДНФ, которая удовлетворяет трём условиям:

§ в ней нет одинаковых элементарных конъюнкций

§ в каждой конъюнкции нет одинаковых пропозициональных букв

§ каждая элементарная конъюнкция содержит каждую пропозициональную букву из входящих в данную ДНФ пропозициональных букв, причем в одинаковом порядке.

Для любой функции алгебры логики существует своя СДНФ, причем единственная.

Пример нахождения СДНФ

Для того, чтобы получить СДНФ функции, требуется составить её таблицу истинности.

В ячейках строки́ отмечаются лишь те комбинации, которые приводят логическое выражение в состояние единицы.
Далее рассматриваются значения переменных при которых функция равна 1. Если значение переменной равно 0, то она записывается с инверсией. Если значение переменной равно 1, то без инверсии.

Первый столбец содержит 1 в указанном поле. Отмечаются значения всех четырёх переменных, это:

§ = 0

§ = 0

§ = 0

§ = 0

Нулевые значения — тут все переменные представлены нулями — записываются в конечном выражении инверсией этой переменной. Первый член СДНФ рассматриваемой функции выглядит так:
Переменные второго члена:

§ = 0

§ = 0

§ = 0

§ = 1

в этом случае будет представлен без инверсии:

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

Совершенная ДНФ этой функции:

 

Полнота системы булевых функций. Примеры полных систем.

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