Algebraisk logik - Algebraic logic

I matematisk logik er algebraisk logik ræsonnementet opnået ved at manipulere ligninger med frie variabler .

Det, der nu normalt kaldes klassisk algebraisk logik, fokuserer på identifikation og algebraisk beskrivelse af modeller, der er egnede til undersøgelse af forskellige logikker (i form af klasser af algebraer, der udgør den algebraiske semantik for disse deduktive systemer ) og forbundne problemer som repræsentation og dualitet. Kendte resultater som repræsentationsteoremet for boolske algebraer og stendualitet falder ind under paraplyen af ​​klassisk algebraisk logik ( Czelakowski 2003 ).

Arbejder i den nyere abstrakte algebraiske logik (AAL) fokuserer på selve algebraiseringsprocessen, ligesom at klassificere forskellige former for algebraiserbarhed ved hjælp af Leibniz -operatoren ( Czelakowski 2003 ).

Beregning af relationer

En homogen binær forhold findes i magt sæt af X × X for nogle sæt X , mens en heterogen forhold findes i strømmen sæt X × Y , hvor X ≠ Y . Om en given relation gælder for to individer er en smule information, så relationer studeres med boolsk regning. Elementer i kraftsættet er delvist ordnet ved inklusion , og gitter af disse sæt bliver til en algebra gennem relativ multiplikation eller sammensætning af relationer .

"De grundlæggende operationer er sætteoretisk forening, skæringspunkt og komplementering, den relative multiplikation og konvertering."

Den konvertering refererer til den omvendte forhold , der altid eksisterer, i modsætning til funktion teori. En given relation kan repræsenteres ved en logisk matrix ; derefter er den omvendte relation repræsenteret af transponeringsmatricen . En relation opnået som sammensætningen af ​​to andre repræsenteres derefter ved den logiske matrix opnået ved matrixmultiplikation ved hjælp af boolsk regning.

Eksempel

Et eksempel på forholdsregning opstår i erotetik , teorien om spørgsmål. I det univers af ytringer der er udsagn S og spørgsmål Q . Der er to relationer π og α fra Q til S : q α a holder, når a er et direkte svar på spørgsmål q . Den anden relation, q π p , når p er en forudsætning for spørgsmål q . Det omvendte forhold π ^T løber fra S til Q , således at sammensætningen π ^T , α er et homogent forhold på S . Kunsten at stille det rigtige spørgsmål for at fremkalde et tilstrækkeligt svar genkendes i dialog med socratisk metode .

Funktioner

Beskrivelsen af ​​de centrale binære forholdsegenskaber er formuleret med beregningen af ​​relationer. Funktionernes univalens -egenskab beskriver en relation, der opfylder formlen, hvor er identitetsrelationen i intervallet . Injektionsegenskaben svarer til univalens af eller formlen, hvor denne gang er identiteten på domænet . ${\ displaystyle R}$${\ displaystyle R^{T} R \ subseteq I,}$${\ displaystyle I}$${\ displaystyle R}$${\ displaystyle R^{T}}$${\ displaystyle RR^{T} \ subseteq I,}$${\ displaystyle I}$${\ displaystyle R}$

Men en univalent relation er kun en delvis funktion , mens en univalent total relation er en funktion . Formlen for totalitet er Charles Loewner og Gunther Schmidt bruger udtrykket kortlægning for en total, ensartet relation. ${\ displaystyle I \ subseteq RR^{T}.}$

Faciliteten af komplementære relationer inspirerede Augustus De Morgan og Ernst Schröder til at indføre ækvivalenser ved hjælp af relationens komplement . Disse ækvivalenser giver alternative formler for univalente relationer ( ) og totale relationer ( ). Derfor tilfredsstiller kortlægninger formlen Schmidt bruger dette princip som "at glide under negationen fra venstre". Til en kortlægning${\ displaystyle {\ bar {R}}}$${\ displaystyle R}$${\ displaystyle R {\ bar {I}} \ subseteq {\ bar {R}}}$${\ displaystyle {\ bar {R}} \ subseteq R {\ bar {I}}}$${\ displaystyle {\ bar {R}} = R {\ bar {I}}.}$${\ displaystyle f, \ quad f {\ bar {A}} = {\ overline {fA}}.}$

Abstraktion

Den relation algebra struktur, der er baseret i mængdelære, blev overskredet ved Tarski med aksiomer, der beskriver det. Derefter spurgte han, om hver algebra, der opfylder aksiomerne, kunne repræsenteres af en bestemt relation. Det negative svar åbnede grænsen for abstrakt algebraisk logik .

Algebras som modeller for logik

Algebraisk logik behandler algebraiske strukturer , ofte afgrænsede gitter , som modeller (fortolkninger) af visse logikker , hvilket gør logik til en gren af ordensteori .

I algebraisk logik:

• Variabler er stiltiende universelt kvantificeret over et eller andet diskursunivers . Der er ingen eksistentielt kvantificerede variabler eller åbne formler ;
• Termer er opbygget af variabler ved hjælp af primitive og definerede operationer . Der er ingen forbindelser ;
• Formler , der er bygget ud fra udtryk på den sædvanlige måde, kan sidestilles med, hvis de er logisk ækvivalente . For at udtrykke en tautologi skal du sidestille en formel med en sandhedsværdi ;
• Bevisereglerne er substitution af lig med ligemænd og ensartet udskiftning. Modus ponens forbliver gyldig, men bruges sjældent.

I tabellen herunder indeholder den venstre kolonne et eller flere logiske eller matematiske systemer, og den algebraiske struktur, der er dens modeller, er vist til højre i samme række. Nogle af disse strukturer er enten boolske algebraer eller korrekte udvidelser deraf. Modal og andre ikke -klassiske logikker er typisk modelleret efter det, der kaldes "boolske algebraer med operatorer."

Algebraiske formalismer, der går ud over førsteordens logik i mindst nogle henseender, omfatter:

• Kombinerende logik , der har sætteoriens udtryksfulde kraft ;
• Relationsalgebra , uden tvivl den paradigmatiske algebraiske logik, kan udtrykke Peano -aritmetiske og mest aksiomatiske sætteorier , herunder den kanoniske ZFC .

Logisk system	Lindenbaum – Tarski algebra
Klassisk følelsesmæssig logik	Boolsk algebra
Intuitionistisk propositionel logik	Heyting algebra
Łukasiewicz logik	MV-algebra
Modal logik K	Modal algebra
Lewis 's S4	Indvendig algebra
Lewis S5 , monadisk prædikatlogik	Monadisk boolsk algebra
Første ordens logik	Komplet boolsk algebra , polyadisk algebra , prædikatfunktorlogik
Første ordens logik med lighed	Cylindrisk algebra
Sætteori	Kombinerende logik , relation algebra

Historie

Algebraisk logik er måske den ældste tilgang til formel logik, der sandsynligvis begynder med en række notater, Leibniz skrev i 1680'erne, hvoraf nogle blev udgivet i det 19. århundrede og oversat til engelsk af Clarence Lewis i 1918. Men næsten alle Leibniz's kendt arbejde om algebraisk logik blev kun udgivet i 1903 efter Louis Couturat opdagede det i Leibniz's Nachlass . Parkinson (1966) og Loemker (1969) oversatte udvalg fra Couturats bind til engelsk.

Moderne matematisk logik begyndte i 1847 med to pjecer, hvis respektive forfattere var George Boole og Augustus De Morgan . I 1870 udgav Charles Sanders Peirce det første af flere værker om slægtningers logik . Alexander Macfarlane udgav sine principper for logisk algebra i 1879, og i 1883 udgav Christine Ladd , studerende ved Peirce ved Johns Hopkins University , "On the Logic Algebra". Logik blev mere algebraisk, når binære relationer blev kombineret med sammensætning af relationer . For sæt A og B , blev forbindelserne først forstås som elementer af magt sæt af A × B med egenskaber beskrevet af Boolean algebra . "Relationsberegningen" er uden tvivl kulminationen på Leibniz's tilgang til logik. På Hochschule Karlsruhe blev forholdet beregnet af Ernst Schröder . Især formulerede han Schröder -regler , selvom De Morgan havde forudset dem med sin sætning K.

"Boole -Schröder algebra of logic" blev udviklet ved University of California, Berkeley i en lærebog af Clarence Lewis i 1918. Han behandlede logikken i relationer som afledt af forslagets funktioner for to eller flere variabler.

Hugh MacColl , Gottlob Frege , Giuseppe Peano , Bertrand Russell og AN Whitehead delte alle Leibnizs drøm om at kombinere symbolsk logik , matematik og filosofi .

Nogle skrifter af Leopold Löwenheim og Thoralf Skolem om algebraisk logik dukkede op efter udgivelsen af Principia Mathematica fra 1910–13 , og Tarski genoplivede interessen for forholdet med sit essay fra 1941 "On the Calculus of Relations".

Ifølge Helena Rasiowa , "Årene 1920-40 så, især i den polske logiske skole, forsker i ikke-klassiske propositionelle beregninger udført af det, der kaldes den logiske matrixmetode . Da logiske matricer er visse abstrakte algebraer, førte dette til brugen af ​​en algebraisk metode i logik. "

Brady (2000) diskuterer de rige historiske forbindelser mellem algebraisk logik og modelteori . Grundlæggerne af modelteorien, Ernst Schröder og Leopold Loewenheim, var logikere i den algebraiske tradition. Alfred Tarski , grundlæggeren af sætteoretisk modelteori som en vigtig gren af ​​nutidig matematisk logik, også:

• Påbegyndt abstrakt algebraisk logik med relation algebraer
• Opfundet cylindrisk algebra
• Co-opdagede Lindenbaum-Tarski algebra .

I praksis med relationens beregning brugte Jacques Riguet den algebraiske logik til at fremme nyttige begreber: han udvidede begrebet ækvivalensforhold (på et sæt) til heterogene forhold til det difunktionelle begreb. Riguet også udvidet bestilling til den heterogene kontekst ved sit notat, at en trappe logisk matrix har et supplement, der er også en trappe, og at sætningen af NM Ferrers følger fortolkningen af transponerede af en trappe. Riguet genererede rektangulære relationer ved at tage det ydre produkt af logiske vektorer; disse bidrager til de ikke-udvidelige rektangler i formel konceptanalyse .

Leibniz havde ingen indflydelse på stigningen i algebraisk logik, fordi hans logiske skrifter var lidt undersøgt før Parkinson- og Loemker -oversættelserne. Vores nuværende forståelse af Leibniz som logiker stammer hovedsageligt fra Wolfgang Lenzens arbejde, opsummeret i Lenzen (2004) . For at se, hvordan nutidens arbejde inden for logik og metafysik kan hente inspiration fra og kaste lys over Leibniz 'tanke, se Zalta (2000) .

Se også

• Boolsk algebra
• Torskens sætning
• Computer algebra
• Universal algebra

Referencer

Kilder

• Brady, Geraldine (2000). Fra Peirce til Skolem: Et forsømt kapitel i logikkens historie . Amsterdam, Holland: North-Holland/Elsevier Science BV. Arkiveret fra originalen 2009-04-02 . Hentet 2009-05-15 .
• Czelakowski, Janusz (2003). "Anmeldelse: Algebraiske metoder i filosofisk logik af J. Michael Dunn og Gary M. Hardegree". Bulletinen om symbolsk logik . Association for Symbolic Logic, Cambridge University Press. 9 . ISSN  1079-8986 . JSTOR  3094793 .
• Lenzen, Wolfgang, 2004, " Leibniz's Logic " i Gabbay, D., og Woods, J., red., Handbook of the History of Logic, bind. 3: The Rise of Modern Logic fra Leibniz til Frege . Nordholland: 1-84.
• Loemker, Leroy (1969) [Første udgave 1956], Leibniz: Philosophical Papers and Letters (2. udgave), Reidel.
• Parkinson, GHR (1966). Leibniz: Logiske papirer . Oxford University Press.
• Zalta, EN, 2000, " A (Leibnizian) Theory of Concepts ", Philosophiegeschichte und logische Analyze / Logical Analysis and History of Philosophy 3: 137-183.

Yderligere læsning

• J. Michael Dunn; Gary M. Hardegree (2001). Algebraiske metoder i filosofisk logik . Oxford University Press. ISBN 978-0-19-853192-0.God introduktion til læsere med forudgående eksponering for ikke-klassisk logik, men uden megen baggrund i rækkefølge teori og/eller universel algebra; bogen dækker disse forudsætninger i længden. Denne bog er imidlertid blevet kritiseret for dårlig og til tider forkert fremstilling af AAL -resultater. Anmeldelse af Janusz Czelakowski
• Hajnal Andréka , István Németi og Ildikó Sain (2001). "Algebraisk logik". I Dov M. Gabbay, Franz Guenthner (red.). Handbook of Philosophical Logic, bind 2 (2. udgave). Springer. ISBN 978-0-7923-7126-7. Udkast .
• Ramon Jansana (2011), " Propositional Consequence Relations and Algebraic Logic ". Stanford Encyclopedia of Philosophy. Hovedsageligt om abstrakt algebraisk logik.
• Stanley Burris (2015), " The Algebra of Logic Tradition ". Stanford Encyclopedia of Philosophy.
• Willard Quine , 1976, "Algebraic Logic and Predicate Functors" side 283 til 307 i The Ways of Paradox , Harvard University Press .

Historisk perspektiv

• Ivor Grattan-Guinness , 2000. Søgningen efter matematiske rødder . Princeton University Press.
• IH Anellis & N. Houser (1991) "Nineteenth Century Roots of Algebraic Logic and Universal Algebra", side 1–36 i Algebraic Logic , Colloquia Mathematica Societatis János Bolyai # 54, János Bolyai Mathematical Society & Elsevier ISBN  0444885439

eksterne links

• Medier relateret til algebraisk logik på Wikimedia Commons