Формулы алгебры предикатов сигнатуры s
Напомним, что строго предикат можно определить как отображение n -ной степени предметного множества M, называемой местностью или арностью предиката в двухэлементное множество B = {1, 0}
Например, предикат простого числа Для предикатов кроме логических операций алгебры высказываний вводятся операции утверждения общности и утверждения существования, называемые операциями связывания предметных переменных. С помощью этих операций из предикатов строятся формулы алгебры предикатов. Например, для предиката делимости D(x,y): ² x нацело делится на y ², определённого на множестве натуральных чисел N, можно построить формулы алгебры предикатов, являющиеся высказываниями, так как обе предметные переменные в них связаны. 1) Высказывание 2) Высказывание 3) Высказывание 4) Высказывание Ряд важнейших понятий алгебры предикатов основывается на понятии модели.
Моделью M называется любое множество M с заданными на нем предикатами M = < M; а набор s = < Любое утверждение в некоторой предметной области можно записать в виде формулы алгебры предикатов сигнатуры s, выбрав соответствующее предметное множество и набор предикатов, определённых на нём, называемый сигнатурой модели. В качестве примера рассмотрим теоремы и определения из евклидовой геометрии. Предметным множеством M здесь является множество точек, прямых и плоскостей трёхмерного пространства. Задание 5.1. Записать в виде формулы на модели M g= < M;
следующие утверждения: a) Через каждые 2 точки можно провести прямую. b) Если 2 точки различны, то проходящая через них прямая единственна. c) Через каждые 3 точки, не лежащие на одной прямой, можно провести единственную плоскость. d) Определение параллельных прямых на плоскости. Решение. a) Данное утверждение можно сформулировать с использованием предикатов модели следующим образом: для произвольных двух точек существует прямая, на которой лежат эти точки. Запишем его в виде формулы b) В дополнении к предыдущему утверждению здесь говорится, что если произвольные точки не совпадают, то построенная по ним прямая является единственной, т.е. любая другая прямая, проходящая через эти точки, совпадает с ней. Таким образом, получим формулу c) Данное утверждение гласит, что если 3 точки не лежат на одной прямой, то существует плоскость, на которой лежат эти точки, причём любая другая такая плоскость совпадает с ней. Введём для краткости записи итоговой формулы вспомогательные формульные предикаты:
Запишем с их помощью утверждение задания
d) Напомним, что параллельными называются те прямые, которые лежат на одной плоскости и не имеют общих точек, либо совпадают, т.е.
Заметим, что в предыдущих формулах все переменные – связанные, т.е. формулы являются высказываниями, принимающими значение 1. Данная формула является формульным предикатом от переменных Контрольные вопросы и задания 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) x и y братья (т.е. имеют общих родителей). g) Все дети человека x состоят в браке. h) Каждый ребёнок человека y состоит в браке с ребёнком человека x. 2. В модели с одним двуместным предикатом a) предикат R рефлексивен; b) предикат R симметричен; c) предикат R транзитивен; d) предикат R является отношением эквивалентности. 3. Определить являются ли следующие формулы на модели M 1 = < N; D (2), S (3), P (3)>, где D(x,y): “ x нацело делится на y ”, выполнимыми, истинными, ложными на модели? a) b) c) d) e) f) 4. Построить на модели M 2 = < N; S (3), P (3)> формулу, принимающую значение истина тогда и только тогда, когда: a) x = 0; b) x = 1; c) x = 2; d) x – чётно; e) x – нечётно; f) x – простое число.
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|