Energi Shakti: Logika Aristoteles

Istilah Temporal Logic telah digunakan secara luas untuk mencakup semua pendekatan terhadap representasi dan penalaran tentang informasi waktu dan temporal dalam kerangka logis, dan juga lebih sempit untuk merujuk secara khusus pada jenis pendekatan logika-modal yang diperkenalkan sekitar tahun 1960 oleh Arthur Prior

dengan nama dari Logika Tegang dan kemudian dikembangkan lebih lanjut oleh banyak ahli logika dan ilmuwan komputer. Aplikasi Temporal Logic mencakup penggunaannya sebagai formalisme untuk mengklarifikasi isu-isu filosofis mengenai waktu, sebagai kerangka di mana untuk mendefinisikan semantik ekspresi temporal dalam bahasa alami, sebagai bahasa untuk mengkodekan pengetahuan temporal dalam kecerdasan buatan, dan sebagai alat untuk spesifikasi , analisis formal, dan verifikasi eksekusi program dan sistem komputer.
Di sini kami memberikan gambaran umum yang luas, ringkas dan pasti tidak lengkap, gambaran tentang beragam model temporal dan logika yang diperkenalkan dan dipelajari selama 50 tahun terakhir.

1. Penalaran temporal dari zaman purbakala ke zaman modern

Pembahasan temporalitas dan penalaran tentang waktu kembali ke zaman purbakala dan contohnya dapat ditemukan bahkan di dalam Alkitab (Boyd 2014). Beberapa argumen paradoks Zeno mengacu pada sifat waktu dan pertanyaan tentang pembagian interval waktu yang tak terbatas. Mungkin referensi ilmiah paling awal tentang penalaran temporal, bagaimanapun, adalah argumen Aristoteles di On Interpretation , Ch. 9, kontingen masa depan , yaitu pernyataan tentang kemungkinan kejadian di masa depan yang mungkin atau mungkin tidak terjadi, seperti "Akan ada hari es melawan laut", seharusnya tidak dianggap sebagai nilai kebenaran yang pasti pada saat ini. Beberapa dekade kemudian, filsuf Diodorus Cronus (ca 340-280 SM) dari sekolah Megaria menunjukkan masalah kontingen masa depan di Argumen Guru yang terkenal, di mana, antara lain, dia mendefinisikan "mungkin" sebagai " apa yang akan pernah ada " dan "Perlu" sebagai " apa adanya dan akan selalu ada ". Untuk rinciannya, lihat Rescher dan Urquhart (1971, Bab XVII) dan entri tentang kontingen masa depan .
Diskusi filosofis tentang temporalitas, kebenaran, kehendak bebas, determinisme, dan bagaimana hubungan mereka, berlanjut selama abad pertengahan. William dari Ockham (sekitar 1287-1347) berpendapat bahwa proposisi tentang masa depan kontingen tidak dapat diketahui manusia sebagai benar atau salah karena hanya Tuhan yang mengetahui nilai kebenaran mereka sekarang. Namun, dia berpendapat bahwa manusia masih memiliki beberapa kebebasan untuk memilih di antara kemungkinan masa depan yang berbeda, sehingga menyarankan gagasan tentang model waktu yang bercabang di masa depan dengan banyak kemungkinan garis waktu (sejarah), kebenaran proposisi yang dikaitkan dengan kemungkinan sejarah yang sebenarnya; Model waktu ini sekarang sering disebut Ockhamist . Kemudian, beberapa filsuf dan ahli logika, termasuk CS Peirce, mengangkat dan menganalisis masalah yang berkaitan dengan temporalitas dengan non-determinisme, kebutuhan historis, kehendak bebas, kehendak dan pengetahuan Tuhan, dan sebagainya, mengusulkan berbagai solusi yang berbeda. Untuk diskusi filosofis yang lebih baru tentang kehendak bebas vs determinisme, lihat Belnap dkk. (2001).
Dari awal 1950an Arthur Prior mulai menganalisis dan memformalkan argumen semacam itu, yang membuatnya, antara lain, dengan penemuan Logika Temporal formal, beberapa versi yang dibahas di bawah ini. Pekerjaan seminalis terdahulu, yang sebagian dipengaruhi oleh prekursor penting seperti J. Findlay, H. Reichenbach dan J. Łukasiewicz, memprakarsai era modern penalaran logis temporal, dengan banyak aplikasi penting tidak hanya pada filsafat, tapi juga pada ilmu komputer, kecerdasan buatan, dan linguistik, yang secara singkat dibahas di bawah pada Bagian 10 .
Waktu tidak hanya filosofis, tapi juga konsep fisik yang mendasar, dan karena itu telah dipelajari dan dianalisis sepanjang sejarah sains. Teori fisik awal, yang berpuncak pada mekanika klasik Newton, mengandaikan konsep waktu yang absolut , bebas dari ruang, materi, dan semua konsep fisik fundamental lainnya. Menentang hal ini, Leibniz menganjurkan pandangan relasional yang menurutnya tergantung pada proses dan kejadian, namun pandangan semacam itu tidak menemukan ekspresi dalam fisika sampai pandangan relativis dari awal abad ke-20, yang menempatkan waktu dalam hubungan yang melibatkan secara matematis dengan ruang , dimodelkan oleh manifold berjejer dua dimensi Minkowski , dan dengan materi, yang ditangkap oleh teori relativitas Einstein. Kita tidak akan membahas teori fisik waktu lebih jauh di sini tapi kita harus menyebutkan Rescher dan Urquhart (1971, Bab XVI), di mana penalaran dan dimensi ruang waktu dibicarakan, dan Goldblatt (1980), di mana logika pasar Diodorean pada ruangwaktu Minkowskian dipelajari dan terbukti menjadi logika logika S4.2 dan sejumlah pertanyaan terkait, beberapa di antaranya masih terbuka, diangkat.
Untuk membaca lebih lanjut tentang sejarah penalaran temporal dan logika lihat Øhrstrøm dan Hasle (1995).

2. Formal model waktu

Sifat ontologis dan sifat waktu adalah isu filosofis mendasar. Berbagai alternatif di sepanjang beberapa dimensi telah diperdebatkan sejak zaman purbakala dan pilihan di antara alternatif-alternatif ini sangat penting bagi wacana filosofis mengenai sifat waktu; adalah waktu, misalnya, diskrit atau kontinyu ; berbasis instan atau berbasis interval ; dibatasi atau tak terbatas ; deterministik atau tidak ; linier atau (maju) bercabang ; melingkar , dll? Kami secara singkat membahas beberapa alternatif di bawah ini, dan kembali lagi ke konteks formal logika temporal.

2.1 Model arus berbasis instan

Dalam model waktu instan, entitas temporal primitif adalah instans waktu dan hubungan dasar di antara keduanya (selain persamaan) didahulukan . Dengan demikian, arus waktu diwakili sebagai seperangkat instants waktu dengan relasi biner yang didahulukan di atasnya: \ (\ left \ langle T, \ prec \ right \ rangle. \) Ada beberapa sifat dasar yang secara alami dapat dipaksakan. pada arus waktu berbasis instan. Biasanya dibutuhkan suatu pemesanan parsial yang ketat, yaitu hubungan irreflexif dan transitif. Terkadang, bagaimanapun, diasumsikan bersifat refleksif dan kemudian kondisi antisimetri ditambahkan. Dua tipe utama dari model semacam itu biasanya dipertimbangkan: urutan linier , yang mencerminkan gagasan bahwa aliran waktu adalah suksesi instants, dan forward branching partial orderings , yang mewakili gagasan bahwa masa lalu ditentukan dan oleh karena itu linier, sementara masa depan dapat ditentukan, bercabang menjadi banyak garis waktu yang mungkin. Beberapa properti dasar lebih lanjut yang merupakan model berbasis instan \ (\ left \ langle T, \ prec \ right \ rangle \) mungkin atau mungkin tidak dapat diungkapkan dengan kalimat orde pertama sebagai berikut (di mana \ (\ preceq \) adalah singkatan dari \ (x \ prec y \ lor x = y \)):

refleksivitas : \ (\ forall x (x \ prec x); \) masing-masing irreflexivity : \ (\ forall x \ lnot (x \ prec x); \)
transitivitas : \ (\ forall x \ forall y \ forall z (x \ prec y \ wedge y \ prec z \ rightarrow x \ prec z); \)
anti-simetri : \ (\ forall x \ forall y (x \ prec y \ wedge y \ prec x \ rightarrow x = y), \)
trichotomy (keterhubungan) : \ (\ forall x \ forall y (x = y \ vee x \ prec y \ vee y \ prec x); \)
kepadatan (antara setiap dua instants terkait sebelumnya ada instan) : \ (\ forall x \ forall y (x \ prec y \ rightarrow \ ada z (x \ prec z \ wedge z \ prec y)); \)
tidak ada permulaan : \ (\ forall x \ exist y (y \ prec x); \) tidak ada akhir : \ (\ forall x \ exist y (x \ prec y); \)
setiap instan memiliki penerus segera : \ (\ forall x \ ada y (x \ prec y \ wedge \ forall z (x \ prec z \ rightarrow y \ preceq z)) \) dan, juga, setiap instan memiliki pendahulu langsung : \ (\ forall x \ ada y (y \ prec x \ wedge \ forall z (z \ prec x \ rightarrow z \ preceq y)); \)
disketitas ke depan (setiap instan dengan penerus memiliki penerus segera) : \ (\ forall x \ ada y (x \ prec y \ rightarrow \ ada y (x \ prec y \ wedge \ forall z (x \ prec z \ rightarrow y \ preceq z)); \)
Discreteness mundur (setiap instan dengan pendahulunya memiliki pendahulu yang segera) : \ (\ forall x \ exist y (y \ prec x \ rightarrow \ exist y (y \ prec x \ wedge \ forall z (z \ prec x \ rightarrow z \ preceq y))). \)

Beberapa sifat alami dan penting arus waktu tidak dapat diungkapkan dengan kalimat orde pertama. Sebagai contoh, seseorang tidak dapat mengatakan dalam logika orde pertama bahwa aliran waktu linier diurutkan dengan baik , yang berarti bahwa setiap deret instans waktu yang turun secara pasti harus terbatas. Setara dengan itu, pemesanan dengan baik berarti bahwa setiap kumpulan waktu yang tidak kosong memiliki elemen \ (\ prec \) - least. Contohnya adalah kumpulan bilangan asli yang dipesan \ (\ left \ langle \ mathbf {N, <} \ right \ rangle; \) contohnya adalah bilangan bulat \ (\ left \ langle \ mathbf {Z, <} \ right \ rangele \) (ambil himpunan bilangan bulat negatif), rationals positif \ (\ left \ langle \ mathbf {Q ^ {+}, <} \ right \ rangle \) atau real positif \ (\ left \ langle \ mathbf {R ^ {+}, <} \ right \ rangle. \) Tidak ada kelengkapan Dedekind yang harus diungkapkan, yang menyatakan bahwa setiap himpunan instants yang tidak kosong yang memiliki batas atas memiliki batas paling atas. Contohnya adalah urutan bilangan asli, bilangan bulat atau bilangan real; Contoh yang tidak disebutkan adalah kumpulan ekspedisi yang dipesan: pertimbangkan himpunan semua bilangan bulat yang kuadratnya kurang dari 2. Untuk mengungkapkan sifat-sifat ini, seseorang memerlukan logika orde kedua monadik yang melibatkan kuantifikasi setel. Seperti ditunjukkan lebih jauh, beberapa sifat semacam itu dapat dinyatakan dalam logika temporal proporsional yang sesuai ekspresif.

2.2 Model interval / periode berdasarkan waktu

Model berbasis instan seringkali tidak sesuai untuk penalaran tentang peristiwa dunia nyata dengan durasi , yang lebih baik dimodelkan jika ontologi temporal yang mendasari menggunakan interval waktu , bukan instants, sebagai entitas primitif. Misalnya, pernyataan seperti "Malam terakhir Alice banyak menangis saat menulis suratnya, lalu dia tenang", "Selalu setelah makan malam, orang tua itu berjalan-jalan diikuti dengan mandi panjang", "Pembangunan Basilika Santo Petrus sekarang mengambil lebih dari 120 tahun ", atau" Bill tidak pernah minum kopi paginya dalam waktu kurang dari 2 menit "tentu memerlukan model waktu berbasis interval untuk dimodelkan dan dievaluasi secara memadai.
Model temporal berbasis temporal secara ontologis lebih kaya daripada yang berbasis instan, karena ada kemungkinan hubungan yang lebih banyak antara interval waktu daripada antar instans waktu. Misalnya, model waktu berbasis interval alami \ (\ mathcal {T} \) dapat mencakup prioritas hubungan \ (\ prec, \) inclusion \ (\ sqsubseteq \) dan tumpang tindih \ (O \) antara interval di atas beberapa aliran waktu \ (T: \) secara formal, \ (\ mathcal {T} = \ left \ langle T, \ prec, \ sqsubseteq, O \ right \ rangle. \) Beberapa sifat dasar alami dari hubungan dan model berbasis interval tersebut meliputi:

refleksivitas \ (\ sqsubseteq: \) \ (\ forall x (x \ sqsubseteq x), \)
anti-simetri dari \ (\ sqsubseteq: \) \ (\ forall x \ forall y (x \ sqsubseteq y \ wedge y \ sqsubseteq x \ rightarrow x = y), \)
atomicity \ (\ sqsubseteq \) (untuk waktu diskrit): \ (\ forall x \ ada y (y \ sqsubseteq x \ wedge \ forall z (z \ sqsubseteq y \ rightarrow z = y)). \)
ke bawah monotonisitas \ (\ prec \) wrt \ (\ sqsubseteq: \) \ (\ forall x \ forall y \ forall z (x \ prec y \ wedge z \ sqsubseteq x \ rightarrow z \ prec y). \)
simetri dari \ (O: \) \ (\ forall x \ forall y (xOy \ rightarrow yOx) \)
interval yang tumpang tindih berpotongan dalam subinterval :
\ (\ forall x \ forall y (xOy \ rightarrow \ ada z (z \ sqsubseteq x \ land z \ sqsubseteq y \ land \ forall u ((u \ sqsubseteq x \ land u \ sqsubseteq y) \ to u \ sqsubseteq z ))). \)
monotonisitas \ (\ sqsubseteq \) wrt \ (O: \) \ (\ forall x \ forall y \ forall z (x \ sqsubseteq y \ land xOz \ rightarrow (z \ sqsubseteq y \ lor zOy)). \)

Ini hanya contoh kecil dari properti semacam itu, yang kondisi kebenarannya dapat didefinisikan secara tepat. Dengan struktur abstrak yang didefinisikan oleh serangkaian relasi dan sifat-sifatnya, timbul pertanyaan apakah dapat diwakili dengan menggunakan model interval beton dari waktu linier. Jawaban diberikan oleh berbagai teorema representasi, lihat misalnya, van Benthem (1983), Ladkin (1987), dan Venema (1990).
Dalam sebuah karya awal yang berpengaruh pada studi formal ontologi temporal berbasis interval dan penalaran di AI, Allen (1983) menganggap keluarga dari semua 13 hubungan biner yang timbul di antara dua interval dalam urutan linier tertentu, yang kemudian disebut hubungan Allen , yang ditampilkan dalam Tabel 1. Ke 13 hubungan ini saling eksklusif dan saling melengkapi , yang berarti bahwa tepat di antara pasangan tertentu yang memiliki interval ketat (yaitu, tidak termasuk interval poin). Mereka ternyata bisa didefinisikan dalam beberapa hal, yaitu. 'bertemu' dan 'bertemu' (Allen 1983).

2.3 Model waktu vs interval instan

Sifat waktu dan, khususnya, pilihan antara instants dan interval sebagai objek utama ontologi temporal, telah menjadi tema filosofis yang diperdebatkan dengan hangat. Akar penalaran temporal berbasis interval dapat ditelusuri kembali ke Zeno dan Aristoteles (Øhrstrøm dan Hasle 1995). Rupanya, Zeno sendiri menyadari bahwa beberapa paradoksnya tidak muncul dalam setting berbasis interval, misalnya paradoks panah terbang ("jika pada setiap saat panah terbang masih berdiri, bagaimana pergerakannya?") Dan dilema instan pembagi ("Jika lampu menyala dan dimatikan, apa keadaannya pada saat di antara kedua acara?"). Tentu saja, kedua jenis ontologi temporal terkait erat dan secara teknis dapat direduksi satu sama lain: di satu sisi, interval waktu dapat ditentukan oleh pasangan instants waktu ( awal ); Di sisi lain, waktu instan dapat dianggap sebagai 'titik interval' yang merosot, yang titik akhirnya bertepatan. Lihat van Benthem (1983) untuk diskusi komparatif rinci mengenai kedua pendekatan tersebut.

Hubungan interval	Notasi Allen	\ (\ textsf {HS} \) notasi
┣━━┫	sama dengan \ (\ {= \} \)
├──┤ ┣┫	sebelum \ (\ {\ lt \} \) / setelah \ (\ {\ gt \} \)	\ (\ langle L \ rangle \: / \: \ langle \ overline {L} \ rangle \) Kemudian
├──╊┫	bertemu \ (\ {m \} \) / met-by } \ (\ {mi \} \)	\ (\ langle A \ rangle \: / \: \ langle \ overline {A} \ rangle \) Setelah
├─╊┿━┫	tumpang tindih \ (\ {o \} \) / tumpang tindih-oleh \ (\ {oi \} \)	\ (\ langle O \ rangle \: / \: \ langle \ overline {O} \ rangle \) Tumpang Tindih
├─╊┫	selesai-oleh \ (\ {fi \} \) / selesai \ (\ {f \} \)	\ (\ langle E \ rangle \: / \: \ langle \ overline {E} \ rangle \) Berakhir
├╊╉┤	berisi \ (\ {di \} \) / selama \ (\ {d \} \)	\ (\ langle D \ rangle \: / \: \ langle \ overline {D} \ rangle \) Selama
┣╉─┤	dimulai-oleh \ (\ {si \} \) / mulai \ (\ {s \} \)	\ (\ langle B \ rangle \: / \: \ langle \ overline {B} \ rangle \) Dimulai

Tabel 1: Hubungan Allen antara pasangan interval dan operator modal Halpern-Shoham pada mereka.

Model waktu lainnya juga telah dipelajari, termasuk model jeda interval dua titik (Balbiani et al., 2011), model perincian waktu, metrik dan model temporal temporal (Montanari 1996). Lihat juga entri SEP tepat waktu .

3. Logika Tegang Dasar Sebelum TL

Seperti disebutkan di atas, motivasi Prior untuk menemukan Logika Tegang sebagian besar bersifat filosofis, idenya adalah bahwa ketepatan dan kejelasan yang diberikan oleh notasi logis formal sangat diperlukan untuk rumusan dan resolusi yang seksama mengenai masalah filosofis mengenai waktu. Awalnya termotivasi oleh masalah mengenai hubungan antara tegang dan modalitas yang diajukan oleh Argumen Guru Diodorus Cronus, Arthur Prior mengenalkan dan menganalisis secara rinci lebih dari satu dekade beberapa versi Logika Tegang (Prior 1957; 1967; 1969). Dia tidak berlangganan pilihan tertentu, namun dengan pandangan modern bahwa "Ahli logika harus seperti seorang pengacara ... dalam artian dia ada untuk menyediakan metafisik, bahkan mungkin fisikawan, logika tegang yang dia inginkan, berikan itu konsisten ".

3.1 Operator tegang sebelumnya

Bahasa logis dasar dari Log Tense Logual Prior memuat, selain operator proposisional (kebenaran fungsional) biasa, empat operator modal temporal dengan makna yang dimaksudkan sebagai berikut:

\ (P \) "Sudah lama terjadi ..."
\ (F \) "Ini akan menjadi kasus yang ..."
\ (H \) "Itu selalu terjadi bahwa ..."
\ (G \) "Itu akan selalu terjadi ..."

Jadi, "\ (GP \) ( Prior Invents Tense Logic )" diterjemahkan sebagai "Akan selalu terjadi bahwa ia memiliki beberapa waktu lamanya bahwa Sebelum menciptakan Tense Logic".
\ (P \) dan \ (F \) dikenal sebagai operator tegang lemah , sedangkan \ (H \) dan \ (G \) dikenal sebagai operator tegang yang kuat . Kedua pasang tersebut dapat disandingkan dengan cara ekuivalensi
\ [P \ varphi \ equiv \ neg H \ negar \ varphi, H \ varphi \ equiv \ neg P \ neg \ varphi, F \ varphi \ equiv \ neg G \ neg \ varphi, G \ varphi \ equiv \ neg F \ neg \ varphi \] Secara formal, himpunan formula TL dapat didefinisikan secara rekursif oleh: \ \ \ varphi = p \ mid \ bot \ mid \ lnot \ varphi \ mid \ varphi \ lor \ psi \ mid G \ varphi \ mid H \ varphi \] Konektif klasik lainnya \ (\ wedge, \ to, \ leftrightarrow \) didefinisikan dalam istilah ini seperti biasa. Selain itu, kita dapat menentukan \ (A \ varphi = H \ varphi \ wedge \ varphi \ wedge G \ varphi \) dan, dually, \ (E \ varphi = P \ varphi \ veehi \ vee F \ varphi, \) yang pada arus waktu yang dipesan secara linear berarti selalu dan kadang - kadang .
Berbagai tenses dalam bahasa alami dapat diekspresikan, setidaknya kira-kira, di TL. Sebagai contoh:

\ (P \ varphi \) dapat sesuai baik untuk menyajikan sempurna ("\ (\ varphi \) telah terjadi") dan untuk masa lalu yang sederhana ("\ (\ varphi \) adalah kasusnya").
\ (PP \ varphi \) sesuai dengan " \ (\ varphi \) telah terjadi",
\ (FP \ varphi \) sesuai dengan " \ (\ varphi \) akan terjadi",
\ (PF \ varphi \) sesuai dengan "\ (\ varphi \) akan menjadi kasus" atau "\ (\ varphi \) akan menjadi masalahnya",
\ (PFP \ varphi \) sesuai dengan "\ (\ varphi \) yang akan terjadi".

Hamblin dan Prior mengidentifikasi 15 jenis tenses yang berbeda yang dapat dinyatakan dalam TL melalui arus linier waktu, lihat (Prior, 1967). Namun, operator Prior tidak terlalu cocok untuk mengekspresikan aspek progresif dari tenses . Misalnya, selain contoh yang diberikan pada akhir Bagian 2.2 , kalimat seperti "Bill sedang minum tehnya saat tukang pos datang", "Bill selalu minum tehnya saat membaca koran pagi", atau "Selama tujuh jam pesawat terbang akan terbang dengan kecepatan rata-rata supersonik "tidak bisa ditangkap secara alami dalam logika TL yang tegang. Arguably, logika berbasis interval adalah kerangka yang lebih alami untuk itu. Untuk rinciannya, lihat Kuhn dan Portner (2006) dan entri pada tegang dan aspek .

3.2 Semantik TL

Sebelumnya diusulkan, meski secara informal, beberapa semantik berbeda untuk TL. Yang paling sederhana pada dasarnya adalah semantik dunia yang mungkin dengan gaya semantik Kripke untuk logika modal, yang diberikan dalam model preseden temporal berbasis instan, yang kemudian disebut kerangka temporal . Bingkai temporal \ (\ mathcal {T} = \ left \ langle T, \ prec \ right \ rangle \) mendefinisikan arus waktu di mana makna dari operator tegang harus didefinisikan. Perhatikan bahwa, sejauh ini, tidak ada kondisi seperti transitivity atau irreflexivity pada relasi "precedence" \ (\ prec \) yang dikenakan.
Model temporal untuk satu set proposisi atom \ (PROP \) adalah triple \ (\ mathcal {M} = \ left \ langle T, \ prec, V \ right \ rangle, \) di mana \ (\ left \ langle T , \ prec \ right \ rangle \) adalah kerangka temporal dan \ (V \) adalah penilaian yang diberikan ke setiap \ (p \ in {PROP} \) satu set instants waktu \ (V (p) \ subseteq T \ ) di mana \ (p \) dinyatakan benar. Secara setara, penafsiran \ (PROP \) di \ (\ mathcal {T} \) adalah pemetaan \ (I: T \ times {PROP} \ to \ {true, false \} \) yang memberikan nilai kebenaran kepada setiap proposisi atom pada setiap waktu instan dalam kerangka temporal. Kebenaran dari formula TL pada waktu tertentu instan \ (t \) dalam model temporal tertentu \ (\ mathcal {M} \) didefinisikan secara induktif sebagai berikut:
\ [\ begin {align} \ mathcal {M}, t \ model p & \ text {iff} t \ in V (p), \ text {for} p \ in {PROP}; \ \ \ mathcal {M}, t \ models \ neg \ psi & \ text {jika bukan itu masalahnya} \ mathcal {M}, t \ models \ psi; \ \ \ mathcal {M}, t \ models \ varphi \ vee \ psi & \ text {iff} \ mathcal {M}, t \ models \ varphi \ text {or} \ mathcal {M}, t \ models \ psi ; \ \ \ mathcal {M}, t \ models H \ varphi & \ text {iff} \ mathcal {M}, t '\ models \ varphi \ text {untuk semua instants waktu} t' \ text {seperti itu} t ' \ prec t; \ \ \ mathcal {M}, t \ models G \ varphi & \ text {iff} \ mathcal {M}, t '\ models \ varphi \ text {untuk semua instants waktu} t' \ text {seperti itu} t \ prec t '. \ end {align} \] Rumus \ (\ varphi \) dari TL berlaku , dilambangkan \ (\ models \ varphi, \) jika benar setiap instants dalam semua model temporal; formula \ (\ varphi \) dapat diterima jika benar pada suatu waktu instan dalam beberapa model temporal.

3.3 Terjemahan standar TL menjadi logika orde pertama

Bahasa dan semantik TL dapat diterjemahkan ke logika orde pertama klasik sebagai berikut. Misalkan himpunan proposisi atom dari TL adalah \ ({PROP} = \ left \ {p_ {0}, p_ {1}, ... \ right \}. \) Misalkan \ (L_ {1} \) menjadi sebuah bahasa orde pertama dengan \ (=, \) simbol predikat biner \ (R, \) dan satu set simbol tanda predikat yang tidak diketahui \ (\ mathcal {P} = \ left \ {P_ {0}, P_ {1} ,...\kanan\}.\)
Terjemahan standar (lihat misalnya van Benthem 1983) \ (ST \) dari TL ke \ (L_ {1} \) sekarang didefinisikan sebagai berikut, di mana \ (\ theta [y / x] \) adalah hasil dari penggabungan \ (y \) untuk semua kejadian bebas \ (x \) di \ (\ theta: \)
\ [\ begin {align} ST (p_ {i}) & = P_ {i} (x); \\ ST (\ bot) & = \ bot; \ \ ST (\ varphi \ lor \ psi) & = ST (\ varphi) \ lor ST (\ psi); \ \ ST (G \ varphi) & = \ forall y (xRy \ rightarrow ST (\ varphi) [y / x]), \ text {where} y \ text {adalah variabel segar;} \\ ST (H \ varphi) & = \ forall y (yRx \ rightarrow ST (\ varphi) [y / x]), \ text {where} y \ text {adalah variabel segar}} end {align} \] Kemudian mengikuti itu
\ [\ begin {align} ST (F \ varphi) & = \ ada y (xRy \ wedge ST (\ varphi) [y / x]), \\ ST (P \ varphi) & = \ ada y (yRx \ baji ST (\ varphi) [y / x]). \ end {align} \]

Contoh :
\ (ST (Gp_ {1} \ lor FHp_ {2}) = \ forall y (xRy \ rightarrow P_ {1} y) \ lor \ ada y (xRy \ wedge \ forall z (zRy \ rightarrow P_ {2} z )). \)

Sekarang, setiap model temporal \ (\ mathcal {M} = \ left \ langle T, \ prec, V \ right \ rangle \) dapat dianggap sebagai model \ (L_ {1} \) dengan menafsirkan \ (R \ ) sebagai \ (\ prec \) dan masing-masing \ (P_ {i} \) sebagai \ (V (p_ {i}). \) Kemudian:
\ [\ begin {align} \ mathcal {M}, t \ models \ varphi & \ text {iff} \ mathcal {M} \ models ST (\ varphi) [x: = t], \\ \ mathcal {M} \ models \ varphi & \ text {iff} \ mathcal {M} \ models \ forall x ST (\ varphi). \ end {align} \] Dengan sedikit perhatian ekstra untuk menggunakan kembali variabel individual, TL dapat diterjemahkan dalam fragmen dua variabel FO \ (^ {2} \) dari logika orde pertama, yang pada akhirnya menyiratkan penolakan validitas di TL. Misalnya, contoh di atas dapat ditulis ulang secara ekivalen
\ [ST (Gp_ {1} \ lor FHp_ {2}) = \ forall y (xRy \ rightarrow P_ {1} y) \ lor \ ada y (xRy \ wedge \ forall x (xRy \ rightarrow P_ {2} x )). \] Jika simbol predikat unary dari \ (\ mathcal {P} \) dianggap sebagai variabel predikat, yang menghasilkan bahasa orde kedua \ (L_ {2}. \) Kemudian, setiap kerangka temporal dapat dianggap sebagai \ (L_ {2} \) - model, di mana variabel predikat mewakili penilaian masing-masing proposisi atom. Misalkan \ overline {P} \ phi \) menunjukkan penutupan universal dari \ (L_ {2} \) - formula \ (\ phi \) atas semua variabel predikat yang terjadi di dalamnya. Kemudian untuk formula TL \ (\ varphi \) dan temporal frame \ (\ mathcal {T}: \) \ [\ mathcal {T} \ models \ varphi \ text {iff} \ mathcal {T} \ models \ forall \ overline {P} \ forall x ST (\ varphi). \]
Karena itu,
\ [\ models \ varphi \ text {iff} \ models \ forall \ overline {P} \ forall x ST (\ varphi). \] Jadi, validitas formula temporal dalam model adalah properti pesanan pertama, sedangkan validitas dalam bingkai adalah properti pesanan kedua.
Rumus temporal \ (\ varphi \) mendefinisikan kelas kerangka temporal yang valid. Demikian juga, kalimat orde pertama di \ (\ prec \) dan \ (= \) mendefinisikan kelas kerangka temporal di mana itu benar. Misalnya, seperti yang telah kita catat sebelumnya, \ (\ forall x \ forall y (x = y \ vee x \ prec y \ vee y \ prec x) \) mendefinisikan kelas frame dengan relasi diutamakan yang terhubung \ (\ prec. \ ) Rumus temporal \ (\ varphi \) dikatakan sesuai dengan kalimat orde pertama \ (\ theta \) jika \ (\ varphi \) mendefinisikan kelas frame yang sama yang didefinisikan (\ theta \). Seperti yang akan kita lihat nanti, banyak tapi tidak semua sifat urutan pertama dari kerangka temporal didefinisikan oleh rumus temporal dan, sebaliknya, banyak tapi tidak semua sifat kerangka temporal yang dapat didefinisikan oleh rumus temporal adalah urutan pertama yang dapat didefinisikan. Jadi, korespondensi non-sepele antara logika temporal dan logika orde pertama sebagai bahasa alternatif untuk menggambarkan sifat arus waktu muncul. Korespondensi ini, yang didasarkan pada persamaan di atas, merupakan inti dari teori korespondensi antara modal dan logika klasik, yang menawarkan perlakuan sistematis terhadap berbagai aspek logika temporal seperti teori ekspresif, determinasi, dan model dengan alat dan teknik klasik. logika. Untuk detail lebih lanjut lihat Rescher dan Urquhart (1971, Bab XI), van Benthem (1983; 1995), Blackburn dkk. (2006) dan masuknya logika modal .

3.4 TL vs logika orde pertama dan deret waktu McTaggart

Hubungan antara pendekatan yang berbeda untuk memformalisasikan logika waktu adalah beberapa relevansi dengan pertanyaan filosofis mengenai sifat waktu. Tentu saja, pada masa-masa awal logika temporal, pendekatan modal yang diwakili oleh Prior's Tense Logic dan cabangnya dianggap sebagai saingan pendekatan yang lebih konvensional dengan menggunakan logika orde pertama. Persaingan ini mencerminkan seperangkat isu filosofis mendasar yang terkait dengan karya McTaggart. Karya ini sangat terkenal, dalam konteks logika temporal, karena memperkenalkan perbedaan antara "seri A" dan "seri B". Dengan "seri A" ini, intinya, karakterisasi kejadian seperti Masa Lalu, Masa Kini, atau Masa Depan. Sebaliknya, "B-series" melibatkan karakterisasi mereka sebagai "Previous" atau "Later" yang relatif lebih rendah. Representasi A-series dari waktu secara tak terelakkan memilih momen tertentu seperti sekarang. Tentu saja, pada waktu yang berbeda, saat yang berbeda hadir - keadaan yang, mengikuti kesimpulan logis, membuat McTaggart menegaskan bahwa waktu itu sendiri tidak nyata (lihat Mellor 1981). Representasi B-series tidak memiliki tempat untuk konsep masa kini, alih-alih mengambil bentuk pandangan sinoptik sepanjang masa dan keterkaitan (yang tidak lekang oleh waktu) antara bagian-bagiannya.
Ada keterkaitan yang jelas antara seri A dan pendekatan modal dan antara seri B dan pendekatan orde pertama. Dalam terminologi Massey (1969), penganut pendekatan terdahulu adalah "tensers", sedangkan penganut yang terakhir adalah "detenser". Masalah ini terkait pada pertanyaan tentang bagaimana serius mengambil representasi ruang-waktu sebagai entitas empat dimensi tunggal di mana keempat dimensi setidaknya dalam beberapa hal dengan pijakan yang sama. Mengingat Teori Relativitas, ini bisa dibilang merupakan masalah Fisika daripada Filsafat.

3.5 Sistem aksiomatik \ (\ mathbf {K} _ {t} \) untuk TL

Seperti setiap sistem logis formal, logika temporal memiliki dua aspek utama, semantik dan deduktif . Disini kami akan menyajikan secara singkat jenis sistem deduktif yang paling sederhana, yaitu. sistem aksiomatis, untuk beberapa sistem logika temporal yang paling penting.
Logika temporal minimal \ (\ mathbf {K} _ {t} \) axiomatizing semua formula TL yang valid, mungkin pertama kali diusulkan oleh Lemmon (lihat Rescher dan Urquhart 1971, Bab VI), mengikuti sistem yang sebelumnya diusulkan oleh Hamblin dan Prior. Ini memperluas logika propositional klasik CL dengan skema aksioma berikut:

\ ((K_G) \) \ (G (\ varphi \ rightarrow \ psi) \ rightarrow (G \ varphi \ rightarrow G \ psi), \)
"Apapun yang akan selalu mengikuti dari apa yang selalu akan, selalu akan"
\ ((K_H) \) \ (H (\ varphi \ rightarrow \ psi) \ rightarrow (H \ varphi \ rightarrow H \ psi), \)
"Apapun yang selalu diikuti dari apa yang selalu ada, selalu"
(GP) \ (\ varphi \ rightarrow GP \ varphi, \)
"Apa yang akan selalu terjadi"
(HF) \ (\ varphi \ rightarrow HF \ varphi, \)
"Apa, selalu menjadi"

dan aturan inferensi berikut, di mana \ (\ vdash \) berarti, seperti biasa, " diturunkan ":

(NEC \ (_ G \)) Jika \ (\ vdash \ varphi \) maka \ (\ vdash G \ varphi \)
(NEG \ (_ H \)) Jika \ (\ vdash \ varphi \) maka \ (\ vdash H \ varphi \)

ditambahkan ke Modus Ponens klasik: if \ (\ vdash \ varphi \) dan \ (\ vdash \ varphi \ rightarrow \ psi \) lalu \ (\ vdash \ psi. \)
Aksioma (GP) dan (HF) secara teknis mengatakan bahwa operator temporal \ (H \) dan \ (G \) sesuai dengan hubungan temporal yang saling berlawanan.
Sistem aksiomatis \ (\ mathbf {K} _ {t} \) terdengar dan lengkap untuk validitas di TL, dalam arti dapat memperoleh semua rumus TL yang valid dan hanya untuk itu. Sebagai bukti, lihat misalnya, Rescher dan Urquhart 1971 dan Goldblatt 1987. Dengan demikian, teorema \ (\ mathbf {K} _ {t} \) mengungkapkan sifat-sifat dari operator tegang yang tidak bergantung pada asumsi spesifik apapun tentang hubungan preseden temporal.

3.6 Mengekspresikan sifat temporal di TL dan ekstensi \ (\ mathbf {K} _ {t} \)

3.6.1 Mengekspresikan beberapa sifat temporal di TL

Kita mengatakan bahwa formula temporal mengekspresikan sebuah properti \ (\ mathcal {P} \) dari frame temporal jika mendefinisikan kelas frame temporal yang memenuhi properti \ (\ mathcal {P}. \)
Rumus dari TL dapat mengekspresikan banyak sifat alami dari aliran waktu. Diambil sebagai aksioma tambahan, ini akan mengekspresikan berbagai asumsi filosofis atau ontologis tentang waktu. Berikut adalah beberapa contoh penting dari korespondensi antara formula TL dan sifat kerangka temporal (ingatlah bahwa \ (E p = Pp \ vee p \ vee Fp \)):

(REF)	(\ varphi \ rightarrow \ varphi, \) \ (\ varphi \ rightarrow F \ varphi, \) \ (\ varphi \ rightarrow P \ varphi \) (refleksivitas \ (\ prec \))
(TRAN)	salah satu \ (Gp \ rightarrow GGp, \) \ (Hp \ rightarrow HHp, \) \ (FFp \ rightarrow Fp, \) \ (PPp \ rightarrow Pp \) (transitivitas \ (\ prec \))
(MENGEMIS)	\ (H \ bot \ vee PH \ bot \) (waktu memiliki awal (dengan asumsi irreflexivity))
(NOBEG)	\ (P \ top \) atau \ (Hp \ rightarrow Pp \) (waktu tidak memiliki awal)
(NOEND)	\ (F \ atas \) atau \ (Gp \ rightarrow Fp \) (waktu tidak ada habisnya)
(LIN-F)	\ (PFp \ rightarrow Ep \) (linearitas di masa depan, yang berarti \ (\ forall {t}, t ', t' '((t' '\ prec {t} \ land t' '\ prec t') \ rightarrow ({t} \ prec t '\ vee {t} = t' \ vee t '\ prec {t}))) \)
(LIN-P)	\ (FPp \ rightarrow Ep \) (linearitas di masa lalu, yang berarti \ (\ forall {t}, t ', t' '((t} \ prec t' '\ land t' \ prec t '') \ rightarrow ({t} \ prec t '\ vee {t} = t' \ vee t '\ prec {t}))) \)
(LIN)	\ ((FPp \ lor PFp) \ rightarrow Ep \) (linearitas)
(PADAT)	\ (GGp \ rightarrow Gp \) atau \ (Fp \ rightarrow FFp \) (massa jenis)
(IND \ (_ {G} \))	\ (Fp \ wedge G (p \ rightarrow Fp) \ rightarrow GFp \) (induksi ke depan)
(IND \ (_ {H} \))	\ (Pp \ wedge H (p \ rightarrow Pp) \ rightarrow HPp \) (induksi terbelakang)
(WELLORD)	\ (H (Hp \ rightarrow p) \ rightarrow Hp \) (transitivity plus well-ordering)
(COMPL)	\ (A (Hp \ rightarrow FHp) \ rightarrow (Hp \ rightarrow Gp) \) (Dedekind kelengkapan)

Perhatikan bahwa IND \ (_ {G} \) menyiratkan disketitas ke belakang dan IND \ (_ {H} \) menyiratkan disketitas ke depan, namun tidak sebaliknya. Ingatlah bahwa dua properti terakhir di atas, (WELLORD) dan (COMPL), tidak dapat didefinisikan dengan kalimat orde pertama. Contoh lain dari formula temporal yang tidak sesuai dengan kalimat orde pertama (kecuali linearitas diasumsikan) adalah \ ({G} F {p} \ rightarrow F {G} {p}. \ Di sisi lain, beberapa sederhana urutan pertama yang dapat didefinisikan dari kerangka temporal, seperti irreflexivity , yang dinyatakan oleh \ (\ forall {t} \ neg ({t} \ prec {t}), \) tidak didefinisikan oleh formula temporal manapun. Untuk lebih lanjut tentang aksioma temporal yang mengungkapkan sifat waktu dan rincian tentang hasil tersebut, lihat Segerberg (1970); Rescher dan Urquhart (1971); Burgess (1979); van Benthem (1983; 1995); dan Goldblatt (1987).

3.6.2 Beberapa ekstensi aksiomatik dari \ (\ mathbf {K} _ {t} \)

Dengan memperluas \ (\ mathbf {K} _ {t} \) dengan aksioma tambahan yang sesuai, seseorang dapat menangkap validitas sejumlah model linier alami untuk arus waktu. Artinya, ekstensi aksiomatik ini terdengar dan lengkap untuk bingkai temporal atau kelas temporal frame yang sesuai.
\ [\ begin {align} \ mathbf {K4} _ {t} & = \ mathbf {K} _ {t} + \ text {(TRAN): semua frame transitif.} \\ \ mathbf {S4} _ {t } & = \ mathbf {K} _ {t} + \ text {(REF) + (TRAN): semua pemesanan sebagian.} \\ \ mathbf {L} _ {t} & = \ mathbf {K} _ {t } + \ text {(TRAN) + (LIN): semua urutan linier yang ketat.} \\ \ mathbf {N} _ {t} & = \ mathbf {L} _ {t} + \ text {(NOEND) + ( IND \ (_ {G} \)) + (WELLORD):} \ langle \ mathbf {N, \ lt} \ rangle. \\ \ mathbf {Z} _ {t} & = \ mathbf {L} _ {t} + \ text {(NOBEG) + (NOEND) + (IND \ (_ {G} \)) + (IND \ ( _ {H} \)):} \ langle \ mathbf {Z, \ lt} \ rangle. \\ \ mathbf {Q} _ {t} & = \ mathbf {L} _ {t} + \ text {(NOBEG) + (NOEND) + (DENSE):} \ left \ langle \ mathbf {Q, \ lt } \ right \ rangle. \\ \ mathbf {R} _ {t} & = \ mathbf {L} _ {t} + \ text {(NOBEG) + (NOEND) + (DENSE) + (COMPL):} \ left \ langle \ mathbf { R, \ lt} \ right \ rangle. \ end {align} \] Semua logika ini ternyata dapat dipecahkan (yaitu memiliki set validitas yang dapat ditolak) yang biasanya ditunjukkan dengan membuktikan properti model yang terbatas , yang berarti bahwa setiap formula memuaskan dapat diterima dalam model yang terbatas; dalam kebanyakan kasus, sehubungan dengan model terbatas non-standar. Untuk bukti rinci tentang kelengkapan variasi sistem aksiomatomatis ini, serta bukti-bukti yang dapat diputuskan, lihat Segerberg (1970); Rescher dan Urquhart (1971); Burgess (1979); Burgess dan Gurevich (1985); dan Goldblatt (1987).
Beberapa ekstensi ini telah dipelajari pada hari-hari awal Logika Tegang, dan Prior (1967) melaporkan adanya kerja keras pada berbagai sistem yang diperoleh dengan mendalilkan berbagai kombinasi aksioma. Seperti biasa, fokus utamanya adalah pada cahaya yang dilemparkan oleh perlakuan logis terhadap waktu mengenai masalah klasik mengenai waktu, kebutuhan dan eksistensi, misalnya, argumen "deterministik" yang telah maju selama ini sehingga "apa yang akan terjadi, akan selalu ", sesuai dengan formula temporal modal \ (F {p} \ rightarrow \ Box F {p}. \) Lihat juga Thomason (1984) dan Finger et al. (2002).

4. Ekstensi TL selama arus waktu linier

Meskipun hanya disajikan secara informal, semantik asli Prior untuk TL tampaknya mengasumsikan aliran waktu linier, sementara bersikap acuh tak acuh terhadap aspek lain seperti discreteness versus density. Di sini kami menjelaskan beberapa ekstensi TL yang lebih penting dengan operator temporal tambahan untuk model linier waktu.

4.1 Menambahkan operator "waktu berikutnya"

Model temporal linear, tak terbatas, maju diskrit temporer \ (\ mathcal {M} = \ left \ langle T, \ prec, V \ right \ rangle, \) di mana setiap instan \ (t \) memiliki penerus langsung (unik) \ (s (t), \) adalah wajar untuk menambahkan operator temporal baru \ (X, \) neXttime (atau, besok ), dengan semantik:
\ [\ mathcal {M}, t \ models X \ varphi \ text {iff} \ mathcal {M}, s (t) \ models \ varphi. \] Operator \ (X \) memenuhi aksioma K

(K \ (X) \) \ (X (\ varphi \ to \ psi) \ ke (X \ varphi \ to X \ psi), \)

dan, pada model linear diskrit-depan, aksioma fungsionalitas:

(FUNC) \ (X \ lnot \ varphi \ leftrightarrow \ lnot X \ varphi. \)

Ini juga memungkinkan definisi rekursif dari \ (G: \)

(FP \ (_ G \)) \ (G \ varphi \ leftrightarrow (\ varphi \ wedge XG \ varphi), \) jika \ (\ prec \) diasumsikan bersifat refleksif, atau
(\ {Ir} _G \)) \ (G \ varphi \ leftrightarrow X (\ varphi \ wedge G \ varphi), \) jika \ (\ prec \) diasumsikan irreflexive.

Pada pemesanan bilangan asli \ (\ left \ langle \ mathbf {N, <} \ right \ rangle, \) operator \ (X \) dan \ (G \) juga memenuhi prinsip induksi ; Versi refleksif dari hal ini adalah:

(IND) \ (\ varphi \ wedge G (\ varphi \ rightarrow X \ varphi) \ rightarrow G \ varphi. \)

Sebenarnya, dalam bahasa dengan \ (G, H \) dan \ (X \) sistem berikut:

\ (\ mathbf {L} _ {t} (X) = \ mathbf {L} _ {t} \) + K \ (_ {X} \) + FUNC + FP \ (_ {G} \)
axiomatizes sepenuhnya logika temporal urutan linear tak terbatas, forward-diskrit, sementara

\ (\ mathbf {N} _ {t} (X) = \ mathbf {N} _ {t} \) + K \ (_ {X} \) + FUNC + FP \ (_ {G} \) + IND
axiomatizes sepenuhnya logika temporal dari \ (\ left \ langle \ mathbf {N}, s, <\ right \ rangle, \) di mana \ (s (n) = n + 1. \)

Analog masa lalu \ (Y \) ( Kemarin ) dari \ (X, \) dapat didefinisikan dan axiomatized juga.
Untuk detail lebih lanjut lihat Thomason (1984), Goldblatt (1987), dan Andréka dkk. (1995).

4.2 Menambah Sejak dan Sampai

Logika Tegang dasar sebelumnya dengan sintaks "PFGH" tidak terlalu ekspresif dan sejak diperkenalkannya berbagai ekstensi telah diajukan, sudah oleh Prior sendiri. Mungkin yang paling penting dari mereka adalah pengenalan operator temporal biner \ (S \) (" Karena ") dan \ (U \) (" Sampai ") oleh Hans Kamp dalam disertasi doktoralnya (Kamp 1968). Arti intuitifnya adalah ^{[ 2 ]}

\ (\ varphi S \ psi \) "\ (\ varphi \) telah benar sejak saat \ (\ psi \) benar"
\ (\ varphi U \ psi \) "\ (\ varphi \) akan menjadi benar sampai suatu saat ketika \ (\ psi \) benar"

Misalnya, mencatat bahwa 'kecuali' hanyalah cara lain untuk mengekspresikan disjungsi), kalimat " Saya akan terus berusaha sampai saya berhasil, kecuali jika saya mati sementara itu " dapat diformalkan dengan menggunakan Sampai dan proposisi atom khusus \ (\ mathrm {try} , \ mathrm {succeed}, \ mathrm {die} \) sebagai: \ (\ mathrm {try} \, U (\ mathrm {succeed} \ lor \ mathrm {die}). \) Sebagai contoh lain, " Sejak Mia meninggalkan rumah, Joe tidak bahagia dan telah minum sampai kehilangan kesadaran, berulang-ulang "dapat diformalkan dengan menggunakan Since and Until as:
\ [(\ text {Joe unhappy} \ land (\ text {Joe drinking} \ U \ lnot (\ text {Joe conscious}))) \ S (\ text {Mia meninggalkan rumah}). \] Semantik formal dari \ (S \) dan \ (U \) dalam model temporal dapat diberikan sebagai:
\ [\ begin {align} \ mathcal {M}, t \ vDash \ varphi S \ psi \ text {iff} & \ mathcal {M}, s \ vDash \ psi \ text {untuk beberapa} s \ text {sedemikian rupa sehingga } s \ preceq t \ \ & \ text {dan} \ mathcal {M}, u \ vDash \ varphi \ text {untuk setiap} teks \ {seperti itu} s \ preceq u \ prec t. \ \ \ mathcal {M}, t \ vDash \ varphi U \ psi \ text {iff} & \ mathcal {M}, s \ vDash \ psi \ text {untuk beberapa} s \ text {sedemikian rupa}} t \ preceq s \ \ & \ text {dan} \ mathcal {M}, u \ vDash \ varphi \ text {untuk setiap} u \ text {seperti itu} t \ preceq u \ prec s. \ end {align} \] Ini adalah definisi semantik dari versi refleksif dari \ (U \) dan \ (S, \) karena mereka menyertakan kemungkinan \ (\ psi \) memegang pada saat ini, dan kemudian tidak ada yang diperlukan tentang \ (\ varphi .) Operator dasar dasar sebelumnya (dalam versi refleksifnya) dapat dinyatakan dengan menggunakan \ (U \) dan \ (S \) sebagai \ (F \ varphi: = \ top U \ varphi \) dan \ (P \ varphi: = \ atas S \ varphi, \) sementara \ (X \) tidak dapat diekspresikan. Inilah versi yang diadopsi secara tradisional dalam ilmu komputer. Namun, orang mungkin berpendapat bahwa definisi yang lebih alami dari \ (U \) dan \ (S \) akan menjadi satu di mana waktu \ (s \) dibutuhkan secara ketat di masa depan (misalnya, di masa lalu) dari \ (t \) dan bahwa tidak ada persyaratan untuk kebenaran \ (\ varphi \) yang dikenakan pada saat ini. Ini adalah versi tidak fleksibel, atau ketat , yang kami nyatakan oleh \ (U ^ {s} \) dan \ (S ^ {s}. \) Mereka lebih ekspresif. Secara khusus, operator \ (X \) dan refleksif \ (U \) dan \ (S \) dapat didefinisikan dalam bentuk \ (U ^ {s} \) dan \ (S ^ {s}: \)
\ [\ begin {align} X \ varphi &: = \ bot U ^ {s} \ varphi, \\ \ varphi U \ psi &: = \ psi \ vee (\ varphi \ land \ varphi U ^ {s} \ psi), \ \ \ varphi S \ psi &: = \ psi \ vee (\ varphi \ land \ varphi S ^ {s} \ psi), \ end {align} \] namun umumnya tidak sebaliknya. Namun, pada bingkai linier diskrit depan \ (U ^ {s} \) dapat didefinisikan dalam bentuk \ (U \) dan \ (X: \) \ (\ varphi U ^ {s} \ psi = X (\ varphi U \ psi). \) Demikian juga, \ (S ^ {s} \) dapat didefinisikan dari \ (S \) pada frame diskrit mundur menggunakan analog sebelumnya dari \ (X. \)
Berbagai operator alam lainnya dapat didefinisikan dalam bentuk \ (U \) dan \ (S \) atau versi ketatnya, misalnya Sebelum , didefinisikan sebagai \ (\ varphi B \ psi: = \ lnot ((\ lnot \ varphi) U \ psi) \) dan artinya "\ (\ varphi \) akan terjadi sebelum \ (\ psi \) (yang mungkin atau mungkin tidak terjadi sama sekali)".
Hans Kamp (1968) membuktikan hasil kelengkapan ekspresif yang luar biasa berikut tentang bahasa temporal dengan Since and Until:

Setiap operator temporal pada kelas Dedekind urutan linier lengkap yang dapat didefinisikan dalam logika orde pertama dapat dinyatakan dalam bentuk \ (S ^ {s} \) dan \ (U ^ {s} \) .

J. Stavi kemudian mengusulkan dua operator lagi, \ (S ^ {\ prime} \) dan \ (U ^ {\ prime} \) yang bila ditambahkan ke \ (S ^ {s} \) dan \ (U ^ {s } \) membuat bahasa temporal secara ekspresif lengkap pada semua frame linier , lihat misalnya (Gabbay et al 1994). Di sisi lain, Gabbay telah menunjukkan ( ibid. ) Bahwa tidak terbatasnya jumlah operator baru yang dapat membuat bahasa temporal selesai secara fungsional pada semua pemesanan parsial .
Burgess (1982a) menyediakan sistem aksiomatik yang lengkap dari logika Sejak-Sampai di kelas semua arus waktu linier, yang selanjutnya disederhanakan oleh Xu (1988). Ini memperluas logika propositional klasik dengan skema aksioma berikut (untuk versi refleksif) dan duet mereka, dengan \ (S \) dan \ (U \) bertukar:

\ (G \ varphi \ rightarrow \ varphi, \)
\ (G (\ varphi \ rightarrow \ psi) \ rightarrow \ varphi U \ chi \ rightarrow \ psi U \ chi, \)
\ (G (\ varphi \ rightarrow \ psi) \ rightarrow \ chi U \ varphi \ rightarrow \ chi U \ psi, \)
\ (\ varphi \ wedge \ chi U \ psi \ rightarrow \ chi U (\ psi \ wedge \ chi S \ varphi), \)
\ (\ varphi U \ psi \ rightarrow (\ varphi \ wedge \ varphi U \ psi) U \ psi, \)
\ (\ varphi U (\ varphi \ wedge \ varphi U \ psi) \ rightarrow \ varphi U \ psi; \)
\ (\ varphi U \ psi \ wedge \ chi U \ theta \ rightarrow (\ varphi \ wedge \ chi) U (\ psi \ wedge \ theta) \ vee (\ varphi \ wedge \ chi) U (\ psi \ wedge \ chi) \ vee (\ varphi \ wedge \ chi) U (\ varphi \ wedge \ theta). \)

dan aturan inferensi NEC \ (_ {H} \) dan NEC \ (_ {G}. \) Aksiomatomatisasi ini, yang diterjemahkan untuk versi yang ketat \ (S ^ {s} \) dan \ (U ^ {s}, \) diperpanjang oleh Venema (1993) untuk melengkapi sistem aksiomatik untuk \ (S ^ {s} \) dan \ (U ^ {s} \) untuk:

semua urutan linear diskrit , dengan menambahkan \ (F ^ {s} \ top \ rightarrow \ bot U ^ {s} \ top \) dan ganda \ (P ^ {s} \ top \ rightarrow \ bot S ^ {s} \puncak.\)
semua pesanan dengan baik , dengan menambahkan lebih jauh \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ) U ^ {s} \ varphi, \)
\ (\ left \ langle \ mathbf {N, <} \ right \ rangle, \) dengan menambahkan \ (F ^ {s} \ top \) ke sistem sebelumnya.

Untuk rincian lebih lanjut dan hasil terkait lainnya lihat Burgess (1984), Thomason (1984), Gabbay et al. (1994), Finger et al. (2002), Hodkinson dan Reynolds (2006).

4.3 Waktu temporer logika temporal LTL

Logika temporal yang paling populer dan banyak digunakan dalam ilmu komputer adalah logika temporal waktu tempuh LTL, yang diusulkan di kertas mani Pnueli (1977) dan pertama secara eksplisit dicekal dan dipelajari di Gabbay et al. (1980). LTL hanya melibatkan \ (X, \) \ (G \) dan \ (U \) saja (tidak ada operator masa lalu), ditafsirkan di \ (\ left \ langle \ mathbf {N, <} \ right \ rangle, \) dan sangat berguna untuk mengekspresikan keamanan, liveness, fairness, dan presedence properties dari perhitungan tak terbatas dalam sistem reaktif Manna dan Pnueli (1992); lihat penjelasan sifat-sifat ini pada Bagian 10.1 . Contoh spesifikasi seperti itu: " Setiap saat ketika sebuah pesan dikirim, sebuah bukti penerimaan akhirnya akan dikembalikan dan pesannya tidak akan ditandai 'dikirim' sebelum pengakuan penerimaan dikembalikan ", yang dapat dilakukan secara formal di LTL sebagai:
\ [G (\ mathrm {Dikirim} \ ke (\ lnot \ mathrm {MarkedSent} \ U \ \ mathrm {AckReturned})). \] Berikut adalah sistem aksiomatik yang lengkap untuk LTL, perpanjang logika proposisi klasik hanya dengan aksioma K standar untuk \ (G \) dan \ (X \) dan aturan inferensi MP dan NEC \ (_ {G}, \) plus aksioma yang mengekspresikan karakterisasi fixed-point dari \ (G \) dan \ (U: \)

(K \ (_ G \)) \ (G (\ varphi \ rightarrow \ psi) \ rightarrow (G \ varphi \ rightarrow G \ psi) \)
(K \ (_ X \)) \ (X (\ varphi \ rightarrow \ psi) \ rightarrow (X \ varphi \ rightarrow X \ psi) \)
(FUNC) \ (X \ lnot \ varphi \ leftrightarrow \ lnot X \ varphi \)
(FP \ (_ G \)) \ (G \ varphi \ leftrightarrow (\ varphi \ wedge XG \ varphi) \)
(GFP \ (_ G \)) \ (\ psi \ tanah G (\ psi \ rightarrow (\ varphi \ land X \ psi)) \ rightarrow G \ varphi \)
(FP \ (_ U \)) \ (\ varphi U \ psi \ leftrightarrow (\ psi \ vee (\ varphi \ wedge X (\ varphi U \ psi))))
(LFP \ (_ U \)) \ (G ((\ psi \ vee (\ varphi \ wedge X \ theta)) \ rightarrow \ theta) \ rightarrow (\ varphi U \ psi \ rightarrow \ theta) \)

Dalam istilah teknis, aksioma FP \ (_ {G} \) mengatakan bahwa \ (G \ varphi \) adalah titik tetap operator \ (\ Gamma_ {G} \) yang didefinisikan oleh \ (\ Gamma_ {G} \ theta) = \ varphi \ land X \ theta, \) sedangkan GFP \ (_ {G} \) mengatakan bahwa \ (G \ varphi \) adalah (set-secara teoritis, dalam hal perpanjangannya) post-fixed terbesar titik \ (\ Gamma_ {G}. \) Demikian juga, aksioma FP \ (_ {U} \) mengatakan bahwa \ (\ varphi U \ psi \) adalah titik tetap operator \ (\ Gamma_ {U} \) yang didefinisikan oleh \ (\ Gamma_ {U} (\ theta) = \ psi \ lor (\ varphi \ land X \ theta), \) sedangkan LFP \ (_ {U} \) mengatakan bahwa \ (\ varphi U \ psi \) adalah titik pra-fixed yang paling awal dari \ (\ Gamma_ {U}. \) Perhatikan bahwa GFP \ (_ {G} \) secara umum melakukan aksioma Induksi (IND): \ (\ varphi \ wedge G (\ varphi \ rightarrow X \ varphi) \ rightarrow G \ varphi. \) Sebenarnya, aksioma GFP \ (_ {G} \) dapat diganti dengan aturan Induksi berikut, diturunkan dalam sistem di atas:

Jika \ (\ vdash \ psi \ rightarrow \ varphi \ land X \ psi \) maka \ (\ vdash \ psi \ rightarrow G \ varphi. \)

Demikian juga, LFP \ (_ {U} \) dapat diganti dengan aturan derivatif berikut ini:

Jika \ (\ vdash (\ psi \ vee (\ varphi \ wedge X \ theta)) \ rightarrow \ theta \) maka \ (\ vdash \ varphi U \ psi \ rightarrow \ theta. \)

Sebenarnya, setelah mendefinisikan \ (Gp \) sebagai \ (\ lnot (\ top U \ lnot p), \) aksioma FP \ (_ {G} \) dan GFP \ (_ {G} \) menjadi turun dari beristirahat.
Bukti kelengkapan variasi sistem aksiomatik di atas dapat ditemukan di Gabbay dkk. (1980; 1994) dan Goldblatt (1987).
Semua logika yang disebutkan di bagian ini memiliki properti model hingga (biasanya, berkenaan dengan model tidak standar) dan oleh karena itu dapat dipecahkan. Bukti dugaan dapat ditemukan dalam referensi kelengkapan.

5. Membentuk time temporal logic

Seperti disebutkan sebelumnya, gagasan tentang waktu mengalir dengan masa depan deterministik, linier masa lalu dan tidak deterministik, bercabang memiliki sejarah yang terhormat; Kami telah menyebutkan perbedaan pandangan yang terkait dengan Ockham dan Peirce ( Bagian 1 ). Gagasan tentang waktu dengan masa depan yang bercabang juga telah terhibur dalam literatur non-ilmiah, misalnya J. Borges '"Taman forking paths", dan juga dalam banyak tulisan fiksi ilmiah.

5.1 Logika waktu bercabang yang dimulai dari kebutuhan historis

Sebelum berpendapat bahwa kekeliruan Argumen Master Diodorus terletak pada anggapan bahwa apa pun, atau tidak, atau akan, atau tidak akan pernah ada, sebelumnya, tentu saja - jadi, dengan asumsi bahwa masa depan deterministik. Dalam analisisnya, Prior mendukung pandangan Aristoteles bahwa "sementara sekarang berada di luar kekuatan manusia atau dewa untuk mempengaruhi masa lalu, ada masa depan alternatif di antara pilihan mana yang mungkin dilakukan". Untuk mengatasi masalah yang ditunjukkan oleh Aristoteles dan Diodorus, Prior menginginkan, antara lain, untuk menangkap logika kebutuhan historis . Analisis filosofisnya dan pencarian formalisasi argumen untuk "ketidakcocokan foreknowledge (dan kedepan kebenaran) dan indeterminisme" membawanya untuk mempertimbangkan dua formalisasi logika temporal waktu bercabang, yang mencerminkan "Ockham" (atau "aktualis") dan "Peircean" dilihat sebelumnya. Untuk rincian tentang pandangan Prior dan analisis yang memotivasi, lihat Prior (1967, Ch VII), Rescher and Urquhart (1971, Ch VII), Øhrstrøm dan Hasle (1995, Chs.6 dan 3.2) dan entri di Arthur Prior .

5.2 logika temporal Ockham

Semantik Ockham untuk logika temporal secara intuitif dikandung oleh Prior namun dikembangkan secara formal kemudian, di Burgess (1979); lihat juga Øhrstrøm dan Hasle (1995) dan Thomason (1984). Hal ini didasarkan pada asumsi bahwa sementara masa lalu tidak dapat diubah, masa depan dapat mengambil kursus yang berbeda dari saat sekarang; Namun, setiap saat satu kemungkinan masa depan dianggap aktual , dan ini terkait dengan masa depan ini bahwa pernyataan masa depan akan dievaluasi. Dengan demikian, ungkapan-ungkapan 'selalu / kadang-kadang di masa depan' sekarang berarti 'selalu / kadang-kadang di masa depan dianggap aktual '. Selanjutnya, masa depan yang sebenarnya dianggap ditentukan, yaitu linier. Secara formal, ini berarti, pertama, bahwa arus alami waktu untuk semantik Ockham adalah sejenis pohon dan bukan linear, dan kedua, bahwa formula temporal dievaluasi relatif tidak hanya sesaat, tapi juga pada sejarah yang mengandung seketika itu. Namun, kami mencatat bahwa menurut Belnap (2001, Bab 6) gagasan tentang "masa depan yang sebenarnya" bermasalah dan dia hanya akan mengatakan bahwa formula yang tegang pada umumnya tidak benar atau salah pada saat tertentu; Mereka benar atau salah berpasangan (momen, sejarah), tapi tanpa komitmen terhadap adanya "masa depan yang sebenarnya". Selain itu, Belnap dan Green (1994) berpendapat bahwa "masa depan" sebenarnya, yang mereka sebut "Garis Merah Tipis", bukanlah gagasan yang berkelanjutan dan "seseorang dapat memahami struktur yang tidak pasti dan bercabang untuk dunia kita tanpa mendalilkan yang sebenarnya. masa depan sebagai dibedakan di antara kemungkinan ", malah mempromosikan gagasan" masa depan yang terbuka ".
Dalam kasus apapun, untuk merujuk, dan mengukur, kemungkinan sejarah yang melewati instan saat ini, sebuah operator modal tambahan \ (\ diamondsuit \) dan dual \ (\ Box \) diperkenalkan, dengan \ (\ diamondsuit \ varphi \) dinyatakan benar pada (\ (h}, {t} \)) jika ada beberapa riwayat \ (h '\) sampai \ (t \) sedemikian rupa sehingga \ (\ varphi \) benar adanya (\ ({h '}, {t} \)). Kemudian \ (\ diamondsuit F \ varphi \) mengatakan bahwa "\ (\ varphi \) memegang akhirnya di beberapa masa depan yang mungkin", sementara \ (\ Box F \ varphi \) mengatakan bahwa "\ (\ varphi \) pada akhirnya berlaku pada semua kemungkinan masa depan ", yaitu, tentu saja, pasti akan jadi masalahnya.
Secara formal, bahasa logika temporal Ockhamis proporsional yang berurutan, OBTL, mengandung, selain modalitas sementara \ (F, P, \) sebuah modalitas \ (\ diamondsuit \) untuk merujuk pada kemungkinan sejarah yang melewati saat ini. Rumus OBTL didefinisikan sebagai berikut:
\ \ \ varphi = \ bot \ mid p \ mid \ varphi \ rightarrow \ varphi \ mid P \ varphi \ mid F \ varphi \ mid \ diamondsuit \ varphi. \] Misalnya, kalimat " Kehidupan di Bumi pada akhirnya akan berhenti ada " hanya merujuk pada masa depan yang saat ini dianggap aktual dan diterjemahkan ke dalam OBTL hanya sebagai \ (F \ lnot \ text {LifeOnEarth}, \) sementara " Kehidupan di Bumi pada akhirnya akan tidak ada lagi jika terjadi perang baru, namun kemanusiaan dapat mengubah jalannya sejarah untuk menghindari perang baru "secara alami akan diterjemahkan ke dalam OBTL sebagai
\ [(F \ text {War} \ to F \ lnot \ text {LifeOnEarth}) \ land \ Diamond \ lnot F \ text {War}. \] Untuk contoh yang lebih terlibat: " Pada setiap masa depan yang mungkin dimana kehidupan di Bumi pada akhirnya akan lenyap, setiap hari ketika ada kehidupan di Bumi, manusia dapat mengubah jalannya sejarah sehingga akan ada kehidupan di Bumi sehari setelah " bisa diterjemahkan sebagai
\ [\ Box (F \ lnot \ text {LifeOnEarth} \ ke G (\ text {LifeOnEarth} \ to \ Diamond X \, \ text {LifeOnEarth})). \] Untuk secara formal menggambarkan semantik Ockham kita memerlukan beberapa definisi teknis. (Mereka sedikit berbeda dari Burgess (1979) tapi setara dengan mereka.) Bingkai temporal \ (\ mathcal {T} = \ left \ langle T, \ prec \ right \ rangle \) adalah pohon jika \ (\ prec \) adalah pemesanan parsial pada \ (T \) dan setiap \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ . \) Sejarah di pohon adalah kumpulan instants yang maksimal (yaitu tidak dapat diperpanjang) yang dipesan secara linier oleh \ (\ prec. \) Kami menunjukkan rangkaian semua sejarah dalam \ (\ mathcal {T} \) oleh \ ( \ mathcal {H} (\ mathcal {T}). \) Cabang pada sejarah \ (h \) dimulai dari seketika \ (t \ in h \) adalah pasangan \ ((h, t) \) yang terdiri dari bagian \ (h \) di atas \ (t, \) yaitu, himpunan semua instants \ (t '\) pada \ (h \) sedemikian rupa sehingga \ (t \ preceq t'. \) himpunan sejarah yang lewat seketika \ (t \) di \ (\ mathcal {T} \) akan dilambangkan dengan \ (\ mathcal {H} (t). \) Secara intuitif, cabang \ ((h, t) \) mewakili instan \ (t \) bersamaan dengan masa depannya yang sebenarnya.
Sebuah valuasi di pohon \ (\ left \ langle T, \ prec \ right \ rangle \) adalah pemetaan \ (V \) yang menetapkan setiap proposisi atom \ (p \ in {PROP} \) satu set cabang \ (V (p) \ subseteq \ mathcal {H} \ times T \) dimana \ (p \) dinyatakan benar. Dengan demikian, kebenaran Ockhamis dari proposisi atom bergantung baik pada waktu instan maupun pada masa depan yang mungkin di mana hal itu dipertimbangkan. Model pohon Ockhamist adalah tuple \ (\ mathcal {M} = \ left \ langle T, \ prec, V \ right \ rangle \) di mana \ (\ left \ langle T, \ prec \ right \ rangle \) adalah sebuah pohon dan \ (V \) adalah penilaian di dalamnya. Sekarang, definisi dari (Ockhamist) kebenaran dari formula OBTL di \ (\ mathcal {M}, \) relatif terhadap cabang \ ((h, t) \) di mana \ (h \ in \ mathcal {H} \ ) dan \ (t \ in h \) , diberikan secara rekursif sebagai berikut:
\ n \ begin {align} \ mathcal {M}, h, t & \ models p \ text {iff} (h, t) \ in V (p), \ text {for any} p \ in {PROP}, \ \ \ \ mathcal {M}, h, t & \ not \ models \ bot, \\ \ mathcal {M}, h, t & \ models \ phi \ lor \ psi \ text {iff} \ mathcal {M}, \ h, t \ models \ phi \ text {or} \ mathcal {M}, h, t \ models \ psi, \\ \ mathcal {M}, h, t & \ models F \ phi \ text {iff} \ mathcal {M}, h, t '\ models \ phi \ text {untuk beberapa} t' \ in h \ text {sedemikian sehingga} t \ prec t '. \ \ \ mathcal {M}, h, t & \ models P \ phi \ text {iff} \ mathcal {M}, h, t '\ models \ phi \ text {for some} t' \ in h \ text { seperti itu} t '\ prec t. \ \ \ mathcal {M}, h, t & \ models \ diamondsuit \ phi \ text {iff} \ mathcal {M}, h ', t \ models \ phi \ text {for some} h' \ in \ mathcal { H} (t). \ end {align} \] Kita sekarang mengatakan bahwa formula OBTL adalah Ockhamist jika benar pada setiap cabang dari setiap model pohon Ockham.
Sebelum (1967) berpendapat bahwa atom harus "tidak mengandung bekas kemurnian" dan kebenaran mereka seharusnya hanya bergantung pada waktu sekarang, tapi tidak pada sejarah saat ini. Jadi, dia mempertimbangkan dua versi logika Ockham: satu, hanya melibatkan atom 'tidak futuritas', yang akan kita sebut 'proposisi atom instan', dan yang lainnya melibatkan kedua jenis proposisi atom. Sebenarnya, atom berbasis instan dapat disimulasikan dengan '(instan, sejarah)' - jenis proposisi atom dengan awalan dengan \ (\ Box, \) karena kebenaran \ (\ Box p \) tidak bergantung pada sejarah saat ini tapi hanya pada titik waktu saat ini.
Secara umum, tidak semua sejarah dalam kerangka temporal mungkin menarik, dan untuk mendefinisikan semantik tipe Ockham, cukuplah untuk mempertimbangkan keluarga sejarah yang cukup kaya, yang disebut bundel . Pohon bundelan adalah sepasang \ ((\ mathcal {T}, \ mathcal {B}) \) di mana \ (\ mathcal {T} \) adalah bingkai temporal \ (\ mathcal {T} = \ left \ langle T , \ prec \ right \ rangle \) yang merupakan pohon dan \ (\ mathcal {B} \) adalah kumpulan sejarah yang tidak kosong di \ (\ mathcal {T} \) ( bundel) , sehingga setiap saat dari \ (\ mathcal {T} \) termasuk beberapa sejarah dari \ (\ mathcal {B}. \) Penilaian di pohon yang dibundel \ ((mathcal {T}, \ mathcal {B}) \) adalah sebuah pemetaan \ (V \) yang memberikan ke setiap \ (p \ in {PROP} \) sekumpulan cabang \ (V (p) \ subseteq \ mathcal {B} \ times T. \) Model pohon yang dibundel adalah kumpulan pohon dianugerahi dengan penilaian. Pohon bundel lengkap adalah pohon yang dibundel dari tipe \ ((mathcal {T}, \ mathcal {H} (\ mathcal {T})), \) yaitu, di mana bundel terdiri dari semua sejarah di pohon. Sekarang, semantik untuk OBTL mudah disamakan dengan model pohon yang dibundel, cukup dengan relativisasi semua klausa definisi kebenaran ke sejarah di \ (\ mathcal {B}. \) Secara khusus, sekarang \ (\ diamondsuit \) hanya mengacu pada sejarah itu Kami mengatakan bahwa formula OBTL adalah pohon paket yang valid (BT-valid) jika benar pada setiap cabang dari setiap model pohon yang dibundel. Kami mencatat bahwa, seperti yang dibuktikan dalam Zanardo dkk. (1999), kelas pohon bundel lengkap tidak dapat didefinisikan dengan rumus Ockham dalam kelas semua pohon yang dibundel, sehingga hasil tentang ketepatan dan kelengkapan tidak mudah dipindahkan ke kedua arah.
Analog analog dari pohon yang dibundel, yang disebut bingkai \ \ T \ times W \) - frames atau Kamp frames oleh Thomason (1984) dan secara teknis setara dengan frame Ockham oleh Zanardo (1996), dapat digunakan sebagai alternatif untuk mengenalkan semikonduktor Ockham. Dalam kerangka seperti itu, cabang adalah entitas primitif abstrak dan hubungan antara cabang yang sesuai dengan modal dan operator temporal di OBTL secara eksplisit diberikan sebagai bagian dari definisi model. Jadi, waktu diwakili sebagai kumpulan sejarah yang melewati "momen" simultan (dalam terminologi Belnap, lihat Belnap et al., 2001) dan instants di sini bukan lagi entitas primitif, tapi rangkaian momen simultan yang maksimal. Secara visual, ini adalah irisan horisontal melalui kumpulan semua sejarah.
Di sisi lain, ternyata validitas pohon yang dibundel benar-benar lebih lemah daripada validitas Ockhamist, yaitu validitas terbatas pada kumpulan pohon yang lengkap. Memang, rumus berikut ini adalah Ockhamist yang valid: \ [\ Box G (\ Box p \ to \ diamondsuit F \ Box p) \ to \ diamondsuit G (\ Box p \ to F \ Box p) \] Namun, seperti yang ditunjukkan pada Reynolds (2002), tidak berlaku di semua pohon yang dibundel. (Perhatikan bahwa, setelah Prior, Reynolds hanya mengasumsikan proposisi atom instan, jadi rumus di atas diperoleh dari rumus Reynolds dengan mengawali setiap kejadian \ (p \) oleh \ (\ Box. \)) Alasannya, secara intuitif, adalah bahwa anteseden memungkinkan konstruksi selangkah demi selangkah dari "sejarah batas", yang sering disebut \ (\ Box q \) seringkali, dari urutan yang tak terbatas dari kemungkinan sejarah yang berbeda. Semua sejarah antara ini mungkin termasuk dalam bundel, sementara sejarah batas mungkin tidak ada di dalamnya. Dengan demikian, untuk benar-benar memalsukan validitas Ockham, kita harus menambahkan aksioma yang menangkap penutupan batas properti dari pohon yang lengkap. Reynolds (2003) mengusulkan sistem aksiomatik lengkap untuk OBTL untuk validitas BT dan validitas Ockham, dengan asumsi proposisi atom instan. Sistem terdahulu memperluas aksioma untuk \ (G \) dan \ (H \) pada arus waktu yang dipesan secara linier dengan aksioma S5 untuk \ a \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ) yang menyiratkan maksimalitas sejarah, skema aksioma

( HN ) \ (P \ varphi \ to \ Box P \ diamondsuit \ varphi \)

mengatakan bahwa semua sejarah melalui masa instan saat ini sama dengan masa lalu, dan peraturan inferensi non-standar ("Gabbay-gaya") berikut, yang digunakan untuk memaksa irevlektivitas hubungan waktu yang didahulukan:
\ [\ tag {\ (\ textbf {IRR} \)} \ frac {(p \ land H \ lnot p) \ to \ varphi} {\ varphi}, \ text {anggap bahwa} p \ text {tidak terjadi in} \ varphi. \] Agar benar-benar memalsukan validitas Ockham, Reynolds menambahkan skema "limit closure axioms" berikut tak terbatas:
\ [\ tag {\ (\ textbf {LC} \)} \ Box G _ {\ leq} \ bigwedge_ {i = 0} ^ {n-1} (\ diamondsuit \ varphi_ {i} \ to \ diamondsuit F \ diamondsuit \ varphi_ {i + 1}) \ to \ diamondsuit G _ {\ leq} \ bigwedge_ {i = 0} ^ {n-1} (\ diamondsuit \ varphi_ {i} \ to F \ diamondsuit \ varphi_ {i + 1} ) \] dimana \ (\ varphi_ {0}, \ ldots, \ varphi_ {n-1} \) adalah formula OBTL, \ (\ varphi_ {n} = \ varphi_ {0}, \) dan \ (G _ {\ leq} \ theta: = \ theta \ land G \ theta. \)
Beberapa ekstensi dan variasi OBTL telah diusulkan dan dipelajari. Misalnya, Brown dan Goranko (1999) memperluas bahasa OBTL dengan modalitas untuk cabang alternatif dan variabel kipas khusus yang mewakili semua sejarah yang berasal dari satu instan, dan axiomatise logika yang dihasilkan. Perpanjangan lain sepanjang garis serupa adalah Ciuni dan Zanardo (2010). Untuk hasil yang lebih terkait, lihat juga Thomason (1984), Zanardo (1985; 1996), Reynolds (2002; 2003).

5.3 logika temporal Peircean

Dalam interpretasi model waktu percabangan masa depan yang tidak deterministik, yang disebut "Peircean" oleh Prior dan tampaknya disukai olehnya, \ (Fp \) dan \ (Gp \) setara dengan Ockhamist \ (\ Box Fp \) dan \ (\ Box Gp, \) masing-masing. Di bawah penafsiran ini tidak ada rumus yang setara dengan Ockhamist \ (Fp, \) yang dianggap belum ditentukan. Dengan demikian, logika temporal Peircean dapat dianggap sebagai fragmen logika temporal Ockham yang tepat, diperoleh dengan mempertimbangkan hanya formula yang dibangun secara rekursif dari atom yang menggunakan penghubung proposisional dan gabungan modalitas \ (\ diamondsuit G, \) \ (\ diamondsuit F \) dan duals \ (\ Box G \) dan \ (\ Box F. \) Peircean Branching Time Logic, PBTL, pada dasarnya kurang ekspresif daripada OBTL, kurang setara dengan misalnya, \ (\ diamondsuit GFp \) dan \ (\ diamondsuit FGp \ ) (untuk bukti lihat Reynolds 2002).
Axiomatisasi finis lengkap dari logika temporal Peircean untuk validitas BT telah diperoleh oleh Burgess (1980) dengan menggunakan versi IRR IRR, dan Zanardo (1990) tanpa menggunakan peraturan semacam itu, namun dengan banyak aksioma yang tak terbatas, termasuk aksioma yang sangat kompleks. skema. Lihat Reynolds (2002) untuk lebih jelasnya.

5.4 Logika pohon perhitungan CTL dan CTL *

Logika waktu percontohan banyak digunakan dalam ilmu komputer. Mereka adalah variasi dari logika Peircean dan Ockham yang disajikan di atas, namun pada dasarnya terbatas pada kelas pohon dimana setiap sejarah memiliki tipe urutan bilangan asli. Pohon-pohon seperti itu, yang disebut pohon perhitungan , secara alami diperoleh sebagai pembukaan pohon dari sistem transisi diskrit, maka secara alamiah mereka mewakili pohon dari semua perhitungan tak terbatas yang timbul dalam sistem semacam itu. Logika waktu percabangan yang paling populer digunakan dalam ilmu komputer adalah:

logika pohon perhitungan CTL, diperkenalkan oleh Clarke dan Emerson (1982). Ini pada dasarnya adalah logika temporal Peircean yang ditafsirkan di kelas pohon penghitungan tanpa operator masa lalu, tapi hanya \ (G, \) \ (X \) ("nexttime") dan \ (U \) ("until"). Seperti dalam logika temporal Peircean biasa PBTL, di CTL, operator temporal selalu didahului oleh \ (\ diamondsuit \) atau \ (\ Box, \) di sini biasanya dilambangkan sebagai quantifier \ (\ exist \) dan \ (forall \) lebih dari sejarah. CTL didahului oleh logika UB, yang diperkenalkan oleh Ben-Ari, Manna dan Pnueli (1983), dimana \ (U \) tidak digunakan.
logika pohon komputasi lengkap CTL *, diperkenalkan oleh Emerson dan Halpern (1985). Ini adalah perluasan CTL Ockham, tanpa batasan sintaksis terhadap aplikasi operator temporal dan pengukur jalur, dan ditafsirkan di kelas pohon penghitungan.

Logika CTL banyak digunakan karena sifat komputasi yang baik berkaitan dengan pengecekan model , yang memiliki kompleksitas linier keduanya dalam ukuran formula masukan dan ukuran model masukan (sebagai sistem transisi yang terbatas). Namun, tidak terlalu ekspresif, yang menyebabkan perluasannya ke CTL *, yang jauh lebih ekspresif dan juga menggabungkan logika waktu linier LTL, namun memiliki kompleksitas model checking (PSPACE) yang lebih tinggi dan satisfiability (2EXPTIME) daripada CTL. Untuk referensi dan keterangan lebih lanjut, lihat Emerson (1990) dan Stirling (1992).
Axiomatisation lengkap CTL dapat diperoleh dengan mengganti aksioma LTL dengan versi yang sesuai dengan jalurnya. Misalnya, aksioma yang mencirikan operator temporal \ (G \) dan \ (U \) sebagai titik tetap sekarang menjadi:

(FP \ (_ {\ ada G} \)) \ (\ ada G \ varphi \ leftrightarrow (\ varphi \ wedge \ ada X \ ada G \ varphi); \)
(FP \ (_ {\ forall G} \)) \ (\ forall G \ varphi \ leftrightarrow (\ varphi \ wedge \ forall X \ forall G \ varphi); \)
(FP \ (_ {\ ada U} \)) \ (\ ada (\ varphi U \ psi) \ leftrightarrow (\ psi \ vee (\ varphi \ wedge \ ada X \ ada (\ varphi U \ psi))) ; \)
(FP \ (_ {\ forall U} \)) \ (\ forall (\ varphi U \ psi) \ leftrightarrow (\ psi \ vee (\ varphi \ wedge \ forall X \ forall (\ varphi U \ psi))) . \)

Untuk kelengkapan bukti versi sistem aksiomatik untuk CTL ini, lihat Goldblatt (1987) dan Emerson (1990).
Untuk CTL * lebih banyak aksioma harus ditambahkan, untuk memperhitungkan kombinasi operator temporal dan untuk menegakkan batas penutupan properti. Inilah dua aksioma tambahan tersebut, yang terakhir menjadi "aksioma penutupan batas" karena Reynolds (2003):

\ (\ Box G (\ Box \ varphi \ to \ diamondsuit XF \ Box \ varphi) \ ke (\ Box \ varphi \ to \ diamondsuit GF \ Box \ varphi); \)
\ (\ Box G (\ diamondsuit \ varphi \ to \ diamondsuit X ((\ diamondsuit \ psi U \ diamondsuit \ theta))) \ to (\ diamondsuit \ varphi \ to \ diamondsuit G ((diamondsuit \ psi U \ diamondsuit \ theta))). \)

Mendapatkan axiomatization lengkap untuk CTL * telah jauh lebih sulit dan satu-satunya yang diketahui sejauh ini, karena Reynolds (2001), melibatkan aturan inferensi yang sangat rumit, diambil dari penggunaan automata Rabin dalam bukti kelengkapan. Menariknya, peraturan tersebut ternyata berlebihan dalam perluasan CTL * dengan operator masa lalu Reynolds (2005), namun tidak diketahui apakah benar-benar diperlukan untuk derivasi di CTL * itu sendiri.
Kami mencatat bahwa semua logika yang disebutkan di bagian ini memiliki properti model yang terbatas dan dapat dipecahkan. Bukti dugaan masing-masing logika dapat ditemukan misalnya di Burgess (1980), Emerson dan Jutla (1984), Gurevich dan Shelah (1985), Emerson dan Halpern (1985), Goldblatt (1987), Emerson (1990), Gabbay et Al. (1994), Finger et al. (2002).

6. Interval logika temporal

Sementara pengurangan teknis antara model berbasis waktu instan dan berbasis interval dapat digunakan untuk mendamaikan berbagai sudut pandang filosofis dan ontologis, mereka tidak menyelesaikan masalah semantik utama yang timbul saat mengembangkan formalisme logis untuk menangkap penalaran sementara, yaitu: proposisi tentang waktu, dan Oleh karena itu, formula dalam bahasa logika yang diberikan, ditafsirkan sebagai mengacu pada instants atau interval? Jawaban alami yang mungkin untuk pertanyaan ini mengarah pada tiga alternatif yang masuk akal, yang masing-masing menimbulkan logika berbasis titik yang dibahas di atas, logika berbasis interval , dan logika gabungan dua bit , di mana titik dan interval dianggap berbeda pada nominal dan Rumus untuk kedua macam itu dibangun. Kami hanya akan membahas di sini murni logika temporal berbasis interval, sedangkan untuk studi baru-baru ini dan eksplorasi teknis dari pendekatan dua-disortir, kami mengacu pada Balbiani dkk. (2011).
Ada berbagai proposal dan perkembangan logika temporal berbasis interval. Makalah logika filosofis awal yang penting termasuk Hamblin (1971), Humberstone (1979), Röper (1980), dan Burgess (1982b), yang terakhir memberikan sebuah aksioma untuk logika temporal berbasis interval (disebut ada "period berbasis") yang melibatkan hubungan awal / kemudian antara interval pada arus waktu dari rasionalisasi dan real.
Pendekatan interval berbasis penalaran temporal lebih menonjol dalam Kecerdasan Buatan, di mana beberapa karya penting mencakup logika perencanaan Allen (1984), kalkulus Kowalski dan kalkulus Sergot (1986), dan logika interval moda Halpern dan Shoham (1986), tetapi juga fitur dalam beberapa aplikasi ke ilmu komputer seperti logika real-time dan verifikasi perangkat keras , terutama Moszkowski's Interval Logic (1983) dan Zhou, Hoare and Ravn's Duration Calculus, lihat Hansen dan Zhou (1997).
Di sini kita akan menyajikan logika interval proporsional Halpern dan Shoham secara singkat, selanjutnya disebut \ (\ mathsf {HS}. \) Ini menggunakan satu set operator modal tak beraturan yang sesuai dengan masing-masing hubungan interval Allen dan memiliki semantik Kripke mengenai hubungan itu. Halpern & Shoham (1986) memilih notasi yang berbeda untuk hubungan Allen dari Allen. Kami membandingkan dua notasi pada Tabel 1.
Bahasa \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ konstanta proposisi (\ top \) dan \ (\ bot, \) diasumsikan dapat didefinisikan seperti biasa), dan sebuah keluarga dari operator modal temporal interval (modalitas) dari bentuk \ (\ langle X \ rangle, \) satu untuk masing-masing hubungan Allen. Rumus didefinisikan oleh tata bahasa berikut: \ [\ varphi :: = p \ mid \ neg \ varphi \ mid \ varphi \ vee \ varphi \ mid \ langle X \ rangle \ varphi \]
Diberikan perintah parsial ketat \ (\ mathbb D = \ langle D, <\ rangle, \) interval di \ (\ mathbb D \) adalah pasangan terurut \ ([d_ {0}, d_ {1}] \) seperti \ (d_ {0}, d_ {1} \ in D \) dan \ (d_ {0} \ leq d_ {1}. \) Kumpulan semua interval dalam \ (\ mathbb {D} \) akan dinotasikan dengan \ (\ mathbb {I} (\ mathbb {D)}. \) Model interval adalah sepasang \ (M \ mathbf {=} \ left \ langle \ mathbb {D}, V \ right \ rangle, \) di mana \ (V: \ mathbb {I} (\ mathbb {D}) \ rightarrow 2 ^ \ mathcal {AP} \) adalah label yang menetapkan setiap interval satu set proposisi atom yang dianggap benar dalam hal itu. Perhatikan bahwa model interval yang didefinisikan di sini mencakup "interval titik", dengan titik akhir yang sama, mengikuti semantik asli \ (\ mathsf {HS} \) di Halpern & Shoham (1986). Terkadang, semantik "ketat" dipertimbangkan, di mana interval titik tidak termasuk.
Kebenaran formula pada interval tertentu \ ([a, b] \) dalam model interval \ (M \) didefinisikan oleh induksi struktural biasa pada formula:
\ [\ begin {array} {ll} M, [a, b] \ model p & \ text {iff} p \ in V ([a, b]), \ text {where} p \ in \ mathcal {AP }; \\ M, [a, b] \ models \ neg \ psi & \ text {iff} M, [a, b] \ not \ models \ psi; \\ M, [a, b] \ models \ varphi \ vee \ psi & \ text {iff} M, [a, b] \ models \ varphi \ text {or} M, [a, b] \ models \ psi ; \\ M, [a, b] \ models \ langle Z \ rangle \ psi & \ text {iff} \ text {ada interval} [c, d] \ text {seperti itu} [a, b] R_ { Z} [c, d] \\ & \ quad \ text {and} M, [c, d] \ models \ psi, \ text {where} R_Z \ text {is} \ langle Z \ rangle \ text {(Tabel 1)}. \ end {array} \] Misalnya, \ (M, [d_ {0}, d_ {1}] \ models \ langle A \ rangle \ varphi \) iff \ (M, [d_ {1}, d_ {2}] \ models \ varphi \) untuk beberapa interval \ ([d_ {1}, d_ {2}]. \)
Untuk setiap modalitas berlian \ (\ langle Z \ rangle, \) modalitas kotak yang sesuai didefinisikan sebagai dual: \ ([Z] \ varphi \ equiv \ neg \ langle Z \ rangle \ neg \ varphi. \)
Kadang-kadang berguna untuk mempertimbangkan sebuah konstanta modal tambahan untuk interval titik, dilambangkan \ (\ pi, \) dengan definisi kebenaran berikut:
\ [M, [d_ {0}, d_ {1}] \ models \ pi \ text {iff} d_ {0} = d_ {1}. \] Beberapa modalitas \ (\ mathsf {HS} \) dapat didefinisikan dalam istilah orang lain dan untuk setiap semantik ketat dan tidak ketat, fragmen minimal yang cukup ekspresif untuk menentukan semua operator lain telah diidentifikasi:

Dalam semantik yang ketat, enam modalitas \ (\ langle A \ rangle, \) \ (\ langle B \ rangle, \) \ (\ langle E \ rangle, \) \ (\ langle \ overline {A} \ rangle, \) \ (\ langle \ overline {B} \ rangle, \) \ (\ langle \ overline {E} \ rangle \) cukup untuk mengekspresikan semua yang lain, seperti yang ditunjukkan oleh ekivalensi berikut:
\ [\ begin {matrix} \ langle L \ rangle \ varphi \ equiv \ langle A \ rangle \ langle A \ rangle \ varphi, & \ langle \ overline {L} \ rangle \ varphi \ equiv \ langle \ overline {A} \ rangle \ langle \ overline {A} \ rangle \ varphi, \\ \ langle D \ rangle \ varphi \ equiv \ langle B \ rangle \ langle E \ rangre \ varphi, & \ langle \ overline {D} \ rangle \ varphi \ equiv \ langle \ overline {B} \ rangle \ langle \ overline {E} \ rangle \ varphi, \\ \ langle O \ rangle \ varphi \ equiv \ langle E \ rangle \ langle \ overline {B} \ rangle \ varphi , & \ langle \ overline {O} \ rangle \ varphi \ equiv \ langle B \ rangle \ langle \ overline {E} \ rangle \ varphi. \ end {matrix} \]
Dalam semantik non-ketat, empat modalitas \ (\ langle B \ rangle, \) \ (\ langle E \ rangle, \) \ (\ langle \ overline {B} \ rangle, \) \ (\ langle \ overline {E} \ rangle \) cukup untuk mengekspresikan semua yang lain, seperti yang ditunjukkan oleh persamaan berikut:
\ [\ begin {align} \ langle A \ rangle \ varphi & \ equiv ([E] \ bot \ wedge (\ varphi \ vee \ langle \ overline {B} \ rangle \ varphi)) \ vee \ langle E \ rangle (\ E \ \ \ bot \ wedge (\ varphi \ vee \ langle \ overline {B} \ rangle \ varphi)), \\ \ langle \ overline {A} \ rangle \ varphi & \ equiv ([B] \ bot \ baji (\ varphi \ vee \ langle \ overline {E} \ rangle \ varphi)) \ vee \ langle B \ rangle ([B] \ bot \ wedge (\ varphi \ vee \ langle \ overline {E} \ rangle \ varphi )), \\ \ langle L \ rangle \ varphi & \ equiv \ langle A \ rangle (\ langle E \ rangle \ top \ wedge \ langle A \ rangle \ varphi), \\ \ langle \ overline {L} \ rangle \ varphi & \ equiv \ langle \ overline {A} \ rangle (\ langle B \ rangle \ top \ wedge \ langle \ overline {A} \ rangle \ varphi), \\ \ langle D \ rangle \ varphi & \ equiv \ langle B \ rangle \ langle E \ rangle \ varphi, \\ \ langle \ overline {D} \ rangle \ varphi & \ equiv \ langle \ overline {B} \ rangle \ langle \ overline {E} \ rangle \ varphi, \ \ \ langle O \ rangle \ varphi & \ equiv \ langle E \ rangle (\ langle E \ rangle \ top \ wedge \ langle \ overline {B} \ rangle \ varphi), \\ \ langle \ overline {O} \ rangle \ varphi & \ equiv \ langle B \ rangle (\ langle B \ rangle \ top \ wedge \ langle \ overline {E} \ rangle \ varphi). \ end {align} \] Juga, konstanta modal \ (\ pi \) dapat didefinisikan dalam bentuk \ (\ langle B \ rangle \) dan \ (\ langle E \ rangle, \) masing-masing sebagai \ ([B] \ bot \) dan \ ( [E] \ bot. \)

Logika \ (\ mathsf {HS} \) memiliki lebih dari seribu fragmen yang secara tidak disengaja yang tidak setara yang hanya melibatkan beberapa operator modal, yang telah dipelajari secara ekstensif (lihat (Della Monica et al, 2011) untuk sebuah survei). \ (\ mathsf {HS} \) dan sebagian besar fragmennya sangat ekspresif dan validitas di dalamnya biasanya tidak dapat diputuskan (dengan beberapa asumsi tambahan, bahkan sangat tidak dapat diputuskan lagi, yaitu \ \ \ ^ ^ {1} _ {1} \ )-lengkap). Namun, beberapa kasus fragmen HS yang tidak dapat diobati sepele dapat diidentifikasi. Mungkin logika interval ekspresif yang paling banyak dipelajari adalah logika interval lingkungan (Goranko et al, 2003), yang melibatkan operator modal \ (\ langle A \ rangle \) dan \ (\ langle \ overline {A} \ rangle. \) Satu spesifik aksioma untuk \ (\ langle A \ rangle \) (dan simetris untuk \ (\ langle \ overline {A} \ rangle \)) adalah \ (\ langle A \ rangle \ langle A \ rangle \ langle A \ rangle p \ untuk \ langle A \ rangle \ langle A \ rangle p, \) mengatakan bahwa dua interval kanan-tetangga dua berturut-turut dapat digabungkan menjadi satu interval jarak kanan.
Ada penafsiran spasial alami dari logika temporal temporal, berdasarkan gagasan bahwa setiap interval pada pemesanan linier \ (L \) diwakili sebagai sepasang titik (awal, akhir), yang dapat dianggap sebagai koordinat titik di bidang \ (L \ times L \) - plane, dan hubungan antar interval memiliki hubungan spasial yang sesuai secara alami antara titik-titik representasinya. Penafsiran ini telah berhasil dieksplorasi untuk menghubungkan berbagai hasil teknis, seperti undecidability, antara logika spasial dan interval, lihat misalnya, Venema (1990), Marx dan Reynolds (1999). Untuk rincian dan lebih banyak tentang logika temporal interval lihat Halpern & Shoham (1986), Venema (1990), Goranko dkk. (2003), Goranko dkk. (2004), Della Monica dkk. (2011), survei Konur (2013), dan referensi di dalamnya.
Selain interval interval unival yang terkait dengan interval hubungan biner Allen, ada operasi alami dan penting untuk memotong interval menjadi dua subinterval, yang menyebabkan hubungan interval terner 'chop', diusulkan dan dipelajari di Moszkowski (1983) dan kemudian diperpanjang di Venema (1991) ke CDT logika, yang melibatkan 'chop' (\ (C \)) dan dua operator 'chop' residu \ (D \) dan \ (T. \) CDT logika benar-benar axiomatised di Venema (1991), lihat juga Goranko dkk. (2004) dan Konur (2013).
Terakhir, beberapa kata tentang hubungan antara ekspresi bahasa logika temporal interval dan logika orde pertama. Terjemahan standar ST dari Prior's Tense Logic ke logika orde pertama, disajikan pada Bagian 3.3 , secara alami melintasi logika interval, di mana proposisi atomik ditunjukkan dalam bahasa orde pertama melalui hubungan biner. Ternyata ada kecocokan alami antara logika temporal temporer dan fragmen variabel terikat dari logika orde pertama: beberapa modalitas \ (\ mathsf {HS} \) dapat diterjemahkan ke dalam fragmen dua variabel FO \ (^ {2} \) logika orde pertama, yang akhirnya menyiratkan keteguhannya, sementara sisanya memerlukan setidaknya 3 variabel berbeda untuk terjemahan standar. Hal itu ditunjukkan di Bresolin dkk. (2009) bahwa logika interval ekspresif yang paling kuat adalah logika interval lingkungan, yang terbukti secara ekspresif lengkap untuk FO \ (2). \ Di sisi lain, bahkan penuh \ (\ mathsf {HS} \) kurang ekspresif daripada fragmen tiga variabel FO \ (^ {3}, \) dimana Venema (1991) membuktikan bahwa CDT logika secara ekspresif lengkap.

7. Varian lain dari logika temporal

Sejauh ini kita telah membahas hirarki logika temporal tradisional, namun ada banyak perkembangan alternatif yang tidak sesuai dengan hirarki ini, namun dapat menjadi formalisms yang berguna untuk berbagai aplikasi. Kami sebentar menyajikan beberapa dari mereka di sini.

7.1 logika temporal hibrida

Perkembangan yang penting, memperkaya kerangka tradisional logika temporal, adalah dengan menggabungkan fitur logika orde pertama untuk menghasilkan keluarga yang disebut logika hibrida , yang menyatukan bahasa dan bahasa dari logika temporal. Logika hibrida sangat ekspresif, namun mereka sering melestarikan sifat komputasi yang baik dari logika temporal standar. Mereka mencakup beberapa mekanisme sintaksis yang memperluas kerangka temporal klasik, beberapa di antaranya kembali ke karya Prior (lihat Blackburn 2006) dan ini secara singkat disebutkan di bawah, kira-kira dalam rangka meningkatkan ekspresivitas. Lihat rincian lebih lanjut dan referensi misalnya, di Goranko (1996), Areces dan sepuluh Cate (2006) dan entri tentang logika hibrida .

Modalitas universal \ (A \) (artinya dalam istilah temporal "always"), ditafsirkan oleh hubungan universal kerangka temporal. Menggunakan \ (A \) seseorang dapat mengekspresikan pernyataan global secara lokal, seperti validitas dalam model \ (\ mathcal {M} \) : \ (\ mathcal {M}, t \ vDash A \ varphi \) iff \ (\ mathcal {M} \ vDash A \ varphi. \)
Nominals , alias variabel jam . Ini adalah proposisi atom khusus yang pasti benar tepat pada satu instan model, yaitu seseorang dapat memikirkan variabel jam \ (t \) yang mengatakan "Ini adalah \ (t \) jam sekarang". Gagasan tentang nominator kembali ke Prior (1967), namun telah dikembangkan dan diterapkan secara independen dalam beberapa karya terbaru, lihat referensi di atas.
Operator kepuasan \ (@_ {i}, \) di mana \ (i \) adalah nominal, dengan semantik \ (M, t \ vDash @_ {i} \ varphi \) iff \ (M, V (i) \ vDash \ varphi, \) di mana \ (V (i) \) adalah saat yang unik dimana \ (i \) benar adanya. Dengan demikian, gagasan semantik dasar tentang sebuah kebenaran pada saat seketika model sekarang dibawa ke dalam sintaksis. Selain meningkatkan ekspresif, ini juga memungkinkan pengembangan sistem bukti yang elegan seperti kalkulus berurutan dan meja tulis semantik dengan gaya deduksi berlabel.
Modalitas perbedaan \ (D \ varphi, \) mengatakan bahwa \ (\ varphi \) benar pada saat lainnya . Ekspresi bahasa yang dihasilkan dalam arti setara dengan yang ada dengan nomina dan modalitas universal.
Petunjuk referensi , pengikat alias: \ (\ downarrow_ {i}, \) di mana \ (i \) adalah nominal. Ini berperilaku sintaksis sebagai pengukur, dan efek semantiknya adalah bahwa \ (\ downarrow _ {i} \) mengikat nilai nominal \ (i \) ke saat evaluasi saat ini . Secara formal, \ (\ mathcal {M}, t \ vDash \ downarrow_ {i} \ varphi \) iff \ (\ mathcal {M} _ {[i \ rightarrow t]}, t \ vDash \ varphi, \) dimana \ (\ mathcal {M} _ {[i \ rightarrow t]} \) adalah model yang diperoleh dari \ (\ mathcal {M} \) dengan menugaskan kembali denotasi \ (i \) menjadi \ (t. \ ) Pengenalan pointer referensi di Goranko (1996) sebagian dimotivasi oleh gagasan untuk menambahkan mekanisme sintaksis untuk mengacu pada waktu saat ini, yaitu mengatakan ' Sekarang '. Untuk analisis logis sistematis dan perawatan formal Now see Kamp (1971). Mekanisme referensi serupa, yang disebut freeze quantifier , mengikat sebuah variabel sampai pada konteks lokal temporal, diperkenalkan di Alur dan Henzinger (1994).
Kuantifier di atas nominator : \ (\ forall i \ varphi, \) di mana \ (i \) adalah nominal. Semantik harus jelas: \ (M, t \ vDash \ forall i \ varphi \) iff \ (M _ {[i \ rightarrow s]}, t \ vDash \ varphi \) untuk setiap instan \ (s \ di M. \) Ini membawa kekuatan penuh dari kuantifikasi orde pertama ke bahasa temporal, sambil tetap menjaga banyak kebajikan proposisionalnya. Idenya kembali ke Bull (1970).
Pengukur proposisional : \ (\ forall p \ varphi \) di mana \ (p \) adalah proposisi atomik. Ini adalah kuantifikasi orde kedua yang dibawa ke dalam bahasa proposisional dan menyebabkan lompatan ekspresif sering menghasilkan rekursif non-axiomatizability. Kami secara singkat membahas kuantifikasi proposisional dalam logika temporal lebih jauh.

Bahasa hibrida cukup ekspresif. Berikut adalah dua contohnya:

mendefinisikan irreflexivity dari relasi diutamakan, yang tidak dapat dinyatakan dalam TL, bahkan jika diperluas dengan refleksif \ (U, \) sangat mudah dalam bahasa dengan nomin dan \ (@ \) sebagai \ (@_ {i} G \ lnot saya.\)
Operator \ (S \) dan \ (U \) (dalam variasi apapun) dapat didefinisikan dalam bahasa hibrida dengan nomina dan pengikat: \ (\ varphi U \ psi: = {\ downarrow _ {i}} F (\ psi \ wedge H (Pi \ rightarrow \ varphi)) \) dan juga untuk \ (S. \)

Sementara versi lemah dari logika hibrida - dengan modalitas dan nomina universal atau dengan modalitas yang berbeda - masih dapat dipecahkan, yang lebih ekspresif, yang melibatkan referensi pointer / pengikat atau pengukur jumlah nominator biasanya tidak dapat diputuskan, lihat Goranko (1996), Areces and ten Cate (2006).

7.2 Metrik dan logika temporal real-time

Metrik logika temporal kembali ke Prior juga. Dia menggunakan notasi \ (Fnp \) untuk berarti "Akan terjadi kasus interval \ (n \) sehingga \ (p \)" (yaitu, \ (p \) akan terjadi setelah \ (n \ ) unit waktu) dan \ (Pnp \) untuk "Itu adalah kasus interval \ (n \) yang lalu \ (p \)" (yaitu, \ (p \) terjadi sebelum \ (n \) waktu unit). Yang terakhir ini dianggap sebagai singkatan dari \ (F (-n) hal. \) Kasus \ (n = 0 \) memberi kita present tense. Kita bisa mendefinisikan operator umum dan non-metrik masing-masing
\ [\ begin {matrix} Pp \ equiv \ ada {n} ({n} \ lt 0 \ land Pnp), & Fp \ equiv \ ada n (n \ gt 0 \ land Fnp); \\ Hp \ equiv \ forall {n} ({n} \ lt 0 \ rightarrow Pnp), & Gp \ equiv \ forall n (n \ gt 0 \ rightarrow Fnp). \ end {matrix} \] Sistem logika temporal berbasis instan untuk waktu metrik dan 'logika kronologis' diperkenalkan dan dipelajari (Rescher and Urquhart, 1971, Bab X). Untuk informasi lebih lanjut tentang logika temporal metrik (dan berlapis) lihat Montanari (1996) dan Montanari dan Policriti (1996). Untuk logika interval lingkungan metrik lihat Bresolin dkk. (2013).
Berbagai perpanjangan logika temporal real-time juga telah diusulkan dan dipelajari, misalnya dengan menambahkan:

operator yang dibatasi waktu , misalnya: \ (G (p \ to F _ {_ {\ leq 3}} q). \)
kuantifikasi pembekuan , mirip dengan pengikat logika hibrid, variabel pengikat ke waktu saat ini, misalnya: \ (Gx. (p \ to Fy. (q \ land y \ leq x + 3)). \)
variabel waktu dan kuantifikasi : \ (\ forall x G (p \ land t = x \ to F (q \ land t \ leq x + 3)). \)

