Логические операции

Алгебра предикатов

Формально определяется следующим образом:

А_пред =<T; F>,

где T= {T₁,T₂,T₃,T₄} - носитель алгебры:

Т₁ - множество предметных переменных,

Т₂ – множество предметных постоянных,

Т₃={f₁,f₂,f₃,...} – множество функциональных символов,

Т₄=(P₁,P₂,P₃,...} – множество предикатных символов,

F={F₁,F₂,F₃} – сигнатура алгебры:

F₁={¬,&,∨,→,↔} - множество логических связок,

F₂={∀,∃} - множество кванторов,

F₃={≡} - символ равносильности формул.

В логике предикатов существует понятие терма:

1. Любую предметную переменную и предметную постоянную предиката называют термом - t_i.

2. Если f_i - функциональный символ и t₁,t₂,...,t_n – его аргументы-термы, то f_i(t₁,t₂,…,t_n) также есть терм.

3. Никаких иных термов нет.

Введем понятие формулы в логике предикатов:

1. Если P_i – предикатный символ и t₁,t₂,...,t_n – термы, то F=P_i(t₁,t₂,...,t_n) - элементарная формула.

2. Если F₁ и F₂ - формулы, то ¬F₁, ¬F₂, (F₁&F₂), (F₁∨F₂), (F₁→F₂), (F₁↔F₂) - также формулы.

3. Если F - формула, a x - предметная переменная, входящая в формулу F, то ∀_x(F) и ∃_x(F) - также формулы.

4. Никаких иных формул нет.

Отрицание (¬F(t₁,t₂,…,t_n)) есть одноместная операция, посредством которой из данной формулы F(t₁,t₂,…,t_n) получают ее отрицание. Например, задан предикат Р(х,"стол"):=«находиться около стола». Тогда:

∀_x(¬Р(х,"стол")):=«для всех х верно, что х не находится около стола»,

¬∀_x(Р(х,"стол")):=«не для всех х верно, что х находится около стола»,

¬∃_x(Р(х,"стол")):=«нет таких х, для которых верно, что х находится около стола”.

Конъюнкция (F₁(t₁₁,t₁₂,…,t_1n)&F₂(t₂₁,t₂₂,…,t_2n)) есть двуместная операция, посредством которой из формул F₁ и F₂ получают новую формулу F (t₁₁,t₁₂,…,t_1n,t₂₁,t₂₂,…,t_2n) с числом предметных переменных и постоянных, равным объединению их в исходных формулах.

Значение формулы F истинно тогда и только тогда, когда истинны обе формулы F₁ и F₂. Например, даны предикаты P₁(х):=«быть выдающимся музыкантом» и P₂(х):=«быть талантливым писателем». Тогда:

∃_x(P₁(х))&∃_x(P₂(х)):=«существуют выдающиеся музыканты и существуют талантливые писатели»,

∃_x(P₁(х)&P₂(х)):=«существуют лица, которые являются выдающимися музыкантами и талантливыми писателями».

¬∀_x(P₁(х)&P₂(х)):=«не каждый может быть и выдающимся музыкантом, и талантливым писателем».

Дизъюнкция (F₁(t₁₁,t₁₂,…,t_1n)∨F₂(t₂₁,t₂₂,…,t_2n)) есть двуместная операция, посредством которой из формул F₁ и F₂ получают новую формулу F (t₁₁,t₁₂,…,t_1n,t₂₁,t₂₂,…,t_2n) с числом предметных переменных и постоянных, равным объединению их в исходных формулах. Значение формулы F ложно тогда и только тогда, когда ложны обе формулы F₁ и F₂. Например, пусть предметные переменные х, у - города России; заданы предикаты P₁(х,y):=«транспортная связь х и у поездом», P₂(х,y):=«транспортная связь х и у самолетом», P₃(х,y):=«транспортная связь х и у автобусом». Тогда:

∀_x∀_y(P₁(х,y)∨P₂(х,y)∨P₃(х,y)):= «для всех городов России возможна транспортная связь поездом, автобусом или самолетом».

Импликация (F₁(t₁₁,t₁₂,…,t_1n)→F₂(t₂₁,t₂₂,…,t_2n)) есть двухместная операция, посредством которой из формул F₁ и F₂ получают новую формулу F(t₁₁,t₁₂,…,t_1n,t₂₁,t₂₂,…,t_2n) с числом предметных переменных и постоянных, равным объединению их в исходных формулах. Значение формулы F ложно тогда и только тогда, когда F₁ истинно, а F₂ - ложно. Например, заданы предикаты P₁(x):=«быть судьей», P₂(x):=«быть юристом». Тогда:

∀_x(P₁(x)→P₂(x)):=«все судьи – юристы»,

¬∀_x(P₂(x)→P₁(x)):=«неверно, что все юристы – судьи».

Эквивалентность (F₁(t₁₁, t₁₂,…, t_1n)↔F₂(t₂₁, t₂₂,…, t_2n)) есть двуместная операция, посредством которой из формул F₁ и F₂ получают новую формулу F(t₁₁,t₁₂,…,t_1n,t₂₁,t₂₂,…,t_2n) c числом предметных переменных и постоянных, равным объединению их в исходных формулах. Значение формулы истинно тогда и только тогда, когда обе формулы F₁ и F₂ имеют одно и то же значение истины или лжи. Например, пусть х - предметная переменная и задан предикат Р(х). Тогда:

∃_x(P(x))↔¬∀_x(¬P(x)):= «формула существования переменной х, для которой Р(х) истинен, эквивалентна формуле «не для всех х Р(х) ложен»».

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

1. за квантором общности чаще всего следует импликация, а за квантором существования - конъюнкция,

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

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

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

Дата добавления: 2014-01-04