Тема 4.2.Решение логических задач

Тема 4.2. Работа с таблицей истинности

Задача 3.

Задача 2.

Рис. 2.4. Рис. 2.5.

Рис. 2.1. Рис. 2.2. Рис. 2.3.

Как вы помните, охотник за мертвыми душами Павел Иванович Чичиков побывал у известных вам помещиков по одному разу у каждого. Он посещал их в следующем порядке: Манилова, Коробочку, Ноздрева, Собакевича, Плюшкина, Тентетникова, генерала Бетрищева, Петуха, Констанжогло, полковника Кошкарева. Найдена схема, на которой Чичиков набросал взаимное расположение имений и проселочных дорог, соединяющих их (рис. 1.1). Установите, какое имение кому принадлежит, если ни по одной из дорог Чичиков не проезжал более одного раза.

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

Задания 1-6. Выписать формулу по заданной функциональной схеме и построить таблицу истинности.

Задания 10 и 11. Упростить логическое выражение.

Цель работы: ознакомиться с основными функциями алгебры логики, освоить навыки решения логических задач.

Задача 1. «Пять офицеров»

В одной из горячих точек служили 5 офицеров: генерал, полковник, майор, капитан и лейтенант. Один из них сапер, другой – пехотинец, третий – танкист, четвертый – связист, пятый – артиллерист. У каждого из них есть сестра. И каждый из них женат на сестре своего однополчанина. Вот что еще известно об этих офицерах:

· По меньшей мере, один из родственников связиста старше его по званию.

· Капитан никогда не служил в Хабаровске.

· Оба родственника-пехотинца и оба родственника-танкиста служили раньше в Мурманске. Ни один родственник генерала в Мурманске не был.

· Танкист служил в Твери вместе с обоими своими родственниками, а лейтенант там не служил.

· Полковник служил в Махачкале вместе со своими родственниками.

· Танкист не служил в Махачкале. Там служил только один из его родственников.

· Генерал служил с обоими своими родственниками в Хабаровске, а в Махачкале он не бывал.

· Артиллерист не служил ни в Хабаровске, ни в Твери.

Определите, кто из офицеров какое звание имеет?

Решение задачи

Ясно, что каждый офицер имеет двух родственников. Один из них – брат жены, а другой – муж сестры. Обозначим для удобства каждого офицера буквой и расположим их так, чтобы соседом каждого были его родственники (рис. 1.1).

Рис. 1.1. Расположение по порядку

Пусть пехотинец будет обозначен буквой А. Поскольку трое из офицеров служили в Мурманске, а двое там не были, то танкисту должна соответствовать либо буква В, либо Г. Допустим, что танкист – В. Отсюда следует (с учетом условия задачи), что А и В не служили в Мурманске и что Б – генерал. Продолжая рассуждать, приходим к выводу, что Б, В и Г служили в Твери. Поэтому лейтенантом должен быть А или Д и букве Д должен соответствовать артиллерист. Далее, либо В и Г, либо В и Б не служили в Махачкале. Следовательно, А, Д и Б либо А, Д и Г служили в Махачкале. А поскольку мы знаем, что Б не служил в Махачкале, это значит, что там служили А, Д и Г и что Д – полковник. Таким образом, А – лейтенант.

Переходим к следующему этапу решения. A, Б и В служили в Хабаровске, а Д там не служил. Нам известно, что капитан в Хабаровске не служил. Поскольку капитал не может быть Д, следовательно, ему соответствует буква Г. Далее приходим к заключению, что В – майор. Известно, что по меньшей мере один офицер должен быть старше по званию, чем связист. Следовательно, связист не может быть Б и должен быть Г, а саперу соответствует буква Б.

Таким образом, в итоге получается, что лейтенант – пехотинец, генерал – сапер, майор – танкист, капитан – связист, полковник – артиллерист.

Решите задачу согласно вашему варианту. Опишите ход решения задачи, логические рассуждения.