Логика предикатов с одним переменным
Аристотелем и вошла как традиционный элемент в систему гуманитарного
образования. Известные формы высказываний этой логики и формы
умозаключений, так называемые «модусы силлогизмов», выражаются полностью в
символике логики предикатов от одного переменного.
Теорема. Если формула логики предикатов, содержащая только предикаты от
одного переменного, выполнима на некотором поле M, то она выполнима на поле
[pic], содержащем не более [pic] элементов, где n - число предикатов,
входящих в рассматриваемую формулу.
Пусть формула U(A1, ..., An), содержащая только символы предикатов A1,
..., An, каждый из которых зависит от одного переменного, выполнима на
некотором поле M. эту формулу мы можем предполагать представленной в
нормальной форме, а все предметные переменные в ней связанными. В самом
деле, какова бы ни была формула U, мы можем, произведя над ней
преобразования, привести её к виду, в котором все кванторы предшествуют
остальным символам формулы, при этом состав её предикатов и предметных
переменных не изменяется. Если в U есть свободные предметные переменные, то
можно связать их квантором общности.
Итак, допустим, что U – нормальная формула. Тогда мы можем представить её
следующим образом:
(( x1)(( x2)...(( xp) B(A1, ..., An, x1, ..., xp),
где каждый из символов (( xi) обозначает квантор ((xi) или ((xi), а формула
B(A1, ..., An, x1, ..., xp)
кванторов не содержит.
В формуле B(A1, ..., An, x1, ..., xp) все переменные x1, ..., xp входят в
предикаты A1, ..., An, и её можно записать в виде
B(A1([pic]), ..., An([pic])),
где i1, ..., in – числа от 1 до p. Однако, будет удобнее пользоваться
выражением
B(A1, ..., An, x1, ..., xp),
если иметь в виду, что B является логической функцией предикатов Ak, а
каждый предикат Ak зависит от какого-то одного переменного [pic].
Покажем, что если для некоторого поля M существуют индивидуальные
предикаты
[pic],..., [pic],
для которых формула U([pic],..., [pic]) истинна, то эта формула истинна и
на некотором подмножестве этого поля, содержащем не более [pic] элементов,
так как иначе наше утверждение тривиально. Разобьём элементы множества M на
классы следующим образом. Для каждой последовательности, содержащей n
символов И и Л в произвольном порядке (И, Л, Л, ..., И,), существует часть
(может быть, пустая) множества M, содержащая те и только те элементы x, для
которых последовательность значений предикатов [pic](x), [pic](x), ...,
[pic](x) совпадает с данной последовательностью символов И и Л.
Обозначим через [pic]1, [pic]2, ...,[pic]n
последовательность символов И и Л, где [pic]i представляет собой И или Л,
а соответствующий этой последовательности класс элементов x обозначим
[pic][pic], [pic], ..., [pic].
Некоторые из этих классов могут оказаться пусты, так как может случиться,
что для некоторой последовательности [pic]1, [pic]2, ...,[pic]n не
существует такого элемента, для которого предикаты [pic], [pic], ..., [pic]
принимают соответствующие значения [pic]1, [pic]2, ...,[pic]n . Вместе с
тем каждый элемент множества M принадлежит одному из классов [pic], и
различные классы общих элементов не имеют. Число всех классов (пустых и
непустых) равно числу последовательностей [pic]1, [pic]2, ...,[pic]n, т. е.
[pic]. Следовательно, число q непустых классов [pic] не превышает [pic].
Выберем из каждого непустого класса по одному элементу и обозначим эти
элементы
a1, a2, ..., aq.
Множество всех этих элементов обозначим [pic].докажем, что если формула
U([pic], ..., [pic]) истинна на поле M, то она истинна и на поле [pic] (так
как [pic] – часть поля M, то предикаты [pic] определены на [pic]). каждому
элементу x поля M поставим в соответствие элемент из [pic], принадлежащий
тому же классу, что и х. В [pic] существует один и только один такой
элемент. Элемент из [pic], поставленный в соответствие х, обозначим
[pic](х). Можно сказать, что мы построили функцию, определённую на
множестве M и принимающую значения из множества [pic].
[pic]Легко видеть, что имеет место следующая равносильность:
[pic](х) ( [pic]([pic](х)).
Действительно, [pic](x) принадлежит тому же классу [pic], что и x. Но, по
определению, для элементов одного и того же класса каждый предикат [pic]
принимает одно и то же значение. Отсюда следует, что если в формуле
U([pic], ..., [pic]) для каждого предметного переменного t заменить каждое
выражение [pic](t) через [pic]([pic](х)), то формула U([pic], ..., [pic])
перейдёт в формулу [pic]([pic], ..., [pic]), равносильную первой. Написание
формулы [pic] отличается от U только тем, что все предметные переменные x,
y, z, …, u формулы U замещены соответственно через [pic](х), [pic](y), ...,
[pic](u). Это следует из того, что по условию формула U([pic], ..., [pic])
содержит только предикаты [pic], и поэтому всякое предметное переменное
входит только под знаком одного из этих предикатов.
Пусть R (x, y, ..., u) – предикат, определённый на поле M. Введём
обозначение
[pic] R (x, y, ..., u).
Под этим выражением мы будем понимать предикат, зависящий от y, z, ..., u
(или высказывание, если, y, z, ..., u отсутствуют) и принимающий значение
И, когда R (y, z, ..., u) имеет значение И для данных y, z, ..., u и для
всех x, принадлежащих полю [pic], и принимающий значение Л в
противоположном случае. Введём также выражение
[pic] R (x, y, ..., u),
которое представляет собой предикат от y, ..., u и принимает значение И,
когда R (x, y, ..., u) имеет значение И для y, ..., u и по крайней мере для
одного значения x из поля [pic], и значение Л в противоположном случае.
Знаки [pic] и [pic] будем называть ограниченными кванторами. Если мы все
переменные предиката R (x, y, ..., u) свяжем ограниченными кванторами,
например
[pic][pic]...[pic] R (x, y, ..., u),
то получим формулу, отнесённую к полю [pic]. покажем, что выражение
((x) R ([pic](х), y, ..., u)
равносильно выражению
[pic] R (x, y, ..., u).
Пусть ((x) R ([pic](х), y, ..., u) имеет значение И. В таком случае R
([pic](х), y, ..., u) имеет значение И для данных y, ..., u и для каждого
x. Но так как функция [pic](х) пробегает всё поле [pic], когда x пробегает
поле M, то R (x, y, ..., u) имеет значение И для данных y, ..., u и для
всех x из [pic]. В силу определения [pic] R (x, y, ..., u) также принимает
значение И. Обратно, если [pic] R (x, y, ..., u) принимает значение И, то R
(x, y, ..., u) имеет значение И для данных y, ..., u и для каждого x из
[pic]. В таком случае выражение R ([pic](х), y, ..., u) имеет значение И
для данных y, ..., u и для каждого x из M, так как [pic](х) для любого x
принадлежит [pic].
Аналогичным образом можно показать, что выражения
([pic]) R ([pic](х), y, ..., u) и ([pic]) R (x, y, ..., u)
также равносильны.
Рассмотрим формулу U([pic], ..., [pic]), которую можно представить в
форме
(( x1)(( x2)...(( xp) B([pic], ..., [pic], x1, ..., xp).
B([pic], ..., [pic], x1, ..., xp)
представляет собой предикат, определённый на поле M и зависящий от p
переменных x1, ..., xp. Каждое из этих переменных входит в формулу B только
через предикаты [pic], ..., [pic]. С другой стороны, мы видели, что
предикаты [pic](х) и [pic]([pic](х)) равносильны. Поэтому если в формуле
B([pic], ..., [pic], x1, ..., xp) мы заменим xi на [pic](хi), то получим
равносильное выражение:
B([pic], ..., [pic], x1, ..., xp) ( B([pic], ..., [pic],[pic](x1), ...,
[pic](xp)).
Отсюда следует, что
(( xp) B([pic], ..., [pic], x1, ..., xp) ( (( xp) B([pic], ..., [pic],
[pic](x1), ..., [pic](xp)).
Далее можно заключить, что
(( xp) B([pic], ..., [pic], [pic](x1), ..., [pic](xp)) (
( [pic] B([pic], ..., [pic], [pic](x1), ..., [pic](xp-1), xp).
Рассуждая аналогичным образом, мы получим
(( xp-1) (( xp) B([pic], ..., [pic], x1, ..., xp-1 , xp) (
([pic][pic] B([pic], ..., [pic], [pic](x1), ..., [pic](xp-2), xp-1, xp)
и, наконец, придём к следующему:
(( x1)(( x2)...(( xp) B([pic], ..., [pic], x1, ..., xp) (
( [pic][pic] B([pic], ..., [pic], x1, ..., xp).
Правая часть последней равносильности, согласно смыслу символа [pic],
представляет не что иное, как формулу
(( x1)...(( xp) B([pic], ..., [pic], x1, ..., xp),
отнесённую к полю [pic].
Таким образом, мы доказали, что формула U([pic], ..., [pic]) сохраняет
своё значение, если её отнести к полю [pic], и теорема, таким образом,
доказана.
С л е д с т в и е. Если формула U, содержащая только предикаты, зависящие
от одного переменного, является тождественно истинной для всякого поля, не
превышающего [pic] элементов, где n – число предикатов в U, то формула U
тождественно истинна (т. е. истинна для любого поля). В самом деле
допустим, что U не является тождественно истинной формулой. В таком случае
её отрицание [pic] выполнимо на некотором поле. Так как [pic] также
удовлетворяет условиям теоремы, то найдётся поле, содержащее не более [pic]
элементов, на котором формула [pic] выполнима. Следовательно, U не может
быть истинной на этом поле, что противоречит условию. Итак, предположение,
что U не является тождественно истинной, приводит к противоречию, что и
требовалось доказать.
§2. Практика по решению проблемы разрешимости формул,
содержащих предикаты от одного переменного
Доказанная (в предыдущем параграфе) теорема позволяет решать проблему
разрешимости для формул, содержащих только предикаты, зависящие от одного
переменного. Из следствия видно, что для того, чтобы установить, является
ли формула U тождественно истинной или нет, достаточно проверить, является
ли она тождественно истинной для всякого поля, содержащего не более чем
[pic] элементов.
Заметим, что достаточно проверить, является ли данная формула U
тождественно истинной на поле, состоящем ровно из [pic] элементов. Это
следует из того, что для формул рассматриваемого типа имеет место
следующее: если формула U тождественно истинна на некотором поле, то она
тождественно истинна на всякой его части.
Рассмотрим произвольное поле, содержащее ровно [pic] элементов: [pic],
[pic], ..., [pic]. Легко видеть, что всякая формула, имеющая вид:
((x) B(x),
отнесённая к данному полю, равносильна формуле
B([pic]) ( B([pic]) ( ... ( B([pic]).
А формула, имеющая вид:
([pic]x) B(x),
равносильна формуле
B([pic]) [pic] B([pic])[pic] ... [pic] B([pic]).
В таком случае произвольная формула U, отнесённая к полю {[pic], ...,
[pic]}, равносильна формуле [pic], в которой все кванторы заменены
операциями логического произведения и логической суммы. Если в U входили
только предикаты A1, ..., An, зависящие от одного переменного, то [pic]
представляет собой формулу, образованную только операциями алгебры
высказываний над выражениями Ai(xj), 1 ( i ( n, 1 ( j ( [pic]. Так как
предикаты Ai(x) совершенно произвольны, то выражения Ai(xj) представляют
собой совершенно произвольные высказывания. Формулу [pic] тогда можно
рассматривать как формулу алгебры высказываний, у которой Ai(xj) являются
элементарными переменными высказываниями. Тогда вопрос о тождественной
истинности U на поле [pic], [pic], ..., [pic] оказывается эквивалентным
вопросу о тождественной истинности [pic], как формулы алгебры высказываний
с переменными высказываниями Ai(xj).
Заметим, что формула алгебра высказываний [pic] по существу не зависит от
того, каковы элементы поля {[pic], ..., [pic]}, а зависит только от их
числа, так как если мы возьмём другое поле {[pic](, ..., [pic](}, то в
[pic] произойдёт только перемена обозначений переменных высказываний Ai(xj)
на Ai(xj(). В силу этого мы можем сказать, что если [pic] тождественно
истинна, как формула алгебры высказываний, то формула U тождественно
истинна на любом поле из p элементов, и обратно. С другой стороны, был
получен конструктивный способ определять – является произвольная формула
алгебры высказываний тождественно истинной или нет. Применяя этот критерий,
мы можем установить, будет ли произвольная формула U, содержащая только
предикаты от одного переменного, тождественно истинной на любом поле,
содержащем p = [pic] элементов. В таком случае в силу высказанного выше
положения мы можем решить также и вопрос о том, будет формула U
тождественно истинной или нет.
Разберём это конкретно на примерах.
П Р И М Е Р 1: Итак, пусть дана формула U, имеющая вид:
((x)[P(x)[pic]( [pic][pic]P(x))],
отнесённая к некоторому полю L. Для того, чтобы установить тождественную
истинность этой формулы, нам достаточно проверить, является ли она
тождественно истинной на поле, содержащем ровно [pic] элементов (см. выше).
В данном случае число предикатов (n) равно 2, т.е. L может быть
представлено как { a1, a2, a3, a4 }.
Легко видеть, что формула U равносильна: ((x)[P(x)[pic](Q(x)[pic]P(x))],
которая, отнесённая к полю L, равносильна [pic]:
[P([pic])[pic](Q([pic])[pic]P([pic]))][pic]
[pic][P([pic])[pic](Q([pic])[pic]P([pic]))] [pic]
[P([pic])[pic](Q([pic])[pic]P([pic]))] [pic] [P([pic])[pic](Q([pic])[pic]
[pic]P([pic]))].
Таким образом, [pic] представляет собой формулу, образованную только
операциями алгебры высказываний над выражениями P([pic]) и Q([pic]), где
i=[pic], т.е. её можно рассматривать как формулу алгебры высказываний, у
которой P([pic]) и Q([pic]) являются элементарными переменными
высказываниями. Значит, ответив на вопрос о тождественной истинности [pic],
мы сможем сказать, является ли формула U тождественно истинной или нет.
[pic] является тождественно истинной в алгебре высказываний [pic] U также
тождественно истинная формула на поле, содержащем [pic] элементов. Это
оэначает, что U тождественно истинна.
П Р И М Е Р 2: Доказать, что формула U, отнесённая к некоторому полю L,
представленная как
[((х)( [pic][pic] Q(x)) [pic]P(x)],
является тождественно истинной.
Для этого она должна быть тождественно истинной на поле, содержащем ровно
[pic] элементов. В данном случае n = 2, т.е. L можно опять определить как {
a1, a2, a3, a4 }.
Применяя равносильные преобразования над U, можем заключить её
равносильность формуле: ((х)[([pic][pic]Q(x))[pic]P(x)], которая,
отнесённая к полю L, равносильна [pic]: [([pic][pic]Q([pic]))[pic]P([pic])]
[pic] [([pic][pic]Q([pic]))[pic]P([pic])] [pic]
[([pic][pic]Q([pic]))[pic]P([pic])] [pic]
[([pic][pic]Q([pic]))[pic]P([pic])].
Легко видеть, что [pic], как и в предыдущем примере, представляет собой
формулу, образованную только операциями алгебры высказываний над
выражениями P([pic]) и Q([pic]), где i=[pic], а поэтому её можно отнести к
формулам алгебры высказываний, у которой P([pic]) и Q([pic]) являются
элементарными переменными высказываниями. Является ли формула [pic]
тождественно истинной?
Формула [pic] представляет собой дизъюнкции некоторых формул. Поэтому
всякий раз, когда одна из них истинна, сама [pic] (по определению
дизъюнкции) будет тождественно истинной. Составим таблицу истинности:
P Q [pic] [pic][pic]Q ([pic][pic]Q)[pic]P
0 0 1 0
1
0 1 1 1
0
1 0 0 1
1
1 1 0 1
1
Таким образом, формула ([pic][pic]Q)[pic]P является выполнимой,
следовательно, [pic] является тождественно истинной формулой в алгебре
высказываний [pic] U также тождественно истинная формула на поле,
содержащем [pic] элементов. Это оэначает, что U тождественно истинна.
ЛИТЕРАТУРА
П. С. Новиков, “Элементы математической логики”, государственное
издательство физико-математической литературы, М., 1959
Страницы: 1, 2
