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

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

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

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

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

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

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

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

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

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

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

Моделью M называется любое множество M с заданными на нем предикатами Формулы алгебры предикатов - student2.ru :

M = < M ; Формулы алгебры предикатов - student2.ru >.

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

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

Формулы алгебры предикатов - student2.ru Формулы алгебры предикатов - student2.ru , Формулы алгебры предикатов - student2.ru Формулы алгебры предикатов - student2.ru ,

Формулы алгебры предикатов - student2.ru Формулы алгебры предикатов - student2.ru , Формулы алгебры предикатов - student2.ru Формулы алгебры предикатов - student2.ru ,

Формулы алгебры предикатов - student2.ru Формулы алгебры предикатов - student2.ru ,

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

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

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

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

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

Решение.

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

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

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

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

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

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

Формулы алгебры предикатов - student2.ru : “x, y, z не лежат на одной прямой“;

Формулы алгебры предикатов - student2.ru : “ x, y, z лежат на плоскости v“.

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

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

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

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

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

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

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

U= Формулы алгебры предикатов - student2.ru (*)

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

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

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

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

Решение. Модель арифметики натуральных чисел является допустимой для формулы U, так как можно построить сигнатурное отображение Формулы алгебры предикатов - student2.ru множества предикатных переменных формулы Формулы алгебры предикатов - student2.ru в сигнатуру модели z = < E(2), S(3), P(3)>. Вариантов такого отображения два:

1) Формулы алгебры предикатов - student2.ru , Формулы алгебры предикатов - student2.ru ;

2) Формулы алгебры предикатов - student2.ru , Формулы алгебры предикатов - student2.ru .

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

s1U= Формулы алгебры предикатов - student2.ru ,

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

Формулы алгебры предикатов - student2.ru Þ Формулы алгебры предикатов - student2.ru , является истинным утверждением.

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

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

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

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

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

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

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

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

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

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

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

Формулы алгебры предикатов - student2.ru º

º Формулы алгебры предикатов - student2.ru .

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

º Формулы алгебры предикатов - student2.ru ,

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

º Формулы алгебры предикатов - student2.ru получим её ПН-форму.

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

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

M P = <P; M(1), W(1), C(2), Y(2), G(2)>, где

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. В модели с одним двуместным предикатом Формулы алгебры предикатов - student2.ru записать утверждения:

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

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

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

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

3. Определить являются ли следующие формулы на модели N 1 = < ô ; D(2), S(3), P(3)>, где D(x,y): “x нацело делится на y”, Формулы алгебры предикатов - student2.ru Формулы алгебры предикатов - student2.ru

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

a) Формулы алгебры предикатов - student2.ru

b) Формулы алгебры предикатов - student2.ru

c) Формулы алгебры предикатов - student2.ru

d) Формулы алгебры предикатов - student2.ru

e) Формулы алгебры предикатов - student2.ru

f) Формулы алгебры предикатов - student2.ru

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

a) x = 0;

b) x = 1;

c) x = 2;

d) x – чётно;

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

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

5. Является ли модель M = <M; T(0), Q(1), R(1), P(2), S(2)> допустимой для формулы U= Формулы алгебры предикатов - student2.ru . Определить является ли формула выполнимой на модели, просто выполнимой, тождественно истинной на модели, общезначимой, если M={a, b}, T(0) =1, а остальные предикаты заданы таблицами?

x Q R
a b
x y P S
a a b b a b a b

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

a) Формулы алгебры предикатов - student2.ru

b) Формулы алгебры предикатов - student2.ru

c) Формулы алгебры предикатов - student2.ru

d) Формулы алгебры предикатов - student2.ru

e) Формулы алгебры предикатов - student2.ru

f) Формулы алгебры предикатов - student2.ru

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

a) Формулы алгебры предикатов - student2.ru ;

b) Формулы алгебры предикатов - student2.ru ;

c) Формулы алгебры предикатов - student2.ru .

Наши рекомендации