Enunciati Flashcards
Definizione di Enunciato
Un enunciato o proposizione è un’affermazione che assume uno ed uno solo valore di verità, vero oppure falso
Esempio di Enunciato Atomici
“La neve è bianca” (citato da Tarski)
Che cos’è una tavola di verità
La tavola di verità è una tabella dove sono riassunte le definzioni dei connettivi
Definizione di Connettivi
In matematica, un connettivo è un simbolo o una parola utilizzata per unire due o più proposizioni per formare una nuova proposizione.
I connetivi binari sono 16 in tutto.
L’insieme { ¬ , ∪ , ∩ } è sufficiente a definirli tutti.
Ma anche { ¬ , -> } è sufficiente per definirli tutti e si dicono basi di connettivi
Definizione Di Logicamente Equivalente
Due enunciati A e B si dicono logicamente equivalenti se hanno lo stesso valore di verità per ogni interpretazione
Esempi di Equivalenze logiche
A = ¬¬ A
A = A ∩ A
A = A ∪ A
A ∩ B = B ∩ A
A ∪ B = B ∪ A
A ⇔ B = B ⇔ A
A ⇒ B = ¬B ⇒ ¬A
A ∩ (B ∩ C) = (A ∩ B) ∩ C
A ∪ (B ∪ C) = (A ∪ B) ∪ C
A ⇔ (B ⇔ C ) = (A ⇔ B) ⇔ C
A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
A ∩ (A ∪ B) = A
A ∪ (A ∩ B) = A
A ∩ B = ¬ ( A ⇒ ¬B)
A ∪ B = ¬ A ⇒ B
Soddisfacibilità di un Enunciato
Un enunciato si dice soddisfacibile se assume il valore di verità V per almeno un’interpretazione; in tal caso, questa interpretazione si dice modello per l’enunciato considerato
Definizione Di Tautologia
Un enunciato P che assume il valore di verità V per ogni interpretazione si dice enunciato valido o tautologia. Se P è un enunciato valido tautologia si scrive ⇒ P
Insoddisfacibilità di un Enunciato
Un enunciato si dice insoddisfacibile se non assume il valore di verità V per alcuna interpretazione, cioè se in ogni interpretazione assume il valore di verità F
Definizione Enunciato Falsificabile
Un enunciato si dice falsificabile se assume il valore di verità F in almeno un’interpretazione
Definizione Validità di un Enunciato
Un enunciato P è valido ( è una tautologia) se e solo se ¬P è insoddisfacibile e che P è soddisfacibile se e solo se ¬P è falsificabile
Principio del Terzo Escluso e Principio di Non Contraddizione
Principio del Terzo Escluso: un’affermazione o la sua negazione deve essere per forza vera”
Principio di Non Contraddizione: un’affermazione e la sua negazione non possono essere contemporaneamente vere
Definizione di Tableau Proposizionali
I Tableau Proposizionali sono dei proccedimenti per provare la soddisfacibilità di un enunciato. Esso decompone l’enunciato fino alle sue componenti elementari alle quali verrà richiesto di essere vere o false per soddisfare l’enunciato.
Tali interpretazioni vengono chiamati modelli
Quando un ramo di un Tableau è detto chiuso
Si dice allora che il ramo è chiuso; quando tutti i rami sono chiusi , il tableau è chiuso e la confutazione è completata , perche esclude ogni soddisfacibilità
Definizione di Correttezza di un Tableau
Detto T un tableau completo per P, P è insoddisfacibile se e soltanto se il tableau T è chiuso. L’implicazione “ se T è chiuso allora P è insoddisfacibile” corrisponde alla correttezza del metodo.
