Analitik tablo yöntemi - Method of analytic tableaux

Kısmen oluşturulmuş bir önerme tablosunun grafik temsili

Olarak dayanıklı teori , semantik tablo ( / t æ b l oʊ , t æ b l oʊ / ; çoğul: tableaux olarak da adlandırılan gerçek ağacı ) a, karar işlemi için tümce ve ilgili mantık ve dayanıklı prosedür formülleri için birinci dereceden mantık . Analitik bir tablo, her düğümde kanıtlanacak veya çürütülecek orijinal formülün bir alt formülü bulunan mantıksal bir formül için hesaplanan bir ağaç yapısıdır. Hesaplama bu ağacı oluşturur ve onu tüm formülü ispatlamak veya çürütmek için kullanır. Tablo yöntemi, çeşitli mantıkların sonlu formül kümelerinin tatmin edilebilirliğini de belirleyebilir . Modal mantık için en popüler ispat prosedürüdür (Girle 2000).

Giriş

Çürütme tablosu için amaç, bir formülün olumsuzlanmasının tatmin edilemeyeceğini göstermektir. Ana bağlayıcıdan başlayarak , olağan bağlantıların her birinin işlenmesi için kurallar vardır . Çoğu durumda, bu kuralların uygulanması alt tablonun ikiye bölünmesine neden olur. Nicelik belirteçleri somutlaştırılır. Bir tablonun herhangi bir dalı bariz bir çelişkiye yol açarsa , dal kapanır . Tüm dallar kapanırsa, kanıt tamamlanmış demektir ve orijinal formül mantıksal bir gerçektir .

Arkasındaki temel fikir rağmen analitik tablo yöntemi elde edilir kesme eleme teoreminin ait yapısal geçirmez teori , anlam olarak tablo taşı kökenleri (ya da semantik bağlantılı mantıksal eklemlerin), dayanıklı teorinin sadece yapıldığı son on yıl.

Daha spesifik olarak, bir tablo hesabı, her bir kuralın bir mantıksal bağlayıcının bileşen parçalarına nasıl ayrılacağını belirleyen sonlu bir kurallar koleksiyonundan oluşur. Kuralları genellikle sonlu cinsinden ifade edilmiştir setleri bu tür daha fazla karmaşık veri yapılarının, kullanmalıdır olan mantık olmasına rağmen, aşağıdaki formüllere ait MULTISETS , listeler , hatta ağaç formüller. Bundan böyle "küme", {set, multiset, list, tree} 'den herhangi birini belirtir.

Her mantıksal bağlayıcı için böyle bir kural varsa, prosedür sonunda yalnızca atomik formüllerden ve bunların olumsuzlamalarından oluşan ve daha fazla parçalanamayan bir küme üretecektir . Böyle bir küme, söz konusu mantığın anlambilimine göre tatmin edici veya tatmin edilemez olarak kolayca tanınabilir. Bu süreci takip etmek için, bir tablonun düğümleri bir ağaç şeklinde düzenlenir ve bu ağacın dalları sistematik bir şekilde oluşturulur ve değerlendirilir. Bu ağacı aramak için böylesine sistematik bir yöntem, kesinti ve otomatik akıl yürütme gerçekleştirmek için bir algoritmaya yol açar. Bu daha büyük ağacın, düğümlerin kümeler, çoklu kümeler, listeler veya ağaçlar içerip içermediğine bakılmaksızın mevcut olduğuna dikkat edin.

Önerme mantığı

Bu bölümde klasik önermeler mantığı için tablo hesabı sunulmaktadır. Bir tablo, belirli bir formül setinin tatmin edici olup olmadığını kontrol eder. Ya geçerliliğini veya Vasiyetiniz kontrol etmek için kullanılabilir: negasyonunun edilemezdir ve formüller eğer bir formül geçerlidir ima eğer edilemezdir olduğunu. ${\ displaystyle A_ {1}, \ ldots, A_ {n}}$${\ displaystyle B}$${\ displaystyle \ {A_ {1}, \ ldots, A_ {n}, \ neg B \}}$

Önerme tablosunun ana ilkesi, karmaşık formülleri, tamamlayıcı değişmez çiftler üretilinceye veya daha fazla genişletme mümkün olmayana kadar daha küçük olanlara "ayırmaya" çalışmaktır.

{(A⋁¬b) ⋀b, ¬a} için ilk tablo

Yöntem, düğümleri formüllerle etiketlenmiş bir ağaç üzerinde çalışır. Her adımda bu ağaç değiştirilir; önerme durumunda, izin verilen tek değişiklik bir yaprağın soyundan gelen bir düğümün eklenmesidir. Prosedür, yetersizliği kanıtlamak için kümedeki tüm formüllerden oluşan bir zincir oluşturarak başlar. Bu başlangıç ​​adımının bir varyantı, kökü ile etiketlenen tek düğümlü bir ağaçla başlamaktır ; bu ikinci durumda, prosedür her zaman bir yaprağın altındaki kümedeki bir formülü kopyalayabilir. Çalışan bir örnek olarak, setin tablosu gösterilmiştir. ${\ displaystyle \ top}$${\ displaystyle \ {{a \ vee \ neg b) \ kama b, \ neg a \}}$

Tablonun ilkesi, aynı dalın düğümlerindeki formüllerin birlikte düşünülürken, farklı dalların bölünmüş olarak kabul edilmesidir. Sonuç olarak, bir tablo, bağlaçların ayrılması olan bir formülün ağaç benzeri bir temsilidir. Bu formül, yetersizliği kanıtlamak için kullanılan sete eşdeğerdir. Prosedür, sonuçtaki tablonun temsil ettiği formülün orijinal olana eşdeğer olacağı şekilde tabloyu değiştirir. Bu bağlaçlardan biri, bir çift tamamlayıcı değişmezi içerebilir ve bu durumda, bu bağlaşımın tatmin edici olmadığı kanıtlanır. Tüm bağlaçların tatmin edici olmadığı kanıtlanırsa, orijinal formül kümesi tatmin edici değildir.

Ve

(a⋁¬b) ⋀b, a⋁¬b ve b üretir

Bir tablonun bir dalı iki formülün birleşimi olan bir formül içerdiğinde , bu iki formül de o formülün sonucudur. Bu gerçek, bir tablonun genişletilmesi için aşağıdaki kuralla resmileştirilebilir: ${\ displaystyle A \ dilim B}$

( ) Tablonun bir dalı birleşik bir formül içeriyorsa , yaprağına formülleri içeren iki düğümden oluşan zinciri ekleyin ve ${\ displaystyle \ kama}$${\ displaystyle A \ dilim B}$${\ displaystyle A}$${\ displaystyle B}$

Bu kural genellikle şu şekilde yazılır:

${\ displaystyle (\ land) {\ frac {A \ wedge B} {\ begin {dizi} {c} A \\ B \ end {dizi}}}}$

Bu kuralın bir çeşidi, bir düğümün tek bir formül yerine bir dizi formül içermesine izin verir. Bu durumda, bu setteki formüller birlikte değerlendirilir, böylece bir dalın sonuna içeren bir eklenebilir . Daha doğrusu, bir dal üzerindeki bir düğüm etiketlenmişse , yeni yaprak dala eklenebilir . ${\ displaystyle \ {A, B \}}$${\ displaystyle A \ dilim B}$${\ displaystyle X \ fincan \ {A \ kama B \}}$${\ displaystyle X \ cup \ {A, B \}}$

Veya

a⋁¬b, a ve ¬b üretir

Bir tablonun bir dalı, iki formülün ayrılması gibi bir formül içeriyorsa , aşağıdaki kural uygulanabilir: ${\ displaystyle A \ vee B}$

( ) Daldaki bir düğüm ayrık bir formül içeriyorsa , dalın yaprağına sırasıyla formül ve formüllerini içeren iki kardeş çocuk oluşturun . ${\ displaystyle \ vee}$${\ displaystyle A \ vee B}$${\ displaystyle A}$${\ displaystyle B}$

Bu kural, bir dalı ikiye böler ve yalnızca son düğüm için farklılık gösterir. Dallar birbirlerinden ayrık olarak kabul edildiğinden, ortak olmayan düğümlerinin ayrışması tam olarak olduğundan, ortaya çıkan iki dal orijinaline eşdeğerdir . Ayrılma kuralı genellikle, oluşturulacak iki farklı düğümün formüllerini ayırmak için sembol kullanılarak resmi olarak yazılır : ${\ displaystyle A \ vee B}$${\ displaystyle |}$

${\ displaystyle (\ vee) {\ frac {A \ vee B} {A \ orta B}}}$

Düğümlerin formül kümeleri içerdiği varsayılırsa, bu kural şu ​​şekilde değiştirilir: Bir düğüm etiketlenirse , bu düğümün bulunduğu dalın bir yaprağına sırasıyla ve etiketli iki kardeş çocuk düğüm eklenebilir . ${\ displaystyle Y \ fincan \ {A \ vee B \}}$${\ displaystyle Y \ fincan \ {A \}}$${\ displaystyle Y \ fincan \ {B \}}$

Değil

Tableaux'nun amacı, karşıt değişmez çiftler üretilinceye veya başka hiçbir kural uygulanamayana kadar giderek daha basit formüller üretmektir. Olumsuzluk, başlangıçta formülleri olumsuzlama normal biçimde yaparak tedavi edilebilir , böylece olumsuzlama yalnızca değişmezlerin önünde gerçekleşir. Alternatif olarak, tablonun genişletilmesi sırasında De Morgan'ın yasaları kullanılabilir , böylece örneğin olarak ele alınır . Bu durumda, bir çift olumsuzlamayı (içinde gibi ) getiren veya kaldıran kurallar da kullanılır (aksi takdirde, aşağıdaki gibi bir formülü genişletmenin hiçbir yolu olmazdı : ${\ displaystyle \ neg (A \ kama B)}$${\ displaystyle \ neg A \ vee \ neg B}$${\ displaystyle \ neg \ neg A}$${\ displaystyle \ neg \ neg (A \ kama B)}$

${\ displaystyle (\ neg 1) {\ frac {A} {\ neg \ neg A}}}$

${\ displaystyle (\ neg 2) {\ frac {\ neg \ neg A} {A}}}$

Tablo kapandı

Kapanış

Her tablo, tablonun oluşturulduğu kümeye eşdeğer olan bir formülün grafiksel temsili olarak düşünülebilir. Bu formül aşağıdaki gibidir: Tablonun her bir dalı, formüllerinin birleşimini temsil eder; tablo, dallarının ayrışmasını temsil eder. Genişletme kuralları bir tabloyu eşdeğer temsil edilen bir formüle sahip bir tabloyu dönüştürür. Tablo, girdi kümesinin formüllerini içeren tek bir dal olarak başlatıldığından, ondan elde edilen sonraki tüm çizelgeler, bu kümeye eşdeğer olan formülleri temsil eder (ilk tablonun doğru olarak etiketlenmiş tek düğüm olduğu varyantta, tablolar, orijinal setin sonuçlarıdır.)

Tatmin edilebilir küme {a⋀c, ¬a⋁b} için bir tablo: tüm kurallar her dalda her formüle uygulanmıştır, ancak tablo, tatmin edici kümeler için beklendiği gibi kapatılmamıştır (yalnızca sol dal kapalıdır)

Tableaux yöntemi, ilk formül kümesiyle başlayarak ve daha sonra, çelişki karşıt değişmezlerin basit biçiminde gösterilinceye kadar tabloya daha basit ve daha basit formüller ekleyerek çalışır. Bir tablonun temsil ettiği formül, dalları tarafından temsil edilen formüllerin ayrımı olduğundan, her dal bir çift zıt değişmez içerdiğinde çelişki elde edilir.

Bir dal bir kez bir kelimeyi ve onun olumsuzlamasını içerdiğinde, karşılık gelen formülü tatmin edici değildir. Sonuç olarak, daha fazla genişletmeye gerek olmadığı için bu dal artık "kapatılabilir". Bir tablonun tüm dalları kapalıysa, tablonun temsil ettiği formül tatmin edici değildir; bu nedenle, orijinal set de tatmin edici değildir. Tüm dalların kapalı olduğu bir tablo elde etmek, orijinal setin yetersizliğini kanıtlamanın bir yoludur. Önerme durumunda, her genişleme kuralının uygulanabildiği her yerde uygulanmış olması koşuluyla, tatmin edilebilirliğin kapalı bir tablo bulmanın imkansızlığı ile kanıtlandığı da kanıtlanabilir. Özellikle, bir tablo bazı açık (kapalı olmayan) dallar içeriyorsa ve gerçek olmayan her formül, formülün içinde bulunduğu her dalda yeni bir düğüm oluşturmak için bir kural tarafından kullanılmışsa, küme tatmin edici olur.

Bu kural, bir formülün birden fazla dalda oluşabileceğini hesaba katar (düğümün "altında" en az bir dallanma noktası varsa bu durum söz konusudur). Bu durumda, formülü genişletme kuralı, tablonun daha fazla genişletilemeyeceği ve formülün bu nedenle daha fazla genişletilemeyeceği sonucuna varılmadan önce, sonuçları hala açık olan tüm bu dallara eklenecek şekilde uygulanmalıdır. tatmin edici.

Set etiketli tablo

Tablonun bir varyantı, düğümleri tek formüllerden ziyade formül kümeleriyle etiketlemektir. Bu durumda, ilk tablo, tatmin edici olduğu kanıtlanmış set ile etiketlenmiş tek bir düğümdür. Bir kümedeki formüllerin bu nedenle bağlantılı olduğu kabul edilir.

Tablonun genişletme kuralları artık tablonun yaprakları üzerinde çalışarak tüm iç düğümleri yok sayabilir. Bağlantı için, kural, her ikisini de içeren ve onun yerine içeren küme ile birleşimi içeren bir kümenin eşdeğerliğine dayanır . Özellikle, bir yaprak etiketlenmişse , ona etiketle bir düğüm eklenebilir : ${\ displaystyle A \ dilim B}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle X \ fincan \ {A \ kama B \}}$${\ displaystyle X \ cup \ {A, B \}}$

${\ displaystyle (\ kama) {\ frac {X \ fincan \ {A \ kama B \}} {X \ fincan \ {A, B \}}}}$

Ayrılma için, bir küme , iki kümenin ve . Sonuç olarak, ilk küme bir yaprağı etiketlerse, son iki formülle etiketlenen iki çocuk buna eklenebilir. ${\ displaystyle X \ fincan \ {A \ vee B \}}$${\ displaystyle X \ cup \ {A \}}$${\ displaystyle X \ cup \ {B \}}$

${\ displaystyle (\ vee) {\ frac {X \ fincan \ {A \ vee B \}} {X \ fincan \ {A \} | X \ fincan \ {B \}}}}$

Son olarak, bir küme hem bir değişmezi hem de onun olumsuzlamasını içeriyorsa, bu dal kapatılabilir:

${\ displaystyle (kimlik) {\ frac {X \ cup \ {p, \ neg p \}} {kapalı}}}$

Belirli bir sonlu küme X için bir tablo, tüm alt düğümlerin ebeveynlerine tablo kurallarını uygulayarak elde edildiği , kök X'e sahip sonlu (baş aşağı) bir ağaçtır . Böyle bir tablodaki bir dal, yaprak düğümü "kapalı" içeriyorsa kapatılır. Tüm dalları kapalıysa bir tablo kapanır. En az bir şube kapatılmamışsa bir tablo açıktır.

Burada, X = { r 0 & ~ r 0, p 0 & ((~ p 0 ∨ q 0) & ~ q 0)} kümesi için, her kural uygulaması sağ tarafta işaretlenmiş (& ve ~ sırasıyla ve için durun ) ${\ displaystyle \ kama}$${\ displaystyle \ neg}$

 {r0 & ~r0, p0 & ((~p0 v q0) & ~q0)}                                    {r0 & ~r0, p0 & ((~p0 v q0) & ~q0)}
--------------------------------------(&)                        ------------------------------------------------------------(&)
 {r0, ~r0, p0 & ((~p0 v q0) & ~q0)}                                    {r0 & ~r0, p0, ((~p0 v q0) & ~q0)}
 -------------------------------------(id)                         ----------------------------------------------------------(&)
            closed                                                      {r0 & ~r0, p0,  (~p0 v q0),  ~q0} 
                                                                -------------------------------------------------------------(v)
                                                                  {r0 & ~r0, p0, ~p0, ~q0}       |   {r0 & ~r0, p0, q0, ~q0}
                                                                 -------------------------- (id)     ----------------------  (id)
                                                                          closed                            closed

Soldaki tablo yalnızca bir kural uygulamasından sonra kapanır, sağ el ise işareti kaçırır ve kapanması çok daha uzun sürer. Açıkça, her zaman en kısa kapalı tabloları bulmayı tercih ederiz, ancak formüllerin tüm girdi kümeleri için en kısa kapalı tabloları bulan tek bir algoritmanın var olamayacağı gösterilebilir.

