Полные по Новикову логики: метод перевода

Алгебра и логика, 43, N 3 (2004), 364—378

УДК 510.64

ПОЛНЫЕ ПО НОВИКОВУ ЛОГИКИ: МЕТОД ПЕРЕВОДА∗) А. Д. ЯШИН Введение Переводом называется отображение t : Fm(L) → Fm(L′ ) из множества Fm(L) высказываний языка (сигнатуры) L в множество Fm(L′ ) высказываний языка L′ . К переводам предъявляются следующие требования: 1) он должен быть эффективно задан, т. е. по высказыванию A ∈ ∈ Fm(L) его перевод t(A) ∈ Fm(L′ ) строится явным образом, кроме того, по любой формуле из Fm(L′ ) можно эффективно определить, является ли она переводом какой-либо формулы; 2) он должен по возможности сохранять смысл высказываний, в частности, если в языках L и L′ есть общая часть L ∩ L′ 6= ∅, то высказывания из нее переводом не преобразуются. Существует множество примеров применения техники перевода в таких разделах, как аксиоматическая теория множеств, теории первого порядка, модальные и неклассические логики. Как правило, с помощью данного перевода t : Fm(L) → Fm(L′ ) строится либо образ некоторой теории T сигнатуры L, либо прообраз некоторой ∗)

Работа выполнена при финансовой поддержке FDD Foundation, грант N PM 884-

02.

c Сибиpский фонд алгебpы и логики, 2005

Полные по Новикову логики: метод перевода

365

теории T ′ сигнатуры L′ . При удачно выбранном переводе наследуются полезные свойства исходной теории. В данной работе вариант техники перевода применяется для построения новых примеров полных по Новикову логик на основе уже известных. § 1. О полных по Новикову логиках 1.1. Предварительные сведения. Язык L интуиционистской пропозициональной логики содержит пропозициональные переменные VAR = = {pi , qj , . . .} и стандартные связки ∧, ∨, →, ¬. Эквивалентность ↔ вводится как сокращение p ↔ r ⇋ (p → q) ∧ (q → p). Иногда удобно вводить в язык стандартные константы 0 (ложь) и 1 (истина). Формулы определяются обычным образом. Класс формул языка L обозначим Fm. Символом Int обозначается интуиционистская логика высказываний. В литературе описаны различные дедуктивные системы, а также семантика этой логики (см., напр. [1]). Законы Int будут в дальнейшем применяться без комментариев. 1.2. О ϕ-логиках. Пpедположим, что язык L интуиционистской логики высказываний pасшиpен путем добавления связок ϕ1 , . . . , ϕn . Каждая связка ϕi имеет ki = ar(ϕi ) аpгументных мест. В частности, связка без аpгументов называется константой. Расшиpенный язык обозначим чеpез L(ϕ), класс фоpмул pасширенного языка — чеpез Fm(ϕ). При этом Fm ⊆ Fm(ϕ). Формулы, не содержащие дополнительных связок, назовем чистыми. Через Sub A обозначается множество подформул формулы A. При этом A ∈ Sub A. Запись D(p1 , . . . , pm ) означает, что в формуле D участвуют только переменные из списка p1 , . . . , pm . Подстановкой в языке L(ϕ) называется отображение s : Fm(ϕ) −→ −→ Fm(ϕ), сохраняющее константы и коммутирующее со всеми логическими связками [2]: s(0) = 0, s(1) = 1, s(¬A) = ¬s(A), s(A ◦ B) = s(A) ◦ s(B) для ◦ ∈ {→, ∧, ∨}, s(ϕi (A1 , . . . , Aki )) = ϕi (s(A1 ), . . . , s(Aki )).

366

А. Д. Яшин

При этом s(A) назовем подстановочным примером формулы A. Фактически для задания подстановки достаточно задать s(p) для каждой пропозициональной переменной p, при этом применяется обозначение A(p|B, q|C, . . .), показывающее, что все вхождения переменной p заменяются формулой B, все вхождения q — формулой C и т. д. Пpавило замены эквивалентных для связки ϕi записывается как (A1 ↔ B1 ) ∧ . . . ∧ (Aki ↔ Bki ) . ϕi (A1 , . . . , Aki ) ↔ ϕi (B1 , . . . , Bki ) Назовем ϕ-логикой пpоизвольное множество фоpмул языка L(ϕ), включающее Int, замкнутое относительно пpавил modus ponens, подстановки и замены эквивалентных для каждой дополнительной связки. Аксиомой замены эквивалентных для связки ϕi называется формула ki ^

(pj ↔ qj ) → (ϕi (p1 , . . . , pki ) ↔ ϕi (q1 , . . . , qki )).

j=1

Схемой замены эквивалентных называется множество формул вида m ^

(pi ↔ qi ) → (D(p1 , . . . , pm ) ↔ D(q1 , . . . , qm ))

i=1

для всякой формулы D(p1 , . . . , pm ). ПРЕДЛОЖЕНИЕ 1.1. ϕ-логика L содержит схему замены эквивалентных тогда и только тогда, когда L содержит аксиому замены для каждой дополнительной связки из набора ϕ. Заметим: если ϕ-логика содержит схему замены эквивалентных, то правило замены эквивалентных становится излишним. Такие ϕ-логики назовем нормальными. L

Для краткости вместо A ↔ B ∈ L будем записывать A ↔ B. Внешнюю связку в формулах иногда обозначаем индексом в виде точки. 1.3. Консервативные ϕ-логики. ϕ-логика L называется консеpвативной (над Int), если для любой чистой формулы D справедливо D ∈ L ⇒ D ∈ Int.

Полные по Новикову логики: метод перевода

367

Пусть L — нормальная ϕ-логика, Σ — некоторое множество формул. Выводом в L из множества гипотез Σ называется конечная последовательность формул, в которой каждый элемент является либо формулой из L, либо гипотезой, либо получается из двух предыдущих формул этой последовательности по правилу modus ponens. Выводимость формулы A в L из Σ обозначаем Σ ⊢L A. ТЕОРЕМА 1.2 (дедукции). Для любых нормальной ϕ-логики L и формул A, B справедливо {A} ⊢L B ⇔ A → B ∈ L. ДОКАЗАТЕЛЬСТВО. Известное доказательство теоремы дедукции для классического (равно как и интуиционистского [3]) исчисления высказываний основано на схемах A → A, A → (B → A), (A → (B → C)) → ((A → B) → (A → C)) и на том, что modus ponens является единственным постулированным правилом вывода. В рассматриваемом случае все эти предпосылки выполняются, поэтому доказательство теоремы дедукции переносится практически без изменений. 2 Напомним, что посредством L + Σ обозначается наименьшая ϕ-логика, включающая L и Σ. Если Σ = {A}, то вместо L + {A} для краткости пишем L + A. ТЕОРЕМА 1.3. L + Σ совпадает с множеством формул, выводимых в L из множества SUBST(Σ) всех подстановочных примеров формул из Σ. ДОКАЗАТЕЛЬСТВО. Ясно, что всякая формула, выводимая в L из множества SUBST(Σ), содержится в L + Σ. Для доказательства обратного включения достаточно проверить, что множество L′ = {A ∈ Fm | SUBST(Σ) ⊢L A}

368

А. Д. Яшин

само является ϕ-логикой, т. е. включает Int, а также замкнуто по modus ponens и подстановке. Первые два требования выполняются очевидным образом, замкнутость по подстановкам проверяется индукцией по длине вывода с использованием свойства ”композиция подстановок является подстановкой“. 2 ТЕОРЕМА 1.4 (о присоединимости [4]). Пусть L — нормальная ϕ-логика, консервативная над Int. а) Множество Σ присоединимо к L тогда и только тогда, когда каждое конечное подмножество Σ′ ⊆ Σ присоединимо к L. б) Формула A неприсоединима к L тогда и только тогда, когда для некоторых подстановок s1 , . . . , sl на Fm(ϕ) некоторой чистой формулы D∈ / Int выполняется s1 (A) ∧ . . . ∧ sl (A) → D ∈ L. в) Константная формула E ϕ-языка неприсоединима к L тогда и только тогда, когда для некоторой чистой формулы D ∈ / Int выполняется E → D ∈ L.

§ 2. Полные по Новикову ϕ-логики 2.1. О новых интуиционистских связках. Пусть L — ϕ-логика. При каких условиях можно говорить, что L задает новые интуиционистские логические связки? Другими словами, как выразить интуиционистский смысл и новизну дополнительных связок в терминах свойств L? Анализируя различные работы, в которых в той или иной степени затрагивается этот вопрос, можно выделить следующий минимальный набор требований: — L консервативна над Int (это условие подчеркивает интуиционистский характер дополнительных связок); — L замкнута относительно правила замены эквивалентных; — L не содержит никакой формулы вида ϕi (p1 , . . . , pki ) ↔ D для чистой D (новизна).

Полные по Новикову логики: метод перевода

369

ЗАМЕЧАНИЕ. Отсутствие конкретного явного соотношения в L может оказаться случайным. Не исключено, что в некотором расширении L, по прежнему консервативном над Int, явное соотношение может присутствовать (подтверждением этому является т. н. логика Каминского, описывающая свойства оператора сильного будущего времени [5]). Подход П. С. Новикова, учитывающий это замечание, может быть сформулирован в виде следующих двух определений. ОПРЕДЕЛЕНИЕ. Нормальная ϕ-логика L называется полной по Новикову, если она консервативна над Int и для любой формулы A ∈ / L ϕ-логика L+A неконсервативна над Int. Другими словами, L не допускает присоединения никакой новой формулы. Явным соотношением для связки ϕi называется фоpмула вида ϕi (p1 , . . . , pki ) ↔ A, где A не содеpжит ϕi . ОПРЕДЕЛЕНИЕ. Связки ϕ1 , . . . , ϕn независимы в консервативной ϕ-логике L, если для любого ϕi ∈ ϕ и любой формулы A, не содержащей вхождений ϕi , ϕ-логика L + ϕi (p1 , . . . , pki ) ↔ A неконсервативна над Int. Другими словами, L не допускает присоединения явных соотношений. ЗАМЕЧАНИЕ. Отметим аналогию с трактовкой отрицания в методе вынуждения: условие a вынуждает ¬A, когда никакое корректное его расширение a′ ≥ a не вынуждает A (см. [6]). p) ↔ B Если |ϕ| = 1, то явные соотношения для ϕ имеют вид ϕ(¯ для некоторых чистой формулы B и переменных p¯ = {p1 , . . . , pk }. В этом случае можно говорить, что L определяет новую k-местную интуиционистскую связку ϕ. Таким образом, при этом подходе среди всех ϕ-логик интерес представляют нормальные ϕ-логики, не допускающие присоединения явных соотношений, а среди последних — полные ϕ-логики. 2.2. Примеры полных по Новикову логик. В связи с определениями, сформулированными выше, известна т. н. проблема Новикова,

370

А. Д. Яшин

заключающаяся в построении явных примеров полных ϕ-логик с независимыми связками. Лемма Цорна показывает, что у любой ϕ-логики, консервативной над Int, существует по крайней мере одно пополнение, однако она ничего не говорит о явном его описании. Необходимо уточнить, что считать явным примером. А. В. Кузнецов под явным примером подразумевал ϕ-логику, определяемую явным конечным списком дополнительных аксиом∗) . Кроме того, явно заданной можно считать и разрешимую ϕ-логику. В дальнейшем будет использоваться следующая ТЕОРЕМА 2.1 [4, 7]. Для любого набора ϕ дополнительных констант существуют явно заданные примеры ϕ-логик, в каждой из которых дополнительные константы независимы. В качестве конкретного примера упомянем т. н. логику Сметанича [8, 9]:     ϕ(p) ↔ ϕ(q), ϕ T = Int + ¬¬ϕ(p),    ϕ(p) → (q ∨ ¬q).

Первая аксиома этой логики показывает, что ϕ(p) не зависит от значения аргумента, т. е. ϕ можно рассматривать как логическую константу. В связи с этим T ϕ естественным образом переформулируется в языке с единственной дополнительной константой ϕ. Получающаяся при этом логика задается [10] так:   ¬¬ϕ, Sm = Int +  ϕ → (A ∨ ¬A).

Существует единственное полное по Новикову расширение Sm+ логики Sm (см. [11]). § 3. Полные по Новикову ϕ-логики: метод перевода 3.1. О прообразах логик. Рассмотрим языки L(ϕ) и L(ψ), содержащие наборы дополнительных связок ϕ = {ϕ1 , . . . , ϕn } и ψ = {ψ1 , ∗)

Это стало известным автору благодаря устному сообщению Л. Л. Максимовой.

Полные по Новикову логики: метод перевода

371

. . . , ψm }. Через Fm(ϕ) и Fm(ψ) обозначаются соответствующие классы формул. Пусть ki = ar(ϕi ), i = 1, . . . , n. Для каждой связки ϕi ∈ ϕ зафиксируем формулу Di (p1 , . . . , pki ) ∈ ∈ Fm(ψ) с ki переменными и определим перевод t : Fm(ϕ) −→ Fm(ψ) по следующему правилу: t(p) ⇋ p для всех p ∈ VAR; t(A ◦ B) ⇋ t(A) ◦ t(B) для ◦ ∈ {∧, ∨, →}; t(¬A) ⇋ ¬t(A); t(ϕi (A1 , . . . , Aki )) ⇋ Di (t(A1 ), . . . , t(Aki )). Следующая лемма показывает, что перевод t согласован с подстановками в языках L(ϕ) и L(ψ) (утверждение леммы можно назвать прямым условием согласованности перевода с подстановками). ЛЕММА 3.1. Для любой подстановки s : Fm(ϕ) −→ Fm(ϕ) найдется подстановка s′ : Fm(ψ) −→ Fm(ψ) такая, что s′ (t(A)) = t(s(A)) для любой формулы A ∈ Fm(ϕ). ДОКАЗАТЕЛЬСТВО. Для каждой p ∈ VAR положим s′ (p) ⇋ t(s(p)) и воспользуемся индукцией по построению A ∈ Fm(ϕ). Если A = p ∈ VAR, то s′ (t(p)) = s′ (p) = t(s(p)) по определению. Если A = B ◦ C, то s′ (t(B ◦ C)) = s′ (t(B) ◦ t(C)) = s′ (t(B)) ◦ s′ (t(C)) = = [инд. предп.] t(s(B)) ◦ t(s(C)) = t(s(B) ◦ s(C)) = t(s(B ◦ C)). Если A = ¬B, то s′ (t(¬B)) = s′ (¬t(B)) = ¬s′ (t(B)) = [инд. предп.] ¬t(s(B)) = t(¬s(B)) = t(s(¬B)). Если A = ϕi (B, C) (для краткости рассматриваем случай ar(ϕi ) = = 2), то s′ (t(ϕi (B, C))) = s′ (Di (t(B), t(C))) = Di (s′ (t(A)), s′ (t(B))) = [инд. предп.] Di (t(s(B)), t(s(C))) = t(ϕi (s(B), s(C))) = t(s(ϕi (B, C))). 2 Пусть L′ — ψ-логика. Определим прообраз этой логики относительно перевода t: t−1 (L′ ) ⇋ {A ∈ Fm(ϕ) | t(A) ∈ L′ }.

372

А. Д. Яшин ТЕОРЕМА 3.2. 1) L = t−1 (L′ ) — ϕ-логика. 2) Если L′ консервативна, то L консервативна. 3) Если L′ содержит схему замены эквивалентных, то это же вер-

