Pembuktian teorema otomatis - Riwayat revisi

Maintenance script: Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

2026-08-24T23:13:01Z

Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi

← Revisi sebelumnya		Revisi per 24 Agustus 2026 23.13
Baris 2:		Baris 2:

	== Landasan logika ==		== Landasan logika ==
	Meskipun akar logika formal dapat ditelusuri kembali ke [[Aristoteles]], akhir abad ke-19 dan awal abad ke-20 menyaksikan perkembangan logika modern dan matematika formal. ''Begriffsschrift'' karya Frege (1879) memperkenalkan baik kalkulus proposisional yang lengkap maupun logika predikat modern pada dasarnya. ''Foundations of Arithmetic'' yang diterbitkan pada 1884 mengekspresikan (sebagian) matematika dalam logika formal. Pendekatan ini dilanjutkan oleh [[Bertrand Russell\|Russell]] dan [[Whitehead]] dalam karya berpengaruh mereka ''[[Principia Mathematica]]'', yang pertama kali diterbitkan antara 1910–1913, dan dengan edisi kedua yang direvisi pada 1927. Russell dan Whitehead percaya bahwa mereka bisa menurunkan semua kebenaran matematika menggunakan aksioma dan aturan inferensi logika formal, yang pada prinsipnya membuka kemungkinan untuk proses otomatisasi.		Meskipun akar logika formal dapat ditelusuri kembali ke [[Aristoteles]], akhir abad ke-19 dan awal abad ke-20 menyaksikan perkembangan logika modern dan matematika formal.<ref>Gottlob (1848-1925) Auteur du texte Frege. [https://gallica.bnf.fr/ark:/12148/bpt6k65658c Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens / von Dr. Gottlob Frege,]. 1879.</ref> ''Begriffsschrift'' karya Frege (1879) memperkenalkan baik kalkulus proposisional yang lengkap maupun logika predikat modern pada dasarnya. ''Foundations of Arithmetic'' yang diterbitkan pada 1884 mengekspresikan (sebagian) matematika dalam logika formal.<ref>[http://www.ac-nancy-metz.fr/enseign/philo/textesph/Frege.pdf Wayback Machine]. ''www.ac-nancy-metz.fr''.</ref> Pendekatan ini dilanjutkan oleh [[Bertrand Russell\|Russell]] dan [[Whitehead]] dalam karya berpengaruh mereka ''[[Principia Mathematica]]'', yang pertama kali diterbitkan antara 1910–1913,<ref>Alfred North Whitehead. [http://archive.org/details/cu31924001575244 Principia mathematica]. Cambridge, University Press. 1910.</ref> dan dengan edisi kedua yang direvisi pada 1927.<ref>Bertrand Russell. [http://archive.org/details/in.ernet.dli.2015.221192 Principia Mathematica Vol Ii]. 1927.</ref> Russell dan Whitehead percaya bahwa mereka bisa menurunkan semua kebenaran matematika menggunakan aksioma dan aturan inferensi logika formal, yang pada prinsipnya membuka kemungkinan untuk proses otomatisasi.

	Pada 1920, Thoralf Skolem menyederhanakan hasil sebelumnya oleh Leopold Löwenheim, yang menghasilkan [[teorema Löwenheim–Skolem]] dan, pada 1930, konsep [[alam semesta Herbrand]] (''Herbrand universe'') dan interpretasi Herbrand (''Herbrand interpretation'') yang memungkinkan ketidakpuasan atau kepuasan formula orde pertama (dan dengan demikian validitas sebuah teorema) direduksi menjadi masalah kepuasan proposisional yang (potensial) tak terbatas.		Pada 1920, Thoralf Skolem menyederhanakan hasil sebelumnya oleh Leopold Löwenheim, yang menghasilkan [[teorema Löwenheim–Skolem]] dan, pada 1930, konsep [[alam semesta Herbrand]] (''Herbrand universe'') dan interpretasi Herbrand (''Herbrand interpretation'') yang memungkinkan ketidakpuasan atau kepuasan formula orde pertama (dan dengan demikian validitas sebuah teorema) direduksi menjadi masalah kepuasan proposisional yang (potensial) tak terbatas.

	Pada 1929, Mojżesz Presburger menunjukkan bahwa teori orde pertama dari bilangan alami dengan operasi penjumlahan dan kesetaraan (yang sekarang disebut [[aritmetika]] [[Presburger]] untuk menghormatinya) dapat diputuskan dan memberikan algoritma yang dapat menentukan apakah suatu kalimat dalam bahasa tersebut benar atau salah.		Pada 1929, Mojżesz Presburger menunjukkan bahwa teori orde pertama dari bilangan alami dengan operasi penjumlahan dan kesetaraan (yang sekarang disebut [[aritmetika]] [[Presburger]] untuk menghormatinya) dapat diputuskan dan memberikan algoritma yang dapat menentukan apakah suatu kalimat dalam bahasa tersebut benar atau salah.<ref>Jacques Herbrand. [https://eudml.org/doc/192791 Recherches sur la théorie de la démonstration]. 1930.</ref><ref>JERZY NEYMAN. [https://doi.org/10.2307/jj.8501421.11 Méthodes nouvelles de vérification des hypothèses]. University of California Press. 2023-11-15. hlm. 35–42. ISBN 978-0-520-32701-6.</ref>

	Namun, tak lama setelah hasil positif ini, [[Kurt Gödel]] menerbitkan ''On Formally Undecidable Propositions of Principia Mathematica and Related Systems'' (1931), yang menunjukkan bahwa dalam sistem aksiomatik yang cukup kuat, terdapat pernyataan yang benar tetapi tidak dapat dibuktikan dalam sistem tersebut. Topik ini kemudian dikembangkan lebih lanjut pada tahun 1930-an oleh Alonzo Church dan [[Alan Turing]], yang di satu sisi memberikan dua definisi komputabilitas yang independen tetapi ekuivalen, dan di sisi lain memberikan contoh konkret dari pertanyaan yang tak dapat diputuskan.		Namun, tak lama setelah hasil positif ini, [[Kurt Gödel]] menerbitkan ''On Formally Undecidable Propositions of Principia Mathematica and Related Systems'' (1931),<ref>Kurt Gödel. [https://philpapers.org/rec/GDEOFU On Formally Undecidable Propositions of Principia Mathematica and Related Systems]. Basic Books. 1931.</ref> yang menunjukkan bahwa dalam sistem aksiomatik yang cukup kuat, terdapat pernyataan yang benar tetapi tidak dapat dibuktikan dalam sistem tersebut. Topik ini kemudian dikembangkan lebih lanjut pada tahun 1930-an oleh Alonzo Church dan [[Alan Turing]], yang di satu sisi memberikan dua definisi komputabilitas yang independen tetapi ekuivalen, dan di sisi lain memberikan contoh konkret dari pertanyaan yang tak dapat diputuskan.<ref>[http://www.cs.nyu.edu/cs/faculty/davism/early.ps Wayback Machine]. ''www.cs.nyu.edu''.</ref>

	== Implementasi pertama ==		== Implementasi pertama ==
	Pada tahun 1954, [[Martin Davis]] memprogram algoritma Presburger untuk komputer tabung vakum JOHNNIAC di ''Institute for Advanced Study'' di [[Princeton, New Jersey]]. Menurut Davis, “Keberhasilan besarnya adalah membuktikan bahwa jumlah dua bilangan genap adalah genap.”		Pada tahun 1954, [[Martin Davis]] memprogram algoritma Presburger untuk komputer tabung vakum JOHNNIAC di ''Institute for Advanced Study'' di [[Princeton, New Jersey]]. Menurut Davis, “Keberhasilan besarnya adalah membuktikan bahwa jumlah dua bilangan genap adalah genap.”<ref>JERZY NEYMAN. [https://doi.org/10.2307/jj.8501421.11 Méthodes nouvelles de vérification des hypothèses]. University of California Press. 2023-11-15. hlm. 35–42. ISBN 978-0-520-32701-6.</ref>

	Lebih ambisius lagi adalah Logic Theorist pada tahun 1956, sebuah sistem deduksi untuk logika proposisional dari ''Principia Mathematica'', yang dikembangkan oleh [[Allen Newell]], [[Herbert Simon\|Herbert A. Simon]], dan [[J. C. Shaw]]. Juga dijalankan pada JOHNNIAC, Logic Theorist menyusun bukti dari sekumpulan kecil aksioma proposisional dan tiga aturan deduksi: ''modus ponens'', substitusi variabel (proposisional), dan penggantian formula dengan definisinya. Sistem ini menggunakan panduan heuristik, dan berhasil membuktikan 38 dari 52 teorema pertama dari ''Principia Mathematica''.		Lebih ambisius lagi adalah Logic Theorist pada tahun 1956, sebuah sistem deduksi untuk logika proposisional dari ''Principia Mathematica'', yang dikembangkan oleh [[Allen Newell]], [[Herbert Simon\|Herbert A. Simon]], dan [[J. C. Shaw]]. Juga dijalankan pada JOHNNIAC, Logic Theorist menyusun bukti dari sekumpulan kecil aksioma proposisional dan tiga aturan deduksi: ''modus ponens'', substitusi variabel (proposisional), dan penggantian formula dengan definisinya. Sistem ini menggunakan panduan heuristik, dan berhasil membuktikan 38 dari 52 teorema pertama dari ''Principia Mathematica''.<ref>Jacques Herbrand. [https://eudml.org/doc/192791 Recherches sur la théorie de la démonstration]. 1930.</ref>

	Pendekatan “[[Heuristika\|heuristik]]” Logic Theorist mencoba meniru cara matematikawan manusia, dan tidak dapat menjamin bahwa bukti dapat ditemukan untuk setiap teorema yang valid, bahkan secara prinsip. Sebaliknya, algoritma lain yang lebih sistematis mampu mencapai, setidaknya secara teoretis, kelengkapan untuk logika orde pertama. Pendekatan awal bergantung pada hasil Herbrand dan Skolem untuk mengubah sebuah formula orde pertama menjadi himpunan formula proposisional yang semakin besar dengan mengganti variabel menggunakan istilah dari alam semesta Herbrand. Formula proposisional tersebut kemudian dapat diperiksa ketidakpuasannya menggunakan berbagai metode. Program Gilmore menggunakan konversi ke bentuk normal disjungtif (''disjunctive normal form''), sebuah bentuk di mana kepuasan suatu formula menjadi jelas.		Pendekatan “[[Heuristika\|heuristik]]” Logic Theorist mencoba meniru cara matematikawan manusia, dan tidak dapat menjamin bahwa bukti dapat ditemukan untuk setiap teorema yang valid, bahkan secara prinsip. Sebaliknya, algoritma lain yang lebih sistematis mampu mencapai, setidaknya secara teoretis, kelengkapan untuk logika orde pertama. Pendekatan awal bergantung pada hasil Herbrand dan Skolem untuk mengubah sebuah formula orde pertama menjadi himpunan formula proposisional yang semakin besar dengan mengganti variabel menggunakan istilah dari alam semesta Herbrand. Formula proposisional tersebut kemudian dapat diperiksa ketidakpuasannya menggunakan berbagai metode. Program Gilmore menggunakan konversi ke bentuk normal disjungtif (''disjunctive normal form''), sebuah bentuk di mana kepuasan suatu formula menjadi jelas.<ref>P. C. Gilmore. [https://ieeexplore.ieee.org/document/5392528/ A Proof Method for Quantification Theory: Its Justification and Realization]. ''IBM Journal of Research and Development''. 1960-01. Vol. 4 (1). hlm. 28–35. doi:10.1147/rd.41.0028.</ref>

	= Referensi =		= Referensi =

			== Referensi ==
			<references />

	== Sumber dan atribusi ==		== Sumber dan atribusi ==

	Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Pembuktian+teorema+otomatis&oldid=29524240 Wikipedia bahasa Indonesia], revisi 29524240 (2026-08-04T11:02:28Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.		Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Pembuktian+teorema+otomatis&oldid=29524240 Wikipedia bahasa Indonesia], revisi 29524240 (2026-08-04T11:02:28Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.

			<!-- WIKI_UNISSULA_PRESENTATION_V4 -->

Maintenance script: Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29524240; atribusi sumber disertakan.

2026-08-24T22:55:15Z

Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 29524240; atribusi sumber disertakan.

Halaman baru

'''Pembuktian teorema otomatis''' (juga dikenal sebagai ATP atau deduksi otomatis) adalah cabang dari penalaran otomatis dan [[logika matematika]] yang berhubungan dengan pembuktian teorema matematika menggunakan program komputer. Penalaran otomatis terhadap bukti matematika merupakan salah satu faktor utama yang mendorong perkembangan ilmu komputer.

== Landasan logika ==
Meskipun akar logika formal dapat ditelusuri kembali ke [[Aristoteles]], akhir abad ke-19 dan awal abad ke-20 menyaksikan perkembangan logika modern dan matematika formal. ''Begriffsschrift'' karya Frege (1879) memperkenalkan baik kalkulus proposisional yang lengkap maupun logika predikat modern pada dasarnya. ''Foundations of Arithmetic'' yang diterbitkan pada 1884 mengekspresikan (sebagian) matematika dalam logika formal. Pendekatan ini dilanjutkan oleh [[Bertrand Russell|Russell]] dan [[Whitehead]] dalam karya berpengaruh mereka ''[[Principia Mathematica]]'', yang pertama kali diterbitkan antara 1910–1913, dan dengan edisi kedua yang direvisi pada 1927. Russell dan Whitehead percaya bahwa mereka bisa menurunkan semua kebenaran matematika menggunakan aksioma dan aturan inferensi logika formal, yang pada prinsipnya membuka kemungkinan untuk proses otomatisasi.

Pada 1920, Thoralf Skolem menyederhanakan hasil sebelumnya oleh Leopold Löwenheim, yang menghasilkan [[teorema Löwenheim–Skolem]] dan, pada 1930, konsep [[alam semesta Herbrand]] (''Herbrand universe'') dan interpretasi Herbrand (''Herbrand interpretation'') yang memungkinkan ketidakpuasan atau kepuasan formula orde pertama (dan dengan demikian validitas sebuah teorema) direduksi menjadi masalah kepuasan proposisional yang (potensial) tak terbatas.

Pada 1929, Mojżesz Presburger menunjukkan bahwa teori orde pertama dari bilangan alami dengan operasi penjumlahan dan kesetaraan (yang sekarang disebut [[aritmetika]] [[Presburger]] untuk menghormatinya) dapat diputuskan dan memberikan algoritma yang dapat menentukan apakah suatu kalimat dalam bahasa tersebut benar atau salah.

Namun, tak lama setelah hasil positif ini, [[Kurt Gödel]] menerbitkan ''On Formally Undecidable Propositions of Principia Mathematica and Related Systems'' (1931), yang menunjukkan bahwa dalam sistem aksiomatik yang cukup kuat, terdapat pernyataan yang benar tetapi tidak dapat dibuktikan dalam sistem tersebut. Topik ini kemudian dikembangkan lebih lanjut pada tahun 1930-an oleh Alonzo Church dan [[Alan Turing]], yang di satu sisi memberikan dua definisi komputabilitas yang independen tetapi ekuivalen, dan di sisi lain memberikan contoh konkret dari pertanyaan yang tak dapat diputuskan.

== Implementasi pertama ==
Pada tahun 1954, [[Martin Davis]] memprogram algoritma Presburger untuk komputer tabung vakum JOHNNIAC di ''Institute for Advanced Study'' di [[Princeton, New Jersey]]. Menurut Davis, “Keberhasilan besarnya adalah membuktikan bahwa jumlah dua bilangan genap adalah genap.”

Lebih ambisius lagi adalah Logic Theorist pada tahun 1956, sebuah sistem deduksi untuk logika proposisional dari ''Principia Mathematica'', yang dikembangkan oleh [[Allen Newell]], [[Herbert Simon|Herbert A. Simon]], dan [[J. C. Shaw]]. Juga dijalankan pada JOHNNIAC, Logic Theorist menyusun bukti dari sekumpulan kecil aksioma proposisional dan tiga aturan deduksi: ''modus ponens'', substitusi variabel (proposisional), dan penggantian formula dengan definisinya. Sistem ini menggunakan panduan heuristik, dan berhasil membuktikan 38 dari 52 teorema pertama dari ''Principia Mathematica''.

Pendekatan “[[Heuristika|heuristik]]” Logic Theorist mencoba meniru cara matematikawan manusia, dan tidak dapat menjamin bahwa bukti dapat ditemukan untuk setiap teorema yang valid, bahkan secara prinsip. Sebaliknya, algoritma lain yang lebih sistematis mampu mencapai, setidaknya secara teoretis, kelengkapan untuk logika orde pertama. Pendekatan awal bergantung pada hasil Herbrand dan Skolem untuk mengubah sebuah formula orde pertama menjadi himpunan formula proposisional yang semakin besar dengan mengganti variabel menggunakan istilah dari alam semesta Herbrand. Formula proposisional tersebut kemudian dapat diperiksa ketidakpuasannya menggunakan berbagai metode. Program Gilmore menggunakan konversi ke bentuk normal disjungtif (''disjunctive normal form''), sebuah bentuk di mana kepuasan suatu formula menjadi jelas.

= Referensi =

== Sumber dan atribusi ==

Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Pembuktian+teorema+otomatis&oldid=29524240 Wikipedia bahasa Indonesia], revisi 29524240 (2026-08-04T11:02:28Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Mohon gunakan konten ini secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.