Материал: 5540

которая типична для высказываний вида «Всякое то-то есть то-то». Это просто значит то же, что Q R .

Подобным образом предложение «Некоторые действительные числа являются рациональными» можно перевести в символическую форму следующим образом:

( x) (R(x) Q(x)),

которая типична для высказываний вида «Некоторые то-то суть то-то». Смысл этого предложения сводится просто к тому, что R Q – непустое множество.

Отрицание утверждения типа «для всех» есть утверждение типа «для некоторого», а отрицание утверждение «для некоторого» есть утверждение типа «для всех». Традиционная логика особое внимание обращала на

86

а) ( x)( y)( z) P(x, y, z);

б) ( x)( y) Q(x, y);

в) ( x)( a)( b) R(a, b, x);

г) a S (а, Тед.).

Задача 4.7. Какой из кванторов определяется следующими выражениями: «Для всякого х истинно F(x)»; «F(x) при произвольном х»; «Найдётся х, такой что F(x)»; «Для подходящего х верно F(x)»; «Всегда имеет место F(x)»; «Каждый элемент обладает свойством F»; «Найдётся, по крайней мере, один х такой, что F(x)»; «Существует не менее одного х, что F(x)»; «Свойство F присуще всем»; «каким бы ни был х, F(x) истинно»; «Хотя бы для одного х верно F(x)».

Задача 4.8. Пусть Р(x): «х – простое число», Е(x): «x – чётное число» и D(x): «у делится на х». Перевести на русский язык:

различные варианты квантификации его переменных. Определите истинность получаемых выражений.

Задача 4.10. Рассмотрите варианты навешивания кванторов на предикат Р(х, у), опишите в словесной форме полученные высказывания и определить их истинность, если:

1.Р(х, у), определённый на конечном множестве натуральных чисел, означает:

а) «х делит у» (или, что то же, «х является делителем у»); б) «х, у делятся на 3»;

в) «х ≥ у».

2.Р(х, у), определённый на множестве людей, означает:

а) «х является родителем у»; б) «х живёт в одном городе с у»; в) «х является сыном у».

Задача 4.11. Запишите приведённые ниже утверждения в

87

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

1.На каждой улице будет праздник.

2.Некоторые машины умнее людей.

3.Любой играет в теннис лучше Фреда.

4.Некоторые композиторы пишут симфонии лучше, чем другие.

5.Не существует совершенных героев.

6.Все студенты учатся усердно.

7.Некоторые целые числа делятся на 5.

4.3 Формулы логики предикатов. Выполнимость и истинность

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

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

В дальнейшем будем называть прописные буквы латинского алфавита F, G, H, P, Q, … – нульместными предикатными переменными; F(,…,), G(,…,), H(,…,), P(,…,), Q(,…,), с указанием числа свободных мест в них – n- местными (n ≥ 1) предикатными переменными. Тогда

1)каждая нульместная предикатная переменная есть формула;

2)если P(,…,) – n-местная предикатная переменная, то Р(х1, ..., хn) есть формула, в которой все предметные переменные х1, ..., хn свободны;

3)Если F – формула, то F – также формула. Свободные (связанные)

предметные переменные в формуле F те и только те, которые являются свободными (связанными) в F;

4)если F1, F2 – формулы и если предметные переменные, входящие одновременно в обе эти формулы, свободные в каждой из них, то

выражения (F1 F2 ) , (F1 F2 ) , (F1 F2 ) , (F1 F2 ) также являются формулами. При этом предметные переменные, свободные (связанные) хотя

88

бы в одной из формул F1, F2, называются свободными (связанными) и в новых формулах;

5) если F – формула и х предметная переменная, входящая в F свободно, то выражения ( x)F и ( x)F также являются формулами, в которых переменная х связанная, а все остальные предметные переменные, входящие в формулу F свободно или связанно, остаются и в новых формулах соответственно такими же;

6) никаких других формул логики предикатов нет.

Формулы, определённые в п.1 и 2, называются элементарными (или атомарными). Формулы, не являющиеся элементарными, называются составными.

Формулы, в которых нет свободных предметных переменных, называются замкнутыми, а формулы, содержащие свободные предметные переменные – открытыми.

Превращение формулы логики предикатов в высказывание (а также само получаемое высказывание) называется интерпретацией этой формулы на множестве М:

–если формула логики предикатов замкнутая, то её интерпретация сводится к подстановке вместо всех предикатных переменных конкретных предикатов, определённых на множестве М, в результате чего формула превращается в конкретное высказывание;

–если формула логики предикатов открытая, то её интерпретация состоит из двух этапов:

1)вместо всех предикатных переменных подставляем конкретные предикаты, определённые на множестве М, в результате чего формула превратится в конкретный предикат, зависящий от такого количества предметных переменных, сколько было свободных предметных переменных

висходной формуле;

2)подставляем вместо этих предметных переменных конкретные предметы из множества М, в результате чего этот предикат (и, значит, вся исходная формула) превратится в конкретное высказывание.

89

Пример 4.5. Дадим интерпретацию формуле ( х) ( у) Р(х, у) . Решение. В качестве множества М возьмём множество всех мужчин, а

вместо предикатной переменной Р(х, у) подставим конкретный предикат, определённый на М: «х есть отец у». Тогда исходная формула превратится в следующее ложное высказывание ( х) ( у) (х есть отец у) – «У каждого мужчины есть сын».

Этой же формуле можно дать и другую интерпретацию. Возьмём в качестве множеств М множество N всех натуральных чисел, а вместо предикатной переменной Р(х, у) подставим конкретный предикат «x < y», определённый на N2. Тогда исходная формула превратится в истинное высказывание ( х) ( у) (x y) – «Для каждого натурального числа существует большее по сравнению с ним натуральное число».

Формула логики предикатов называется выполнимой (опровержимой) на множестве М, если при некоторой подстановке вместо предикатных переменных конкретных предикатов, заданных на этом множестве, она превращается в выполнимый (опровержимый) предикат.

Другими словами, формула выполнима (опровержима) на М, если существует истинная (ложная) её интерпретация на М.

Формула логики предикатов называется тождественно истинной (тождественно ложной) на множестве М, если при всякой подстановке вместо предикатных переменных любых конкретных предикатов, заданных на этом множестве, она превращается в тождественно истинный (тождественно ложный) предикат.

Формула логики предикатов называется общезначимой, или

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

Тот факт, что формула F является тавтологией, обозначается, как и в алгебре высказываний, ╞ F.

Пример 4.6. Показать, что формула Р(х) ( у) Р( у) является противоречием (тождественно ложной).

90