но и для L. ДОКАЗАТЕЛЬСТВО. По определению перевода t для любой чистой формулы A имеем t(A) = A. Тогда Int ⊆ L и L консервативна. Пусть A, A → B ∈ L. Тогда t(A), t(A → B) ∈ L′ . По определению перевода имеем t(A) → t(B) ∈ L′ . По правилу modus ponens справедливо t(B) ∈ L′ , т. е. B ∈ L. Таким образом, L замкнуто относительно правила modus ponens. Пусть A ∈ L, а s : Fm(ϕ) −→ Fm(ϕ) — подстановка. Тогда t(A) ∈ L′ . Найдется подстановка s′ : Fm(ψ) −→ Fm(ψ) такая, что s′ (t(A)) = t(s(A)). При этом s′ (t(A)) ∈ L′ . Отсюда t(s(A)) ∈ L′ , т. е. s(A) ∈ L. Таким образом, L замкнуто относительно правила подстановки. Проверим замкнутость L относительно правила замены эквивалентных. Для краткости рассмотрим двухместную связку ϕi (·, ·). Пусть A ↔ ↔ A1 , B ↔ B1 ∈ L. Тогда t(A ↔ A1 ) = t(A) ↔ t(A1 ) ∈ L′ , t(B ↔ B1 ) = t(B) ↔ t(B1 ) ∈ L′ . По правилу замены эквивалентных в L′ верно Di (t(A), t(B)) ↔ ↔ Di (t(A1 ), t(B1 )) ∈ L′ . По свойствам перевода выполняется t(ϕi (A, B) ↔ ↔ ϕi (A1 , B1 )) ∈ L′ , поэтому ϕi (A, B) ↔ ϕi (A1 , B1 ) ∈ L. Пусть L′ содержит схему замены эквивалентных. Рассмотрим перевод аксиомы замены для ϕi (·, ·) t((p ↔ p1 ) ∧ (q ↔ q1 ) →. (ϕi (p, q) ↔ ϕi (p1 , q1 ))) = = (p ↔ p1 ) ∧ (q ↔ q1 ) →. (Di (p, q) ↔ Di (p1 , q1 ))) ∈ L′ , как частный случай схемы замены эквивалентных. Отсюда следует, что L содержит аксиому замены для ϕi . 2

Полные по Новикову логики: метод перевода

373

3.2. Сюръекивные переводы и полнота по Новикову. Основная цель данного раздела — выяснить, при каких условиях прообраз полной ψ-логики будет полной ϕ-логикой. Пусть L′ — ψ-логика. Обратным условием согласованности перевода t c подстановками (относительно L′ ) назовем следующее утверждение: для любых подстановки s′ : Fm(ψ) −→ Fm(ψ) и формулы A ∈ Fm(ϕ) найдется подстановка s : Fm(ϕ) −→ Fm(ϕ) такая, что s′ (t(A)) ↔ t(s(A)) ∈ ∈ L′ . ТЕОРЕМА 3.3. Пусть L′ — полная нормальная ψ-логика и перевод t удовлетворяет обратному условию согласованности с подстановками. Тогда L = t−1 (L′ ) — полная нормальная ϕ-логика. ДОКАЗАТЕЛЬСТВО. Пусть A ∈ Fm(ϕ) и A ∈ / L. Покажем, что A неприсоединима к L. Имеем t(A) ∈ / L′ . В силу полноты L′ формула t(A) неприсоединима к L′ . По теореме 1.4(б) найдутся чистая формула D ∈ / Int и подстановки s′1 ,. . . ,s′j на Fm(ψ) такие, что j ^

s′i (t(A)) →. D ∈ L′ .

i=1

По обратному условию согласованности найдутся подстановки s1 , . . . . . . , sj на Fm(ϕ) такие, что s′i (t(A)) ↔ t(si (A)) ∈ L′ , i = 1, . . . , j. По правилу замены эквивалентных в L′ имеем j ^

t(si (A)) →. D ∈ L′ .

i=1

По свойствам перевода t выполняется t

