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

UptoLike

ВУЗ: 

МУМ | Москва

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

Рубрика: 

а) (A
1
& A
2
& ... & A
k
) Ú (B
1
& B
2
& ... & B
l
) = (A
1
Ú B
1
) & (A
1
Ú B
2
) &
& ... & (A
1
Ú B
l
) & (A
2
Ú B
1
) & (A
2
Ú B
2
) & ... & (A
2
Ú B
l
) & ... & (A
k
ÚB
1
) &
& (A
k
Ú B
2
) & ... & (A
k
Ú B
l
);
б) (A
1
Ú A
2
Ú ... Ú A
k
) & (B
1
Ú B
2
Ú ... Ú B
l
) = (A
1
& B
1
) Ú (A
1
& B
2
) Ú
Ú ... Ú (A
1
& B
l
) Ú (A
2
& B
1
) Ú (A
2
& B
2
) Ú ... Ú (A
2
& B
l
) Ú ... Ú (A
k
& B
1
) Ú
Ú (A
k
& B
2
) Ú ... Ú (A
k
& B
l
);
а так же име ет ме сто обоб щен ный за кон де Мор га на:
а) Ø(A
1
& ... & A
k
) = ØA
1
Ú ... Ú ØA
k
;
б) Ø(A
1
Ú ... Ú A
k
) = ØA
1
& ... & ØA
k
;
2) Фор му лу на зы ва ют эле мен тар ной конъ юнк ци ей, ес ли она яв ля -
ет ся конъ юнк ци ей пе ре мен ных и от ри ца ний пе ре мен ных (конъ юнк ция
мо жет быть и од но член ной).
При меры.
а) X
2
; ØX
3
; X
2
& ØX
3
; X
2
& X
3
; X
1
& ØX
2
& X
4
& X
2
.
б) X
1
& X
2
& X
3
— то есть не обя за тель но ре гу ляр ное че ре до ва ние
пе ре мен ных и их от ри ца ний.
3) Го во рят, что фор му ла на хо дит ся в дизъ юнк тив ной нор маль ной
фор ме (ДНФ), ес ли она яв ля ет ся дизъ юнк ци ей эле мен тар ных конъ юнк -
ций (ДНФ мо жет быть и од но член ной).
При мер. X
2
; ØX
3
; (X
1
& X
2
& X
3
); (X
1
& X
2
& ØX
3
) Ú (X
1
& ØX
2
& X
3
).
Пра ви ло при ве де ния к ДНФ: Для лю бой фор му лы A мож но най ти
та кую фор му лу B, на хо дя щую ся в ДНФ, что A = B.
1 этап: для фор му лы A стро им та кую фор му лу A
1
, что A = A
1
и в A
1
не со дер жит ся сим во лов ~, É.
2 этап: для фор му лы A
1
на хо дим та кую фор му лу A
2
, что A
1
= A
2
и в
A
2
от ри ца ние на хо дит ся толь ко пе ред пе ре мен ны ми. Та кая фор ма на зы -
ва ет ся фор му лой с «тес ны ми» от ри ца ния ми. Здесь ис поль зу ют ся за ко -
ны де Мор га на и унич то же ния пар стоя щих ря дом от ри ца ний:
При мер. Ø[ØØ(X
1
& ØX
2
) Ú (X
2
& ØX
1
)] = (Ø Ø ØX
1
& X
2
) & Ø(X
2
&
& ØX
1
) = Ø(X
1
& ØX
2
) & (ØX
2
Ú ØØX
1
) = (ØX
1
Ú ØØX
2
) & (ØX
2
Ú X
1
) =
= (ØX
1
Ú X
2
) & (ØX
2
Ú X
1
).
3 этап: A
2
— то фор му ла из пе ре мен ных и их от ри ца ний в фор ме
мно го член ной конъ юнк ции и дизъ юнк ции. Те перь, при ме нив обоб -
щен ную ди ст ри бу тив ность & от но си тель но Ú, по сле до ва тель но пре об -
ра зу ем по лу чен ную фор му лу (пом ним, что Ú — ана ло гич на сло же нию,
& — ум но же нию).
40
       а) (A1 & A2 & ... & Ak) Ú (B1 & B2 & ... & Bl) = (A1 Ú B1) & (A1 Ú B2) &
& ... & (A1 Ú Bl) & (A2 Ú B1) & (A2 Ú B2) & ... & (A2 Ú Bl) & ... & (AkÚB1) &
& (Ak Ú B2) & ... & (Ak Ú Bl);
       б) (A1 Ú A2 Ú ... Ú Ak) & (B1 Ú B2 Ú ... Ú Bl) = (A1 & B1) Ú (A1 & B2) Ú
Ú ... Ú (A1 & Bl) Ú (A2 & B1) Ú (A2 & B2) Ú ... Ú (A2 & Bl) Ú ... Ú (Ak & B1) Ú
Ú (Ak & B2) Ú ... Ú (Ak & Bl);
       а также имеет место обобщенный закон де Моргана:
       а) Ø(A1 & ... & Ak) = ØA1 Ú ... Ú ØAk;
       б) Ø(A1 Ú ... Ú Ak) = ØA1 & ... & ØAk;

      2) Формулу называют элементарной конъюнкцией, если она явля-
ется конъюнкцией переменных и отрицаний переменных (конъюнкция
может быть и одночленной).
      Примеры.
      а) X2; ØX3; X2 & ØX3; X2 & X3; X1 & ØX2 & X4 & X2.
      б) X1 & X2 & X3 — то есть не обязательно регулярное чередование
переменных и их отрицаний.

      3) Говорят, что формула находится в дизъюнктивной нормальной
форме (ДНФ), если она является дизъюнкцией элементарных конъюнк-
ций (ДНФ может быть и одночленной).
      Пример. X2; ØX3; (X1 & X2 & X3); (X1 & X2 & ØX3) Ú (X1 & ØX2 & X3).
      Правило приведения к ДНФ: Для любой формулы A можно найти
такую формулу B, находящуюся в ДНФ, что A = B.
      1 этап: для формулы A строим такую формулу A1, что A = A1 и в A1
не содержится символов ~, É.
      2 этап: для формулы A1 находим такую формулу A2, что A1 = A2 и в
A2 отрицание находится только перед переменными. Такая форма назы-
вается формулой с «тесными» отрицаниями. Здесь используются зако-
ны де Моргана и уничтожения пар стоящих рядом отрицаний:
      Пример. Ø[ØØ(X1 & ØX2) Ú (X2 & ØX1)] = (Ø Ø ØX1 & X2) & Ø(X2 &
& ØX1) = Ø(X1 & ØX2) & (ØX2 Ú ØØX1) = (ØX1 Ú ØØX2) & (ØX2 Ú X1) =
= (ØX1 Ú X2) & (ØX2 Ú X1).
      3 этап: A2 — то формула из переменных и их отрицаний в форме
многочленной конъюнкции и дизъюнкции. Теперь, применив обоб-
щенную дистрибутивность & относительно Ú, последовательно преоб-
разуем полученную формулу (помним, что Ú — аналогична сложению,
& — умножению).
40

Страницы