Лекции ДМ

Полная система. Достаточное условие полноты.

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

Эти функции можно рассматривать как систему элементарных функций, через которые выражается любая булева функция.

Возникает вопрос: в какой мере является случайным наличие таких систем элементарных функций?

Дадим определение таких систем.

Система булевых функций {f₁, f₂, …, f_m} называется полной, если любая булева функция может быть выражена через функции этой системы с помощью составления из них сложных функций.

Составление сложных функций из элементарных функций системы называется суперпозицией.

Познакомимся с достаточным условием полноты системы.

Пусть система функций {f₁, f₂, …, f_m} (I) полная и любая из функций этой системы может быть выражена через функции g₁, g₂, …, g_l , тогда система { g₁, g₂, …, g_l}(II) тоже полная.

Докажем полноту следующих систем: {-, V, }, {-, V}, {-, }, {-, }, {x|y}, {xy}, {0, 1, V, , +}.

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

Опираясь на достаточное условие полноты докажем, что вторая систем тоже полная. За полную систему примем {-, V, }. Выразим функции этой системы через отрицание и дизъюнкцию. Нужно выразить только конъюнкцию: следовательно , система {-, V} полная.

С помощью той же полной системы докажем полноту {-, }. Для этого нужно выразить дизъюнкцию:

Для доказательства полноты системы {-, }воспользуемся полной системой {-, V}. Выразим дизъюнкцию: Полнота доказана.

Для доказательства полноты системы {x|y} за полную примем, например, {-, }. Выразим отрицание и конъюнкцию через штрих Шеффера:

Полнота доказана.

При доказательстве полноты системы {xy} за полную систему примем {-, V}. Выразим обе функции через стрелку Пирса:

Полнота доказана.

Полноту системы можно доказать , опираясь на то, что любая булева функция представима в виде полинома, или доказав с помощью достаточного условия. Воспользуемся полной системой {-, }. Выразим 0, 1 и + через отрицание и конъюнкцию:

Содержание