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

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

Каждый человек смертен.

Сократ — человек, следовательно, он смертен.

Очевидно, рассмотренное рассуждение интуитивно корректно. Однако, введя следующие обозначения:

Р: Каждый человек смертен,

Q: Сократ — человек,

R: Сократ смертен,

мы получаем формулу Ρ  Q  R, которая не доказуема в ИВ. Указанное несоответствие между утверждениями имеет место потому, что в логике высказываний не используется структура высказываний Р, Q и R. В этой главе мы введем логику предикатов (логику первого порядка) и исчисления предикатов, которые позволяют преодолевать подобные трудности и дают возможность проводить формализацию большей части повседневного и математического языка. Аналогично исчислению секвенций и исчислению высказываний мы будем рассматривать два их расширения — секвенциальное исчисление предикатов данной сигнатуры Σ (ИПС^) и исчисление предикатов гильбертовского типа ИП^. Построение исчислений предикатов данной сигнатуры мы начнем с понятий синтаксиса и семантики формулы, определения алгебраических систем (АС).

1. Алгебраические системы. Формулы сигнатуры σ. Истинность формулы на алгебраической системе

Часто объектом изучения в математике служит множество с определенной на нем структурой (к примеру, треугольники с отношением подобия), для уточнения этого понятия введем определение АС.

Упорядочная тройка =<P, F, > называется сигнатурой, если выполняются следующие условия:

1. Множества P и F не имеют общих элементов;

2.  - отображение множества PF в .

Элементы P называются символами отношений или предикатами; F –символами операций или функций. Отображение  называется отображением местности или арности для (валентность). Если (q)=n, то q – n-местный предикатный символ, если qP, и q – n-местный функциональный символ, если qF. 0-местный функциональный символ назовем символом константы или просто константой.

