Математическая логика и теория алгоритмов

В примерах, приведенных  выше, мы видели, что для записи предикатов использовались арифметические выражения: 2x, x+y, – x². Аналогом арифметического выражения в логике служит понятие терма.

Определение. Термом называется

1) переменная и константа;

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

Можно сказать, что терм – выражение, полученное из переменных и констант с помощью  символов функций.

Определение. Атомарной формулой называется выражение вида r(t₁,…,t_n), где t₁,…,t_n – термы, r – символ n-местного предиката.

Примерами атомарных  формул являются выражения x£y²+1, |x-y|<z, x делит нацело y-3.

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

1) атомарная  формула,

2) выражения  вида (F)&(G), (F₁)Ú(G), Ø(F), (F)®(G),(F)«(G), ("v)(F), ($v)(F), где F и G – формулы логики предикатов, v – переменная.

Формула F в двух последних выражениях называется областью действия квантора по переменной n.

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

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

Например, в формуле

F=t(x)&("y)[s(x,y)®($x)(r(x,y)Út(y))]

Первое и второе вхождение переменной x свободны, третье и четвертое связаны. Все вхождения  переменной y связаны.

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

Формула F из предыдущего  примера имеет одну свободную  переменную x.

Если x₁,…,x_n – все свободные переменные формулы F, то эту формулу будем обозначать через F(x₁,…,x_n). Это обозначение будем применять и в том случае, когда не все переменные из x₁,…,x_n являются свободными в F.

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

Необходимо соотнести  формулы логики предикатов первого  порядка и предикаты. Как и в логике высказываний подобное соотнесение осуществляет функция, называемая интерпретацией.

 

Определение. Интерпретацией на непустом множестве М называется функция, заданная на сигнатуре FÈR, которая

1) константе  ставит в соответствие элемент из М;

2) символу n-местной  функции ставит в соответствие  некоторую n-местную функцию, определенную  на множестве М;

3) символу n-местного  предиката ставит в соответствие n-местный предикат, заданный на  М.

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

Приведем примеры. Пусть сигнатура состоит из символа  одноместного предиката P и двухместного предиката D, M={2,3,6,9,12,15} и

