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

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

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

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 =

= ¬A&¬B&¬C

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 веке» — V₃;
«Сосуд изготовлен в IV веке» — V₄;
«Сосуд изготовлен в V веке» — V₅.

Формализуем задачу, записав в данных обозначениях условия задачи.

Со слов учителя следует, что Алеша прав только в чем-то одном: или G = 1, или V₅ = 1.

Таким образом, тождественно истинным будет высказывание: G¬V₅ v ¬GV₅.=1

Аналогично, из слов Бори и учителя следует: F¬V₃ v ¬FV₃ = 1,

а из слов Гриши и учителя: ¬G¬V₄ v GV₄ = 1.

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

V3¬V4¬V₅  ˅ ¬V3V4¬V5  ˅ ¬V3¬V4V5 = 1,

F¬G v ¬FG = 1.

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

1 = (G¬V₅ v ¬GV₅) & (F¬V₃ v ¬FV₃) & (¬G¬V₄ v GV₄) & (F¬G v ¬FG) & (V3¬V4¬V₅  ˅ ¬V3V4¬V5  ˅ ¬V3¬V4V5) =

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

=(G¬V₅¬G¬V₄˅¬GV₅¬G¬V₄  ˅ G¬V₅GV₄  ˅ ¬GV₅ GV₄)&( F¬V₃ F¬G˅¬FV₃ F¬G˅ F¬V₃ ¬FG  ˅ ¬FV₃¬FG) & (V3¬V4¬V₅  ˅ ¬V3V4¬V5  ˅ ¬V3¬V4V5) =

учитывая, что, G¬G = 0, GG = G,¬ G¬G =¬ G, упростим выражения в первой и второй скобках:

=(¬GV₅¬V₄  ˅ ¬V₅GV₄ ) &( ¬FV₃G ˅¬V₃ F¬G)& (V3¬V4¬V₅  ˅ ¬V3V4¬V5  ˅ ¬V3¬V4V5) =

(перемножим первую и вторую скобки и упростим полученное выражение)

(¬GV₅¬V₄  ¬FV₃G˅¬V₅GV₄¬FV₃G˅¬GV₅¬V₄  ¬V₃ F¬G ˅ ¬V₅GV₄¬V₃ F¬G) & (V3¬V4¬V₅  ˅ ¬V3V4¬V5  ˅ (¬V3¬V4V5)= (¬V₅V₄¬FV₃G˅¬GV₅¬V₄  ¬V₃ F) & (V3¬V4¬V₅  ˅ ¬V3V4¬V5  ˅ ¬V3¬V4V5)= ¬GV₅¬V₄  ¬V₃ F

¬GV₅¬V₄  ¬V₃ F=1, если ¬G=1, V₅=1, ¬V₄ =1_, ¬V₃=1, F=1

Итак, сосуд финикийский и изготовлен в V веке.

Задача 4  «Поход в кино».

Андрей, Аня и Маша решили пойти в кино. Каждый из них высказал свои пожелания по поводу выбора фильма.

Андрей сказал: «Я хочу посмотреть французский боевик».

Маша сказала: «Я не хочу смотреть французскую комедию».

Аня сказала: «Я хочу посмотреть американскую мелодраму».

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

Решение:

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

А — «Французский фильм»

В — «Боевик»

С — «Комедия»

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

а) «Французский боевик» ¬A&B˅A&¬B

б) «Американскую мелодраму» ¬¬A&¬B˅¬ А &¬¬В

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

3. Запишем произведение :
  (¬A&B˅A&¬B) & (¬¬A&¬B˅¬ А&¬¬В)&( ¬¬A&C˅¬A&¬C)=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&B&¬C˅ A&¬B&C =1

6. Составим таблицу истинности для выражения:
 ¬A&B&¬C˅ A&¬B&C:

А	В	С	¬A&B&¬C˅A&¬B&C
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	0

7. Найдем по таблице значения переменных, для которых F=1.

 А)

0	1	0	1
Б)
1	0	1	1

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

 Результат Б) не является решением, т.к. в ответе Маши оба утверждения оказываются неверными, что проти­воречит условию задачи.

 Результат А) полностью удовлетворяет усло­вию задачи и поэтому является верным решением.

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

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