Главная страница
Навигация по странице:

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

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

  • Задача 3 «История с амфорой».

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


    Скачать 93.19 Kb.
    НазваниеРешение задач с помощью алгебры логики
    Дата06.01.2019
    Размер93.19 Kb.
    Формат файлаdocx
    Имя файла2.docx.docx
    ТипРешение
    #53972

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

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

    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 ˅ B˄A) ˄ (¬B ˅ C˄A) =

    = (¬A ˅ B ˄ ¬C) ˄ (¬B ˅ C˄A) ˄ (¬C ˅ B˄A) = (¬A ˄¬ B v B˄¬C˄¬B v ¬A˄C˄A ˅ B˄¬C˄C˄A) ˄
     (C ˅ B˄A)= ¬A ˄ ¬B ˄(C ˅ B˄¬A) =A˄¬B˄C ˅ ¬ 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 веке» — V3;
    «Сосуд изготовлен в IV веке» — V4;
    «Сосуд изготовлен в V веке» — V5.

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

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

    Таким образом, тождественно истинным будет высказывание: G¬V5 ˅ ¬GV5.=1

    Аналогично, из слов Бори и учителя следует: F¬V3 ˅ ¬FV3 = 1, а из слов Гриши и учителя: ¬G¬V4˅GV4 = 1.

    Кроме того, ясно, что сосуд может быть изготовлен только в одном из веков и только в одной из стран. Эти условия можно записать так: V3¬V4¬V5  ˅ ¬V3V4¬V5  ˅ ¬V3¬V4V5 = 1,F¬G ˅ ¬FG = 1.

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

    1 = (G¬V5 ˅ ¬GV5) ˄ (F¬V3 ˅¬FV3) ˄ (¬G¬V4 ˅ GV4) ˄ (F¬G ˅ ¬FG) ˄(V3¬V4¬V5  ˅ ¬V3V4¬V5  ˅ ¬V3¬V4V5) =

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

    =(G¬V5¬G¬V4˅¬GV5¬G¬V4  ˅ G¬V5GV4  ˅ ¬GV5 GV4)˄( F¬V3F¬G˅¬FV3 F¬G˅ F¬V3 ¬FG  ˅ ¬FV3¬FG) ˄ (V3¬V4¬V5  ˅ ¬V3V4¬V5 ˅ ¬V3¬V4V5) =

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

    =(¬GV5¬V4  ˅ ¬V5GV4 ) ˄( ¬FV3G ˅¬V3 F¬G)˄ (V3¬V4¬V5  ˅ ¬V3V4¬V5  ˅ ¬V3¬V4V5) =

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

    (¬GV5¬V4  ¬FV3G˅¬V5GV4¬FV3G˅¬GV5¬V4  ¬V3 F¬G ˅ ¬V5GV4¬V3F¬G) ˄ (V3¬V4¬V5  ˅ ¬V3V4¬V5  ˅ (¬V3¬V4V5)=(¬V5V4¬FV3G˅¬GV5¬V4  ¬V3 F) ˄ (V3¬V4¬V5  ˅ ¬V3V4¬V5  ˅ ¬V3¬V4V5)= ¬GV5¬V4  ¬V3 F

    ¬GV5¬V4  ¬V3 F=1, если ¬G=1, V5=1, ¬V=1, ¬V3=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. Проанализируем результат:

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

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

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


    написать администратору сайта