Teorema di compattezza

Messaggioda Michele.c93 » 20/03/2017, 18:04

Ragazzi non ho capito il teorema di compattezza che dice che Dato un Insieme $ F $ di formule proposizionali soddisfacibile lo è anche ogni suo sottoinsieme $ Gsube F $.
In particolare non ho capito la dimostrazione per cui se ogni suo sottoinsieme è soddisfacibile lo è anche $ F $ .
Il mio prof la spiega cosi:
1) Caso in cui $F$ è finito. Siano ${p1,p2,..,pn}$ le variabili proposizionali che compaiono in $F$ e sia $Gnsube F$ l'insieme di sottoformule di $F$ che contengono al più le variabili ${p1,p2,..,pn}$ e quindi significa che $Gn$ contiene al più $2^n$ elementi(dato che ognuno di essi ha una tavola di verità distinta). E da questo ne consegue che se in $F$ occorrono variabili in numero finito allora $F$ è finito e quindi soddisfacibile.
DOMANDA. Non ho capito,quindi se ho un insieme finito di formule esso è sempre soddisfacibile? Se si Perchè?

2) CASO IN CUI $F$ E' INFINITO. Fa riferimento all'assegnamento dei valori di verità come all'assegnamento lungo un albero binario e al LEMMA DI KONIG che dice che se un albero ha cammini arbitrariamente lunghi ha cammini infiniti. E quindi dice che sia $Ts$ il sottoalbero binario ottenuto da tutti i cammini finiti $r,a1,...an$ tale che una valutazione di verità rende ogni formula in $Gn$ vera. Allora dato che $Ts$ può soddisfare qualunque elemento di $Gn$ ne consegue che ha cammini arbitrariamente lunghi e quindi,per il lemma di Konig,infiniti. Ma se la valutazione di verità vale per un cammino infinito allora vale per tutto l'albero, quindi rende tutte le formule di $F$ vere, e quindi F è soddisfacibile.
Qui se ho ben capito mi basta trovare un cammino finito soddisfacibile per dire che vale per tutto l'albero?
Michele.c93
Junior Member
Junior Member
 
Messaggio: 65 di 150
Iscritto il: 28/06/2014, 16:21

Torna a Algebra, logica, teoria dei numeri e matematica discreta

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite