Flervärdig logik

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 20 februari 2021; kontroller kräver 19 redigeringar .

Flervärdig logik är logik där logiska uttryck kan ta värden från en uppsättning som innehåller mer än två element. Vissa av dessa värden anses dock vara sanna . I dessa egenskaper skiljer sig flervärdig logik från Aristoteles klassiska logik , där logiska uttryck bara kan ta ett av två möjliga värden - "sant" eller "falskt". Klassisk tvåvärdig logik kan dock utökas till n-värdig logik med n > 2. De mest populära i litteraturen är trevärdig logik (till exempel logiken hos Jan Lukasiewicz och Stephen Kleene , som tar värdena "sant", "falskt" och "okänt"), finit -värderad (kan ha fler än tre värden) och oändlig -värderad logik (detta inkluderar probabilistisk logik med en kontinuerlig skala av sanningsvärden från 0 till 1, såväl som fuzzy logic ).

Historik

Den första kända vetenskapsmannen som inte fullt ut accepterade och förlitade sig på lagen om den uteslutna mitten var Aristoteles (som ironiskt nog har krediterats som "den klassiska logikens fader"). Aristoteles insåg det faktum att hans lagar inte alltid kunde tillämpas på framtida händelser, men han generaliserade inte tvåvärdig logik till det n-dimensionella fallet för att eliminera felaktigheter.

Fram till slutet av 1800-talet följde matematiker lagarna i den aristoteliska logiken , som baserades på lagen om den uteslutna mitten . Men på 1900-talet började intresset för mångvärdig logik växa. Så, till exempel, började den polske matematikern och filosofen Jan Lukasiewicz att utveckla det första systemet av mångvärdig logik med hjälp av en tredje betydelse - "neutral" för att övervinna paradoxen med ett sjöslag formulerat av Aristoteles . Samtidigt presenterade den amerikanske matematikern Emil Post en artikel som beskrev möjligheten att införa ytterligare sanningsvärden för . Lite senare kunde Lukasiewicz, i samarbete med Alfred Tarski , upprepa Posts framgångar genom att formulera de grundläggande principerna för n-värderad logik för . 1932 sammanfattade Hans Reichenbach dessa principer med . $n>2$ $n>2$ $n\rightarrow \infty$

1932 visade Kurt Gödel att den intuitionistiska kalkylen inte är finitdimensionell och introducerade ett eget system (Gödel calculus, eng. Gödel logic ) som en mellanlänk mellan klassisk logik och intuitionistisk. Gödels kalkyl blev senare känd som "mellanlogik" (eng. intermediate logic ).

Grundläggande information

Huvudartiklar: Logik med tre värden, logik med fyra värden, logik med nio värden

För att beskriva många värdefulla propositionslogiker används de så kallade logiska matriserna [1] [2] , det vill säga algebraiska system av formen , där är universum, är funktionella symboler, är en predikatsymbol på en plats. Universums element motsvarar logiska värden och funktionssymbolerna motsvarar logiska kopplingar (operationer), så signaturtermerna är logiska formler. Om den logiska formeln är sådan att , kallas den en giltig eller tautologi för den givna logiska matrisen, medan predikatet definierar en delmängd av logiska värden som behandlas som sanna. Sålunda byggs matrisrepresentationer av propositionella logiker - uppsättningar av tautologier i ett språk som består av variabelnamn och bindemedel. ${\mathfrak {M}}=(V,f_{1},f_{2},...,f_{l},{\mathcal {D}})$ $V$ ${\displaystyle f_{1},f_{2},...,f_{l))$ $\mathcal{D}$ $\sigma ({\mathfrak {M}})$ $A(x_{1},x_{2},...,x_{k})$ ${\mathfrak {M}}\models \forall {x_{1}}\forall {x_{2}}{..}\forall {x_{k}}{\mathcal {D}}(A( x_{1},x_{2},...,x_{k}))$ $\mathcal{D}$

Vilken funktion som helst , inklusive den som uttrycks av en logisk formel med flera värden, där , kan representeras som en perfekt disjunktiv normalform (PDNF) av logik med flera värden, enligt följande [2] : $f:E_{n+1}^{k}\rightarrow E_{n+1}$ ${\displaystyle E_{n+1}=\{0,1,2,...,n\))$

