Apa sebenarnya logika itu?

36

Permintaan maaf mungkin karena mengajukan pertanyaan lain tentang prasyarat, tapi saya bingung tentang poin awal. Saya telah menemukan berbagai istilah seperti "Modal Logika", "Logika temporal", "Logika Orde Pertama", "Logika Orde Kedua", dan "Logika Orde Tinggi".

Apa sebenarnya arti "Logika" dalam konteks ini? Bagaimana kita secara ketat mendefinisikan kata "Logika"?

Setelah melalui halaman awal beberapa buku saya kira-kira dapat menyimpulkan bahwa "Logika adalah cara untuk memutuskan apa yang mengikuti dari apa dan penting dalam merancang bahasa pemrograman karena mendikte dan memfasilitasi perancangan program untuk secara otomatis beralasan dan memahami program. Saya ingin untuk memahami tentang poin kedua dengan cara yang agak rumit.

Sekarang datang ke logika ini.

Apakah semua logika ini, "Logika temporal", "Logika Modal", "Logika orde pertama", "Logika orde tinggi" tidak tergantung satu sama lain atau kita perlu memahami sedikit dari logika ini untuk memahami beberapa lainnya dalam grup ini? Singkatnya, apa yang akan menjadi prasyarat bagi mereka? (Akan sangat bagus jika saya bisa mendapatkan saran tentang beberapa materi juga.)

PS: Terima kasih banyak atas kebaikan Anda

Sheldon Kripke
sumber
17
Ironisnya, pertanyaan seperti ini akan ditanyakan oleh seseorang bernama Kripke . :-)
David Richerby
1
Saya harus mengatakan bahwa reaksi Anda tidak aneh. Saya sendiri cukup terkejut ketika saya menemukan definisi formal tentang 'aljabar'.
Kadal diskrit
2
@Discretelizard "Aljabar" mungkin bahkan lebih mengejutkan, karena sama sekali tidak ada hubungannya dengan hal yang mereka sebut aljabar di sekolah menengah.
David Richerby
@ DavidRicherby saya lakukan juga, "aljabar linier" hanyalah aljabar.
Niklas Rosencrantz
1
@ MartinRosenau Mengapa Anda berpikir itu akan menjadi penghalang untuk menyesuaikan logika fuzzy ke dalam pengertian umum tentang logika?
Derek Elkins

Jawaban:

39

Pada dasarnya, logika terdiri dari dua hal.

  • Sintaks adalah seperangkat aturan yang menentukan apa yang merupakan dan bukan rumus.
  • Semantik adalah seperangkat aturan yang menentukan rumus apa yang "benar" dan apa yang "salah". Bagi seorang teoretikus model , ini diungkapkan dengan menghubungkan rumus-rumus dengan struktur matematika yang benar; bagi ahli teori bukti , kebenaran berhubungan dengan kemampuan dari serangkaian aksioma pilihan dengan seperangkat aturan pembuktian yang dipilih (teknik).

Perbedaan antara logika yang berbeda adalah, paling sederhana, dalam pilihan sintaksis dan semantik. Kebanyakan logika adalah ekstensi dari logika proposisional atau logika tingkat pertama . Dalam arti tertentu, Anda dapat melihat ekstensi ini sebagai "menambahkan lebih banyak fitur" ke logika. Sebagai contoh, logika temporal berurusan dengan kebenaran yang dapat bervariasi dari waktu ke waktu.

Secara umum, fitur-fitur ini dapat diekspresikan dalam logika yang lebih sederhana, dengan mengorbankan keharusan menulis formula yang lebih panjang. Misalnya, konsep temporal "  benar dari titik ini untuk selamanya" dapat diekspresikan dalam cara urutan pertama dengan menambahkan parameter waktu ke semua proposisi Anda dan mengatakan "Untuk semua waktu  t , jika tφtt  lebih besar dari atau sama dengan waktu saat ini, maka  benar pada waktu  t . " Dalam arti tertentu, Anda dapat menganggap logika ini sebagai menambahkan pustaka ke bahasa pemrograman dasar sehingga Anda dapat mengatakan sesuatu dengan lebih mudah.φt

Karena hampir semua logika didasarkan pada logika proposisional dan orde pertama, saya akan merekomendasikan untuk belajar tentang itu terlebih dahulu.

David Richerby
sumber
2
Sebagai seorang ilmuwan komputer saya juga menemukan mempertimbangkan koneksi ke teori ketik yang sangat berguna untuk belajar logika. Sistem tipe dapat dianggap sebagai presentasi alternatif dari logika yang setara, melalui korespondensi Howard-Curry . Saya merekomendasikan buku Pierce untuk memulai.
phs
1
Ada lebih banyak sintaksis dalam logika daripada sekadar rumus, dan ada lebih banyak pada semantik daripada sekadar penentuan kebenaran.
Andrej Bauer
Perspektif formal yang kira-kira sesuai dengan pandangan yang disebutkan dalam jawaban ini dan memang berusaha memberikan definisi pemersatu (dan dirancang untuk mengatasi masalah dalam ilmu komputer) adalah teori institusi .
Derek Elkins
Tidak begitu kebetulan, institusi dijelaskan dalam makalah berjudul Apa itu Logika?
Derek Elkins
@ phs Wow ... Saya tidak tahu bagaimana saya sampai sejauh ini, tapi ini adalah pertama kalinya saya mempertimbangkan gagasan bahwa Currying suatu fungsi bisa menjadi referensi untuk apa pun selain rempah-rempah.
Cort Ammon
21

Sementara bidang-bidang seperti ilmu komputer, matematika dan fisika relatif terorganisir dengan baik, Logic memiliki sejarah yang kacau. Organisasinya benar - benar membingungkan, jadi saya pikir penting untuk membaca beberapa sejarah untuk memahami struktur lapangan yang padat.

Jalur yang harus Anda pilih akan tergantung pada latar belakang dan tujuan Anda .

Apa itu logika?

  1. Pandangan tradisional mengatakan bahwa logika adalah sistem formal dengan bahasa formal (sintaksis), semantik (makna eksternal, pemikiran penafsir program) dan seperangkat aturan untuk menyimpulkan pernyataan dari yang lain (pikirkan aturan pengurangan program). Logika murni dilihat sebagai objek matematika semata.

  2. Sudut pandang modern, mengatakan, melalui isomorfisme Curry-Howard yang terkenal bahwa logika adalah sistem tipe yang koheren (bukti adalah program dan tipe adalah formula). Lebih tepatnya: sistem inferensi aturan menikmati teorema cut-elimination dan teorema Rosser / confluence teorema menyiratkan bahwa sistem pemrograman yang mendasarinya akan berperilaku baik.

  3. hal,q

    • P,QP(x1,...,xn)Q(x1,...,xn)
    • Dalam logika urutan kedua, variabel untuk predikat menjadi jenis fungsi yang mengambil urutan pertama. Mereka berperilaku seperti fungsi yang mengambil fungsi orde pertama sebagai argumen. Sebagai contoh, kita dapat memiliki predikat dan kuantifikasi dibandingkan predikat.
    • Alasan yang sama untuk urutan ketiga, dll. Logika tingkat tinggi menerima pesanan apa pun. Pikirkan Haskell dan OCaml yang memiliki fungsi mengambil fungsi fungsi, dll sebagai argumen.
  4. Secara umum, tidak ada konsensus tentang apa logika trully itu. Beberapa filsuf menggunakan sistem yang tidak memiliki sistem pemrograman yang mendasarinya koheren. Sebenarnya, saya akan mengatakan bahwa setiap bidang menggunakan Logika memiliki konsepsi logika sendiri. Dan sebagian besar ahli matematika mungkin tidak peduli tentang apa itu logika.

Struktur lapangan

Sejarah Logika terlalu besar sehingga saya hanya akan memberikan struktur lapangan. Bidang logika formal terbagi menjadi: penggunaan filosofis, matematis dan komputasi. Logika formal dimulai pada abad ke 19-20.

  • Anda harus mempelajari logika proposisional dan logika tingkat pertama terlebih dahulu. Mereka adalah yang paling standar. Mereka diciptakan untuk memberikan akun formal / matematika dengan logika lama waktu Yunani Kuno.

    • Teori model (semantik), mempelajari struktur matematika dari perspektif logika
    • Teori bukti (sintaksis), secara independen, mempelajari bukti sebagai objek matematika.
  • Logika orde kedua adalah perpanjangan dari logika orde pertama yang merupakan perpanjangan dari logika proposisional. Ini sangat menarik karena aritmatika "hidup" di urutan kedua (predikat pada predikat dengan induksi). Demikian pula, topologi hidup dalam "orde ketiga" (predikat pada perangkat yang dapat dilihat sebagai predikat sendiri).

  • Kemudian datang LEJ Brouwer yang membagi logika menjadi dua:

    • SEBUAHSEBUAH¬SEBUAH
    • Intuitionistic Logic adalah sejenis logika yang menolak hukum tengah dan semua yang setara yang dikecualikan (untuk alasan teknis dan filosofis yang tidak akan saya jelaskan di sini).
  • Dalam konteks lain, para filsuf menjadi tertarik pada logika formal dan berpikir itu dapat menjawab pertanyaan filosofis (filsafat analis). Mereka membuat sistem logis independen mereka sendiri (logika paraconsistent, logika relevansi, dan logika modal seperti logika deontik, logika temporal, logika epistemik, ...). Modal logika tidak bekerja dengan kebenaran tetapi dengan modalitas seperti kemungkinan, kebutuhan, waktu, pengetahuan. Mereka semua independen dari logika di atas.

  • λ

  • Ilmuwan komputer ingin memverifikasi dan membuktikan kebenaran sistem secara formal dan tampaknya logika modal itu relevan. Hari ini mereka menggunakan logika temporal dan modal logika untuk alasan sistem (lihat: metode formal, pengecekan model). Sistem dimodelkan melalui Teori Automata (misalnya) dan diverifikasi menggunakan alat logis. Itu mengarah ke Linear Temporal Logic (LTL) dan Computational Tree Logic (CTL) .

  • Dalam motivasi yang sama, para ilmuwan komputer ingin memverifikasi kesehatan dan membuktikan properti tentang program. Jadi kami menemukan Hoare Logic untuk program penting dan lebih umum, Pemisahan Logika .

  • Dengan mempelajari, isomorfisma Curry-Howard, muncul logika baru: Linear Logic yang membatasi aturan struktural (melemah dan kontraksi) dilihat sebagai penghapusan dan duplikasi yang beroperasi dalam bukti dan program. Potensi kebenaran yang tak terbatas dijelaskan. Tampaknya logika ini adalah generalisasi dari logika klasik dan intuitionistic dan memberikan konsepsi Logika yang sepenuhnya baru berdasarkan komputasi dan paradigma prosedural. Sebagian besar dipelajari oleh para ilmuwan komputer.

  • Logika Linier juga berasal dari apa yang kita sebut Logika Substruktural yang menolak aturan struktural Logika. Logika Relevan dan Logika Affine adalah contoh untuk sistem tersebut.

Ringkasan dan pemilihan jalur

  • Logika apa pun bisa: logika proposisional, orde pertama, orde kedua, orde ketiga, ..., orde lebih tinggi (masing-masing memperpanjang yang sebelumnya).

  • Kami dapat menambah atau menghapus aturan untuk membuat varian dari sistem yang ada:

    • Hapus excluded-middle: logika intuitionistic
    • Tambahkan modalitas: modal logika
    • Batasi kontradiksi dan pelemahan: logika linier
    • Hapus kontraksi: logika affine
    • Hapus pelemahan: logika yang relevan
    • Tangani negasi secara berbeda: logika parakonsisten
  • Pelajari proposisional dan logika urutan pertama terlebih dahulu dan:

    • teori model, urutan kedua, urutan lebih tinggi jika Anda tertarik pada matematika
    • teori bukti, logika intuitionistic, urutan kedua, logika linier jika Anda tertarik pada dasar ilmu komputer
    • modal logika, logika hoare, logika pemisahan jika Anda tertarik pada verifikasi sistem dan program
    • modal logika, logika non-klasik secara umum jika Anda tertarik pada filosofi

Referensi (Buku)

Saya pribadi merekomendasikan untuk mencampur referensi, jika mungkin.

  • Logika Matematika (Chiswell & Hodges) : buku yang sangat ringkas dan sederhana untuk memulai.
  • Kursus pertama dalam Logika (Hedman) : sedikit seperti yang di atas, tetapi berikan rincian lebih lanjut dan pertimbangkan komputabilitas.
  • Buku Pegangan Logika Praktis dan Penalaran Otomatis (Harrison) : Jika Anda ingin memahami bagaimana beberapa konsep terkait logika diimplementasikan dalam praktik. Lebih berorientasi pada penalaran otomatis.
  • Logika dalam Ilmu Komputer (Huth & Ryan) : sangat jelas dan berorientasi pada ilmuwan komputer (verifikasi program dan sistem, logika Hoare, penggunaan praktis logika modal, logika temporal, pengecekan model).
  • Pengantar Teori Bukti (Buss) : pengantar teori bukti. Seharusnya lebih baik membaca ini setelah beberapa logika umum.

Referensi (Wikipedia)

Boris E.
sumber
Baiklah, ini sangat ... komprehensif, menurut saya. Terima kasih telah meluangkan waktu untuk menulis ini!
Kadal diskrit
5
Ini terlihat sangat komprehensif tetapi saya benar-benar tidak akan membawa Curry-Howard sebagai hal kedua yang Anda katakan tentang logika kepada seseorang yang baru mempelajari apa itu. Kecuali Anda benar-benar mempelajari teori tipe, Curry-Howard bukanlah "definisi modern dari logika"; itu hanya sesuatu yang dilakukan sebagian orang dengan logika.
David Richerby
2
@ DavidRicherby Ok. Saya mengerti tapi saya pikir Curry-Howard cukup penting bagi para ilmuwan komputer (juga karena kita berada di cs.stackexchange). Ini sebenarnya bukan definisi logika modern tapi saya pikir itu untuk beberapa ilmuwan komputer. Apa sebenarnya logika itu mungkin subyektif. Saya tahu itu tidak selalu merupakan ide yang baik untuk mengekspos poster asli untuk banyak hal, tetapi saya tidak benar-benar mengharapkan pemahaman penuh, melainkan panorama komprehensif dari cabang-cabang Logika (sedikit bias oleh CS) yang dapat bertindak sebagai referensi untuk mengetahui jenis logika apa yang ada dan di mana ia digunakan.
Boris E.
Saya mendapat kesan bahwa logika tingkat tinggi di Haskell akan menjadi operator tipe , bukan fungsi yang bisa mengambil fungsi sebagai input.
martin
@martin Hm ... Itu hanya analogi sederhana untuk memahami gagasan mekanisme tetapi tidak harus dianggap terlalu serius. Saya ingin menggambarkan ide "orde tinggi" daripada "logika orde tinggi" (dengan mempertimbangkan latar belakang poster asli).
Boris E.
0

Semua logika ini datang di bawah Matematika Logika .

Logika matematika sering dibagi menjadi bidang teori himpunan, teori model, teori rekursi, dan teori pembuktian. Area-area ini membagikan hasil-hasil dasar pada logika, khususnya logika tingkat pertama, dan keterjelasan. Dalam ilmu komputer (khususnya dalam Klasifikasi ACM) logika matematika mencakup topik tambahan yang tidak dirinci dalam artikel ini; lihat Logika dalam ilmu komputer untuk itu.

Apalagi jika Anda ingin tahu tentang logika secara umum artikel ini bisa bermanfaat.

Logika, awalnya berarti "kata" atau "apa yang diucapkan", tetapi kemudian berarti "pikiran" atau "alasan", adalah subjek yang berkaitan dengan hukum kebenaran paling umum, dan sekarang umumnya dianggap terdiri dari studi sistematis dari bentuk inferensi yang valid. Inferensi yang valid adalah kesimpulan di mana terdapat hubungan spesifik dukungan logis antara asumsi kesimpulan dan kesimpulannya.

Oh Tuhan
sumber
4
Hmm, saya tidak yakin apakah ini sangat membantu di sini. Apakah Anda akan mengatakan bahwa jabatan David membuat jabatan Anda 'digantikan'? Jika tidak, mengapa? Cobalah untuk mengembangkannya.
Kadal diskrit
@ Omg: Bisakah Anda merekomendasikan daftar bahan untuk dipelajari?
Sheldon Kripke