predicati, calcolo dei
predicati, calcolo dei calcolo logico in cui si può esprimere, in modo rigoroso, un ragionamento e valutarne la correttezza. Se si pensa al ragionamento come a una successione [...] dei predicati ed è dimostrabile in esso. Un’altra analogia con il calcolo degli enunciati è il teoremadicompletezza semantica (→ completezza logica) il quale stabilisce che nel calcolo dei predicati possono essere dimostrate tutte e sole le formule ...
Leggi Tutto
modus ponens
modus ponens in logica, regola di deduzione (indicata sinteticamente con MP) che permette di dedurre da una implicazione (per esempio, «se Socrate è un uomo allora è mortale») e dalla premessa [...] può essere espresso dalla formula ben formata ((A ⇒ B) ∧ A ⇒ B), che, come si verifica costruendo la sua tavola di verità, è una tautologia:
Resta così verificata la condizione del teoremadicompletezza semantica del linguaggio degli → enunciati. ...
Leggi Tutto
Logico e matematico statunitense (Brooklyn 1921- Oak land 2006), dal 1962 al 1965 presidente dell'Association for symbolic logic. A lui si deve, fra l'altro, una nota versione del teoremadicompletezza [...] semantica per le teorie del 1º ordine. Importante il suo impegno per garantire l'accesso all'istruzione universitaria per studenti svantaggiati tramite incentivi economici ...
Leggi Tutto
MODELLI, Teoria dei (App. III, 11, p. 139)
Giulio Supino
Alberto Pasquinelli
Aldo Marruccelli
In questi ultimi 15 anni (1960-75) la t. dei m. si è sviluppata secondo due ordini di idee del tutto opposti. [...] necessarie e sufficienti aflìnché una formula di T sia un teoremadi T′. Una prima soluzione di questo problema è espressa dal teoremadicompletezza semantica di Gödel: "una formula di una teoria elementare T è un teorema se e solo se è valida ...
Leggi Tutto
Storia della civiltà europea a cura di Umberto Eco (2014)
Maria Conforti
Il contributo è tratto da Storia della civiltà europea a cura di Umberto Eco, edizione in 75 ebook
I teoremi d’incompletezza di Gödel del 1931 sono i risultati più profondi e spettacolari [...] cui G è falsa: infatti, applicando il teoremadicompletezza semantica, dall’indimostrabilità di G in PA segue che G non è conseguenza logica di PA, ossia che non tutti i modelli di PA sono anche modelli di G.) Naturalmente non è possibile ovviare a ...
Leggi Tutto
SEGRE, Beniamino.
Enrico Rogora
– Nacque a Torino il 16 febbraio 1903, da Samuele e da Leonilda Segre, entrambi di famiglia ebraica.
Studiò a Torino e ottenne una borsa di studio per l’Università quando [...] chiaramente a nudo dalle polemiche tra Federigo Enriques e Severi sulle rispettive dimostrazioni del teoremadicompletezza e dalla ricerca internazionale. Ciò lo portò probabilmente ad anticipare le considerazioni pessimistiche sull’inadeguatezza ...
Leggi Tutto
proposizioni, calcolo delle
proposizioni, calcolo delle calcolo logico sviluppato nell’ambito del linguaggio degli → enunciati, detto anche calcolo proposizionale. I suoi oggetti sono le proposizioni, [...] si dimostra che ogni forma proposizionale derivabile nel calcolo delle proposizioni è una tautologia (teoremadicompletezza semantica, in → completezza logica).
La teoria formale assiomatica che esprime il calcolo delle proposizioni si articola in ...
Leggi Tutto
validita
validità in logica, proprietà di una formula di essere vera per ogni interpretazione dei simboli che vi compaiono. Per esempio, la formula ∀x(x = x) (si legge «per ogni x, x = x») è vera per [...] è valida se risulta soddisfatta in ogni dominio di interpretazione del linguaggio logico in questione.
Nel calcolo catturare” tutte e sole le formule valide. Questo risultato è noto con il nome diteoremadicompletezza semantica (→ completezza). ...
Leggi Tutto
funzione logica
funzione logica detta anche funzione di verità oppure → funzione booleana, associa a uno o più valori di verità in ingresso (vero V e falso F) un solo valore di verità in uscita. Un esempio [...] enunciato a essa associato. Tale risultato è dovuto al logico E.L. Post e va sotto il nome diteoremadicompletezza funzionale. Da ciò deriva che ogni funzione logica è una funzione calcolabile perché esiste una procedura algoritmica (rappresentata ...
Leggi Tutto
conseguenza
conseguenza si dice che l’enunciato P è conseguenza logica di un insieme A di enunciati (tipicamente un sistema di assiomi) quando P è dedotta da uno o più enunciati di A. Se la deduzione [...] invece il fatto che P risulta vero in tutti modelli in cui sono veri gli enunciati di A. Per il teoremadicompletezzadi Gödel, le due nozioni di conseguenza coincidono nella teoria del primo ordine relativa ai predicati. In essa, quindi, tutto ciò ...
Leggi Tutto