Üç kural , ve yukarıda verilen belirli bir dizi karar vermek için daha sonra yeterli reddedildiği normal formda formüller ortaklaşa karşılanabilir şunlardır: ${\ displaystyle (\ kama)}$${\ displaystyle (\ vee)}$${\ displaystyle (kimlik)}$${\ displaystyle X '}$

Tüm olasılıkları tüketene kadar veya tüm olasılıkları tüketene ve her tablonun açık olduğu sonucuna varana kadar tüm olası siparişlerde olası tüm kuralları uygulayın . ${\ displaystyle X '}$${\ displaystyle X '}$

İlk durumda, birlikte tatmin edilemez ve ikinci durumda, açık dalın yaprak düğümü, atomik formüllere ve birlikte tatmin edici kılan olumsuz atomik formüllere bir görev verir . Klasik mantık aslında sadece (herhangi) bir tabloyu tamamen araştırmamız gereken oldukça hoş bir özelliğe sahiptir: eğer kapanırsa o zaman tatmin edilemez ve eğer açıksa o zaman tatmin edici olur. Ancak bu özellik genellikle diğer mantıklardan hoşlanmaz. ${\ displaystyle X '}$${\ displaystyle X '}$${\ displaystyle X '}$${\ displaystyle X '}$

Bu kurallar, bir X formülünün ilk setini alarak ve her bir üye C'yi , bir dizi formül X veren mantıksal olarak eşdeğer olumsuzlanmış C normal formu ile değiştirerek tüm klasik mantık için yeterlidir . X'in ancak ve ancak X ' tatmin edici ise tatmin edilebilir olduğunu biliyoruz , bu nedenle yukarıda özetlenen prosedürü kullanarak X' için kapalı bir tablo aramak yeterlidir .

Ayarlayarak biz formül olmadığını test edebilirsiniz A bir olduğunu totoloji Klasik Mantık: ${\ displaystyle X = \ {\ neg A \}}$

İçin tablo halinde kapanmadan sonra edilemezdir ve bu yüzden A hiçbir atama beri totolojidir doğruluk değerlerine hiç yapacak bir false. Aksi takdirde, herhangi bir açık tablonun herhangi bir açık dalının herhangi bir açık yaprağı, A'yı tahrif eden bir atama verir . ${\ displaystyle \ {\ neg A \}}$${\ displaystyle \ neg A}$${\ displaystyle \ {\ neg A \}}$

Koşullu

Klasik önermesel mantık genellikle maddi imayı belirtmek için bir bağa sahiptir . Biz ⇒ olarak bu bağ yazarsan, o zaman formül A ⇒ B "ise açılımı bir sonra B ". A ⇒ B'yi bileşen formüllerine ayırmak için bir tablo kuralı vermek mümkündür . Benzer şekilde, ¬ ( A ∧ B ), ¬ ( A ∨ B ), ¬ (¬ A ) ve ¬ ( A ⇒ B ) 'nin her birini ayırmak için birer kural verebiliriz . Bu kurallar birlikte, belirli bir formül setinin klasik mantıkta aynı anda tatmin edici olup olmadığına karar vermek için bir sonlandırma prosedürü verecektir, çünkü her kural bir formülü bileşenlerine böler, ancak hiçbir kural daha küçük bileşenlerden daha büyük formüller oluşturmaz. Bu nedenle, sonunda yalnızca atomların ve atomların olumsuzluklarını içeren bir düğüme ulaşmalıyız . Bu son düğüm (id) ile eşleşirse, şubeyi kapatabiliriz, aksi takdirde açık kalır.

Ancak, aşağıdaki denkliklerin klasik mantıkta geçerli olduğuna dikkat edin; burada (...) = (...), sol taraftaki formülün mantıksal olarak sağ taraftaki formüle eşdeğer olduğu anlamına gelir :

${\ displaystyle {\ begin {array} {lcl} \ neg (A \ land B) & = & \ neg A \ lor \ neg B \\\ neg (A \ lor B) & = & \ neg A \ land \ neg B \\\ neg (\ neg A) & = & A \\\ neg (A \ Rightarrow B) & = & A \ land \ neg B \\ A \ Rightarrow B & = & \ neg A \ lor B \\ A \ Leftrightarrow B & = & (A \ land B) \ lor (\ neg A \ land \ neg B) \\\ neg (A \ Leftrightarrow B) & = & (A \ land \ neg B) \ lor (\ neg A \ arazi B) \ end {dizi}}}$

Biz keyfi bir formül ile başlarsanız C arasında Klasik Mantık ve içinde sağ tarafla da sol el tarafı yerine arka arkaya bu eşdeğerlikleri uygulamak C , o zaman bir formül elde edecek C' mantıksal olarak eşdeğerdir C ancak özelliğine sahip olan o C' etkilemeyeceğini ve yalnızca atomik formüller önünde ¬ görünür içeriyor. Böyle bir formülün olumsuz normal formda olduğu söylenir ve klasik mantığın her C formülünün olumsuzluk normal formunda mantıksal olarak eşdeğer bir C ' formülüne sahip olduğunu resmi olarak kanıtlamak mümkündür . Olduğunu, C ancak ve ancak karşılanabilir olduğunu 'C karşılanabilir olduğunu.

Birinci dereceden mantık tablosu

Tableaux, sırasıyla evrensel ve varoluşsal niceleyicilerle ilgilenmek için iki kural ile birinci dereceden yüklem mantığına genişletilir. İki farklı kural kümesi kullanılabilir; her ikisi de varoluşsal niceleyicileri işlemek için bir Skolemization biçimi kullanır , ancak evrensel niceleyicilerin işlenmesi konusunda farklılık gösterir.

Geçerliliğini kontrol etmek için formül setinin burada hiçbir serbest değişken içermediği varsayılmaktadır; Serbest değişkenler dolaylı olarak evrensel olarak ölçüldüğünden bu bir sınırlama değildir, bu nedenle bu değişkenler üzerine evrensel niceleyiciler eklenebilir ve sonuçta serbest değişken içermeyen bir formül elde edilir.

Birleştirme olmadan birinci dereceden tablo

Bir birinci dereceden, formül tüm formülleri ifade eder a, toprak terimi . Bu nedenle aşağıdaki çıkarım kuralı doğrudur: ${\ displaystyle \ forall x. \ gamma (x)}$${\ displaystyle \ gama (t)}$${\ displaystyle t}$

${\ displaystyle (\ forall) {\ frac {\ forall x. \ gamma (x)} {\ gamma (t)}}}$ keyfi bir temel terim nerede ${\ displaystyle t}$

Önerme bağlaçlarına ilişkin kuralların aksine, bu kuralın aynı formüle birden fazla uygulaması gerekli olabilir. Örnek olarak, setin tatmin edici olmadığı, ancak her ikisi de ve ondan üretilirse kanıtlanabilir . ${\ displaystyle \ {\ neg P (a) \ vee \ neg P (b), \ forall xP (x) \}}$${\ displaystyle P (a)}$${\ displaystyle P (b)}$${\ displaystyle \ forall xP (x)}$

Varoluşsal niceleyiciler Skolemization aracılığıyla ele alınır. Özel olarak, böyle bir lider varoluş nicelik bir formül olan Skolemization oluşturur , yeni sabit bir semboldür. ${\ displaystyle \ var x. \ delta (x)}$${\ displaystyle \ delta (c)}$${\ displaystyle c}$

${\ displaystyle (\ var) {\ frac {\ var x. \ delta (x)} {\ delta (c)}}}$ yeni sabit sembol nerede ${\ displaystyle c}$

{∀xP (x), ∃x. (¬P (x) ⋁¬P (f (x)))} için birleştirilmemiş bir tablo. Anlaşılır olması için, formüller solda numaralandırılmıştır ve her adımda kullanılan formül ve kural sağdadır.

Skolem terimi bir sabittir (arity 0'ın bir fonksiyonu) çünkü aşırı niceleme herhangi bir evrensel niceleyici kapsamında gerçekleşmez. Orijinal formül bazı evrensel niceleyiciler içeriyorsa , bu şekilde niceleme, kendi kapsamları dahilindeyse, bu niceleyiciler, evrensel niceleyiciler için kuralın uygulanmasıyla açıkça kaldırılmıştır. ${\ displaystyle c}$${\ displaystyle x}$${\ displaystyle x}$

Varoluşsal niceleyiciler kuralı, yeni sabit semboller getirir. Bu semboller, evrensel nicelik belirteçleri kuralı tarafından kullanılabilir, böylece orijinal formülde olmasa bile üretilebilir , ancak varoluşsal niceleyiciler için kural tarafından oluşturulan bir Skolem sabitidir. ${\ displaystyle \ forall y. \ gamma (y)}$${\ displaystyle \ gama (c)}$${\ displaystyle c}$

Evrensel ve varoluşsal niceleyiciler için yukarıdaki iki kural ve önermesel kurallar da doğrudur: bir formül kümesi kapalı bir tablo oluşturuyorsa, bu küme tatmin edici değildir. Tamlık da ispatlanabilir: Eğer bir dizi formül tatmin edici değilse, ondan bu kurallara göre inşa edilmiş kapalı bir tablo vardır. Bununla birlikte, gerçekte böyle kapalı bir tablonun bulunması, kuralların uygun bir uygulama politikasını gerektirir. Aksi takdirde, tatmin edici olmayan bir küme, sonsuz büyüyen bir tablo oluşturabilir. Bir örnek olarak, küme tatmin edici değildir, ancak bir kişi örneğin evrensel niceleyiciler için kuralı akılsızca uygulamaya devam ederse, kapalı bir tablo asla elde edilemez . Kapalı bir tablo her zaman bu ve benzeri "adaletsiz" tablo kuralları uygulama politikaları dışlanarak bulunabilir. ${\ displaystyle \ {\ neg P (f (c)), \ forall xP (x) \}}$${\ displaystyle \ forall xP (x)}$${\ Displaystyle P (c), P (f (c)), P (f (f (c))), \ ldots}$

Evrensel niceleyiciler için kural, belirleyici olmayan tek kuraldır, çünkü hangi terimin somutlaştırılacağını belirtmez. Ayrıca, diğer kuralların her formül ve formülün bulunduğu her yol için yalnızca bir kez uygulanması gerekirken, bu, birden fazla uygulama gerektirebilir. Ancak bu kuralın uygulanması, başka hiçbir kural uygulanmayana kadar kuralın uygulanmasını geciktirerek ve kuralın uygulanmasını tablonun yolunda zaten görünen temel terimlerle sınırlandırarak sınırlandırılabilir. Aşağıda gösterilen birleşik tablo türü varyantı, determinizm sorununu çözmeyi amaçlamaktadır. ${\ displaystyle (\ forall)}$

Birleştirme ile birinci dereceden tablo

Birleştirme olmaksızın tablonun temel sorunu , evrensel niceliksel kuralı için bir temel terimin nasıl seçileceğidir . Aslında, mümkün olan her temel terim kullanılabilir, ancak bunların çoğu tabloyu kapatmak için yararsız olabilir. ${\ displaystyle t}$

Bu soruna bir çözüm, terimin seçimini, kuralın sonucu tablonun en azından bir dalının kapatılmasına izin verdiği zamana "geciktirmektir". Bu, bir terim yerine bir değişken kullanılarak yapılabilir, böylece oluşturulur ve ardından ikamelerin daha sonra bir terimle değiştirilmesine izin verilir . Evrensel niceleyiciler için kural şu ​​şekildedir: ${\ displaystyle \ forall x. \ gamma (x)}$${\ displaystyle \ gama (x ')}$${\ displaystyle x '}$

${\ displaystyle (\ forall) {\ frac {\ forall x. \ gamma (x)} {\ gamma (x ')}}}$ Tablonun her yerinde olmayan bir değişken nerede ${\ displaystyle x '}$

İlk formül setinin serbest değişkenler içermemesi beklenirken, tablonun bir formülü bu kural tarafından üretilen serbest değişkenleri içerir. Bu serbest değişkenler örtük olarak evrensel olarak nicelendirilmiş olarak kabul edilir.

Bu kural, temel terim yerine bir değişken kullanır. Bu değişikliğin kazancı, tablonun bir dalı kapatılabildiğinde bu değişkenlere bir değer verilebilmesidir, bu da işe yaramaz olabilecek terimler üretme problemini çözer.

${\ displaystyle (\ sigma)}$

Eğer iki sabitinden en genel birleştiricidir; ve , ve reddi tablosunun aynı dalda meydana tablosunun tüm formüllerde aynı anda uygulanabilir ${\ displaystyle \ sigma}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle \ sigma}$

Örnek olarak, ilk üretme ile tatmin edilemez olduğu kanıtlanabilir ; bu değişmezin olumsuzlanması , en genel birleştirici ile ikame edilen ikame ile birleştirilemez ; değiştirilmesi bu ikame sonuçları uygulamak ile tablosunu kapatır. ${\ displaystyle \ {\ neg P (a), \ forall xP (x) \}}$${\ displaystyle P (x_ {1})}$${\ displaystyle \ neg P (a)}$${\ displaystyle x_ {1}}$${\ displaystyle a}$${\ displaystyle P (x_ {1})}$${\ displaystyle P (a)}$

Bu kural, tablonun en azından bir dalını kapatır - dikkate alınan değişmez çiftleri içeren. Bununla birlikte, ikame sadece bu iki değişmeze değil, tüm tabloya uygulanmalıdır. Bu, tablonun serbest değişkenlerinin katı olduğu söylenerek ifade edilir : eğer bir değişkenin bir oluşumu başka bir şeyle değiştirilirse, aynı değişkenin diğer tüm oluşumlarının aynı şekilde değiştirilmesi gerekir. Resmi olarak, serbest değişkenler (örtük olarak) evrensel olarak ölçülür ve tablonun tüm formülleri bu niceleyicilerin kapsamındadır.

Varoluşsal niceleyiciler Skolemization tarafından ele alınır. Birleştirmesiz tablonun aksine, Skolem terimleri basit sabit olmayabilir. Gerçekte, birleştirilmiş bir tablodaki formüller, evrensel olarak niceliksel olarak kabul edilen örtük olarak kabul edilen serbest değişkenler içerebilir. Sonuç olarak, benzer bir formül evrensel niceleyiciler kapsamında olabilir; bu durumda, Skolem terimi basit bir sabit değil, yeni bir fonksiyon sembolü ve formülün serbest değişkenlerinden oluşan bir terimdir. ${\ displaystyle \ var x. \ delta (x)}$

${\ displaystyle (\ var) {\ frac {\ var x. \ delta (x)} {\ delta (f (x_ {1}, \ ldots, x_ {n}))}}}$ nerede yeni bir fonksiyon sembolü ve serbest değişkenler ${\ displaystyle f}$${\ displaystyle x_ {1}, \ ldots, x_ {n}}$${\ displaystyle \ delta}$

{∀xP (x), ∃x. (¬P (x) ⋁¬P (f (x)))} için birleştirilmiş birinci dereceden bir tablo. Anlaşılır olması için, formüller solda numaralandırılmıştır ve her adımda kullanılan formül ve kural sağdadır.

Bu kural , tek başına değil, dalın serbest değişkenlerinin olduğu bir kural üzerinde bir basitleştirme içerir . Bu kural, değişken yeniden adlandırma ile aynı olan bir formülde zaten kullanılmışsa, bir işlev sembolünün yeniden kullanılmasıyla daha da basitleştirilebilir . ${\ displaystyle x_ {1}, \ ldots, x_ {n}}$${\ displaystyle \ delta}$${\ displaystyle \ delta}$

Bir tablo ile temsil edilen formül, serbest değişkenlerin evrensel olarak nicelendirilmiş olarak kabul edildiği ek varsayımla birlikte, önermesel duruma benzer bir şekilde elde edilir. Önerme durumuna gelince, her daldaki formüller birleştirilir ve ortaya çıkan formüller birleştirilir. Ek olarak, elde edilen formülün tüm serbest değişkenleri evrensel olarak ölçülür. Tüm bu niceleyiciler, kapsamlarında tam formüle sahiptir. Başka bir deyişle, formül her daldaki formüllerin birleşiminin ayrılmasıyla elde edilen formül ve içindeki serbest değişkenler ise , tablo ile temsil edilen formüldür. Aşağıdaki hususlar geçerlidir: ${\ displaystyle F}$${\ displaystyle x_ {1}, \ ldots, x_ {n}}$${\ displaystyle \ forall x_ {1}, \ ldots, x_ {n} .F}$

• Beri: ücretsiz değişkenler evrensel sayısal olduğu varsayımı ses kural birleştiricidir bir en genel uygulanmasını kılan araçlar olası her değer için doğrudur , sonra dönem için geçerlidir , en genel bir birleştiricidir cümledeki ile. ${\ displaystyle \ gama (x ')}$${\ displaystyle \ gamma}$${\ displaystyle x '}$${\ displaystyle \ gama (t)}$${\ displaystyle t}$${\ displaystyle x}$
• Bir tablodaki serbest değişkenler katıdır: aynı değişkenin tüm oluşumlarının tümü aynı terimle değiştirilmelidir. Her değişken, henüz kararlaştırılmamış bir terimi temsil eden bir sembol olarak düşünülebilir. Bu, serbest değişkenlerin, tablonun temsil ettiği tüm formül üzerinden evrensel olarak nicelleştirildiği varsayılmasının bir sonucudur: eğer aynı değişken iki farklı düğümde serbest olarak ortaya çıkarsa, her iki oluşum da aynı niceleyicinin kapsamındadır. Bir örnek olarak, iki düğüm formüllerde ise ve burada, hem de serbest olan, Tabloda ile temsil edilen formül şeklinde bir şeydir . Bu formül, bunun herhangi bir değeri için doğru olduğunu , ancak genel olarak iki farklı terimi ifade etmediğini ve bu iki terim genel olarak farklı değerler alabileceğinden ima eder . Bu , ve içindeki iki farklı terimle değiştirilemeyeceği anlamına gelir . ${\ displaystyle A (x)}$${\ displaystyle B (x)}$${\ displaystyle x}$${\ displaystyle \ forall x. (... A (x) ... B (x) ...)}$${\ displaystyle (... A (x) ... B (x) ...)}$${\ displaystyle x}$${\ displaystyle (... A (t) ... A (t ') ...)}$${\ displaystyle t}$${\ displaystyle t '}$${\ displaystyle x}$${\ displaystyle A (x)}$${\ displaystyle B (x)}$
• Geçerliliği kontrol etmek için bir formüldeki serbest değişkenler de evrensel olarak nicelendirilmiş olarak kabul edilir. Bununla birlikte, bir tablo oluştururken bu değişkenler serbest bırakılamaz, çünkü tablo kuralları formülün tersi üzerinde çalışır, ancak yine de serbest değişkenleri evrensel olarak ölçülmüş olarak ele alır. Örneğin, geçerli değildir (nerede modelinde ve nerede yorumunda doğru değildir ). Sonuç olarak tatmin edicidir (aynı model ve yorumla tatmin edilir). Bununla birlikte, kapalı bir tablo ile oluşturulmuş olabilir ve ve ikame ile bir kapatma oluşturmak. Doğru bir prosedür, ilk önce evrensel niceleyicileri açık hale getirmek, böylece üretmektir . ${\ displaystyle P (x) \ sağ P (c)}$${\ displaystyle D = \ {1,2 \}, P (1) = \ bot, P (2) = \ top, c = 1}$${\ displaystyle x = 2}$${\ displaystyle \ {P (x), \ neg P (c) \}}$${\ displaystyle P (x)}$${\ displaystyle \ neg P (c)}$${\ displaystyle x}$${\ displaystyle c}$${\ displaystyle \ forall x. (P (x) \ rightarrow P (c))}$

Aşağıdaki iki varyant da doğrudur.

• Tüm tabloya, tablonun serbest değişkenlerine bir ikame uygulamak, bu ikamenin tabloyu temsil eden formül için serbest olması koşuluyla, doğru bir kuraldır. Diğer dünyalarda, böyle bir ikamenin uygulanması, formülü hala girdi kümesinin bir sonucu olan bir tabloya götürür. Çoğu genel birleştiricinin kullanılması, tablo için serbestlik koşulunun otomatik olarak karşılanmasını sağlar.
• Genel olarak tüm tabloda her değişkenin aynı terimle değiştirilmesi gerekmekle birlikte, bunun gerekli olmadığı bazı özel durumlar vardır.

Birleştirmeye sahip tabloların eksiksiz olduğu kanıtlanabilir: eğer bir dizi formül tatmin edici değilse, birleştirme ile bir tabloya sahiptir. Ancak aslında böyle bir kanıtı bulmak zor bir problem olabilir. Birleştirmesiz durumun aksine, bir ikame uygulamak bir tablonun mevcut bölümünü değiştirebilir; bir ikame uygulamak en az bir dalı kapatırken, diğer şubelerin kapatılmasını imkansız hale getirebilir (set tatmin edici olmasa bile).

Bu soruna bir çözüm, gecikmiş somutlaştırmadır : tüm dalları aynı anda kapatan bir tane bulunana kadar hiçbir ikame uygulanmaz. Bu varyantla, tatmin edici olmayan bir küme için bir kanıt, her zaman diğer kuralların uygun bir uygulama politikası ile bulunabilir. Ancak bu yöntem, tüm tablonun bellekte tutulmasını gerektirir: genel yöntem, daha sonra atılabilen dalları kapatır, bu varyant ise sonuna kadar herhangi bir dalı kapatmaz.

Oluşturulabilen bazı tabloların, küme tatmin edici olmasa bile kapatılmasının imkansız olması sorunu, diğer tablo genişletme kuralları kümelerinde ortaktır: bu kuralların bazı belirli uygulama dizileri kapalı bir tablo oluşturmaya izin verse bile (eğer küme tatmin edici değilse ), diğer bazı diziler kapatılamayan tablolara yol açar. Bu durumlar için genel çözümler "Tablo arama" bölümünde özetlenmiştir.

Tableau calculi ve özellikleri

Tablo hesabı, bir tablonun oluşturulmasına ve değiştirilmesine izin veren bir dizi kuraldır. Önerme tablosu kuralları, birleştirme olmadan tablo kuralları ve birleştirme ile tablo kuralları, tablo hesaplarıdır. Bir tablo analizinin sahip olabileceği ya da olmayabileceği bazı önemli özellikler, bütünlük, yıkıcılık ve kanıt birleşimidir.

Verilen her tatmin edilemez formül kümesi için bir tablo kanıtı oluşturmaya izin veriyorsa, bir tablo hesabı tam olarak adlandırılır. Yukarıda bahsedilen tablo taşları tam olarak ispatlanabilir.

Birleştirmeli tablo ile diğer iki kalkül arasındaki dikkate değer bir fark, son iki kalkülün bir tabloyu sadece yeni düğümler ekleyerek değiştirmesi, birincisi ise ikamelerin tablonun mevcut bölümünü değiştirmesine izin vermesidir. Daha genel olarak, tablo taşları, tabloya yalnızca yeni düğümler ekleyip eklememelerine bağlı olarak yıkıcı veya tahribatsız olarak sınıflandırılır . Bu nedenle, birleşme ile Tablo yıkıcıdır, oysa önermesel tablo ve birleşme olmaksızın tablo yıkıcı değildir.

İspat izdiham, bu tablonun analizin kurallarını uygulayarak elde edildiğini varsayarak, keyfi bir tablodan keyfi olarak tatmin edilemeyen bir küme için bir kanıt elde etmek için bir çizelge hesabının özelliğidir. Başka bir deyişle, bir ispat birleşik tablo hesaplamasında, tatmin edilemez bir kümeden, kişi her türlü kural setini uygulayabilir ve yine de başka bazı kurallar uygulayarak kapalı bir tablonun elde edilebileceği bir tablo elde edebilir.

İspat prosedürleri

Bir tablo hesabı, bir tablonun nasıl değiştirilebileceğini söyleyen bir kurallar dizisidir. İspat prosedürü, gerçekten bir ispat bulma yöntemidir (eğer varsa). Başka bir deyişle, bir tablo hesabı bir kurallar dizisidir, oysa ispat prosedürü bu kuralların uygulanmasının bir politikasıdır. Bir analiz tamamlanmış olsa bile, kuralların olası her uygulama seçimi, tatmin edici olmayan bir kümenin ispatına yol açmaz. Örneğin , tatmin edici değildir, ancak hem birleştirmeli tablolar hem de birleştirmesiz tablolar, evrensel niceleyiciler kuralının son formüle tekrar tekrar uygulanmasına izin verirken, üçüncü olana ayrılma kuralını basitçe uygulamak, doğrudan kapanmaya yol açacaktır. ${\ Displaystyle \ {P (f (c)), R (c), \ neg P (f (c)) \ vee \ neg R (c), \ forall xQ (x) \}}$

İspat prosedürleri için bir tamlık tanımı verilmiştir: herhangi bir tatmin edici olmayan formül seti için kapalı bir tablo bulmaya izin veriyorsa, bir ispat prosedürü kesinlikle tamamlanmıştır. Altta yatan analizin kanıt birleşikliği, tamlık ile ilgilidir: kanıt birleşikliği, kapalı bir tablonun her zaman keyfi kısmen oluşturulmuş bir tablodan (eğer küme tatmin edici değilse) oluşturulabileceğinin garantisidir. Kanıt birleşmesi olmadan, 'yanlış' bir kuralın uygulanması, diğer kuralları uygulayarak tablonun tamamlanmasının imkansızlığı ile sonuçlanabilir.

Önermeli tablolar ve birleştirilmemiş tablolar, güçlü bir şekilde eksiksiz ispat prosedürlerine sahiptir. Özellikle, eksiksiz bir kanıt prosedürü, kuralları adil bir şekilde uygulamaktır. Bunun nedeni, böyle bir hesaplamanın tatmin edilemez bir kümeden kapalı bir tablo üretememesinin tek yolunun, bazı uygulanabilir kuralları uygulamamaktır.

Önerme tablosu için adalet, her formülü her dalda genişletmek anlamına gelir. Daha doğrusu, her formül ve formülün içinde bulunduğu her dal için, dalı genişletmek için formülü ön koşul olarak alma kuralı kullanılmıştır. Önerme tablosu için adil bir ispat prosedürü tamamen tamamlanmıştır.

Birleştirmesiz birinci dereceden tablolar için, evrensel niceliksel kuralın birden fazla uygulama gerektirmesi dışında, adalet koşulu benzerdir. Adalet, her evrensel niceleyiciyi sonsuz sıklıkta genişletmek anlamına gelir. Başka bir deyişle, kuralların adil bir şekilde uygulanması politikası, arada bir hala açık olan her dalda her evrensel niceleyiciyi genişletmeden diğer kuralları uygulamaya devam edemez.

Kapalı bir tablonun aranması

Bir tablo hesabı tamamlanmışsa, tatmin edici olmayan her formül kümesinin ilişkili bir kapalı tablo vardır. Bu tablo her zaman analizin bazı kurallarının uygulanmasıyla elde edilebilirken, belirli bir formül için hangi kuralların uygulanacağı sorunu hala devam etmektedir. Sonuç olarak, tamlık otomatik olarak her verili tatmin edilemez formül kümesi için kapalı bir tabloya yol açan uygulanabilir bir kural uygulama politikasının varlığını ima etmez. Birleştirme olmaksızın zemin tablosu ve tablo için adil bir ispat prosedürü tamamlanırken, bu birleşme tablosu için durum böyle değildir.

{∀xP (x), ¬P (c) ⋁¬Q (c), ∃yQ (c)} için tablo uzayında bir arama ağacı. Basit olması için, setin formülleri şekildeki tüm tablodan çıkarılmış ve bunların yerine bir dikdörtgen kullanılmıştır. Kalın kutuda kapalı bir tablo vardır; diğer dallar hala genişletilebilir.

Bu problem için genel bir çözüm, kapalı bir tane bulunana kadar (eğer varsa, yani küme tatmin edici değildir) tablo uzayını aramaktır. Bu yaklaşımda, kişi boş bir tabloyla başlar ve ardından her olası uygulanabilir kuralı özyinelemeli olarak uygular. Bu prosedür, düğümleri tableaux ile etiketlenmiş bir (örtük) ağacı ziyaret eder ve öyle ki bir düğümdeki tablo, geçerli kurallardan biri uygulanarak üstündeki tablodan elde edilir.

Her dal sonsuz olabileceğinden, bu ağacın derinlikten önce enine ziyaret edilmesi gerekir. Ağacın genişliği katlanarak büyüyebileceği için bu büyük miktarda alan gerektirir. Bazı düğümleri birden fazla ziyaret edebilen ancak polinom uzayda işe yarayan bir yöntem, önce derinlemesine bir şekilde yinelemeli derinleştirme ile ziyaret etmektir: biri önce ağacı belirli bir derinliğe kadar ziyaret eder, ardından derinliği artırır ve ziyareti tekrar gerçekleştirir. Bu özel prosedür, her adımda ne zaman duracağına karar vermek için derinliği (aynı zamanda uygulanan tablo kurallarının sayısıdır) kullanır. Bunun yerine çeşitli başka parametreler (bir düğümü etiketleyen tablonun boyutu gibi) kullanılmıştır.

Aramayı azaltmak

Arama ağacının boyutu, belirli bir (ebeveyn) olandan üretilebilecek (çocuk) tabloların sayısına bağlıdır. Bu tür tabloların sayısının azaltılması bu nedenle gerekli aramayı azaltır.

Bu sayıyı azaltmanın bir yolu, iç yapılarına bağlı olarak bazı tabloların oluşumuna izin vermektir. Bir örnek, düzenlilik koşuludur: Bir dal bir değişmez bilgi içeriyorsa, aynı değişmezi üreten bir genişletme kuralını kullanmak işe yaramaz çünkü değişmez değerlerin iki kopyasını içeren dal, orijinalin aynı formül kümesine sahip olacaktır. Bu genişletmeye izin verilmeyebilir, çünkü kapalı bir tablo varsa, o olmadan da bulunabilir. Bu kısıtlama yapısaldır çünkü sadece genişletmek için tablonun yapısına bakılarak kontrol edilebilir.

Aramayı azaltmak için farklı yöntemler, kapalı bir tablonun diğerlerini genişleterek hala bulunabileceği gerekçesiyle bazı tabloların oluşturulmasına izin vermez. Bu kısıtlamalara global denir. Küresel kısıtlamaya bir örnek olarak, açık dallardan hangisinin genişletileceğini belirten bir kural kullanılabilir. Sonuç olarak, eğer bir tablonun örneğin iki kapalı olmayan dalı varsa, kural hangisinin genişletileceğini söyleyerek ikincisinin genişlemesine izin vermez. Bu kısıtlama arama alanını azaltır çünkü olası bir seçim artık yasaklanmıştır; Bununla birlikte, bütünlük zarar görmez, çünkü ilk dal sonunda kapatılırsa ikinci dal yine de genişleyecektir. Bir örnek olarak, bir kök ile tablo , çocuk ve iki yaprak ve iki yolla kapatılabilir: uygulanması ilk ve daha sonra tam tersi ya da tersine. Açıkça her iki olasılığı da takip etmeye gerek yoktur; sadece ilk başvurulan dava dikkate alınabilir ve ilk başvurulduğu dava göz ardı edilebilir . Bu küresel bir kısıtlamadır, çünkü bu ikinci genişlemeyi ihmal etmeye izin veren şey, genişlemenin önce ve sonra uygulandığı diğer tablonun varlığıdır . ${\ displaystyle \ neg a \ kama \ neg b}$${\ displaystyle a \ vee b}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle (\ kama)}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle (\ kama)}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle a}$${\ displaystyle b}$

Yan tümce tableaux

Cümleler kümelerine uygulandığında (keyfi formüllerden ziyade), tableaux yöntemleri bir dizi verimlilik iyileştirmesine izin verir. Birinci dereceden bir cümle, serbest değişkenler içermeyen ve her biri bir değişmez olacak şekilde bir formüldür . Evrensel nicelik belirteçleri genellikle açıklık için ihmal edilir, bu nedenle örneğin aslında anlamına gelir . Kelimenin tam anlamıyla alındığında, bu iki formülün tatmin edilebilirlik ile aynı olmadığını unutmayın: daha ziyade, tatmin edilebilirlik ile aynıdır . Serbest değişkenlerin evrensel olarak nicelleştirilmesi, birinci dereceden tatmin edilebilirlik tanımının bir sonucu değildir; daha çok cümleciklerle uğraşırken örtük bir ortak varsayım olarak kullanılır. ${\ displaystyle \ forall x_ {1}, \ ldots, x_ {n} L_ {1} \ vee \ cdots \ vee L_ {m}}$${\ displaystyle L_ {i}}$${\ displaystyle P (x, y) \ vee Q (f (x))}$${\ displaystyle \ forall x, yP (x, y) \ vee Q (f (x))}$${\ displaystyle P (x, y) \ vee Q (f (x))}$${\ Displaystyle \ vardır x, yP (x, y) \ vee Q (f (x))}$

Bir cümle için geçerli olan tek genişletme kuralları şunlardır: ve ; bu iki kural, bütünlüklerini kaybetmeden kombinasyonları ile değiştirilebilir. Özellikle, aşağıdaki kural, kuralları ve birinci dereceden analizin birleştirme ile sırayla uygulanmasına karşılık gelir . ${\ displaystyle (\ forall)}$${\ displaystyle (\ vee)}$${\ displaystyle (\ forall)}$${\ displaystyle (\ vee)}$

${\ displaystyle (C) {\ frac {L_ {1} \ vee \ cdots \ vee L_ {n}} {L_ {1} '| \ cdots | L_ {n}'}}}$ burada yeni bir tane her değişken değiştirilmesi ile elde edilir ${\ displaystyle L_ {1} '\ vee \ cdots \ vee L_ {n}'}$${\ displaystyle L_ {1} \ vee \ cdots \ vee L_ {n}}$

Tatmin edilebilirlik için kontrol edilecek küme sadece maddelerden oluştuğunda, bu ve birleştirme kuralları yetersizliği ispatlamak için yeterlidir. Diğer dünyalarda, tableau calculi oluşur ve tamamlanmıştır. ${\ displaystyle (C)}$${\ displaystyle (\ sigma)}$

Yan tümce genişletme kuralı yalnızca değişmez değerler ürettiğinden ve hiçbir zaman yeni yan tümceleri oluşturmadığından, uygulanabileceği tümceler girdi kümesinin yalnızca tümceleridir. Sonuç olarak, yan tümce genişletme kuralı, yan tümcenin girdi kümesinde olduğu durumla daha da sınırlandırılabilir.

${\ displaystyle (C) {\ frac {L_ {1} \ vee \ cdots \ vee L_ {n}} {L_ {1} '| \ cdots | L_ {n}'}}}$ burada bir yenisi ile her değişken değiştirilmesi ile elde edilir , giriş kümesinin bir madde olduğu, ${\ displaystyle L_ {1} '\ vee \ cdots \ vee L_ {n}'}$${\ displaystyle L_ {1} \ vee \ cdots \ vee L_ {n}}$

Bu kural, girdi kümesindeki tümcecikleri doğrudan kullandığından, tabloyu girdi yan tümceleri zincirine ilklendirmeye gerek yoktur. İlk tablo bu nedenle tek düğüm etiketli olarak başlatılabilir ; bu etiket genellikle örtük olarak çıkarılır. Bu daha fazla basitleştirmenin bir sonucu olarak, tablonun her düğümü (kök dışında) bir literal ile etiketlenir. ${\ displaystyle true}$

Madde tablosu için bir dizi optimizasyon kullanılabilir. Bu optimizasyon, yukarıdaki "Kapalı bir tablonun aranması" bölümünde açıklandığı gibi kapalı bir tablo ararken keşfedilecek olası tabloların sayısını azaltmayı amaçlamaktadır.

Bağlantı tablosu

Bağlantı, zaten dalda bulunan değişmez değerlerle ilgisi olmayan yan tümceleri kullanarak bir dalı genişletmeyi yasaklayan tablo üzerinde bir koşuldur. Bağlantı iki şekilde tanımlanabilir:

güçlü bağlılık

bir dalı genişletirken, yalnızca geçerli yapraktaki değişmez bilginin olumsuzlanmasıyla birleştirilebilecek bir değişmez değer içeriyorsa bir girdi cümlesini kullanın

zayıf bağlılık

dalda bir değişmezin olumsuzlamasıyla bütünleşen bir değişmezi içeren cümleciklerin kullanımına izin verin

Her iki koşul da yalnızca kökten ibaret olmayan dallar için geçerlidir. İkinci tanım, daldaki bir değişmezin olumsuzlamasıyla birleşen bir değişmezi içeren bir cümlenin kullanımına izin verirken, ilk yalnızca bu değişmezin mevcut dalın yaprağında olması için ek kısıtlama sağlar.

Madde genişletme bağlılık ile sınırlandırılmışsa (güçlü veya zayıf), uygulaması, ikamenin yeni yapraklardan birine uygulanabileceği ve dalını kapattığı bir tablo oluşturur. Özellikle, bu, daldaki bir değişmezin olumsuzlamasıyla (veya güçlü bağlantı durumunda ebeveyndeki değişmezin olumsuzlamasıyla) birleşen cümlenin değişmezini içeren yapraktır.

Her iki bağlılık koşulu da tam bir birinci dereceden hesaplamaya yol açar: eğer bir dizi cümle tatmin edilemezse, kapalı bir bağlantılı (güçlü veya zayıf) bir tabloya sahiptir. Bu tür kapalı bir tablo, "Kapalı bir tablonun aranması" bölümünde açıklandığı gibi, tablo uzayında arama yapılarak bulunabilir. Bu arama sırasında, bağlılık olası bazı genişletme seçeneklerini ortadan kaldırır ve böylece aramayı azaltır. Diğer dünyalarda, ağacın bir düğümündeki tablo genel olarak birkaç farklı şekilde genişletilebilirken, bağlantı bunlardan yalnızca birkaçına izin verebilir, böylece daha fazla genişletilmesi gereken sonuçta ortaya çıkan tablo sayısını azaltabilir.

Bu, aşağıdaki (önerme) örnekte görülebilir. Cümleler kümesi için bir zincirden yapılan tablo genel olarak dört giriş cümlesinin her biri kullanılarak genişletilebilir, ancak bağlantı yalnızca kullanan genişletmeye izin verir . Bu, tableaux ağacının genel olarak dört yaprağı olduğu, ancak bağlantılılık empoze edilirse yalnızca bir yaprağı olduğu anlamına gelir. Bu, bağlantılılığın genel olarak dikkate alınması gereken dört tablo yerine genişletmeye çalışmak için yalnızca bir tablo bıraktığı anlamına gelir. Seçimlerdeki bu azalmaya rağmen, tamlık teoremi, küme tatmin edici değilse kapalı bir tablonun bulunabileceğini ima eder. ${\ displaystyle true-a}$${\ displaystyle \ {a, \ neg a \ vee b, \ neg c \ vee d, \ neg b \}}$${\ displaystyle \ neg a \ vee b}$

Önermesel (cümle) durumuna uygulandığında bağlantılılık koşulları, sonuçta ortaya çıkan hesabı birbirine karışmaz hale getirir. Bir örnek olarak, edilemezdir, ama uygulama için zincir oluşturur kapalı değildir ve hangi başka bir genişleme kural ya kuvvetli ya da zayıf bağlantılılık zarar vermeden uygulanabilir. Zayıf bağlılık durumunda, kökü genişletmek için kullanılan cümlenin tatmin edici olmama ile ilgili olması, yani cümle kümesinin minimal olarak tatmin edilemez bir alt kümesinde yer alması koşuluyla, izdiham geçerli olur. Ne yazık ki, bir cümlenin bu koşulu karşılayıp karşılamadığını kontrol etme sorunu başlı başına zor bir sorundur. Birleşme olmamasına rağmen, yukarıdaki "Kapalı bir tablonun aranması" bölümünde sunulduğu gibi, arama kullanılarak kapalı bir tablo bulunabilir. Arama gerekli hale getirilirken, bağlılık olası genişleme seçeneklerini azaltır ve böylece aramayı daha verimli hale getirir. ${\ displaystyle \ {a, b, \ neg b \}}$${\ displaystyle (C)}$${\ displaystyle a}$${\ displaystyle true-a}$

Düzenli tablolar

Aynı dalda iki kez değişmez bilgi yoksa bir tablo düzenlidir. Düzenli olmayan bir tablo oluşturacak tümceler genişletilemeyeceğinden, bu koşulun zorlanması olası tablo genişletme seçeneklerinde bir azalmaya izin verir.

Ancak bu izin verilmeyen genişletme adımları işe yaramaz. Eğer bir değişmezi içeren bir dalıdır ve kimin genişleme düzenlilik ihlal eden bir fıkra, sonra içerir . Şube, diğerleri arasında, yakın genişletmek için bir ihtiyacı tablosunu kapatmak ve amacıyla , iki kez yaşanır. Ancak bu daldaki formüller tek başına formüller ile birebir aynıdır . Sonuç olarak, kapanan aynı genişletme adımları da kapanır . Bu, genişletmenin gereksiz olduğu anlamına gelir ; dahası, başka değişmezler içeriyorsa, genişlemesi kapatılması gereken başka yapraklar oluşturdu. Önerme durumunda, bu yaprakları kapatmak için gereken genişletme tamamen işe yaramaz; birinci dereceden durumda, bazı birleşmeler nedeniyle tablonun yalnızca geri kalanını etkileyebilirler; ancak bunlar tablonun geri kalanını kapatmak için kullanılan ikamelerle birleştirilebilir. ${\ displaystyle B}$${\ displaystyle L}$${\ displaystyle C}$${\ displaystyle C}$${\ displaystyle L}$${\ displaystyle BL}$${\ displaystyle L}$${\ displaystyle B}$${\ displaystyle BL}$${\ displaystyle B}$${\ displaystyle C}$${\ displaystyle C}$

Modal mantık için Tableaux

Bir olarak lojik bir model kümesini içermektedir olası dünyalar , bir doğruluk değerlendirme bağlantılı her biri; Bir erişilebilirlik ilişki bir dünya olduğu zaman söyler erişilebilir başka birinden. Modal bir formül, yalnızca olası bir dünya üzerindeki koşulları değil, aynı zamanda ondan erişilebilenleri de belirtebilir. Örnek olarak, erişilebilen tüm dünyalarda doğruysa, bir dünyada doğrudur. ${\ displaystyle \ Box A}$${\ displaystyle A}$

Önerme mantığına gelince, modal mantık için tablolar, formülleri özyinelemeli olarak temel bileşenlerine ayırmaya dayanır. Bununla birlikte, modal bir formülü genişletmek, farklı dünyalar üzerinde koşulların belirtilmesini gerektirebilir. Örnek olarak, eğer bir dünyada doğruysa, o zaman ondan erişilebilen ve yanlış olan bir dünya vardır . Bununla birlikte, aşağıdaki kuralı önerme kurallarına basitçe ekleyemezsiniz. ${\ displaystyle \ neg \ Kutu A}$${\ displaystyle A}$

${\ displaystyle {\ frac {\ neg \ Box A} {\ neg A}}}$

Önerme tablosunda tüm formüller aynı hakikat değerlendirmesine atıfta bulunur, ancak yukarıdaki kuralın önkoşulu, sonuç başka bir dünyada geçerliyken bir dünyada geçerlidir. Bunun hesaba katılmaması yanlış sonuçlar doğuracaktır. Örneğin, formül devletler o anki dünyada doğrudur ve ondan erişilebilen bir dünyada yanlıştır. Basitçe uygulamak ve yukarıdaki genişletme kuralı ve üretir , ancak bu iki formül, farklı dünyalarda olduğu gibi genel olarak bir çelişki oluşturmamalıdır. Modal tableaux calculi, yukarıdaki gibi kurallar içerir, ancak farklı dünyalara atıfta bulunan formüllerin yanlış etkileşiminden kaçınmak için mekanizmalar içerir. ${\ displaystyle a \ wedge \ neg \ Box a}$${\ displaystyle a}$${\ displaystyle a}$${\ displaystyle (\ kama)}$${\ displaystyle a}$${\ displaystyle \ neg a}$

Teknik olarak, modal mantık tabloları, bir dizi formülün tatmin edilebilirliğini kontrol eder: Kümedeki formüllerin bu model ve dünyada doğru olmasını sağlayacak bir model ve dünya olup olmadığını kontrol ederler . İse, yukarıdaki örnekte durumların gerçek olarak , formül gerçekliğini bildiren bazı dünyanın erişilebilen ve genel farklı olabilen . Modal mantık için Tableaux calculi, formüllerin farklı dünyalara atıfta bulunabileceğini hesaba katar. ${\ displaystyle M}$${\ displaystyle w}$${\ displaystyle a}$${\ displaystyle a}$${\ displaystyle w}$${\ displaystyle \ neg \ Box a}$${\ displaystyle \ neg a}$${\ displaystyle w '}$${\ displaystyle w}$${\ displaystyle w}$

Bu gerçeğin önemli bir sonucu vardır: Bir dünyada geçerli olan formüller, o dünyanın farklı halefleri üzerindeki koşulları ima edebilir. Tatmin edilemezlik daha sonra tek bir halefe atıfta bulunan formüllerin alt kümesinden ispatlanabilir. Bu, bir dünyanın birden fazla ardılına sahip olması durumunda geçerlidir, ki bu çoğu modal mantık için doğrudur. Durum böyleyse, muhafazaların olduğu bir halef ve muhafazaların var olduğu bir halef varsa , benzer bir formül doğrudur . Diğer taraftan, keyfi bir halefin tatmin edilemezliğini gösterebilirse , formülün tuttuğu dünyaları kontrol etmeden tatmin edilemez olduğu kanıtlanır . Aynı zamanda tatmin edilemezlik gösterilebiliyorsa , kontrol etmeye gerek yoktur . Sonuç olarak, genişletmenin iki olası yolu varken , bu iki yoldan biri, formül tatmin edici değilse, tatmin edici olmadığını kanıtlamak için her zaman yeterlidir. Örneğin, tutulan keyfi bir dünyayı düşünerek tabloyu genişletebiliriz . Bu genişleme tatmin edilemezliğe yol açarsa, orijinal formül tatmin edici değildir. Bununla birlikte, tatmin edilemezliğin bu şekilde kanıtlanamaması ve bunun yerine ambarların bulunduğu dünyanın düşünülmesi de mümkündür. Sonuç olarak, sadece ya da sadece genişleterek her zaman tatmin edilemez olduğu kanıtlanabilir ; ancak yanlış seçim yapılırsa ortaya çıkan tablo kapatılmayabilir. Her iki alt formülü genişletmek, tamamlanmış ancak kanıtla birleşik olmayan tablo hesaplarına yol açar. Bu nedenle, "Kapalı bir tablonun aranması" nda açıklandığı gibi arama yapmak gerekli olabilir. ${\ displaystyle \ neg \ Box A \ kama \ neg \ Box B}$${\ displaystyle \ neg A}$${\ displaystyle \ neg B}$${\ displaystyle \ neg A}$${\ displaystyle \ neg B}$${\ displaystyle \ neg B}$${\ displaystyle \ neg A}$${\ displaystyle \ neg \ Box A \ kama \ neg \ Box B}$${\ displaystyle \ neg A}$${\ displaystyle \ neg B}$${\ displaystyle \ neg \ Kutu A}$${\ displaystyle \ neg \ Box B}$

Bir tablo genişletme kuralının ön koşulunun ve sonucunun aynı dünyaya atıfta bulunup bulunmadığına bağlı olarak, kurala statik veya işlemsel denir. Önerme bağlaçları için kurallar tamamen durağan olsa da, kipli bağlaçlar için tüm kurallar işlemsel değildir: örneğin, aksiyom T dahil her kip mantığında , bunu aynı dünyada ifade eder . Sonuç olarak, göreli (modal) tablo genişletme kuralı, hem ön koşulu hem de sonucu aynı dünyaya atıfta bulunduğundan statiktir. ${\ displaystyle \ Box A}$${\ displaystyle A}$

Formül silme tablosu

Yanlış etkileşimde bulunmayan farklı dünyalara atıfta bulunan formüller yapmanın bir yolu, bir dalın tüm formüllerinin aynı dünyaya atıfta bulunduğundan emin olmaktır. Bu koşul, tutarlılık açısından kontrol edilecek kümedeki tüm formüllerin aynı dünyaya atıfta bulunduğu varsayıldığı için başlangıçta doğrudur. Bir dalı genişletirken, iki durum mümkündür: ya yeni formüller, daldaki diğeri ile aynı dünyayı ifade eder ya da etmez. İlk durumda kural normal olarak uygulanır. İkinci durumda, şubenin yeni dünyada da bulunmayan tüm formülleri şubeden silinir ve muhtemelen hala eski dünyaya göre olan diğer tüm dallara eklenir.

Bir örnek olarak, içinde S5 her formül bir dünyada doğrudur (olduğunu, tüm erişilebilir dünyalar hem tüm erişilebilir dünyalarda de geçerlidir ve doğrudur). Bu nedenle, sonucu farklı bir dünyada geçerli olan uygularken , daldaki tüm formüller silinir, ancak yeni dünyada da geçerli olduğu gibi tüm formüller saklanabilir . Tamlığı korumak için, silinen formüller daha sonra eski dünyaya atıfta bulunan diğer tüm dallara eklenir. ${\ displaystyle \ Box A}$${\ displaystyle A}$${\ displaystyle \ Box A}$${\ displaystyle {\ frac {\ neg \ Box A} {\ neg A}}}$${\ displaystyle \ Box A}$

Dünya etiketli tablo

Farklı dünyalara atıfta bulunan formüller arasında doğru etkileşimi sağlamak için farklı bir mekanizma, formüllerden etiketli formüllere geçmektir: kişi yazmak yerine, onu dünyada geçerli olduğunu açıkça göstermek için yazacaktır . ${\ displaystyle A}$${\ displaystyle w: A}$${\ displaystyle A}$${\ displaystyle w}$

Tüm önerme genişletme kuralları, hepsinin aynı dünya etiketine sahip formüllere atıfta bulunduğu belirtilerek bu varyanta uyarlanmıştır. Örneğin, ve ile etiketlenmiş iki düğüm oluşturur ; bir dal, ancak aynı dünyanın iki zıt değişmezini içeriyorsa kapanır, örneğin ve ; İki dünya etiketleri gibi, farklı ise hiçbir kapatma oluşturulur ve . ${\ displaystyle w: A \ kama B}$${\ displaystyle w: A}$${\ displaystyle w: B}$${\ displaystyle w: a}$${\ displaystyle w: \ neg a}$${\ displaystyle w: a}$${\ displaystyle w ': \ neg a}$

Modal genişleme kuralı, farklı dünyalara atıfta bulunan bir sonuca sahip olabilir. Örneğin, kuralı aşağıdaki gibi yazılır ${\ displaystyle \ neg \ Kutu A}$

${\ displaystyle {\ frac {w: \ neg \ Box A} {w ': \ neg A}}}$

Bu kuralın ön koşulu ve sonucu , sırasıyla dünyalara ve dünyalara atıfta bulunur. Çeşitli taşlar, etiket olarak kullanılan dünyaların erişilebilirliğini takip etmek için farklı yöntemler kullanır. Bazıları , erişilebildiğini belirtmek gibi sözde formüller içerir . Bazıları tamsayı dizilerini dünya etiketleri olarak kullanır; bu gösterim, erişilebilirlik ilişkisini dolaylı olarak temsil eder (örneğin, adresinden erişilebilir ). ${\ displaystyle w}$${\ displaystyle w '}$${\ displaystyle wRw '}$${\ displaystyle w '}$${\ displaystyle w}$${\ displaystyle (1,4,2,3)}$${\ displaystyle (1,4,2)}$

Set-etiketleme tablosu

Farklı dünyalardaki formüller arasındaki etkileşim sorunu, set etiketleme tabloları kullanılarak aşılabilir. Bunlar, düğümleri formül kümeleriyle etiketlenmiş ağaçlardır; genişletme kuralları, yalnızca yaprağın etiketine göre (daldaki diğer düğümlerin etiketine değil) bir yaprağa yeni düğümlerin nasıl ekleneceğini söyler.

Modal mantık için tablolar, belirli bir modal mantıkta bir dizi modal formülün karşılanabilirliğini doğrulamak için kullanılır. Formüllerin kümesi verildiğinde , bir modelin varlığını kontrol ve dünyada böyle . ${\ displaystyle S}$${\ displaystyle M}$${\ displaystyle w}$${\ displaystyle M, w \ modelleri S}$

Genişletme kuralları, kullanılan belirli mod mantığına bağlıdır. Temel modal mantık K için bir tablo sistemi , önerme tablosuna aşağıdaki kuralların eklenmesiyle elde edilebilir:

${\ displaystyle (K) {\ frac {\ Box A_ {1}; \ ldots; \ Box A_ {n}; \ neg \ Box B} {A_ {1}; \ ldots; A_ {n}; \ neg B }}}$

Sezgisel olarak, bu kuralın önkoşulu , tüm erişilebilir dünyalardaki tüm formüllerin doğruluğunu ve bazı erişilebilir dünyalardaki doğruluğunu ifade eder . Bu kuralın sonucu , doğru olduğu dünyalardan birinde doğru olması gereken bir formüldür . ${\ displaystyle A_ {1}, \ ldots, A_ {n}}$${\ displaystyle \ neg B}$${\ displaystyle \ neg B}$

Daha teknik olarak, modal tablo metotları, bir modelin ve formülleri doğru kılan bir dünyanın varlığını kontrol eder . Eğer doğruysa , erişilebilen ve bunu gerçekleştiren bir dünya olmalıdır . Bu kural, bu nedenle, bu şekilde karşılanması gereken bir dizi formül türetmek anlamına gelir . ${\ displaystyle M}$${\ displaystyle w}$${\ displaystyle \ Box A_ {1}; \ ldots; \ Box A_ {n}; \ neg \ Box B}$${\ displaystyle w}$${\ displaystyle w '}$${\ displaystyle w}$${\ displaystyle A_ {1}; \ ldots; A_ {n}; \ neg B}$${\ displaystyle w '}$

Ön koşullar tarafından yerine getirildiği varsayılırken , sonuçların aynı modelde ancak muhtemelen farklı dünyalarda karşılandığı varsayılır . Küme etiketli tablolar, her formülün doğru kabul edildiği dünyayı açıkça takip etmezler: iki düğüm aynı dünyayı ifade edebilir veya etmeyebilir. Bununla birlikte, herhangi bir düğümü etiketleyen formüllerin aynı dünyada doğru olduğu varsayılır. ${\ displaystyle \ Box A_ {1}; \ ldots; \ Box A_ {n}; \ neg \ Box B}$${\ displaystyle M, w}$${\ displaystyle A_ {1}; \ ldots; A_ {n}; \ neg B}$${\ displaystyle M, w '}$

Formüllerin doğru kabul edildiği muhtemelen farklı dünyaların bir sonucu olarak, mod kuralının her uygulaması bir dünyadan diğerine bir geçişe karşılık geldiğinden, bir düğümdeki formül tüm soyundan gelenlerde otomatik olarak geçerli olmaz. Genişletme kuralları atalarına değil, yalnızca uygulandıkları yaprağa dayandığından, bu koşul otomatik olarak set etiketleme tablosu tarafından yakalanır.

Dikkat çekici bir şekilde, aşağıdaki gibi birden çok olumsuzlanmış kutulu formülü doğrudan kapsamaz : yanlış olan ve birinin yanlış olduğu erişilebilir bir dünya varken , bu iki dünya ille de aynı olmak zorunda değildir. ${\ displaystyle (K)}$${\ displaystyle \ Box A_ {1}; \ ldots; \ Box A_ {n}; \ neg \ Box B_ {1}; \ neg \ Box B_ {2}}$${\ displaystyle B_ {1}}$${\ displaystyle B_ {2}}$

Önerme kurallarından farklı olarak, koşulları tüm ön koşullarının üzerinde belirtir. Örneğin, şu şekilde etiketlenmiş bir düğüme uygulanamaz ; bu küme tutarsız iken ve bu uygulama ile kolayca kanıtlanabilse de , bu kural tutarsızlığı bile ilgilendirmeyen formül nedeniyle uygulanamaz . Bu tür formüllerin kaldırılması şu kural ile mümkündür: ${\ displaystyle (K)}$${\ Displaystyle a; \ Kutu b; \ Kutu (b \ sağ c); \ neg \ Kutu c}$${\ displaystyle (K)}$${\ displaystyle a}$

${\ displaystyle (\ theta) {\ frac {A_ {1}; \ ldots; A_ {n}; B_ {1}; \ ldots; B_ {m}} {A_ {1}; \ ldots; A_ {n} }}}$

Bu kuralın eklenmesi (inceltme kuralı), sonuçta ortaya çıkan analizi birbirine karıştırmaz hale getirir: tutarsız bir küme için bir tablonun, aynı küme için kapalı bir tablo mevcut olsa bile kapatılması imkansız olabilir.

Kural deterministik değildir: kaldırılacak (veya tutulacak) formül seti keyfi olarak seçilebilir; bu, çok büyük olmayan bir dizi formülün atılması sorununu yaratır, bu da elde edilen kümeyi tatmin edici hale getirir ve o kadar küçük değildir ki, gerekli genişletme kurallarını uygulanamaz hale getirir. Çok sayıda olası seçeneğe sahip olmak, kapalı bir tablo arama sorununu daha da zorlaştırır. ${\ displaystyle (\ theta)}$

Bu determinizm , yalnızca modal genişletme kuralından önce uygulanacak ve böylece yalnızca diğer kuralı uygulanamaz kılan formülleri kaldıracak şekilde kullanımını kısıtlayarak önlenebilir . Bu durum, iki kuralın tek bir kuralda birleştirilmesiyle de formüle edilebilir. Ortaya çıkan kural, eski kural ile aynı sonucu verir, ancak eski kuralı uygulanamaz kılan tüm formülleri örtük olarak atın. Bu kaldırma mekanizmasının birçok mod mantığı için tamlığı koruduğu kanıtlanmıştır. ${\ displaystyle (\ theta)}$${\ displaystyle (\ theta)}$

Axiom T , erişilebilirlik ilişkisinin yansımasını ifade eder: her dünyaya kendisinden erişilebilir. Karşılık gelen tablo genişletme kuralı:

${\ displaystyle (T) {\ frac {A_ {1}; \ ldots; A_ {n}; \ Box B} {A_ {1}; \ ldots; A_ {n}; \ Box B; B}}}$

Bu kural, aynı dünyadaki koşulları ilişkilendirir: Bir dünyada doğruysa, yansıtma ile de aynı dünyada geçerlidir . Bu kural, hem ön koşulu hem de sonucu aynı dünyaya atıfta bulunduğundan işlemsel değil durağandır. ${\ displaystyle \ Box B}$${\ displaystyle B}$

Bu kural , bu formül üretmek için "kullanılmış" olmasına rağmen, ön koşuldan sonuca kopyalar . Bu doğru, çünkü dikkate alınan dünya aynı, orada da öyle . Bu "kopyalama" bazı durumlarda gereklidir. Örneğin, aşağıdakilerin tutarsızlığını kanıtlamak gereklidir : tek uygulanabilir kural sıralıdır , kopyalanmadığı takdirde bunlardan biri engellenir . ${\ displaystyle \ Box B}$${\ displaystyle B}$${\ displaystyle \ Box B}$${\ displaystyle \ Box (a \ kama \ neg \ Kutu a)}$${\ Displaystyle (T), (\ kama), (\ theta), (K)}$${\ displaystyle \ Box a}$

Yardımcı tablolar

Alternatif dünyalarda tutulan formüllerle uğraşmanın farklı bir yöntemi, tabloda tanıtılan her yeni dünya için farklı bir tablo başlatmaktır. Örneğin, erişilebilir bir dünyada bunun yanlış olduğunu ima eder , bu nedenle kişi köklerini temel alan yeni bir tablo başlatır . Bu yeni tablo, genişletme kuralının uygulandığı orijinal tablonun düğümüne eklenir; Bu tablonun kapanması, aynı düğümün diğer yardımcı tablolarla ilişkilendirilmiş olup olmadığına bakılmaksızın, o düğümün bulunduğu tüm dalların bir kapanışını derhal oluşturur. Yardımcı tablolar için genişletme kuralları orijinal olanla aynıdır; bu nedenle, bir yardımcı tablo sırayla diğer (alt) yardımcı tablolara sahip olabilir. ${\ displaystyle \ neg \ Kutu A}$${\ displaystyle A}$${\ displaystyle \ neg A}$

Küresel varsayımlar

Yukarıdaki modal tablolar, bir dizi formülün tutarlılığını belirler ve yerel mantıksal sonuç problemini çözmek için kullanılabilir . Bu, her model için , bir dünyada doğru ise , o zaman aynı dünyada da doğru olup olmadığını anlama sorunudur . Bu, aynı modelin aynı dünyasında da geçerli olan varsayımla, bir model dünyasında doğru olup olmadığını kontrol etmekle aynıdır. ${\ displaystyle M}$${\ displaystyle A}$${\ displaystyle w}$${\ displaystyle B}$${\ displaystyle B}$${\ displaystyle A}$

Bununla ilgili bir problem, modelin tüm olası dünyalarında bir formülün (veya formül setinin) doğru olduğu varsayımının olduğu küresel sonuç problemidir . Sorun tüm modellerinde, olmadığının kontrol edilmesi olmasıdır tüm dünyada geçerlidir, aynı zamanda tüm dünyada geçerlidir. ${\ displaystyle G}$${\ displaystyle M}$${\ displaystyle G}$${\ displaystyle B}$

Yerel ve küresel varsayım, varsayılan formülün bazı dünyalarda doğru olduğu ancak diğerlerinde doğru olmadığı modellerde farklılık gösterir. Örnek olarak, küresel olarak gerektirir , ancak yerel olarak değil. Yerel girişim , sırasıyla yapan ve doğru olan iki dünyadan oluşan ve ikincisine birinciden erişilebilen bir modelde geçerli değildir ; birinci dünyada varsayım doğrudur ama yanlıştır. Bu karşı örnek işe yarar çünkü bir dünyada doğru ve başka bir dünyada yanlış kabul edilebilir. Bununla birlikte, aynı varsayım küresel kabul edilirse , modelin hiçbir dünyasında izin verilmez. ${\ displaystyle \ {P, \ neg \ Kutu (P \ kama S) \}}$${\ displaystyle \ neg \ Box Q}$${\ displaystyle P}$${\ displaystyle \ neg P, Q}$${\ displaystyle \ Box Q}$${\ displaystyle P}$${\ displaystyle \ neg P}$

Bu iki sorun birleştirilebilir, böylece küresel varsayımın yerel bir sonucu olup olmadığı kontrol edilebilir . Tableaux calculi, bahsettiği dünyadan bağımsız olarak, her düğüme eklenmesine izin veren bir kuralla küresel varsayımı ele alabilir. ${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle G}$

Notasyonlar

Aşağıdaki kurallar bazen kullanılır.

Düzgün gösterim

Tableaux genişletme kuralları yazılırken, formüller genellikle bir kural kullanılarak belirtilir, böylece örneğin her zaman olduğu kabul edilir . Aşağıdaki tablo, önermesel, birinci dereceden ve modal mantığındaki formüllerin gösterimini sağlar. ${\ displaystyle \ alpha}$${\ displaystyle \ alpha _ {1} \ wedge \ alpha _ {2}}$

Gösterim	Formüller
${\ displaystyle \ alpha}$	${\ displaystyle \ alpha _ {1} \ wedge \ alpha _ {2}}$	${\ displaystyle \ neg ({\ overline {\ alpha _ {1}}} \ vee {\ overline {\ alpha _ {2}}})}$	${\ displaystyle \ neg (\ alpha _ {1} \ rightarrow {\ overline {\ alpha _ {2}}})}$
${\ displaystyle \ beta}$	${\ displaystyle \ beta _ {1} \ vee \ beta _ {2}}$	${\ displaystyle {\ overline {\ beta _ {1}}} \ rightarrow \ beta _ {2}}$	${\ displaystyle \ neg ({\ overline {\ beta _ {1}}} \ wedge {\ overline {\ beta _ {2}}})}$
${\ displaystyle \ gamma}$	${\ displaystyle \ forall x \ gamma _ {1} (x)}$	${\ displaystyle \ neg \ var x {\ overline {\ gamma _ {1} (x)}}}$
${\ displaystyle \ delta}$	${\ displaystyle \ var x \ delta _ {1} (x)}$	${\ displaystyle \ neg \ forall x {\ overline {\ delta _ {1} (x)}}}$
${\ displaystyle \ pi}$	${\ displaystyle \ Diamond \ pi _ {1}}$	${\ displaystyle \ neg \ Box {\ overline {\ pi _ {1}}}}$
${\ displaystyle \ upsilon}$	${\ displaystyle \ Box \ upsilon _ {1}}$	${\ displaystyle \ neg \ Diamond {\ overline {\ upsilon _ {1}}}}$

İlk sütundaki her etiket, diğer sütunlardaki formüllerden biri olarak alınır. Örneğin, formülde alt formülün olumsuzlanması olması için, onun yerine görünen formülün olumsuzlamasını gösteren gibi üstü çizili bir formül . ${\ displaystyle {\ overline {\ alpha _ {1}}}}$${\ displaystyle \ alpha _ {1}}$${\ displaystyle \ neg (a \ vee b)}$${\ displaystyle \ alpha _ {1}}$${\ displaystyle a}$

Her etiket birçok eşdeğer formülü gösterdiğinden, bu gösterim tüm bu eşdeğer formüller için tek bir kural yazmaya izin verir. Örneğin, birleşik genişletme kuralı şu şekilde formüle edilir:

${\ displaystyle (\ alpha) {\ frac {\ alpha} {\ begin {dizi} {c} \ alpha _ {1} \\\ alpha _ {2} \ end {dizi}}}}$

İmzalı formüller

Bir tablodaki formül doğru kabul edilir. İşaretli tablolar, bir formülün yanlış olduğunu belirtmeye izin verir. Bu genellikle her formüle bir etiket eklenerek elde edilir, burada T etiketi formüllerin doğru olduğunu ve F'nin yanlış kabul edildiğini gösterir . Farklı ama eşdeğer bir gösterim, düğümün solunda doğru olduğu ve sağında yanlış kabul edilen formüllerin yazılmasıdır.

Tarih

Onun içinde Sembolik Mantık Bölüm II , Charles Lutwidge Dodgson Ağaçlar Yöntem, bir hakikat ağacının ilk modern kullanımını gündeme getirdi.

Anlamsal tablo yöntemi Hollandalı mantıkçı Evert Willem Beth (Beth 1955) tarafından icat edildi ve Raymond Smullyan tarafından klasik mantık için basitleştirildi (Smullyan 1968, 1995). Yukarıda anlatılan, Smullyan'ın basitleştirmesi, "tek taraflı tablolar" dır. Smullyan'ın yöntemi, Walter Carnielli (Carnielli 1987) tarafından keyfi çok değerli önermelere ve birinci dereceden mantığa genelleştirilmiştir. Tableaux, sezgisel olarak baş aşağı sıralı sistemler olarak görülebilir. Tableaux ve ardışık sistemler arasındaki bu simetrik ilişki resmi olarak (Carnielli 1991) 'de kurulmuştur.

Ayrıca bakınız

• Çözünürlük (mantık)

Referanslar

• Beth, Evert W., 1955. " Anlamsal işlem ve biçimsel türetilebilirlik ", Mededelingen van de Koninklijke Nederlandse Akademie van Wetenschappen, Afdeling Letterkunde , NR Cilt 18, no 13, 1955, s 309–42. Jaakko Intikka'da (ed.) The Philosophy of Mathematics , Oxford University Press, 1969'da yeniden basılmıştır .
• Bostock, David, 1997. Intermediate Logic . Oxford Üniv. Basın.
• M D'Agostino, D Gabbay, R Haehnle, J Posegga (Eds), Handbook of Tableau Methods , Kluwer, 1999.
• Girle, Rod, 2000. Modal Mantık ve Felsefe . Teddington UK: Acumen.
• Goré, Rajeev (1999) D'Agostino, M., Dov Gabbay, R. Haehnle ve J. Posegga, eds, Handbook of Tableau Methods'da " Modal ve Zamansal Mantık için Tableau Methods" . Kluwer: 297-396.
• Richard Jeffrey , 2006 (1967). Biçimsel Mantık: Kapsamı ve Sınırları , 4. baskı. Hackett Publishing Company, Inc.
• Raymond Smullyan , 1995 (1968). Birinci Derece Mantık . Dover Yayınları.
• Melvin Fitting (1996). Birinci dereceden mantık ve otomatik teorem kanıtlama (2. baskı). Springer-Verlag.
• Reiner Hähnle (2001). Tableaux ve İlgili Yöntemler. Otomatik Akıl Yürütme El Kitabı
• Reinhold Letz, Gernot Stenz (2001). Model Eleme ve Bağlantı Tablosu Prosedürleri. Otomatik Akıl Yürütme El Kitabı
• Zeman, JJ (1973) Modal Mantık. Reidel.

Dış bağlantılar

• TABLEAUX : analitik tablolar ve ilgili yöntemlerle otomatik akıl yürütme üzerine yıllık uluslararası bir konferans
• JAR : Otomatik Akıl Yürütme Dergisi
• Tableaux paketi : tableaux kullanarak önerme ve birinci dereceden mantık için etkileşimli bir kanıtlayıcı
• Ağaç kanıtı oluşturucu : Tabloları kullanarak önerme ve birinci dereceden mantık için başka bir etkileşimli kanıtlayıcı
• LoTREC : IRIT / Toulouse Üniversitesi'nden modal mantık için genel bir tabloya dayalı kanıtlayıcı