Часто конечную сигнатуру =<P, F, > будем представлять в виде =<p₁^(p₁⁾,...,p_n^(p_n⁾,... f₁^(f₁⁾,..., f_k^(f_k⁾,...,c₁,..c_m..>=<P, F, C>(иногда с индексом)

Будем говорить, что  содержится в ₁ (₁), если PP₁, FF_1, _1.

Если PF, F= (P=), то  называется предикатной (функциональной). Если PF=, то  назовем пустой.

Упорядочная пара A=<A,  ^A > ( часто будем обозначать готическими буквами A)называется алгебраической системой сигнатуры , если выполняются следующие условия:

1. А – непустое множество

2.  ^A - отображение PF в множество отношений и операций на множестве А;

3. если pP, то  ^A (p) является (p)-местным отношением на А;

4. если fF, то  ^A (f) является (f)-местной операцией на А

Множество А назовем носителем A, ^A – интерпретацией сигнатуры  в А. (далее вместо ^A(p) будем обозначать p^A или p, если ясно о какой A идет речь). Мощностью АС A будем называть мощность ее носителя А( количество элементов).

Зафиксируем некоторую сигнатуру Σ и счетное множество V = {v_t | i ω}, элементы которого будем называть переменными и обозначать буквами х, у и z, возможно, с индексами. Алфавит исчисления предикатов сигнатуры Σ (ИΠ^Σ) состоит из следующих групп символов:

1. Предикатные и функциональные символы, образующие сигнатуру Σ.

2. Символы переменных, составляющих множество V.

3. Символ равенства: .

4. Логические связки: ¬, , , .

5. Кванторы: ,.

6. Вспомогательные символы: левая скобка (, правая скобка), запятая ,.

Термы сигнатуры  определим по индукции:

1. переменные xV являются термами

2. если t₁,...t_n – термы , fF, (f)=n, то f(t₁,...t_n) – терм  (при n=0 константа с – тоже терм).

Пример. =<c, g⁽²⁾, h⁽²⁾>, g,h –функции. x, y,V, тогда термами являются с, x, y, g(c,x), h(c,c), g(y,h(c,c)),h(y,c), h(g(c,x),h(y,c)).

Обозначим через Τ(Σ) множество всех термов сигнатуры Σ, в определении которых используются лишь переменные из V. Очевидно, любой терм из Τ(Σ) является словом алфавита ИΠ^Σ.

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

1. если t₁, t₂  Τ(Σ), то (t₁ t₁) — атомарная формула;

2. если р⁽ⁿ⁾  Σ — предикатный символ, t₁,...t_n  Τ(Σ), тο p(t₁,...t_n) — атомарная формула;

3. никаких атомарных формул, кроме построенных по пп. 1, 2, нет.

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

1. атомарная формула есть формула;

1. если φ, ψ — формулы и xV, то ¬ψ, (ψ φ), (ψ φ),(φ ψ), x φ, xφ — формулы;

2. никаких формул, кроме построенных по пп. 1, 2, нет.

Символы , , использованные в определении, называются соответственно квантором всеобщности и квантором существования. Запись x (соответственно х) читается "для всех х" ("существует х"). Все соглашения относительно расстановок скобок, принятые ранее, остаются в силе и для формул логики предикатов. Кроме того, вместо записей x₁...x_n φ и х₁... х_n φ будем использовать записи x₁,...,x_n φ и х_1,... ,х_nφ. Формула φ сигнатуры Σ называется бескванторной, если она не содержит кванторов.

Пример1. Рассмотрим предикатную сигнатуру Σ=<Q⁽¹⁾,R⁽¹⁾,P⁽¹⁾, меньше⁽²⁾> со следующими интерпретациями:

Q(x) – x - рациональное число,

R(x) - x — вещественное число,

Р(х) - x — простое число,

меньше(х, у) х < у.

Формула x (Q(x) R(x)) означает, что любое рациональное число является вещественным, а формула xy (меньше(х, у) Ρ (у)) – для любого элемента х найдется больший элемент у, являющийся простым числом.

2. Любая бескванторная формула сигнатуры нульместных предикатов может рассматриваться как формула исчисления высказываний. Например, таковой является формула АВ ¬С сигнатуры Σ = {А⁽⁰⁾, В⁽⁰⁾, С⁽⁰⁾}.

Определим множество SF(φ) подформул формулы φ сигнатуры Σ:

1. если φ — атомарная формула, то φ — ее единственная подформула и SF(φ) = {φ};

2. если φ имеет вид ¬φ₁, или x φ₁, или х φ₁, то подформула формулы φ — это либо φ, либо подформула формулы φ₁ и SF(φ)=SF(φ₁){φ}.

3) если φ имеет вид φ₁φ₂, или φ₁φ₂, или φ₁φ₂, то подформула формулы φ — это либо φ, либо подформула формулы φ₁, либо подформула формулы φ₂ и SF(φ) = SF(φ₁)  SF(φ₂) {φ}·

Каждое вхождение квантора () в данную формулу φ однозначно определяет некоторое вхождение хψ (хψ) подформулы из SF(φ), первым символом которого является рассматриваемое вхождение соответствующего квантора. Формула хψ(хψ), связанная с вхождением квантора (), называется областью действия этого вхождения квантора.

Заметим, что в записи формулы возможно наложение области действия вхождения одного квантора с данной переменной на область действия другого квантора с той же самой переменной. Например, в формуле х(Р₂(х,у)  xΡ₁(x)) вхождение переменной x в Р₁(х) находится одновременно под кванторами x и x. Поскольку число переменных, образующих множество V, бесконечно, мы будем избегать подобных коллизий введением новых переменных для меньших областей действия вхождений кванторов. Так, вместо формулы х(Р₂(х,у)  xΡ₁(x)) будет рассматриваться, например, формула х(Р₂(х,у)  zΡ₁(z)).

Говорят, что вхождение переменной x в формулу φ связано в φ, если оно находится в области действия некоторого вхождения квантора в формулу φ, имеющую вид x ψ или х ψ; в противном случае это вхождение называется свободным в φ. Переменная x называется свободной (связанной), если некоторое вхождение x в φ свободно (связано).

Пример 3. Рассмотрим следующие формулы сигнатуры S={P₁⁽¹⁾, P₂⁽²⁾}:

¬ P₁(x); P₂(x,y)x P₁(x); x(P₂(x,y)P₁(x))

Переменная х в первой формуле является свободной, во второй — и свободной, и связанной, в третьей — связанной; переменная у во всех формулах свободна.

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

Пример 4. Формула x,y(x + у  у + х) является предложением сигнатуры {+}, формула zх (у Р₂(х,у)¬Ρ₁(x)) — предложением сигнатуры <{ P₁⁽¹⁾, P₂⁽²}> а формула x (Р₂(х,у)¬Ρ₁(x)) предложением не является.

Запись φ(x₁,..,x_n) будет означать, что все свободные переменные формулы φ содержатся в множестве {x₁,..,x_n }.

Дадим индуктивное определение истинности формулы φ(x₁,..,x_n) сигнатуры Σ на элементах a₁,..,a_n  А в алгебраической системе A = (Α;Σ) (запись A╞ φ(a₁,..,a_n) будет означать, что формула φ истинна на элементах a₁,..,a_n А в системе A):

1. если t₁, t₂  Τ(Σ), то A |= t₁( a₁,..,a_n)  t₂ (a₁,..,a_n)  значения термов t₁, t₂ в системе A на элементах a₁,..,a_n A совпадают;

2. если p^(k) — предикатный символ сигнатуры Σ, t₁,...t_k T(Σ), то A╞P(t₁(a₁,..,a_n),..., t_k(a₁,..,a_n)) -- <t₁(a₁,..,a_n),..., t_k(a₁,..,a_n)>P_A;

1. A |= (ψ(a₁,..,a_n)χ(a₁,..,a_n))  A |= ψ(a₁,..,a_n) и A |= χ(a₁,..,a_n)

2. A |= (ψ(a₁,..,a_n)χ(a₁,..,a_n))  A |= ψ(a₁,..,a_n) или A |= χ(a₁,..,a_n)

3. A |= (ψ(a₁,..,a_n)χ(a₁,..,a_n))  если A |= ψ(a₁,..,a_n), то A |= χ(a₁,..,a_n)

4. A |= ¬ψ(a₁,..,a_n)  неверно, что A |= ψ(a₁,..,a_n)

5. A |=xψ(x,a₁,..,a_n)  A |= ψ(a,a₁,..,a_n) для aA

6. A |=xψ(x,a₁,..,a_n)  A |= ψ(a,a₁,..,a_n) для некоторого aA

Если не выполняется A|=φ(a₁,..,a_n), то будем говорить, что формула φ ложна на элементах a₁,..,a_n в системе A, и писать A φ(a₁,..,a_n)

Пример 1. Записать формулу φ(x), истинную в A=<; +⁽²⁾, ⁽²⁾> тогда и только тогда, когда x четно.

Искомая формула φ(x) имеет, например, вид y (х  у + у).

Пример 2.. Рассмотрим формулу φ(x, у) функциональной сигнатуры {+^(2),0⁽⁰⁾}, имеющую вид (х + у  0). Для алгебраической системы A = <Z; +, 0> тогда и только тогда имеет место A╞φ(m, n), когда т = —n. Для формулы ψ(х)=у (х+у  0) справедливо A╞ ψ(п) для любого целого числа n, поскольку у любого целого числа имеется к нему противоположное и так же целое число. Следовательно, A╞xy(x +y  0).

Ф ормула φ(x₁,..,x_n) сигнатуры Σ называется тождественно истинной или общезначимой (тождественно ложной или противоречивой), если для любой алгебраической системы A = <Α; Σ> и любого кортежа элементов (a₁,..., а_п)  А^п выполнено A╞φ(a₁,..., а_п) (A φ(a₁,..., а_п))· Если φ — тождественно истинное предложение, то пишем ╞ φ.

Формула φ(x₁,..,x_n) называется выполнимой в системе A, если A╞φ(a₁,..., а_п) для некоторых a₁,..., а_п А.

Пример 1. Формула (х  х) общезначима, поскольку A╞(а  а) для любой системы A = <A; Σ> и любого элемента a А По этой же причине формула ¬(x  х) тождественно ложна.

Пример 2. Формула φ= x, у (х · у  у · x) выполнима, но не тождественно истинна, так как <Z; > |= φ, а на АС =<Μ₂(Ζ); ·> не выполняется, где Μ₂(Ζ) —множество матриц порядка 2 с элементами из Ζ.

Пример3. φ=xy(x +y  0) - выполнима, но не тождественно истинна, так как <Z; +,0> |= φ, <N;+,0> φ. Т.е. предложение φ описывает свойство, отличающие системы друг от друга.

Предложение 1.

1. Для любой формулы φ сигнатуры Σ следующие формулы общезначимы:

(а) x ¬φ  ¬x φ;

(б) х ¬φ ¬x φ;

(в) x,y φ  y,xφ;

(г) х,уφ у,хφ;

(д) xy φ yx φ.

2. Для любой формулы φ сигнатуры Σ формула x φ х¬φ противоречива. . 

Заметим, что общезначимость формулы yx φ xy φ в общем случае утверждать нельзя.

Следующая теорема позволяет создавать общезначимые и противоречивые формулы на основе формул ИВ.

Теорема 1. Пусть φ(Α₁,..., А_п) — общезначимая (противоречивая) формула ИВ, φ₁,..., φ_n — формулы сигнатуры Σ. Тогда в результате подстановки формул φ₁,..., φ_n вместо всех соответствующих вхождений пропозициональных переменных Α₁,..., А_п образуется общезначимая (противоречивая) формула φ(φ₁,..., φ_n) сигнатуры Σ.

Доказательство. Нетрудно заметить, что если φ(Α₁,..., А_п) — общезначимая (противоречивая) формула ИВ, то при любых значениях истинности формул φ₁,..., φ_n на элементах алгебраической системы формула φ(φ₁,..., φ_n) будет истинной (ложной) на тех же элементах. 

Теорема 2. Если f — изоморфизм системы A на систему A, φ(x₁,... ,х_п) — формула сигнатуры системы A, то для любых a₁,..., а_пА свойство A╞φ(a₁,..., а_п) эквивалентно свойству A╞ φ(f(а₁),..., f(а_n)).

Доказательство легко проводится индукцией по числу шагов построения формулы φ. При этом для атомарной формулы φ утверждение следует непосредственно из определения изоморфизма. 

Множество формул Г сигнатуры Σ с множеством свободных переменных X называется выполнимым, если существует система M = <Μ; Σ>, элементы а_х  Μ для каждого x X такие, что для любой формулы φ(x₁,... ,х_п)  Γ выполнимо M ╞ φ(а_x1,... ,а_xп). Система M называется моделью множества формул Г, и этот факт обозначается через M ╞Г.

Пример. Рассмотрим следующее множество формул сигнатуры {}, описывающих линейные порядки: Γ_lo = {х (х  x),x,y,z(((x у)(у z)) (x  z)),x,y(((x у)  (у  х))  (хy)),x,y((x  у)  (у  х))}· Очевидно, что множество Γ_lo имеет как конечные, так и бесконечные модели. Например, <{0};  > ╞ Г_1о, где {0} = {(0,0)}, а на <Ν;  > ╞ Г_lo. Добавив к множеству Г_1о две формулы х, у ¬(х  у) и х, у((х  у)¬ (х  у) z((x  z)¬(x  z)  (z у)¬(z у))), получаем множество Г_dlo, описывающее бесконечные плотные линейные порядки. Моделями множества Г_dlo являются в точности бесконечные линейно упорядоченные множества, у которых между любыми двумя различными элементами имеется некоторый промежуточный. Примерами таких моделей служат <Q;  > и <R;  >.