Logika aljabar

Dalam logika matematika, logika aljabar adalah penalaran yang diperoleh melalui memanipulasi persamaan-persamaan yang memiliki peubah bebas.

Kajian logika aljabar klasik saat ini fokus kepada identifikasi dan deskripsi aljabar dari model yang digunakan dalam studi logika (dalam bentuk kelas aljabar yang membentuk semantik aljabar untuk sistem deduktif ini) dan masalah-masalah yang berkaitan seperti dalam hal representasi dan dualitas. Logika aljabar klasik sebelumnya menghasilkan teori seperti teorema representasi untuk aljabar Boolean dan dualitas Stone.^[1]

Penelitian dalam logika aljabar abstrak (abstract algebraic logic; AAL) terkini berfokus pada proses aljabarisasi itu sendiri, seperti mengklasifikasikan berbagai bentuk aljabar menggunakan operator Leibniz.^[1]

Relasi biner homogen ditemukan dalam himpunan kuasa X × X untuk beberapa himpunan X, sementara relasi heterogen ditemukan dalam himpunan kuasa X × Y, dengan X ≠ Y.. Dalam aritmetika boolean, relasi tertentu berlaku untuk dua individu adalah termasuk dalam satu bit informasi. Elemen-elemen himpunan kuasa diurutkan sebagian dengan cara inklusi, dan kekisi himpunan ini menjadi suatu aljabar melalui perkalian relatif atau komposisi relasi.

“Operasi dasar yang dilakukan adalah gabungan teori himpunan, irisan dan komplementasi, perkalian relatif, dan konversi.”^[2]

Konversi mengacu pada hubungan sebalik yang selalu ada, bertentangan dengan teori fungsi. Suatu relasi tertentu dapat direpresentasikan oleh matriks logika, sedangkan relasi kebalikannya direpresentasikan oleh matriks transpos . Suatu relasi yang diperoleh sebagai komposisi dua relasi lainnya kemudian direpresentasikan oleh matriks logika yang diperoleh melalui perkalian matriks menggunakan aritmetika Boolean.

Contoh kalkulus hubungan muncul dalam teori pertanyaan (erotetics, erotetika). Dalam semesta ujaran terdapat pernyataan ${\displaystyle S}$ dan pertanyaan ${\displaystyle Q}$. Terdapat dua relasi ${\displaystyle \pi }$ dan ${\displaystyle \alpha }$ dari ${\displaystyle Q}$ ke ${\displaystyle S}$: ${\displaystyle q\alpha a}$ berlaku ketika a merupakan jawaban langsung untuk pertanyaan q . Relasi lainnya, ${\displaystyle q\pi p}$berlaku ketika p merupakan praanggapan dari pertanyaan q. Relasi sebalik ${\displaystyle \pi ^{T}}$berjalan dari ${\displaystyle S}$ ke ${\displaystyle Q}$ sehingga komposisi ${\displaystyle \pi ^{T}\alpha }$ merupakan relasi homogen pada ${\displaystyle S}$.^[3] Seni mengajukan pertanyaan yang tepat untuk memperoleh jawaban yang cukup diakui dalam dialog metode Sokrates .

Deskripsi sifat-sifat relasi biner utama dirumuskan dengan kalkulus relasi. Sifat univalensi fungsi menggambarkan relasi R yang memenuhi rumus ${\displaystyle R^{T}R\subseteq I,}$ dengan I adalah relasi identitas pada rentang R. Sifat injektif sesuai dengan univalensi ${\displaystyle R^{T}}$, atau rumus ${\displaystyle RR^{T}\subseteq I,}$ dengan I adalah identitas pada domain R

Namun relasi univalen hanya merupakan fungsi parsial, sedangkan relasi total univalen adalah fungsi. Rumus untuk totalitas adalah ${\displaystyle I\subseteq RR^{T}.}$ Charles Loewner dan Gunther Schmidt menggunakan istilah pemetaan untuk hubungan total dan univalen.^[4][5]

Hubungan komplementer merupakan dasar bagi Augustus De Morgan dan Ernst Schröder untuk memperkenalkan teori kesetaraan menggunakan ${\displaystyle {\bar {R}}}$ untuk melengkapi relasi R. Kesetaraan ini memberikan rumus alternatif untuk relasi univalen ( ${\displaystyle R{\bar {I}}\subseteq {\bar {R}}}$ ), dan total hubungan ( ${\displaystyle {\bar {R}}\subseteq R{\bar {I}}}$ ). Oleh karena itu, pemetaan memenuhi rumus ${\displaystyle {\bar {R}}=R{\bar {I}}.}$ Schmidt menggunakan prinsip ini sebagai "menyelinap di bawah negasi dari kiri".^[6] Untuk pemetaan f, ${\displaystyle f{\bar {A}}={\overline {fA}}.}$

Struktur aljabar relasi, yang didasarkan pada teori himpunan, diubah menjadi transenden oleh Tarski dengan aksioma yang menggambarkannya. Kemudian muncul pertanyaan apakah setiap aljabar yang memenuhi aksioma dapat direpresentasikan oleh suatu relasi himpunan. Jawaban negatif ^[7] membuka batas logika aljabar abstrak.^[8][9][10]

Logika aljabar memperlakukan struktur aljabar, sering kali kekisi terbatas, sebagai model (interpretasi) dari logika tertentu, menjadikan logika sebagai cabang teori tatanan.

Dalam logika aljabar:

• Variabel-variabel secara diam-diam dikuantifikasi secara universal pada beberapa jagat wacana. Tidak ada variabel yang dikuantifikasi secara eksistensial atau rumus terbuka;
• Istilah dibangun dari variabel menggunakan operasi primitif dan terdefinisi. Tidak ada kata hubung;
• Rumus yang dibangun dari istilah-istilah dengan cara biasa dapat disamakan jika secara logika ekuivalen. Untuk menyatakan tautologi, samakan suatu rumus dengan nilai kebenaran;
• Aturan pembuktiannya adalah substitusikan yang sama dengan yang sama, dan penggantian seragam. Modus ponens tetap berlaku, tetapi jarang digunakan.

Pada tabel di bawah, kolom kiri berisi satu atau lebih sistem logika atau matematika, dan struktur aljabar yang merupakan modelnya ditunjukkan di sebelah kanan dalam baris yang sama. Beberapa struktur ini merupakan aljabar Boolean atau perluasan yang tepat darinya. Logika modal dan logika nonklasik lainnya biasanya dimodelkan oleh apa yang disebut "aljabar Boolean dengan operator."

Formalisme aljabar yang melampaui logika tingkat pertama setidaknya dalam beberapa hal meliputi:

• Logika kombinasi, memiliki kekuatan ekspresif teori himpunan ;
• Aljabar relasi, yang mungkin merupakan logika aljabar paradigmatik, dapat mengekspresikan aritmetika Peano dan sebagian besar teori himpunan aksiomatik, termasuk ZFC kanonik.

Logika aljabar mungkin merupakan pendekatan tertua terhadap logika formal, yang mungkin dimulai dengan sejumlah memorandum yang ditulis Leibniz pada tahun 1680-an, beberapa di antaranya diterbitkan pada abad ke-19 dan diterjemahkan ke dalam bahasa Inggris oleh Clarence Lewis pada tahun 1918.^[11] Tetapi hampir semua karya Leibniz yang diketahui tentang logika aljabar baru diterbitkan pada tahun 1903 setelah Louis Couturat menemukannya dalam Nachlass karya Leibniz. Parkinson^[12] dan Loemker^[13] menerjemahkan pilihan dari volume Couturat ke dalam bahasa Inggris.

Logika matematika modern dimulai pada tahun 1847, dengan dua karya tulis singkat oleh George Boole^[14] dan Augustus De Morgan.^[15] Pada tahun 1870 Charles Sanders Peirce menerbitkan karya pertama dari beberapa karya tentang logika relatif. Alexander Macfarlane menerbitkan Principles of the Algebra of Logic^[16] pada tahun 1879, dan pada tahun 1883, Christine Ladd, seorang mahasiswa Peirce di Universitas Johns Hopkins, menerbitkan "On the Algebra of Logic".^[17] Logika berubah lebih aljabar ketika relasi biner dikombinasikan dengan komposisi relasi. Untuk himpunan ${\displaystyle A}$ dan ${\displaystyle B}$, relasi atas ${\displaystyle A}$ dan ${\displaystyle B}$ direpresentasikan sebagai anggota himpunan kuasa ${\displaystyle A\times B}$ dengan sifat-sifat yang dijelaskan oleh aljabar Boolean. "Kalkulus relasi" ^[10] disebut merupakan puncak pendekatan Leibniz terhadap logika. Di Hochschule Karlsruhe kalkulus hubungan dijelaskan oleh Ernst Schröder.^[18] Secara khusus ia merumuskan aturan Schröder, meskipun De Morgan telah mengantisipasinya dengan Teorema K.

Pada tahun 1903 Bertrand Russell mengembangkan kalkulus relasi dan logikaisme sebagai versi matematika murni yang berdasarkan operasi kalkulus sebagai gagasan primitif.^[19] "Aljabar logika Boole–Schröder" dikembangkan di Universitas California, Berkeley dalam sebuah buku teks oleh Clarence Lewis pada tahun 1918.^[11] Dia memperlakukan logika hubungan sebagai sesuatu yang diturunkan dari fungsi proposisional dua variabel atau lebih.

Hugh MacColl, Gottlob Frege, Giuseppe Peano, dan AN Whitehead seluruhnya merupakan peneliti yang berbagi visi Leibniz untuk menggabungkan logika simbolik, matematika, dan filsafat.

Beberapa tulisan Leopold Löwenheim dan Thoralf Skolem mengenai logika aljabar muncul setelah publikasi Principia Mathematica pada tahun 1910–13, dan Tarski menghidupkan kembali minat pada relasi dengan esainya pada tahun 1941 "On the Calculus of Relations".^[10]

Menurut Helena Rasiowa, "Tahun 1920-40, khususnya di sekolah logika Polandia, penelitian tentang kalkulus proposisional non-klasik dilakukan dengan apa yang disebut metode matriks logis . Karena matriks logis adalah aljabar abstrak tertentu, hal ini menyebabkan penggunaan metode aljabar dalam logika." ^[20]

Brady discusses the rich historical connections between algebraic logic and model theory.^[21] The founders of model theory, Ernst Schröder and Leopold Loewenheim, were logicians in the algebraic tradition. Alfred Tarski, the founder of set theoretic model theory as a major branch of contemporary mathematical logic, also:

• Memulai logika aljabar abstrak dengan aljabar relasi ^[10]
• Menemukan aljabar silinder
• Menemukan bersama aljabar Lindenbaum–Tarski .

Dalam praktik kalkulus relasi, Jacques Riguet menggunakan logika aljabar untuk memajukan konsep-konsep yang berguna: ia memperluas konsep relasi ekivalensi (pada suatu himpunan) ke kasus heterogen dengan gagasan relasi difungsional. Riguet juga memperluas pengurutan pada konteks heterogen melalui catatannya bahwa matriks logika tangga mempunyai komplemen yang juga merupakan tangga, dan bahwa teorema NM Ferrers mengikuti interpretasi transpos tangga. Riguet menghasilkan hubungan persegi panjang dengan mengambil produk luar vektor logika; ini berkontribusi pada persegi panjang yang tidak dapat diperbesar dalam analisis konsep formal.

Leibniz tidak mempunyai pengaruh terhadap munculnya logika aljabar karena tulisan-tulisan logikanya hanya sedikit dipelajari sebelum terjemahan Parkinson dan Loemker. Pemahaman kita saat ini tentang Leibniz sebagai ahli logika terutama berasal dari karya Wolfgang Lenzen.^[22] Untuk melihat bagaimana karya logika dan metafisika masa kini dapat mengambil inspirasi dari pemikiran Leibniz dan memberikan pencerahan, lihat karya Zalta.^[23]

• Aljabar Boolean
• Aljabar universal

1. ^ ^{a b} Czelakowski, Janusz (2003). "Review of Algebraic Methods in Philosophical Logic". The Bulletin of Symbolic Logic. 9 (2): 231–234. ISSN 1079-8986.
2. ^ Bjarni Jónsson (1984). "Maximal Algebras of Binary Relations". Dalam Kenneth I. Appel; John G. Ratcliffe; Paul E. Schupp (ed.). Contributions to Group Theory. Contemporary Mathematics. Vol. 33. Providence/RI: American Mathematical Society. hlm. 299–307. ISBN 978-0-8218-5035-0.
3. ^ Freeman, Eugene (1934). The Categories of Charles Peirce (dalam bahasa Inggris). Open Court Publishing Company. ISBN 978-0-598-93370-6. Pemeliharaan CS1: Status URL (link)
4. ^ G. Schmidt & T. Ströhlein (1993) Relations and Graphs Discrete Mathematics for Computer Scientists, page 54, EATCS Monographs on Theoretical Computer Science, Springer Verlag, ISBN 3-540-56254-0
5. ^ G. Schmidt (2011) Relational Mathematics, Encyclopedia of Mathematics and its Applications, vol. 132, pages 49 and 57, Cambridge University Press ISBN 978-0-521-76268-7
6. ^ Schmidt, Gunther; Winter, Michael (2018). Relational Topology. Lecture Notes in Mathematics (Edisi 1st ed. 2018). Cham: Springer International Publishing : Imprint: Springer. ISBN 978-3-319-74451-3.
7. ^ Roger C. Lyndon (May 1950). "The representation of Relational Algebras". Annals of Mathematics. 51: 707–729. doi:10.2307/1969375. JSTOR 1969375. MR 0037278.
8. ^ Maddux, Roger D. (1991). "The origin of relation algebras in the development and axiomatization of the calculus of relations". Studia Logica (dalam bahasa Inggris). 50 (3–4): 421–455. doi:10.1007/BF00370681. ISSN 0039-3215.
9. ^ Pratt, Vaughn. Origins of the Calculus of Binary Relations (PDF). Universitas Stanford. Pemeliharaan CS1: Status URL (link)
10. ^ ^{a b c d} Alfred Tarski (1941), "On the Calculus of Relations", Journal of Symbolic Logic 6: 73–89 DOI:10.2307/2268577 Kesalahan pengutipan: Tanda <ref> tidak sah; nama "T41" didefinisikan berulang dengan isi berbeda
11. ^ ^{a b} Lewis, Clarence Irving (1918). A survey of symbolic logic. Robarts - University of Toronto. Berkeley University of California Press.
12. ^ Leibniz, G. W.; Leibniz, Gottfried Wilhelm Freiherr von; Leibniz (1966). Logical Papers (dalam bahasa Inggris). Clarendon P. ISBN 978-0-19-824306-9.
13. ^ Loemker, Leroy E., ed. (1969). Gottfried Wilhelm Leibniz: Philosophical Papers and Letters. Reidel.
14. ^ Boole, George (1847). The Mathematical Analysis of Logic (dalam bahasa Inggris). CreateSpace Independent Publishing Platform. ISBN 978-1-5485-5452-1.
15. ^ "Formal logic ; or, The Calculus of inference, necessary and probable / By Augustus De Morgan". HathiTrust (dalam bahasa Inggris). Diakses tanggal 2025-05-10.
16. ^ Macfarlane, Alexander (1879). Principles of the algerbra of logic. University of California. Edinburgh, D. Douglas.
17. ^ Peirce, Charles Sanders; Marquand, Allan (1883). Studies in Logic (dalam bahasa Inggris). Little, Brown,. Pemeliharaan CS1: Tanda baca tambahan (link)
18. ^ Schröder, Ernst; Lüroth, Jakob; Müller, Karl Eugen; Deutsche Mathematiker-Vereinigung (1890). Vorlesungen über die algebra der logik (exakte logik). University of Michigan. Leipzig, B. G. Teubner.
19. ^ Russell, Bertrand (1903). The Principles Of Mathematics. Universal Digital Library. W. W. Norton & Company. Pemeliharaan CS1: Status URL (link)
20. ^ Helena Rasiowa (1974), "Post Algebras as Semantic Foundations of m-valued Logics", pages 92–142 in Studies in Algebraic Logic, edited by Aubert Daigneault, Mathematical Association of America ISBN 0-88385-109-1
21. ^ Brady, Geraldine (2000). From Peirce to Skolem: a neglected chapter in the history of logic (Edisi 1st ed). Amsterdam: Elsevier. ISBN 978-0-08-053202-8. Pemeliharaan CS1: Status URL (link)
22. ^ Kanamori, Akihiro; Woods, John Hayden; Gabbay, Dov M. (2004). Handbook of the history of logic (Edisi 1st ed). Amsterdam Boston: Elsevier. ISBN 978-0-444-50466-1.
23. ^ Zalta, Edward N. (2000-04-05). "A (Leibnizian) Theory of Concepts". History of Philosophy & Logical Analysis. 3 (1): 137–183. doi:10.30965/26664275-00301008. ISSN 2666-4275.

