Материал: Дискретная математика. учебное пособие. Собенина О.В

Итак, для любого набора значений переменных Х₁, Х₂, ..., Х_n левая и правая части равносильности совпадают, что и доказывает справедливость теоремы.

Пример. Для ПФ определить дизъюнктивное разложение по переменной Х₁.

С ледствие. Для любой ПФ и любого натурального k имеет место равносильность

,

называемая дизъюнктивным разложением по переменным .

Теорема 5.5.2. Для любой ПФ имеет место равносильность

называемая конъюнктивным разложением по переменной Х₁.

Доказательство теоремы 5.5.2 аналогично доказательству теоремы 5.5.1.

Пример. Для ПФ определить конъюнктивное разложение по переменной Х₁.

Следствие. Для любой ПФ и любого натурального k имеет место равносильность

,

называемая конъюнктивным разложением по переменным .

Таким образом, для любой ПФ существует равносильная ей, содержащая только константы 0 и 1, символы и переменные.

Определим некоторые канонические представления ПФ.

ПФ называется элементарной конъюнкцией (конъюнктом), если она является конъюнкцией переменных и отрицаний переменных (конъюнкцией литер).

ПФ называется элементарной дизъюнкцией (дизъюнктом), если она является дизъюнкцией переменных и отрицаний переменных (дизъюнкцией литер).

Пример.

, , , – элементарные конъюнкции.

, , – элементарные дизъюнкции.

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

Пример. – ДНФ.

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

Пример. – КНФ.

На основе равносильных преобразований любая формула может быть приведена к нормальной форме (ДНФ или КНФ) [3,4].

Алгоритм приведения ПФ к нормальным формам описывает следующая последовательность шагов.

1. Если ПФ содержит операции → и ↔, то их исключить с помощью равносильностей

, .

2. Привести отрицания к независимым переменным, используя законы де Моргана.

3. Раскрыть скобки по дистрибутивному закону конъюнкции относительно дизъюнкции для приведения к ДНФ или по дистрибутивному закону дизъюнкции относительно конъюнкции для приведения к КНФ.

Пример. Определить нормальные формы для ПФ .

Действуя, в соответствии с алгоритмом, получим ДНФ.

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

Замечание. Для ПФ представление в виде нормальных форм не единственно. Переход от одной формы к другой осуществляется на основе равносильных преобразований.

В отличие от нормальных форм представление в виде совершенных нормальных форм является единственным.

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

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

Существует два способа перехода к совершенным формам табличный и аналитический [2, 3, 4].

5.5.1. Аналитический способ приведения к сднф

Для приведения ПФ к СДНФ выполняются равносильные преобразования, описанные следующей последовательностью шагов.

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

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

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

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

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

Пример.

Пусть ПФ, содержащая переменные X, Y, Z, имеет ДНФ вида . Используя аналитический способ привести к СДНФ.

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

5.5.2. Табличный способ приведения к сднф

Используя таблицу истинности, можно составить СДНФ для ПФ. Для этого надо выполнить следующую последовательность шагов.

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

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

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

Пример. Привести ПФ к СДНФ. Построим таблицу истинности и на ее основе составим СДНФ.

СДНФ примет вид

.

5.5.3. Табличный способ приведения к скнф

Используя таблицу истинности, можно составить СКНФ для ПФ. Для этого надо выполнить следующую последовательность шагов.

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

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

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

Пример. Привести ПФ к СКНФ. Построим таблицу истинности и на ее основе составим СКНФ.