Главная | Обратная связь
МегаЛекции

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





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

.

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

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

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

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 можно указать множество значений N, которые делятся на y.

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

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

M = < M ; >,

а набор s = < > называется сигнатурой модели M.

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



Задание 5.1. Записать в виде формулы на модели

Mg= < M ; > , где

, ,

, ,

,

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

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

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

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

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

Решение.

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

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

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

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

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

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

.

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. Определить являются ли следующие формулы на модели M1 = < N ; D(2), S(3), P(3)>, где D(x,y): “x нацело делится на y”,

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

a)

b)

c)

d)

e)

f)

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


a) x = 0;

b) x = 1;

c) x = 2;

d) x – чётно;

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

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





Рекомендуемые страницы:

Воспользуйтесь поиском по сайту:
©2015- 2021 megalektsii.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.