Исчисление предикатов первого порядка

Определение логики предикатов

Формальная система, называемая исчислением предикатов первого порядка, или логикой предикатов первого порядка, является расширением логики высказываний. Логика предикатов дает возможность более детально рассматривать, а следовательно, более точно формализовать знания и рассуждения о свойствах объектов предметной области.

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

— л — «не», «неверно, что»,.

V — «или», «либо», л — «и», «а», «но»,.

-> — «если», «при условии, что»,.

= — «равносильно», «эквивалентно», «тогда и только тогда, когда».

В силу этого формулы логики высказываний обозначают простые или сложные (с несколькими грамматическими основами) повествовательные предложения, в которых выражены свойства предметной области. Исчисление высказываний не «проникает» внутрь простого высказывания, т. е. не учитывает его внутренней структуры.

Логика предикатов позволяет учесть внутреннюю структуру простых высказываний, обеспечивая тем самым более точное представление знаний и рассуждений о свойствах предметной области. Рассмотрим простое высказывание «5 является целым положительным числом». В логике высказываний оно может быть обозначено единственным пропозициональным символом р. В логике предикатов это простое высказывание может быть представлено формулой /(5)л/^>(5), в которой использованы одноместные предикаты: 1(х) — означает «* — целое число»,.

Р (х) — означает «х — положительное число».

Другое простое высказывание «квадрат любого действительного числа положителен» в логике высказываний может быть обозначено единственным пропозициональным символом q. В логике предикатов оно может быть представлено формулой в которой

V — квантор общности, обозначающий фразы: «все», «любой», «произвольный», «для всех» и т. п.,.

R (x) — предикат, означающий «х — действительное число»,.

Q (x) — предикат, означающий «х — неотрицательное число», s (x) — функция, определяемая равенством s (x) =х².

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

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

1. Алфавит

а, b, с,… — константы, х, у, z,… — переменные,.

/, g, /7,… — функциональные символы; каждый символ характеризуется некоторым натуральным числом т — число аргументов символа; это число называют арность, или местность символа,.

Р, Q, R,… — предикатные символы; каждый символ также характеризуется некоторым натуральным числом п — число аргументов символа; это число называют арность, или местность, символа,.

/?, q, г,… — пропозициональные символы (символы высказываний), -1, -> — логические связки (отрицание, импликация),.

V — квантор общности, О, 1 — символы значений истинности: 0 — «ложь» и 1 — «истина».

• (,) — скобки; используются для правильной записи и интерпретации формул.
• 2. Синтаксические правила
• — символы 0 и 1 являются формулами,
• — любой пропозициональный символ есть формула,
• — если А есть формула, то (А) тоже является формулой,
• — если А, А_х и А₂ являются формулами, то выраженияА, А_{аА₂, A_tvA₂, A_t—>A₂ и А_] = А₂ тоже являются формулами,
• — если Р— /7-местный предикатный символ, х, х₂, …, х" — переменные, то выражение Р (х_ьх_ъ …, х") является формулой,
• — если А (х, х₂,…, х") — формула, в которой отсутствуют кванторы, то выражение /х, Л (Xj, х₂,…, х") является формулой, при этом в ней х, называется связанной переменной, а остальные переменные называются свободными.
• 3. Аксиомы (А)А^> (А^В)
• 042) 04-> (Я->С))-> (04—"/?)—" 04—>0)
• 043) (-i/?-«-u4)—> 04->Д)
• 044) {VtB (t))-> В (и), где и — переменная и B (t) не содержит и в качестве связанной переменной,
• 045) (/t (A^B))^> (A->Vt (B)), где А и В являются формулами, а/не является свободной переменной в формуле А.

Заметим, что первые три аксиомы такие же, как в логике высказываний.

4. Правила вывода

— правило modus ponens,

— правило обобщения, где t — свободная переменная в А.