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

UptoLike

ВУЗ: 

МУМ | Москва

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

Рубрика: 

Рас су ж да ем от про тив но го: F ® Лож но, то есть най дут ся та кие пе -
ре мен ные (оцен ки), что F = Л, та ким об ра зом B = Л, а сле ва все скоб ки
® И. Сле до ва тель но: (A É B)=И; (A Ú C)=И; (C É ØD)= И; D = И. Из
(C É ØD) = И, так как D = Л, сле ду ет C = Л. Из (A Ú C) = И сле ду ет
(A Ú Л)=И , то есть A = И. Из (A É B)=И сле ду ет (И É B)=И, то есть B=И.
То есть мы по лу чим, что за ра бот ная пла та вы со ка — это ис ти на
(B = И), а пред по ла га ли, что это ложь: B = Л. Та ким об ра зом, мы по лу -
чи ли про ти во ре чие, зна чит, на ша фор му ла то ж де ст вен но-ис тин на и
рассуждение является правильным.
13) Двой ст вен ность.
Сим во лы &, Ú на зы ва ют ся двой ст вен ны ми друг дру гу. Фор му ла A*
на зы ва ет ся двой ст вен ной фор му ле A, ес ли она по лу че на из A од но вре -
мен ной за ме ной всех сим во лов &, Ú на двой ст вен ные. Оче вид но, что
(A*)* = A.
При мер: фор му ла X
1
& (X
2
Ú X
1
) двой ст вен на фор му ле X
1
Ú (X
2
& X
1
).
Пра ви ло 1. Пусть (X
i
, ..., X
i
) — спи сок пе ре мен ных, а (s
1
, ..., s
k
) —
его оцен ка. На зо вем оцен ку (t
1
, ..., t
k
) двой ст вен ной оцен ке (s
1
, ..., s
k
), ес -
ли она по лу ча ет ся из (s
1
, ..., s
k
) за ме ной всех И на Л и Л на И.
Пусть A — фор му ла, а (X
i
, ..., X
i
) — спи сок ее пе ре мен ных. То гда
A при ни ма ет зна че ние И на оцен ке (s
1
, ..., s
k
) в том и толь ко в том слу чае,
ес ли A* при ни ма ет зна че ние Л на оцен ке (t
1
, ..., t
k
), двой ст вен ной оцен ке
(s
1
, ..., s
k
).
Пра ви ло 2. (Прин цип двой ст вен но сти). Ес ли A = B, то A* = B*. Это
мож но ис поль зо вать для на хо ж де ния но вых рав но силь но стей: из рав но -
силь но сти: X
i
& (X
j
Ú X
k
) = (X
i
& X
j
) Ú (X
i
& X
k
) мож но по лу чить:
X
i
Ú (X
j
& X
k
) = (X
i
Ú X
j
) & (X
i
Ú X
k
).
1.5.7 Нор маль ная фор ма фор мул
1) В си лу ас со циа тив но сти опе ра ций & и Ú, как бы мы не рас став -
ля ли скоб ки в вы ра же ни ях A
1
& A
2
& ... & A
k
; A
1
Ú A
2
Ú ...Ú A
k
все гда бу дем
при хо дить к рав но силь ным фор му лам.
Бу дем счи тать ка ж дое из этих вы ра же ний фор му лой и на зы вать
со от вет ст вен но мно го член ной конъ юнк ци ей и дизъ юнк ци ей фор мул
A
1
... A
k
.
Для этих фор мул не труд но по лу чить рав но силь но сти, вы ра жаю -
щие обоб щен ную ди ст ри бу тив ность:
39
      Рассуждаем от противного: F ® Ложно, то есть найдутся такие пе-
ременные (оценки), что F = Л, таким образом B = Л, а слева все скобки
® И. Сле до ва тель но: (A É B)=И; (A Ú C)=И; (C É ØD)= И; D = И. Из
(C É ØD) = И, так как D = Л, следует C = Л. Из (A Ú C) = И следует
(A Ú Л)=И , то есть A = И. Из (A É B)=И следует (И É B)=И, то есть B=И.
      То есть мы получим, что заработная плата высока — это истина
(B = И), а предполагали, что это ложь: B = Л. Таким образом, мы полу-
чили противоречие, значит, наша формула тождественно-истинна и
рассуждение является правильным.

         13) Двойственность.
         Символы &, Ú называются двойственными друг другу. Формула A*
называется двойственной формуле A, если она получена из A одновре-
менной заменой всех символов &, Ú на двойственные. Очевидно, что
(A*)* = A.
         Пример: формула X1 & (X2 Ú X1) двойственна формуле X1 Ú (X2 & X1).
         Правило 1. Пусть (Xi, ..., Xi) — список переменных, а (s1, ..., sk) —
его оценка. Назовем оценку (t1, ..., tk) двойственной оценке (s1, ..., sk), ес-
ли она получается из (s1, ..., sk) заменой всех И на Л и Л на И.
         Пусть A — формула, а (Xi, ..., Xi) — список ее переменных. Тогда
A принимает значение И на оценке (s1, ..., sk) в том и только в том случае,
если A* принимает значение Л на оценке (t1, ..., tk), двойственной оценке
(s1, ..., sk).
         Правило 2. (Принцип двойственности). Если A = B, то A* = B*. Это
можно использовать для нахождения новых равносильностей: из равно-
сильности: Xi & (Xj Ú Xk) = (Xi & Xj) Ú (Xi & Xk) можно получить:
Xi Ú (Xj & Xk) = (Xi Ú Xj) & (Xi Ú Xk).

      1.5.7 Нормальная форма формул

        1) В силу ассоциативности операций & и Ú, как бы мы не расстав-
ляли скобки в выражениях A1 & A2 & ... & Ak; A1 Ú A2 Ú ...Ú Ak всегда будем
приходить к равносильным формулам.
        Будем считать каждое из этих выражений формулой и называть
соответственно многочленной конъюнкцией и дизъюнкцией формул
A1 ... Ak.
        Для этих формул нетрудно получить равносильности, выражаю-
щие обобщенную дистрибутивность:
                                                                            39

Страницы