Многозначная двузначная логика

Размещено на http://www.allbest.ru/

Тема: Многозначная двузначная логика

План

Логики многозначные

Двузначная логика

Список использованной литературы

Логики многозначные

логика многозначный формальный философ

Многозначная логика -- тип формальной логики, в которой допускается более двух истинностных значений для высказываний. Первую систему многозначной логики предложил польский философ Ян Лукасевич в 1920 году. В настоящее время существует очень много других систем многозначной логики, которые в свою очередь могут быть сгруппированы по классам. Важнейшими из таких классов являются частичные логики и нечёткие.

Может показаться, что теория вероятностей очень похожа на бесконечнозначную логику: вероятность соответствует истинностному значению (1=истина, 0=ложь), вероятность не наступления какого-либо события соответствует отрицанию, вероятность одновременного наступления двух событий соответствует конъюнкции, а вероятность наступления хотя бы одного из двух событий соответствует дизъюнкции.

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

Это проявляется, в частности, в том, что в теории вероятностей выполняется эквивалент «закона исключённого третьего»: вероятность того, что {некоторое событие наступит или не наступит}, всегда равна единице, в то время как в многозначных логиках закон исключённого третьего не выполняется.

В теории вероятностей выполняется также эквивалент «закона противоречия»: вероятность того, что {некоторое событие одновременно наступит и не наступит}, всегда равна 0, в то время как в многозначных логиках закон противоречия не выполняется.

В то же время существует некоторая связь между истинностными значениями вышеописанной бесконечнозначной логики и вероятностями теории вероятностей, а именно:

· если a -- вероятность некоторого события, то вероятность ненаступления этого события составляет 1?a;

· если a и b -- вероятности некоторых двух событий, то вероятность совместного наступления этих двух событий не превышает min(a,b);

· если a и b -- вероятности некоторых двух событий, то вероятность наступления хотя бы одного из этих двух событий больше или равна max(a, b).

Двузначная логика

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

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

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

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

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

· p ? q = (p > q) > q

· p ? q = ~ (~ p > ~ q)

· p ? q = (p > q) ? (q > p)

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

Логика Ј₃ оказалась весьма необычной, например в ней не имеют места следующие законы C₂:

· p ? ~ p -- закон исключённого третьего

· ~ (p ? ~ p) -- закон непротиворечия

· (p > (p > q)) > (p > q) -- закон сокращения

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

?p = ~ p > p и p = ~ ? ~ p

что и было сделано А. Тарским в 1921 году.

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

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

1. (p > q) > (q > r) > (p > r)

2. p > (q > p)

3. (~ p > ~ q) > (q > p)

4. (p > ~ p) > p) > p

Правила вывода: modus ponens и подстановка.

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

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

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

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

При изучении многозначных логик понятие функции является основным и наряду с булевыми функциями (функциями двузначной логики) используется для описания дискретных устройств, компоненты которых могут находиться в некотором числе различных состояний. Произвольная функция f (x₁, … x_m) от любого конечного числа переменных, областью определения которых и областью значения самой функции является множество M (без ограничения общности можно считать, что его элементами являются 0, 1, 2, … n ? 1), называется n-значной функцией, или функциейn-значной логики. Имеются различные способы задания функций. Например, функция f (x₁, … x_m) может быть задана таблицей, где в некотором порядке перечислены все n-ичные наборы длины m(из элементов 0, 1, 2, … n ? 1) и на каждом из них указано значение функции, как это делалось в двузначной логике. Число n-ичных наборов длины m равно n^m и на каждом из них значение функции можно задать n способами. Поэтому число всех функций n-значной логики P_n, зависящих от аргументовx₁, … x_m, составляет_nn^m. Случай n > 2 оказывается существенно более сложным, чем классический случай P₂. Уже в P₃ число функций от двух переменных равно 19 683, в то время как в P₂ таких функций всего 16.

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

J_i(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 -- это обобщение одного из свойств классической импликации; функция Вебба: W_n (x, y) = max (x, y) + 1 (mod n) -- это обобщение штриха Шеффера на функционально полную логику Поста С_n.

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

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

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

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

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

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

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

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

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

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

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

M = ?[0, 1]; >, ~, {1}?, где x > y = min (1, 1 ? x + y), ~ x = 1 ? x.

Список использованной литератур

1. Бочвар Д. Б., Финн В.К. О многозначных логиках, допускающих формализацию анализа антиномий, 1. - В кн.: Исследования по математической лингвистике, математической логике и информационным языкам. М., 1972;

2. Они же. Некоторые дополнения к статьям о многозначных логиках. - В кн.: Исследования по теории множеств и неклассическим логикам. М., 1976;

3. Зиновьев А.А. Философские проблемы многозначной логики. М., 1960;

4. Карпенко А.С. Многозначные логики (монография), в серии «Логика и компьютер», вып. 4. М., 1997;

Размещено на Allbest.ru