Apa intuisi di balik logika linier?

Saya mencoba memahami logika linier untuk memahami sistem tipe linear dengan lebih baik. Namun, ketika saya membaca aturan, saya gagal mendapatkan intuisi di belakangnya seperti yang saya lakukan dalam modal logika - berarti diperlukan seperti dalam Kripke frame diperlukan untuk setiap dunia yang dapat dijangkau [ adalah adalah mungkin mutatis mutandis]. Tetapi saya tidak dapat menemukan penjelasan intuitif untuk dualitas dan yang dari pasangan konjungsi / disjungsi (jika ada) sesuai dengan dan . $\Box A$ $A$ $A$ $\Diamond A$ $A$ $\land$ $\lor$

lo.logic type-theory linear-logic Maciej Piechotka
sumber

Kertas asli Girard adalah tempat Anda harus melihat jika Anda ingin memahami intuisi di belakangnya. Pertanyaan seperti imo terlalu umum dan jawabannya adalah untuk melihat halaman Wikipedia untuk logika linier.

Kaveh

Saya setuju bahwa ini agak terlalu roti dan jelas bukan tingkat penelitian, mungkin Anda harus mengajukan pertanyaan di CS Stack Exchange. Namun, saya akan mencegah Anda menggunakan kertas asli Girard sebagai titik masuk ke logika linier. Mungkin Wikipedia adalah tempat yang lebih baik untuk memulai.

Damiano Mazza

Ini cukup luas. Sebuah saran, mungkin, dapat mulai menganggap formula sebagai "mata uang" yang dapat digunakan, alih-alih pernyataan kebenaran. Kemudian, bersamaan bisa menjadi

berarti kita dapat menghabiskan kedua sebuah

koin dan

koin. Jenis lain dari konjungsi dapat

, artinya kita dapat memilih antara pengeluaran

dan pengeluaran

(tetapi tidak keduanya!). Anda dapat menemukan beberapa contoh di Wikipedia, seperti yang disarankan Damiano.

a \otimes b

$a \otimes b$

a

$a$

b

$b$

a & b

$a \& b$

a

$a$

b

$b$

chi

@ Ya, saya tidak yakin "interpretasi sumber daya" adalah cara terbaik untuk memahami dualitas dalam LL. Proses interpretasi jauh lebih mudah dipahami.

Martin Berger

Jawaban:

Saya tidak yakin pertanyaan ini ideal untuk CSTheory, tetapi mengingat sudah mengumpulkan suara, inilah jawaban yang mungkin diberikan seseorang jika pertanyaannya diposting di cs.stackexchange .

$(\cdot)^{\bot}$ $A$

$A \otimes B$ $A$ $B$ $A \otimes B$ $(a, b)$ $a$ $A$ $b$ $B$

$(.)^{\bot}$ $A \otimes B$

(A \otimes B)^{⊥} = A^{⊥} ⅋ B^{⊥}

$(A \otimes B)^{\bot} \quad = \quad A^{\bot} ⅋ B^{\bot}$

$A^{\bot} ⅋ B^{\bot}$ $A \otimes B$

Setara dengan disjungsi logika linier dapat diberikan pembacaan proses-teoritik yang serupa. Rumus

A & B

$A\ \&\ B$

$A$ $B$ $A \& B$ $A \& B$ $A$ $B$ $if/then/else$ $(A \& B)^{\bot}$ $A \& B$

(A & B)^{⊥} = A^{⊥} \oplus B^{⊥}

$(A \& B)^{\bot} \quad = \quad A^{\bot} \oplus B^{\bot}$

$A \& B$ $A$ $B$ $if\ true\ then\ P\ else\ Q$ $P$ $if\ false\ then\ P\ else\ Q$ $Q$ $A$ $B$

A

$A$

! A

$!A$

A

$A$

$A \vdash A$ $A^{\bot}$ $A$

Interpretasi proses-teoretis ini telah berpengaruh dan memunculkan banyak pekerjaan lanjutan seperti misalnya (2) untuk tipe sesi. Namun demikian, ada beberapa kasus tepi yang membuatnya sedikit canggung, dan sejauh yang saya tahu, ini tidak dibuat untuk bekerja dengan logika linier penuh bahkan pada tahun 2017.

_{1. S. Abramsky, Interpretasi Komputasi Logika Linier .

2. P. Wadler, Proposisi sebagai sesi .

3. Wikipedia, jaring bukti .}

Martin Berger
sumber