Задание 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 – Борис старше Сергея

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

A∨B, A→¬C, B→D├ ¬C∨D

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

(A∨B)&(A→¬C)&(B→D)&¬ (¬C∨D)

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

(A∨B)&(¬A∨¬C)&( ¬B∨D)&¬(¬C∨D)=

=(A∨B)&(¬A∨¬C)&( ¬B∨D)&C&¬D

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

D1=(A∨B)

D2=(¬A∨¬C)

D3=( ¬B∨D)

D4=C

D5=¬D

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

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

D1=(A∨B)

D2=(¬A∨¬C)

D3=( ¬B∨D)

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)

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