Вычисление пределов
Криволинейный интеграл
Карта сайта

Дискретная математика Исчисление предикатов

 

 Определение. Предикатом  P(x1, x2, …, xn) называется функция, переменные которой принимают значения из некоторого множества М, а сама функция принимает два значения: И (истина) и Л (ложь), т.е.

 

 Предикат от п аргументов называется п – местным предикатом. Высказывания считаются нуль – местными предикатами.

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

 

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

 Кванторы бывают двух видов:

 

 1) Квантор общности. Обозначается ("х)Р(х). Квантором общности называется высказывание истинное, когда Р(х) истинно для каждого элемента х из множества М, и ложное – в противном случае.

 2) Квантор существования. Обозначается ($х)Р(х). Квантором существования называется высказывание, истинное, когда существует элемент из множества М, для которого Р(х) истинно, и ложное в противном случае.

 Операцию связывания квантором можно применять и к предикатам от большего числа переменных.

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

 1) Перенос квантора через отрицание.

Ø("x)A(x) º ($x)ØA(x); Ø($x)A(x) º ("x)ØA(x);

 

2)      Вынесение квантора за скобки.

 

($х)(А(х) & B) º ($x)A(x) & B; ("x)(A(x) & B) º ("x)A(x) & B;

 

($х)(А(х) Ú B) º ($x)A(x) Ú B; ("x)(A(x) Ú B) º ("x)A(x) Ú B;

 

 3) Перестановка одноименных кванторов.

  [an error occurred while processing this directive]

("y)("x)A(x,y) º ("x)("y)A(x,y); ($y)($x)A(x,y) º ($x)($y)A(x,y);

 

 4) Переименование связанных переменных. Если заменить связанную переменную формулы А другой переменной, не входящей в эту формулу, в кванторе и всюду в области действия квантора получаем формулу, равносильную А.

 

 Исчисление предикатов базируется на приведенных выше свойствах и правилах, называемых аксиомами.

 

 Какими бы ни были формулы А и В для них справедливы следующие аксиомы:

 

 1) A Þ (B Þ A);

 

 2) (A Þ (B Þ C)) Þ ((A Þ B) Þ (A Þ C));

 

 3) (ØB Þ ØA) Þ ((ØB Þ A) Þ B);

 

 4) ("xi)A(xi) Þ A(xj), где формула А(хi) не содержит переменной xi.

 

 5) A(xi) Þ ($xj)A(xj), где формула А(хi) не содержит переменной xi.


На главную страницу сайта