Задачи на алгебру логики с решениями – Методическая разработка на тему «Алгебра высказываний. Основные логические операции. Решение задач с помощью алгебры логики в аспекте межпредметных связей информатики и математики»

решение задач с помощью алгебры логики.



        Одним из мощных методов решения логических задач является решение с помощью законов алгебры логики.

Алгоритм решения логических задач с помощью алгебры логики: 1) внимательно изучить условие; 2) выделить простые высказывания и обозначить их латинскими буквами; 3) записать условие задачи на языке алгебры логики; 4) составить конечную формулу, для этого объединить логическим умножением формулы каждого утверждения, приравнять произведение единице; 5) упростить формулу, проанализировать полученный результат или составить таблицу истинности, найти по таблице значения переменных, для которых F = 1, проанализировать результаты.

Задача1 " Кто преступник"

  Определить участника преступления, исходя из двух 

посылок:


     1) "Если Иванов не участвовал или Петров участвовал, 


то Сидоров участвовал";


     2) "Если Иванов не участвовал, то Сидоров не 


участвовал".


  

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

1 способ


     Составим выражения:


     I - "Иванов участвовал в преступлении";

 P - "Петров участвовал в преступлении";


     S - "Сидоров участвовал в преступлении"

.
    Запишем посылки в виде формул:


¬I˅P→S и ¬I→¬S



Из таблицы видно, что совершил преступление Иванов

Способ 2

Применим для решения этой же задачи преобразования с

 помощью законов алгебры логики:


( ¬I˅P→S) &( ¬I→¬S)=(¬(¬I˅P)˅S) & (I˅¬S) =

= (I & ¬P ˅S) &(I ˅¬S) =  I&¬P˅ I & S˅  I &¬P &¬S ˅0= 

= I&¬P ˅ I & S =I & (¬P˅S)


Из последнего выражения видно, что выражение верно, если I=1, значит преступник - Иванов.

Задача 2 "Прогноз погоды"

     На вопрос, какая завтра будет погода, синоптик ответил: 1.              Если не будет ветра, то будет пасмурная погода без дождя. 2.              Если будет дождь, то будет пасмурно и без ветра. 3.              Если будет пасмурная погода, то будет дождь и не будет ветра. Так какая же погода будет завтра? 

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

  1.         Выделим простые высказывания и запишем их через переменные:

       A – «Ветра нет»

       B – «Пасмурно»

   С – «Дождь»    2.          Запишем логические функции (сложные высказывания) через введенные переменные:

     Если не будет ветра, то будет пасмурная погода без дождя: 

     A → B & C 
     Если будет дождь, то будет пасмурно и без ветра:
     С → B & A 
     Если будет пасмурная погода, то будет дождь и не будет ветра
     B → C & 

     в) Запишем произведение указанных функций:
    F=(A→ B & C) & (C→B & A) & (B→ C & A) 

    Упростим формулу (используются законы де Моргана, переместительный закон, закон противоречия):

F=(A→ B & ¬C) & (C→B & A) & (B→ C & A)

 = (¬A v B & ¬C) & (¬C v B&A) & (¬B v C&A) =

= (¬A v B & ¬C) & (¬B v C&A) & (¬C v B&A) =

= (¬A &¬ B v B&¬C&¬B v ¬A&C&A v B&¬C&C&A) &
 (C v B&A)=

= ¬A & ¬B &(C v B&¬A) =A&¬B&C v¬ A&¬B&B&¬A = 3.         Приравняем результат  единице, т.е. наше выражение должно быть истинным:F = ¬A &¬ B & ¬C = 1 и проанализируем результат: Логическое произведение равно 1, если каждый множитель равен 1. ¬A = 1; ¬B = 1; ¬C = 1.значит: A = 0; B = 0; C = 0;

Ответ: погода будет ясная, без дождя, но ветреная.

 Задача 3 «История с амфорой».
Алеша, Боря и Гриша нашли в земле сосуд. Рассматри­вая удивительную находку, каждый высказал по два предположения.

Алеша: «Это сосуд греческий и изготовлен в V веке». Боря: «Это сосуд финикийский и изготовлен в III веке». Гриша: «Это сосуд не греческий и изготовлен в IV веке».
Учитель истории сказал ребятам, что каждый из них прав только в одном из двух предположений. Где и в каком веке изготовлен сосуд?

Введем следующие обозначения:

«Это сосуд греческий» — G
«Это сосуд финикийский» — F
«Сосуд изготовлен в III веке» — V3;
«Сосуд изготовлен в IV веке» — V4;
«Сосуд изготовлен в V веке» — V5. Формализуем задачу, записав в данных обозначениях условия задачи. Со слов учителя следует, что Алеша прав только в чем-то одном: или G = 1, или V5 = 1. Таким образом, тождественно истинным будет высказывание: G¬V5 v ¬GV5.=1 Аналогично, из слов Бори и учителя следует: F¬V3 v ¬FV3 = 1, а из слов Гриши и учителя: ¬G¬V4
v GV4 = 1. Кроме того, ясно, что сосуд может быть изготовлен только в одном из веков и только в одной из стран. Эти условия можно записать так: VVV˅ ¬V3VV5  ˅ ¬VV4V5 = 1, Итак, мы получили пять тождественно истинных высказываний. Их нужно логически перемножить. Резуль­тат должен быть также тождественно истинным высказыванием: 1 = (G¬V5 v ¬GV5) & (F¬V3 v ¬FV3) & G¬V4 v GV4) & (F¬G v ¬FG) & (VVV˅ ¬V3VV5  ˅ ¬VV4V5) =  (упростим: сначала перемножим первую и третью скобки и вторую и четвертую скобки) =(
G¬V5¬G¬V4˅¬GV5¬G¬V4  ˅ G¬V5GV4  ˅ ¬GV5 GV4)&( F¬V3 F¬G˅¬FV3 F¬G˅ F¬V3 ¬FG  ˅ ¬FV3¬FG) & (VVV˅ ¬V3VV5  ˅ ¬VV4V5) = учитывая, что, G¬G = 0, GG = GG¬GG, упростим выражения в первой и второй скобках: =(¬GV5¬V4 
˅
¬V5GV4 ) &( ¬FV3G ˅¬V3 F¬G)& (VVV˅ ¬V3VV5  ˅ ¬VV4V5) = (перемножим первую и вторую скобки и упростим полученное выражение) (¬GV5¬V¬FV3G˅¬V5GV4¬FV3G˅¬GV5¬V4  ¬V3 F¬G ˅ ¬V5GV4¬V3 F¬G) & (VVV˅ ¬V3VV5
 ˅ (¬
VV4V5)= (¬V5V4¬FV3G˅¬GV5¬V4  ¬V3 F) & (VVV˅ ¬V3VV5  ˅ ¬VV4V5)= ¬GV5¬V4  ¬V3 F ¬GV5¬V4  ¬V3 F=1, если ¬G=1, V5=1, ¬V4 =1, ¬V3=1, F=1 Итак, сосуд финикийский и изготовлен в V веке.

Задача 4  «Поход в кино».
Андрей, Аня и Маша решили пойти в кино. Каждый из них высказал свои пожелания по поводу выбора фильма.
Андрей сказал: «Я хочу посмотреть французский боевик». Маша сказала: «Я не хочу смотреть французскую комедию». Аня сказала: «Я хочу посмотреть американскую мелодраму». Каждый из них слукавил в одном из двух пожеланий. На какой фильм пошли ребята? 1.         Выделим простые высказывания и запишем их через переменные: А — «Французский фильм» С — «Комедия» 2. Запишем логические функции (сложные высказывания). Учтем условие о том, что каждый из ребят оказался прав в одном предположении: а) «Французский боевик» ¬A&B˅AB б) «Американскую мелодраму» ¬¬AB˅¬ А &¬¬В

в) «Нефранцузская комедия» ¬¬A&C˅¬AC

3. Запишем произведение :
  (¬A&B˅AB) & (¬¬AB˅¬ А&¬¬В)&( ¬¬A&C˅¬AC)=1.
Упростим формулу: (¬A&B˅A&¬B) & (¬¬A&¬B˅¬ А&¬¬В)&( ¬¬A&C˅¬A&¬C)= (¬A&B˅A&¬B) & (A&¬B˅¬ А&В)&( A&C˅¬A&¬C)= =(¬A&B& A&¬B˅ A&¬B& A&¬B˅¬A&B &¬А&В˅ A&¬B&¬A&B)&( A&C˅¬A&¬C)= =(A&¬B ˅¬A&B)&( A&C˅¬A&¬C)= A&¬B& A&C˅¬A&B& A&C˅ A&¬B&¬A&¬C˅¬A&B&¬A&¬C= ¬A&BC˅ AB&C =1 6. Составим таблицу истинности для выражения:
 ¬A&BC˅ AB&C:
7. Найдем по таблице значения переменных, для которых F=1. 8. Проанализируем результат:  Результат Б) не является решением, т.к. в ответе Маши оба утверждения оказываются неверными, что проти­воречит условию задачи.  Результат А) полностью удовлетворяет усло­вию задачи и поэтому является верным решением.

Ответ: ребята выбрали американский боевик.
А

Решите самостоятельно задачи уровня 3

inf61.blogspot.com

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

Разделы: Информатика


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

Задачи урока:

образовательная – знакомство учащихся с понятием решения логических задач средствами алгебры логики;

развивающие – развитие логического мышления учащихся, памяти, внимания, а также интереса к разделу информатики - алгебре логики;

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

Тип урока: проверка знаний и изучение нового материала.

Возраст учащихся: 10-11 класс.

Оборудование урока:

Требования к знаниям и умениям учащихся:

учащиеся должны знать:

  • основные понятия и определения алгебры логики;
  • основные законы алгебры логики;

учащиеся должны уметь:

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

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

План урока:

  1. Организационная часть.
  2. Повторение пройденных тем.
  3. Физкультминутка.
  4. Изучение нового материала.
  5. Закрепление изученного материала.
  6. Подведение итогов урока.
  7. Домашнее задание.

Ход урока

1. Организационная часть

  • приветствие;
  • проверка отсутствующих;
  • постановка целей урока.

Учитель. Нам известны три способа решения логических задач:

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

2. с помощью таблиц;

3. средствами алгебры логики.

Первым способом мы умеем решать логические задачи с первого класса. Вторым способом мы научились решать на предыдущих уроках. А вот третьим способом – средствами алгебры логики – научимся решать сегодня.

2. Повторение пройденных тем.

Учитель. Прежде чем перейти к изучению новой темы нам будет необходимо вспомнить некоторые пройденные темы, а именно, упрощение логических выражений с помощью законов алгебры логики и запись составных высказываний в виде логических выражений.

(Все задачи на повторение пройденной темы решаются учениками на доске с объяснением применяемых правил и законов).

Первое задание. Упростить логическое выражение. (Демонстрируется слайд).

_______________

F =

Решение (используются законы де Моргана, закон двойного отрицания, распределительный закон):

_______________ _____

F = = A v B & = (A v B) & (B v C) = B v (A & C)

Дальше ученики самостоятельно решают подобную задачу в своих индивидуальных карточках.

Второе задание. Проверить правильность упрощения построением таблиц истинности. (Демонстрируется слайд).

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

Решение:

Таблица истинности для исходного логического выражения

А

В

C

A V B

B V C

F

0

0

0

0

0

1

1

0

0

0

1

0

1

0

1

0

0

1

0

1

1

0

0

1

0

1

1

1

1

0

0

1

1

0

0

1

0

1

1

0

1

0

1

1

1

0

0

1

1

1

0

1

1

0

0

1

1

1

1

1

1

0

0

1

Таблица истинности для упрощенного логического выражения

 

А

В

C

A & C

B V А & C

0

0

0

0

0

0

0

1

0

0

0

1

0

0

1

0

1

1

0

1

1

0

0

0

0

1

0

1

1

1

1

1

0

0

1

1

1

1

1

1

Из таблиц истинности видно, что упрощение верное.

Дальше ученики самостоятельно решают подобную задачу в своих индивидуальных карточках.

Третье задание. Построить логическую схему полученного упрощенного логического выражения. (Демонстрируется слайд).

(Продемонстрировать и объяснить работу схемы).

Дальше ученики самостоятельно решают подобную задачу в своих индивидуальных карточках.

Четвертое задание. Записать следующее высказывание в виде логического выражения: «Если я хорошо подготовлюсь по русскому языку, математике и физике, то я получу пятерки или четверки».

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

А – хорошо подготовлюсь по русскому языку;

В – хорошо подготовлюсь по математике;

С – хорошо подготовлюсь по физике;

D – получу пятерки;

Е – получу четверки.

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

F = (A & B & C) --> (D V E)

Дальше ученики самостоятельно решают подобную задачу в своих индивидуальных карточках.

Пятое задание. Решить логическую задачу с помощью рассуждений. (Демонстрируется слайд).

Принцу необходимо спасти принцессу от злого колдуна. Принцесса находится в одной из комнат с надписями на дверях:

  1. В этой комнате сидит тигр.
  2. Принцесса находится в комнате 1.
  3. Тигр сидит в комнате 2.

Колдун сообщил принцу, что одно из этих утверждений является истинным. И если принц с первого раза отгадает, где находится принцесса, то колдун освободит ее.

Учитель. Сейчас мы узнаем, есть ли среди нас принцы. Кто поможет принцессе? Если кто-то готов выручить ее, то он должен щелкнуть мышкой по двери и дверь откроется. (Демонстрируется слайд)

III. Физкультминутка. Разгадывание кроссворда за компьютером.

(Учащиеся встают, разминаются, садятся за компьютеры и решают кроссворд, подготовленный в MS Excel. Оценку, выставленную компьютером, ученики заносят в карточку).

IV. Изучение нового материала. (Демонстрируются слайды)

Учитель. Представим такую ситуацию: по телевизору синоптик объявляет прогноз погоды на завтра и утверждает следующее:

Если не будет ветра, то будет пасмурная погода без дождя.

Если будет дождь, то будет пасмурно и без ветра.

Если будет пасмурная погода, то будет дождь и не будет ветра.

Так какая же погода будет завтра? (Ответы учеников)

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

Решение:

а) Выделим простые высказывания и запишем их через переменные:

A – «Ветра нет»

B – «Пасмурно»

С – «Дождь»

б) Запишем логические функции (сложные высказывания) через введенные переменные:

1. Если не будет ветра, то будет пасмурная погода без дождя:

A --> B & C

2. Если будет дождь, то будет пасмурно и без ветра:

С --> B & A

3. Если будет пасмурная погода, то будет дождь и не будет ветра

B --> C & A

в) Запишем произведение указанных функций:

F=(A --> B & C) & (C -->B & A) & (B --> C & A)

г) Упростим формулу (используются законы де Моргана, переместительный закон, закон противоречия):

F=(A --> B & C) & (C -->B & A) & (B --> C & A)

= (A v B & C) & (C v B&A) & (B v C&A) =

= (A v B & C) & (B v C&A) & (C v B&A) =

= (A & B v B&C&B v A&C&A v B&C&C&A) & (C v B&A)=

= A & B &(C v B&A) =A&B&C v A&B&B&A =

= A&B&C

д) Приравняем результат единице, т.е. наше выражение должно быть истинным:

F = A & B & C = 1

е) Проанализируем результат:

Логическое произведение равно 1, если каждый множитель равен 1.

Поэтому:

A = 1; B = 1; C = 1;

Значит: A = 0; B = 0; C = 0;

Ответ: погода будет ясная, без дождя, но ветреная.

Учитель. Ребята, вы познакомились с новым методом решения логических задач. Как вам кажется, какой из трех способов решения логических задач является самым точным? (Ответы учеников)

V. Закрепление изученного материала.

Учитель. Запишем условие еще одной интересной задачи из жизни, которую мы начнем решать в классе, а закончим дома самостоятельно.

Задача. Джеку, Питеру и Майку предъявлено обвинение в соучастии в ограблении банка. Похитители скрылись на поджидавшем их автомобиле. На следствии Джек показал, что преступники скрылись на синем Мерседесе, Питер сказал, что это был черный Джип, а Майк утверждал, что это был Форд Мустанг и ни в коем случае не синий. Стало известно, что желая запутать следствие, каждый из них указал правильно либо марку машины, либо только ее цвет. Какого цвета и какой марки была машина?

Учитель. Можно ли раскрыть это преступление? Имея в виду, что у нас каждое преступление раскрывается, и, учитывая, что следователи изучали в школе алгебру логики, с уверенностью можно сказать, что преступники будут наказаны. Кто из вас поможет следствию и правильно вычислит цвет и марку машины, узнаем на следующем уроке, а сейчас вместе напишем логическую функцию.(Учитель помогает детям записать правильно логическое выражение.)

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

(Ответом на это будет выступление ученика с показом слайдов, подготовленных им заранее).

VI.Подведение итогов урока.

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

(Поставить оценки наиболее активным ученикам. Собрать индивидуальные карточки для проверки.)

VII. Домашнее задание.

Учитель. Попробуйте решить домашнее задание – задачу об ограблении банка всеми тремя известными вам способами и сравнить результаты.

xn--i1abbnckbmcl9fb.xn--p1ai

Решение комбинаторных задач с помощью алгебры логики.

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

      Обычно используется следующая схема решения:
1. Изучается условие задачи.
2. Вводится система обозначений для логических высказываний.
3. Конструируется логическая формула, описывающая логические связи между всеми высказываниями, выделенными из условия задачи.
4. Определяются значения истинности этой логической формулы.
5. Из полученных значений истинности формулы определяются значения истин-ности введённых логических высказываний, на основании которых делается заключение о решении.
Рассмотрим текстовые задачи, которые могут быть решены с привлечением аппарата алгебры логики, т. е. основных законов алгебры логики.

ЗАДАЧА 1.


     Однажды гномы, решившие отправиться за сокровищами, собрались на совет, чтобы обсудить возможные опасности, которые их ожидают. Было высказано три предложения:
1. Их либо захватят гоблины, либо нападёт дракон, либо они заблудятся в лесу, либо их ожидают какие – то две, а может быть, и все три из этих опасностей.
2. Если дракон не нападёт, то они утонут в реке.
3. И дракон нападёт, и заблудятся в лесу.
     Помогавший им волшебник успокоил их и сказал, что второе и третье предположения ложны. Каких же опасностей следует ожидать гномам?
 

Решение:

Введём логические переменные:
x – гномов захватят гоблины;
y – на гномов нападёт дракон;
z – они утонут в реке;
w – они заблудятся в лесу.
     Первому высказыванию соответствует формула x+y+w, второму – y→z и третьему– z&w.
     С учётом, что второе и третье высказывания ложны, запишем истинное составное вы-сказывание и упростим его.
(x+y+w)&(y→z)&z&w= (x+y+w)&(y+z)&(z+w)= (x+y+w)&y&z&(z+w)= (x&y&z+y&z&w)&(z+w)= x&y&z+x&y&z&w+y&z&w= x&y&z+y&z&w.
     Из полученного выражения видно, что исходное высказывание истинно, когда истин-но x, а y и z – ложны, либо когда истинно w, а y и z – ложны, либо когда x и w одновременно истинны, а y и z – ложны. Возвращаясь к исходной интерпретации, можно сказать, что гно-мам следует приготовиться и к нападению гоблинов, и к переходу через лес.

ЗАДАЧА 2.


     Один король как – то подвергся нападению вражеской армии и был осаждён в крепо-сти, в которой были северные и южные ворота. Чтобы выдержать штурм, ему необходимо было точно знать, на какие из этих ворот готовится атака.
     Рано утром перед началом штурма к нему привели пленника, захваченного у против-ника. Об этом пленнике было известно, что он либо рыцарь, который всегда говорит правду, либо лжец, который всегда лжёт, и, кроме того, на все вопросы он отвечает только «да» или «нет».
      Король быстро понял, что задавать простые вопросы бесполезно. Если бы он спросил: «Назначен ли штурм на северные ворота?» - и получил бы ответ «да», то из этого ответа нельзя было бы сделать правильного вывода. Если бы штурм действительно был назначен на северные ворота, то рыцарь ответил бы «да», а лжец «нет». А если бы на южные, то рыцарь сказал бы «нет», а лжец – «да». Поскольку король не знал, кто перед ним (рыцарь или лжец), то ответ «да» не позволял бы понять, верно ли, что штурм назначен на северные ворота.
     Король впал в отчаяние, но присутствующий при допросе логик задал вопрос, с по-мощью которого удалось установить, на какие ворота готовится штурм. Какой это вопрос?


Решение:

Необходимо рассмотреть четыре возможности.

Место штурма               Кто пленник            Ответ
северные ворота           Рыцарь                     да
северные ворота             Лжец                       да
южные ворота                Рыцарь                    нет
южные ворота                  Лжец                       нет

       Надо сформулировать вопрос, ответ на который в первых двух случаях будет «да», и «нет» в двух остальных. Пусть вопрос будет таким: «Верно ли, что штурм назначен на юж-ные ворота и ты лжец, или неправда, что штурм назначен на южные ворота и ты рыцарь?»
       В первом случае (северные ворота – рыцарь) на первую часть вопроса: «Верно ли, что штурм назначен на южные вопросы и ты лжец?» - рыцарь ответит «нет», потому что на са-мом деле штурм назначен на северные ворота. На вторую часть вопроса: «Верно ли, что не-правда, что штурм назначен на южные ворота и ты рыцарь?» - рыцарь ответит «да», потому что это действительно неправда. Поэтому ответ на весь вопрос будет «да».
       Во втором случае (северные ворота – лжец) на первую часть вопроса лжец ответит «да», потому что на самом деле штурм назначен на северные ворота, а лжец говорит неправ-ду. Поэтому независимо от ответа на вторую часть вопроса ответ на весь вопрос будет «да», это следует из определения дизъюнкции.
       В третьем случае (южные ворота – рыцарь) на первую половину вопроса рыцарь отве-тит «нет», потому что он не лжец. На вторую половину вопроса он также скажет «нет», по-тому что верно, что штурм назначен на южные ворота и он рыцарь. Значит, ответ на весь во-прос будет «нет».
      В четвёртом случае (южные ворота – лжец) на первую половину вопроса лжец отве-тит «нет», потому что это истина. На вторую половину он также скажет «нет», потому что он не рыцарь, значит, это в самом деле неправда, но лжец вместо «да» всегда говорит «нет». От-сюда ответ на весь вопрос будет «нет».
       Таким образом, независимо от того, рыцарь это или лжец, каждый из них ответит «да», если штурм назначен на северные ворота, и «нет» - если на южные.

ЗАДАЧА 3.


       Менеджер банка должен установить 4 банкомата. В течение каждого дня работы должны выполняться следующие условия:
1. Если работает первый банкомат, то третий банкомат не должен работать, а второй и четвёртый должны.
2. Если работает третий банкомат, то первый и четвёртый не должны работать, а вто-рой должен.
3. Должен работать по крайней мере один банкомат.
     Необходимо определить наибольшее число дней, которое могут работать банкоматы при выполнении этих условий, так, чтобы их назначение ни в один из дней не повторялось, а также указать допустимое расписание на каждый день.
 

Решение:

     Максимальное количество дней и соответствующее расписание можно най-ти прямым перебором. При четырёх переменных надо рассмотреть 16 логических возможно-стей. Однако более рационально построить составное высказывание, истинное для заданных условий, а затем преобразовать соответствующую ему формулу к СДНФ. Введём логические переменные:
w – работает первый банкомат;
x – работает второй банкомат;
y – работает третий банкомат;
z – работает четвёртый банкомат.
      Первому условию соответствует формула w→x&y&z, а второму- y→w&x&z. Запи-шем формулу истинного составного высказывания, определяющего ежедневную работу бан-коматов в соответствии с первыми двумя условиями: (w→x&y&z)&(y→w&x&z)=(w+x&y&z)&(y+w&x&z). Раскроем скобки и получим: w&y+w&x&z+x&y&z. Учитывая, что выражения
(x&z+x&z+x&z+x&z)=1
(y+y)=1
(w+w)=1
       перепишем исходную формулу в виде эквивалентного выражения:
w&y&(x&z+x&z+x&z+x&z)+w&x&z&(y+y)+x&y&z&(w+w)= w&x&y&z+w&x&y&z+w&x&y&z+w&x&y&z+w&x&y&z+w&x&y&z+w&x&y&z+w&x&y&z
исключив из него повторяющиеся элементарные конъюнкции, а также конъюнкцию w&x&y&z, которая противоречит третьему условию, получим выражение в форме СДНФ: w&x&y&z+w&x&y&z+w&x&y&z+w&x&y&z+w&x&y&z.
        Анализируя его, можно сказать, что максимальное число дней, при котором нет по-вторений в работе банкоматов, равно пяти, потому что в полученном выражении 5 элемен-тарных конъюнкций, а каждая элементарная конъюнкция этого выражения определяет на-значение банкоматов на один день работы. Допустимое расписание работы может быть та-ким: в первый день работает четвёртый банкомат (это следует из того, что в первую конъ-юнкцию w&x&y&z переменная z входит без отрицания), во второй день – второй банкомат, в третий день должны работать второй и четвёртый, в четвёртый день – второй и третий бан-коматы и, наконец, в пятый день – первый, второй и четвёртый банкоматы.

ЗАДАЧА 4.


        Имеется множество из 8 различных букв {A, B, C, D, E, F, G, H}. Один из играющих задумывает любую букву из этого множества. Другой играющий должен угадать эту букву. Он имеет возможность задать три вопроса, ответы на которые должны быть «да» или «нет». Вопросы должны быть заданы независимо один от другого, т. е. второй играющий узнает от-веты только после того, как он задал все три вопроса. Какие вопросы необходимо задать?
 

Решение:

       Если выбрать какую – то букву из заданного множества и спросить, являет-ся ли она задуманной, то в общем случае потребуется 7 вопросов для установления искомой буквы. Чтобы была возможность определять любую букву при помощи трёх вопросов, надо разбить множество на три подмножества. Возьмём три такие подмножества: {B, D, F, H}, {E, F, G, H}, {C, D, G, H}.
        Три вопроса будут такими:
1. Входит ли задуманная буква в первое подмножество?
2. Входит ли задуманная буква во второе подмножество?
3. Входит ли задуманная буква в третье подмножество?
        Если получено три ответа «да», то задумана буква H, поскольку только она входит во все три подмножества. Если получены «да», «да», «нет», то задумана буква F, потому что только она входит в первое и второе подмножества, но не входит в третье. Если получены ответы «да», «нет», «да», то задумана буква D, потому что только она входит в первое и третье подмножества и не входит во второе, и т. д. Наконец, если получено три ответа «нет», то это буква A, потому что она не входит ни в одно из подмножеств.
       Этот пример иллюстрирует прямую аналогию между алгеброй логики и алгеброй множеств. Если вместо операции конъюнкции рассматривать операцию пересечения мно-жеств, а вместо операции дизъюнкции – операцию объединения множеств, то эти операции над подмножествами заданного множества подчиняются тем же законам, что и операции над высказываниями. В то же время любая алгебраическая система, подчиняющаяся этим зако-нам, называется булевой алгеброй. Поэтому если подмножества обозначать переменными, то с помощью операций объединения и пересечения можно строить сложные выражения (фор-мулы), также определяющие некоторые подмножества. Используя булеву алгебру, можно преобразовывать и упрощать формулы.

ЗАДАЧА 5.


       Трое друзей, болельщиков автогонок «Формула - 1», спорили о результатах пред-стоящего этапа гонок.
- Вот увидишь, Шумахер не придёт первым, - сказал Джон. - Первым будет Хилл.
- Да нет же, победителем будет, как всегда Шумахер,- воскликнул Ник. - А об Алези и говорить нечего, ему не быть первым.
Питер, к которому обратился Ник, возмутился:
- Хиллу не видать первого места, а вот Алези пилотирует самую мощную машину.
       По завершении этапа гонок оказалось, что каждое из двух предположений двоих дру-зей подтвердилось, а оба предположения третьего оказались неверными. Кто выиграл этап гонки?
 

Решение:

Введём обозначения для логических высказываний:
Ш – победит Шумахер;
Х – победит Хилл;
А – победит Алези.
      Реплика Ника «Алези пилотирует самую мощную машину» не содержит никакого ут-верждения о месте, которое займёт этот гонщик, поэтому в дальнейших рассуждениях не учитывается.
Зафиксируем высказывания каждого из друзей:
Джон: Ш&Х;
Ник: Ш&А;
Питер: Х;
       Учитывая то, что предположения двух друзей подтвердились, а предположения третьего неверны, запишем истинное высказывание:
(Ш&Х)&(Ш&А)&Х+(Ш&Х)&(Ш&А)&Х+(Ш&Х)&(Ш&А)&Х= (Ш+Х)&Ш&А&Х= Ш&А&Х.
Высказывание Ш&А&Х истинно только при Ш=1, А=0, Х=0.
Победителем этапа гонок стал Шумахер.

ЗАДАЧА 6.


       По обвинению в ограблении перед судом предстали Иванов, Петров, Сидоров. Следствием установлено следующее:
1. Если Иванов невиновен или Петров виновен, то Сидоров виновен.
2. Если Иванов невиновен, то Сидоров невиновен.
Виновен ли Иванов?
 

Решение:

Рассмотрим простые высказывания:
A = Иванов виновен,
B = Петров виновен,
C = Сидоров виновен.
Запишем на языке алгебры логики факты, установленные следствием:
(A+B)→C и A→C.
Пусть F(A,B,C) = ((A+B)→C)&(A→C).
Решить задачу – это значит указать, при каких значениях A это сложное высказыва-ние истинно. И если хотя бы в одном случае (при разных значениях B и C) F=1 при A=0 (Иванов невиновен), то у следствия недостаточно фактов для того, чтобы обвинить Иванова в преступлении.
Составим таблицу истинности: 

 

АВСF
0000
0010
0100
0110
1001
1011
1100
1111

 
Из таблицы истинности видно, что сложное высказывание истинно только когда A – истинно, т. е. Иванов виновен в ограблении.

ЗАДАЧА 7.


      На вопрос, кто из трёх школьников изучал логику, был получен правильный ответ: если изучал первый, то изучал и второй, но неверно, что если изучал третий, то изучал и вто-рой. Кто из учащихся изучал логику?
 

Решение:

Обозначим через P1, P2, P3, высказывания, состоящие в том, что, соответ-ственно, первый, второй, третий школьник изучали логику. Из условия задачи следует ис-тинность высказывания:
(P1→P2)&(P3→P2).
Воспользуемся тем, что A→B=A+B, и упростим полученное высказывание:
(P1+P2)&P3+P2)=(P1+P2)&(P3&P2)=(P1&P3&P2)+(P2&P3&P2).
Высказывание P2&P2 ложно, а следовательно, ложно и высказывание P2&P3&P2. По-этому истинным является высказывание P1&P3&P2, а это означает, что логику изучал третий учащийся, а первый и второй не изучали.

ЗАДАЧА 8.


Алёша, Боря и Гриша нашли в земле старинный сосуд. Рассматривая удивительную находку, каждый высказал по два предположения:
Алёша: «Это сосуд греческий и изготовлен в V веке».
Боря: «Это сосуд финикийский и изготовлен в III веке».
Гриша: «Это сосуд не греческий и изготовлен в IV веке».
Учитель истории сказал ребятам, что каждый из них прав только в одном из двух предположений.
Где и в каком веке изготовлен сосуд?
 

Решение:

Рассмотрим простые высказывания:
A = сосуд греческий,
B = сосуд финикийский,
C = сосуд изготовлен в III веке,
D = изготовлен в IV веке,
E = сосуд изготовлен в V веке.
Запишем предположения школьников на языке алгебры логики:
A&E (слова Алёши),
B&C (слова Бори),
A&D (слова Гриши).
    Из слов учителя следует, что каждое из этих высказываний ложно, так как каждый мальчик прав только в чём-то одном. Предположим, Алёша угадал, что сосуд греческий (А=1), но ошибся во времени его изготовления (Е=0). В противном случае (верно угадано время изготовления, но неправильно – место) А=0 и Е=1. Следовательно, всегда А+Е=1.
Рассуждая аналогично, получаем ещё два истинных сложных высказывания:
В+С=1,
А+D=1.
Если все эти высказывания логически перемножить, то получится истинное сложное высказывание:
(A+E)&(B+C)&(A+D)=1
Раскроем скобки:
(A&B+A&C+E&B+E&C)&(A+D)=1 (2)
Исходя из того, что сосуд мог быть изготовлен только в одной стране и в одном веке, запишем высказывания заведомо ложные:
A&B=0, 
E&C=0.
Получим из (2): 
(0+A&C+E&B+0)&(A+D)=1
(A&C+E&B)&(A+D)=1
A&C&A+A&C&D+E&B&A+E&B&D=1 (2´)
Снова запишем высказывания заведомо ложные:
A&A=0,
C&D=0,
E&D=0.
Следовательно:
A&C&A=0,
A&C&D=0,
E&B&D=0.
Подставим в (2´)
0+0+E&B&A+0=1
Значит, Е&B&A=1.
Мы установили, что сосуд финикийский и изготовлен в V веке, что удовлетворяет ус-ловию задачи. 

ЗАДАЧА 9.


Брауну, Джонсу и Смиту предъявлено обвинение в соучастии в ограблении банка. Похитители скрылись на поджидавшем их автомобиле. На следствии Браун показал, что преступники скрылись на синем «Бьюике», Джонс сказал, что это был чёрный «Крайслер», а Смит утверждает, что это был «Форд Мустанг», и ни в коем случае не синий. Стало извест-но, что желая запутать следствие, каждый из них указал правильно либо только марку маши-ны, либо только её цвет.
Какого цвета и какой марки был автомобиль?
 

Решение:

Рассмотрим простые высказывания:
A = машина синего цвета,
B = машина марки «Бьюик», 
C = машина чёрного цвета,
D = машина марки «Крайслер»,
E = машина марки «Форд Мустанг».
Так как либо цвет, либо марка машины каждым из соучастников названа верно, то из их слов можно заключить, что:
A+B=1 (из слов Брауна),
C+D=1 (из слов Джонса),
A+E=1 (из слов Смита).
Если все эти высказывания логически перемножить, то получится истинное высказы-вание:
(A+B)&(C+D)&(A+E) = 1&1&1 =1. (1)
По аналогии с алгеброй чисел выполним преобразование левой части этого выраже-ния:
(A&C&A)+(A&C&E)+(A&D&A)+(A&D&E)+(B&C&A)+(B&C&E)+(B&D&A)+(B&D&E)=1
Запишем заведомо ложные высказывания.
Во - первых:
A&A=0.
Так как разыскиваемый автомобиль определённой марки и цвета, то все логические произведения, содержащие высказывания о разных цветах одного автомобиля, являются ложными:
A&C=0,
D&E=0,
B&E=0,
B&D=0.
Следовательно:
A&C&A=0,
A&C&E=0,
A&D&A=0,
A&D&E=0,
B&C&E=0,
B&D&E=0,
B&D&A=0.
Подставим эти значения в (1):
0+0+0+0+(B&C&A)+0+0+0=1.
Единственное выражение, значение которого может быть истинным, это B&C&A. Действительно, чёрный «Бьюик» удовлетворяет условию задачи.
Следовательно, B&C&A=1, т. е. автомобиль был чёрного цвета марки «Бьюик».

Задача Эйнштейна.

Условие: Есть 5 домов разного цвета, стоящие в ряд. В каждом доме живет по одному человеку отличной от другого национальности. Каждый жилец пьет только один определенный напиток, курит определенную марку сигарет и держит животное. Никто из пяти человек не пьет одинаковые напитки, не курит одинаковые сигареты и не держит одинаковых животных. 


Известно, что:
Англичанин живет в красном доме.
Швед держит собаку. 
Датчанин пьет чай. 
Зеленой дом стоит слева от белого. 
Жилец зеленого дома пьет кофе. 
Человек, который курит Pallmall, держит птицу. 
Жилец среднего дома пьет молоко. 
Жилец из желтого дома курит Dunhill. 
Норвежец живет в первом доме. 
Курильщик Marlboro живет около того, кто держит кошку. 
Человек, который содержит лошадь, живет около того, кто курит Dunhill.
Курильщик Winfield пьет пиво. 
Норвежец живет около голубого дома. 
Немец курит Rothmans. 
Курильщик Marlboro живет по соседству с человеком, который пьет воду. 
Вопрос: У кого живет рыба?

Решение:

ШАГ 1
По условию, норвежец живёт в первом доме (9). Из (14) следует, что второй дом синий.
Какого цвета первый дом? Он не может быть ни зелёным, ни белым, поскольку дома? этих двух цветов должны располагаться рядом (5). Красным он тоже не может быть, потому что в красном доме живёт англичанин (1). Итак, первый дом жёлтый.
Следовательно, в первом доме курят «Данхел» (7), а во втором доме держат лошадь (11).
Что пьёт норвежец (который живёт в первом, жёлтом, доме и курит «Данхел»)? Это не чай, поскольку чай пьёт датчанин (4). И не кофе, потому что кофе пьют в зелёном доме (3). И не молоко, которое пьют в третьем доме (8). И не пиво, потому что человек, который пьёт пиво, курит «Винфилд» (12). Следовательно, норвежец пьёт воду.

ДОМ12345
ЦВЕТжелтый    
НАЦИОНАЛЬНОСТЬнорвежец    
НАПИТОКвода молоко  
СИГАРЕТЫданхел    
ЖИВОТНОЕ лошадь  
 

 

ШАГ 2
Из (15) следует, что человек, живущий во втором, синем, доме, курит «Мальборо».
Какой национальности человек, живущий во втором, синем, доме, предпочитающий «Мальборо» и держащий лошадь? Это не норвежец — он в первом доме (9). Не англичанин — он в красном доме (1). Не швед — у шведа собака (2). Не немец — немец курит «Ротманс» (13). Значит, во втором доме живёт датчанин и, как следует из (4), пьёт чай.

ДОМ12345
ЦВЕТжелтыйсиний    
НАЦИОНАЛЬНОСТЬнорвежецдатчанин   
НАПИТОКводачаймолоко  
СИГАРЕТЫданхелмальборо   
ЖИВОТНОЕ лошадь  
 

 

ШАГ 3
Зеленый дом не может быть третьим, поскольку в нём пьют кофе, а не молоко (3). Зеленый дом не может быть пятым, поскольку справа от него есть дом (5). Следовательно, зеленый дом — четвёртый. Значит, белый дом — пятый, а красный — третий, и в нём живёт англичанин (1). В зеленом доме пьют кофе, и для белого дома остаётся только пиво. Из (12) следует, что в белом доме курят «Винфилд».

ДОМ12345
ЦВЕТжелтыйсинийкрасныйзеленыйбелый
НАЦИОНАЛЬНОСТЬнорвежецдатчанинангличанин  
НАПИТОКводачаймолококофепиво
СИГАРЕТЫданхелмальборо  винфилд
ЖИВОТНОЕ лошадь  
 

 

ШАГ 4
Где живёт немец, который курит «Ротманс» (13)? Он может жить только в четвёртом, зелёном доме. А значит, человек, который курит «Пал Мал» и разводит птиц, может жить только в третьем, красном доме — это англичанин.

ДОМ12345
ЦВЕТжелтыйсинийкрасныйзеленыйбелый
НАЦИОНАЛЬНОСТЬнорвежецдатчанинангличаниннемец 
НАПИТОКводачаймолококофепиво
СИГАРЕТЫданхелмальборопал малротмансвинфилд
ЖИВОТНОЕ лошадьптицы 
 

Тогда шведу, у которого собака (2), остаётся пятый дом. По условию (10), кошка живет в первом или в третьем доме, но в третьем доме — птицы, а значит, кошка в первом доме.

Следовательно, рыбку держит немец.
 

ДОМ12345
ЦВЕТжелтыйсинийкрасныйзеленыйбелый
НАЦИОНАЛЬНОСТЬнорвежецдатчанинангличаниннемецшвед
НАПИТОКводачаймолококофепиво
СИГАРЕТЫданхелмальборопал малротмансвинфилд
ЖИВОТНОЕкошкалошадьптицырыбкасобака
 

    Конечно, это решение предполагает, что недостающие в условиях задачи животное и есть искомая рыбка. Кроме того, предполагается, что первый дом — слева. Тем не менее, прямо в условиях это нигде не указано. Многие поэтому утверждают, что единственный правильный ответ — «в задаче не хватает данных», так как мы не можем быть уверены в том, что рыбки, например, вообще живут хотя бы в одном из этих домов. Однако, этим суждением зачастую «покрывают» свою неудачу в решении задачи.
     Если предположить, что первый дом находится справа, и в нём живёт норвежец (по условию задачи), то первым слева стоит зелёный, а рядом белый, дальше красный и синий. Разница между первым вариантом решения задачи, в расположении домов по цветам (а в условии об этом ничего не сказано). В итоге решение задачи такое же как и в первом варианте — рыбок разводит немец, пьёт — кофе, курит — Ротманс.

 

 

 

www.openclass.ru

Задачи по теме "Алгебра логики"

Задачи по теме «Алгебра логики»


Задача 1. В школе-новостройке в каждой из двух аудиторий может находиться либо кабинет информатики, либо кабинет физики. На аудиториях повесили шутливые таблички. На первой аудитории повесили табличку «По крайней мере, в одной из этих аудиторий размещается кабинет информатики», а на второй аудитории – табличку с надписью «Кабинет физики находится в другой аудитории». Проверяющему, который пришел в школу, известно только, что надписи на табличках или обе истинны, либо обе ложны. Помогите проверяющему найти кабинет информатики.

Задача 2. Аня, Вика и Сергей решили пойти в кино. Учитель, хорошо знавший ребят, высказал предложения:

  1. Аня пойдет в кино только тогда, когда пойдут Вика и Сергей;

  2. Аня и Сергей пойдут в кино вместе или же оба останутся дома;

  3. чтобы Сергей пошел в кино, необходимо, чтобы пошла Вика.

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

Ответ. Т.к. два высказывания должны быть «истина», а одно «ложь», то правильный ответ следующий: Аня и Сергей не пойдут в кино, а пойдет Вика.

Задача 2. Алеша, Боря и Гриша нашли в земле старинный сосуд. Рассматривая удивительную находку, каждый высказал по два предположения:
Алеша: «Это сосуд греческий и изготовлен в V веке».
Боря: «Это сосуд финский и изготовлен в Ш веке».
Гриша: «Это сосуд не греческий и изготовлен в IV веке».
Учитель истории сказал ребятам, что каждый из них прав только в одном из двух предположений. Где и в каком веке изготовлен сосуд?

Задача 3. В нарушении правил обмена валюты подозревают четыре работника банка – А, В, С и D. Известно, что:

  1. Если А нарушил, то и В нарушил правила обмена валюты.

  2. Если В нарушил, то и С нарушил или А не нарушал.

  3. Если D не нарушил, то А нарушил, а С не нарушал.

  4. Если D нарушил, то и А нарушил.

Кто из подозреваемых нарушил правила обмена валюты?

Задача 4. На вопрос, какая завтра будет погода, синоптик ответил:

    1. «если не будет ветра, то будет пасмурная погода без дождя»;

    2. «если будет дождь, то будет пасмурно и без ветра»;

    3. «если будет пасмурная погода, то будет дождь и не будет ветра».

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

Задача 5. Определите, кто из подозреваемых участвовал в преступлении, если известно:

  1. Если Иванов не участвовал или Петров участвовал, то Сидоров участвовал;

  2. Если Иванов не участвовал, то Сидоров не участвовал.

Задача 6. Виктор, Роман, Леонид и Сергей заняли на олимпиаде по физике четыре первых места. Когда их спросили о распределении мест, они дали три таких ответа:

  1. Сергей – первый, Роман – второй;

  2. Сергей – второй, Виктор – третий;

  3. Леонид – второй, Виктор – четвертый.

Известно, что в каждом ответе только одно утверждение истинно. Как распределились места?

infourok.ru

Методы решения логических задач

Исходными данными в логических задачах являются высказывания. Эти высказывания и взаимосвязи между ними бывают так сложны, что разобраться в них без ис­пользования специальных методов достаточно трудно.

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

Формальный способ решения логических задач

  1. Выделить из условия задачи элементарные (простые) высказывания и обозначить их буквами.

  2. Записать условие задачи на языке алгебры логики, соединив простые высказывания в сложные с помо­щью логических операций.

  3. Составить единое логическое выражение для всех тре­бований задачи.

  4. Используя законы алгебры логики, попытаться либо упро­стить полученное выражение и вычислить все его зна­чения, либо построить таблицу истинности для рас­сматриваемого выражения, либо доказать истинность (ложность) некоторых утверждений методом рассуждений.

  1. Выбрать решение — набор значений простых выска­зываний, при котором построенное логическое выра­жение является истинным.

  1. Проверить, удовлетворяет ли полученное решение условию задачи.

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

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

Задача «Уроки логики». На вопрос, кто из трех учащихся изучал логику, был получен ответ: «Если изучал первый, то изучал и вто­рой, но неверно, что если изучал третий, то изучал и второй». Кто из учащихся изучал логику?

Решение. Введём обозначения:

  • Р1 – первый учащийся изучал логику;

  • Р2 – второй учащийся изучал логику;

  • Р3 – третий учащийся изучал логику.

Из условия задачи следует истинность высказывания . Воспользуемся соотношением (20) и упростим исходное высказывание:

.

Высказывание (согласно (11)), а, следовательно, ложно и высказывание . Поэтому должно быть истинным высказывание .

Ответ. Логику изучал третий учащийся, а первый и второй не изучали.

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

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

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

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

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

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

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

Ш — победит Шумахер; Х — победит Хилл; А — победит Алези.

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

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

Джон: ,Ник: , Питер: .

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

=1.

Упростим это выражение. Используя (11), установим, что первые два слагаемые тождественно-ложные. Тогда, с учётом формул де Моргана для третьего слагаемого:

Произведение будет истинным только при Ш=1, А=0, Х=0.

Ответ. Победителем этапа гонок стал Шумахер.

studfiles.net

Применение инструмента алгебры логики при решении логических задач

История с амфорой

Антон, Борис и Григорий нашли в земле сосуд, о котором каждый высказал по два предположения:

  • Антон: «Сосуд греческий и изготовлен в V столетии»;

  • Борис: «Сосуд финикийский и изготовлен в III столетии»;

  • Григорий: «Сосуд не греческий и изготовлен в IV столетии».

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

Решение:

Введем следующие обозначения:

$G$ -- «Сосуд греческий»;

$F$ -- «Сосуд финикийский»;

$S_3$ -- «Сосуд изготовлен в $III$ столетии»;

$S_4$ -- «Сосуд изготовлен в $IV$ столетии»;

$S_5$ -- «Сосуд изготовлен в $V$ столетии».

Запишем условие задачи с помощью обозначений:

Антон прав только в одном предположении: $G = 1$ или $S_5 = 1$. Тогда $G\overline{S_5}\vee \overline{G}S_5=1$.

Аналогично для слов Бориса: $F\overline{S_3}\vee \overline{F}S_3=1$.

Для слов Григория: $\overline{G}\overline{S_4}\vee GS_4=1$.

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

\[S_3\overline{S_4}\overline{S_5}\vee \overline{S_3}S_4\overline{S_5}\vee \overline{S_3}\overline{S_4}S_5=1,\] \[F\overline{G}\vee \overline{F}G=1.\]

Применим операцию логического умножения к полученным тождественно истинным высказываниям, результат которого также должен быть тождественно истинным:

\[\left(G\overline{S_5}\vee \overline{G}S_5\right)\wedge \left(F\overline{S_3}\vee \overline{F}S_3\right)\wedge \left(\overline{G}\overline{S_4}\vee GS_4\right)\wedge \left(F\overline{G}\vee \overline{F}G\right)\wedge \] \[\wedge \left(S_3\overline{S_4}\overline{S_5}\vee \overline{S_3}S_4\overline{S_5}\vee \overline{S_3}\overline{S_4}S_5\right)=\]

