Проблема функциональной полноты в теории пропозициональных связок как функций истинности

Ознакомившись с табличным определением «классических» пропозициональных связок и законами взаимовыразимости связок, многие задаются следующими вопросами. Какие все-таки пропозициональные связки следует использовать при построении логики высказываний и почему? Все возможные? Только те, для которых есть аналог среди союзов естественного языка? Только некоторые двухместные и отрицание? Существуют ли многоместные пропозициональные связки? Что лежит в основании выбора нами того или иного набора связок?

Приведем сводную таблицу (табл. 3.7) для некоторых двухместных связок (для удобства приведем только их знаки) — уже известных нам, а также обратной импликации с и обратной антиимпликации с?.

Таблица 3.7

Сводная таблица двухместных связок

А

В

&

V

V

D

=

1

л

с

и

и

и

и

л

и

и

л

л

и

л

и

л

л

и

и

л

л

и

TI

и

л

л

и

л

и

и

и

л

и

л

л

и

л

л

л

л

л

и

и

и

и

и

л

При взгляде на эту таблицу возникает вопрос: сколько вообще существует различных двухместных функций истинности? Иными словами, сколькими различными способами можно отобразить множество {ИИ, ИЛ, ЛИ, ЛЛ} на множество {ИЛ}? Говоря проще, сколькими способами можно задать значения четырех аргументов (ИИ, ИЛ, ЛИ, ЛЛ) — т.е. четверки таких значений с точностью до порядка, если каждому такому аргументу может быть приписано одно из двух значений (И, Л)? Ответ очевиден — 16. Столько же, сколько существует строк в таблице истинности для 4 аргументов. Значения наших функций (четверки типа ИЛЛЛ для конъюнкции, ИЛИИ для импликации, ЛЛЛИ для функции Нико и т.д.) — это де-факто те самые «комбинации значений переменных», о которых мы сможем говорить, если повернем таблицу на 90° по часовой стрелке — так, что в качестве аналогов переменных будут выступать пары значений Aw В.

В таблице приведены 9 из 16 таких функций. 6 из 7 оставшихся функций представляют собой вырожденные случаи двухместных операций. Так, функция с распределением значений ИИЛЛ только по видимости является двухместной, на самом же деле ее значения в точности совпадают со значениями А (аналогично для функции ИЛ ИЛ — только относительно В). Функция ЛЛИИ — на самом деле обычное одноместное отрицание (-1Л), так же как и функция ЛИЛИ (-лВ). Функция ИИИИ — нульместная, называемая константой истинности (Т) — так же как функция ЛЛЛЛ - константа ложности (1). И остается только один содержательный случай. Внимательные читатели уже догадались, что речь идет об антиимпликации, функции с распределением значений ЛИЛЛ. Она может быть выражена формулой —1 з В). И поясним, что обратная импликация эквивалентна формуле В з А, обратная антиимпликация — формуле -i(Sd А).

Поскольку пропозициональные связки — не что иное, как функции истинности, нетрудно понять, что можно вести речь о трех-, четырех- и т.д. местных функциях. Так, трехместная конъюнкция — это функция истинности, принимающая значение «истина» в одном и только в одном случае — когда все три аргумента истинны. Во всех остальных семи случаях она ложна. Очевидно, что число трехместных функций истинности в КЛВ уже значительно больше — их 256. Вообще число различных функций произвольной местности в логике с произвольным числом значений можно посчитать по формуле где Nf» — количество различных я-местных функций истинности, т — число возможных значений (для КЛВ — два, для системы Лукасевича — три и т.д.), п — число переменных (аргументов функции).

Так, в трехзначной логике одних только двухместных функций будет З9, т.е. 19 683!

Но практических сложностей с использованием многоместных функций на самом деле в логике нет. Оказывается, что все функции с местностью больше двух можно выразить формулами, включающими только двухместные связки и отрицание (их комбинацию, называемую суперпозицией). Например, трехместную конъюнкцию &3 (Л, В, С) можно эквивалентным образом записать как ((Л & В) & Q. Существует специальная теорема, доказывающая подобную универсальную выразимость многоместных связок. Более того, существуют совершенно определенные наборы связок, с помощью которых можно выразить все возможные связки вообще. Такие наборы называются функционально полными наборами связок. Поэтому в выборе используемого набора главное — убедиться, чтобы он был функционально полным.

Вышеупомянутая теорема называется теоремой о функциональной полноте набора связок КДО (конъюнкция, дизъюнкция, отрицание) и содержит удивительный результат — вообще любую функцию можно представить формулой, в которой будут использоваться максимум только эти три знака &, v, Остальные знаки можно ввести по определению (см. выше законы взаимовыразимости связок). Более того, из этих законов вытекает, что набор КДО можно сократить до набора КО или ДО (по законам де Моргана) или взять набор ИО (импликация, отрицание — с опорой на законы выразимости коныонкции/дизыонкции через импликацию — № 2, № 4 или № 5 в нашем списке). Однако это не очень удобно с практической точки зрения. Выражения приобретают слишком громоздкий вид. Поэтому набор КДО не сокращают, а расширяют, добавляя такие связки, как импликация, эквиваленция, строгая дизъюнкция, возможно, также функции Шеффера и Нико. Указанные связки имеют, кроме того, аналоги, часто употребляемые в естественном языке. Впрочем, мы уже об этом говорили.

Но если стремиться к минимизации любой ценой (а также к удовлетворению чисто теоретического интереса относительно существования минимального функционально полного набора), то достаточно взять одну- единственную связку — штрих Шеффера или штрих Нико, чтобы получить функционально полную систему! Через эти связки выразимы все связки набора КДО. Убедитесь в этом сами, построив соответствующие таблицы истинности:

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

  • 1. {&, v, -i} — канонический набор КДО
  • 2.
  • 3. {v, з, —1}
  • 4. {-,,3}
  • 5. Ь, &}
  • 6. b,v}
  • 7. {1}
  • 8. {1}
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >