§ 7. Полные системы логических знаков

С помощью правила замены мы можем преобразовать формулу таким образом, чтобы она не содержала некоторого логического знака. Например, если дана формула

(p  q)  (r  s),

то, применив к ее подформуле (р  q) правило замены по равносильности (13), получим формулу

(~р  q)  (r  s),

которая равносильна данной, но уже не содержит знака .

Так как формулы имеют конечную длину, то каждый из логических знаков может входить в них лишь конечное число раз. Поэтому конечным числом применений правила замены с помощью равносильностей (13), (16) и (17) любую формулу можно преобразовать таким образом, чтобы она не содержала логических знаков, отличных от ~,  и . Из полученной формулы также в конечное число шагов с помощью равносильности (14) можно получить формулу, не содержащую знаков, отличных от ~ и , а затем из нее с помощью равносильности (15) можно получить формулу, не содержащую знаков, отличных от ~ и . Наконец, из этой формулы с помощью равносильности (12) можно получить формулу, не содержащую знаков, отличных от ~ и .

Рассмотрим в качестве примера преобразование формулы

(p  q)  (q  r) (a)

в формулу, которая равносильна ей, но не содержит знаков, отличных от ~ и . Применяя к подформуле (р  q) формулы (а) правило замены по равносильности (16), получаем формулу

((~р  q)  (~q  p))  (q  r). (б)

Затем к подформуле (q  r) формулы (б) применяем правило замены по равносильности (13) и получаем формулу

((~р  q)  (~q  p))  (~q  r). (в)

Теперь к подформулам (~р  q), (~q  р) и (~q  r) формулы (в) применяем правило замены по равносильности (15) и получаем формулу

(~(~~р  ~q)  ~(~~q  ~р))  ~(~~q  ~r). (г)

Формула (г), согласно той же равносильности (15), может быть заменена формулой

