Дизъюнктивная и конъюнктивная нормальные формы

Введем обозначение

,

где – параметр, равный либо 0, либо 1. Очевидно, что

Легко видеть, что 1 тогда и только тогда, когда .

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

, (1)

где дизъюнкция берется по всевозможным наборам значений переменных .

Это представление называется разложением функции по переменным .

Доказательство. Рассмотрим произвольный набор значений переменных и покажем, что левая и правая части соотношения (1) принимают на нем одно и то же значение. Левая часть дает . Правая –

В качестве следствий из теоремы рассмотрим два специальных случая разложения.

1) Разложение по переменной:

.

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

2) Разложение по всем переменным:

.

При тождественно не равной 0 оно может быть преобразовано:

.

В результате окончательно получим

. (2)

Такое разложение называется совершенной дизъюнктивной нормальной формой (совершенной д. н. ф.).

Непосредственно к понятию совершенной д. н. ф. примыкает следующая теорема.

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

Доказательство.1) Пусть . Тогда, очевидно,

.

2) Пусть тождественно не равна 0. Тогда ее можно представить формулой (2).

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

Пример 3. Найти совершенную д. н. ф. для функции .

0 0
0 1
1 0
1 1

.

Совершенная д. н. ф. есть выражение типа П. Покажем, что при тождественно не равной 1 ее можно представить в виде . Запишем для двойственной функции (очевидно не равной тождественно 0) разложение в виде совершенной д. н. ф.:

.

Из принципа двойственности следует

.

Таким образом, получаем разложение, которое называется совершенной конъюнктивной нормальной формой (совершенной к. н. ф.):

. (3)

Пример 4. Построить совершенную к. н. ф. для функции .

Имеем .

Полнота и замкнутость. Примеры функционально полных систем

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

Примеры полных систем.

1) Система – множество всех булевых функций.

2) Система

Очевидно, что не каждая система является полной, например, система не полная. Следующая теорема позволяет сводить вопрос о полноте одних систем к вопросу о полноте других систем.

Теорема. Пусть даны две системы функций из :

, ,

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

Доказательство. Пусть – произвольная функция из . В силу полноты системы можно выразить формулой над , т. е. .

По условию теоремы

, , …, .

Поэтому в формуле можно исключить вхождения функций , заменив их формулами над :

,

То есть мы выразили в виде формулы над . Теорема доказана.

Опираясь на эту теорему, можно установить полноту еще ряда систем и тем самым расширить список примеров полных систем.

3) Система является полной. Для доказательства возьмем за систему систему 2), а за систему – систему 3) и используем тождество

.

4) Система является полной. Доказательство аналогично предыдущему, либо через принцип двойственности.

5) Система является полной. Для доказательства возьмем за систему систему 3), а за систему – систему 5). Тогда

, .

6) Система является полной. Для доказательства возьмем за систему систему 3), а за систему – систему 6). Имеем

.

С понятием полноты тесно связано понятие замыкания и замкнутого класса.

Пусть – некоторое подмножество функций из . Замыканием называется множество всех булевых функций, представимых в виде формул через функции множества . Замыкание множества обозначается через . Очевидно, что замыкание инвариантно относительно операций введения и удаления фиктивных переменных.

Свойства замыкания:

1) ;

2) ;

3) если , то ;

4) .

Класс (множество) называется функционально замкнутым, если .

Очевидно, что всякий класс будет замкнутым.Это дает возможность получать многочисленные применения замкнутых классов.

В терминах замыкания и замкнутого класса можно дать другое определение полноты, эквивалентное исходному: – полная система, если .