• Brady, Geraldine (2000). From Peirce to Skolem: A Neglected Chapter in the History of Logic. Studies in the History and Philosophy of Mathematics. Amsterdam, Netherlands: North-Holland/Elsevier Science BV. ISBN 9780080532028.
• Czelakowski, Janusz (2003). "Review: Algebraic Methods in Philosophical Logic by J. Michael Dunn and Gary M. Hardegree". The Bulletin of Symbolic Logic. 9. Association for Symbolic Logic, Cambridge University Press. ISSN 1079-8986. JSTOR 3094793.
• Loemker, Leroy (1969) [First edition 1956], Leibniz: Philosophical Papers and Letters (Edisi 2nd), Reidel.
• Parkinson, G.H.R (1966). Leibniz: Logical Papers. Oxford University Press.

• J. Michael Dunn; Gary M. Hardegree (2001). Algebraic Methods in Philosophical Logic. Oxford University Press. ISBN 978-0-19-853192-0. Good introduction for readers with prior exposure to non-classical logics but without much background in order theory and/or universal algebra; the book covers these prerequisites at length. This book however has been criticized for poor and sometimes incorrect presentation of AAL results. Review by Janusz Czelakowski
• Hajnal Andréka, István Németi and Ildikó Sain (2001). "Algebraic logic". Dalam Dov M. Gabbay, Franz Guenthner (ed.). Handbook of Philosophical Logic, vol 2 (Edisi 2nd). Springer. ISBN 978-0-7923-7126-7. Draft.
• Ramon Jansana (2011), "Propositional Consequence Relations and Algebraic Logic". Stanford Encyclopedia of Philosophy. Mainly about abstract algebraic logic.
• Stanley Burris (2015), "The Algebra of Logic Tradition". Stanford Encyclopedia of Philosophy.
• Willard Quine, 1976, "Algebraic Logic and Predicate Functors" pages 283 to 307 in The Ways of Paradox, Harvard University Press.

Perspektif sejarah

• Ivor Grattan-Guinness, 2000. The Search for Mathematical Roots. Princeton University Press.
• Irving Anellis & N. Houser (1991) "Nineteenth Century Roots of Algebraic Logic and Universal Algebra", pages 1–36 in Algebraic Logic, Colloquia Mathematica Societatis János Bolyai # 54, János Bolyai Mathematical Society & Elsevier ISBN 0444885439