Tautologii, contradicții și formule satisfiabile

În logica propozițională, clasificarea formulelor în funcție de valorile lor de adevăr este fundamentală pentru validarea raționamentelor. Tautologiile sunt mereu adevărate, contradicțiile mereu false, iar formulele satisfiabile sunt adevărate cel puțin într-un caz. Înțelegerea acestor distincții îți permite să verifici corectitudinea argumentelor matematice și algoritmilor computaționali, evitând erori logice grave în proiectare sau demonstrații.

Ce trebuie să știi

• Tautologie: O formulă care este adevărată pentru orice atribuire posibilă a variabilelor. Exemplu clasic: $P \lor \neg P$ (principiul terțului exclus).
• Contradicție (Insatisfiabil): O formulă care este falsă indiferent de valorile variabilelor. Exemplu: $P \land \neg P$.
• Formulă Satisfiabilă: O formulă pentru care există cel puțin o atribuire de valori care o face adevărată. Orice tautologie este și satisfiabilă.
• Metoda Tabelului de Adevăr: Instrumentul principal de verificare. Se enumeră toate combinațiile posibile de valori pentru variabilele $P, Q, \dots$ și se calculează valoarea finală a formulei.
• Echivalența Logică: Două formule sunt echivalente dacă au același tabel de adevăr. Aceasta implică faptul că negația uneia este o contradicție dacă cealaltă este o tautologie.
• Implicație Logică: Spunem că $\phi \models \psi$ dacă orice atribuire care îl face pe $\phi$ adevărat îl face și pe $\psi$ adevărat. Acest concept este baza deducției valide.

Exemplu: Verificarea unei tautologii

Să verificăm dacă formula $P \to Q$ este echivalentă cu $\neg P \lor Q$. Construim tabelul de adevăr:

$P$	$Q$	$P \to Q$	$\neg P$	$\neg P \lor Q$
V	V	V	F	V
V	F	F	F	F
F	V	V	V	V
F	F	V	V	V

Observăm că coloanele pentru $P \to Q$ și $\neg P \lor Q$ sunt identice. Prin urmare, cele două formule sunt echivalente logic. Deoarece rezultatul nu este întotdeauna adevărat (vezi rândul 2), niciuna nu este o tautologie universală, dar ambele sunt satisfiabile.

Cum să înveți

1. Exersează tabelele de adevăr: Începe cu formule simple (2-3 variabile) și construiește tabelele pas cu pas. Este cea mai sigură metodă de a vizualiza comportamentul logic.
2. Memorează legile fundamentale: Învață pe de rost legile de idempotență, asociativitate, comutativitate, distributivitate și dubla negație. Ele simplifică enorm verificarea tautologiilor complexe.
3. Gândește-te contraexemplu: Pentru a disprove o afirmație că o formulă este tautologie, caută doar un singur caz (rând din tabel) unde rezultatul este fals.