Упрощение систем высказываний

До сих пор мы упрощали высказывания в целом. Как быть, если имеется некоторая их система? Упростить систему высказываний — значит привести ее к меньшему числу не более сложных высказываний:

Рассмотрим возможные случаи.

1. Система высказываний А, В, С, D, Е. Каждое из высказываний данной совокупности истинно, поэтому истинна конъюнкция всех этих высказываний. Чтобы упростить данную систему высказываний, нужно составить конъюнкцию из высказываний А, В, С, D, Е и привести ее эквивалентными преобразованиями к конъюнкции более простого вида:

2. Система высказываний А, В, С, D, Е, относительно которых известно, что по меньшей мере одно из них истинно. По меньшей мере одно из высказываний А, В, С, D, Е истинно, значит, истинна дизъюнкция всех данных высказываний. Поэтому, чтобы упростить данную систему высказываний, нужно составить дизъюнкцию из данных высказываний и привести ее путем эквивалентных преобразований к дизъюнкции более простого вида:

3. Система высказываний А, В, С, D, Е, в которой хотя Бы одно из высказываний ложно. Если хотя бы одно из высказываний системы ложно, то ложна и конъюнкция этих высказываний. Поэтому для упрощения данной системы используется конъюнктивная нормальная форма:

4. Система ложных высказываний А, В, С, D, Е. Если все высказывания системы ложны, то ложна и их дизъюнкция. Поэтому для упрощения данной системы используется дизъюнктивная нормальная форма:

Решение логических задач

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

Фактически решение логической задачи сводится к правильному преобразованию ее условия по законам логики. Оно включает ряд этапов:

• 1) формализация условия задачи;
• 2) составление системы высказываний, то есть объединение условия в единую формулу;
• 3) путем эквивалентных преобразований приведения формулы к искомому результату.

Рассмотрим следующую задачу.

Кто из студентов-заочников был вчера в библиотеке, если известно следующее:

• • если в библиотеке Алексеев, то с ним обязательно бывают Борисов и Волков;
• • если Волков идет в библиотеку, то Григорьев отправляется с ним;
• • Дмитриев бывает в библиотеке тогда и только тогда, когда там Борисов;
• • по крайней мере, Алексеев или Борисов были в библиотеке;
• • либо Дмитриев, либо Григорьев были вчера в библиотеке.

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

где 1: А —^ (Б а В); 2: В —^ Г; 3: Д Б; 4: А/Б; 5: ДуГ.

Учитывая это, получим следующее соотношение:

Удалим знаки импликации, эквиваленции и строгой дизъюнкции, а в качестве знаков дизъюнкции и конъюнкции выберем для удобства, соответственно, «+» и «•», тогда будем иметь:

По правилам алгебры логики перемножим скобки:

Таким образом, получаем АГВДБ = И стало быть в библиотеке были только студенты Дмитриев и Борисов.