§3. Предикаты. Кванторы общности и существования п.1. Определение предиката.

Рассмотрим несколько предложений с переменной:

- « - простое натуральное число»;

- « - чётное целое число»;

- « - равносторонний»;

- « »

- «студент получил оценку »

- « делиться нацело на 3»

Если в перечисленных предложениях вместо и подставить обозначаемые ими предметы, то эти предложения превра­тятся в высказывания. Те предметы, которые обозначают , и т.д. на­зываются допустимыми значениями переменных.

Например, область допустимых значений предложения - множе­ство всех натуральных чисел.

множество треугольников плоскости

множеству студентов

Определение. Если предложение с переменными при любой за­мене переменных допустимыми значениями превращается в высказы­вание, то такое предложение называется предикатом.

, , - предикаты от одной переменной (одноместные пре­дикаты). Предикаты от двух переменных: , , - двухместные предикаты. Высказывания – нульместные предикаты.

П.2. Логические операции алгебры предикатов.

Пусть и - два предиката с одинаковыми областями до­пустимых значений переменных.

Рассмотрим предложение: . если вместо x подставим любое допустимое значение, то получим высказывание. Следовательно, - предикат с той же областью допустимых значений, что и . Аналогично: , , , - предикаты.

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

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

- предикат. ( - простое число и делится нацело на 3)

- предикат.

- предикат.

- предикат.

- предикат.

П.3.Равносильность предикатов.

Определение. Предикаты и называются равносильными, если они имеют одинаковые области допустимых зна­чений и при замене переменных одинаковыми допустимыми значе­ниями логические значения полученных высказываний совпадают. Пи­шут: .

П.4. Квантор общности.

Определение. Символ называется квантором общности.

Читается: для любого , для каждого , для всех .

Пусть - одноместный предикат.

читается: для любых - истина.

Определение. Предложение обозначает высказывание, которое истинно, если принимает значение «истина» для всех до­пустимых значений переменных, в противном случае высказывание ложно.

Пример. - «Все натуральные числа простые» - Лож­ное высказывание.

- «Все целые числа чётные» - Ложное высказывание.

- «Все студенты получили оценку » - одноместный преди­кат. Навесили квантор на двуместный предикат, получили одномест­ный предикат. Аналогично - n-местный предикат, то - (n-1)-местный предикат. - (n-2)-местный пре­дикат.

В русском языке квантор общности опускается.

П.5. Квантор существования.

Определение. называется квантором существования.

читается: существует , есть , найдётся .

Выражение , где - одноместный предикат, чита­ется: существует , для которого истинно.

Определение. Пусть - одноместный предикат, под выраже­нием будем понимать высказывание, которое истинно, если хотя бы при одном допустимом значении превращается в истинное высказывание и ложно во всех остальных случаях.

Пример. - «существуют простые числа».

- «существуют чётные числа».

- «существует студент , который получил оценку » - од­номестный предикат.

Если на n-местный предикат навесить 1 квантор, то получим (n-1)-ме­стный предикат, если навесить n кванторов, то получим нульместный предикат, т.е. высказывание.

Если навешивать кванторы одного вида, то порядок навешива­ния кванторов безразличен. А если на предикат навешиваются разные кванторы, то порядок навешивания кванторов менять нельзя.

.