Интерпретация и классификация формул логики предикатов

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

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

Пример 1. Дадим интерпретацию формуле . В качестве множества М возьмем множество всех мужчин, а вместо предикатной переменной подставим конкретный предикат, определенный на М: «х есть отец у». Тогда исходная формула превратится в следующее (очевидно, ложное) высказывание — «у каждого мужчины есть сын». Этой же формуле можно дать и другую интерпретацию. Возьмем в качестве , где ‑ множество натуральных чисел, а вместо предикатной переменной подставим предикат «». Тогда исходная формула превратится в (очевидно, истинное) высказывание ‑ «для каждого натурального числа существует большее по сравнению с ним натуральное число».

Пример 2. В предыдущем примере была рассмотрена интерпретация замкнутой формулы. Дадим интерпретацию открытой формуле . Возьмем и вместо предикатных переменных и подставим трехместные предикаты «» и «» соответственно, а вместо нульместного предиката подставим (ложное) высказывание «». Тогда данная формула превратится в двухместный предикат (от предметных переменных х, у):

.

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

.

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

истинно.

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

Сформулируем классификационные определения для формул логики предикатов.

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

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

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

Нахождение тавтологий является одной из важнейших задач логики предикатов, как и алгебры высказываний. Но если в алгебре высказываний имеется общий метод определения, является или нет данная формула тавтологией (это — метод составления таблицы истинности для формулы), то в логике предикатов такого общего метода не существует. Каждая формула подлежит изучению индивидуальным методом на тождественную истинность. Дело здесь в том, что каждое высказывание имеет только одно из двух логических значений: «истина» или «ложь»», тогда как значение предиката зависит от выбора значений его предметных переменных, который, вообще говоря, можно сделать бесконечным числом способов.