f(x_{1},x_{2},..,x_{k})=\bigvee _{(a_{1},a_{2},..,a_{k})\i E_ {n+1}^{k}}f(a_{1},a_{2},..,a_{k})\wedge \left(\bigwedge _{m=1,..,k}J_{ a_{m}}(x_{m})\right)

var är konjunktionsoperationen : $\wedge$

x\wedge y=min(x,y),

symbolen står för disjunction operation : $\vee$

x\vee y=max(x,y),

och Rosser-Turquette-operatörerna: $J_{i}(x)$

J_{i}(x)={\begin{cases}n,&x=i,\\0,&x\neq i.\end{cases))

K 3 Kleene logik och P 3 Priest logik

Kleenes obestämbarhetslogik (ibland betecknad ) och Priests "paradoxlogik" introducerar en tredje "obestämd" eller "mellanliggande" betydelse av I. Sanningstabeller för negation (¬), konjunktion (˄), disjunktion ( ˅), implikation (→) och ekvivalenter (↔), ser ut så här: $K_{3}$ ${\displaystyle K_{3}^{S))$

¬
T	F
jag	jag
F	T

∧	T	jag	F
T	T	jag	F
jag	jag	jag	F
F	F	F	F

∨	T	jag	F
T	T	T	T
jag	T	jag	jag
F	T	jag	F

→K	T	jag	F
T	T	jag	F
jag	T	jag	jag
F	T	T	T

↔K	T	jag	F
T	T	jag	F
jag	jag	jag	jag
F	F	jag	T

Skillnaden mellan de två logikerna ligger i den olika definitionen av tautologin för algebra av propositioner (Tautologi är en identisk sann proposition som är oföränderlig med avseende på värdena för dess komponenter). I B definieras endast T som sant, medan både T och I definieras som sant. I Kleene-logik är I en "obestämd" storhet som inte är "sant" eller "falsk"; i Priests logik är I en "omdefinierad" storhet som är både "sant" och "falsk". innehåller inte tautologier, men innehåller samma tautologier som klassisk tvåvärdig logik. $K_{3}$ $P_{3}$ $K_{3}$ $P_{3}$

Bochvars interna logik med tre värden

Ett annat exempel är Bochvars "inre" logik med tre värden , erhållen 1938 av Dmitry Anatolyevich Bochvar. Det kallas också för svag trevärdig Kleene-logik. Sanningstabellerna för negation och ekvivalens förblir desamma, men för de andra tre operationerna tar de formen: $B_{3}^{I}$

∧+	T	jag	F
T	T	jag	F
jag	jag	jag	jag
F	F	jag	F

∨+	T	jag	F
T	T	jag	T
jag	jag	jag	jag
F	T	jag	F

→+	T	jag	F
T	T	jag	F
jag	jag	jag	jag
F	T	jag	T

I Bochvars interna logik kan jag beskrivas som "oberoende" eftersom dess värde inte beror på värdena på T och F.

Belnaps logik B 4

Logiken som föreslås av Nuel Belnap kombinerar och . Ett "överbestämt" värde betecknas med B och ett "underbestämt" värde med N. $K_{3}$ $P_{3}$

f ¬
T	F
B	B
N	N
F	T

f ∧	T	B	N	F
T	T	B	N	F
B	B	B	F	F
N	N	F	N	F
F	F	F	F	F

f ∨	T	B	N	F
T	T	T	T	T
B	T	B	T	B
N	T	T	N	N
F	T	B	N	F

Gödels logik G k och G ∞

År 1932 definierade Gödel en familj av många värdefulla logiker med en ändlig uppsättning värden: $G_{k}$ $0,{\frac {1}{k-1)),{\frac {2}{k-1)),...,{\frac {k-2}{k-1)), ett$

Till exempel för värdena kommer att vara $G_{3}$ $0,{\frac {1}{2)),1$

För värdet kommer att ha formen: ${\displaystyle G_{4))$ $0,{\frac {1}{3)),{\frac {2}{3)),1$

På liknande sätt definierade Gödel logik med ett oändligt antal värden . Alla värden i är reella tal som hör till intervallet [0, 1]. Sanningen i denna logik är 1. ${\displaystyle G_{\infty ))$ ${\displaystyle G_{\infty ))$

Konjunktion (˄) och disjunktion (˅) definieras som det lägsta/maximivärdet för följande uttryck:

{\begin{aligned}u\wedge v&:=\min\{u,v\}\\u\vee v&:=\max\{u,v\}\end{aligned))

Negation (¬) och implikation (→) definieras enligt följande:

{\begin{aligned}\neg _{G}u&={\begin{cases}1,&{\text{if }}u=0\\0,&{\text{if }}u> 0\end{cases}}\\u{\xrightarrow[{G}]{}}v&={\begin{cases}1,&{\text{if }}u\leq v\\v,&{\ text{if }}u>v\end{cases}}\end{aligned}}

Gödels logik är helt axiomatiserbar, så det är möjligt att definiera en logisk kalkyl där alla tautologier kan bevisas.

Lukasiewiczs logik L v och L ∞

Implikation (→) och negation (¬) definierades av Łukasiewicz med följande funktioner:

{\begin{aligned}{\underset {L}{\neg }}u&:=1-u\\u{\xrightarrow[{L}]{}}v&:=\min\{1,1 -u+v\}\end{aligned}}

Lukasiewicz använde först dessa definitioner 1920 när han beskrev logik med värden . $L_{3}$ $0,{\frac {1}{2)),1$

1922 beskrev han en logik med oändligt värde , vars alla värden låg i intervallet [0, 1] och var reella tal . I båda fallen var 1 sant. $L_{{\infty ))$

Att beskriva värden på ett Gödel-liknande sätt, nämligen: man kan skapa en ändligt värderad familj av logik , såväl som logik , där värdena också representeras av rationella tal och ligger i intervallet [0, 1 ]. Många tautologier i och är identiska. $0,{\frac {1}{v-1)),{\frac {2}{v-1)),...,{\frac {v-2}{v-1)), ett$ $L_{v}$ $L_{N_{0))$ $L_{{\infty ))$ $L_{N_{0))$

Den resulterande logiken Π

I den resulterande logiken har vi värden som hör till intervallet [0,1], för vilka konjunktion (ʘ) och implikation (→) definieras enligt följande:

{\begin{aligned}u\odot v&:=uv\\u{\xrightarrow[{\Pi }]{}}v&:={\begin{cases}1,&{\text{if }} u\leq v\\{\frac {v}{u}},&{\text{if }}u>v\end{cases}}\end{aligned}}

Ett falskt värde i denna logik är 0. Genom det är det möjligt att definiera operationerna för negation (¬) och konjunktion genom addition (˄):

{\begin{aligned}{\underset {\Pi }{\neg }}u&:=u{\xrightarrow[{\Pi }]{}}{\overline {0}}\\u{\underset {\Pi }{\wedge }}v&:=u\odot (u{\xrightarrow[{\Pi }]{}}v)\end{aligned}}

Postens logik P m

År 1921 definierade Post en familj av logiker med betydelser: ${\displaystyle P_{m))$

$0,{\frac {1}{m-1)),{\frac {2}{m-1)),...,{\frac {m-2}{m-1)), ett$ . (liknar logikerna och ). Negation (¬), konjunktion (˄) och disjunktion (˅) definieras enligt följande: $L_{v}$ $G_{k}$

{\begin{aligned}{\underset {P}{\neg }}u&:={\begin{cases}1,&{\text{if }}u=0\\u-{\frac { 1}{m-1)),&{\text{if }}u\not =0\end{cases}}\\u{\underset {P}{\wedge }}v&:=\min\{u ,v\}\\u{\underset {P}{\vee }}v&:=\max\{u,v\}\end{aligned}}

Roses logik

1951 beskrev Alan Rose en familj av logiker för system vars värden bildar gitter .

Semantik

Matrissemantik (logiska matriser)

Anslutning till klassisk logik

Logik är ett system med en uppsättning regler utformade för att bevara egenskaperna hos meningar under olika transformationer. I klassisk logik är denna egenskap "sann".

