Алгоритм 6.2

(аналитический способ приведения к СДНФ)

1. С помощью равносильных преобразований привести ПФ к ДНФ.

2. Те элементарные конъюнкции, в которые сомножителями входят не все переменные, умножить на единицы, представленные в виде дизъюнкций каждой недостающей переменной с ее отрицанием.

3. Раскрыть скобки по соответствующему дистрибутивному закону.

4. Для получения искомой СДНФ исключить повторения.

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

Пример. Пусть ПФ, содержащая переменные X, Y, Z, имеет ДНФ вида .

Заметим, что в первую элементарную конъюнкцию не входит переменная Y, а во вторую – переменная Х. В соответствии с процедурой приведения к СНДФ первую элементарную конъюнкцию умножим на , а вторую – на . Получим

Алгоритм 6.3

(табличный способ приведения к СДНФ)

1. Составляется таблица истинности данной ПФ.

2. Рассматриваются те строки, в которых формула принимает истинностное значение 1. Каждой такой строке ставится в соответствие элементарная конъюнкция, причем переменная, принимающая значение 1, входит в нее без отрицания, а 0 – с отрицанием.

3. Образуется дизъюнкция всех полученных элементарных конъюнкций, которая и составляет СДНФ.

Алгоритм 6.4

(табличный способ приведения к СКНФ)

1. Составляется таблица истинности данной ПФ.

2. Рассматриваются те строки, в которых формула принимает истинностное значение 0. Каждой такой строке ставится в соответствие элементарная дизъюнкция, причем переменная, принимающая значение 1, входит в нее с отрицанием, а 0 – без отрицания.

4. Образуется конъюнкция всех полученных элементарных дизъюнкций, которая и составляет СКНФ.

Пример решения задачи

Задача. Привести ПФ к нормальным и совершенным нормальным формам.

Решение. С помощью равносильных преобразований, согласно алгоритма 6.1, приведем ПФ к дизъюнктивной нормальной форме (ДНФ).

1) Исключим операцию импликацию (®), получим

2) Исключим операцию сложение по модулю два (Å), получим.

3) Исключим операцию эквиваленцию («), получим

4) Применив закон де Моргана, получим

.

Таким образом, искомая ДНФ имеет вид

С помощью равносильных преобразований приведем ПФ к конъюнктивной нормальной форме (КНФ).

Используя дистрибутивный закон и равносильности , , получим

Таким образом, искомая КНФ имеет вид

.

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

X	Y	Z			F	Элементарные конъюнкции	Элементарные дизъюнкции

СКНФ: .

СДНФ:

.

Приведем к СДНФ, СКНФ с помощью аналитического способа.

СДНФ:

СКНФ:

Поиск по сайту: