Занятие 2 (часть 2) Методы решения логических задач

Способ решения логических задач 1. Выделить из условия задачи элементарные высказывания и обозначить их буквами. 2. Записать условие задачи с помощью логических операций. 3. Составить единое логическое выражение для всех требований задачи. 4. Используя законы алгебры логики, упростить выражение и вычислить его значения либо построить для него таблицу истинности. 5. Выбрать решение набор значений простых высказываний, при котором построенное логическое выражение является истинным. 6. Проверить, удовлетворяет ли полученное решение условию задачи.

Примеры

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

Решение Обозначим Р 1 – логику изучал первый учащийся, Р 2 – логику изучал второй учащийся, Р 3 – логику изучал третий учащийся. Выражение (Р 1 Р 2 ) & (Р 3 Р 2 ) истинно. Упростим выражение (Р 1 Р 2 ) & (Р 3 Р 2 ) = (Р 1 v Р 2 ) & (Р 3 v Р 2 ) = = (Р 1 v Р 2 ) & Р 3 & Р 2 =Р 1 & Р 3 & P 2 v Р 2 & Р 3 & Р 2

Высказывание Р 2 & Р 2 - ложно, а это значит, ложно и высказывание Р 2 & Р 3 & Р 2. Поэтому истинно высказывание Р 1 & Р 3 & Р 2. Логику изучал третий учащийся, а первый и второй не изучали.

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

Рассмотрим высказывания: А = {Иванов виновен}, В = {Петров виновен}, С = {Сидоров виновен}. Запишем на языке алгебры логики факты, установленные следствием: (A v В) С,А С. Обозначим F = ((A v В) С) & (А С)

Составим таблицу истинности ABCF

Из анализа таблицы следует, что F истинно только в тех случаях, когда А истинно, т. е. Иванов в ограблении виновен.

Задача «Максимальная прибыль» Три подразделения А, В, С фирмы стремились получить максимальную прибыль. 1. А получит максимальную прибыль только тогда, когда получат максимальную прибыль В и С, 2. Либо А и С получат максимальную прибыль одновременно, либо одновременно не получат, 3. Для того чтобы подразделение С получило максимальную прибыль, необходимо, чтобы и В получило максимальную прибыль. Одно из трех предположений оказалось ложно, а остальные два истинны. Какие подразделения получили максимальную прибыль?

Решение А = {А получит максимальную прибыль}, В = {В получит максимальную прибыль}, С = {С получит максимальную прибыль}. 1) F 1 = А В & С; 2) F 2 = А & С v А & С; 3) F 3 = С В.

Таблица истинности для F 1, F 2, F 3 АBCF1F1 F2F2 F3F

Ответ В и С получат максимальную прибыль.

Задачи

Задача «Валютные махинации» В нарушении правил обмена валюты подозреваются четверо Антипов (А), Борисов (B), Цветков (С) и Дмитриев (D). Известно: 1. если А нарушил правила обмена валюты, то и B нарушил; 2. если В нарушил, то и С нарушил или А не нарушил; 3. если D не нарушил, то А нарушил, а С не нарушил; 4. если D нарушил, то и А нарушил. Кто нарушил правила обмена валюты?

Решение А = {А нарушил правила обмена валюты}, В = {В нарушил правила обмена валюты}, С = {С нарушил правила обмена валюты}, D = {D нарушил правила обмена валюты}. 1) А В = 1 2) B (С v А) = 1 3) D A & C = 1 4) D A = 1

Обобщенная формула (A B) & (B C v A) & (D A & C) & (D A) = 1 1) (A v B)(B v C v A) = = AB v BB v AC v BC v AA v BA = = A(B v C v 1 v B) v BC = A v BC 2) (D v AC)(D v A) = DD v ACD v DA v ACA = = ACD v AD v AC = AC(D v 1) v AD = AC v AD 3) (A v BC)(AC v AD) = = AAC v AAD v ABCC v ABCD = ABCD ИТОГ:A & B & C & D = 1 123

Ответ Правила обмена валюты нарушили все подозреваемые работники: Антипов, Борисов, Цветков и Дмитриев.

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

Решение А = {марка машины Бьюик}, В = {марка машины Крайслер}, С = {марка машины Форд Мустанг}, D = {цвет машины – синий}, E = {цвет машины – черный}. 1) А D = 1 2) B E = 1 3) C D = 1

Обобщенная формула (A D) & (B E) & (C D) = 1 (AD v AD) & (BE v BE) & (CD v CD) = = (ADCDvADCDvADCDvADCD)(BEvBE) = = (ACD v ACD)(BE v BE) = = ABCDE v ABCDE v ABCDE v ABCDE ABCDE = 1 0 (по усл.)

Ответ A & E – Черный Бьюик

Задача «Экспедиция» Из 8-ми претендентов А, В, С, D, Е, F, G и Н отобрать шестерых: биолога, гидролога, радиста, синоптика, механика и врача. Биологи Е и G, гидрологи В и F, синоптики F и G, радисты С и D, механики С и Н, врачи А и D. В экспедиции каждый сможет выполнять только одну обязанность. Кого и кем следует взять в экспедицию, если F не может ехать без В, D без С и без Н, С не может ехать одновременно с G, а А вместе с В?

Решение F & B = 1 D & C & H = 1 C & G = 1 A & B = 1 F & B & D & C & H & C & G & A & B = = A & B & C & D & F & H & G = 1 Не едут: A, G. Едут: B, C, D, F, H и E.

Ответ ДолжностьУсловиеЕдет биологE v GE гидрологB v FB синоптикF v GF радистC v DC механикC v HH врачA v DD