Flervärdig logik är utformad för att bevara notationsegenskapen. Eftersom det finns fler än två "sanna" värden kan slutledningsregler tillämpas för att lagra ytterligare data som kanske inte är sanna. Till exempel kan trevärdig logik ha två värden som motsvarar "sant" av olika gradationer (till exempel kan de vara positiva heltal), och inferensreglerna bevarar dessa värden.

Till exempel kan en lagrad egendom vara en bekräftelse som spelar en viktig roll i intuitionistisk logik . Vi betraktar inte dess sanning eller falskhet; istället arbetar vi med begrepp som exponering och felbarhet.

Den viktigaste skillnaden mellan bekräftelse och sanning är att lagen om den uteslutna mitten inte håller i det här fallet: ett påstående som inte är falskt kommer inte nödvändigtvis att bekräftas; istället har det bara bevisats att det inte är felaktigt. Den viktigaste skillnaden är säkerheten för den bibehållna egenskapen: det kan visas att P är validerat, att P är felaktigt eller att det inte är någotdera. Ett giltigt argument behåller giltighet under transformationer, så ett påstående som härrör från giltiga påståenden förblir giltigt. Ändå finns det bevis inom klassisk logik som är direkt beroende av lagen om den uteslutna mitten; eftersom denna lag inte gäller inom ramen för denna ordning finns det påståenden som inte kan bevisas på detta sätt.

Sushkos avhandling

Huvudartikel: Principen om bivalens

1900-talet präglades av den snabba utvecklingen av system med många värderade logiker, som för närvarande representeras av ett stort antal studier och artiklar. Men i takt med att antalet olika formella system ökade uppstod frågan om tolkningen av de erhållna resultaten. Forskare har akut insett behovet av att reducera (reducera) många värdefulla logiker till en enda bas.

Vanlig klassisk logik kan fungera som en av varianterna av en sådan grund. Den mest framstående representanten för detta tillvägagångssätt är den polske logikern Roman Sushko , som föreslog sin algoritm för att reducera all flervärdig logik till klassisk tvåvärdig logik och formulerade principen, som senare blev känd som "Sushkos tes". Enligt denna princip kan man för vilken flervärdig logik som helst få en bivalent semantik som beskriver denna logik.

Funktionell fullständighet av logik med många värden

Funktionell fullständighet är en term som används för att beskriva speciella egenskaper hos finita logik och algebror.

En logisk uppsättning är funktionellt komplett om och endast om uppsättningen av operationer i denna uppsättning kan användas för att beskriva en formel som motsvarar alla möjliga sanningsfunktioner .

En funktionellt komplett algebra är en algebra där varje finit avbildning kan uttryckas i termer av en sammansättning av operationerna som introduceras på den.

Klassisk logik: är funktionellt komplett, medan logiken i Lukasiewicz eller logik med oändligt värde inte har denna egenskap. $CL=(\{0,1\}\ \neg \ \rightarrow \land \ \lor \longleftrightarrow )$

Vi kan definiera ändvärdig logik enligt följande: , där och n tillhör mängden naturliga tal. Emil Post 1921 bevisade att om logik kan producera en m-te ordningens funktion, så finns det en kombination av operatorer i som kommer att producera en m+1 ordningsfunktion. $L_{n}(\{1,2,...,n\},\ f_{1},...,f_{m})$ $n\geq 2$ $L_{n}$

Oändligt värdefull logik

Oändligt värdead logik kan introduceras så här:

sanningsvärdet är i segmentet av reella tal från 0 till 1;
negation definieras som: ¬A = 1−A;
konjunktion definieras som: A∧B = min(A, B);
disjunktion definieras som: A∨B = max(A, B).

Systemen av R-funktioner av VL Rvachev [3] kan klassificeras som formella system av oändligt värderad logik .

Sannolikhetsteori och många värderade logiker

Det kan tyckas som att sannolikhetsteorin är mycket lik logik med oändligt värde: sannolikheten motsvarar ett sanningsvärde (1=sant, 0=falskt), sannolikheten för att inte inträffa någon händelse motsvarar negation, sannolikheten för förekomsten av två händelser samtidigt motsvarar en konjunktion, och sannolikheten för minst en av två händelser motsvarar en disjunktion.

