---
Пройти Антиплагиат ©

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

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

 Наименование параметра  Значение
Тема статьи: Применение инструмента алгебры логики при решении логических задач
Рубрика (тематическая категория) Технические дисциплины

Articles-ads




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

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

  1. изучение условия;

  2. выделение простых высказываний, которым даются имена;

  3. запись условия задачи языком алгебры логики;

  4. составление конечнои̌ формулы, чᴇᴦο объединяются формулы каждого утверждения с помощью логического умножения и приравнивается полученная формула единице;

  5. упрощение формулы, анализ полученного результата или составление таблицы истинности, нахождение по таблице значения переменных, которых F=1 , анализ результатов.

Законы алгебры логики



Рисунок 1.

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

Пример 1

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

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

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

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

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

Решение:

Решение с помощью таблицы истинности

Пусть:

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

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

S -- ʼʼСемен участвовал в преступленииʼʼ.

Запишем условия задачи в виде формул:

overline{I}vee P o S и overline{I}vee P o overline{S}

Построим таблицу истинности всœех возможных наборов:



Рисунок 2.

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

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

[Fleft(I,P,S ight)=left(overline{I}vee P o S ight)wedge left(overline{I} o overline{S} ight)=left(left(overline{overline{I}vee P} ight)vee S ight)wedge left(Ivee overline{S} ight)=] [=left(Iwedge overline{P}vee S ight)wedge left(Ivee overline{S} ight)=Iwedge overline{P}vee Iwedge Svee Iwedge overline{P}wedge overline{S}vee 0=Iwedge overline{P}vee Iwedge S=] [=Iwedge left(overline{P}vee S ight)]

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

Пример 2

Задача о погоде

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

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

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

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

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

Решение:

  1. Пусть:

    A -- ʼʼНе будет ветраʼʼ;

    B -- ʼʼПасмурноʼʼ;

    C -- ʼʼДождьʼʼ.

  2. Запишем с помощью переменных A , B , C высказывания синоптика:

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

    [A o Bwedge overline{C}]

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

    [C o Bwedge A]

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

    [B o Cwedge A]

    Составим конъюнкцию указанных функций:

    [F=left(A o Bwedge overline{C} ight)wedge left(C o Bwedge A ight)wedge left(B o Cwedge A ight)]

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

    [F=left(A o Bwedge overline{C} ight)wedge left(C o Bwedge A ight)wedge left(B o Cwedge A ight)=] [=left(overline{A}vee Bwedge overline{C} ight)wedge left(overline{C}vee Bwedge A ight)wedge left(overline{B}vee Cwedge A ight)=] [=left(overline{A}vee Bwedge overline{C} ight)wedge left(overline{B}vee Cwedge A ight)wedge left(overline{C}vee Bwedge A ight)=] [=left(overline{A}wedge overline{B}vee Bwedge overline{C}wedge overline{B}vee overline{A}wedge Cwedge Avee Bwedge overline{C}wedge Cwedge A ight)wedge left(overline{C}vee Bwedge A ight)=] [=overline{A}wedge overline{B}wedge left(Cvee Bwedge overline{A} ight)=overline{A}wedge overline{B}wedge Cvee overline{A}wedge overline{B}wedge Bwedge overline{A}=overline{A}wedge overline{B}wedge overline{C}]
  3. Приравниваем результат к единице, т.е. проверяем, при каких условиях выражение будет истинным:

    [F=overline{A}wedge overline{B}wedge overline{C}=1.]

    Проанализируем полученный результат:

    Функция будет истиннои̌, если каждый множитель будет истинным, т.е. overline{A}=1 , overline{B}=1 , overline{C}=1 . Отсюда следует, что A=0 , B=0 , C=0 .

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

Пример 3

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

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

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

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

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

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

Решение:

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

G -- ʼʼСосуд греческийʼʼ;

F -- ʼʼСосуд финикийскийʼʼ;

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

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

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

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

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

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

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

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

[S_3overline{S_4}overline{S_5}vee overline{S_3}S_4overline{S_5}vee overline{S_3}overline{S_4}S_5=1,] [Foverline{G}vee overline{F}G=1.]

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

[left(Goverline{S_5}vee overline{G}S_5 ight)wedge left(Foverline{S_3}vee overline{F}S_3 ight)wedge left(overline{G}overline{S_4}vee GS_4 ight)wedge left(Foverline{G}vee overline{F}G ight)wedge ] [wedge left(S_3overline{S_4}overline{S_5}vee overline{S_3}S_4overline{S_5}vee overline{S_3}overline{S_4}S_5 ight)=]

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

[=left(Goverline{S_5}overline{G}overline{S_4}vee overline{G}S_5overline{G}overline{S_4}vee Goverline{S_5}GS_4vee overline{G}S_5GS_4 ight)wedge ] [wedge left(Foverline{S_3}Foverline{G}vee overline{F}S_3Foverline{G}vee Foverline{S_3}overline{F}Gvee overline{F}S_3overline{F}G ight)wedge left(S_3overline{S_4}overline{S_5}vee overline{S_3}S_4overline{S_5}vee overline{S_3}overline{S_4}S_5 ight)=]

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

[=left(overline{G}S_5overline{S_4}vee Goverline{S_5}S_4 ight)wedge left(Foverline{S_3}overline{G}vee overline{F}S_3G ight)wedge left(S_3overline{S_4}overline{S_5}vee overline{S_3}S_4overline{S_5}vee overline{S_3}overline{S_4}S_5 ight)=]

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

[=left(overline{G}S_5overline{S_4}overline{F}S_3Gvee Goverline{S_5}S_4overline{F}S_3Gvee overline{G}S_5overline{S_4}Foverline{S_3}overline{G}vee Goverline{S_5}S_4Foverline{S_3}overline{G} ight)wedge ] [wedge left(S_3overline{S_4}overline{S_5}vee overline{S_3}S_4overline{S_5}vee overline{S_3}overline{S_4}S_5 ight)=] [=left(Goverline{S_5}S_4overline{F}S_3vee overline{G}S_5overline{S_4}Foverline{S_3} ight)wedge left(S_3overline{S_4}overline{S_5}vee overline{S_3}S_4overline{S_5}vee overline{S_3}overline{S_4}S_5 ight)=] [=left(Goverline{S_5}S_4overline{F}S_3vee overline{G}S_5overline{S_4}Foverline{S_3} ight)wedge left(S_3overline{S_4}overline{S_5}vee overline{S_3}S_4overline{S_5}vee overline{S_3}overline{S_4}S_5 ight)=overline{G}S_5overline{S_4}Foverline{S_3};]

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

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

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


Применение инструмента алгебры логики при решении логических задач - понятие и виды. Классификация и особенности категории "Применение инструмента алгебры логики при решении логических задач"2018-2019.



Читайте также


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

    Решение логических задач с помощью алгебры логики является мощным средством. Алгоритм решения логических задач с помощью алгебры логики изучение условия; выделение простых высказываний, которым даются имена; запись условия задачи языком алгебры логики; составление... [читать далее].