A) элементтері болса 6 страница

 

Пример 2.3.4.

Конъюнкция любого числа элементарных дизъюнкций называется конъюнктивной нормальной формой (КНФ).

 

Пример 2.3.5.

;

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

Пример 2.3.6.

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

Пример 2.3.7.

 

2.4 Преобразование функций алгебры логики

в СДНФ и СКНФ.

 

В пункте 1.6.1 с помощью теоремы (1.4) была показана возможность представлять любую функцию общей алгебры логики в базисе {И, ИЛИ, НЕ}. Можно использовать ту же самую теорему, чтобы доказать более сильное утверждение: любую функцию алгебры логики можно представить в СНДФ и СКНФ. Для доказательства используем две аналитические формулировки этой теоремы.

(2.20)

(2.21)

Справедливость этой теоремы доказывается путём подстановки и . В результате предлагаемой подстановки (2.20) и (2.21) превращаются в тождества и, тем самым, доказывая справедливость этих равенств. Правая часть (2.20) и (2.21) есть результат разложения функции по переменной . В свою очередь, полученный результат можно дополнительно разложить по переменной . Если такую процедуру довести до конечного разложения по переменной , получим СДНФ и СКНФ. Для функции трёх переменных рассматриваемое разложение в СДНФ принимает вид (2.22) (2.22)

Такое же разложение, но в СКНФ по (2.21), представляет (2.23).

(2.23)

Естественно, что (2.22) будут составлять только те логические слагаемые, для которых (согласно аксиоме 7), а, в (2.23) останутся только те логические сомножители, для которых (согласно аксиоме 2).

Представим рассматриваемую функцию в табличной форме (табл. 2.4.1). Совместный визуальный анализ этой таблицы с (2.22),

Таблица 2.4.1  
№ x1 x2 x3

затем, с (2.23) даёт возможность сформулировать правило преобразования табличной формы представления логической функции в СДНФ и СКНФ.

Для получения СДНФ необходимо выполнить следующие действия.

1) Выделить строки таблицы истинности, для которых функция имеет значение « 1» (истина). Каждой выделенной строке будет соответствовать логическое слагаемое (минтерм) СДНФ.

2) Построить каждое логическое слагаемое СДНФ в виде логического произведений полного набора логических переменных . Причём, в таком произведении лагаемыеических произведений полного набора логических переменныхоторыхзаписывается в прямой форме (то есть ), если в левой части таблицы (в строке соответствующей рассматриваемому слагаемому) . Иначе, записывается в инверсной форме (то есть), если .

Для получения СКНФ необходимо выполнить следующие действия.

1) Выделить строки таблицы истинности, для которых функция имеет значение « 0 » (ложь). Каждой выделенной строке будет соответствовать логический сомножитель (элементарная дизъюнкция) СКНФ.

2) Построить каждый логический сомножитель СКНФ в виде лоческой суммы полного набора логических переменных . Причём, в такой сумме записывается в прямой форме (то есть ), если в левой части таблицы (в строке соответствующей рассматриваемому сомножителю) . Иначе, записывается в инверсной форме (то есть ), если .

Пример 2.4.1.

x1 x2 x3 y
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1

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

Тогда

СДНФ функции : ,

СКНФ функции : .

Справедливость полученных результатов может быть проверена обратным преобразованием.

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

 

Пример 2.4.2.

Задана функция

Надо преобразовать её в СДНФ.

x3 x2 x1 a b x3 y
1 1 1 0 1 0 0
1 1 1 0 1 0 0
0 1 0 1 0 1 0
0 1 0 1 1 0 0
1 0 0 1 1 0 0
1 0 0 1 1 0 0
0 0 1 0 0 1 1
0 0 1 0 1 0 0

В соответствии с рангами операций проведём последовательное преобразование функции в табличную форму. Обозначим