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

Напомним, что строго предикат можно определить как отображение n -ной степени предметного множества M, называемой местностью или арностью предиката в двухэлементное множество B = {1, 0}

.

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

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

Например, для предиката делимости D(x,y): “ x нацело делится на y ”, определённого на множестве натуральных чисел ô, можно построить формулы алгебры предикатов, являющиеся высказываниями, так как обе предметные переменные в них связаны.

1) Высказывание читается, как “для любого x существует y, такое, что x делится на y ”, и является истинным высказыванием, так как любое натуральное x делится на себя и на 1, т.е. y = x или y =1;

2) Высказывание читается, как “существует y, на который делится любой x ”, и является истинным высказыванием, так как на значение y =1 делится любое натуральное x;

3) Высказывание читается, как “существует x, который делится на любое y ”, и является ложным высказыванием, так как нет ни одного натурального числа, которое делится на любое натуральное число;

4) Высказывание читается, как “для любого y существует такой x, что x делится на y ”, и является истинным высказыванием, так как для любого натурального y можно указать множество значений ô, которые делятся на y.

Ряд важнейших понятий алгебры предикатов основывается на понятии модели.

Моделью M называется любое множество M с заданными на нем предикатами :

M = < M; >.

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

Задание. Записать в виде формулы на модели M = < M; >, где

, ,

, ,

,

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

a) Через каждые 2 точки можно провести прямую.

b) Если 2 точки различны, то проходящая через них прямая единственна.

c) Через каждые 3 точки, не лежащие на одной прямой, можно провести единственную плоскость.

d) Определение параллельных прямых на плоскости.

Решение.

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

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

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

: “ x, y, z не лежат на одной прямой“;

: “ x, y, z лежат на плоскости v “.

Запишем с их помощью утверждение задания

.

d) Напомним, что параллельными называются те прямые, которые лежат на одной плоскости и не имеют общих точек, либо совпадают, т.е.

.

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

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

U = (*)

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

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

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

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

1) , ;

2) , .

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

s₁ U = ,

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

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

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

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

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

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

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

.

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

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

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

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

º

º .

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

º ,

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

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

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

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

M _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 ”,

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

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

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

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

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

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

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

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

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

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

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

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

a) предикат R рефлексивен;

b) предикат R симметричен;

c) предикат R транзитивен;

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

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

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

a)

b)

c)

d)

e)

f)

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

a) x = 0;

b) x = 1;

c) x = 2;

d) x – чётно;

e) x – нечётно;

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

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

x	Q	R
a b

 

 

x	y	P	S
a a b b	a b a b

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

a)

b)

c)

d)

e)

f)

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

a) ;

b) ;

c) .