Łukasiewicz logik

₀ Inom matematik och filosofi är Łukasiewicz logik ( / ˌ l uː k ə ˈ ʃ ɛ v ɪ tʃ / LOO -kə- SHEV -itch , polska: [wukaˈɕɛvitʂ] ) en icke-klassisk logik med många värden . Det definierades ursprungligen i början av 1900-talet av Jan Łukasiewicz som en modal logik med tre värden ; den generaliserades senare till n -värderade (för alla finita n ) såväl som oändligt många ( ℵ ₀ -värderade) varianter, både propositionella och första ordningens . Den ℵ -värderade versionen publicerades 1930 av Łukasiewicz och Alfred Tarski ; följaktligen kallas det ibland Łukasiewicz–Tarski-logiken . Den tillhör klasserna t-norm fuzzy logics och substruktural logics .

Łukasiewicz logik motiverades av Aristoteles förslag att bivalent logik inte var tillämplig på framtida kontingenter, t.ex. uttalandet "Det kommer att bli ett sjöslag i morgon". Med andra ord, påståenden om framtiden var varken sanna eller falska, men ett mellanvärde kunde tilldelas dem, för att representera deras möjlighet att bli sanna i framtiden.

Den här artikeln presenterar Łukasiewicz(–Tarski)-logiken i dess fulla allmänhet, dvs som en logik med oändligt värde. För en grundläggande introduktion till den trevärdiga instansieringen Ł ₃ , se logik med tre värden .

Språk

Łukasiewicz logiks propositionella kopplingar är $\rightarrow$ ("implikation") och konstanten $\bot$ ("falsk"). Ytterligare anslutningar kan definieras i termer av dessa:

${\begin{aligned}\neg A&=_{def}A\högerpil \bot \\A\vee B&=_{def}(A\högerpil B)\högerpil B\\ A\kil B&=_{def}\neg (\neg A\vee \neg B)\\A\leftrightarrow B&=_{def}(A\högerpil B)\kil (B\högerpil A)\end{justerad }}$

Konnektiven $\vee$ och $\wedge$ kallas svag disjunktion och konjunktion, eftersom de är icke-klassiska, eftersom lagen om utesluten mitt inte gäller för dem. I samband med substrukturella logiker kallas de för additiv bindning. De motsvarar också gitter min/max kopplingar.

När det gäller substrukturella logiker finns det också starka eller multiplikativa disjunktions- och konjunktionskopplingar, även om dessa inte är en del av Łukasiewiczs ursprungliga presentation:

${\begin{aligned}A\oplus B&=_{def}\neg A\högerpil B\ \A\otimes B&=_{def}\neg (A\högerpil \neg B)\end{aligned}}$

Det finns också definierade modala operatorer som använder Tarskian Möglichkeit :

${\begin{aligned}\Diamond A&=_{def}\neg A\rightarrow A\\\Box A&=_ {def}\neg \Diamond \neg A\end{aligned}}$

Axiom

Det ursprungliga axiomsystemet för propositionell oändligt värderad Łukasiewicz-logik använde implikation och negation som de primitiva kopplingarna, tillsammans med modus ponens :

${\begin{aligned}A&\högerpil (B\högerpil A)\\(A\högerpil B)&\högerpil ((B\högerpil C)\högerpil (A\högerpil C))\\((A \högerpil B)\högerpil B)&\högerpil ((B\högerpil A)\högerpil A)\\(\neg B\högerpil \neg A)&\högerpil (A\högerpil B).\end{aligned}}$

Propositionell oändligt värderad Łukasiewicz-logik kan också axiomatiseras genom att lägga till följande axiom till det axiomatiska systemet för monoidal t-norm-logik :

Delbarhet: $(A\wedge B)\rightarrow (A\otimes (A\rightarrow B))$
Dubbel negation: $\neg \neg A\högerpil A.$

Det vill säga, oändligt värderad Łukasiewicz-logik uppstår genom att addera axiomet dubbel negation till grundläggande fuzzy logic (BL), eller genom att lägga till axiomet delbarhet till logiken IMTL.

Finita-värderade Łukasiewicz-logiker kräver ytterligare axiom.

Bevisteori

En hypersekvent kalkyl för trevärdig Łukasiewicz-logik introducerades av Arnon Avron 1991.

Sekvensberäkningar för finita och oändligt värderade Łukasiewicz-logik som en förlängning av linjär logik introducerades av A. Prijatelj 1994. Dessa är dock inte fria system.

Hypersequent calculi för Łukasiewicz-logik introducerades av A. Ciabattoni et al 1999. Dessa är dock inte fria för $n>3$ ändligt värderade logiker.

Ett märkt tablåsystem introducerades av Nicola Olivetti 2003.

Verkligt värderad semantik

Oändligt värderad Łukasiewicz-logik är en realvärdig logik där meningar från sententialkalkyl kan tilldelas ett sanningsvärde på inte bara 0 eller 1 utan även vilket reellt tal som helst däremellan (t.ex. 0,25). Värderingar har en rekursiv definition där:

$w(\theta \circ \phi )=F_{\circ }(w(\theta ),w(\phi ) )$ för en binär anslutning $\circ ,$
$w(\neg \theta )=F_{\neg }(w(\theta )),$
$w\left({\overline {0}}\right)=0$ och $w\left({\overline {1}}\right )=1,$

och där definitionerna av verksamheten gäller enligt följande:

Implikation: $F_{\rightarrow }(x,y)=\min\{1,1-x+y\}$
Ekvivalens: $F_{\leftrightarrow }(x,y)=1-|xy|$
Negation: $F_{\neg }(x)=1-x$
Svag konjunktion: $F_{\wedge }(x,y)=\min\{x,y\}$
Svag disjunktion: $F_{\vee }(x,y)=\max\{x,y\}$
Stark konjunktion: $F_{\otimes }(x,y)=\max\{0,x+y-1\}$
Stark disjunktion: $F_{\oplus }(x,y)=\min\{1,x+y\}.$

Sanningsfunktionen $F_{\otimes }$ av stark konjunktion är Łukasiewicz t-norm och sanningsfunktionen $F_{\oplus }$ av stark disjunktion är dess dubbla t-konorm . Uppenbarligen är $F_{\otimes }(.5,.5)=0$ och $F_{\oplus } (.5,.5)=1$ , så om $T(p)=.5$ så är $T(p\wedge p)=T(\neg p\wedge \neg p)=0$ medan respektive logiskt ekvivalenta propositioner har $T(p\vee p)=T(\neg p\vee \neg p)=1$ .

Sanningsfunktionen $F_{\rightarrow }$ är resten av Łukasiewicz t-normen. Alla sanningsfunktioner hos de grundläggande kopplingarna är kontinuerliga.

Per definition är en formel en tautologi av oändligt värderad Łukasiewicz-logik om den utvärderas till 1 under varje värdering av propositionella variabler med reella tal i intervallet [0, 1].

Finit-värderad och räknebar-värderad semantik

Genom att använda exakt samma värderingsformler som för verkligt värderad semantik definierade Łukasiewicz (1922) också (upp till isomorfism) semantik över

valfri ändlig uppsättning av kardinalitet n ≥ 2 genom att välja domänen som { 0, 1/( n − 1), 2/( n − 1), ..., 1 }
någon räknebar uppsättning genom att välja domänen som { p / q | 0 ≤ p ≤ q där p är ett icke-negativt heltal och q är ett positivt heltal }.

Allmän algebraisk semantik

Den standardmässiga verkliga semantiken som bestäms av Łukasiewicz t-norm är inte den enda möjliga semantiken i Łukasiewicz logik. Allmän algebraisk semantik av propositionell oändligt värderad Łukasiewicz-logik bildas av klassen av alla MV-algebror . Den vanliga verkliga semantiken är en speciell MV-algebra, kallad standard MV-algebra .

Liksom andra t-norms fuzzy logiker , åtnjuter propositionell oändligt värderad Łukasiewicz-logik fullständighet med avseende på klassen av alla algebror för vilka logiken är sund (det vill säga MV-algebror) såväl som med avseende på endast linjära. Detta uttrycks av de allmänna, linjära och standardfullhetssatserna:

Följande villkor är likvärdiga:

$A$ är bevisbar i propositionell Łukasiewicz logik med oändligt värde
$A$ är giltig i alla MV-algebror ( allmän fullständighet )
$A$ är giltig i alla linjärt ordnade MV-algebror ( linjär fullständighet )
$A$ är giltig i standard MV-algebra ( standardfullständighet) .

Här värderas giltiga medel nödvändigtvis till 1 .

Font, Rodriguez och Torrens introducerade 1984 Wajsberg-algebra som en alternativ modell för den oändligt värderade Łukasiewicz-logiken.

₀ Ett försök från 1940-talet av Grigore Moisil att tillhandahålla algebraisk semantik för den n -värdade Łukasiewicz-logiken med hjälp av hans Łukasiewicz–Moisil (LM) algebra (som Moisil kallade Łukasiewicz algebras ) visade sig vara en felaktig modell för n ≥ 5. offentliggjordes av Alan Rose 1956. CC Changs MV-algebra, som är en modell för den ℵ -värderade (oändligt många värderade) Łukasiewicz–Tarski-logiken, publicerades 1958. För den axiomatiskt mer komplicerade (ändliga) n- värderade Łukasiewicz logiker, lämpliga algebror publicerades 1977 av Revaz Grigolia och kallades MV _n -algebror. MV _n -algebror är en underklass av LM _n -algebror, och inkluderingen är strikt för n ≥ 5. 1982 publicerade Roberto Cignoli några ytterligare begränsningar som lagts till LM _n -algebror producerar korrekta modeller för n -värderad Łukasiewicz logik; Cignoli kallade sin upptäckt för Łukasiewicz algebras .

Komplexitet

Łukasiewicz logik är co-NP komplett .

Modal logik

Łukasiewicz logik kan ses som modal logik med de definierade operatorerna,

${\begin{aligned}\Diamond A&=_{def}\neg A\rightarrow A\\\Box A&=_ {def}\neg \Diamond \neg A\\\end{aligned}}$

En tredje tveksam operator har föreslagits, $\odot A=_{def}A\leftrightarrow \neg A$ .

Från dessa kan vi bevisa följande satser, som är vanliga axiom i många modala logiker :

${\begin {aligned}A&\rightarrow \Diamond A\\\Box A&\rightarrow A\\A&\rightarrow (A\rightarrow \Box A)\\\Box (A\rightarrow B)&\rightarrow (\Box A\rightarrow \ Ruta B)\\\Box (A\högerpil B)&\högerpil (\Diamond A\rightarrow \Diamond B)\\\end{aligned}}$

Vi kan också bevisa fördelningssatser om de starka bindemedlen:

$\ displaystyle {\begin{aligned}\Box (A\otimes B)&\leftrightarrow \Box A\otimes \Box B\\\Diamond (A\oplus B)&\leftrightarrow \Diamond A\oplus \Diamond B\\\ Diamant (A\otimes B)&\rightarrow \Diamond A\otimes \Diamond B\\\Box A\oplus \Box B&\rightarrow \Box (A\oplus B)\end{aligned}}}$

Men följande fördelningssatser gäller också:

$_ displaystyle {\begin{aligned}\Box A\vee \Box B&\leftrightarrow \Box (A\vee B)\\\Box A\wedge \Box B&\leftrightarrow \Box (A\wedge B)\\\Diamond A \vee \Diamond B&\leftrightarrow \Diamond (A\vee B)\\\Diamond A\wedge \Diamond B&\leftrightarrow \Diamond (A\wedge B)\end{aligned}}}$

Med andra ord, om $\Diamond A\wedge \Diamond \neg A$ , då $\Diamond (A\wedge \neg A)$ , vilket är kontraintuitivt. Emellertid har dessa kontroversiella teorem försvarats som en modal logik om framtida kontingenter av AN Prior . Särskilt $\Diamond A\wedge \Diamond \neg A\leftrightarrow \odot A$ .

^ Łukasiewicz J., 1920, O logice trójwartościowej (på polska). Ruch filozoficzny 5 :170–171. Engelsk översättning: On three-valued logic, i L. Borkowski (red.), Selected works by Jan Łukasiewicz , North–Holland, Amsterdam, 1970, s. 87–88. ISBN 0-7204-2252-3
^ Hay, LS, 1963, Axiomatization of the infinite-valued predicate calculus . Journal of Symbolic Logic 28 :77–86.
^ Lavinia Corina Ciungu (2013). Icke-kommutativa logiska algebror med flera värden . Springer. sid. vii. ISBN 978-3-319-01589-7 . citerar Łukasiewicz, J., Tarski, A.: Untersuchungen über den Aussagenkalkül . Comp. Rämna. Soc. Sci. et Lettres Varsovie Cl. III 23, 30–50 (1930).
^ ^a ^b Hájek P. , 1998, Metamathematics of Fuzzy Logic . Dordrecht: Kluwer.
^ Ono, H., 2003, "Substructural logics and rested lattices - an introduction". I FV Hendricks, J. Malinowski (red.): Trends in Logic: 50 Years of Studia Logica, Trends in Logic 20 : 177–212.
^ A. Avron, "Natural 3-valued Logics– Characterization and Proof Theory", Journal of Symbolic Logic 56(1), doi:10.2307/2274919
^ A. Prijateli, "Bounded contraction and Gentzen-style formulering of Łukasiewicz logics", Studia Logica 57: 437-456, 1996
^ A. Ciabattoni, DM Gabbay, N. Olivetti, "Cut-free proof system for logics of weak excluded middle" Soft Computing 2 (1999) 147—156
^ N. Olivetti, "Tableaux for Łukasiewicz Infinite-valued Logic", Studia Logica volym 73, sidorna 81–111 (2003)
^ http://journal.univagora.ro/download/pdf/28.pdf med hänvisning till JM Font, AJ Rodriguez, A. Torrens, Wajsberg Algebras, Stochastica, VIII, 1, 5-31, 1984
^ Lavinia Corina Ciungu (2013). Icke-kommutativa logiska algebror med flera värden . Springer. s. vii–viii. ISBN 978-3-319-01589-7 . citerar Grigolia, RS: "Algebraisk analys av Lukasiewicz-Tarskis n-värderade logiska system". I: Wójcicki, R., Malinkowski, G. (red.) Selected Papers on Lukasiewicz Sentential Calculi, s. 81–92. Polska vetenskapsakademin, Wroclav (1977)
^ Iorgulescu, A.: Anslutningar mellan MV _n -algebras och n -värderade Łukasiewicz–Moisil algebras Del I. Diskret matematik 181, 155–177 (1998) doi : 10.1016/S0012-3605X(527)
^ R. Cignoli, Proper n -Valued Łukasiewicz Algebras as S-Algebras of Łukasiewicz n -Valued Propositional Calculi, Studia Logica, 41, 1982, 3-16, doi : 10.1007/BF0037349
^ A. Ciabattoni, M. Bongini och F. Montagna, bevissökning och Co-NP-fullständighet för logik med många värden. Fuzzy uppsättningar och system .
^ Clarence Irving Lewis och Cooper Harold Langford. Symbolisk logik. Dover, New York, andra upplagan, 1959.
^ Robert Bull och Krister Segerberg. Grundläggande modal logik. I Dov M. Gabbay och Franz Guenthner, redaktörer, Handbook of Philosophical Logic, volym 2. D. Reidel Publishing Company, Lancaster, 1986
^ Alasdair Urquhart . En tolkning av mångvärdig logik. Zeitschr. f. matematik. Logik und Grundlagen d. Math., 19:111–114, 1973.
^ AN Före. Trevärdig logik och framtida kontingenter. 3(13):317–26, oktober 1953.

Vidare läsning

₀ Rose, A.: 1956, Formalization du Calcul Propositionnel Implicatif ℵ Valeurs de Łukasiewicz, CR Acad. Sci. Paris 243, 1183–1185.
₀ Rose, A.: 1978, Formalisations of Further ℵ -Valued Łukasiewicz Propositional Calculi, Journal of Symbolic Logic 43(2), 207–210. doi : 10.2307/2272818
Cignoli, R., "The algebras of Lukasiewicz mångvärdig logik - En historisk översikt," i S. Aguzzoli et al. (Eds.), Algebraic and Proof-theoretic Aspects of Non-classical Logics, LNAI 4460, Springer, 2007 69-83. doi : 10.1007/978-3-540-75939-3_5

[Luk1920-1] Łukasiewicz J., 1920, O logice trójwartościowej (på polska). Ruch filozoficzny 5 :170–171. Engelsk översättning: On three-valued logic, i L. Borkowski (red.), Selected works by Jan Łukasiewicz , North–Holland, Amsterdam, 1970, s. 87–88. ISBN 0-7204-2252-3

[Hay1963-2] Hay, LS, 1963, Axiomatization of the infinite-valued predicate calculus . Journal of Symbolic Logic 28 :77–86.

