WikiSort.ru - Не сортированное

ПОИСК ПО САЙТУ | о проекте

Трои́чная ло́гика (трёхзначная логика или тернарная логика) — один из видов многозначной логики, предложенный Яном Лукасевичем в 1920 году. Трёхзначная логика — исторически первая многозначная логика. Она является простейшим расширением двузначной логики.

Чёткую математическую троичную логику, в которой имеется три чётких значения (0,1,2), (-1,0,+1), (0,1/2,1) и т. п. часто путают с нечёткой троичной логикой, которая является частным случаем нечёткой логики c тремя значениями, одно, два или все три из которых нечёткие.

Перечень значений нечёткой трёхзначной логики с двумя чёткими и с одним нечётким значением помимо «истинно» и «ложно» включает также третье значение, которое нечётко и трактуется как «не определено» или «неизвестно».

Примерами значений нечёткой трёхзначной логики с одним чётким и с двумя нечёткими значениями являются: («меньше», «равно», «больше»), («уклон влево», «прямо», «уклон вправо») и другие.

Примерами значений нечёткой трёхзначной логики с тремя нечёткими значениями, к которым сводится очень большое количество практических народнохозяйственных задач, являются: («меньше», «равно, в допустимых пределах», «больше»), («уклон влево», «прямо, в допустимых пределах», «уклон вправо»), («холодно», «прохладно», «жарко») и другие.

Алгебраические свойства

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

Для конъюнкции и дизъюнкции в тройной логике сохраняются коммутативный (переместительный), ассоциативный (сочетательный) и дистрибутивный (распределительный) законы.

Несколько свойств образуются благодаря особенности отрицания Лукасевича:

$\lnot {\bar {1}}=1$
$\lnot (x\land {\bar {1}})=\lnot x\lor 1$

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

Физическая реализация

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

Схемы с 3-4-значной логикой дают возможность сократить количество используемых логических и запоминающих элементов, а также межэлементных соединений. Схемы трёхзначной логики легко реализуются на КМОП-технологии. Трёхзначная логика обладает большей выразительностью, чем двухзначная. Например, существует лишь 16 комбинаций входов-выходов двухвходового двоичного вентиля, тогда как у аналогичного троичного вентиля таких комбинаций 19683.^[1]

На основе троичных элементов — троичной ферритодиодной ячейки разработки Николая Брусенцова — в 1959 году в вычислительном центре МГУ спроектирована малая ЭВМ «Сетунь», выпущена в 46 экземплярах.

Логики

Логики Клини и Приста

Ниже показаны таблицы истинности для логических операций «Сильной логики неопределённости» (strong logic of indeterminacy) Стивена Клини и «Парадоксальной логики» (logic of paradox, LP) Приста. Обе логики имеют три логических значения — «ложь», «неопределённость» и «истина», которые в логике Клини обозначаются буквами F (false), U (unknown), T (true), а в логике Приста числами -1, 0 и 1.

F: false, U: unknown, T: true

NOT(A)
A	¬ A
F	T
U	U
T	F

AND(A, B)
A ∧ B		B
A ∧ B		F	U	T
A	F	F	F	F
	U	F	U	U
	T	F	U	T

OR(A, B)
A ∨ B		B
A ∨ B		F	U	T
A	F	F	U	T
	U	U	U	T
	T	T	T	T

−1: false, 0: unknown, +1: true

NEG(A)
A	¬ A
−1	+1
0	0
+1	−1

MIN(A, B)
A ∧ B		B
A ∧ B		−1	0	+1
A	−1	−1	−1	−1
	0	−1	0	0
	+1	−1	0	+1

MAX(A, B)
A ∨ B		B
A ∨ B		−1	0	+1
A	−1	−1	0	+1
	0	0	0	+1
	+1	+1	+1	+1

Значение U присваивается выражениям, которые реально имеют значение T или F, но в данный момент это значение по каким-то причинам неизвестно, в результате чего возникает неопределённость. Тем не менее, результат логической операции с величиной U может оказаться определённым. Например, поскольку T & F = F и F & F = F, то и U & F = F. В более общем виде: если для некоторой логической операции oper выполняется соотношение
oper(F,F)=oper(F,T), то oper(F,U)=oper(F,F)=oper(F,T);
аналогично, если
oper(T,F)=oper(T,T), то oper(T,U)=oper(T,F)=oper(T,T).

При численном обозначении логических значений (–1, 0, 1) логические операции эквивалентны следующим численным операциям:

{\bar {X}}=-X;

X\lor Y=max(X,Y);

X\land Y=min(X,Y).

Операция импликации в логиках Клини и Приста определяется формулой, аналогичной формуле двоичной логики:

X\rightarrow Y\ {\overset {\underset {\mathrm {def} }{}}{=}}{\bar {X}}\lor Y

.

Таблицы истинности для неё

IMP_K(A, B), OR(¬A, B)
A → B		B
A → B		T	U	F
A	T	T	U	F
	U	T	U	U
	F	T	T	T

