Учебник по дискретной математике

Оглавление
n1.doc (26 стр.)
Скачать
1   ...   18   19   20   21   22   23   24   25   26

Пример 7. Во время перемены в классе были Аня, Борис, Ваня и Майя. Один из них разбил окно. На вопрос:”Кто разбил окно?”, были даны ответы:

Аня: 1) Я не разбивала. 2) Я сидела и читала. 3) Майя знает, кто разбил.

Борис: 1) Я этого не делал. 2) С Майей я давно не разговариваю. 3) Это сделал Ваня.

Ваня: 1) Я не виновен. 2) Разбила Майя. 3) Борис лжёт, говоря, что разбил я.

Майя: 1) Я не разбивала. 2) Это вина Ани. 3) Борис знает, что я не виновна, т.е. мы с ним беседовали во время перемены.

Затем каждый признался, что из трёх ответов каждого, два – истинны, а один ложный. Кто разбил окно?

Решение. Введем булевы переменные. Высказывания, принадлежащие Ане, обозначим буквами с индексами ; высказывания, принадлежащие Борису – соответственно, принадлежащие Ване – и принадлежащие Майе – .

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

;

;

;

.

Выпишем все противоречия:





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

и

что тоже будет тавтологией. Получим

В
этой формуле слева останется всего три ненулевых члена:

или Последнее уравнение даёт Так как и то и следовательно, а Следовательно, окно разбила Аня.

Рассмотрим еще одну задачу, для решения которой не требуется аппарат логики высказываний, но тем не менее эта задача относится к логическим задачам.

Пример 8. В кафе встретились три друга: скульптор Белов, скрипач Чернов и художник Рыжов. «Замечательно, что один из нас имеет белые, один черные, а один рыжие волосы, но ни у кого цвет волос не совпадает с фамилией», – заметил черноволосый. «Ты прав», – сказал Белов. Какой цвет волос у художника?

Решение. Составим таблицу.

Фамилия

Цвет волос

Б

Ч

Р

б

0







ч




0




р







0

Н

Фамилия

Цвет волос

Б

Ч

Р

б

0

1

0

ч

0

0

1

р

1

0

0



евозможное сочетание фамилии и цвета волос будем обозначать 0, возможное 1. Очевидно, что в каждой строке и в каждом столбце должна быть только одна 1. Получим два варианта.

Фамилия

Цвет волос

Б

Ч

Р

б

0

0

1

ч

1

0

0

р

0

1

0


Из условия задачи ясно, что черноволосый не Белов, поэтому первый вариант не подходит. Следовательно, Белов – рыжий, Чернов – белый, Рыжов – черный.

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

Спрашивается, имеет ли этот механизм также следующее свойство: если не въехал в помещение склада грузовик с углем, то шахта для угля не откроется, а если не въехал грузовик с коксом, то не откроется шахта для кокса.

Решение. Введем булевы переменные: высказывание « прибыл грузовик с углем» обозначим через x, « прибыл грузовик с коксом» – y, «открыта шахта для угля» – z, «открыта шахта для кокса» – t. Тогда посылками будут: заключение Задача сводится к тому, чтобы выяснить, правильны ли рассуждения , т. е. вытекает ли это заключение из конъюнкции посылок. Кроме того, имеются два дополнительных условия, что может въехать только одна машина и открывается лишь одна дверь. Эти условия можно задать равенствами: и . аналогично, (представление в виде СДНФ или СКНФ). Построим формулу:





Так как , то аналогично, , следовательно, Мы получили тавтологию, следовательно, рассуждения верны.

Пример 10. На предприятии есть три цеха: A, B, C, договорившиеся о порядке утверждения проектов, а именно:

1. Если цех B не участвует в утверждении проекта, то в этом утверждении не участвует и цех A.

2. Если цех B принимает участие в утверждении проекта, то в нем принимают участие цеха A и C.

Спрашивается, обязан ли при этих условиях цех C принимать участие в утверждении проекта, когда в нем принимает участие цех A?

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

следовательно, рассуждения верны.

Пример 11. Перед судом стоят три человека, из которых каждый может быть либо туземцем, либо колониалистом. Судья знает, что туземцы всегда отвечают на вопросы правдиво, между тем как колониалисты всегда лгут. Однако судья не знает, кто из них туземец, а кто колониалист. Он спрашивает первого, но не понимает его ответа. Поэтому он спрашивает сначала второго, а потом третьего о том, что ответил первый. Второй говорит, что первый назвал себя туземцем. Третий говорит, что первый назвал себя колониалистом. Кем были второй и третий подсудимые?

Решение. Во-первых, если первый человек туземец, то он назовет себя туземцем, если он колониалист, то тоже назовет себя туземцем. Высказывание «первый сказал, что он туземец» обозначим через x, «второй туземец» – y, «третий туземец» – z, и заметим, что x  1.

Имеем следовательно, второй – туземец. следовательно, третий – колониалист.
Портфель ученика
© lib.rushkolnik.ru
При копировании укажите ссылку.
обратиться к администрации