Metoda arborilor de decizie in logica propozitiilor

Metoda arborilor de decizie (sau metoda tableurilor semantice) este o tehnica eficienta de verificare a validitatii formulelor logice si a consistentiei multimilor de propozitii. Ea se bazeaza pe reducerea la absurd: presupunem ca formula este falsa (sau multimea de propozitii este satisfiabila) si construim un arbore prin descompunerea conectivilor logici, urmand reguli precise pentru fiecare operator. Regulile de baza: pentru conjunctie (∧), ambele subformule trebuie sa fie adevarate, deci adaugam ambele pe aceeasi ramura; pentru disjunctie (∨), cel putin una trebuie sa fie adevarata, deci creem ramuri separate pentru fiecare alternativa; pentru implicatie (→), falsa doar cand antecedentul e adevarat si consecventul fals, deci descompunem in doua ramuri (una cu antecedentul fals, alta cu consecventul adevarat); pentru negatie (¬), aplicam reguli duale.

Scopul este sa obtinem ramuri inchise (care contin o contradictie, de ex. o formula si negatia ei) si ramuri deschise (fara contraditii). Daca toate ramurile se inchid, formula este valida (tautologie) sau multimea este inconsistenta. Daca ramane macar o ramura deschisa, exista un contraexemplu.

Metoda este sistematica, completa si usor de aplicat, fiind preferata in demonstratiile automate. In liceu, se utilizeaza pentru verificarea tautologiilor, a echivalentelor si a argumentelor valide, pregatind elevii pentru notiuni avansate de logica matematica.

Exemple

• Exemplul 1: Verificati daca formula (p ∧ q) → (p ∨ q) este tautologie. Construim arborele: negam formula (presupunem falsa) → punem ¬((p ∧ q) → (p ∨ q)). Regula pentru implicatie falsa: antecedentul (p ∧ q) adevarat si consecventul (p ∨ q) fals. Desfacem p ∧ q: adaugam p si q pe ramura. Desfacem p ∨ q fals: inseamna ¬p si ¬q. Ramura contine p, q, ¬p, ¬q → contradictie p si ¬p. Ramura se inchide. Toate ramurile inchise → formula este tautologie.
• Exemplul 2: Verificati consistenta multimii {p ∨ q, ¬p}. Construim arborele pentru satisfiabilitate. Punem p ∨ q si ¬p. Regula pentru ∨: ramura1 cu p, ramura2 cu q. Pe ramura1 avem p si ¬p → contradictie, ramura inchisa. Pe ramura2 avem q si ¬p → fara contradictie, ramura deschisa. Multimea este consistenta (model: p fals, q adevarat).
• Exemplul 3: Verificati validitatea argumentului: (p → q), (q → r) deci (p → r). Asociem premizele si negam concluzia: p → q, q → r, ¬(p → r). Descompunem ¬(p → r): p adevarat, r fals. Apoi p → q: ramura1 cu ¬p, ramura2 cu q. Ramura1: p si ¬p → contradictie, inchisa. Ramura2: p, q si r fals. Apoi q → r: ramura2a cu ¬q, ramura2b cu r. Ramura2a: q si ¬q → contradictie. Ramura2b: r si ¬r → contradictie. Toate ramurile inchise → argumentul este valid (modus tollens).

Concepte cheie: Arbore de decizie, Ramura inchisa, Ramura deschisa, Conjunctie (∧) - ambele adevarate pe aceeasi ramura, Disjunctie (∨) - ramuri separate, Implicatie (→) - regula specifica, Negatie (¬) - duala, Consistenta vs. inconsistența, Tautologie, Contraexemplu