By Daniele Mundici

Senza richiedere prerequisiti il testo si propone di fornire una dimostrazione dei fondamentali teoremi della logica matematica (compattezza, completezza di Gödel, Löwenheim-Skolem) introducendo i concetti sintattici e semantici in modo progressivo, dalla logica booleana a quella predicativa. according to facilitare l. a. lettura attiva, il testo contiene numerosi esercizi.

Show description

Read Online or Download Logica: Metodo Breve PDF

Best italian books

La passione secondo Thérèse

Milano, Feltrinelli,, 1999, eightvo brossura editoriale con copertina illustrata a colori, pp. 172 (piccole fioriture al taglio) .

Extra info for Logica: Metodo Breve

Sample text

La formula F = (¬(XII ∧ XI) ∨ XIII) comincia con una parentesi aperta “(” quindi siamo nel Caso 3 o 4. Partendo da sinistra, per ogni connettivo ∧ oppure ∨ contiamo di quanto vincono le parentesi aperte alla sua sinistra, rispetto alle chiuse. Quando incontriamo il primo connettivo binario in cui le aperte vincono di uno, spezziamo la formula in due, quella di sinistra e quella di destra, eliminando le due parentesi esterne. Nel nostro esempio tale connettivo `e un ∨, e siamo nel Caso 4. Alla sua sinistra troviamo la formula ¬(XII ∧ XI), mentre a destra troviamo la formula XIII.

Es . Ora, usando la distributivit` a possiamo scrivere F ≡ G ∧ H ≡ (K1 ∨ . . ∨ Kq ) ∧ (E1 ∨ . . ∨ Es ) ≡ (Ki ∧ Ej ). i,j E quest’ultima formula `e una DNF per F . Caso 3. F = G ∨ H. Ragioniamo come nel Caso 2. Dalle DNF di G e H immediatamente troviamo una DNF per F . Con la distributivit` a partendo dalle CNF per G e H troviamo una CNF per F . Un insieme S di formule si dice finitamente soddisfacibile se ogni sottinsieme finito di S `e soddisfacibile. 5 (Teorema di compattezza, G¨ odel, 1930).

Decidi se la tesi sia o no conseguenza logica delle premesse. Suggerimento: Per ogni assegnazione α che soddisfi le tre premesse (e che sia appropriata alle variabili X, Y, Z, W ), dobbiamo verificare se α soddisfa anche la tesi. Ci sono 16 controlli da fare. Esercizi 53 Il metodo refutazionale offre la seguente procedura alternativa: (i) metti in CNF ogni premessa Pi , i = 1, 2, 3, e riscrivila come insieme finito Ci di clausole; (ii) fai la stessa cosa per la negazione della tesi, ottenendo un insieme finito N di clausole; (iii) applica DPP all’insieme di clausole C1 ∪ C2 ∪ C3 ∪ N .

Download PDF sample

Rated 4.52 of 5 – based on 34 votes