Трёхзначная логика Я.Лукасевича и n-значная логика Э.Поста

Содержание:

Введение

Трёхзначная логика Я.Лукасевича и n-значная логика Э.Поста

Заключение

Список литературы

 

Введение

Многозначная логика - это совокупность логических систем, опирающихся на принцип многозначности, в соответствии с которым всякое высказывание имеет одно (и только одно) из трёх или более истинностных значений. Принцип многозначности, который лежит в основе многозначной логики, противопоставляется принципу двузначности, лежащему в основе классической логики, согласно которой всякое высказывание является либо истинным, либо ложным, то есть принимает одно из двух возможных истинностных значений - «истинно» и «ложно». Принцип многозначности утверждает, что высказывание имеет одно из n-значений истинности (например: «неопределённо», «возможно», «бессмысленно» и так далее), где и больше двух и может быть как конечным, так и бесконечным. В зависимости от множества истинностных значений различают конечнозначные и бесконечнозначные логики. Несмотря на то, что принцип двузначности отбрасывается, построение многозначной логики осуществляется по аналогии с классической двузначной логикой. Следует отметить, что ни двузначность, ни многозначность не являются прирождёнными свойствами человеческого мышления. Решение одних проблем может быть получено в рамках двузначной логики, рассуждение о других может оказаться более успешным, если опирается на тот или иной вариант многозначной логики.

Трёхзначная логика Я.Лукасевича и n-значная логика Э.Поста

Первыми логическими системами, опирающимися на принцип многозначности, были трёхзначная логика Я. Лукасевича и n-значная логика Э. Поста, в которой высказываниям приписывались значения из конечного множества натуральных чисел 1, 2, … n, где n больше единицы и конечно.

Лукасевичем была построена трёхзначная логика с целью опровержения логического фатализма.В этой логике явным образом указывается число истинностных значений, в данном случае 1 (истина),

½ (случайность) и 0 (ложь). Выделенным истинностным значением, как и в двузначной логике, является 1.

Исходными логическими связками у Лукасевича являются → (импликация) и ~ (отрицание). Как и в случае с двузначной логикой, даётся их табличное определение:

 

 

 

 

 

 

Посредством исходных связок определяются ν (дизъюнкция), ∧ (конъюнкция) и ≡ (эквиваленция):

• p ∨ q = (p → q) → q
• p ∧ q = ~ (~ p → ~ q)
• p ≡ q = (p → q) ∧ (q → p)

Значения p ∨ q и p ∧ q, как и в двузначной логике, есть max и min соответственно от значений p и q. Формула A является общезначимой , если при любом приписывании значений из множества {1,½, 0} переменным, входящим в A, формула A принимает значение 1.

Трёхзначная логика оказалась весьма необычной, например в ней не имеют места следующие законы двузначной логики:

• p ∨ ~ p — закон исключённого третьего
• ~ (p ∧ ~ p) — закон непротиворечия
• (p → (p → q)) → (p → q) — закон сокращения

С другой стороны, выразительные средства трёхзначной логики богаче классической, поскольку в ней уже можно выразить своеобразные модальные операторы ◊p (возможно, что p) и p (необходимо, что p):

◊p = ~ p → p и p = ~ ◊ ~ p

Понятно, что множество связок {~, ∧, ∨} недостаточно для определения. С другой стороны, добавление к {~, ∧, ∨} одного из модальных операторов позволяет определить →.

В 1931 году трёхзначная логика была аксиоматизирована учеником Лукасевича М. Вайсбергом:

• (p → q) → (q → r) → (p → r)
• p → (q → p)
• (~ p → ~ q) → (q → p)
• (p → ~ p) → p) → p

В общей теории многозначных логик основным способом задания является матричный. Система 〈M = M; D, ∨, ∧, ⊃, ¬〉 называется логической матрицей, где M — множество истинностных значений; D ⊃ M есть множество выделенных значений; ∨, ∧, ⊃ — это двуместные, а ¬ — это одноместные операции на M. Поскольку алгебра 〈A = M; ∨, ∧, ⊃, ¬〉 является однотипной алгеброй формул пропозиционального языка логики, то обычным образом определяется функция оценки ∨ (гомоморфизм) формул языка логики в матрице M. Формула A называется общезначимой в M, если при всех значениях переменных в множестве M значение A принадлежит D. Логическая матрица называется характеристической для исчисления высказываний логики, если общезначимы те и только те формулы, которые выводимы в логике. Множество всех общезначимых формул называется матричной многозначной логикой. Здесь возникают две проблемы:

Нахождение минимальной характеристической матрицы для логики.

Нахождение конечной аксиоматизации (если это возможно) по каждой конечной матрице M.

Примерами минимальных характеристических матриц могут служить матрицы для классической двузначной логики и трёхзначной логики Лукасевича . Ниже представлены примеры других n-значных логик (n ≥ 3).

При изучении многозначных логик понятие функции является основным и наряду с булевыми функциями (функциями двузначной логики) используется для описания дискретных устройств, компоненты которых могут находиться в некотором числе различных состояний. Произвольная функция f (x1, … xm) от любого конечного числа переменных, областью определения которых и областью значения самой функции является множество M (без ограничения общности можно считать, что его элементами являются 0, 1, 2, … n − 1), называется n-значной функцией, или функцией n-значной логики. Имеются различные способы задания функций. Например, функция f (x1, … xm) может быть задана таблицей, где в некотором порядке перечислены все n-ичные наборы длины m (из элементов 0, 1, 2, … n − 1) и на каждом из них указано значение функции, как это делалось в двузначной логике. Число n-ичных наборов длины m равно nm и на каждом из них значение функции можно задать n способами. Поэтому число всех функций n-значной логики Pn, зависящих от аргументов x1, … xm, составляет nnm.

Как и в двузначном случае, в Ρn выделяются функции, которые наиболее часто употребляются в логике и кибернетике и играют там важную роль. Такие функции называются элементарными. Вот некоторые из них: константы 0, 1, 2, … n − 1 — это нульместные функции; отрицание Лукасевича: ~ x = (n − 1) − x — это обобщение отрицания в смысле «зеркального отрицания»; отрицание Поста: ¬ x = x + 1 (mod n) — это обобщение отрицания в смысле «циклического сдвига значений»; характеристическая функция числа 1, 1 = 0, 1, … n − 1:

 

 

Ji(x) - это обобщение некоторых свойств отрицания; минимум x и y: x ∧ y = min (x, y) - это обобщение конъюнкции; максимум x и y: x ν y = max (x, y) - это обобщение дизъюнкции; сумма по модулю n: x ⊕ y = x + y (mod n) -это обобщение суммы по mod 2 (значение этой функции равно остатку от деления суммы x + y на n); импликация Лукасевича:

 

x → y - это обобщение одного из свойств классической импликации; функция Вебба: Wn (x, y) = max (x, y) + 1 (mod n) - это обобщение штриха Шеффера на функционально полную логику Поста Ρn.

Операция дизъюнкции x ∨ y и отрицание Поста ¬ x, определённые на множестве M, являются исходными операциями первой n-значной логикой (n ≥ 3), названной Pn, которая была построена Постом в 1921 году, притом с произвольным числом выделенных значений. В свою очередь, n-значная логика Лукасевича  была построена в 1922–1923 годах как обобщение трёхзначной логики.

