Варианты заданий

1. Представить формулой на модели

 _P = <P; M⁽¹⁾, W⁽¹⁾, C⁽²⁾, Y⁽²⁾, G⁽²⁾>, где

M(x): ”x – мужчина”,

W(x): ”x – женщина”,

C(x, y): ”x ребёнок y”,

Y(x, y): ”x моложе, чем y”,

G(x, y): ”x состоит в браке с y”,

следующие утверждения:

1. Каждый человек имеет отца и мать.

2. Каждый, кто имеет отца, имеет и мать.

3. Каждый человек моложе своих родителей.

4. Каждый человек моложе родителей своих родителей.

5. Человек x состоит в браке.

6. Существует мужчина, жена сына которого старше его самого.

7. x и y братья (т.е. имеют общих родителей).

8. Все дети человека x состоят в браке.

9. Каждый ребёнок человека y состоит в браке с ребёнком человека x.

10. У человека y есть ребёнок, который не состоит в браке с ребёнком человека x.

2. В модели с одним двуместным предикатом записать утверждения:

1. предикат R рефлексивен;

2. предикат R симметричен;

3. предикат R транзитивен;

4. предикат R является отношением эквивалентности.

3. Определить являются ли следующие формулы на модели  ₁ = <  ; D⁽²⁾, S⁽³⁾, P⁽³⁾>, где D(x,y): “x нацело делится на y”,

выполнимыми, истинными, ложными на модели?

1. 

2. 

3. 

4. 

5. 

6. 

4. Построить на модели  ₂ = <  ; S⁽³⁾, P⁽³⁾> формулу, принимающую значение истина тогда и только тогда, когда:

1. x = 0;

2. x = 1;

3. x = 2;

4. x – чётно;

5. x – нечётно;

6. x – простое число.

5. Является ли модель  = <M; T⁽⁰⁾, Q⁽¹⁾, R⁽¹⁾, P⁽²⁾, S⁽²⁾> допустимой для формулы U =. Определить является ли формула выполнимой на модели, просто выполнимой, тождественно истинной на модели, общезначимой, еслиM={a, b}, T⁽⁰⁾ =1, а остальные предикаты заданы таблицами?

x	Q	R
a b	1 0	0 1

x	y	P	S
a a b b	a b a b	0 1 1 1	1 0 0 0

6. Доказать общезначимость формул:

1. 

2. 

3. 

4. 

5. 

6. 

7. Построить ПН-форму для формул:

1. ;

2. ;

3. .