Masing-masing rumusan di atas berarti bahwa "kapan pun di masa depan \ (p \) berlaku, \ (q \) akan disimpan dalam 3 unit waktu kemudian".
Ekstensi real-time semacam itu biasanya sangat ekspresif dan sering mengarah pada logika dengan masalah keputusan yang tidak dapat dipecahkan. Cara untuk mendapatkan kembali decidability adalah untuk melonggarkan persyaratan "ketepatan waktu" yang melibatkan waktu yang tepat, dengan persyaratan yang melibatkan interval waktu. Untuk informasi lebih lanjut lihat Alur dan Henzinger (1992; 1993; 1994), serta Reynolds (2010; 2014) tentang logika temporal real time RTL dan survei Konur (2013).

7.3 Mengukur logika temporal proporsional

Logika temporal proporsional dapat diperluas dengan quantifier di atas proposisi atom, lihat Rescher dan Urquhart (1971, Bab XIX). Secara semantis, ini mengukur semua valuasi proposisi atom, jadi mereka adalah bilangan orde dua monadik. Bahasa yang dihasilkan sangat ekspresif dan logika masing-masing biasanya tidak dapat diputuskan, seringkali tidak direkayasa secara rekursif. Ekstensi yang menonjol termasuk QPTL, perluasan LTL yang proporsional secara kuantitatif, yang dapat dipecahkan, meskipun dengan kompleksitas non-elementer, serta CTL * di bawah beberapa batasan semantik khusus, lihat Prancis (2001). Beberapa sistem aksiomatik lengkap untuk logika temporal proporsional kuantitatif telah dirancang, lihat Kesten dan Pnueli (2002) dan Prancis dan Reynolds (2002) untuk QPTL dengan dan tanpa operator masa lalu, juga memberikan bukti penolakan.

8. Menggabungkan logika temporal dan lainnya

Logika sering digunakan untuk alasan tentang perubahan struktur atau aspek dunia yang dinamis. Oleh karena itu sangat wajar untuk mempertimbangkan evolusi dari waktu ke waktu struktur tersebut dengan menambahkan dimensi temporal kepada mereka. Perspektif alternatif adalah mempertimbangkan model waktu berbasis instan dan bergaul dengan setiap saat di dalamnya sebuah "potret" model pada saat itu instan. Hal ini mengarah pada gagasan untuk menambahkan dimensi temporal ke logika yang dirancang untuk alasan mengenai model semacam itu, yaitu memperkaya bahasa logis dengan operator temporal yang sesuai untuk penalaran tentang evolusi model dari waktu ke waktu. Contoh utama adalah logika temporal orde pertama, yang dibahas di Bagian 8.1 . Berbagai logika modal juga dapat dipikul secara alami dan hubungan antara waktu dan modalitas merupakan salah satu pertanyaan utama dalam studi filosofis logika modal. Studi tentang kebutuhan historis adalah contoh penting lain dari analisis filosofis tentang modalitas dari perspektif logika temporal. Untuk diskusi filosofis dan teknis tentang menggabungkan tenses dan modalitas, lihat Rescher dan Urquhart (1971, Chapters XII, XV, XX), Thomason (1984), Cocciarella (2006) dan Lindström dan Segerberg (2006).
Dari sudut pandang teknis, ada beberapa cara untuk menggabungkan model dan sistem logis dan, khususnya, untuk membandingkan logika : produk, fusi, dll. (Lihat entri SEP tentang menggabungkan logika ).
Beberapa pertanyaan umum tentang transfer sifat logis , seperti axiomatisations, completeness, decidability, dan lain-lain muncul secara alami. Decidability, misalnya, biasanya dipelihara dalam fusi, namun sering hilang dalam produk sistem logis. Untuk diskusi umum dan studi tentang temporalizing sistem logis dan sifat logika temporer, lihat Finger and Gabbay (1992; 1996), Finger et al. (2002), Gabbay dkk. (2003). Di sini kami hanya sebentar menyajikan dan mendiskusikan beberapa kasus sistem logis temporer yang paling populer.

8.1 Logika temporal orde pertama

Temporal Logic diperoleh dengan menambahkan operator tegang ke logika yang ada; Di atas ini secara diam-diam diasumsikan sebagai Kalkulus Proposisi Klasik. Sistem temporal-logis lainnya diperoleh dengan mengambil basis logis yang berbeda. Yang jelas menarik adalah logika predikat tegang, di mana operator tegang ditambahkan ke Kalkulus Predikat Orde Pertama klasik. Hal ini memungkinkan kita untuk mengungkapkan perbedaan penting mengenai logika waktu dan eksistensi. Misalnya, pernyataan seorang filsuf akan menjadi raja bisa ditafsirkan dengan berbagai cara, seperti

\ ({\ ada x (Philosopher (x)} \ amp F King (x)) \)
Seseorang yang sekarang seorang filsuf akan menjadi raja di masa depan.

\ ({\ ada x F (Philosopher (x)} \ amp King (x)) \)
Sekarang ada seseorang yang akan di masa depan menjadi filsuf dan raja.

\ ({F \ ada x (Philosopher (x)} \ amp F King (x)) \)
Akan ada seseorang yang adalah seorang filsuf dan nantinya akan menjadi raja.

\ ({F \ ada x (Philosopher (x)} \ amp King (x)) \)
Akan ada seseorang yang pada saat bersamaan sama-sama seorang filsuf dan seorang raja.

Interpretasi formula semacam itu tidak bermasalah. Masalahnya menyangkut domain kuantifikasi. Untuk dua rumus kedua di atas untuk memikul interpretasi yang diberikan kepada mereka, perlu bahwa domain kuantifikasi selalu relatif terhadap suatu waktu: oleh karena itu, perlu diperkenalkan secara semantik domain kuantifikasi \ ({D} {t}) \) untuk setiap waktu \ (t. \) Tapi ini bisa menimbulkan masalah jika kita ingin menjalin hubungan antar objek yang ada pada waktu yang berbeda, seperti misalnya dalam pernyataan "Salah satu teman saya diturunkan dari seorang pengikut dari William the Conqueror ".
Masalah ini terkait dengan apa yang disebut rumus teori logika Barcan, analog temporal yang mana

\ (F \ ada {x} {Q} ({x}) \ rightarrow \ ada {x} F {Q} ({x}) \)
Jika akan ada sesuatu yang \ (Q, \) maka sekarang ada sesuatu yang akan menjadi \ (Q. \)

Rumus ini hanya bisa dijamin benar jika ada domain konstan untuk semua instants waktu; Di bawah asumsi ini, keberadaan kosong (seperti yang diungkapkan oleh quantifier eksistensial) perlu dilengkapi dengan predikat eksistensi temporer yang dibatasi (yang mungkin bisa dibaca 'masih ada') untuk merujuk pada objek yang berbeda yang ada pada waktu yang berbeda. Untuk informasi lebih lanjut tentang masalah logika temporal orde satu ini, lihat Bab XX dari Rescher dan Urquhart (1971), Bagian 7 van Benthem (1995) serta Lindström dan Segerberg (2006).
Isu terkait, terutama mewujudkan dirinya bila dikombinasikan dengan penalaran sementara, adalah masalah deskripsi yang pasti : istilah yang menggambarkan individu, seperti "Paus", "Paus sekarang", dan "Jorge Mario Bergoglio", mungkin atau mungkin tidak mengacu pada individu yang sama (atau siapa pun) pada instants waktu yang berbeda, dan pernyataan "Paus sekarang berasal dari Argentina" dan "Jorge Mario Bergoglio berasal dari Argentina" memiliki perilaku kebenaran yang sangat berbeda dari waktu ke waktu. Yang lebih bermasalah lagi adalah istilah deskripsi seperti "raja Prancis sekarang" dan sebuah semantik yang tak diragukan lagi dari pernyataan (sebenarnya) bahwa "raja Prancis sekarang tidak ada" tidak mudah diberikan. Lihat lebih lanjut tentang teori deskripsi Russell dalam entri SEP Deskripsi dan hubungan dengan penalaran temporal dan logika di Rescher dan Urquhart (1971, Bab XIII dan XX).
Logika orde pertama orisinal biasanya sangat tidak dapat diputuskan. Sedikit yang dapat dibedakan, dan bahkan lebih sedikit lagi, fragmen alami dari logika temporal orde pertama telah diidentifikasi dan diselidiki sejauh ini, termasuk fragmen monodik , lihat Hodkinson dkk. (2000) dan Wolter dan Zakharyaschev (2002).

8.2 Fisika temporal-epistemik

Fisika temporal-epistemik menggabungkan logika pengetahuan temporal dan (multi-agent) pengetahuan. Beberapa sifat alami dapat diekspresikan dengan menggabungkan operator temporal dan modalitas epistemik \ (K \) ("diketahui bahwa"), misalnya ingat sempurna , atau tidak ada yang lupa : (Jika agen mengetahui \ (p \) sekarang agen akan selalu tahu \ (p \) di masa depan): \ (K p \ to GK p; \) dan juga tidak ada pembelajaran : \ (FK p \ to K p, \) dll. Ini dikembangkan dengan berbagai cara selama 1980-an, dengan sebuah studi pemersatu oleh Halpern dan Vardi (1989), yang mempertimbangkan berbagai logika temporal-epistemik dengan semantik berdasarkan sistem interpretasi yang disebut: rangkaian berjalan dalam sistem transisi dengan hubungan indistinguishability epistemis pada ruang negara untuk setiap agen Variasi didasarkan pada enam parameter: jumlah agen (satu atau banyak), bahasa (dengan atau tanpa pengetahuan umum, waktu linier atau bercabang, dll.), Kemampuan mengingat (tidak ingat, ingat, ingat sempurna, sempurna), kemampuan belajar (belajar atau tidak belajar), sinkron (sinkron atau asinkron), keadaan awal yang unik . Bergantung pada pilihannya, kompleksitas komputasi dari masalah keputusan untuk logika ini berkisar sangat luas, dari PSPACE - lengkap sampai sangat tidak dapat diputuskan (\ (\ Pi ^ {1} _ {1} \) - lengkap). Untuk detail lebih lanjut lihat Halpern dan Vardi (1989), Fagin dkk. (1995), serta van Benthem dan Pacuit (2006) yang lebih baru yang meneliti sejumlah hasil decidablity dan undecidablity mengenai logika temporal-epistemik dan mengilustrasikan kembali efek krusial pada kompleksitas komputasi yang dapat dikombinasikan dengan temporal dan modalitas lainnya. membawa.

8.3 Logika temporal dan logika agensi

Alasan temporal adalah aspek penting dari penalaran tentang agensi. Salah satu keluarga logika yang paling berpengaruh untuk biro iklan berasal dari karya Belnap and Perloff (1988), yang memperkenalkan operator " memastikannya ", disingkat stit , hingga alasan tentang apa yang dapat dicapai agen dengan membuat pilihan yang sesuai dari waktu ke waktu. Meskipun logika asli untuk stit tidak melibatkan waktu secara eksplisit, semantik mereka didasarkan pada model waktu percabangan, di mana setiap pilihan agen pada waktu tertentu ditunjukkan oleh sebuah partisi dari sekian banyak sejarah yang melewati saat itu. Rumus \ (\ textit {stit} \, \ varphi \) secara intuitif mengatakan bahwa agen dapat membuat pilihan yang sesuai sehingga semua sejarah dalam pilihan tersebut memenuhi tujuan \ (\ varphi. \) Sejumlah ekstensi dan elaborasi dari STIT Logika kemudian dikembangkan Belnap dkk. (2001). Secara khusus, dimensi temporal secara bertahap diperkenalkan secara eksplisit ke dalam model STIT dan logika; untuk sebuah akun baru-baru ini, lihat Lorrini (2013), yang memberikan semantik formal dan melakukan axiomatisasi lengkap dari logika STIT temporal.
Keluarga penting lain dari logika temporal agensi adalah perpanjangan multiagen dari logika temporal tempaan CTL dan CTL *, yang diperkenalkan di Alur dkk. (2002) untuk penalaran temporal tentang sistem terbuka dengan nama logika temporal waktu bergantian ATL dan ATL *. Mereka kemudian menjadi kerangka logis yang sangat populer untuk penalaran strategis dalam sistem multiagen . Ini menambahkan bahasa LTL "quantifiers jalur strategis", parameterised dengan set agen \ (C \) dan mengkuantifikasi secara eksistensial melalui strategi kolektif \ (C \) dan kemudian secara universal mengenai kemungkinan pemutaran (sejarah) yang dapat muncul sebagai hasil dari \ (C \) mengikuti strategi kolektif yang dipilih. Jadi, konstruksi sintaksis utama baru dalam logika ATL * adalah rumus tipe \ (\ langle \! \ Langle C \ rangle \! \ Rangle \ varphi, \) secara intuitif mengatakan " Koalisi \ (C \) memiliki strategi kolektif untuk menjamin kepuasan tujuan \ (\ varphi \) pada setiap permainan (jalur) yang dimungkinkan oleh strategi kolektif dari \ (C \) ". Disini tujuan \ (\ varphi \) adalah formula temporal, yang ditentukan misalnya dalam logika LTL. Jadi, operator strategis satu langkah agen tunggal di ATL secara teknis sangat mirip dengan operator stit (Belnap dan Perloff, 1988). Perbedaan teknis utama antara logika-logika ini adalah pada semantik, yang agak lebih umum dan abstrak dalam kasus STIT, di mana 'sejarah' adalah entitas abstrak daripada 'permainan' konkrit - urutan negara penerus yang dihasilkan oleh transisi diskrit yang disebabkan oleh kolektif. tindakan semua agen, yang mendasari semantik ATL. Perpanjangan ATL, memperkenalkan beberapa gagasan dari teori STIT, dikembangkan di Broersen et al. (2006).
ATL * secara alami menggabungkan penalaran temporal dan strategis dalam permainan multi-player diskrit. Logika waktu bercabang CTL dan CTL * dapat dianggap sebagai versi agen tunggal ATL dan ATL *. Meskipun bahasa yang terakhir ini cukup ekspresif, namun pada umumnya mereka mempertahankan sifat komputasi yang baik dari yang pertama. Untuk keterangan lebih lanjut lihat Alur dkk. (2002), serta Goranko dan van Drimmelen (2006), di mana sebuah axiomatisasi dan desidabilitas lengkap ATL telah ditetapkan.

8.4 Logika spasial-temporal

Ruang dan waktu sangat terkait erat di dunia fisik, dan telah menjadi tidak terpisahkan dalam teori fisika modern. Pemikiran logis gabungan tentang ruang-waktu telah berkembang secara aktif selama beberapa dekade terakhir, terutama dalam konteks Kecerdasan Buatan, database spatio-temporal, ontologi dan jaringan kendala. Fokus utama penelitian terbaru adalah karakterisasi logis model spatio-temporal, ekspresif dan kompleksitas komputasi Kontchakov dkk. (2007). Bidang penelitian aktif baru-baru ini tentang teori logis untuk ruang-waktu adalah dalam konteks Teori Relativitas (Andréka et al 2007).

8.5 logika deskripsi Temporal

Logika deskripsi sangat dekat dengan logika modal. Mereka melibatkan konsep (predikat terbuka) dan peran (predikat biner) dan digunakan untuk menggambarkan berbagai ontologi dan hubungan antara konsep di dalamnya. Untuk detail lebih lanjut lihat misalnya Baader dan Lutz (2006). Logika deskripsi secara alami dapat dilokalisir dengan berbagai cara, lihat Artale dan Franconi (2000), Wolter dan Zakharyaschev (2000), dan Lutz dkk. (2008).

8.6 Logika temporal dan logika non-klasik lainnya

Pemikiran logis temporal secara alami dapat dibangun di atas, atau dikombinasikan dengan, berbagai sistem logika non-klasik yang menghasilkan, misalnya, dalam logika temporal yang banyak dihargai (Rescher and Urquhart 1971, Bab XVIII), logika temporal intuisi (Ewald 1986), konstruktif dan logika temporal paraconsistent (Kamide and Wansing 2010; 2011), logika temporal probabilistik (Hart dan Sharir 1986; Konur 2013), dll.

9. Pengurangan logis dan metode pengambilan keputusan untuk logika temporal