F=(P(x)&("_y)(P(y)®D(x,y))

Поставим в  соответствие (проинтерпретируем) P(x) предикат «x – простое число», D(x,y) – предикат «x меньше или равно y». Тогда формула F получит в соответствие предикат «x=2». На этом же множестве можно рассмотреть и другую интерпретацию: P(x) ставится в соответствие «x – нечетное число», D(x,y) – предикат «x делит y». В таком случае, формула F получает в соответствие предикат «x=3». Если j – интерпретация, то предикат, соответствующий формуле F будем обозначать через j(F).

Одним из основных типов задач этой темы являются задачи, связанные с использованием выразительных возможностей языка логики предикатов. В качестве примера рассмотрим задачу перевода на язык логики предикатов следующего рассуждения. «Каждый первокурсник знаком с кем-либо из спортсменов. Никакой первокурсник не знаком ни с одном любителем подледного лова. Следовательно, никто из спортсменов не является любителем подледного лова». Для удобства ссылок это рассуждение условимся называть рассуждением о первокурсниках. Выберем следующую сигнатуру:

П(х): «х – первокурсник»,

С(х): «х – спортсмен»,

Л(х): «х – любитель подледного лова»,

З(x,y): «х знаком с y».

Тогда рассуждение  запишется в виде следующей последовательности формул.

Н₁=("x)[П(х)®($y)(C(y)&З(x,y))],

H₂=("x)("y)[П(x)&Л(y)®ØЗ(x,y)],

H₃=("x)(C(x)®ØЛ(x))

Равносильность, законы логики первого порядка 

Определение. Формулы F(x₁,…,x_n) и G(x₁,…,x_n) называются равносильными, если для любой интерпретации j с областью М высказывания (jF)(a₁,…,a_n) и (jG)(a₁,…,a_n) при любых a₁,…,a_n из М одновременно истинны или одновременно ложны.

Пусть F(x)=Ø("y)P(x,y), G(x)=($y)ØP(x,y), где Р – символ двухместного предиката. Докажем, что формулы F(x) и G(x) равносильны. Возьмем интерпретацию j с областью М. Пусть высказывание (jF)(a) истинно для aÎM. Истинность этого высказывания означает, что не для всякого yÎM высказывание (jP)(a,y) истинно. Следовательно, найдется bÎM, для которого высказывание (jP)(a,b) ложно. Если высказывание (jP)(a,b), ложно, то высказывание Ø(jP)(a,b) истинно. Отсюда следует, что найдется yÎM такой, для которого высказывание Ø(jP)(a,y) истинно. Это означает истинность высказывания (jG)(a). Итак, мы доказали, что если высказывание (jF)(a) истинно, то высказывание (jG)(a) тоже истинно. Обратная импликация доказывается аналогично. Значения истинности высказываний (jF)(a) и (jG)(a) при любом aÎM совпадают. Следовательно, формулы F(x) и G(x) равносильны.

 

Определение. Формула F(x₁,…,x_n) называется тождественно истинной, если для любой интерпретации j с областью М высказывание (jF)(a₁,…,a_n) при любых a₁,…,a_n из М является истинным.

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

22) ("x)(F(x)&G(x) равносильна ("x)(F(x)&("x)G(x),

23) ($x)(F(x)ÚG(x) равносильна ($x)F(x)Ú($x)G(x),

24) ("x)("y)F(x,y) равносильна ("y)("x)F(x,y),

25) ($x)($y)F(x,y) равносильна ($y)($x)F(x,y),

26) Ø("x)F(x) равносильна ($x)ØF(x),

27) Ø($x)F(x) равносильна ("x)ØF(x).

Законы 22, 23 утверждают, что квантор общности можно переносить через конъюнкцию, а квантор существования через – дизъюнкцию. Естественно поставить вопрос, можно ли квантор существования переносить через конъюнкцию, а квантор общности – через дизъюнкцию. Другими словами, будут ли равносильны следующие пары формул

 

("x)(F(x)ÚG(x) и ("x)(F(x)Ú("x)G(x)

($x)(F(x)&G(x) и ($x)(F(x)& ($x )G(x) ?

 

Оказывается нет. Докажем это для случая, когда F(x) и G(x) – атомарные формулы. Пусть  основное множество – множество натуральных чисел N, F(x) – предикат «x – четное число» , G(x) – предикат «x – нечетное число». Обозначим эту интерпретацию буквой j. Тогда j("x)(F(x)ÚG(x))]=1, но j[("x)F(x)Ú("x)G(x)=0. Аналогично, j($x)(F(x)&G(x))]=0 и j($x)F(x)&($x)G(x)]=1.

 

Рассмотрим законы 24 и 25. Они утверждают, что одноименные кванторы можно менять местами. Можно ли переставлять местами разноименные кванторы, сохраняя равносильность. Другими словами, равносильны ли формулы

 

("x)($y)(F(x,y) и ($y)("x)F(x,y)?

 

Оказывается, тоже нет. В качестве основного множеств возьмем опять множество натуральных чисел, F(x,y) будем считать атомарной формулой и поставим ей в соответствие предикат «x меньше y». Тогда левая формула будет истинной, правая – ложной.

 

Вернемся к законам 22 и 23. Мы отмечали, что квантор существования – через конъюнкцию. Тем не менее, если одна из формул F или G не содержит переменной x, то это делать можно. Запишем соответствующие законы:

 

28) ("x)(F(x)ÚG) равносильна ("x)(F(x)ÚG,

29) ($x)(F(x)&G) равносильна ($x)(F(x)&G, где G не содержит x.

 

Законы 22, 23, 28, 29 можно записать в общем виде:

30) (Q₁x)(Q₂z)(F(x)ÚG(z)) равносильна (Q₁x)F(x)Ú(Q₂z)G(z)

31) (Q₁x)(Q₂u)(F(x)&G(u)) равносильна (Q₁x)F(x)&(Q₂u)G(u),

где Q₁, Q₂ кванторы V или Э, u не входит в F(x), а x не входит в G(u). Для доказательства равносильности двух формул могут оказаться полезными следующие законы:

Рассмотрим формулу F(x)=("y)P(x,y)®P(x,c), где P – символ двухместного отношения, с – константа. Докажем, что формула F(x) тождественно истинна. Возьмем интерпретацию j с областью М и элемент а из М. Высказывание (jF)(a) равно ("y)(jP)(a,y)®(jP)(a,j(c)). Если посылка ("y)(jP)(a,y) ложна, то вся импликация (jF)(a) истинна. Предположим, что посылка ("y)(jP)(a,y) истинна. Это означает, что для всякого yÎM высказывание (jP)(a,y) истинно, в том числе истинно это высказывание и для y=j(c). Следовательно, истинно заключение (jP)(a,j(c)) и вся импликация (jF)(a). Мы доказали, что высказывание (jF)(a) истинно для любого aÎM. Это означает, что формула F(x) является тождественно истинной.

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

Теорема 3.1 Формулы F(x₁,…,x_n) и G(x₁,…,x_n) равносильны тогда и только тогда, когда формулы F(x₁,…,x_n)«G(x₁,…,x_n) тождественно истинны.

Законы замены переменных:

32) ("x)F(x) равносильна ("z)F(z),

33) ($x)F(x) равносильна ($z)F(z).

В законах 32 и 33 переменная z не входит в F(x), а переменная x не входит в F(z).

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

Проиллюстрируем его на примере следующей задачи: доказать равносильность формул:

F=Ø("x)($y)[S(x)&P(x,y)®($z)(T(z)&P(x,z))]

G=($x)("y)[S(x)&P(x,y)&("z)(T(z)®ØP(x,z))].

Применим к формуле F последовательно законы логики предикатов, получим, что формула F равносильна формуле

F₁=($x)("y)Ø[Ø(S(x)&P(x,y))Ú($z)(T(z)&P(x,z))].

Далее, используя  законы логики предикатов из F₁, получим формулу

F₂=($x)("y)[S(x)&P(x,y)&("z)Ø(T(z)&P(x,z))].

Осталось заметить, что в формуле F₂ подформулу Ø(T(z)&P(x,z)) можно заменить на T(z)®ØP(x,z).

Доказательство равносильности двух формул будем проводить с помощью законов логики первого порядка. Доказательство того, что формулы неравносильны, будем осуществлять построением интерпретации, при которой одна формула истинна, другая ложна. Например, так, как это было сделано выше для доказательства неравносильности формул ("x)(F(x)ÚG(x)) и ("x)F(x)Ú("x)G(x). Разумеется, до построения интерпретации формулы можно предварительно преобразовывать с помощью законов.

Логическое  следствие

Определение. Формула G(x₁,…,x_n) называется логическим следствием формул F₁(x₁,…,x_n),…,F_k(x₁,…,x_n), если для любой интерпретации j с областью М и любых a₁,…,a_nÎM из истинности высказываний (jF₁)(a₁,…,a_n),…,(jF_k)(a₁,…,a_n) следует истинность высказывания (jG)(a₁,…,a_n).

Приведем примеры. Пусть F₁=("x)(P(x)®Q(x)&R(x)), F₂=P(c), G=Q(c). Покажем, что формула G является логическим следствием формул F₁ и F₂. Возьмем интерпретацию j с областью М такую, что высказывания jF₁ и jF₂ истинны. Элемент j(c) обозначим буквой b. Истинность jF₂ означает, что высказывание (jP)(b) истинно. А истинность высказывания jF₁ означает, что для любого элемента xÎM истинно высказывание (jP)(x)®(jQ)(x)&(jR)(x). Поскольку это высказывание истинно для любого х, то, в частности, истинно для x=b. Мы видим, что истинна импликация (jP)(b)®(jQ)(b)&(jR)(b) и ее посылка (jP)(b). Из таблицы истинности импликации следует истинность заключения (jQ)(b)&(jR)(b). Следовательно, истинно высказывание (jQ)(b). А это и есть jG. Мы доказали, что если истинны высказывания jF₁ и jF₂, то истинно высказывание jG, т.е. что G –логическое следствие F₁ и F₂.

В качестве второго  примера докажем нелогичность рассуждения  о первокурсниках. Мы записали это  рассуждение в виде последовательности формул Н₁,Н₂, и Н₃. Для доказательства нелогичности рассуждения надо найти интерпретацию j, при которой формулы Н₁ и Н₂ истинны, а формула Н₃ ложна. Пусть множество М состоит из трех элементов 2,3,4. Символы С, Л и П проинтерпретируем следующим образом:

 

(jС)(х)=«х – простое число»,

(jЛ)(х)=«х – четное число»,

(jП)(х)=’’х>4»,

 

т.е. П интерпретируется как тождественно ложный предикат. Тогда формулы Н₁ и Н₂ истинны, поскольку посылки импликаций этих формул ложны при любом х. А формула Н₃ ложна. Чтобы убедиться в этом достаточно взять х=2. Следовательно, рассуждение о первокурсниках нелогично.

 

Определение. Множество формул

 

K={F₁(x₁,…,x_l),…,F_m(x₁,…,x_l)}

 

называется выполнимым, если существует интерпретация j с областью М и элементы a₁,…,a_lÎM такие, что все высказывания (jF₁)(a₁,…,a_l),…,(jF_m)(a₁,…,a_l) истинны.

Множество формул K = { F₁=("x)($y)(P(y)&Q(x,y)), F₂=("y)Q(c,y), F₃=ØP(c) } выполнимо. Возьмем в качестве области интерпретации множество натуральных чисел N. Символы P,Q и C проинтерпретируем следующим образом:

 

(jP)(u)=«u – простое число»,

(jQ)(u,v)=«u меньше или равно v»,

j(C)=1.

 

Тогда высказывание jF₁ означает, что для любого натурального числа х найдется простое число y, которое не меньше х, высказывание jF₂ означает, что 1 –наименьшее натуральное число, а высказывание jF₃ означает, что 1 – непростое число. Ясно, что все эти высказывания истинны, и поэтому множество формул K выполнимо.

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

Теорема 3.2. Формула G(x₁,…,x_n) является логическим следствием формул F₁(x₁,…,x_n),…,F_k(x₁,…,x_n) тогда и только тогда, когда множество формул {F₁(x₁,…,x_n),…,F_k(x₁,…,x_n),ØG(x₁,…,x_n)} невыполнимо.

Нормальные  формы 

Как и в логике высказываний, в логике первого порядка  вводятся нормальные формы. Мы рассмотрим две из них: предваренную нормальную и сколемовскую нормальную формы.

Определение. Формула G имеет предваренную нормальную форму (сокращенно: ПНФ), если

G(Q₁,x₁)…(Q_n,x_n)H,

где Q₁,…,Q_n кванторы, а формула H не содержит кванторов.

Например, формула ("x)($y)(P(x,y)&ØQ(y)) имеет предваренную нормальную форму, а формула Ø("x)(T(x)&S(x,y)) не имеет.

Теорема 3.3. Для всякой формулы F существует формула G, равносильная F и имеющая предваренную нормальную форму.