Ternær logik

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 31. august 2021; checks kræver 5 redigeringer .

Ternær logik ( tre-værdi logik eller ternær logik ) er en af de typer af mange-værdi logik foreslået af Jan Lukasiewicz i 1920 . Logik med tre værdier - historisk set er den første logik med flere værdier , den enkleste udvidelse af logik med to værdier .

Klassifikation

Der er tydelige TL, hvor alle tre værdier er defineret som specifikke numeriske værdier (for eksempel, , , ), samt et antal fuzzy ternære logikker med en, to og tre fuzzy logiske værdier (udtrykt ved tal som værdiområder). $\{0,1,2\}$ $\{-1,0,+1\}$ ${\displaystyle \{0,{}^{1}\!/_{2},1\))$

Fuzzy ternær logik med en fuzzy værdi supplerer værdierne ("false") og ("true") med en fuzzy værdi "uncertainty", som optager (i sammenligning med probabilistisk logik ) hele intervallet . Et eksempel på TL-værdier med to fuzzy værdier er ("mindre", "lige", "større"), ("negativ", 0, "positiv"). $0$ $en$ $(0,1)$

En TL med tre fuzzy værdier er af stor praktisk interesse, da enhver målt (for eksempel ved hjælp af sensorer) information kun er korrekt med en vis tolerance, det vil sige i et bestemt værdiområde. Eksempler på værdier for sådanne logikker kan være tripletter ("mindre end", "lige, inden for tolerance", "større end"), ("hældning til venstre", "lige, inden for acceptable grænser", "hældning til højre"), ("kold", "kølig", "varm") og andre.

Algebraiske egenskaber

Ternær logik, i modsætning til binær, er ikke en boolsk ring og har sit eget matematiske apparat. Det består af et system af aksiomer , der definerer enkelt- og dobbeltoperationer over mængden {" 1 ", "0", "1"}, såvel som egenskaberne afledt af dem.

For konjunktion og disjunktion i ternær logik er kommutative (forskydning), associative (associative) og distributive (distributive) love bevaret.

Flere egenskaber er dannet på grund af træk ved Lukasiewiczs negation:

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

Men på grund af tilstedeværelsen af den tredje stat viser nogle love for binær logik sig at være forkerte, og ternære analoger er formuleret til dem. Så i stedet for modsigelsesloven begyndte de at anvende loven om staters uforenelighed i stedet for loven om den udelukkede midterste - loven om staters fuldstændighed ( den udelukkede fjerde lov ), i stedet for den ukorrekte Blake- Poretsky-loven, den tre-sigtede Blake-Poretsky-lov bruges .

Fysisk implementering

Når de er fysisk implementeret, svarer ternære funktioner i ternær logik til ternære logiske elementer , i det generelle tilfælde ikke nødvendigvis elektroniske.

Kredsløb med 3-4-værdilogik gør det muligt at reducere antallet af brugte logiske og lagerelementer samt sammenkoblinger. Tre-værdi logiske kredsløb implementeres nemt på CMOS - teknologi. Tre-værdi logik er mere udtryksfuld end to-værdi logik.

På basis af ternære elementer - en ternær ferritdiodecelle udviklet af Nikolai Brusentsov - i 1959, blev en lille computer " Setun " designet i computercentret på Moscow State University , udgivet i 46 eksemplarer.

Logik

Kleene og Priests logikker

Nedenfor er sandhedstabellerne for de logiske operationer af Stephen Kleenes " stærke logik om ubestemmelighed " og Graham Priests " logic of paradox, LP " Begge logikker har tre logiske værdier - "falsk", "usikkerhed" (i Priests logik - "paradoks") og "sandhed", som i Kleenes logik er betegnet med bogstaverne F (falsk), U (ukendt), T (sandt), og i Priests logik med tallene −1, 0 og 1 [1] .

F: falsk, U: ukendt, T: sand

IKKE (A)

EN	¬ A
F	T
U	U
T	F

OG (A,B)

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

ELLER (A, B)

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

−1: falsk, 0: paradoksalt, +1: sand

NEG(A)

EN	¬ A
−1	+1
0	0
+1	−1

MIN (A, B)

A∧B _ _		B
A∧B _ _		−1	0	+1
EN	−1	−1	−1	−1
	0	−1	0	0
	+1	−1	0	+1

MAX (A, B)

A∨B _ _		B
A∨B _ _		−1	0	+1
EN	−1	−1	0	+1
	0	0	0	+1
	+1	+1	+1	+1

Værdien U i Kleenes logik er tildelt udtryk, der faktisk har værdien T eller F, men i øjeblikket er denne værdi ukendt af en eller anden grund, hvilket resulterer i usikkerhed. Resultatet af en logisk operation med værdien U kan dog bestemmes. For eksempel, da T & F = F og F & F = F, så U & F = F. Mere generelt: hvis for en logisk operation opererer relationen
oper(F,F)=oper(F,T), så oper (F,U)=oper(F,F)=oper(F,T);
på samme måde, hvis
oper(T,F)=oper(T,T), så oper(T,U)=oper(T,F)=oper(T,T).

I modsætning til Kleenes logik er værdien 0 i Priests logik defineret og betragtet som både sand og falsk (paradoksalt) på samme tid. Forskellen ligger i definitionen af tautologier. Mens der i Kleenes logik kun er én fornemt sandhedsværdi, der er T, skelnes der i Priests logik både værdierne 1 og 0.

Med den numeriske betegnelse af logiske værdier (-1, 0, 1) svarer logiske operationer til følgende numeriske operationer:

{\bar {X}}=-X;

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

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

Implikationsoperationen i Kleene og Priest logikken er defineret af en formel svarende til den binære logiske formel:

X\højrepil Y\ {\overset {{\underset {{\mathrm {def}}}{}}}{=}}{\bar {X}}\lor Y

Sandhedstabeller for hende

IMP K (A, B), ELLER(¬A, B)

A → B		B
A → B		T	U	F
EN	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
EN	+1	+1	0	−1
	0	+1	0	0
	−1	+1	+1	+1

Denne definition adskiller sig fra den definition af implikation, der er vedtaget i Lukasiewicz's logik.

Funktionel tilgang

Vi kalder en funktion for en logisk funktion med tre værdier, hvis alle dens variabler tager værdier fra mængden {0,1,2} og selve funktionen tager værdier fra det samme sæt. Funktionseksempler: max (x, y), min (x, y), x+1 ( mod 3). Angiv mængden af alle funktioner i logik med tre værdier. Ved operation på funktioner mener vi superposition. En klasse af funktioner K fra kaldes lukket, hvis en hvilken som helst superposition af funktioner fra K tilhører K . Et system af funktioner af klasse K kaldes komplet, hvis en funktion fra K kan repræsenteres ved en superposition af funktioner i dette system. Et komplet system kaldes en basis, hvis ingen funktion fra dette system kan repræsenteres ved en superposition af de resterende funktioner i dette system. Det er bevist, at der findes en endelig basis i (især bestående af én funktion). En lukket klasse K kaldes precomplete, hvis den ikke falder sammen med , men tilføjelse af en funktion, der ikke hører til den, genererer . SV Yablonsky beviste [2] at der er 18 prækomplette klasser i . Det er også bevist, at de alle har endelige baser, især bestående af funktioner afhængig af højst to variable [3] . Yu. I. Yanov og A. A. Muchnik beviste [4] , at der er klasser af funktioner, der ikke har en basis, og klasser af funktioner, der har en uendelig basis. Dette indebærer, at sættet af lukkede klasser i har kontinuummets kardinalitet . I denne, adskiller tre-værdi (og enhver multi-værdi) logik væsentligt fra to-værdi logik, hvor, som Post bevist [5] , alle lukkede klasser har en endelig basis, og sættet af lukkede klasser kan tælles. $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}$

