III. Решение логических задач средствами алгебры логики.

РЕШЕНИЕ ЛОГИЧЕСКИХ ЗАДАЧ

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

· с помощью рассуждений.

· табличный способ;

· средствами алгебры логики;

III. Решение логических задач средствами алгебры логики.

Обычно используется следующая схема решения:

1. изучается условие задачи;

2. вводится система обозначений для логических высказываний;

3. конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи;

4. определяются значения истинности этой логической формулы;

5. из полученных значений истинности формулы определяются значения истинности введённых логических высказываний, на основании которых делается заключение о решении.

Пример 1.

Учитель проверил работы трех учеников: Алеши, Димы и Саши, но не захватил их с собой. Ученикам он сказал:

"Все вы написали работу и получили разные оценки.

У Саши не "5",

у Димы не "4",

а вот у Алеши, по-моему "4".

Впоследствии оказалось, что учитель ошибся: одному ученику сказал верно, а двум другим - нет. Определите, какие оценки ученикам поставил учитель?
Решение: 1. С5 - Саша получил не "5";

2. Д4 - у Димы не "4";

3. А4 - У Алеши "4".

Мы знаем, что учитель одному сказал верно, другим двум нет. Тогда получаем: С5•Д4•А4+С5•Д4•А4+С5•Д4•А4 = 1 (Истина);

Учитывая, что ученики получили разные оценки, имеем:

С5•Д4•А4 = 0 (Ложь), поскольку два ученика одновременно не могут получить "4"; С5•Д4•А4 = 0 (Ложь), так как, если Сергей получил "5", то один из двух других должен получить "4";.

Следовательно истинно только высказывание: С5•Д4•А4

Ответ: Алеша - "5", Дима - "4",Саша - "3".

Пример 2.

Трое друзей, болельщиков автогонок "Формула-1", спорили о результатах предстоящего этапа гонок.

— Вот увидишь, Шумахер не придет первым, — сказал Джон. Первым будет Хилл.

— Да нет же, победителем будет, как всегда, Шумахер, — воскликнул Ник. — А об Алези и говорить нечего, ему не быть первым.

Питер, к которому обратился Ник, возмутился:

— Хиллу не видать первого места, а вот Алези пилотирует самую мощную машину.

По завершении этапа гонок оказалось, что каждое из двух предположений двоих друзей подтвердилось, а оба предположения третьего из друзей оказались неверны. Кто выиграл этап гонки?

Решение.

Введем обозначения для логических высказываний:

Ш — победит Шумахер;

Х — победит Хилл;

А — победит Алези.

Реплика Ника "Алези пилотирует самую мощную машину" не содержит никакого утверждения о месте, которое займёт этот гонщик, поэтому в дальнейших рассуждениях не учитывается.

Зафиксируем высказывания каждого из друзей:

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

Высказывание истинно только при Ш=1, А=0, Х=0.

Ответ. Победителем этапа гонок стал Шумахер.
Пример 3. Четыре команды: "Артек", "Сокол", "Вымпел" и "Метеор" - в спортивных соревнованиях заняли четыре призовых места, причем ни одно место не было разделено между командами. О занятых командами местами были получены три высказывания:

1. "Второе место "Сокол", а "Метеор" третье";

2. "Победителем вышел "Сокол", а "Вымпел" был вторым";

3. "Второе место занял "Артек", а "Метеор" был последним".

Пример 4. На марафонском беге были высказаны 2 прогноза о местах, которые займут спортсмены Иванов, Петров, Сидоров, реально претендующие на призовые места.

Виновен ли Иванов?

Решение: Рассмотрим простые высказывания:

И={Иванов виновен}; П={Петров виновен}; С={Сидоров виновен}.

Запишем на языке алгебры логики факты, установленные следствием:

РЕШЕНИЕ ЛОГИЧЕСКИХ ЗАДАЧ

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

· с помощью рассуждений.

· табличный способ;

· средствами алгебры логики;

III. Решение логических задач средствами алгебры логики.

Обычно используется следующая схема решения:

1. изучается условие задачи;

2. вводится система обозначений для логических высказываний;

3. конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи;

4. определяются значения истинности этой логической формулы;

5. из полученных значений истинности формулы определяются значения истинности введённых логических высказываний, на основании которых делается заключение о решении.

Пример 1.

Учитель проверил работы трех учеников: Алеши, Димы и Саши, но не захватил их с собой. Ученикам он сказал:

"Все вы написали работу и получили разные оценки.

У Саши не "5",

у Димы не "4",

а вот у Алеши, по-моему "4".

Впоследствии оказалось, что учитель ошибся: одному ученику сказал верно, а двум другим - нет. Определите, какие оценки ученикам поставил учитель?
Решение: 1. С5 - Саша получил не "5";

2. Д4 - у Димы не "4";

3. А4 - У Алеши "4".

Мы знаем, что учитель одному сказал верно, другим двум нет. Тогда получаем: С5•Д4•А4+С5•Д4•А4+С5•Д4•А4 = 1 (Истина);

Учитывая, что ученики получили разные оценки, имеем:

С5•Д4•А4 = 0 (Ложь), поскольку два ученика одновременно не могут получить "4"; С5•Д4•А4 = 0 (Ложь), так как, если Сергей получил "5", то один из двух других должен получить "4";.

Следовательно истинно только высказывание: С5•Д4•А4

Ответ: Алеша - "5", Дима - "4",Саша - "3".

Пример 2.

Трое друзей, болельщиков автогонок "Формула-1", спорили о результатах предстоящего этапа гонок.

— Вот увидишь, Шумахер не придет первым, — сказал Джон. Первым будет Хилл.

— Да нет же, победителем будет, как всегда, Шумахер, — воскликнул Ник. — А об Алези и говорить нечего, ему не быть первым.

Питер, к которому обратился Ник, возмутился:

— Хиллу не видать первого места, а вот Алези пилотирует самую мощную машину.