Учебное пособие 1203

ключение импликации и эквиваленции);

10.X Y X Y (исключение дизъюнкции);

11.X Y X Y (исключение конъюнкции);

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

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

Задача 1. Упростить ПФ X Y Z X Y X Y , используя равносильные преобразования.

Решение.

1) Применим дистрибутивный закон, получим

X Y Z X Y X Y X Y (Z 1) X Y . 2) Так как Z 1 1, то получим

X Y (Z 1) X Y X Y X Y.

3) По дистрибутивному закону

XY X Y Y (X X).

4)Так как X 1 1, Y 1 Y , то получим

X Y X Y Y 1 Y .

Таким образом, X Y Z X Y X Y Y.

29

Замечание. Шаги 1-2 в решении можно заменить одним шагом, если использовать закон поглощения

(X Y Z) (X Y) (X Y) X Y X Y .

Задача 2. Составить таблицу истинности ПФ и опреде-

лить тип ПФ X Y ZY.

Решение. Составим таблицу истинности ПФ

F(X,Y,Z) X Y Z Y.

F(X,Y,Z) X Y ZY является выполнимой.

Задание 4

Упростить ПФ, используя равносильные преобразования. Варианты

1.(X Y) (X Y).

2.(Y X) Y (X Y).

3.X X Z X Z X Y .

4.((X Y) X) (X (X Y)).

5.X Y Z X Y Z Y Z .

6.(X Y) (X Y).

30

7.X (X Y).

8.X Y Z Y Z X .

9.(X Y Z) (X Z).

10.(X Y) (Y Z) (Z X).

11.(X Y) (Y Z) (Z X).

12.(Y X) Y (X Y).

13.X X Z X Z X Y .

14.((X Y) X) (X (X Y)).

15.X Y Z X Y Z Y Z .

16.(X Y Z) (X Z).

17.X Y Z X Y X Y .

18.(X Y) (X Y).

19.(X Y) (X Y).

20.(X Y) (Y Z) (Z X).

Задание 5

Составить таблицу истинности ПФ и определить тип ПФ. Варианты

31

4. НОРМАЛЬНЫЕ И СОВЕРШЕННЫЕ

НОРМАЛЬНЫЕ ФОРМЫ

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

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

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

Пример.

X Y Z - элементарная конъюнкция.

X Z - элементарная дизъюнкция.

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

Пример. X Y Z X Y Y Z - ДНФ.

32

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

Пример. (X Y Z) (X Y) - КНФ.

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

Алгоритм 4.1

(приведение ПФ к нормальной форме)

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

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

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

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

(X Y) Z .

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

(X Y) Z X Y Z X Y Z ДНФ.

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

(X Y ) Z (X Z) (Y Z) КНФ

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

Совершенной дизъюнктивной нормальной формой

(СДНФ) данной ПФ называется ДНФ, в которой каждая эле-

33

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

Совершенной конъюнктивной нормальной формой

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

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

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

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

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

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

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

ния.

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

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

имеет ДНФ вида X Z Y Z .

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

ную конъюнкцию умножим на 1 Y Y , а вторую – на 1 X X . Получим

34

X Z Y Z X Z (Y Y ) Y Z (X X)

X Z Y X Z Y Y Z X Y Z X

X Z Y X Z Y Y Z X СДНФ

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

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

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

–с отрицанием.

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

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

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

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

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

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

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

35

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

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

(X Y ) (Z X ) (X Y ) (Z X )

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

(X Y ) (Z X ) (X Y ) (Z X )

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

(X Y ) (Z X ) (X Y ) ((Z X ) (Z X ))

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

(X. Y ) ((Z X ) (Z X )) (X Y ) (Z X )

(Z X )

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

(X Y ) (Z X ) (Z X )

Спомощью равносильных преобразований приведем ПФ

кконъюнктивной нормальной форме (КНФ).

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

X X 1, Z Z 1, получим

(X Y) (Z X) (Z X) (X (Y Z)) (X Z)

((X Z) X) ((X Z) (Y Z)) ((X X) (X Z))

((Y Z X) (Y Z Z)) (X Z) (X Y Z) Y

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

(X Z) (X Y Z) Y .

36

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

СКНФ: (X Y Z) (X Y Z) (X Y Z).

СДНФ:

X Y Z X Y Z X Y Z X Y Z X Y Z .

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

СДНФ:

(X Y) (Z X) (Z X) X Y 1 Z X 1 Z X 1

X Y (Z Z) Z X (Y Y) Z X (Y Y)

(X Y Z) (X Y Z) (X Y Z) (X Y Z)

(X Y Z) (X Y Z (X Y Z) (X Y Z)

(X Y Z) (X Y Z) (X Y Z).

37

СКНФ:

(X Z) (X Y Z) Y (Y 0 0) (X Z 0) (X Y Z)

(Y (X X) (Z Z)) (X Z (Y Y)) (X Y Z)

(((Y X) (Y X)) (Z Z)) ((X Z Y) (X Z Y))

(X Y Z) (Y X Z) (Y X Z) (Y X Z)

(Y X Z) (X Z Y) (X Z Y) (X Y Z)

(X Y Z) (X Y Z) (X Y Z).

Задание 6

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

Варианты

38