^ j

i=1

si (A) → .D



′

∈ L , т. е.

j ^

si (A) →. D ∈ L.

i=1

Поэтому A неприсоединима к L. 2 Итак, наличие полной ψ-логики L′ и перевода, удовлетворяющего обратному условию согласованности относительно L′ , дает возможность построить пример полной ϕ-логики.

374

А. Д. Яшин Скажем, что перевод t : Fm(ϕ) −→ Fm(ψ) сюръективен относитель-

но ψ-логики L′ , если для любой формулы A′ ∈ Fm(ψ) найдется формула A ∈ Fm(ϕ) такая, что t(A) ↔ A′ ∈ L′ . ТЕОРЕМА 3.4. Пусть t сюръективен относительно L′ . Тогда выполняется обратное условие согласованности t с подстановками относительно L′ . ДОКАЗАТЕЛЬСТВО. Рассмотрим подстановку s′ : Fm(ψ) −→ −→ Fm(ψ). Обозначим A′i ⇋ s′ (pi ) для каждой переменной pi . По условию найдутся формулы Ai ∈ Fm(ϕ) такие, что t(Ai ) ↔ A′i ∈ ∈ L′ . Определим подстановку s : Fm(ϕ) −→ Fm(ϕ) по правилу s(pi ) ⇋ Ai . Теперь индукцией по построению A ∈ Fm(ϕ) докажем t(s(A)) ↔ s′ (t(A)) ∈ ∈ L′ . L′

Если A = pi , то t(s(pi )) = t(Ai ) ↔ A′i = s′ (pi ) = s′ (t(pi )). L′

Если A = B ◦ C, то t(s(B ◦ C)) = t(s(B) ◦ s(C)) = t(s(B)) ◦ t(s(C)) ↔ L′

