§ 5. Изучение формализма исчисления предпкатов

1. Понятие переводимости; производные правила.

Таким образом, мы далеки от общего решения проблемы разрешимости. Следовательно, в этом отношении в исчислении предикатов мы имеем существенно иное положение, чем в исчислении высказываний. Здесь мы не можем, как в исчислении высказываний, заменить вывод формул применением какой-либо распознающей процедуры; напротив, мы в принципе оказываемся вынужденными остановиться на дедуктивном методе.

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

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

В исчислении высказываний преобразования производятся путем применения определенных правил замены. При таком

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

является тождественно истинной.

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

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

является выводимой.

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

Основание называть переход от преобразованием в случае переводимости нам дают следующие факты:

1. Если переводима в то и переводима в Если переводима в в то переводима в

2. Если переводима в то выводима из выводима из с помощью наших основных правил.

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

Утверждения 1 и 2 очевидны; утверждение 3 является следствием того, что из эквивалентности можно, во-первых, вывести

а кроме того, для любого выражения можно вывести

Заметим также, что любые две выводимые формулы переводимы друг в друга.

Действительно, если обе выводимы, то выводимы также а вместе с ними и значит, переводима в .

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

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

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

если она не содержит ни х, ни у, ни z, мы можем перейти к

следующим образом.

Сначала подставим вместо а какую-нибудь не входящую в свободную переменную, например , а затем подставим а вместо так мы получим

Применив правило мы получим

а отсюда, переименовав переменную и подставив а вместо с, получим

Эта формула вместе с формулой

получающейся из формулы по схеме заключения дает

Переименовав и подставив а вместо получаем

а отсюда по правилу (7) получаем

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

можно получить такие формулы, как

из

можно получить

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

(Это правило является частичным обращением предыдущего.) Допустим, что у нас имеется формула

и пусть мы хотим получить из нее

С этой целью мы сначала подставим вместо переменной а, если она входит в какую-нибудь новую свободную переменную, например с; если переменная х входит в переименуем ее в какую-нибудь еще не встречавшуюся связанную переменную, например в . В результате из

получится некоторая формула

Теперь переименуем у в х. Получившаяся формула

вместе с формулой

получающейся подстановкой из формулы по схеме заключения дает

Подставим теперь вместо а какую-нибудь новую переменную, например и переименуем Из получившейся формулы

воспользовавшись еще раз формулой (а) и применив схему заключения, мы получим

и, подставив вместо

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

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

Так, от импликации

если переменные х и у в нее не входят, мы можем перейти к

или же к

Точно так же от эквивалентности

в которую не входят ни х, ни у, ни z, мы можем перейти к

Процедуру перехода мы рассмотрим на примере формулы

не содержащей переменных Выведем из нее формулу

Сначала, если в исходной формуле встречается переменная а, мы подставим вместо нее какую-нибудь новую переменную, например затем вместо с подставим а. Из получившейся формулы

мы по правилу получим

Переименовав х в у и подставив а вместо мы получим

Применив еще раз правило (6), мы получим

Если мы теперь снова подставим а вместо то придем к искомой формуле.

В случае, когда исходная формула является не импликацией, а эквивалентностью, вместо правила (6) следует применять правило (6).

Применив правило к эквивалентностям, мы, в частности, получим

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

Если, например, у нас имеется формула

то в выражении

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

В самом деле из тождественной формулы

подстановкой мы получим

Пусть при этом переменные выбраны так, что они не входят в .

Тогда правило даст нам формулу

Значит, исходная формула действительно переводима в формулу

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

В том случае, когда приставка состоит только из одного квантора всеобщности или существования, это правило получается непосредственным применением формул (7) и (9) 1) в сочетании с правилом переименования связанных переменных.

Распространение на случай нескольких кванторов всеобщности или нескольких кванторов существования мы проиллюстрируем на примере формулы вида

Наше правило утверждает, что эта формула переводима в формулу

Для доказательства возьмем какую-нибудь свободную переменную, не входящую в и например с. Так как мы уже умеем применять наше правило для случая одного квантора всеобщности, то мы получим, что

можно преобразовать в

Отсюда по правилу следует, что

может быть преобразована в

а эта формула по уже один раз примененному правилу для единичного квантора всеобщности переводима в

Поэтому формула

также переводима в эту формулу.

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

Так, например, выводимая формула

не переводима в

что усматривается хотя бы из того, что эта последняя формула не является даже 2-тождественной.

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

В качестве примера рассмотрим формулу вида

где не содержит переменной не содержит ни х, ни у, ни не содержит переменных х и у. Правило утверждает, что эта формула переводима в

Соответствующее преобразование производится следующим образом.

Возьмем сначала какие-нибудь две свободные переменные, не входящие в исходную формулу, например Из формулы (8) подстановкой и переименованием мы получаем

По правилам и отсюда получается

Таким образом, наша исходная формула переводима в

В этой формуле мы прежде всего можем по правилу поменять местами члены дизъюнкции, так что получится

Теперь применим формулу (5) 3); из нее подстановкой и переименованием х в у получается

а отсюда, по правилам

Возьмем, кроме того, формулу, получающуюся из формулы (8) подстановкой [и применением правила (г)]:

Из обеих этих эквивалентностей получается, что формула

а тем самым и исходная формула, переводима в формулу

из которой нужная нам формула получается перестановкой членов дизъюнкции.

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

Это правило получается применением формул (13) и (13). Так, например, любая формула

переводима в

Действительно, произведя подстановку в формулу (13) и переименовав переменные хлувуигв обеих частях эквивалентности, мы получим

а отсюдд, по правилу

С другой стороны, формула (13) переименованием у в и подстановкой вместо именной формы дает формулу

а из предыдущей эквивалентности путем подстановки вместо именной формы и последующего переименования получается

Три полученные эквивалентности совместно друг с другом дают формулу

из которой и получается нужная нам переводимость.

Следует заметить, что, согласно правилу перестановка следующих друг за другом кванторов всеобщности допустима и в том случае, когда им предшествует квантор существования, так что, например, формула

переводима в

Правило Отрицание формулы с кванторной приставкой может быть получено заменой каждого из кванторов

всеобщности квантором существования, каждого квантора существования — квантором всеобщности, а следующего за ними выражения — его отрицанием.

Так, формула

может быть преобразована в

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

затем из формулы (3) переименованием х в у и подстановкой получаем

Теперь по правилу получается

Объединив эту формулу с ранее полученной, мы получаем

откуда и вытекает искомая переводимость.