Det finns emellertid en grundläggande skillnad mellan flervärdeslogik och sannolikhetsteori: i logik bestäms sannolikheten för alla funktioner helt av sannolikheten i dess argument, medan sannolikhetsteorin sannolikheten för en sammansatt händelse inte bara beror på sannolikheterna för dess ingående händelser, men också på deras beroende av varandra (vilket uttrycks i termer av deras betingade sannolikheter ).

Detta manifesteras särskilt i det faktum att i sannolikhetsteorin är motsvarigheten till "lagen om det uteslutna mitten" uppfylld: sannolikheten för att en händelse inträffar eller inte inträffar är alltid lika med ett, medan det i många värderade logiker lagen om den uteslutna mitten är inte uppfylld.

I sannolikhetsteorin gäller också motsvarigheten till " motsägelselagen ": sannolikheten att någon händelse inträffar och inte inträffar samtidigt är alltid 0, medan motsägelselagen inte håller i logik med många värden.

Samtidigt finns det ett visst samband mellan sanningsvärdena för ovanstående oändligt värderade logik och sannolikhetsteorins sannolikheter, nämligen:

om a är sannolikheten för någon händelse, så är sannolikheten för att denna händelse inte inträffar 1 − a ;
om a och b är sannolikheterna för några två händelser, så överstiger inte sannolikheten för att dessa två händelser gemensamt inträffar min( a , b );
om a och b är sannolikheten för några två händelser, så är sannolikheten för att åtminstone en av dessa två händelser inträffar större än eller lika med max( a , b ).

Applikationer

Tillämpningar av mångvärdig logik kan grovt delas in i två grupper.

Den första gruppen använder flervärdig logik för att effektivt lösa problemet med en binär representation av någon entitet. Att till exempel representera en boolesk funktion med flera utdata är att behandla dess utdata som en enda variabel som beror på flera argument. Ytterligare transformationer utförs med den: den omvandlas till en karakteristisk funktion med en utgång (särskilt en indikatorfunktion ).

Andra tillämpningar av logik med flera värden inkluderar PLA-design ( Programmable Logic ), tillståndsmaskinoptimering, testning och validering.

Den andra gruppen syftar till att skapa och designa elektroniska kretsar med mer än två diskreta nivåer. Dessa inkluderar: flervärdesminne, aritmetiska logiska enheter och fältprogrammerbara grindmatriser (FPGA). Flervärdesscheman har ett antal allvarliga teoretiska fördelar jämfört med vanliga binära scheman. Så, till exempel, kan kopplingen mellan kretsen och kretsen vara mindre om signalerna i kretsen kan hantera fyra nivåer istället för bara två. I minnesdesign fördubblar lagring av två informationsbitar istället för en per minnescell minnets täthet samtidigt som chipstorleken hålls densamma.

Programvaruapplikationer som använder aritmetiska logiska enheter drar ofta nytta av användningen av alternativ till binära talsystem. Så till exempel kan resterande och redundanta (eng. redundant binär representation ) talsystem reducera eller eliminera genom överföringar (eng. rippel-carry ), som sker i vanlig binär addition eller subtraktion, vilket leder till höghastighetsaritmetiska operationer. Sådana nummersystem har en naturlig implementering med flervärdesscheman.

