Fondamenti di informatica - Laurea triennale Informatica/Proposizioni condizionali ed equivalenza logica

Proposizioni condizionali (implicazioni) p→q

• Una proposizione del tipo “Se p, allora q” si chiama proposizione condizionale.
• p è l’ipotesi (o antecedente), q è la conclusione (o conseguente).

Valore di verità di p→q

La regola fondamentale è:

• p→q è falsa solo quando p è vera e q è falsa.
• In tutti gli altri casi è vera (anche quando p è falsa).

Tabella (in parole):

• p vera, q vera → vero
• p vera, q falsa → falso
• p falsa, q vera → vero
• p falsa, q falsa → vero

Questo giustifica l’idea che, se l’ipotesi non si verifica, non possiamo dire che l’affermazione “se… allora…” sia sbagliata: per convenzione logica risulta vera.

“Vera per default” (verità vacua)

Quando p→q è vera solo perché p è falsa, si dice vacuamente vera (o “vera per default”).

Precedenza degli operatori

Nelle espressioni con ¬, ∧, ∨, →, l’operatore → viene valutato per ultimo (quindi spesso si calcolano prima negazioni e congiunzioni/disgiunzioni).

Riscrivere frasi come condizionali

Molte frasi naturali possono essere riscritte come “se… allora…”, ad esempio:

• “q se p” → “Se p, allora q”.
• “p solo se q” significa che q è condizione necessaria per p: quindi “Se p, allora q”.
• “Condizione necessaria per p è q” → “Se p, allora q”.
• “Condizione sufficiente per p è q” → “Se q, allora p”.

Idea chiave:

• necessaria: senza q, p non può accadere → p→q
• sufficiente: q garantisce p → q→p

Converso, contropositiva e loro differenze

• Converso di p→q: q→p. Non è in generale equivalente all’originale: può avere valore di verità diverso.
• Contropositiva di p→q: ¬q→¬p. Questa invece è sempre logicamente equivalente all’originale.

Teorema fondamentale: (p→q)≡(¬q→¬p) cioè condizionale e contropositiva hanno sempre la stessa verità.

Bicondizionale p↔q

• La proposizione “p se e solo se q” (anche “iff”) è vera quando p e q hanno lo stesso valore di verità:
  • entrambe vere oppure entrambe false.

È equivalente a dire: p↔q≡(p→q)∧(q→p) Quindi “se e solo se” significa due implicazioni in entrambe le direzioni.

Nota linguistica: in matematica a volte “se” viene usato informalmente con senso di “se e solo se”, ma in logica formale vanno distinti.

Equivalenza logica

Due proposizioni composte sono logicamente equivalenti se hanno sempre gli stessi valori di verità per ogni assegnazione delle proposizioni di base. Si verifica tipicamente tramite tabelle di verità.

Leggi di De Morgan

Servono per negare correttamente “e”/“o”:

• ¬(p∨q)≡(¬p∧¬q)
• ¬(p∧q)≡(¬p∨¬q)

Negazione di un condizionale

Un risultato molto importante è: ¬(p→q)≡(p∧¬q) Cioè negare “se p allora q” non produce un altro “→”, ma un “e”: “p è vero e q è falso”.

Messaggio finale (precisione)

Nel linguaggio comune spesso “se” viene usato con intenzione di “se e solo se”, ma in matematica e scienze serve precisione: distinguere bene condizionale, bicondizionale, converso e contropositiva evita ambiguità e errori di ragionamento.