Математика. Раздел 1. Дискретная математика. Тетрадь 1.2. Казанцев Э.Ф. - 41 стр.

UptoLike

ВУЗ: 

МУМ | Москва

Составители: 

Рубрика: 

Про дол жа ем на ча тый при мер:
(Ø X
1
Ú X
2
) & (ØX
2
Ú X
1
) = (ØX
1
& ØX
2
) Ú (ØX
1
& X
1
) Ú(X
2
& ØX
2
) Ú
Ú (X
2
& X
1
), т.е. по лу чи ли фор му лу, на хо дя щую ся в ДНФ.
4) Го во рят, что фор му ла A на хо дит ся в конъ юк тив ной нор маль ной
фор ме (КНФ), ес ли фор му ла A* оп ре де ле на (то есть в A нет сим во лов ~
и É) и на хо дит ся в ДНФ.
Фор му лу на зы ва ют эле мен тар ной дизъ юнк ци ей, ес ли она яв ля ет ся
дизъ юнк ци ей пе ре мен ных и от ри ца ний пе ре мен ных (дизъ юнк ция
может быть и одночленной).
Та ким об ра зом фор му ла на хо дит ся в КНФ, ес ли она яв ля ет ся
конъ юнк ци ей эле мен тар ных дизъюнкций.
Пра ви ло при ве де ния к КНФ: Для лю бой фор му лы A мож но най ти
та кую фор му лу B, что A на хо дит ся в КНФ и A = B.
Фор му ла B на зы ва ет ся конъ юнк тив ной нор маль ной фор мой фор -
му лы A.
Со вер шен ная дизъ юнк тив ная нор маль ная фор ма
Оче вид но, что ДНФ не яв ля ет ся од но знач но оп ре де лен ной. На -
при мер, фор му ла X
1
Ú (X
2
& X
3
) уже на хо дит ся в ДНФ. В то же вре мя,
сде лав пре об ра зо ва ние: X
1
Ú (X
2
& X
3
) º (X
1
Ú X
2
) & (X
1
Ú X
3
) º (X
1
& X
1
) Ú
Ú (X
1
& X
3
) Ú (X
2
& X
1
) Ú (X
2
& X
3
) мы по лу чим дру гую ДНФ. Ко неч но, все
ДНФ дан ной фор му лы бу дут рав но силь ны. Свой ст вом един ст вен но -
сти об ла да ет, так на зы вае мая, со вер шен ная дизъ юнк тив ная нор маль -
ная фор ма. Го во рят, что фор му ла А на хо дит ся в со вер шен ной дизъ -
юнк тив ной нор маль ной фор ме (СДНФ), ес ли вы пол ня ют ся сле дую -
щие ус ло вия:
а) фор му ла А на хо дит ся в ДНФ;
б) ка ж дый дизъ юнк тив ный член фор му лы А яв ля ет ся k-член ной
конъ юнк ци ей, при чем на l-ом мес те (
1 £ £l k
) этой конъ юнк ции сто ит
ли бо пе ре мен ная Х, ли бо ее от ри ца ние ØХ;
в) все дизъ юнк тив ные чле ны фор му лы А по пар но раз лич ны.
При мер: 1) X
1
& ØX
2
& ØX
3
;
2) (X
1
& X
2
& X
3
) Ú (ØX
1
& X
2
& X
3
) Ú (X
1
& X
2
& ØX
3
).
Пра ви ла по лу че ния СДНФ:
1) для фор му лы А по лу ча ем лю бую ДНФ;
2) из ДНФ фор му лы А пу тем пре об ра зо ва ний по лу ча ем СДНФ
сле дую щим образом:
41
       Продолжаем начатый пример:
       (ØX 1 Ú X 2) & (ØX 2 Ú X 1) = (ØX 1 & ØX 2) Ú (ØX 1 & X 1) Ú(X 2 & ØX 2) Ú
Ú (X 2 & X 1), т.е. по лу чи ли фор му лу, на хо дя щую ся в ДНФ.

      4) Говорят, что формула A находится в конъюктивной нормальной
форме (КНФ), если формула A* определена (то есть в A нет символов ~
и É) и находится в ДНФ.
      Формулу называют элементарной дизъюнкцией, если она является
дизъюнкцией переменных и отрицаний переменных (дизъюнкция
может быть и одночленной).
      Таким образом формула находится в КНФ, если она является
конъюнкцией элементарных дизъюнкций.
      Правило приведения к КНФ: Для любой формулы A можно найти
такую формулу B, что A находится в КНФ и A = B.
      Формула B называется конъюнктивной нормальной формой фор-
мулы A.
      Совершенная дизъюнктивная нормальная форма
      Очевидно, что ДНФ не является однозначно определенной. На-
пример, формула X1 Ú (X2 & X3) уже находится в ДНФ. В то же время,
сделав преобразование: X1 Ú (X2 & X3) º (X1 Ú X2) & (X1 Ú X3) º (X1 & X1) Ú
Ú (X1 & X3) Ú (X2 & X1) Ú (X2 & X3) мы получим другую ДНФ. Конечно, все
ДНФ данной формулы будут равносильны. Свойством единственно-
сти обладает, так называемая, совершенная дизъюнктивная нормаль-
ная форма. Говорят, что формула А находится в совершенной дизъ-
юнктивной нормальной форме (СДНФ), если выполняются следую-
щие условия:
      а) формула А находится в ДНФ;
      б) каждый дизъюнктивный член формулы А является k-членной
конъюнкцией, причем на l-ом месте (1 £ l £ k) этой конъюнкции стоит
либо переменная Х, либо ее отрицание ØХ;
      в) все дизъюнктивные члены формулы А попарно различны.
      Пример: 1) X1 & ØX2 & ØX3;
                   2) (X1 & X2 & X3) Ú (ØX1 & X2 & X3) Ú (X1 & X2 & ØX3).
      Правила получения СДНФ:
      1) для формулы А получаем любую ДНФ;
      2) из ДНФ формулы А путем преобразований получаем СДНФ
следующим образом:
                                                                              41

Страницы