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

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

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

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

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

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

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

Пример.

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

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