Перемножим первую на третью скобку и вторую на четвертую:

\[=\left(G\overline{S_5}\overline{G}\overline{S_4}\vee \overline{G}S_5\overline{G}\overline{S_4}\vee G\overline{S_5}GS_4\vee \overline{G}S_5GS_4\right)\wedge \] \[\wedge \left(F\overline{S_3}F\overline{G}\vee \overline{F}S_3F\overline{G}\vee F\overline{S_3}\overline{F}G\vee \overline{F}S_3\overline{F}G\right)\wedge \left(S_3\overline{S_4}\overline{S_5}\vee \overline{S_3}S_4\overline{S_5}\vee \overline{S_3}\overline{S_4}S_5\right)=\]

Т.к. $G\overline{G}=0$, $GG=G$, $\overline{G}\overline{G}=\overline{G}$, упростим выражения:

\[=\left(\overline{G}S_5\overline{S_4}\vee G\overline{S_5}S_4\right)\wedge \left(F\overline{S_3}\overline{G}\vee \overline{F}S_3G\right)\wedge \left(S_3\overline{S_4}\overline{S_5}\vee \overline{S_3}S_4\overline{S_5}\vee \overline{S_3}\overline{S_4}S_5\right)=\]

Перемножим первые две скобки и упростим выражение:

\[=\left(\overline{G}S_5\overline{S_4}\overline{F}S_3G\vee G\overline{S_5}S_4\overline{F}S_3G\vee \overline{G}S_5\overline{S_4}F\overline{S_3}\overline{G}\vee G\overline{S_5}S_4F\overline{S_3}\overline{G}\right)\wedge \] \[\wedge \left(S_3\overline{S_4}\overline{S_5}\vee \overline{S_3}S_4\overline{S_5}\vee \overline{S_3}\overline{S_4}S_5\right)=\] \[=\left(G\overline{S_5}S_4\overline{F}S_3\vee \overline{G}S_5\overline{S_4}F\overline{S_3}\right)\wedge \left(S_3\overline{S_4}\overline{S_5}\vee \overline{S_3}S_4\overline{S_5}\vee \overline{S_3}\overline{S_4}S_5\right)=\] \[=\left(G\overline{S_5}S_4\overline{F}S_3\vee \overline{G}S_5\overline{S_4}F\overline{S_3}\right)\wedge \left(S_3\overline{S_4}\overline{S_5}\vee \overline{S_3}S_4\overline{S_5}\vee \overline{S_3}\overline{S_4}S_5\right)=\overline{G}S_5\overline{S_4}F\overline{S_3};\]

$\overline{G}S_5\overline{S_4}F\overline{S_3}=1$, что возможно только в случае:

\[\overline{G}=1, S_5=1, \overline{S_4}=1, F=1, \overline{S_3}=1.\]

Ответ: сосуд финикийский и изготовлен в $V$ столетии.

spravochnick.ru

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

Обычно используется следующая схема решения:
  • изучается условие задачи;
  • вводится система обозначений для логических высказываний;
  • конструируется логическая формула, описывающая логические связи между всеми высказываниями условия задачи;
  • определяются значения истинности этой логической формулы;
  • из полученных значений истинности формулы определяются значения истинности введённых логических высказываний, на основании которых делается заключение о решении.
Задача.
Три свидетеля дорожного происшествия сообщили сведения о скрывшемся нарушителе. Боб утверждает, что тот был на красном «Рено», Джон сказал, что нарушитель уехал на синей «Тойоте», а Сэм показал, что машина была точно не красная, и по всей видимости, это был «Форд».
Когда удалось отыскать машину, выяснилось, что каждый из свидетелей точно определил только один из параметров автомобиля. А в другом ошибся, какая и какого цвета была машина у нарушителя?
Ответ записать в виде двух слов, разделенных пробелом: МАРКА, ЦВЕТ.
Решение.
Обозначим высказывания:
A = «машина красного цвета»;
B = «машина была «Рено»;
C = «машина синего цвета»;
D = «машина была «Тойота»;
E = «машина была «Форд».
Согласно условию:
из показаний Боба следует, что A \/ B истинно;
из показаний Джона следует, что C \/ D истинно;
из показаний Сэма следует, что ¬A \/ E истинно.
Следовательно, истинна конъюнкция (A \/ B) /\ (C \/ D) /\ (¬A \/ E) = 1
Раскрывая скобки, получаем:
(A \/ B) /\ (C \/ D) /\ (¬A \/ E) = (A /\ C \/ A /\ D \/ B /\ C \/ B /\ D) /\ ( ¬A \/ E) =
A /\ C /\ ¬A \/ A /\ D /\ ¬A \/ B /\ C /\ ¬A \/ B /\ D /\ ¬A \/ A /\ C /\ E \/ A /\ D /\ E \/ B /\ C /\ E \/ B /\ D /\ E = 1.
Из полученных восьми слагаемых семь (согласно условию) являются ложными. Остается единственное истинное слагаемое:
B /\ C /\ ¬A = 1.
Значит, нарушитель скрылся на автомобиле «Рено» синего цвета.
Ответ: РЕНО, СИНИЙ.

Пример.

Трое друзей, болельщиков автогонок "Формула-1", спорили о результатах предстоящего этапа гонок.
— Вот увидишь, Шумахер не придет первым, — сказал Джон. Первым будет Хилл.
— Да нет же, победителем будет, как всегда, Шумахер, — воскликнул Ник. — А об Алези и говорить нечего, ему не быть первым.
Питер, к которому обратился Ник, возмутился:
— Хиллу не видать первого места, а вот Алези пилотирует самую мощную машину.
По завершении этапа гонок оказалось, что каждое из двух предположений двоих друзей подтвердилось, а оба предположения третьего из друзей оказались неверны. Кто выиграл этап гонки?

Решение.

Введем обозначения для логических высказываний:
Ш — победит Шумахер;
Х — победит Хилл;
А — победит Алези.
Реплика Ника "Алези пилотирует самую мощную машину" не содержит никакого утверждения о месте, которое займёт этот гонщик, поэтому в дальнейших рассуждениях не учитывается.
Зафиксируем высказывания каждого из друзей:

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

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

Ответ.

Победителем этапа гонок стал Шумахер.

Задача для самопроверки:
На перемене в кабинете биологии 8 ребят баловались и разбили дорогой микроскоп. Их всех вызвали к директору и выслушали:
Ира: Это Антон разбил.
Наташа: Нет, Антон не бил!
Сергей: А я тоже знаю, что это Наташа разбила!
Антон: Нет, ни Наташа, ни Сергей этого не делали!
Оля: А я видела, что разбил Сергей!
Максим: Это кто-то чужой!
Костя: Это либо Наташа, либо Сергей – больше некому!
Кто разбил микроскоп, если известно, что из этих восьми высказываний истинны только два?
Ответ записать в виде первой буквы имени.
 

logikinformatik.blogspot.com

Author: alexxlab

Отправить ответ

avatar
  Подписаться  
Уведомление о