Практическая логика.

Полные системы логических операций

Возможность вывести любую тавтологию в чрезвычайно простом исчислении Гильберта всего с двумя операциями ¬ и Ъ наводит на вопрос, достаточно ли широко наше понятие пропозициональной формулы, чтобы охватывать все способы образования высказываний? Нет ли каких-нибудь новых логических операций, которые нельзя было бы выразить через ¬ и Ъ, и использование которых сильно расширило бы возможности нашего формального логического языка? Покажем, что таких операций нет.

Каждая мыслимая логическая операция над n высказываниями определяется соответствующей функцией f(A₁,А₂,...,A_n) от n логических переменных, принимающей значения И или Л для каждого набора значений своих аргументов. Такая функция называется логической и задаётся таблицей

Поскольку столбец значений f(А₁, А₂, ..., А_n) содержит 2ⁿ букв И или Л, всего возможных логических функций от n переменных будет . Так, число 2-местных логических функций (n = 2) равно 16, а мы использовали только 4. 3-местных функций уже 256. Ответ на наш вопрос даёт следующая теорема.

Теорема (об определении логических функций).

Любая n-местная (n>0) логическая функция определяется некоторой пропозициональной формулой, содержащей только операции  ¬и Ъ.

Доказательство.  Возможны два случая.
1) Функция f(А₁, А₂, ..., А_n) тожественно ложна, т.е. в правом столбце определяющей её таблицы стоят только значения Л. Такая такая функция определяется тождественно ложной формулой

¬(А₁Ъ¬А₁ЪА₂Ъ¬А₂Ъ ... ЪА_nЪ¬А_n).

2) Функция f(А₁, А₂, ..., А_n) принимает значения И при некоторых или при всех наборах значений аргументов. Рассмотрим строки её таблицы, в которых значение f равно И. Для каждой такой строки с номером i определим формулу j_i как конъюнкцию переменных или их отрицаний: если А_j имеет значение И, то в j_i включается А_j, а если А_j имеет значение Л, то в j_i включается ¬А_j. Например, для функции с таблицей

формула j_i будет иметь вид А₁Щ ¬А₂Щ ¬А₃ЩА₄. Так построенная формула j_i будет истинна только при тех значениях переменных, которые они принимают в i-той строке таблицы. Следовательно, дизъюнкция j всех построенных формул j_i (напомним, что i - это номер строки, в которой функция f имеет значение И) истинна только в тех строках, в которых истинна и f. Остаётся лишь заменить в формуле j конъюнкцию на дизъюнкцию по закону (АЩВ)«¬(¬АЪ¬В).

Пример. Для операции "исключающая дизъюнкция" A Е B построение определяющей формулы, описанное в доказательстве теоремы, имеет вид

Эта таблица даёт определяющую формулу j как дизъюнкцию j₂Ъj₃, т.е. АЩ¬ВЪ¬АЩВ. Заменяя Щ на Ъ, получим j в виде ¬(¬АЪ¬¬В)Ъ¬(¬¬АЪ¬В), или после упрощения по закону двойного отрицания

 ¬(¬АЪВ)Ъ¬(АЪ¬В).

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

Следствие. Любой набор логических функций, содержащий операции ¬ и Ъ или ¬ и Щ, образует полную систему логических операций. В частности, системы операций {¬, Ъ}, {¬, Щ} и {¬, Ъ, Щ} являются полными.

Существуют полные наборы операций, содержащие всего по одной операции. Это системы {Ї} и {­}, где операции Ї и ­ определяются формулами:

Это следует из тавтологичности формул 

¬А«АЇА,  АЪВ« ¬(АЇВ), 
¬А«А­А,  АЩВ« ¬(А­В), 

а также из полноты систем операций {¬, Ъ}и {¬, Щ}.