Упражнения

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

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

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

|P²|_I1= 

|a|_I1= 2

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

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

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

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

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

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

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

1. ₁[I₁](x=y⊃y=x)=…, ₂[I₁](x=y⊃y=x)=…

2. ₁[I₂](x=y⊃y=x)=…, ₂[I₂](x=y⊃y=x)=…

3. ₁[I₁](R(x,a))=…, ₂[I₁](R(x,a))=…

4. ₁[I₂](R(x,a))=…, ₂[I₂](R(x,a))=…

5. ₁ [I₁](R(a,a))=… , ₂[I₁] (R(a,a))=…

6. ₁ [I₂](R(a,a))=… , ₂[I₂] (R(a,a))=…

7. ₁[I₁](P(x,y)& ¬P(z,x))=…, ₂ [I₁](P(x,y)& ¬P(z,x))=…

8. ₁[I₂](P(x,y)& ¬P(z,x))=…, ₂ [I₂](P(x,y)& ¬P(z,x))=…

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

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

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

(а) zx+z=y

(б) z x+z'=y

(в) z xz=y.

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

1. x>0

1. x>y

2. x– чётное число

3. х – нечетное число

4. х – простое число

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: Логический статус формул в клп Отношение логического следования в клп

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

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