05. Предикаты математической логики

Рассмотрим повествовательное предложение «Число X Меньше 3». Это предложение не является высказыванием. Если заменить в нём переменную X На конкретное число, то получим высказывание – истинное или ложное в зависимости от значения X.

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

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

Например, .

Областью определения D(P) предиката называется множество значений переменной , при которых предикат имеет смысл.

Например, запись Р(X), D(P) означает предикат одной переменной X, Определённый на множестве D(P).

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

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

1. Символическая запись означает высказывание «для всех » или «для каждого », истинное тогда и только тогда, когда предикат принимает истинное значение для Каждого элемента множества D(P).

Символ называется Квантором всеобщности, а переменная – Связанной этим квантором.

2. Символическая запись означает высказывание «существует , для которого » или «найдётся хотя бы одно , такое что», истинное тогда и только тогда, когда предикат принимает истинное значение Хотя бы для одного элемента множества D(P).

Символ называется Квантором существования, а переменная – Связанной этим квантором.

Символическая запись означает высказывание «существует единственный элемент , для которого », истинное тогда и только тогда, когда предикат принимает истинное значение Только для одного элемента множества D(P).

Например: высказывание «Произведение любых двух последовательных натуральных чисел кратно числу два» записывается в символьной форме с использованием квантора всеобщности так: (в математике запись «» означает, что число A делится на число B без остатка).

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

Например: если и – действительные числа, обозначает предикат , то высказывание читается так: для любого действительного числа существует единственное действительное число такое, что . Это истинное высказывание, так как для любого действительного числа существует единственное действительное число , при котором .

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

Теорема 1.4. При вынесении квантора из-под знака отрицания высказывания квантор изменяется на двойственный, а операция отрицания переходит на предикат:

и .

Пример. Найти множество истинности предиката , определенного на множестве действительных чисел.

Решение. По условию, . Для ответа на вопрос задачи нужно найти множество решений квадратного неравенства: . Значит, .□

Определение. Предикат называется Выполнимым на множестве, если он обращается в истинное высказывание Хотя бы при одном значении переменной.

Например, на множестве действительных чисел предикат является выполнимым.

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

Например, на множестве действительных чисел предикат является тождеством.

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

Например, на множестве действительных чисел предикат является невыполнимым.

Задачи и упражнения

1.16. Выберите среди следующих предложений предикаты.

1) Здравствуйте, Петя!

2) Число 5 является корнем уравнения .

3) .

4) Сколько граммов в одном килограмме?

5) X2 + y2.

6) .

7) Число 6 делится на 2 и на 3.

1.17. Запишите следующие высказывания в символьной форме с использованием предикатов и кванторов. Определите истинностные значения высказываний с кванторами:

1) любое натуральное число больше 3;

1.18

1.19. Выберите среди заданных высказываний правильную запись высказывания «Всякое действительное число не меньше самого себя»:

1) ;

2) ;

3) ;

4).

1.20. Укажите, какие из следующих предикатов выполнимы на множестве действительных чисел:

1) ;

2) ;

3) ;

4) .

1.21. Укажите, какие из следующих предикатов являются тождествами на множестве действительных чисел:

1) ;

2) ;

3) ;

4) .

1.22. Приведите примеры значений параметра , при которых каждый из заданных предикатов, определенных на множестве действительных чисел, является тождеством: