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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. ;

2. ;

3. ;

4. .

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

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

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

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

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

=

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

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

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