Контрольные вопросы и задания

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. x и y братья (т.е. имеют общих родителей).

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

8. Каждый ребёнок человека 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 – простое число.

6. Формулы алгебры предикатов

Математическая логика описывает общие методы умозаключений, применяемые к утверждениям, записанным в виде формул. Поэтому от символов предикатов фиксированной сигнатуры в формулах алгебры предикатов сигнатуры s перейдём к предикатным переменным. Например, формула

U = (1)

является формулой алгебры предикатов, в которой  произвольные предикаты арности 3 и 2 соответственно. Для определения же свойств таких формул рассматриваются формулы сигнатуры s, полученные замещением предикатных переменных на предикаты некоторой заданной сигнатуры s.

Задание 6.1. Является ли модель арифметики натуральных чисел _a = <  ; E⁽²⁾, S⁽³⁾, P⁽³⁾ >, где

допустимой для формулы (1)? Определить является ли формула (1) выполнимой на модели _a, просто выполнимой, тождественно истинной на модели _a, общезначимой?

Решение. Модель арифметики натуральных чисел является допустимой для формулы U, так как можно построить сигнатурное отображение множества предикатных переменных формулы в сигнатуру модели s = < E⁽²⁾, S⁽³⁾, P⁽³⁾ >. Вариантов такого отображения два:

1. , ;

2. , .

Проверим, является ли формула выполнимой на допустимой модели  . Рассмотрим формулу

₁U = ,

полученную подстановкой в формулу U предикатов сигнатурного отображения ₁. Легко проверить, что ₁U = 1 для любых значений , так как

 , является истинным утверждением.

Это означает, что формула U выполнима на модели _a и, более того, она истинна на этой модели. Выполнимость формулы следует из её выполнимости на модели _a.

Для проверки тождественной истинности формулы на модели нужно проверить истинность U при любом сигнатурном отображении. Аналогично предыдущему случаю получим, что формула ₂U = истинна на модели _a , а следовательно U тождественно истинна на этой модели.

Данная формула не является общезначимой, чтобы доказать это достаточно привести пример допустимой модели, на которой формула не будет тождественно истинной. В качестве такой модели возьмем ₃ = < ; G⁽²⁾, S⁽³⁾, P⁽³⁾>, где .

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

Задание 6.2. Доказать общезначимость формулы

.

Решение. Так как единственная переменная в обеих частях эквиваленции связана, то обе они являются высказываниями. Поэтому для доказательства общезначимости формулы, покажем, что истинностные значения левой и правой части совпадают для любых одноместных предикатов , определённых на произвольном множестве M.

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

Задание 6.3. Построить ПН-форму для формулы

Решение. Воспользовавшись общезначимостью из предыдущего задания, получим



 .

В первом дизъюнкте переменные x и y – связанные, а z – свободная, а во втором – наоборот. Переобозначив связанные переменные 

 ,

получим, что первый дизъюнкт не зависит от w, а второй – от u и v. Поэтому, вынеся соответствующие им кванторы в начало формулы 

 получим её ПН-форму.