Penelitian ekstensif dan banyak publikasi selama 50 tahun terakhir telah mengembangkan berbagai sistem deduksi logis dan metode pengambilan keputusan untuk logika temporal yang disebutkan di sini dan banyak lagi. Hilbert gaya sistem aksiomatik telah menjadi yang paling umum dikembangkan sistem deduksi logis untuk logika temporal. Selain itu, banyak sistem lengkap tabelole semantik , kalkulus berurutan , dan sistem berbasis resolusi telah dikembangkan untuk berbagai logika temporal. Tidak jauh dari ruang lingkup dan ruang masuk ini untuk memberikan penjelasan menyeluruh tentang hal ini, jadi di sini kita hanya mencantumkan beberapa referensi umum mengenai sistem deduktif untuk logika temporal, di samping referensi yang lebih spesifik yang disebutkan di bagian lain dalam teks ini: Rescher and Urquhart ( 1971), Burgess (1984), Goldblatt (1987), Emerson (1990), Gabbay dkk. (1994), Bolc dan Szalas (1995), van Benthem (1995), Gabbay dan Guenthner (2002), Gabbay et al. (2003), Fisher et al. (2005), Blackburn dkk. (2006), Kröger dan Merz (2008), Fisher (2011).
Terutama yang efisien dan praktis berguna adalah metode berbasis taplak meja untuk menentukan kepuasan. Metode deskriptif semantik (aka, analitik), yang berasal dari karya perintis Beth, Hintikka, Smullyan, dan Fitting, didasarkan pada pencarian model memuaskan secara sistematis (menuai, pemalsuan model balik) jika sebuah formula masukan yang diuji untuk satisfiability (menuai, validitas), yang dijamin dapat menemukan model seperti itu kapan pun ada. Telah berhasil dikembangkan untuk pengujian kepuasan yang memuaskan untuk berbagai logika temporal, lihat Goré (1999) untuk survei tentang sistem taplak meja untuk banyak logika temporal dan yang lebih spesifik: Ben-Ari dkk. (1983) untuk logika waktu bercabang UB; Wolper (1985) untuk logika waktu linier LTL; Emerson dan Halpern (1985) untuk logika pohon komputasi CTL, Reynolds (2007) untuk CTL dengan pohon bundel semantik; Goranko dan Shkatov (2010) untuk ATL; Reynolds (2011) untuk logika pohon komputasi lengkap CTL *; Reynolds (2014) untuk real-time temporal logic RTL, dll.
Yang lain yang sangat penting dan praktis berguna adalah metode berbasis automata , digunakan baik untuk menentukan kepuasan dan untuk pengecekan model logika temporal. Metode ini telah berkembang secara aktif sejak awal 1990an. Mereka didasarkan pada hasil klasik tentang desidabilitas teori urutan ke 2 monadik dari bilangan natural (oleh Büchi) dan pohon biner tak terbatas (oleh Rabin). Metode berbasis automata mengubah formula temporal menjadi automata dengan kata-kata tak terbatas (untuk logika waktu linier) atau pohon tak terbatas (untuk logika waktu bercabang) dan mewakili model untuk logika sebagai objek masukan masing-masing (kata atau pohon tak terbatas) untuk automata terkait mereka. Jadi, khususnya, satisfiability dari sebuah formula menjadi setara dengan non-kekosongan bahasa robot yang terkait dengan rumus itu. Misalnya, otomasi pada pohon tak terbatas dan teorema Rabin digunakan untuk mendapatkan prosedur pengambilan keputusan CTL * di Emerson dan Sistla (1984). Untuk keterangan lebih lanjut lihat Vardi (2006).
Referensi penting lainnya mengenai hasil decidability dan prosedur keputusan untuk berbagai logika temporal termasuk Burgess (1980) dan Gurevich and Shelah (1985) untuk logika waktu bercabang, Burgess dan Gurevich (1985) untuk logika temporal linier, Goldblatt (1987) pada linier dan percabangan logika waktu, Montanari dan Policriti (1996) pada logika temporal metrik dan berlapis, French (2001) untuk beberapa logika waktu percepatan proporsional proporsional.
Sementara kebanyakan logika temporal proporsional dapat dipecahkan, menambahkan beberapa fitur sintaksis atau semantik dapat membuat mereka meledak secara komputasi dan menjadi tidak dapat diputuskan. Banyak logika temporal yang penting terus menjadi tidak dapat dipungkiri, bahkan di bawah asumsi yang sangat lemah sekalipun. Selain kombinasi dengan logika ekspresif lainnya, yang dibahas di Bagian 8 , penyebab paling umum lainnya dari undecidability dalam logika temporal meliputi: model seperti grid, khas untuk sistem banyak dimensi atau temporal; operator temporal sepanjang banyak jalur waktu; produk logika temporal; logika berbasis interval, di mana kebenaran rumus didefinisikan pada interval waktu tanpa asumsi lokalitas; mekanisme referensi waktu, seperti quantifier pembeku dan pengikat hibrida; aritmatika fitur: penambahan waktu, kendala waktu yang tepat, dll Namun, ada berbagai cara untuk menjinakkan logika temporal dan mengembalikan kemampuan decidability, seperti: batasan sintaksis, mengidentifikasi fragmen yang dapat ditolak (misalnya fragmen dua variabel dari logika orde pertama klasik FO \ (^ {2}, \) fragmen yang dijaga, fragmen monodik, dll.); pembatasan parametrik yang sesuai, misalnya pada jumlah variabel proposisional atau kedalaman nesting; pembatasan semantik yang sesuai, misalnya lokalitas untuk logika interval, dll.

10. Aplikasi logika temporal

Logika temporal adalah salah satu bidang logika dan filosofi yang paling luas, dengan aplikasi aktual dan potensial mulai dari ilmu komputer, kecerdasan buatan dan linguistik, hingga ilmu pengetahuan alam, kognitif, dan sosial. Dalam entri ini kita akan membatasi diri kita pada eksposisi singkat beberapa dari ini.

10.1 Logika temporal dalam Ilmu Komputer

Logika temporal adalah salah satu titik pertemuan alami filsafat dan ilmu komputer, yang isu dan agenda terpisahnya digabungkan dalam interaksi yang subur. Pekerjaan awal secara implisit menyarankan penerapan penalaran temporal untuk pemodelan dan analisis sistem transisi deterministik dan stokastik adalah teori proses dan peristiwa di Rescher dan Urquhart (1971, Bab XIV). Namun, logika temporal menjadi sangat menonjol di Ilmu Komputer dengan kertas mani Pnueli (1977) yang mengusulkan penerapan logika temporal terhadap spesifikasi dan verifikasi program dan sistem reaktif dan bersamaan . Untuk memastikan perilaku program reaktif yang benar, di mana penghitungannya tidak berakhir (misalnya, sistem operasi), perlu menetapkan dan memverifikasi secara pasti eksekusi tak terhingga yang dapat diterima dari program tersebut. Demikian juga, untuk memastikan kebenaran program bersamaan, yang dilakukan oleh dua atau lebih prosesor yang bekerja secara paralel, perlu untuk secara formal menentukan dan memverifikasi sinkronisasi mereka, yaitu cara kerja berbagai prosesor saling terkait, dan untuk menggambarkan secara formal eksekusi program yang tak terbatas yang dapat diterima. Waktu relatif dari tindakan harus dikoordinasikan dengan hati-hati agar memastikan integritas informasi yang dibagi di antara prosesor dipertahankan.
Pola kunci temporal penting dalam menentukan program tersebut adalah:

" Liveness " properties, atau " eventualities ", yang melibatkan pola temporal \ (F {p}, \) \ (q \ to F {p}, \) or \ (G (q \ to F {p}), \) yang memastikan bahwa jika prasyarat tertentu (\ (q \)) pada awalnya terpenuhi, maka keadaan yang diinginkan (memuaskan \ (p \)) pada akhirnya akan tercapai dalam perhitungan. Misalnya, seperti " Jika sebuah pesan dikirim, akhirnya akan dikirim " dan " Kapan pun pekerjaan pencetakan diaktifkan, pada akhirnya akan selesai ".
" Keamanan " atau " invariance ", yang melibatkan pola temporal \ ({G} {p}, \) \ (q \ to {G} {p}, \) or \ (G (q \ to {G} {p }), \) yang memastikan bahwa jika prasyarat tertentu (\ (q \)) pada awalnya terpenuhi, maka keadaan yang tidak diinginkan (melanggar kondisi keamanan \ (p \)) tidak akan pernah terjadi. Contohnya adalah: " Tidak lebih dari satu proses akan berada dalam bagian kritisnya setiap saat ", " Sumber daya tidak akan pernah digunakan oleh dua atau lebih proses secara simultan ", atau, untuk contoh yang lebih praktis: " Lampu lalu lintas tidak akan pernah menunjukkan hijau di kedua arah "," Sebuah kereta api tidak akan pernah melewati semafor merah ".
" Keadilan ", yang melibatkan kombinasi pola temporal dari bentuk \ ({GF} {p} \) ("tak terbatas sering \ (p \)") atau \ ({FG} {p} \) ("akhirnya selalu \ (p \) "). Secara intuitif, keadilan mensyaratkan bahwa dalam sistem di mana beberapa proses berbagi sumber daya dijalankan bersamaan, mereka harus diperlakukan secara 'adil' oleh sistem operasi, penjadwal, dsb. Persyaratan kewajaran yang khas mengatakan bahwa jika sebuah proses cukup kuat dalam mengirimkan permintaan (secara wajar) misalnya, terus mengirimkannya lagi dan lagi) maka akhirnya permintaannya akan diberikan.

Karena perhitungan tak terbatas secara formal diwakili oleh model logika waktu linier LTL, sementara non-determinisme yang dimodelkan oleh waktu percabangan merupakan ciri yang melekat pada banyak aplikasi sains komputer, LTL dan logon pohon komputasi CTL dan CTL * sangat penting untuk spesifikasi. dan verifikasi sistem konkuren dan reaktif. Berikut adalah contoh menggabungkan sifat liveness and safety dari satu perhitungan: " Setiap kali keadaan siaga tercapai, alarm akan diaktifkan dan tetap aktif sampai keadaan aman tercapai ". Hal ini dapat dinyatakan dalam LTL sebagai
\ [G (\ tt {alert} \ ke (\ tt {alarm} \ U \ \ tt {secure})). \] Contoh lain, mengacu pada semua penghitungan di sistem: " Jika proses \ (\ sigma \) akhirnya diaktifkan pada beberapa perhitungan mulai dari keadaan saat ini, maka pada setiap perhitungan yang dimulai di sana, kapan saja \ (\ sigma \) diaktifkan akan tetap aktif sampai proses \ (\ tau \) dinonaktifkan "dapat diformalkan di CTL * sebagai:
\ [\ Diamond F \, \ textsf {enabled} _ {\ sigma} \ to \ Box G (\ textsf {enabled} _ {\ sigma} \ to (\ textsf {enabled} _ {\ sigma} \, U \ , \ textsf {disabled} _ {\ tau})). \] Variasi LTL dengan aplikasi yang berguna untuk menentukan dan mempertimbangkan sistem bersamaan adalah logika temporal Lamport (1994) tentang tindakan TLA. Aplikasi lain dari logika temporal dalam ilmu komputer meliputi: database temporal, proses dan sistem real-time, verifikasi perangkat keras, dll. Informasi lebih lanjut mengenai aplikasi semacam itu dapat ditemukan misalnya di Pnueli (1977), Emerson and Clarke (1982), Moszkowski ( 1983), Galton (1987), Emerson (1990), Alur dan Henzinger (1992), Lamport (1994), Vardi dan Wolper (1994), Bolc dan Szalas (1995), Kröger dan Merz (2008), Fisher (2011) .

10.2 logika temporal dalam Kecerdasan Buatan

Mengaitkan penalaran temporal dengan Artificial Intelligence (AI) setidaknya sampai pada teori proses dan kejadian yang telah disebutkan di Rescher dan Urquhart (1971, Bab XIV). Presentasi dan penalaran temporal telah menjadi tema yang lebih menonjol di AI sejak karya mani Allen (1984), yang disebutkan dalam konteks logika temporal temporal, yang berkaitan dengan menemukan kerangka kerja umum yang memadai untuk semua representasi temporal yang disyaratkan oleh program AI. Kalkulus Peristiwa Kowalski dan Sergot (1986) dikejar lebih spesifik dalam kerangka pemrograman logika, namun karakternya sama umumnya. Alasan temporal juga digabungkan secara alami dengan kerangka kerja AI lainnya, seperti Situation Calculus (Pinto dan Reiter 1995) dan Action Theory (Lamport 1994). Sebuah survei yang berguna mengenai isu-isu yang melibatkan penalaran waktu dan temporal di AI adalah Galton (1995); Survei yang lebih baru tentang wilayah ini adalah Fisher et al. (2005) dan bab buku pegangan yang lebih ringkas (Fisher 2008).
Sebuah isu yang telah berkembang dalam konteks AI - tapi yang juga penting bagi filsafat dan linguistik - menyangkut bentuk logis dari pernyataan yang melibatkan waktu atau ketegangan. Mungkin pendekatan yang paling tradisional adalah dengan cara metode argumen temporal yang disebut, dimana dimensi temporal ditangkap dengan menambahkan setiap proposisi variabel waktu atau predikat dengan tempat argumen tambahan, untuk diisi oleh sebuah ekspresi yang menunjuk suatu waktu. , seperti misalnya
\ [\ text {Kill} (\ text {Brutus}, \ text {Caesar}, 44 \ text {BCE}). \] Memang, sebelum munculnya Logika Tegang, metode argumen temporal adalah pilihan alami formalisme untuk ekspresi logis dari informasi temporal.
Metode argumen temporal menemukan kesulitan, bagaimanapun, jika diinginkan untuk memodelkan pembedaan aspek antara, misalnya, keadaan, peristiwa dan proses. Pernyataan yang diajukan oleh pembuat laporan (seperti "Mary is sleep") memiliki kejadian temporal yang homogen , karena mereka harus memegang subinterval dari interval di mana mereka memegang (misalnya, jika Maria tertidur dari jam 1 sampai jam 6 pagi Dia tertidur dari jam 1 sampai jam 2, dari jam 2 sampai jam 3, dan seterusnya). Sebaliknya, proposisi yang melaporkan kejadian (seperti "John berjalan ke stasiun") memiliki kejadian temporal yang tidak homogen; lebih tepatnya, proposisi semacam itu tidak berlaku untuk subinterval yang tepat dari interval yang benar (misalnya, jika John berjalan ke stasiun selama selang waktu dari jam 1 sampai seperempat yang lalu, maka bukan itu masalahnya bahwa dia berjalan ke stasiun selama selang waktu dari jam 1 sampai lima lewat satu - lebih tepatnya, selama interval itu dia berjalan sampai ke stasiun radio).
Metode reifikasi tipe negara dan peristiwa diperkenalkan untuk memenuhi perbedaan jenis ini. Ini adalah pendekatan yang sangat populer di Artificial Intelligence, yang terutama terkait dengan Allen (1984). Dalam pendekatan ini, jenis keadaan dan peristiwa dilambangkan dengan istilah dalam teori orde pertama; Kejadian temporal mereka diungkapkan dengan menggunakan predikat relasional "Holds" dan "Occurs", seperti misalnya,

Berpegang (Tertidur (Mary), (13:00, 18:00))
Terjadi (Walk-to (John, Station), (13:00, 13:15))

dimana persyaratan bentuk \ (({t}, t ') \) menunjukkan interval waktu dengan cara yang jelas.
Homogenitas negara dan inhomogeneity kejadian dijamin oleh aksioma seperti

\ (\ forall {s}, {i}, {i '} (Tahan {{s}, {i}) \ land In ({i'}, {i}) \ rightarrow Holds {{s}, {i '})) \)
\ (\ forall {e}, {i}, {i '} (Terjadi ({e}, {i}) \ land In ({i'}, {i}) \ rightarrow \ neg Terjadi ({e}, {saya'}))\)

dimana "\ (In \)" mengungkapkan hubungan subinterval yang tepat.
Alternatif untuk mengenang jenis acara adalah untuk mengidentifikasikan token acara. Gagasan ini diajukan oleh Donald Davidson (1967) sebagai solusi atas apa yang disebut "variabel poladisitas". Masalahnya adalah memberikan akun formal tentang keabsahan kesimpulan tersebut

John melihat Mary di London pada hari Selasa.
Oleh karena itu, John melihat Maria pada hari Selasa.

Gagasan utamanya adalah bahwa setiap predikat pembentuk acara diberkahi dengan tempat argumen tambahan untuk diisi dengan variabel yang berkisar dari event-token, yaitu kejadian tanggal tertentu. Inferensi di atas kemudian dilemparkan dalam bentuk logis seperti

\ (\ exist {e} (lihat (John, Mary, {e}) \ & Place ({e}, London) \ land Time ({e}, Selasa)), \)
Oleh karena itu, \ (\ ada {e} (lihat (John, Mary, {e}) \ land Time ({e}, Selasa)). \)

Dalam bentuk ini, kesimpulan tidak memerlukan aparatus logis yang melebihi dan di atas standar logika urutan pertama; Atas dasar itu, validitas kesimpulan dianggap dijelaskan. Pendekatan ini telah digunakan dalam konteks komputasi di Calculus Acara Kowalski dan Sergot (1986).
Sebagian besar pekerjaan tentang penalaran sementara di AI telah terkait erat dengan masalah kerangka yang terkenal, yang timbul dari keharusan bagi seorang ahli logika untuk mengetahui, atau dapat menyimpulkan, tidak hanya sifat-sifat dunia yang berubah sebagai hasil dari setiap kejadian atau tindakan, tapi juga sifat-sifat yang tidak berubah. Dalam kehidupan sehari-hari, kita biasanya menangani fakta-fakta seperti itu dengan lancar tanpa secara sadar mengiklankannya: kita anggap remeh tanpa memikirkannya, misalnya, bahwa warna mobil biasanya tidak berubah saat gigi berubah. Masalah bingkai berkaitan dengan bagaimana memformalkan logika tindakan dan kejadian sehingga inferensi yang tidak terbatas semacam ini tersedia tanpa kita harus mengkodekan semuanya secara eksplisit. Pekerjaan mani di daerah ini adalah McCarthy dan Hayes (1969). Referensi yang berguna untuk masalah frame adalah Shanahan (1997).

10.3 Temporalitas dalam bahasa dan linguistik alami

Aspek temporal bahasa alam beragam dan meluas. Salah satu pendekatan analitik pertama untuk topik itu, yang terdaftar di Prior (1967) di antara prekursor Logika Tegang, adalah analisis tenses bahasa Inggris Hans Reichenbach (1947), yang menurut fungsinya masing-masing tegang adalah untuk menentukan hubungan temporal. Di antara tiga titik waktu yang terkait dengan ujaran, yaitu: waktu bicara \ (S, \) waktu referensi \ (R, \) dan waktu kejadian \ (E. \) Dengan teori itu, Reichenbach mencirikan sebagian besar tenses dalam bahasa alami Misalnya, dia dapat dengan mudah membedakan antara masa lalu yang sederhana, "Saya melihat Yohanes", yang mana "(lihatlah)," dan saya sekarang melihat "Saya telah melihat Yohanes", untuk mana \ (E \ lt R = S, \) pernyataan terdahulu yang mengacu pada masa lalu bersamaan dengan kejadian melihat John, yang terakhir sampai sekarang, yang relatif terkait dengan melihat John di masa lalu. Namun, analisis Reichenbach tidak memadai untuk memperhitungkan penggunaan tegang dalam bahasa alami secara keseluruhan. Selanjutnya, banyak pekerjaan telah dilakukan untuk memperbaiki analisis, tidak hanya dari tenses tapi juga ekspresi temporal lainnya dalam bahasa seperti preposisi temporal dan connectives ("before", "after", "since", "during", "until") , menggunakan banyak jenis logika temporal yang disajikan di sini. Untuk beberapa contoh, lihat Dowty (1979), Galton (1984), Taylor (1985), Richards et al. (1989). Kumpulan makalah tengara yang berguna di daerah ini adalah Mani et al. (2005). Untuk detail lebih lanjut lihat Steedman (1997), Kuhn dan Portner (2006), dan masuk pada tegang dan aspek .Sumber: plato.stanford.edu

Logika Aristoteles - Logika Temporal