↔ [по индуктивному предположению и правилу замены эквивалентных] s′ (t(B)) ◦ s′ (t(C)) = s′ (t(B) ◦ t(C)) = s′ (t(B ◦ C)). Если A = ϕj (B, C) (для краткости рассматриваем двухместную L′

связку), то t(s(ϕj (B, C)) = t(ϕi (s(B), s(C))) = Dj (t(s(B)), t(s(C))) ↔ L′

↔ [по индуктивному предположение и правилу замены эквивалентных] Dj (s′ (t(B)), s′ (t(C))) = s′ (Dj (t(B), t(C))) = s′ (t(ϕj (B, C))). 2 Следующее предложение показывает, что для проверки сюръективности перевода t достаточно убедиться в справедливости т. н. условия накрытия дополнительных связок ψ-языка. ПРЕДЛОЖЕНИЕ 3.5. Пусть для каждой связки ψi найдется формула Ψi (p1 , . . . , pki ) ∈ Fm(ϕ) такая, что ψi (p1 , . . . , pki ) ↔ t(Ψi (p1 , . . . , pki )) ∈ L′ .

(∗)

Тогда перевод t сюръективен относительно L′ . ДОКАЗАТЕЛЬСТВО. Для каждой формулы A ∈ Fm(ψ) построим формулу A∗ ∈ Fm(ϕ) так, чтобы t(A∗ ) ↔ A ∈ L′ . Далее используем индукцию по A.

Полные по Новикову логики: метод перевода

375

Если A — переменная или стандартная константа, то положим A∗ ⇋ ⇋ A. Если A = B ◦ C (◦ — стандартная связка), то положим A∗ ⇋ B ∗ ◦ C ∗ , где B ∗ и C ∗ определены на предыдущем шаге. Аналогично для отрицания. Если A = ψi (B1 , B2 ) (для краткости рассматриваем двухместную связку ψi ), то положим A∗ ⇋ Ψi (B1∗ , B2∗ ), где B1∗ , B2∗ построены на предыдущих шагах. Рассмотрим подстановку s на Fm(ψ), удовлетворяющую условиям s(p1 ) ⇋ B1 и s(p2 ) ⇋ B2 . Имеем s(ψi (p1 , p2 )) ↔ s(t(Ψi (p1 , p2 ))) ∈ L′ как подстановочный пример (∗). Левая часть последней эквивалентности совпадает с A. Правая часть преобразуется в t(Ψi (B1 , B2 )), поскольку подстановка проносится сквозь все связки (как стандартные, так и дополнительные). 2 ЗАМЕЧАНИЕ. Вопрос о явных соотношениях в t−1 (L′ ) должен рассматриваться отдельно. § 4. Примеры применения метода перевода 4.1. Полное расширение логики Бессонова. Логика Бессонова Bes задается в языке с одной дополнительной одноместной связкой φ следующим образом [12]: стандартные схемы аксиом Int, (A → B) → (φ(A) → φ(B)), ¬¬φ(A), φ(1), φ(0) → (A ∨ ¬A), modus ponens как единственное правило вывода. Определим перевод t из φ-языка в язык с единственной дополнительной константой ϕ по правилу t(φ(p)) = ϕ ∨ p. Константа ϕ является переводом формулы φ(0), т. е. перевод сюръективен относительной любой ϕ-логики. Для отыскания полного по Но-

376

А. Д. Яшин

викову расширения логики Бессонова достаточно указать пример полной ϕ-логики, содержащей переводы специфических аксиом логики Bes. Пусть Sm+ — полное по Новикову расширение ϕ-логики Сметанича. Переводы аксиом Bes имеют вид (t(A) → t(B)) → ((t(A) ∨ ϕ) → (t(B) ∨ ϕ)), ¬¬(t(A) ∨ ϕ), 1 ∨ ϕ, (0 ∨ ϕ) → (t(A) ∨ ¬t(A)). Легко видеть, что все они принадлежат Sm и тем более Sm+ . Таким образом, t−1 (Sm+ ) является примером полного по Новикову расширения логики Бессонова (см. [13]). 4.2. Пример полной логики с несколькими независимыми одноместными связками. Пусть ψ = {ψ1 (·), . . . , ψn (·)} — набор одноместных связок, ϕ = {ϕ1 , . . . , ϕn } — набор из такого же числа констант. Определим перевод t : Fm(ψ) → Fm(ϕ) по правилу t(ψi (A)) = t(A) ∨ ϕi , i = 1, . . . , n. Здесь используется тот же прием, что и для логики Бессонова. Этот перевод сюръективен относительно любой ϕ-логики. Пусть L — произвольная полная по Новикову ϕ-логика. В силу основного результата ее прообраз L′ = t−1 (L) является полной по Новикову ψ-логикой. Покажем: если L не содержит явных соотношений, то аналогичное верно и для L′ . Пусть ψ1 (p) ↔ A(p, ψ2 , . . . , ψn ) ∈ L′ . Перевод этого явного соотношения имеет вид (p ∨ ϕ1 ) ↔ B(p, ϕ2 , . . . , ϕn ) (здесь важно только то, что B не содержит ϕ1 ). Подставляя в последнюю формулу 0 вместо p, получаем явное соотношение для ϕ1 в L: ϕ1 ↔ B(0, ϕ2 , . . . , ϕn ) ∈ L, приходим к противоречию.

Полные по Новикову логики: метод перевода

377

4.3. Пример полной логики с n-местной связкой. Пусть ψ — n-местная связка, ϕ — константа. Определим перевод t(ψ(A1 , . . . , An )) = t(A1 ) ∨ . . . ∨ t(An ) ∨ ϕ. Он сюръективен, т. к. ϕ является переводом формулы ψ(0, . . . , 0). По основному результату прообраз L′ = t−1 (L) любой полной ϕ-логики L является полной ψ-логикой. Покажем: если L не содержит явных соотношений, то это же верно и для L′ . Пусть, напротив, L′ содержит явное соотношение ψ(¯ p) ↔ ↔ A(¯ p). Здесь A — чистая формула. Перевод явного соотношения имеет вид (p1 ∨ . . . ∨ pn ∨ ϕ) ↔ A(p1 , . . . , pn ) (напомним, что перевод не затрагивает чистые формулы). Подставляя в последней формуле 0 вместо всех pi , получим явное соотношение для ϕ в L: ϕ ↔ A(0, . . . , 0) ∈ L, приходим к противоречию. Более того, все аргументы связки ψ в L′ являются существенными, а именно, L′ не содержит формул вида ψ(p1 , p2 , . . . , pn ) ↔ ψ(q, p2 , . . . , pn ), где q — новая переменная. В самом деле, допустим противное. Перевод этой формулы выглядит как (p1 ∨ p2 ∨ . . . ∨ pn ∨ ϕ) ↔ (q ∨ p2 ∨ . . . ∨ pn ∨ ϕ). Подставив 0 вместо всех pi и 1 вместо q, получаем явное соотношение ϕ ↔ 1 ∈ L, тем самым, приходим к противоречию. Наконец, покажем, что в L′ связка ψ является существенно nместной, т. е. L′ не содержит формул вида ψ(p1 , p2 , . . . , pn ) ↔ A(p2 , . . . . . . , pn ). Предположим обратное, т. е. ψ(p1 , p2 , . . . , pn ) ↔ A(p2 , . . . , pn ) ∈ L′ . Перевод этой формулы будет иметь вид (p1 ∨ p2 ∨ . . . ∨ pn ∨ ϕ) ↔ t(A(p2 , . . . , pn )) ∈ L. Подставим 1 вместо p1 . Правая часть не затрагивается этой подстановкой. Получаем 1 ↔ t(A(p2 , . . . , pn )) ∈ L, т. е. t(A(p2 , . . . , pn )) ∈ L. Следовательно, A(p2 , . . . , pn ) ∈ L′ , отсюда ψ(p1 , p2 , . . . , pn ) ↔ 1 ∈ L′ , что неверно.

378

А. Д. Яшин ЛИТЕРАТУРА 1. А. Г. Драгалин, Математический интуиционизм: введение в теорию доказательств, М., Наука, 1979. 2. Ю. Л. Ершов, Е. А. Палютин, Математическая логика, М., Наука, 1987. 3. С. К. Клини, Введение в метаматематику. М., Иностр. лит-ра, 1959. 4. А. Д. Яшин, О новой константе в интуиционистской логике высказываний, Фунд. прикл. матем., 5, N 3 (1999), 903—926. 5. M. Kaminski, Nonstandard connectives for intuitionistic propositional logic, Notre Dame J. Formal Logic, 29, N 3 (1988), 309—331. 6. Дж. Булос, Р. Джеффри, Вычислимость и логика, М., Мир, 1993. 7. A. D. Yashin, New intuitionistic logical constants and Novikov completeness, Stud. Log., 63, N 2 (1999), 151—180. 8. Я. С. Сметанич, О полноте исчисления высказываний с дополнительной операцией от одной переменной, Тр. Моск. матем. об-ва, 9 (1960), 357— 371. 9. Я. С. Сметанич, Об исчислениях высказываний с дополнительной операцией, Докл. АН СССР, 139, N 2 (1961), 309—312.

10. А. Д. Яшин, Логика Сметанича T Φ и два определения новой интуиционистской связки, Матем. заметки, 56, N 1 (1994), 135—142. 11. A. D. Yashin, The Smetanich logic has the unique Novikov complete extension, Proc. Logic Colloq.’94, Clermont-Ferrand, France (1994), 163. 12. А. В. Бессонов, О новых операциях в интуиционистском исчислении, Матем. заметки, 22, N 1 (1977), 23—28. 13. А. Д. Яшин, О полноте одной новой интуиционистской связки, Матем. заметки, 60, N 3 (1996), 423—433.

Поступило 17 января 2003 г. Адрес автора: ЯШИН Александр Данилович, факультет информационных технологий, МГППУ, ул. Сретенка, 29, г. Москва, 127051, РОССИЯ. e-mail: yashin− [email protected], [email protected]