Brug i databaser

Nogle databasestyringssystemer bruger den særlige værdi UNKNOWN, som kan være resultatet af en logisk operation sammen med værdierne TRUE og FALSE.

Betydningen af UNKNOWN-værdien er "ukendt", det vil sige det udefinerede resultat af operationen. Værdien UNKNOWN kan bruges, når den særlige værdi NULL bruges i det anvendte softwareudviklingssystem . UNKNOWN-værdien returnerer en sammenligningsoperation, hvis en eller begge dens operander er NULL, samt nogle booleske operationer, hvis en af deres operander er UNKNOWN. De betingede operatører af programmeringssprog behandler UNKENDT værdien på samme måde som FALSE, det vil sige en konstruktion af formen:

hvis UKENDT så a := 1 ellers a := 2

vil medføre, at variabel a tildeles værdien 2.

Regler for operationer med UNKENDT

Enhver sammenligning af en værdi med NULL eller UNKNOWN resulterer i UNKNOWN.
ikke UNKNOWN = UNKNOWN
SAND og UKENDT = UKENDT
FALSK og UKENDT = FALSK
SAND eller UKENDT = SAND
FALSK eller UKENDT = UKENDT
TRUE xor UNKNOWN = UNKNOWN
FALSK xor UKENDT = UKENDT

Se også

Noter

↑ I den originale 1979-publikation Arkiveret 23. maj 2021 på Wayback Machine , som henholdsvis f , p og t .
↑ Yablonsky S. I. Funktionelle konstruktioner i k -værdilogik, Proceedings of the Mathematical Institute. V. A. Steklova, 51, 1958
↑ Gnidenko V. M., Finding rækkefølgen af prækomplette klasser i logik med tre værdier, lør. Problemer med kybernetik, udgave 8, M., 1962
↑ Yanov Yu .
↑ Post EL Two-valued iterative systems, Ann Math. Studier, 5, nr. 1, 1941

Litteratur

DC Rine (red.), Computer Science and Multiple-Valued Logic. Teori og anvendelser. Elsevier , 1977, 548 s. ISBN 9780720404067
Vasiliev N. I. Imaginær logik. — M .: Nauka, 1989.
Karpenko A.S. Multivalued logics // Logik og computer. Problem. nr. 4. — M .: Nauka, 1997.
Carroll Lewis. Symbolsk logik // Lewis Carroll. Knudehistorie. — M .: Mir, 1973.
Lukasevich Ya Aristotelisk syllogistik ud fra den moderne formelle logiks synspunkt. - M . : Udenlandsk litteratur, 1959.
Slinin Ya. A. Moderne modal logik. - L . : Forlag ved Leningrad Universitet, 1976.
Styazhkin NI Dannelse af matematisk logik. - M . : Nauka, 1967.
Getmanova A. D. Lærebog i logik. - M . : Vlados, 1995. - S. 259-268. — 303 s. — ISBN 5-87065-009-7 .
Explanatory Dictionary of Computing Systems / Ed. V. Illingworth m.fl. - M . : Mashinostroenie, 1990. - 560 s. — ISBN 5-217-00617-X .
Yablonsky S. I. Funktionelle konstruktioner i k -værdilogik, Proceedings of the Mathematical Institute. V. A. Steklova, 51, 1958
Yanov Yu. I., Muchnik A. A., Om eksistensen af k -vurderede lukkede klasser uden et endeligt grundlag, DAN SSSR , 127, nr. 1, 1959
Gnidenko V. M., Finde rækkefølgen af prækomplette klasser i logik med tre værdier, lør. Problemer med kybernetik, udgave 8, M., 1962
Post EL Two-valued iterative systems, Ann Math. Studier, 5, nr. 1, 1941
Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer Widom “Databasesystemer. Fuldt kursus»