Логика. Радько О.Ю. - 31 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

= П2 * ¬П1 * П1 ∨ П2 * ¬П1 * ¬П2 ∨ ¬П2 * П1 * П1 ∨ ¬П2 * П1 * П2 =
= П1 * ¬П2.
Замечание: жирным шрифтом здесь отмечены нулевые конъюнкции, ∨ – знак операции дизъюнкция, * –
знак операции конъюнкция, ¬ – знак операции отрицания.
С учётом введённых обозначений для переменных П1 и П2 (П1 – «Принцесса находится в первой комна-
те», П2 – «Принцесса находится во второй комнате») и полученной в результате преобразований формуле П1 *
¬П2 можем сформулировать ответ на вопрос задачи – «Принцесса находится в первой комнате».
Элементарной конъюнкцией называется конъюнкция, состоящая только из переменных или их отрица-
ний. Например: DCBA .
Дизъюнктивно-нормальной формой (ДНФ) называется дизъюнкция элементарных конъюнкций. Напри-
мер: CBBABCBCACBAA ∨∨∨ .
Если учесть, что нулевые конъюнкции можно опустить, а А * А = А, то приведённая ДНФ сведётся к более
простому виду:
CBABCBA ∨∨
. Дальнейшее упрощение получается с помощью законов поглоще-
ния:
CBABAC ∨∨
. Но полученная формула ещё не является минимальной. Можно применить правило, осно-
ванное на соображениях симметрии: в рассматриваемой формуле каждая из переменных А, В, встречается два
раза, но переменная В встречается один раз с отрицанием, а один раз без отрицания. Значит, симметрия нару-
шена по переменной В. Тогда тот член дизъюнкции, который эту переменную В не содержит, пропадёт, т.е. по-
глотится АС.
Покажем, что это действительно так:
=∨∨=∨∨ CBABACCBABAC 1*
CBABCBABCBAABCCBABBBAC ∨=∨∨∨=∨∨∨= )(
(по закону поглощения
A
B
AA =∨
).
Мы доказали следующее правило поглощения.
Если ДНФ является трёхчленом, зависящим от трёх переменных, и если симметрия нарушена толь-
ко по одной из переменных, то пропадает тот член дизъюнкции, который эту переменную не содержит.
Проиллюстрируем это правило ещё на двух примерах.
1.
BD
D
A
B
A
∨∨
. Этот трёхчлен содержит два раза
A
, два раза B, но один раз D и один раз
D
. Значит,
симметрия нарушена по D. Поэтому, согласно нашему правилу, пропадает член, не содержащий букву D (т.е. не
содержащий ни D, ни
D
). Значит, надо вычеркнуть AB.
2. DCDBCB ∨∨ . Этот трёхчлен содержит два раза
B
, два раза
D
, но один раз C и один раз C . Сим-
метрия нарушена по C. Значит, вычёркиваем член, не содержащий C, т.е. вычёркиваем BD.
Минимальной мы назовём ту ДНФ, которая имеет самую короткую запись.
Существует ещё одно правило поглощения, которое тоже основано на соображениях симметрии:
Если ДНФ является трёхчленом, зависящим от трёх переменных, и если симметрия нарушена по
двум из этих переменных, то данная ДНФ равносильна дизъюнкции, одним из членов которой является
переменная, по которой симметрия не нарушена, а вторым членом служит тот член первоначальной
ДНФ, который эту переменную не содержит.
Например: CBAACCBAB ∨=∨∨ . Покажем, что это действительно так:
CBACBACBCBA
CBCBACBAACCBAB
∨=∨∨=∨∨∨=
=∨∨=∨=∨∨
)(
)(
.
Рассмотрим ещё несколько примеров, иллюстрирующих это правило.
1. DBDCCB ∨∨ . Этот трёхчлен содержит два раза
B
, но содержит по одному разу C и C, и по одному
разу D и
D
. Значит, симметрия нарушена дважды: по C и по D. Симметрия не нарушена только по B. Поэтому,
применяя наше правило, получим дизъюнкцию, одним членов которой будет B, а другим – тот член трёхчлена,
который не содержит B. Значит, получим DCB ∨ .
2.
D
B
A
DB
A
∨∨
. В этом трёхчлене симметрия нарушена по B и по D. Симметрия не нарушена только по
A. Значит
D
B
A
D
B
∨∨
=
D
B
∨
.
Для каждой формулы существует бесконечно много различных, но равносильных ей ДНФ. Если, напри-
мер, найдена одна ДНФ, то путём повторения имеющихся элементарных конъюнкций, добавления нулевых
конъюнкций, добавления поглощаемых конъюнкций можно построить бесконечно много новых, но равносиль-
ных ей ДНФ.
Например:
...=∨∨=∨∨=
=∨∨∨=∨
BCACABABCBCABABAB
BCABAAABABBCAAB

Страницы