§ 30. Дедуктивная эквивалентность

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

Обычно говорят, что два выражения аир дедуктивно эквивалентны по отношению друг к другу, когда возможно вывести р из а, если принято а, и обратно, а — из р, если принято р. Правила вывода всегда пред-полагаются данными. Но они редко бывают достаточными. Они достаточны, например, в следующем примере. Из принятого закона коммутации CCpCqrCqCpr мы можем вывести положение CqCCpCqrCpr:

CCpCqrCqCpr

p/CpCqr, r/Cpr X С(1) — (2)

CqCCpCqrCpr,

и снова из этого положения мы можем вывести закон коммутации

q/CqCCpCqrCpr, p/s, r/tXC(2) — (3)

CCsCCqCCpCqrCprtCst

q/CpCqr, p/q, r/Cpr X (4)

CCpCqrCCqCCpCqrCprCqCpr

s/CpCqr, t/CqCpr X С(4) — (1)

(1) CCpCqrCqCpr ).

Но мы не можем таким простым способом вывести из цринятого выражения CNpCpqзакон Дунса Скота CpCNpq, потому что из первого выражения мы можем выводить новые предложения лишь с помощью подстановки, а все подстановки в CNpCpqначинаются с CN, а не с Ср.Для того чтобы вывести одно из этих выражений из другого, нам потребуются вспомогательные средства. Вообще говоря, отношение дедуктивной эквивалентности редко бывает абсолютным, в большинстве случаев оно соотносительно определенному основанию положений. В нашем случае этим основанием является закон коммутации. Начиная с

CNpCpq,

мы получаем посредством коммутации закон Дунса Скота:

p/Np, qtp, rlqX С (5) —(6)

CpCNpq,

а, начиная с (6), мы вновь получаем посредством коммутации (5)

q/Np, rjqX С (6) — (5)

CNpCpq.

Я говорю поэтому, что CNpCpqи CpCNpqдедуктивно эквивалентны относительно закона коммутации, и пишу

CNpCpq~ CpCNpqотносительно (1).

Знак «~» обозначает отношение дедуктивной экви-валентности.

Qpq= KCpqCqp

и не нуждается в каком-либо основании. Если принимается обычная эквивалентность Qa|3 и а или подстановка на место а, то мы можем принять (3 или соответствующую подстановку на ‘место (3, и наоборот. Принятая обычная эквивалентность Qaj3является, следовательно, достаточным основанием для дедуктивной эквивалентности а~(3, но она не является для нее необходимым основанием. Этот пункт как раз нуждается в объяснении.

Не только принятые или истинные выражения могут быть дедуктивно эквивалентными, таковыми могут быть и ложные выражения. Для того чтобы решить проблему разрешимости для С—N-системы, мы должны уметь преобразовать произвольное осмысленное выражение a в выражении CNCLT:, где тс — пропозициональная беременная, не встречающаяся в а. Это может быть сделано с помощью двух положений:

CpCNpq

CCNppp

Я говорю, что а дедуктивно эквивалентно СЛ/атс относительно S1и S2, и пишу:

I. а ~ СЛЛхтс относительно S1 и S2.

Все проходит легко, когда а принято. Возьмем в качестве примера NNCpp.Это положение легко верифицируется с помощью О—7-метода. В соответствии с формулой I я пишу соотношение

NNCpp~CNNNCppqотносительно S1 и S2. Начиная с

NNCpp,

мы получаем с помощью S1

p/NNCppXC(7) —(8)

CNNNCppq,

а начиная снова с (8), мы получаем с помощью подстановки и S2:

q/NNCpp X (9)

CNNNCppNNCpp

р!NNCpp X С (9) — (7)

NNCpp.

Но а — произвольное выражение; оно может быть ложным, например Cpq.В этом случае формула I читается:

Cpq ~ CNCpqrотносительно S1 и S2.

Здесь начинаются затруднения: мы можем получить положение CCpqCNCpqrиз S1при помощи подстановки p/Cpq, #/г, — но мы не можем вывести из этого положения консеквент CNCpqr, так как Cpqне является положением и не может быть принято. Следовательно, CNCpqrне может быть отделено.

На мой взгляд, существует лишь один способ устранить эти трудности: ввести операцию отбрасывания в теорию дедукции. Мы аксиоматически отбрасываем переменную р и допускаем очевидные правила отбрасывания (с) и (d). На этой основе можно легко показать, что Cpqдолжно быть отброшено. Ибо мы полу-чаем из аксиомы

(*10) р и положения

СССрррр посредством правил отбрасывания

ХС(*12) — (*10)

(*12) ССррр

(*12) X (*Щр/Срр,qlp (*13 )Cpq.

Теперь мы в состоянии доказать, что если Cpqотбрасывается, то CNCpqrтакже должно быть отброшено; и обратно, если CNCpqrотбрасывается, то Cpqтакже должно быть отброшено. Начиная с

(*ЩСРЯ>

мы получаем с помощью S2 и правил отбрасывания

S2. p/CpqX (14)

(14) CCNCpqCpqCpq

ХС(*15) —(*13)

(*15) CNCpqCpq

(*15) X (*16)r/Cpq (*16) CNCpqr.

В другом направлении мы легко получаем Cpqиз (*16) с помощью S1:

SI. plCpq, qlrX[(17)

CCpqCNCpqr

X С (*13) — (*16) (*13) Cpq.

Формула I теперь полностью подтверждена, однако мы должны исправить наше предыдущее определение де-дуктивной эквивалентности, сказав:

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

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

Cpq~CNCpqrотносительно S1 и S2.

Соответствующая обычная эквивалентность QCpqCNCpqr здесь не имеет места, так как она ложна при р/1, q/0, r/L

Очевидно, что отношение дедуктивной эквивалентности рефлексивно, симметрично и транзитивно. Имеются случаи, когда а дедуктивно эквивалентно двум выражениям р и у относительно определенных положений. Это значит: если принимается а, то принимается р и принимается 7, а следовательно, принимается их конъюнкция «р и 7»; и обратно, если принимаются и р и 7или их конъюнкция «р и 7», то принимается также а. С другой стороны, если а отбрасывается, то конъюнкция «р и 7» также должна быть отброшена, а в этом случае достаточно, чтобы было отброшено лишь одно из них, р или 7; и обратно, если хотя бы одно из них отброшено, также должно быть отброшено и а.