Файл: Интеллектуальные информационные системы. Решение.docx

ВУЗ: Не указан

Категория: Решение задач

Дисциплина: Логика

Добавлен: 18.10.2018

Просмотров: 2327

Скачиваний: 25

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Задание 6

1.Пусть S(x) означает «число х – делится нацело на 3»

Что означают утверждения:

S(7)

S(12)

∀xS(x)

2.Какие из них истинны, какие нет?

S(7) – ЛОЖЬ (7 не делится нацело на 3)

S(12) – ИСТИНА (12 делится нацело на 3)

∀xS(x) – ЛОЖЬ (каждый х не делится нацело на 3)

3. Введен предикат L(x,y) «х любит y -ка»

Как записать утверждения:

«Марго не любит Ваню»: ¬L(Марго,Ваня)

«Каждый любит кого-нибудь»: x y:L(x,y)

«Кто-то не любит никого»: х ∃!y: ¬L(x,y)





Задание 7

Формализовать рассуждение на языке ИП: ввести необходимые предикаты, переменные, константы. С их помощью записать в виде формул посылки и заключение.

Ни один республиканец или демократ не является социалистом. Джон-социалист. Следовательно, Джон не республиканец.

Введем предикаты:

R(x) – быть республиканцем

D(x) – быть демократом

S(x) – быть социалистом


Посылка1: x((R(x)D(x))→¬S(x))

Посылка2: S(Джон)=И

Заключение:

¬R(Джон)





Задание 8


Доказать справедливость рассуждения на языке ИП. Построить множество дизъюнктов для рассуждения. Для этого привести посылки и отрицание заключения к ПНФ, а затем к Сколемовской стандартной форме.

Использовать формализацию из задания № 7

Ни один республиканец или демократ не является социалистом. Джон- социалист. Следовательно, Джон не республиканец.

Докажем рассуждение «от противного», построив логическое произведение посылок и отрицания заключения.

Посылка1: x((R(x)D(x))→¬S(x))=x(¬(R(x)D(x)) ¬S(x)) Формула преобразована к ПНФ

Посылка2: S(Джон) Формула преобразована к ПНФ

Заключение:

¬R(Джон) формула преобразована в ПНФ

Преобразование Сколема и получение множества дизъюнктов

Посылка1: ПНФ: x(¬(R(x)D(x)) ¬S(x)) =

x((¬R(x) & ¬D(x)) ¬S(x)) = x( (¬R(x) ¬S(x))& (¬ D(x) ¬S(x))

Получаем 2 дизъюнкта: ¬R(x)¬S(x) и ¬ D(x) ¬S(x)

Посылка2: S(Джон) - единственный дизъюнкт

Отрицание заключения:

¬(¬R(Джон))= R(Джон) - единственный дизъюнкт


По теореме о логическом следствии построим произведение:

(Посылка 1)&(Посылка 2)&¬ (Заключение)

R(x)¬S(x))&(¬ D(x) ¬S(x))& S(Джон)& R(Джон)

Поскольку Посылка 1 верна для всех х, то она будет верна и для x=Джон.

Тогда:

R(Джон)¬S(Джон))&(¬ D(Джон) ¬S(Джон))& S(Джон)& R(Джон)=

=(R(Джон)& ¬R(Джон) R(Джон)& ¬S(Джон))& (S(Джон)& ¬D(Джон) S(Джон)& ¬S(Джон))

Выделенные цветом произведения обращаются в ноль (Ложь), тогда остается произведение:

R(Джон)& ¬S(Джон))& S(Джон)& ¬D(Джон)

В нем выделенные члены также обращаются в ноль (Ложь), соответственно и все произведение обращается в ноль (Ложь), а это значит, что исходное рассуждение верно.






Задание 9

Доказать справедливость рассуждения (взять свой вариант из задания на исчисление высказываний) методом резолюции.

Или Валя и Борис одного возраста, или Валя старше Бориса. Если Валя и Борис одного возраста, то Наташа и Борис не одного возраста. Если Валя старше Бориса, то Борис старше Сергея. Следовательно, или Наташа и Борис не одного возраста, или Борис старше Сергея.

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

A – Валя и Борис одного возраста

B – Валя старше Бориса

C–Наташа и Борис одного возраста

D – Борис старше Сергея

Формализация рассуждения:

AB, A→¬C, B→D├ ¬CD

Доказательство методом резолюции выполняется только «от противного»: К произведению всех посылок добавляем отрицание заключения:

(AB)&(A→¬C)&(B→D)&¬ (¬CD)

Приводим к КНФ:

(AB)&(¬A¬C)&( ¬BD)&¬(¬CD)=

=(AB)&(¬A¬C)&( ¬BD)&C&¬D

Строим S – множество дизъюнктов, входящих в КНФ:

D1=(AB)

D2=(¬A¬C)

D3=( ¬BD)

D4=C

D5=¬D

Для доказательства противоречивости S нужно убедиться в том, что множество дизъюнктов S содержит пустой (ложный) дизъюнкт

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

D1=(AB)

D2=(¬A¬C)

D3=( ¬BD)

D4=C

D5=¬D

------------------

D7: ¬A (Резольвента D2, D4)

D8: B (Резольвента D1, D7)

D9: D (Резольвента D3, D8)

D10:  (Резольвента D5, D9)

Итак, мы вывели пустой дизъюнкт и доказали противоречивость множества S.




Задание 10

Построить множество дизъюнктов для рассуждения. Для этого привести посылки и отрицание заключения к ПНФ, а затем к Сколемовской стандартной форме. Методом резолюции вывести пустой (тождественно ложный) дизъюнкт из исходного множества дизъюнктов, доказав тем самым справедливость рассуждения.

Ни один республиканец или демократ не является социалистом. Джон- социалист. Следовательно, Джон не республиканец.

В ходе решения задачи 8 были получены следующие дизъюнкты:

Посылка 1: Получаем 2 дизъюнкта: ¬R(x)¬S(x) и ¬ D(x) ¬S(x)

Посылка2: S(Джон) - единственный дизъюнкт

Заключение:

ПНФ: ¬R(Джон) - единственный дизъюнкт


D1: ¬R(x)¬S(x)

D2: ¬ D(x) ¬S(x)

D3: S(Джон)

D4: R(Джон))

-------------------------------

D5: ¬R(Джон) (резольвента D1 и D3, чтобы её получить была применена подстановка x=Джон)

D6: (резольвента D4 и D5)

Получен пустой дизъюнкт