[Ciungu2013-3] Lavinia Corina Ciungu (2013). Icke-kommutativa logiska algebror med flera värden . Springer. sid. vii. ISBN 978-3-319-01589-7 . citerar Łukasiewicz, J., Tarski, A.: Untersuchungen über den Aussagenkalkül . Comp. Rämna. Soc. Sci. et Lettres Varsovie Cl. III 23, 30–50 (1930).

[Hájek1998-4] Hájek P. , 1998, Metamathematics of Fuzzy Logic . Dordrecht: Kluwer.

[Ono2003-5] Ono, H., 2003, "Substructural logics and rested lattices - an introduction". I FV Hendricks, J. Malinowski (red.): Trends in Logic: 50 Years of Studia Logica, Trends in Logic 20 : 177–212.

[6] A. Avron, "Natural 3-valued Logics– Characterization and Proof Theory", Journal of Symbolic Logic 56(1), doi:10.2307/2274919

[7] A. Prijateli, "Bounded contraction and Gentzen-style formulering of Łukasiewicz logics", Studia Logica 57: 437-456, 1996

[8] A. Ciabattoni, DM Gabbay, N. Olivetti, "Cut-free proof system for logics of weak excluded middle" Soft Computing 2 (1999) 147—156

[9] N. Olivetti, "Tableaux for Łukasiewicz Infinite-valued Logic", Studia Logica volym 73, sidorna 81–111 (2003)

[10] ttp://journal.univagora.ro/download/pdf/28.pdf med hänvisning till JM Font, AJ Rodriguez, A. Torrens, Wajsberg Algebras, Stochastica, VIII, 1, 5-31, 1984

[Ciungu2013bis-11] Lavinia Corina Ciungu (2013). Icke-kommutativa logiska algebror med flera värden . Springer. s. vii–viii. ISBN 978-3-319-01589-7 . citerar Grigolia, RS: "Algebraisk analys av Lukasiewicz-Tarskis n-värderade logiska system". I: Wójcicki, R., Malinkowski, G. (red.) Selected Papers on Lukasiewicz Sentential Calculi, s. 81–92. Polska vetenskapsakademin, Wroclav (1977)

[12] Iorgulescu, A.: Anslutningar mellan MV _n -algebras och n -värderade Łukasiewicz–Moisil algebras Del I. Diskret matematik 181, 155–177 (1998) doi : 10.1016/S0012-3605X(527)

[13] R. Cignoli, Proper n -Valued Łukasiewicz Algebras as S-Algebras of Łukasiewicz n -Valued Propositional Calculi, Studia Logica, 41, 1982, 3-16, doi : 10.1007/BF0037349

[14] A. Ciabattoni, M. Bongini och F. Montagna, bevissökning och Co-NP-fullständighet för logik med många värden. Fuzzy uppsättningar och system .

[15] Clarence Irving Lewis och Cooper Harold Langford. Symbolisk logik. Dover, New York, andra upplagan, 1959.

[16] Robert Bull och Krister Segerberg. Grundläggande modal logik. I Dov M. Gabbay och Franz Guenthner, redaktörer, Handbook of Philosophical Logic, volym 2. D. Reidel Publishing Company, Lancaster, 1986

[17] Alasdair Urquhart . En tolkning av mångvärdig logik. Zeitschr. f. matematik. Logik und Grundlagen d. Math., 19:111–114, 1973.

[18] AN Före. Trevärdig logik och framtida kontingenter. 3(13):317–26, oktober 1953.

Icke-klassisk logik
Intuitionistisk	Intuitionistisk logik Konstruktiv analys Heyting aritmetik Intuitionistisk typteori Konstruktiv mängdlära
Suddig	Grad av sanning Luddrig regel Luddigt set Fuzzy finita element Luddiga setoperationer
Substrukturell	Strukturell regel Relevanslogik Linjär logik
Parakonsekvent	Dialeteism
Beskrivning	Ontologi (datavetenskap) Ontologispråk
Många värderade	Trevärdig Fyrvärdig Łukasiewicz
Digital logik	Tretillståndslogik Tretillståndsbuffert Verilog med fyra värden IEEE 1164 VHDL
Andra	Dynamisk semantik Nyfiken logik Mellanlogik Modal logik Ickemonotonisk logik