5.8Основные понятия логики предикатов

Предикат – функция от произвольных переменных, принимающая значение «истина» или «ложь» в зависимости от значений этих переменных.

Примеры предикатов: «x – четное число», «число Х делится на число y без остатка», «город x - столица страны y», «человек по фамилии x закончил школу номер y в году Z».

Подстановка конкретных значений переменных в предикат превращает его в высказывание (истинное или ложное). В зависимости от количества переменных предикаты могут быть одноместными, двухместными и т.д. В примере, приведенном выше, первый предикат – одноместный, второй и третий - двухместные, четвертый – трехместный.

Если множество значений, которые могут принимать переменные предиката, конечно, то предикат можно задать таблично.

Пример 5.8 – Дан предикат P(x): «x – четное число». Переменная x принимает значения из множества M = {3, 5, 6, 7, 8}. Задать предикат P(x) таблично.

Предикат задан в таблице 5.8.

Таблица 5.8 – Пример задания одноместного предиката

x	3	5	6	7	8
P(x)	Л	Л	И	Л	И

Пример 5.9 – Дан предикат P(x, y): «x – валюта страны y». Переменная x принимает значения из множества M = {евро, иена, юань, рупия}, а y – на множестве N = {Германия, Франция, Индия, Китай, Япония}. Задать предикат P(x, y) таблично.

Предикат задан в таблице 5.9.

Таблица 5.9 – Пример задания двухместного предиката

x	y
	Германия	Франция	Индия	Китай	Япония
евро	И	И	Л	Л	Л
иена	Л	Л	Л	Л	И
юань	Л	Л	Л	И	Л
рупия	Л	Л	И	Л	Л

5.9 Операции над предикатами

Так как при подстановке конкретных значений переменных предикат превращается в высказывание, для предикатов могут выполняться все операции, применяемые для высказываний.

Пример 5.10 – Даны предикаты P(x): «x - четное число», Q(x): «x делится на 3». Переменная x принимает значения из множества M = {5, 6, 8, 9, 11, 15}. Задать таблично предикаты ,P(x)  Q(x), P(x) & Q(x), P(x) ~ Q(x).

Операции, используемые в данном случае, рассмотрены в разделе 5. Следует обратить внимание, что, например, P(x)  Q(x) – это тоже предикат, причем одноместный, так как он содержит только одну переменную (x). Если, например, x=11, то предикат P(x)  Q(x) превращается в высказывание «11 – четное число или делится на 3», т.е. в ложное высказывание. Если, например, x=15, то получаем высказывание «15 – четное число или делится на 3», т.е. истинное высказывание. Аналогично рассматриваются предикаты ,P(x) & Q(x), P(x) ~ Q(x).

Таблица 5.10 – Примеры операций над предикатами (результат - одноместный предикат)

x	5	6	8	9	11	15
	И	Л	Л	И	И	И
P(x)  Q(x)	Л	И	И	И	Л	И
P(x) & Q(x)	Л	И	Л	Л	Л	Л
P(x) ~ Q(x)	И	И	Л	Л	И	Л

Пример 5.11 – Даны предикаты P(x): «x - четное число», Q(y): «y делится на 3». Переменные x и y принимают значения из множества M = {5, 6, 8, 9, 11, 15}. Задать таблично предикаты P(x)  Q(y) и P(x) & Q(y).

Здесь предикаты P(x)  Q(y) и P(x) & Q(y) – двухместные, так как в них имеются две переменные (x и y). Предикат P(x)  Q(y) задан таблицей 5.11, а предикат P(x) & Q(y) – таблицей 5.12.

Таблица 5.11 – Пример дизъюнкции предикатов (результат – двухместный предикат)

x	y
	5	6	8	9	11	15
5	Л	И	Л	И	Л	И
6	И	И	И	И	И	И
8	И	И	И	И	И	И
9	Л	И	Л	И	Л	И
11	Л	И	Л	И	Л	И
15	Л	И	Л	И	Л	И

Здесь, например, при x=5, y=6 предикат P(x)  Q(y) превращается в истинное высказывание: «5 – четное число, или 6 делится на 3». При x=5, y=8 предикат P(x)  Q(y) превращается в ложное высказывание: «5 – четное число, или 8 делится на 3».

Таблица 5.12 – Пример конъюнкции предикатов (результат – двухместный предикат)

x	y
	5	6	8	9	11	15
5	Л	Л	Л	Л	Л	Л
6	Л	И	Л	И	Л	И
8	Л	И	Л	И	Л	И
9	Л	Л	Л	Л	Л	Л
11	Л	Л	Л	Л	Л	Л
15	Л	Л	Л	Л	Л	Л

Здесь, например, при x=6, y=11 получаем ложное высказывание: «6 – четное число, и 11 делится на 3». При x=6, y=15 получаем истинное высказывание: «6 – четное число, и 15 делится на 3».