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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

Мы получили тот же ответ.
Приведение формул к виду СДНФ бывает необходимо при решении конкретных, содержательных задач.
Если, например, в условиях задачи речь идёт об элементарных высказываниях А, В, С и если условия задачи
записаны в виде формулы, то, приведя эту формулу к виду СДНФ, мы тем самым получим полный перечень
всех тех случаев, при которых условия задачи будут выполнены.
Рассмотрим конкретный пример.
Задача. Известно, что если Андрей и Володя
пойдут в кино, то Серёжа в кино не пойдёт. Известно также,
что если Володя не пойдёт в кино, то в кино пойдут Андрей и Серёжа. Надо узнать, кто при этих условиях мо-
жет пойти в кино.
Решение. Введём обозначения. Пусть А означает «Андрей пойдёт в кино», В означает «Володя пойдёт в
кино», С означает «Серёжа пойдёт в кино». Условия задачи запишутся следующим образом:
АСВСАВ →→ ,
.
Воспользуемся теперь равносильностью YXYX ∨=→ . Эта равносильность легко устанавливается с по-
мощью таблиц истинности. На основании этой равносильности условия задачи примут вид:
ACBCAB ∨∨ ,
.
Так как оба условия задачи должны быть выполнены, то должна быть истинной их конъюнкция. Составим эту
конъюнкцию и приведём её к виду ДНФ:
CBCBABAACBCBAACBСAB ∨∨=∨∨∨=∨∨ ))(())((
.
Условия задачи свелись к формуле CBCBABA ∨∨ , которая должна быть истинной. Но дизъюнкция ис-
тинна, если истинным будет хотя бы один из её членов. Значит для того, чтобы условия задачи были выполне-
ны, достаточно, чтобы имел место один из трёх случаев:
1.
B
A
, т.е. в кино может пойти Володя без Андрея.
2. CBA , т.е. в кино могут пойти Андрей с Серёжей, но без Володи.
3. CB , т.е. в кино может пойти Володя без Серёжи.
Задача как будто бы решена. Но на самом деле это решение нельзя признать окончательным, так как в пер-
вом и третьем случае ответ будет неполным. Чтобы получить полный ответ, нужно ранее полученную ДНФ
преобразовать к СДНФ.
.
)()(
CABCBACBABCA
CBACABCBACBABCA
AACBCBACCBACBCBABA
∨∨∨=
=∨∨∨∨=
=∨∨∨∨=∨∨
Теперь мы действительно получили полный перечень всех случаев, при которых выполняются условия
задачи, к тому же выяснилось, что таких случев не три, а четыре.
Возникает вопрос: зачем нужны преобразования, приводящие исходные формулы к минимальной форме?
Зачем нужна минимальная КНФ? Ответ заключается в том, что всё это совершенно необходимо при решении
задач. Рассмотрим конкретный пример.
Задача. В школе решили организовать секцию атлетической гимнастики. Надо было разработать правила
приёма в эту секцию. Ребята внесли ряд предложений:
1. Если ученик не отличник и не здоров, то он не может быть принят.
2. Если ученик является отличником, то не может быть, чтобы он был здоров и его не приняли.
3. Если ученик не принят, то он не отличник.
4. Если ученик не здоров, то он не отличник и не будет принят. Учитель физкультуры сказал, что четыре
правила – это слишком много. К тому же формулировки правил должны быть более простыми, более лаконич-
ными. Поэтому, сказал учитель, возникает следующая задача: надо совокупность всех четырёх правил заменить
новыми правилами – и надо это сделать так, чтобы число новых правил было минимальным, чтобы каждое но-
вое правило было сформулировано кратчайшим образом и чтобы совокупность новых правил была равносильна
совокупности четырёх исходных правил.
Через некоторое время эту задачу действительно удалось решить. Какие правила получились?
Решение. Обозначим элементарные высказывания: ученик является отличником – О, ученик здоров – З,
ученик принят – П. Теперь мы можем записать исходные правила в символической форме. Полученные фор-
мулы мы сразу же упростим, воспользовавшись равносильностью YXYX ∨=→ , законом де Моргана
Y
X
X
Y
∨=
и законом снятия двойного отрицания
X
X
=
. Мы получим следующие цепочки равносильностей:
1. ПЗОПЗОПЗОПЗО ∨∨=∨∨=∨=→ ;
2. ПЗОПЗОПЗОПЗО ∨∨=∨∨=∨=→ ;
3. ОПОП ∨=→ ;

Страницы