Logica ternară

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 31 august 2021; verificările necesită 5 modificări .

Logica ternară ( logica cu trei valori sau logica ternară ) este unul dintre tipurile de logică cu mai multe valori propuse de Jan Lukasiewicz în 1920 . Logica cu trei valori - din punct de vedere istoric, prima logică cu mai multe valori , este cea mai simplă extensie a logicii cu două valori .

Clasificare

Există TL clare, în care toate cele trei valori sunt definite ca valori numerice specifice (de exemplu, , , ), precum și o serie de logici ternare fuzzy cu una, două și trei valori logice fuzzy (exprimate prin numere ca intervale de valori). $\{0,1,2\}$ $\{-1,0,+1\)$ $\{0,{}^{1}\!/_{2},1\)$

Logica ternară fuzzy cu o valoare fuzzy completează valorile ("fals") și ("adevărat") cu o valoare fuzzy "incertitudine", care ocupă (în comparație cu logica probabilistică ) întregul interval . Un exemplu de valori TL cu două valori neclare este ("mai puțin", "egal", "mai mare"), ("negativ", 0, "pozitiv"). $0$ $unu$ $(0,1)$

Un TL cu trei valori neclare este de mare interes practic, deoarece orice informație măsurată (de exemplu, prin intermediul senzorilor) este corectă numai cu o anumită toleranță, adică într-un anumit interval de valori. Exemple de valori pentru astfel de logici pot fi triplete („mai puțin decât”, „egal, în limitele toleranței”, „mai mare decât”), („pantă spre stânga”, „drept, în limite acceptabile”, „pantă spre dreapta”), („rece”, „rece”, „fierbinte”) și altele.

Proprietăți algebrice

Logica ternară, spre deosebire de binară, nu este un inel boolean și are propriul său aparat matematic. Constă dintr-un sistem de axiome care definesc operații simple și duble asupra mulțimii {" 1 ", "0", "1"}, precum și proprietățile derivate din acestea.

Pentru conjuncția și disjuncția în logica ternară, se păstrează legile comutative (deplasare), asociative (asociative) și distributive (distributive).

Mai multe proprietăți se formează datorită caracteristicii negației lui Lukasiewicz:

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

Cu toate acestea, din cauza prezenței celei de-a treia stări, unele legi ale logicii binare se dovedesc a fi incorecte și pentru ele sunt formulați analogi ternari. Deci, în locul legii contradicției , au început să aplice legea incompatibilității statelor , în locul legii mijlocului exclus - legea completității statelor ( legea al patrulea exclus ), în loc de Blake incorectă. Legea Poretsky, se folosește legea Blake-Poretsky cu trei termeni .

Implementare fizică

Când sunt implementate fizic, funcțiile ternare în logica ternară corespund elementelor logice ternare , în cazul general, nu neapărat electronice.

Circuitele cu logica cu 3-4 valori fac posibilă reducerea numărului de elemente logice și de stocare utilizate, precum și a interconexiunilor. Circuitele logice cu trei valori sunt ușor de implementat pe tehnologia CMOS . Logica cu trei valori este mai expresivă decât logica cu două valori.

Pe baza elementelor ternare - o celulă de diodă de ferită ternară dezvoltată de Nikolai Brusentsov - în 1959, un mic computer „ Setun ” a fost proiectat în centrul de calcul al Universității de Stat din Moscova , lansat în 46 de exemplare.

Logica

Logica lui Kleene și Priest

Mai jos sunt tabelele de adevăr pentru operațiunile logice ale „ logicii puternice a indeterminației ” a lui Stephen Kleene și ale „ logicii paradoxului ” a lui Graham Priest , LP Ambele logici au trei valori logice - „fals”, „incertitudine” (în logica lui Priest - „paradox”) și „adevăr”, care în logica lui Kleene sunt notate cu literele F (fals), U (necunoscut), T (adevărat), iar în logica lui Priest prin numerele −1, 0 și 1 [1] .

F: fals, U: necunoscut, T: adevărat

NU (A)

A	¬ A
F	T
U	U
T	F

ȘI (A, B)

A∧B _ _		B
A∧B _ _		F	U	T
A	F	F	F	F
	U	F	U	U
	T	F	U	T

SAU (A, B)

A∨B _ _		B
A∨B _ _		F	U	T
A	F	F	U	T
	U	U	U	T
	T	T	T	T

−1: fals, 0: paradoxal, +1: adevărat

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

Valoarea U în logica lui Kleene este atribuită expresiilor care au de fapt valoarea T sau F, dar în acest moment această valoare este necunoscută dintr-un motiv oarecare, rezultând incertitudine. Totuși, rezultatul unei operații logice cu valoarea U poate fi determinat. De exemplu, deoarece T & F = F și F & F = F, atunci U & F = F. Mai general: dacă pentru o operație logică oper relația
oper(F,F)=oper(F,T), atunci oper (F,U)=oper(F,F)=oper(F,T);
în mod similar, dacă
oper(T,F)=oper(T,T), atunci oper(T,U)=oper(T,F)=oper(T,T).

Spre deosebire de logica lui Kleene, în logica lui Priest valoarea 0 este definită și considerată atât adevărată cât și falsă (paradoxală) în același timp. Diferența constă în definiția tautologiilor. În timp ce în logica lui Kleene o singură valoare de adevăr distinsă este T, în logica lui Priest se disting ambele valori 1 și 0.

Cu desemnarea numerică a valorilor logice (-1, 0, 1), operațiile logice sunt echivalente cu următoarele operații numerice:

{\bar {X}}=-X;

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

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

Operația de implicare în logica Kleene și Priest este definită printr-o formulă similară cu formula logică binară:

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

Tabele de adevăr pentru ea

IMP K (A, B), SAU(¬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

Această definiție diferă de definiția implicației adoptată în logica lui Lukasiewicz.

Abordare funcțională

Numim o funcție o funcție logică cu trei valori dacă toate variabilele sale iau valori din mulțimea {0,1,2} și funcția în sine ia valori din același set. Exemple de funcții: max (x, y), min (x, y), x+1 ( mod 3). Indicați mulțimea tuturor funcțiilor logicii cu trei valori. Prin operare pe funcții înțelegem suprapunere. O clasă de funcții din K se numește închisă dacă orice suprapunere de funcții din K aparține lui K . Un sistem de funcții din clasa K se numește complet dacă orice funcție din K poate fi reprezentată printr-o suprapunere de funcții a acestui sistem. Un sistem complet se numește bază dacă nicio funcție din acest sistem nu poate fi reprezentată printr-o suprapunere a funcțiilor rămase ale acestui sistem. Se dovedește că există o bază finită în (în special, constând dintr-o funcție). O clasă închisă K se numește precompletă dacă nu coincide cu , dar adăugarea oricărei funcții care nu îi aparține generează . SV Yablonsky a demonstrat [2] că există 18 clase precomplete în . De asemenea, se dovedește că toate au baze finite, în special, formate din funcții care depind de cel mult două variabile [3] . Yu. I. Yanov și A. A. Muchnik au demonstrat [4] că există clase de funcții care nu au bază și clase de funcții care au o bază infinită. Aceasta implică faptul că setul de clase închise în are cardinalitatea continuumului . În acest sens, logica cu trei valori (și orice multi-valori) diferă în mod esențial de logica cu două valori, unde, după cum a demonstrat Post [5] , toate clasele închise au o bază finită și setul de clase închise este numărabil. $y=f(x_{1},\;x_{2},\;\ldots ,\;x_{n})$ $P_{3}$ $P_{3}$ $P_{3}$ $P_{3}$ $P_{3}$ $P_{3}$ $P_{3}$ $P_{3}$

Utilizare în baze de date

Unele sisteme de gestionare a bazelor de date folosesc valoarea specială NECUNOSCUT, care poate fi rezultatul unei operații logice, împreună cu valorile TRUE și FALSE.

Semnificația valorii NECUNOSCUT este „necunoscut”, adică rezultatul nedefinit al operației. Valoarea UNKNOWN poate fi utilizată atunci când valoarea specială NULL este utilizată în sistemul de dezvoltare software aplicat . Valoarea UNKNOWN returnează o operație de comparare dacă unul sau ambii operanzi ai săi sunt NULL, precum și unele operații booleene dacă unul dintre operanzii lor este NECUNOSCUT. Operatorii condiționali ai limbajelor de programare tratează valoarea NECUNOSCUT în același mod ca FALSE, adică o construcție de forma:

dacă NECUNOSCUT atunci a := 1 altfel a := 2

va face ca variabilei a să i se atribuie valoarea 2.

Reguli pentru operațiuni cu NECUNOSCUT

Orice comparație a oricărei valori cu NULL sau UNKNOWN are ca rezultat UNKNOWN.
nu NECUNOSCUT = NECUNOSCUT
ADEVĂRAT și NECUNOSCUT = NECUNOSCUT
FALSE și NECUNOSCUT = FALS
ADEVĂRAT sau NECUNOSCUT = ADEVĂRAT
FALSE sau NECUNOSCUT = NECUNOSCUT
TRUE xor NECUNOSCUT = NECUNOSCUT
FALSE xor NECUNOSCUT = NECUNOSCUT

Vezi și

Note

↑ În publicația originală din 1979, arhivată la 23 mai 2021 la Wayback Machine , ca f , p și , respectiv, t .
↑ Yablonsky S. I. Construcții funcționale în logica k -valuată, Proceedings of the Mathematical Institute. V. A. Steklova, 51, 1958
↑ Gnidenko V. M., Finding the orders of precomplet classs in three-valued logic, Sat. Probleme de cibernetică, numărul 8, M., 1962
↑ Yanov Yu .
↑ Post EL Sisteme iterative cu două valori, Ann Math. Studii, 5, nr. 1, 1941

Literatură

DC Rine (ed.), Computer Science and Multiple-Valued Logic. Teorie și aplicații. Elsevier , 1977, 548p. ISBN 9780720404067
Vasiliev N. I. Logica imaginară. — M .: Nauka, 1989.
Karpenko A.S. Logica multivalorică // Logica și computerul. Problema. nr. 4. — M .: Nauka, 1997.
Carroll Lewis. Logica simbolică // Lewis Carroll. Istoria nodurilor. — M .: Mir, 1973.
Lukasevici Ya. Silogistica aristotelică din punctul de vedere al logicii formale moderne. - M . : Literatură străină, 1959.
Slinin Ya. A. Logica modală modernă. - L. : Editura Universității din Leningrad, 1976.
Styazhkin NI Formarea logicii matematice. - M .: Nauka, 1967.
Getmanova A. D. Manual de logică. - M . : Vlados, 1995. - S. 259-268. — 303 p. — ISBN 5-87065-009-7 .
Dicţionar explicativ de sisteme de calcul / Ed. V. Illingworth și alții.- M . : Mashinostroenie, 1990. - 560 p. — ISBN 5-217-00617-X .
Yablonsky S. I. Construcții funcționale în logica k -valuată, Proceedings of the Mathematical Institute. V. A. Steklova, 51, 1958
Yanov Yu. I., Muchnik A. A., Despre existența claselor închise cu valori k fără o bază finită, DAN SSSR , 127, nr.1, 1959
Gnidenko V. M., Găsirea ordinelor claselor precomplete în logica cu trei valori, Sat. Probleme de cibernetică, numărul 8, M., 1962
Post EL Sisteme iterative cu două valori, Ann Math. Studii, 5, nr. 1, 1941
Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer Widom „Sisteme de baze de date. curs complet»