Упражнения. Рассмотрим формулу х¹у É (Q(у,х) Ú Q(х,у))

Контрмодель

Модель

U = {Цезарь, Брут}.

|Q|_I = современник

Рассмотрим формулу х¹у É (Q(у,х) Ú Q(х,у)). При любом понимании х и у (а в этой интерпретации есть только два варианта: или Брут, или Цезарь), каждая из формул Q(у,х) и Q(х,у) истинна. Значит, при любой оценке х и у дизъюнкция истинна. В импликативной структуре А É В, если консеквент истинен, вся импликация истинна, независимо от значения антецедента. Значит формула х¹уÉ(Q(у,х)ÚQ(х,у)) истинна при любой подстановке вместо х и у. Значит, в этой интерпретации истинна формула

∀у∀x(х¹у É (Q(у,х) Ú Q(х,у))).

U = множество людей (когда-либо живших).

|Q|_I = современник

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

17. Определите значения формул со свободными переменными в данных интерпретациях при указанных функциях приписывания значений переменным.

Формулы сигнатуры S=(P², a)

I₁: U=N, N={0,1,2,…}

|P²|_I1= <

|a|_I1= 2

j₁(x)=0, j₁(y)=0, j₁(z)=5

j₂(x)=5, j₂(y)=0, j₂(z)=10

I₂: U=люди (когда-либо жившие)

|P²|_I2= современник

|a|_I2= М.Ю.Лермонтов

j₁(x)=Дж.Буш младший, j₁(y)=Дж.Буш старший, j₁(z)= Зенидин Зидан

j₂(x)=Вольфганг Амадей Моцарт, j₂(y)= Бенедикт Спиноза, j₂(z)=З. Зидан

(a) j₁[I₁](x=y⊃y=x)=…, j₂[I₁](x=y⊃y=x)=…

(b) j₁[I₂](x=y⊃y=x)=…, j₂[I₂](x=y⊃y=x)=…

(c) j₁[I₁](R(x,a))=…, j₂[I₁](R(x,a))=…

(d) j₁[I₂](R(x,a))=…, j₂[I₂](R(x,a))=…

(e) j₁ [I₁](R(a,a))=…, j₂[I₁] (R(a,a))=…

(f) j₁ [I₂](R(a,a))=…, j₂[I₂] (R(a,a))=…

(g) j₁[I₁](P(x,y)& P(z,x))=…, j₂ [I₁](P(x,y)& P(z,x))=…

(h) j₁[I₂](P(x,y)& P(z,x))=…, j₂ [I₂](P(x,y)& P(z,x))=…

(i) j₁[I₁](∀x(x≠y⊃P(x,y))=…, j₂[I₁](∀x(x≠y⊃P(x,y))=…

(j) j₁[I₂](∀x(x≠y⊃P(x,y))=…, j₂[I₂](∀x(x≠y⊃P(x,y))=…

18. Рассмотрим сигнатуру языка формальной арифметики Ω= (0, ', +, ·) с обычной интерпретацией символов (символ ' понимается как операция взятия следующегоэлемента натурального ряда или операция прибавления единицы). Скажите, какие отношения задают следующие формулы:

(а) $z x+z=y

(б) $z x+z'=y

(в) $z x×z=y.

19. Выразите в сигнатуре языка формальной арифметики Ω= (0, ', +, ·) следующие свойства:

а) x>0

б) x>y

в) x – чётное число

г) х – нечетное число

д) х – простое число

20. Показать, что следующие формулы логически недетерминированы (найдите для них модели и контрмодели):

1. P (b, а)

2. P (b, а) & P (a, b)

3. P (b, а) & ØP (a, b)

4. ØP (a, a)

5. ⁺ Q(a)&Q(c)& ØQ(b)

6. (Q(a)&Q(c))ÚQ(b)

7. ⁺ P (b, а) º P (a, b)

8. $x (P (x, а) & P (x, в))

9. ⁺ $x (S(x) & (ØP(а,x) Ú ØP (b,x)))

10. ⁺ "x "y (R(x, y) º R(y, x))

11. "x "y (R(x, y) É R(y, x))

12. "x (P(x) Ú Q(x)) É ("xP(x) Ú "xQ(x))

13. "x $y R (x, y) É $y "x R (x, y)

14. ($x P (x) & $xQ (x)) É $x (P (x) & Q (x))

15. $x (P (x,а) É Q (x,с))

16. "x (R(x, а) É Р(x))

17. "x $y R (x, y)

18. "x "y (х≠у É Р(х,у))

19. $х R (x) É "x R(x)

20. $x$y (х≠у & Р(х,у)&ØР(у,х))

21. Может ли предложение «"x (отличник(x) ≡ двоечник(x))» оказаться истинным для какого-то конкретного класса школьников? (Непейвода Н.Н. Прикладная логика).

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

1. P(a,b)&ØP(b,a)

2. $x(Q(x)&P(b,x))

3. "x(Q(x)ÉR(x))

23. Выполнимы ли следующие формулы (существует ли у каждой из ниже следующих формул модель):

1. "хР(х)

2. Р(с,а) & $xØ P(x, а)

3. $x"у(Р(х,х) & Ø Р(х,у))

24. Являются ли следующие формулы общезначимыми (законами логики), т.е. порождают ли данные структуры только истинные предложения?

1. $x,уР(х,у)

2. "x,y х≠у

3. "x R(x) É $х R (x)

4. $у R(у) É $х R (x)

5. $х(Р(х) É "у Р(у))

25. Сравните классы моделей формул $x(P(x)&Q(x)), $x(P(x)ÚQ(x)) и

$x (P (x) É Q (x)).

Тема 5: Логический статус формул в КЛП Отношение логического следования в КЛП

Основные понятия, которые необходимо усвоить: · логически выполнимая формула КЛП · логически общезначимая формула КЛП · логическое противоречие КЛП · отношение логического следования в КЛП  

Пояснения и определения – см. лекцию

Упражнения

26. Какие из следующих формул являются общезначимыми (логическими законами):

1. $x (P (x) É "y P (y))

2. "x (P (x) Ú Q (x)) ≡ ("x P (x) Ú "x Q (x))

3. "x (P (x) & Q (x)) ≡ ("x P (x) & "x Q (x))

4. $x (P (x) Ú Q (x)) ≡ ($x P (x) Ú $x Q (x))

5. $x (P (x) & Q (x)) ≡ ($x P (x) & $x Q (x))

6. R(a,c)&ØR(a,c)

7. R(a,c,a)ÚØR(a,c,a)

Дата добавления: 2014-12-27