Кроме двух рассмотренных способов задания функций (табличного и алгоритмического (в последнем случае x ∨ y, к примеру, задается как max (x, y) не менее известным способом является формула, описывающая функцию как суперпозицию исходных элементарных функций. Функция, полученная из функций f1, … fk подстановкой и/или переименованием аргументов, называется суперпозицией f1, … fk. Выражение, описывающее эту суперпозицию и содержащее функциональные знаки и символы аргументов, называется формулой, и тогда говорят, что формула реализует или представляет данную функцию. В этом случае имеем дело с формульной моделью многозначной логики, а сама модель зачастую отождествляется с этой логикой. Основной проблемой здесь является проблема интерпретации истинностных значений. Для широкого класса многозначных логик эта проблема решена А. С. Карпенко (1983) в терминах классических истинностных значений.

В кибернетике такие модели рассматриваются как управляющие системы. Элементарные функции при этом являются элементами, производящими определённые операции, а формулы интерпретируются как схемы, построенные из элементов и осуществляющие переработку входной информации в выходную. Характерными для формульной модели являются: задача об указании всех формул, реализующих заданную константу; задача об эквивалентных преобразованиях; задача о сложности реализации; задача о минимизации и так далее. Однако в зависимости от того, какие цели преследуются при изучении многозначных логик, по-разному понимается, что собой представляет её модель. Для многих специалистов, связанных с вычислительной техникой, инженеров, прикладных математиков и физиков гораздо большее значение имеет представление модели многозначной логики в виде функциональной системы, обозначаемой (Pn, C), где Pn есть множество всех функций n-значной логики (или множество всех функций счётнозначной логики Ρω) с заданной на нём операцией суперпозиции C, а сама функциональная система (Pn, C) зачастую отождествляется с многозначной логикой, то есть (Pn, C) выступает в качестве модели многозначной логики. Эта модель, в отличие от рассмотренных выше алгебр истинностных значений, является алгеброй функций.

Известна содержательная трактовка понятия функциональной системы ((Pn, C) выступает её частным случаем), в основе которой лежит рассмотрение таких пар (Ρ, Ω), в которых Ρ есть множество отображений, реализуемых управляющими системами из некоторого класса, а Ω состоит из операции, используемой при построении новых управляющих систем из заданных. В данном случае Ω представляет собой операцию суперпозиции C.

Наиболее трудной проблемой при изучении функциональных систем является следующая: какие функции могут быть сконструированы из данного множества функций. Проблема эта возникает и в самом пропозициональном исчислении, представленном формульной моделью, и в синтезе автоматов, и в универсальной алгебре; но именно здесь ей уделяется специальное внимание. Наиболее важное свойство функциональной системы есть свойство функциональной полноты (например, для того, чтобы можно было реализовать любую переключательную схему). Система функций R = {f1, … fk, …} из Pn называется функционально полной, если любая функция из Pn представима посредством суперпозиций функций из системы R. Таким образом, указанная выше проблема приобретает здесь следующий вид: является ли некоторое множество R функционально полным? Например, логика Поста Pn, как и классическая двузначная логика, является функционально полной. Отсюда их исключительно широкое применение и развитие.

С понятием полноты связано понятие операции замыкания и замкнутого класса. Пусть R ⊆ Pn. Множество всех функций, которые могут быть получены из функций системы R с помощью операции суперпозиции, называется замыканием R и обозначается [R]. Класс функций R называется (функционально) замкнутым, если [R] = R, то есть замкнутость класса функций R обозначает собой сохранение при суперпозиции «наследственных» свойств этих функций. В терминах замыкания можно дать другое определение полноты, эквивалентное исходному: R - полная система, если [R] = Pn.

Сложной технической проблемой для n-значных логик остаётся распознавание полноты для произвольных систем. Выделяются два подхода к решению задачи о полноте. В первом случае ставится вопрос о существовании алгоритма, устанавливающего полноту или неполноту системы функций; во втором рассматривается совокупность всех предполных классов функций в Pn. Система R функций называется предполной в Pn, если R представляет не полную систему, но добавление к R любой функции f такой, что f ∊ Pn и f ∉ R преобразует R в полную систему. Или, в терминах замыкания: R предполна в Pn, если [R] ≠ Pn и [R ∪ {f}] = Pn, где f ∊ Pn и f ∉ R. Важная роль предполных классов функций видна из следующей теоремы, которая формулирует критерий функциональной полноты: система функций R n-значной логики полна тогда и только тогда, когда она не содержится целиком ни в одном предполном классе. Г. Розенбергом в 1970 году было дано описание всех предполных классов в n-значной логике, и хотя число предполных классов π (n) конечно для любого n, однако очень быстрый их рост указывает на малую практическую эффективность предполных классов для решения проблемы полноты.

Удивительную связь свойста функциональной предполноты с теорией простых чисел имеет многозначная логика Лукасевича. Как было установлено В. К. Финном в 1970 году, n - 1 является простым числом тогда и только тогда, когда в многозначной логике предполно в Pn. Таким образом, мы имеем новое определение простого числа. Более того, оказалось возможным построить такие варианты, которые имеют класс общезначимых формул тогда и только тогда, когда n - 1 есть простое число. Последние результаты привели А. С. Карпенко к открытию закона порождения классов простых чисел, притом порождаются все простые числа.

К проблеме полноты примыкает задача о базисах, состоящая в указании всех полных в замкнутом классе R ⊆ Pn подмножеств, никакое собственное подмножество которых уже не полно в R, то есть базисом является минимальная полная независимая система функций, удаление из которой любой функции делает систему неполной. Особую роль играют базисы, состоящие из одной функции, то есть штрихи Шеффера.

Однако наиболее сложной глобальной задачей для многозначной логики остаётся описание решётки замкнутых классов данной модели многозначной логики. Для двузначной логики эта задача полностью решена Э. Постом в начале 1920-х годов, где установлено, что мощность множества замкнутых классов в P2 счётна. Позже им дано полное описание решётки замкнутых классов, каждый класс строится эффективно, и показано, что каждый замкнутый класс имеет конечный базис. Эти классы названы классами Поста. Однако с многозначной логикой дело обстоит совсем по-другому. Оказалось, что имеются существенные различия между классической двузначной логикой и многозначной, говорящие о принципиальной несводимости второй к первой. В отличие от P2 для всякого n ≥ 3 существует в Pn замкнутый класс, не имеющий базиса, а также для всякого n ≥ 3 существует в Pn замкнутый класс со счётным базисом. Непосредственно к этому примыкает следующий результат: для всякого n ≥ 3 Pn содержит континуум различных замкнутых классов, то есть уже P3 содержит континуум различных замкнутых классов. Следует отметить, что точная природа такого различия между двузначной и трёхзначной логиками пока неясна.

Особый интерес в силу их различных приложений представляют собой бесконечнозначные логики. Исторически первой такой логикой была бесконечнозначная логика Лукасевича(1929), которая определяется следующей матрицей:

M = 〈[0, 1]; →, ~, {1}〉, где x → y = min (1, 1 − x + y), ~ x = 1 − x.

Почти через тридцать лет бесконечнозначная логика была аксиоматизирована следующим образом: аксиома (p → q) → q) → (q → p) → p). Последние десятилетия алгебраические исследования бесконечнозначной логики приобрели исключительный масштаб, который позволяет говорить о новом направлении в алгебраической логике.