Файл: Василевский, А. Б. Методы решения задач учебное пособие.pdf

А

в

AVB

1

1

1

1

0

1

0

1

1

0

0

0

можно переписать

так:

А Д В V (А V В) Д С.

Если

известно

значение

каждого

высказывания,

входящего

в алгебраическое

выражение,

то с помощью таблиц истинности

можно найти значение этого

алгебраического выражения. Найдем)

например,

значения алгебраического

выражения А \/В

при всех

возможных значениях его компонент А и В:

А

в

А

в

A V В

1

1

0

0

0

1

0

0

1

1

0

1

1

0

1

0

0

1

1

1

и четвертый столбцы, а

потом последний.

Эта таблица называется

таблицей истинности для выражения А\/В.

Строим таблицу истинности для

Л Л В:

А

в

АЛ в

А л в

1

1

1

0

1

0

0

1

0

1

0

1

0

0

0

1

1.

Л Д В = В Л А ;

2. А \/В = В\/А]

3.

(АЛВ)ЛС =

АЛ(ВЛС);

4. (A \/£ )V C =A V (£ V C );

5. AA(BVC) =

(AAB)V(AAC);

6.

Av (BAC)eee(Av £)A (A v C);

7. А Л А ^ А ;

8. A vA = А;

9.

А Л В ж; А\/ В\

10.

А \ / В ~ А / \ В \

11.

1 = А \

12.

АЛА =

Л;

13.

AVA =

H;

14.

А Д Л =

Л;

15.

AVH =

H;

16.

А л И =

А;

17.

А у Я ~ А .

Пример 3. Однажды следователю

пришлось одновременно до­

противоречили

друг другу,

и каждый из них обвинял кого-нибудь

рр лжи, Клод

утверждал,

что Ж аА ДЖет, Жак обвинял во лжи

Дика, а Дик уговаривал следователя не верить

ни Клоду,

ни

Жаку. Но следователь быстро вывел их на чистую

воду, не задав

им ни одного вопроса. Кто из свидетелей говорил правду?

Д.

Обозначим показания Клода, Жака и Дика буквами К, Ж,

Мы знаем, что:

3) либо Дик сказал правду,

и тогда Клод и Жак солгали, либо

Дик солгал, и тогда

неверно,

что оба

других

свидетеля солгали.

Эти три составных

высказывания на

языке

алгебры высказыва­

ний выглядят следующим образом:

1) КЛЯЫКЛЖ-,

2) Ж А Д А Ж А Д\

3) Д а К А Ж АД А (К \/Ж ).

= 1 •

(1)

Получили одно логическое уравнение с тремя неизвестными.

Теперь в левой части уравнения (1)

выполняем умножение по пра­

вилам 1—17:

Строим штриховой отрезок ХД (рис.

54),

потому что Л соот­

ветствует

X и Л не соответствует Д,

т.

е. X

не

может соответ­

ствовать

Д.

типичную для таких задач операцию

на графе:

если

Используем

у треугольника

с

вершинами в трех разных множествах одна

сто­

рона сплошная,

а

вторая штриховая,

то

и третья

сторона должна

нить с третьей

точкой

этого

множества сплошным

отрезком.

По­

этому строим сплошной отрезок ФД.

что

в

треугольнике

Строим штриховой

отрезок

МД, потому

ДФМ сторона ДФ сплошная, а сторона ФМ штриховая.

Строим сплошной отрезок

ДК,

потому что отрезки ДМ и ДЛ

штриховые.

Строим сплошной отрезок ФК.

множествах

две

Если в треугольнике с вершинами в разных

стороны сплошные, то и третья сторона должна

быть сплошной.

Таким образом,

построен первый

«сплошной»

треугольник ДФК,

Вершины «сплошных»

треугольников

ДФК, ЛХИ и СМБ дают

ответ на вопрос задачи:

Степан преподает биологию в Москве,

Иван живет

в Ленинграде и преподает химию, Дмитрий преподает

физику в Киеве.

Упражнения

1.

При составлении расписания уроков

на

понедельник трое учителей вы­

сказали пожелания, чтобы их уроки были:

по математике— первый или второй;

по истории — первый

или третий; по

литературе — второй или третий. Сколь­

кими способами и как при составлении

расписания можно удовлетворить поже­

лания

всех учителей?

Женя

и Катя умеют играть на разных инструментах

2.

Маша,

Лида,

(виолончели,

рояле,

гитаре,

скрипке),

но

каждая только на одном. Они же

говорит по-испански. Лида не играет ни на

скрипке,

ни на

виолончели и не

знает английского

языка.

Маша

не играет

ни на

скрипке,

ни

на виолончели

и не знает английского языка. Девушка,

которая говорит по-немецки, не играет

на виолончели. Женя знает французский язык,

но не играет на скрипке.

Кто на каком инструменте играет и какой иностранный язык знает?

3. Четырех подруг спросили, на каком

проспекте в Ленинграде и в каком

доме живет Аня.

Каждая

из них сделала два

высказывания:

Первая:

1)

Аня живет не на Невском проспекте;

2)

номер дома 84.

Вторая:

1)

Аня живет

не на

Невском проспекте и не на

Чкаловской про­

спекте; 2) номер дома делится на 2,

на 3,

на 4

и на 6.

Третья:

1)

Аня живет на Чкаловской проспекте;

2) номер дома 96.

Четвертая:

1)

Аня живет на

Московском

проспекте;

2) номер дома оканчи­

вается на 6.

а

другое

ложное. Где

Одно из высказываний каждой подруги верное,

живет Аня?

П р и м е ч а н и е .

Указанные

проспекты

расположены в различных районах

Ленинграда, не пересекаются и не имеют общих домов.

уверен,

что он поде­

4. Три

разбойника хотят поделить

добычу.

Каждый

лил бы добычу на равные части,

но остальные

ему не

доверяют. Если бы раз­

бойников было двое, то выйти из положения

было бы легко: один разделил бы

добычу на две части, а другой

взял

бы ту часть,

которая

ему кажется боль­

шей. Указать,

как должны действовать три

разбойника, чтобы каждый из них

был уверен, что его

доля

составляет

не

менее

одной

трети от всей добычи.

(Добыча настолько разнородна,

что

объективного

способа сравнения отдельных

частей не существует.)

известных

в

городе

М под кличками Арчи,

5. Один из трех

гангстеров,

Босс и Весли,

украл портфель

с

деньгами.

На допросе

каждый

из них сделал

три заявления:

Арчи: Я не брал портфеля.

В5день кражи я уезжал из города М.

Портфель украл Весли.

Босс: Портфель украл

Весли.

я бы не сознался.

Если бы я и взял его,

У меня и так много денег.

Весли: Я не брал портфель.

Я давно ищу хороший портфель.

Арчи прав,

говоря,

что он уезжал из города М.