Logica formale

Tableaux semantico

Dagli anni '80 un'altra tecnica per determinare la validità degli argomenti in PC o LPC ha guadagnato una certa popolarità, sia per la sua facilità di apprendimento che per la sua diretta implementazione da parte dei programmi per computer. Originariamente suggerito dal logico olandese Evert W. Beth, fu sviluppato e pubblicizzato in modo più completo dal matematico e logico americano Raymond M. Smullyan. Basandosi sull'osservazione che è impossibile che le premesse di un argomento valido siano vere mentre la conclusione è falsa, questo metodo tenta di interpretare (o valutare) le premesse in modo tale che siano tutte contemporaneamente soddisfatte e la negazione del anche la conclusione è soddisfatta. Il successo in tale sforzo mostrerebbe l'argomento non valido, mentre la mancata individuazione di tale interpretazione lo dimostrerebbe valido.

La costruzione di un tableau semantico procede come segue: esprime le premesse e la negazione della conclusione di un argomento nel PC usando solo negazione (∼) e disgiunzione (∨) come connettivi proposizionali. Elimina ogni ricorrenza di due segni di negazione in una sequenza (ad esempio, ∼∼∼∼∼a diventa ∼a). Ora costruisci un diagramma ad albero che si dirama verso il basso in modo tale che ogni disgiunzione sia sostituita da due rami, uno per lo sbieco sinistro e uno per quello destro. La disgiunzione originale è vera se uno dei due rami è vero. Il riferimento alle leggi di De Morgan mostra che una negazione di una disgiunzione è vera nel caso in cui le negazioni di entrambi i disgiunti siano vere [cioè, ∼ (p ∨ q) ≡ (∼p · ∼q)]. Questa osservazione semantica porta alla regola che la negazione di una disgiunzione diventa un ramo contenente la negazione di ogni disgiunzione:

Considera il seguente argomento:

Scrivi:

Ora cancella la disgiunzione e forma due rami:

Solo se tutte le frasi in almeno un ramo sono vere è possibile che le premesse originali siano vere e la conclusione falsa (equivalentemente per la negazione della conclusione). Tracciando la linea verso l'alto in ciascun ramo fino alla cima dell'albero, si osserva che nessuna valutazione di a nel ramo sinistro comporterà che tutte le frasi in quel ramo ricevano il valore vero (a causa della presenza di a e ∼a). Allo stesso modo, nel ramo giusto la presenza di b e ∼b rende impossibile che una valutazione comporti che tutte le frasi del ramo ricevano il valore vero. Questi sono tutti i rami possibili; quindi, è impossibile trovare una situazione in cui le premesse sono vere e la conclusione falsa. L'argomento originale è quindi valido.

Questa tecnica può essere estesa per gestire altri connettivi:

Inoltre, in LPC, devono essere introdotte regole per l'istanza di wff quantificati. Chiaramente, qualsiasi ramo contenente entrambi (∀x) ϕx e ∼ϕy è uno in cui non tutte le frasi in quel ramo possono essere soddisfatte simultaneamente (presupponendo la coerenza ω; vedi metalogic). Ancora una volta, se tutti i rami non sono contemporaneamente soddisfacenti, l'argomento originale è valido.

Sistemi speciali di LPC

LPC come esposto sopra può essere modificato restringendo o estendendo la gamma di wff in vari modi:

• 1.Sistemi parziali di LPC. Alcuni dei sistemi più importanti prodotti dalla restrizione sono qui delineati:

  • a. Potrebbe essere richiesto che ogni variabile predicato sia monadica, pur consentendo un numero infinito di variabili individuali e predicate. I wff atomici sono semplicemente quelli costituiti da una variabile predicata seguita da una singola variabile individuale. Altrimenti, le regole di formazione rimangono come prima e anche la definizione di validità è come prima, sebbene semplificata in modi ovvi. Questo sistema è noto come LPC monadico; fornisce una logica di proprietà ma non di relazioni. Una caratteristica importante di questo sistema è che è decidibile. (L'introduzione anche di una singola variabile di predicato diadico, tuttavia, renderebbe il sistema indecidibile e, di fatto, anche il sistema che contiene solo una singola variabile di predicato diadico e nessuna altra variabile di predicato si è dimostrato indecidibile.)

  • bUn sistema ancora più semplice può essere formato richiedendo (1) che ogni variabile predicato sia monadica, (2) che venga utilizzata una sola singola variabile (ad esempio, x), (3) che ogni occorrenza di questa variabile sia vincolata, e (4) che non esiste un quantificatore nell'ambito di nessun altro. Esempi di wff di questo sistema sono (∀x) [ϕx ⊃ (ψx · χx)] (“Qualunque cosa sia ϕ è sia ψ che χ”); (∃x) (ϕx · ∼ψx) (“C'è qualcosa che è ϕ ma non ψ”); e (∀x) (ϕx ⊃ ψx) ⊃ (∃x) (ϕx · ψx) (“Se qualunque cosa sia ϕ è ψ, allora qualcosa è sia ϕ che ψ”). La notazione per questo sistema può essere semplificata omettendo x ovunque e scrivendo ∃ϕ per “Qualcosa è ϕ”, ∀ (ϕ ⊃ ψ) per “Qualunque cosa sia ϕ è ψ” e così via. Sebbene questo sistema sia più rudimentale anche dell'LPC monadico (di cui è un frammento), in esso possono essere rappresentate le forme di una vasta gamma di inferenze. È anche un sistema decidibile e le procedure decisionali di tipo elementare possono essere date per questo.

• 2.Estensioni di LPC. Sistemi più elaborati, in cui è possibile esprimere una gamma più ampia di proposizioni, sono stati costruiti aggiungendo a LPC nuovi simboli di vario tipo. Le più semplici di tali aggiunte sono:

  • a. Una o più singole costanti (ad esempio, a, b,

    ): queste costanti sono interpretate come nomi di individui specifici; formalmente si distinguono dalle singole variabili per il fatto che non possono verificarsi all'interno di quantificatori; ad esempio, (∀x) è un quantificatore ma (∀a) non lo è.

  • b. una o più costanti predicate (ad esempio, A, B,

    ), ciascuno con un determinato grado, considerato come designazione di proprietà o relazioni specifiche.

Un'ulteriore aggiunta possibile, che richiede una spiegazione un po 'più completa, consiste in simboli progettati per rappresentare le funzioni. La nozione di funzione può essere sufficientemente spiegata per gli scopi attuali come segue. Si dice che ci sia una certa funzione di n argomenti (o, di grado n) quando esiste una regola che specifica un oggetto unico (chiamato il valore della funzione) ogni volta che vengono specificati tutti gli argomenti. Nel dominio degli esseri umani, ad esempio, "la madre di -" è una funzione monadica (una funzione di un argomento), poiché per ogni essere umano esiste un individuo unico che è sua madre; e nel dominio dei numeri naturali (ovvero 0, 1, 2,

), "La somma di - e -" è una funzione di due argomenti, poiché per ogni coppia di numeri naturali esiste un numero naturale che è la loro somma. Si può pensare che un simbolo di funzione formi un nome da altri nomi (i suoi argomenti); così, ogni volta che x e y nominano numeri, "la somma di xey" nomina anche un numero, e allo stesso modo per altri tipi di funzioni e argomenti.

Per consentire l'espressione delle funzioni in LPC è possibile aggiungere:

• c.Una o più variabili di funzione (diciamo, f, g,

  ) o una o più costanti di funzione (ad esempio, F, G,

  ) o entrambi, ciascuno di alcuni gradi specifici. I primi sono interpretati come funzioni che vanno oltre i gradi specificati e i secondi come designanti funzioni specifiche di quel grado.

Quando una o tutte le a – c vengono aggiunte a LPC, le regole di formazione elencate nel primo paragrafo della sezione sul calcolo del predicato inferiore (vedi sopra Il calcolo del predicato inferiore) devono essere modificate per consentire l'integrazione dei nuovi simboli fbf. Questo può essere fatto come segue: un termine viene prima definito come (1) una singola variabile o (2) una singola costante o (3) qualsiasi espressione formata prefissando una variabile di funzione o una costante di funzione di grado n a qualsiasi n termini (questi termini - gli argomenti del simbolo della funzione - sono generalmente separati da virgole e racchiusi tra parentesi). La regola di formazione 1 è quindi sostituita da:

• 1′ Un'espressione consistente in una variabile predicata o costante predicata di grado n seguita da n termini è un wff.

Le basi assiomatiche fornite nella sezione sull'assiomatizzazione dell'LPC (vedi sopra Assiomatizzazione dell'LPC) richiedono anche la seguente modifica: nello schema assiomatico 2 a qualsiasi termine è consentito sostituire un quando si forma β, a condizione che nessuna variabile libera nella termine viene associato in β. I seguenti esempi illustreranno l'uso delle summenzionate aggiunte a LPC: lascia che i valori delle singole variabili siano i numeri naturali; lascia che le singole costanti aeb rappresentino rispettivamente i numeri 2 e 3; lascia che A significhi "è primo"; e lascia che F rappresenti la funzione diadica "la somma di". Quindi AF (a, b) esprime la proposizione "La somma di 2 e 3 è il primo", e (∃x) AF (x, a) esprime la proposizione "Esiste un numero tale che la somma di esso e 2 è il primo “.

L'introduzione delle costanti è normalmente accompagnata dall'aggiunta alle basi assiomatiche di assiomi speciali contenenti quelle costanti, progettate per esprimere i principi che detengono gli oggetti, le proprietà, le relazioni o le funzioni da essi rappresentate, sebbene non contengano oggetti, proprietà, relazioni o funzioni in generale. Si può decidere, ad esempio, di usare la costante A per rappresentare la relazione diadica "è maggiore di" (in modo che Axy significhi "x è maggiore di y" e così via). Questa relazione, a differenza di molte altre, è transitiva; cioè, se un oggetto è maggiore di un secondo e quel secondo è a sua volta maggiore di un terzo, allora il primo è maggiore del terzo. Quindi, potrebbe essere aggiunto il seguente schema di assioma speciale: se t ₁, t ₂ e t ₃ sono dei termini, allora (At ₁ t ₂ · At ₂ t ₃) ⊃ At ₁ t ₃ è un assioma. In tal modo è possibile costruire sistemi per esprimere le strutture logiche di varie discipline particolari. L'area in cui è stata svolta la maggior parte di questo tipo di lavoro è quella dell'aritmetica dei numeri naturali.

PC e LPC sono talvolta combinati in un unico sistema. Ciò può essere fatto semplicemente aggiungendo variabili proposizionali all'elenco di primitive LPC, aggiungendo una regola di formazione all'effetto che una variabile proposizionale in piedi da sola è un wff ed eliminando "LPC" nello schema assioma 1. Questo produce come espressioni wff come (p ∨ q) ⊃ (∀x) ϕx e (∃x) [p ⊃ (∀y) ϕxy].

• 3.LPC-con-identità. La parola "is" non è sempre usata allo stesso modo. In una proposizione come (1) "Socrate è snub-nosed", l'espressione che precede "is" nomina un individuo e l'espressione che segue rappresenta una proprietà attribuita a quell'individuo. Ma, in una proposizione come (2) "Socrate è il filosofo ateniese che beveva cicuta", le espressioni che precedono e seguono "è" entrambi i nomi, e il senso di tutta la proposizione è che l'individuo nominato dal primo è lo stesso individuo dell'individuo nominato dal secondo. Pertanto, in 2 "is" può essere espanso in "è lo stesso individuo", mentre in 1 non può. Come usato in 2, "is" sta per una relazione diadica - vale a dire, identità - che la proposizione afferma di mantenere tra i due individui. Una proposta di identità deve essere intesa in questo contesto come affermazione non più di questa; in particolare non si deve ritenere che le due espressioni di denominazione abbiano lo stesso significato. Un esempio molto discusso per illustrare questo ultimo punto è "La stella del mattino è la stella della sera". È falso che le espressioni "la stella del mattino" e "la stella della sera" significano lo stesso, ma è vero che l'oggetto a cui fa riferimento il primo è lo stesso di quello a cui fa riferimento il secondo (il pianeta Venere).

Per consentire l'espressione delle forme di proposizioni di identità, una costante di predicato diadico viene aggiunta a LPC, per cui la notazione più usuale è = (scritta tra, anziché prima, i suoi argomenti). L'interpretazione prevista di x = y è che x è lo stesso individuo di y, e la lettura più conveniente è "x è identica a y". La sua negazione ∼ (x = y) è comunemente abbreviata in x ≠ y. Alla definizione di un modello LPC data in precedenza (vedi sopra Validità in LPC) ora viene aggiunta la regola (che concorda in modo ovvio con l'interpretazione prevista) che il valore di x = y deve essere 1 se lo stesso membro di D è assegnato sia a x che a y e altrimenti il ​​suo valore deve essere 0; la validità può quindi essere definita come prima. Le seguenti aggiunte (o alcune equivalenti) sono fatte alla base assiomatica per LPC: l'assioma x = x e lo schema dell'assioma che, dove aeb sono eventuali variabili individuali e α e β sono wff che differiscono solo in quello, a uno o più luoghi in cui α ha un'occorrenza libera di a, β ha un'occorrenza libera di b, (a = b) ⊃ (α ⊃ β) è un assioma. Tale sistema è noto come calcolo del predicato inferiore con identità; può ovviamente essere ulteriormente aumentato negli altri modi di cui sopra in "Estensioni di LPC", nel qual caso qualsiasi termine può essere un argomento di =.

L'identità è una relazione di equivalenza; cioè, è riflessivo, simmetrico e transitivo. La sua riflessività è espressa direttamente nell'assioma x = x, e i teoremi che esprimono la sua simmetria e transitività possono essere facilmente derivati ​​dalla base data.

Alcuni wff di LPC con identità esprimono proposizioni sul numero di cose che possiedono una determinata proprietà. "Almeno una cosa è ϕ" potrebbe, ovviamente, essere già espresso da (∃x) ϕx; “Almeno due cose distinte (non identiche) sono ϕ” ora possono essere espresse da (∃x) (∃y) (ϕx · ϕy · x ≠ y); e la sequenza può essere continuata in modo ovvio. "Al massimo una cosa è ϕ" (ovvero, "Non ci sono due cose distinte entrambe ϕ") può essere espresso dalla negazione dell'ultimo wff menzionato o dal suo equivalente, (∀x) (∀y) [(ϕx · ϕy) ⊃ x = y] e la sequenza può essere facilmente proseguita. Una formula per "Esattamente una cosa è ϕ" può essere ottenuta congiungendo le formule per "Almeno una cosa è ϕ" e "Al massimo una cosa è ϕ", ma un wff più semplice equivalente a questa congiunzione è (∃x) [ϕx · (∀y) (ϕy ⊃ x = y)], che significa "C'è qualcosa che è ϕ, e tutto ciò che è ϕ è quella cosa." La proposizione "Esattamente due cose sono ϕ" può essere rappresentata da (∃x) (∃y) {ϕx · ϕy · x ≠ y · (∀z) [ϕz ⊃ (z = x ∨ z = y)]}; vale a dire, "Ci sono due cose non identiche ognuna delle quali è ϕ, e tutto ciò che è ϕ è l'una o l'altra di queste". Chiaramente, questa sequenza può anche essere estesa per dare una formula per "Esattamente n cose sono ϕ" per ogni numero naturale n. È conveniente abbreviare il wff per "Esattamente una cosa è ϕ" a (∃! X) ϕx. Questo quantificatore speciale viene spesso letto ad alta voce come "E-Shriek x".

Descrizioni definite

Quando una determinata proprietà ϕ appartiene a un solo oggetto, è conveniente avere un'espressione che nomina quell'oggetto. Una notazione comune per questo scopo è (ιx) ϕx, che può essere letta come “la cosa che è ϕ” o più brevemente come “la ϕ”. In generale, dove a è una singola variabile e α è qualsiasi wff, (ιa) α quindi rappresenta il singolo valore di a che rende α vero. Un'espressione della forma "il così-così-così" è chiamata una descrizione definita; e (ιx), noto come operatore di descrizione, può essere considerato come formare un nome di un individuo da una forma di proposizione. (ιx) è analogo a un quantificatore in quanto, quando preceduto da un wff α, lega ogni occorrenza libera di x in α. È anche ammesso il reinserimento di variabili associate; nel caso più semplice, (ιx) ϕx e (ιy) ϕy possono essere letti semplicemente come "il ϕ".

Per quanto riguarda le regole di formazione, le descrizioni definite possono essere incorporate in LPC lasciando che le espressioni del modulo (ιa) α contino come termini; la regola 1 ′ sopra, in “Estensioni di LPC”, consentirà quindi che si verifichino in formule atomiche (comprese le formule di identità). "Il ϕ è (cioè ha la proprietà) ψ" può quindi essere espresso come ψ (ιx) ϕx; “Y è (lo stesso individuo di) ϕ” come y = (ιx) ϕx; “Il ϕ è (lo stesso individuo di) il ψ” come (ιx) ϕx = (ιy) ψy; e così via.

La corretta analisi delle proposizioni contenenti descrizioni definite è stata oggetto di notevoli controversie filosofiche. Un resoconto ampiamente accettato, tuttavia, sostanzialmente quello presentato in Principia Mathematica e noto come la teoria delle descrizioni di Russell, sostiene che "The ϕ is ψ" deve essere inteso nel senso che esattamente una cosa è ϕ e quella cosa è anche ψ. In tal caso, può essere espresso da un wff di LPC con identità che non contiene operatori descrittivi, ovvero (1) (∃x) [ϕx · (∀y) (ϕy ⊃ x = y) · ψx]. Analogamente, "y è la ϕ" viene analizzato come "y è ϕ e nient'altro è ϕ" e quindi espressibile da (2) ϕy · (∀x) (ϕx ⊃ x = y). "The ϕ is the ψ" viene analizzato come "Esattamente una cosa è ϕ, esattamente una cosa è ψ, e qualunque cosa sia ϕ è ψ" e quindi espressibile da (3) (∃x) [ϕx · (∀y) (ϕy ⊃ x = y)] · (∃x) [ψx · (∀y) (ψy ⊃ x = y)] · (∀x) (ϕx ⊃ ψx). ψ (ιx) ϕx, y = (ιx) ϕx e (ιx) ϕx = (ιy) ψy possono quindi essere considerati abbreviazioni per (1), (2) e (3), rispettivamente; e generalizzando a casi più complessi, tutti i wff che contengono operatori descrittivi possono essere considerati abbreviazioni per wff più lunghi che non lo fanno.

L'analisi che porta a (1) come formula per "Il ϕ è ψ" porta al seguente per "Il ϕ non è ψ": (4) (∃x) [ϕx · (∀y) (ϕy ⊃ x = y) · ∼ψx]. È importante notare che (4) non è la negazione di (1); questa negazione è invece (5) ∼ (∃x) [ϕx · (∀y) (ϕy ⊃ x = y) · ψx]. La differenza di significato tra (4) e (5) sta nel fatto che (4) è vero solo quando c'è esattamente una cosa che è ϕ e quella cosa non è ψ, ma (5) è vera sia in questo caso che anche quando nulla è ϕ e quando più di una cosa è ϕ. Trascurare la distinzione tra (4) e (5) può provocare una grave confusione di pensiero; nel linguaggio ordinario spesso non è chiaro se qualcuno che nega che ϕ è ψ ammette che esattamente una cosa è ϕ ma nega che sia ψ, o negare che esattamente una cosa sia ϕ.

La tesi di base della teoria delle descrizioni di Russell è che una proposizione contenente una descrizione definita non deve essere considerata come un'asserzione su un oggetto di cui quella descrizione è un nome ma piuttosto come un'asserzione quantificata esistenzialmente che una certa proprietà (piuttosto complessa) ha un caso. Formalmente, ciò si riflette nelle regole per l'eliminazione degli operatori di descrizione che sono stati descritti sopra.