Решение логических задач с помощью булевых функций

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

Пример: Сергей, Анна, Юрий и Ольга заняли на математической олимпиаде четыре первых места. На вопрос о распределении мест, одноклассники ответили следующее: 1) Анна – первая, Ольга – вторая; 2) Анна – вторая, Сергей – третий; 3) Юрий – второй, Сергей – четвертый. В каждом из ответов только одно утверждение истинно. Определим, как распределились места.

Пусть -- простые высказывания, где X – первая буква имени участника. Y – номер занятого места. Тогда высказывания можно записать: 1) ; 2) ; 3) .

Так как все дизъюнкции истинны, то истинной будет и конъюнкция этих дизъюнкций, т.е.

()()()=1;

=1;

=0, т.к. Анна не может занимать два места;

=0, т.к. Ольга и Анна не могут обе быть на втором месте.

Тогда равенство примет вид: =1;

=1;

=1.

Следовательно, Анна заняла первое место, Сергей – второе, Юрий – третье, тогда Ольга – четвертое.

Задачи.

1. Записать символически следующие сложные предложения:

а) идет дождь или кто-то не выключил душ;

b) если вечером будет дождь, то Олег или останется дома, или должен будет взять такси;

c) если я устал или голоден, я не могу заниматься;

d) хлеба уцелеют тогда и только тогда, когда будут вырыты ирригационные канавы; если хлеба не уцелеют, то фермеры обанкротятся и оставят фермы.

2. Пусть даны высказывания: c= «сегодня ясно», r= «сегодня идет дождь», s= «сегодня идет снег», y= «вчера было пасмурно». Перевести на обычный язык следующие сложные высказывания:

a) ;

b) ;

c) .

3. Исследовать справедливость следующих рассуждений.

(а) Я пойду домой или останусь в университете и сдам долги. Я не пойду домой. Следовательно, я останусь и сдам.

(b) Заработная плата возрастет только, если будет инфляция. Если будет инфляция, то увеличится стоимость жизни. Заработная плата возрастет. Следовательно, увеличится стоимость жизни.

(с) Преподаватель или переутомился, или болен. Если он переутомился, то он раздражается. Он не раздражается. Следовательно, он болен.

(d) Если я пойду завтра на первое занятие, то должен буду встать рано, а если я пойду вечером на танцы, то лягу спать поздно. Если я лягу спать поздно, а встану рано, то я буду вынужден довольствоваться пятью часами сна. Я просто не в состоянии обойтись пятью часами сна. Следовательно, я должен или пропустить завтра первое занятие, или не ходить на танцы.

(e) Объем фонда музея возрастет только, если в него будут поступления из личных коллекций граждан. Если будут поступления, то увеличится число выставок. Объем фонда возрастет. Следовательно, увеличится число выставок.

(f) Встретились скульптор Белов, скрипач Чернов и художник Рыжов. «Замечательно, что один из нас имеет белые, один черные и один рыжие волосы, но ни у одного нет волос того цвета, на который указывает его фамилия», -- заметил черноволосый. «Ты прав», -- сказал Белов. Определить, какой цвет волос у художника.

Глава 3. Комбинаторика.

Часто приходится составлять из конечного числа элементов различные комбинации и производить подсчет числа всех возможных комбинаций, составленных по некоторому правилу. Например: -- сколькими способами можно расположить людей в очереди?; -- сколькими способами возможно распределение мест на чемпионате среди десяти команд?; -- сколько существует вариантов составления расписания?; и т.д. Такие задачи получили название комбинаторных, а раздел математики, занимающийся их решением, называется комбинаторикой. В комбинаторике имеют дело только с конечными множествами.

Дата добавления: 2014-11-29