Лабораторная работа № 6

Проверил Мартемьянов Б.В.

Выполнил студент группы к4136(ИТМО) Куленко Е.А.

Самара 2015

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

Краткая теория:

Формулы F(X₁,X₂…,Xn) и H(X₁,X₂…,Xn) алгебры высказываний называются равносильными (эквивалентными), если при любых значениях входящих в них пропозициональных переменных логические значения получающихся из формул F и H высказываний совпадают.

Для указания равносильности формул используют обозначение F ≡ H. Определение равносильности формул можно записать символически для любых конкретных высказываний A₁, A₂, …, An:

F ≡ H ↔ λ(F(A₁,A₂…,An)) = λ(H(A₁,A₂…,An))

Не следует думать, что в обе формулы F и H непременно входят одни и те же переменные. Некоторые из переменных X₁, X₂, …, Xn могут фактически отсутствовать в любой из них.

Две формулы F и H алгебры высказываний равносильны тогда и только тогда, когда формула F ↔ H является тавтологией:

F ≡ H ↔ ╞ F ↔ H

Отношение равносильности между формулами алгебры высказываний:

а) рефлексивно: F ≡ F;

б) симметрично: если F₁≡ F₂, то F₂≡ F₁;

в) транзитивно: если F₁≡ F₂ и F₂≡ F₃, то F₁≡ F₃, т.е. отношение равносильности является отношением эквивалентности.

Справедливы следующие равносильности

Задание:

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

Приведем выражения к виду, принимаемому программой:

!((a||!(!b||c&&k))&&!(!a||b&&!c&&k||c&&!k)) и!a||b&&!c&&k||c&&!k

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

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

Приведем выражения к виду, принимаемому программой:

(a->(b->c))->((a->b)->(a->c)) и!b||!a||1

Так как высказывание истинно, то оно истинно при любых комбинациях операнд.

Задача типа 3. Решить заданную логическую задачу. Продумать и реализовать способ подтвердить полученное решение средствами программы, разработанной на предыдущей лабораторной работе.

В санатории на берегу моря отдыхают отец (O), мать (M), сын (C) и две дочери (D1 и D2). До завтрака члены семьи часто купаются в море. Известно, что если отец утром купается, то с ним обязательно идут мать и сын; если сын идет купаться, то с ним идет сестра D1; вторая дочь купается тогда и только тогда, когда купается мать, и каждое утро купается по крайней мере один из родителей. Если в воскресенье утром купалась в море лишь одна из дочерей, то кто из членов семьи в это утро ходил на море?

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

Логически перемножим все полученные равенства, выбрав следующий порядок действий:

[1] [2] [3] [4] [5]

(OMC˅O̅)(CD₁˅C̅)(MD₂˅M̅D̅₂)(O˅M)(D₁D̅₂˅D̅₁D₂)=1

Перемножим равенства [1] и [4]:

(OMC˅O̅O˅O̅M)(CD₁˅C̅)(MD₂˅M̅D̅₂)(D₁D̅₂˅D̅₁D₂)= (OMC˅O̅M)(CD₁˅C̅)(MD₂˅M̅D̅₂)(D₁D̅₂˅D̅₁D₂)=1 Получившееся выражение перемножим с [3] равенством:

(OMCD₂˅O̅MD₂˅OMCM̅D̅₂˅O̅MM̅D̅₂)(CD₁˅C̅)(D₁D̅₂˅D̅₁D₂)=(OMCD₂˅O̅MD₂) (CD₁˅C̅)(D₁D̅₂˅D̅₁D₂)=1 Получившееся выражение перемножим с равенством [5]:

(OMCD₂D₁D̅₂˅OMCD₂D̅₁˅O̅MD₂D₁D̅₂˅O̅MD₂D̅₁)(CD₁˅C̅)=(OMCD₂D̅₁˅O̅MD₂D̅₁)(CD₁˅C̅)=1

Получившееся выражение перемножим с равенством [2]:

OMCD₂D̅₁D₁˅OMCD₂D̅₁C̅˅O̅MD₂D̅₁CD₁˅O̅MD₂D̅₁C̅ = O̅MD₂D̅₁C̅ =1

Следовательно, в воскресенье купались мать и вторая дочь.

Приведем выражения к виду, принимаемому программой:

(o&&m&&c||!o)&&(c&&d1||!c)&&(m&&d2||!m&&!d2)&&(o||m)&&(d1&&!d2||!d1&&d2) и!o&&d&&d2&&!d1&&!c

Из результат работы программы видно, что выражения истинны лишь в одном случае, когда истинны M и D2.