Det praktiska med dessa potentiella teoretiska fördelar är dock starkt beroende av tillgången på speciella implementeringar som måste vara kompatibla och konkurrenskraftiga med nuvarande standardteknologier. Förutom dess användning i elektronisk kretsdesign, används flervärdig logik i stor utsträckning för att testa kretsar för fel och defekter. Nästan alla kända automatiska testsekvensgenerering (ATG) algoritmer som används för att testa digitala kretsar kräver en simulator som kan hantera 5-värdig logik (0, 1, x, D, D'). Ytterligare värden - x, D och D'- representerar okänt/oinitierat (x-värde), 0 istället för 1 (D-värde) och 1 istället för 0 (D'-värde).

Ternär logisk dator

Den ternära datorn "Setun" skapades och togs i drift vid fakulteten för mekanik och matematik vid Moscow State University 1958.

Till skillnad från det klassiska tillvägagångssättet som används i moderna datorer använde Setun en ternär kod med talen −1, 0, 1. Detta tillvägagångssätt har ett antal fördelar när man utför aritmetiska operationer och representerar ett tal i maskinens minne: det finns inget behov av imperfekt ytterligare, direkta eller omvända koder av siffror, avrundning utförs genom att helt enkelt skära av de minst signifikanta siffrorna, skiftoperationer är unika, siffrornas kod är enhetlig.

Forskningssajter

Det internationella symposiet om problem och frågor som uppstår från forskning i tillämpningar av flervärdig logik (ISMVL) har hållits årligen sedan 1970. Symposiets huvudsakliga arbetsområden är underhåll av olika digitala applikationer och verifieringsproblem.

Dessutom finns det en tidskrift dedikerad till flervärdig logik och dess tillämpningar i den digitala sfären.

Anteckningar

↑ Karpenko A. S. Lukasiewicz logik och primtal. Moskva: Nauka, 2000.
↑ 1 2 Kovalev S.P., "Mathematical foundations of computer aithmetic", Matem. tr., 8:1 (2005), 3-42; Siberian Adv. Math., 15:4 (2005), 34-70. Åtkomst: 2021-06-19
↑ Rvachev V. L. Teorin om R-funktioner och några av dess tillämpningar. - Kiev: Nauk. trodde 1982.

Länkar

Litteratur

Yablonsky SV Introduktion till diskret matematik. 2:a uppl. M.: Nauka, 1986. 384 sid. (länk ner) (länk nere sedan 2013-05-13 [3454 dagar]) Kapitel 2.
Flervärdiga logiker och deras tillämpningar: logisk kalkyl, algebror och funktionella egenskaper. Ed. Finna V.K Volym 1. M.: URSS, 2008. 416 sid.
Flervärdiga logiker och deras tillämpningar: Logik i artificiell intelligenssystem. Ed. Finna V.K Volym 2. M.: URSS, 2008. 240 sid.
Karpenko A. S. Flervärdiga logiker. Logik och dator. Problem. 4. M.: Nauka, 1997. 223 sid.
Karpenko A. S. Lukasiewicz logik och primtal. M.: Nauka, 2000. 319s.
Kondakov N. I. Logisk ordbok / Gorsky D. P. - M . : Nauka, 1971. - 656 sid.
Artiklar om flervärdiga logiker på arxiv.org
Levin V.I. Oändligt värderad logik i cybernetikproblem. Moskva: Radio och kommunikation, 1982. 176 sid.
Rescher, N. "Many-Valued Logic", Mc. Graw-Hill, New York, 1969.
Rosser, JB, Turquette, A.R. "Many-Valued Logics", North Holland, Amsterdam, 1952.

Logik

Filosofi • Semantik • Syntax • Historia

Logiska grupper

klassisk logik	Aristotelisk logik propositionell logik Första beställningslogik Andra ordningens logik högre ordningslogik
matematisk logik	mängdteori Modellteori Beräkningsbarhetsteori Bevisteori och konstruktiv matematik Linjär logik formellt system naturlig slutsats Sekvenskalkyl Algebra av logik Relevant logik Deontisk logik intuitionistisk logik Lambek kalkyl
Icke-klassisk logik	intuitionism rolig logik Substrukturell logik logik Beskrivningslogik Flervärdig logik Logisk syntes Bindande logik Temporal logik Modal logik ( Hybrid logik ) epistemisk logik
Filosofisk logik	Kritiskt tänkande informell logik deduktiva resonemang

Komponenter

Bortförande (logik)
Sannolikhet
påstående
Avdrag / Induktion / Traduktion
Verklighet
induktivt resonemang
slutledning
boolesk konstant
Sann
logiskt följa
Logisk form
Nödvändiga och tillräckliga förutsättningar
Beskrivning
Definition
Utbyte
Paket
Kontrovers ( Antinomy )
Syntetisk bedömning / Analytisk bedömning
Länk

Lista över booleska symboler