Курс высшей математики Примеры решений и лекции Элементы комбинаторики Непрерывность функции Комплексные числа Дискретная математика Кривые второго порядка Линейная алгебра Элементы векторной алгебры

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

 

 Определение. Предикатом  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.


Математика примеры решения задач