~(~(~(~~р  ~q)  ~(~~q  ~р))  ~~(~~q  ~r), (д)

которая равносильна (а) и не содержит знаков, отличных от ~ и . Применив к формуле (д) четыре раза правило замены по равносильности (1), мы можем получить более простую формулу

~(~(~(р  ~q)  ~(q  ~р))  (q  ~r)). (е)

Однако не любой набор логических знаков позволяет выразить через него все остальные. Не любую формулу, например, можно преобразовать в равносильную ей и содержащую одни лишь знаки ~ и  или одни лишь знаки  и , или одни лишь знаки ,  и .

Так, с помощью ~ и  нельзя построить формулу, равносильную формуле p  q, а с помощью ,  и  — формулу, равносильную формуле ~р.

В языке логики высказывании имеется, как мы знаем, шесть логических союзов, из которых один — знак отрицания ~ — унарный, т. е. относящийся к одной формуле, и пять — , , , ,  — бинарные, т. е. относящиеся к двум формулам. Возникает вопрос, существуют ли еще какие-нибудь логические союзы, смысл которых может быть уточнен с помощью таблиц, заполненных логическими значениями «истина» и «ложь»? Исходя из общих соображений относительно семантики логических знаков, можно предположить существование следующих четырех унарных логических союзов:

А	—1A	—2А	—3А	—4А
и	и	и	л	л
л	и	л	и	л

Но знаки —₁ и —₄ не используются в качестве логических союзов, так как логические значения выражений —₁A и —₄А в заключительном столбце, таблицы не зависят от значений во входном, а логические значения выражения —₂A в заключительном столбце лишь повторяют значения во входном. И только знак —₃ есть знак отрицания ~.

Из тех же общих соображений относительно семантики логических знаков можно предположить существование следующих шестнадцати бинарных логических союзов:

А

B

А 1B

А 2B

А 3B

А 4B

А 5B

А 6B

А 7B

А 8B

А 9B

А 10B

А 11B

А 12B

А 13B

А 14B

А 15B

А 16B

и

и

и

и

и

и

л

и

и

л

л

л

и

и

л

л

л

л

л

и

и

и

и

л

и

и

л

л

и

и

л

л

и

л

л

л

и

л

и

и

л

и

и

л

л

и

л

и

и

л

л

и

л

л

л

л

и

л

и

и

и

л

и

и

и

л

л

л

л

л

и

л

Знаки ₁ и ₁₆ не используются в качестве логических союзов, так как логические значения выражений A₁B и A₁₆B не зависят от значений А и В во входных столбцах, знаки ₆ и ₁₁ не используются в качестве логических постоянных, так как выражения A₆B и A₁₁B не зависят соответственно от А и В и равносильны В и А; знаки ₈ и ₉ не используются в качестве логических союзов, так как выражения A₈B и A₉B не зависят соответственно от А и В и равносильны ~В и ~А. Остальные десять бинарных логических знаков используются в качестве логических союзов. Знаки _2, _3, _7, ₁₀ и ₁₂ суть логические знаки , , ,  и  нашего языка. Знаки _4, _5, _8, _13, и ₁₅ используются в качестве логических союзов, но их нет в нашем языке. Они называются соответственно знаками обратной импликации (обознач. ), антиконъюнкции (обознач. ), обратной антиимпликации (обознач. ), антиимпликации (обознач. ) и антидизъюнкции (обознач. ). Если ввести эти знаки в алфавит языка и добавить соответствующие пункты к определению формулы, то формулы (А  В), (А  В), (А  В), (А  В) и (А  В) будут читаться соответственно: А, если В; А несовместно с В; не А, но В; А, но не В и ни А, ни В.

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

А  В равносильно ~В  А; (35)

А  В равносильно ~А  ~В; (36)

А  В равносильно ~(~В  А); (37)

А  В равносильно ~(~А  В); (38)

А  В равносильно ~(А  В); (39)

~ А равносильно A  А; (40)

А  В равносильно (А  A)  (В  В). (41)

Равносильности (13), (16), (17), (14) и (35) — (39) свидетельствуют о том, что из любой формулы языка, расширенной знаками , , ,  и , конечным числом применений правила замены можно получить формулу, не содержащую знаков, отличных от знаков ~ и . Но так как равносильности (40) и (41) позволяют ~ и  выразить через антиконъюнкцию , то ясно, что любая формула логического языка, содержащего отрицание и все десять бинарных логических знаков, может быть преобразована в равносильную ей формулу, которая не содержит логических знаков, отличных от .

Наряду с унарными и бинарными логическими знаками можно вводить логические знаки для различных тернарных и вообще n-арных логических союзов. Из общего числа 256 возможных таблиц для тернарных логических союзов лишь с некоторыми связывают логический знак. Используют, например, тернарный логический союз, который называется условной дизъюнкцией, обозначается знаком  и характеризуется следующей таблицей:

А	B	С	 A B C
и	и	и	и
л	и	и	л
и	л	и	и
л	л	и	и
и	и	л	и
л	и	л	л
и	л	л	л
л	л	л	л

Имеет место равносильность:



А В С равносильно (А  ~В)  (В  С), (42)

согласно которой условная дизъюнкция выразима через конъюнкцию, дизъюнкцию и отрицание.

Можно показать, что из какого бы набора унарных, бинарных, тернарных, ..., n-арных логических знаков не была построена формула А, существует формула В, которая равносильна А и не содержит знаков, отличных от ~,  и .

Так как каждому набору логических значений пропозициональных переменных E₁, Е₂, ..., E_n в таблице формулы А однозначно соответствует логическое значение, зафиксированное в заключительном столбце, то говорят, что формула А определяет логическую функцию F (E₁, Е₂, ..., E_n). Эта функция может быть задана таблицей, которая получается из таблицы формулы А вычеркиванием всех столбцов, кроме входных и заключительного. F (E₁, Е₂, ..., E_n) — двузначная функция, так как пропозициональные переменные и сама функция принимают только два значения :«истина» и «ложь».

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

p  (q  r)

определяет логическую функцию F(p, q, r), которая может быть задана также следующей таблицей с перечнем пропозициональных переменных р, q, r:

p	q	r	F(p, q, r)
и	и	и	и
л	и	и	и
и	л	и	л
л	л	и	и
и	и	л	л
л	и	л	и
и	л	л	и
л	л	л	и

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

Теорема. Любая логическая функция определяется формулой, содержащей только знаки ~,  и .

Доказательство. Пусть F (E₁, Е₂, ..., E_n) — функция, заданная таблицей Т. В каждой строке Т зафиксирован набор логических значений пропозициональных переменных E₁, Е₂, ..., E_n и соответствующее ему логическое значение F (E₁, Е₂, ..., E_n). Занумеруем строки таблицы Т сверху вниз числами 1, 2,…, 2ⁿ.

Пусть формула В_i где i  2ⁿ, есть конъюнкция

Сⁱ₁  Сⁱ₂  ...  Сⁱ_n,

причем Сⁱ_j, где (j  n), есть Е_j, если в 1-й строке Т Е_j имеет логическое значение «истина», и Сⁱ_j есть ~Е_j, если в 1-й строке Т Е_j имеет логическое значение «ложь». Пусть, далее, формула D есть дизъюнкция всех таких В_i, которые в i-й строке заключительного столбца таблицы Т имеют логическое значение «истина».

Если таких строк в Т нет и в заключительном столбце все строки имеют логическое значение «ложь», то функцию F (E₁, Е₂, ..., E_n), заданную Т, определяет формула E_i  ~E_i. Действительно, в заключительном столбце построенной по формуле E_i  ~E_i таблицы с перечнем пропозициональных переменных E₁, Е₂, ..., E_n, все строки имеют логическое значение «ложь».

Если же такие строки в Т есть, то заданную таблицей Т функцию F (E₁, Е₂, ..., E_n) определяет формула D. Действительно, пусть имеется какой-нибудь набор логических значений переменных E₁, Е₂, ..., E_n и пусть в Т подобный набор логических значений переменных представлен в k-й строке. При данном наборе B_k имеет логическое значение «истина», тогда как все остальные В, имеют при этом наборе логическое значение «ложь». Если для k-й строки Т имеет в заключительном столбце логическое значение «истина», то В_k является дизъюнктом D и, следовательно, при этом наборе D тоже имеет значение «истина». Если для k-й строки Т имеет в заключительном столбце значение «ложь», то В_k не является дизъюнктом D и для рассматриваемого набора логических значений все дизъюнкты D принимают значение «ложь», а следовательно, и вся формула D принимает значение «ложь». Таким образом, формула D определяет функцию F (E₁, Е₂, ... E_n).

Пусть, например, дана таблица функции F(p, q, r).

р	q	r	F(р, q, r)
и	и	и	л
л	и	и	и
и	л	и	и
л	л	и	л
и	и	л	л
л	и	л	и
и	л	л	л
л	л	л	и

Эта функция определяется формулой

(~p  q  r)  (p  ~q  r)  (~р  q  ~r)  (~р  ~q  ~r).

Из теоремы, в частности, следует, что какова бы ни была формула А и ее таблица Т с перечнем пропозициональных переменных E₁, Е₂, ..., E_n, можно построить формулу, равносильную А, но не содержащую других логических знаков, кроме ~,  и .

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

Аналогичным образом полную систему логических знаков образуют пары ~ и , ~ и ,  и . Равносильности же (36) и (37) свидетельствуют о том, что знака  достаточно для построения формулы, определяющей любую логическую функцию.

Упражнения

I. Из формулы (p  q)  r

путем равносильных замен получить формулу:

1) не содержащую логических знаков, отличных от ~ и ;

2) не содержащую логических знаков, отличных от ~ и ;

3) не содержащую логических знаков, отличных от ~ в .

II. Найти формулу D, которая содержит только логические знаки ~,  и  и определяет следующую функцию:

p	q	r	F(p, q, r)
и	и	и	и
л	и	и	и
и	л	и	л
л	л	и	л
и	и	л	и
л	и	л	л
и	л	л	л
л	л	л	и

III. Показать, что знака  достаточно для построения формулы, определяющей произвольную логическую функцию.

IV. Найти равносильности, которые свидетельствуют о том, что  и  образуют полную систему логических знаков (выразить через них ~ и ).