Применение основных равносильностей алгебры высказываний для решения содержательных задач, требующих приведения формул алгебры логики к минимальной КНФ и СДНФ виду.

Приведение формул к виду СДНФ бывает необходимо при решении конкретных, содержательных задач. Если, например, в условиях задачи речь идет об элементарных высказываниях А, В, С и если условия задачи записаны в виде формулы, то, приведя эту формулу к виду СДНФ, мы тем самым получим полныйперечень всех тех случаев, при которых условия задачи будут выполнены.

Рассмотрим конкретный пример.

Задача.Известно, что если Андрей и Володяпойдут в кино, то Сережа в кино не пойдет. Известно также, что если Володя не пойдет в кино, то в кино пойдут Андрей и Сережа. Надо узнать, кто при этих условиях может пойти в кино.

Решение.Введем обозначения. Пусть А означает: «Андрей пойдет в кино», В означает: «Володя пойдет в кино», С означает: «Сережа пойдет в кино». Условия задачи запишутся следующим образом:

Воспользуемся теперь равносильностью . (Эта равносильность легко устанавливается с помощью таблиц истинности.) На основании этой равносильности условия задачи примут вид: . Так как оба условия задачи должны быть выполнены, то должна быть истинной их конъюнкция. Составим эту конъюнкцию и приведем ее к виду ДНФ:

Условия задачи свелись к формуле , которая должна быть истинной. Но дизъюнкция истинна, если истинным будет хотя бы один из ее членов. Значит, для того, чтобы условия задачи были выполнены, достаточно, чтобы имел место один из трех случаев:

1. , т. е. в кино может пойти Володя без Андрея.

2. , т. е. в кино могут пойти Андрей с Сережей, но без Володи.

3. , т. е. в кино может пойти Володя без Сережи.

Задача как будто бы решена. Но на самом деле это решение нельзя признать окончательным, так как в первом и третьем случае ответ будет неполным. Чтобы получить полный ответ, нужно ранее полученную ДНФ преобразовать к СДНФ.

Теперь мы действительно получили полный перечень всех случаев, при которых выполняются условия задачи, к тому же выяснилось, что таких случев не три, а четыре.

Возникает вопрос: зачем нужны преобразования, приводящие исходные формулы к минимальной форме? Зачем нужна минимальная КНФ? Ответ заключается в том, что все это совершенно необходимо при решении задач. Рассмотрим конкретный пример.

Задача.В школе решили организовать секцию атлетической гимнастики. Надо было разработать правила приема в эту секцию. Ребята внесли ряд предложений:

1. Если ученик не отличник и не здоров, то он не может быть принят.

2. Если ученик является отличником, то не может быть, чтобы он был здоров и его не приняли.

3. Если ученик не принят, то он не отличник.

4. Если ученик не здоров, то он не отличник и не будет принят. Учитель физкультуры сказал, что четыре правила — это слишком много. К тому же формулировки правил должны быть более простыми, более лаконичными. Поэтому, сказал учитель, возникает следующая задача: надо совокупность всех четырех правил заменить новыми правилами — и надо это сделать так, чтобы число новых правил было минимальным, чтобы каждое новое правило было сформулировано кратчайшим образом и чтобы совокупность новых правил была равносильна совокупности четырех исходных правил.

Через некоторое время эту задачу действительно удалось решить. Какие правила получились?

Решение.Обозначим элементарные высказывания: ученик является отличником — О, ученик здоров — 3, ученик принят — П. Теперь мы можем записать исходные правила в символической форме. Полученные формулы мы сразу же упростим, воспользовавшись равносильностью , законом де Моргана и законом снятия двойного отрицания . Мы получим следующие цепочки равносильностей:

1. ;

2. ;

3. ;

4. .

Так как все четыре условия должны выполняться, то должна быть истинной их конъюнкция. Составим эту конъюнкцию и приведем ее к минимальной дизъюнктивной форме. Мы получим следующий результат: .

Некоторые учащиеся, которые впервые решают задачу подобного рода, считают, что решение уже найдено. По их мнению, получилось два новых правила: и .

На самом же деле ответ будет совсем другим. Чтобы понять, в чем тут дело, рассмотрим внимательно полученный результат. Формула представляет собой дизъюнкцию, а дизъюнкция истинна тогда и только тогда, когда истинным является хотя бы один из ее компонентов. Может, например, оказаться, что истинно только или только . Когда же учащиеся, получив формулу , считают, что они тем самым получили два правила, т. е. два истинных утверждения, то они совершают грубую ошибку. Ведь из истинности дизъюнкции вовсе не следует, что истинны оба ее компонента. Чтобы найти новые правила приема в спортивную секцию, надо рассуждать совсем по-другому. Начнем с того, что искомые правила должны представлять собой истинные высказывания. Но если высказывания истинны, то истинна и их конъюнкция, а если истинна конъюнкция, то истинно и каждое из высказываний в отдельности.

Значит, чтобы найти новые правила, достаточно найти конъюнкцию этих правил. Следовательно, мы должны полученную ранее формулу преобразовать в конъюнкцию. А так как число новых правил должно быть минимальным и так как каждое правило должно быть сформулировано кратчайшим образом, то искомая конъюнкция должна иметь вид минимальной КНФ.

Чтобы выполнить это преобразование, воспользуемся законом исключенного третьего и законом поглощения. Мы получим следующую цепочку равносильностей:

Таким образом, задача решена. Получилось два правила приема в секцию:

1. Если ученик является отличником, то он будет приняв ;

2. Если ученик принят, то необходимо, чтобы он был| здоров .

Задача (для самостоятельного выполнения).Собираясь в поход, ребята высказали следующие суждения:

1. Если будет холодно или пойдет дождь, то поход не состоится.

2. Если будет холодно, то пойдет дождь.

3. Если не будет холодно и поход состоится, то дождя не будет.

Учитель сказал, что эти суждения можно свести к двум простейшим высказываниям. Найдите их!