IMP_K(A, B), MAX(−A, B)
A → B		B
A → B		+1	0	−1
A	+1	+1	0	−1
	0	+1	0	0
	−1	+1	+1	+1

Это определение отличается от определения импликации, принятого в логике Лукасевича.

Функциональный подход

Назовём функцию $y=f(x_{1},\;x_{2},\;\ldots ,\;x_{n})$ функцией трёхзначной логики, если все её переменные принимают значения из множества {0,1,2} и сама функция принимает значения из этого же множества. Примеры функций: max(x,y), min(x,y), x+1 (mod 3). Обозначим $P_{3}$ множесто всех функций трёхзначной логики. Под операцией над функциями будем понимать суперпозицию. Класс функций K из $P_{3}$ назовём замкнутым, если любая суперпозиция функций из K принадлежит K. Система функций класса K называется полной, если любая функция из K может быть представлена суперпозицией функций этой системы. Полная система называется базисом, если никакая функция из этой системы не может быть представлена суперпозицией остальных функций этой системы. Доказано, что в $P_{3}$ существует конечный базис (в частности, состоящий из одной функции). Замкнутый класс K называется предполным, если он не совпадает с $P_{3}$ , но добавление любой функции, ему не принадлежащей, порождает $P_{3}$ . С.В. Яблонским доказано^[2], что в $P_{3}$ существует 18 предполных классов. Также доказано, что все они имеют конечные базисы, в частности, состоящие из функций, зависящих не более чем от двух переменных^[3]. Ю.И.Янов и А.А.Мучник доказали^[4], что в $P_{3}$ существуют классы функций, не имеющие базиса, и классы функций, имеющие бесконечный базис. Отсюда следует, что множество замкнутых классов в $P_{3}$ имеет мощность континуума. Этим трёхзначная (и любая многозначная) логика существенно отличается от двухзначной, где, как доказано Постом^[5], все замкнутые классы имеют конечный базис и множество замкнутых классов счётно.

См. также

Примечания

↑ Толковый словарь по вычислительным системам, 1990, M.235.
↑ Яблонский С.И. Функциональные построения в k-значной логике, Труды Математического института им. В.А.Стеклова, 51, 1958
↑ Гниденко В.М., Нахождение порядков предполных классов в трёхзначной логике, сб. Проблемы кибернетики, вып 8, М., 1962
↑ Янов Ю.И., Мучник А.А., О существовании k-значных замкнутых классов, не имеющих конечного базиса, ДАН СССР, 127, №1, 1959
↑ Post E.L. Two-valued iterative systems, Аnn Math. Studies, 5, №1, 1941

Литература

D. C. Rine (ed.), Computer Science and Multiple-Valued Logic. Theory and Applications. Elsevier, 1977, 548p. ISBN 9780720404067
Васильев Н. И. Воображаемая логика. — М.: Наука, 1989.
Карпенко А. С. Многозначные логики // Логика и компьютер. Вып. №4. — М.: Наука, 1997.
Кэррол Льюис. Символическая логика // Льюис Кэррол. История с узелками. — М.: Мир, 1973.
Лукасевич Я. Аристотелевская силлогистика с точки зрения современной формальной логики. — М.: Иностранная литература, 1959.
Слинин Я. А. Современная модальная логика. — Л.: Издательство Ленинградского университета, 1976.
Стяжкин Н. И. Формирование математической логики. — М.: Наука, 1967.
Гетманова А. Д. Учебник по логике. — М.: Владос, 1995. — С. 259—268. — 303 с. — ISBN 5-87065-009-7.
Толковый словарь по вычислительным системам / Под ред. В. Иллингуорта и др.. — М.: Машиностроение, 1990. — 560 с. — ISBN 5-217-00617-X.
Яблонский С.И. Функциональные построения в k-значной логике, Труды Математического института им. В.А.Стеклова, 51, 1958
Янов Ю.И., Мучник А.А., О существовании k-значных замкнутых классов, не имеющих конечного базиса, ДАН СССР, 127, №1, 1959
Гниденко В.М., Нахождение порядков предполных классов в трёхзначной логике, сб. Проблемы кибернетики, вып 8, М., 1962
Post E.L. Two-valued iterative systems, Аnn Math. Studies, 5, №1, 1941

Ссылки

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .

Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии

[_c416bbb8ecd40887-1] Толковый словарь по вычислительным системам, 1990, M.235.

[2] Яблонский С.И. Функциональные построения в k-значной логике, Труды Математического института им. В.А.Стеклова, 51, 1958

[3] Гниденко В.М., Нахождение порядков предполных классов в трёхзначной логике, сб. Проблемы кибернетики, вып 8, М., 1962

[4] Янов Ю.И., Мучник А.А., О существовании k-значных замкнутых классов, не имеющих конечного базиса, ДАН СССР, 127, №1, 1959

[5] Post E.L. Two-valued iterative systems, Аnn Math. Studies, 5, №1, 1941