Exemple de logică propozițională

În acest articol vom arăta câteva formule și evaluările lor posibile cu ajutorul metodei tabelului de adevăr.

Primul exemplu

Vom încerca să aflăm când este adevărată această formulă: ϕ = (p ∧ q) ∨ ¬q. Scriem în tabel variabilele propoziționale p și q:

$$\begin{array}{cc}p& q\\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Apoi adăugăm în tabel prima parte a formulei: (p ∧ q), negația ¬q și apoi întreaga formulă:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Acum calculăm valorile pentru a treia coloană, care este o conjuncție simplă, și în același timp pentru negație – acolo doar înlocuim valorile inverse celor din a doua coloană:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0\\ 1& 0& 0& 1\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}$$

La sfârșit calculăm valorile din ultima coloană. Aceasta este întreaga formulă. Având în vedere tabelul nostru, calculăm disjuncția „între coloana a treia și a patra”. Rezultatul:

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0& 1\\ 1& 0& 0& 1& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 1& 1\end{array}$$

Al doilea exemplu

Aceeași cerință, altă formulă: ϕ = (p ∧ ¬q) ⇔ (¬p ⇒ q). Vedem că în formulă apar variabilele propoziționale p și q și negațiile lor. Mai întâi creăm, deci, un tabel cu cele două variabile și negațiile lor:

$$\begin{array}{cccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q\\ 1& 1& 0& 0\\ 1& 0& 0& 1\\ 0& 1& 1& 0\\ 0& 0& 1& 1\end{array}$$

Apoi adăugăm formulele p ∧ ¬q și ¬p ⇒ q, pe care știm deja să le evaluăm ușor, pentru că avem în tabel atât evaluările propozițiilor, cât și pe cele ale negațiilor lor. Tabelul arată astfel:

$$\begin{array}{cccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)\\ 1& 1& 0& 0& 0& 1\\ 1& 0& 0& 1& 1& 1\\ 0& 1& 1& 0& 0& 1\\ 0& 0& 1& 1& 0& 0\end{array}$$

La sfârșit ne rămâne să evaluăm întreaga formulă, care este echivalența dintre ultimele două coloane:

$$\begin{array}{ccccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)& \varphi \\ 1& 1& 0& 0& 0& 1& 0\\ 1& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 0& 0& 1& 0\\ 0& 0& 1& 1& 0& 0& 1\end{array}$$

Al treilea exemplu

Al treilea exemplu este ceva mai complicat, vom încerca trei variabile propoziționale, ceea ce face calculul tabelului mai complex. Formula va arăta astfel: ϕ = (¬(p ⇒ q)) ∧ (r ⇔ (¬p ∨ q)).

Pentru că avem trei variabile propoziționale, numărul total de evaluări posibile este opt:

$$\begin{array}{ccc}p& q& r\\ 1& 1& 1\\ 1& 1& 0\\ 1& 0& 1\\ 1& 0& 0\\ 0& 1& 1\\ 0& 1& 0\\ 0& 0& 1\\ 0& 0& 0\end{array}$$

Mai departe procedăm la fel ca în cazul precedent, evaluăm fiecare coloană în toate cele opt rânduri. Întregul tabel va arăta astfel:

$$\begin{array}{ccccccccc}p& q& r& \mathrm{\neg }p& (p\Rightarrow q)& (\mathrm{\neg }p\vee q)& \mathrm{\neg }(p\Rightarrow q)& (r\iff (\mathrm{\neg }p\vee q))& \varphi \\ 1& 1& 1& 0& 1& 1& 0& 1& 0\\ 1& 1& 0& 0& 1& 1& 0& 0& 0\\ 1& 0& 1& 0& 0& 0& 1& 0& 0\\ 1& 0& 0& 0& 0& 0& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 0& 1& 0\\ 0& 1& 0& 1& 1& 1& 0& 0& 0\\ 0& 0& 1& 1& 1& 1& 0& 1& 0\\ 0& 0& 0& 1& 1& 1& 0& 0& 0\end{array}$$

Al patrulea exemplu

Acest exemplu nu îl vom da ca o formulă obișnuită, ci ca o problemă cu text. Trei prieteni vor să meargă la o petrecere cu tort și muzică, dar nu se plac chiar foarte mult și pun condiții în care vor merge la petrecere. Numele lor sunt Matei, Ioan și Petru. Regulile sunt următoarele:

1. Dacă merge Matei, atunci merge și Ioan.
2. La petrecere vine Petru sau, dacă vine acolo Matei, atunci nu vine Ioan.
3. Petru vine dacă și numai dacă nu vine Matei sau nu vine Ioan.

Întrebarea este: pot merge toți la petrecere? Dacă nu, cine poate merge la petrecere fără să încalce nicio regulă?

Mai întâi trebuie să rescriem enunțurile de mai sus în variabile propoziționale și formule. Notăm deci variabilele propoziționale M, I și P (Matei, Ioan, Petru) și ele vor semnifica întotdeauna o propoziție de tipul „Matei merge la petrecere”. Prima regulă am putea-o scrie astfel: M ⇒ I – „dacă M, atunci I”, adică „dacă Matei merge la petrecere, atunci Ioan merge la petrecere”.

A doua regulă o scriem astfel. Regula începe cu enunțul „La petrecere vine Petru sau…”, deci evident vom avea nevoie de o disjuncție. Deocamdată scriem așa: P ∨ … Următoarea parte a enunțului spune: „dacă vine acolo Matei, atunci nu vine Ioan”. Aceasta este o implicație, în care în partea dreaptă trebuie să folosim încă o negație. „nu vine Ioan” = ¬I. Întreaga implicație ar arăta astfel: M ⇒ ¬I. O atașăm la disjuncția anterioară: P ∨ (M ⇒ ¬I).

A treia regulă o scriem astfel: începem cu „Petru vine dacă și numai dacă”. Aceasta înseamnă o echivalență: P ⇔ … Apoi avem „nu vine Matei sau nu vine Ioan”, pe care o scriem astfel: ¬M ∨ ¬I. Le punem cap la cap: (P ⇔ (¬M ∨ ¬I)).

Acum introducem toate formulele în tabel și calculăm valorile:

$$\begin{array}{cccccc}M& I& P& (M\Rightarrow I)& (P\vee (M\Rightarrow \mathrm{\neg }I))& (P\iff (\mathrm{\neg }M\vee \mathrm{\neg }I))\\ 1& 1& 1& 1& 1& 0\\ 1& 1& 0& 1& 0& 1\\ 1& 0& 1& 0& 1& 1\\ 1& 0& 0& 0& 1& 0\\ 0& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0\\ 0& 0& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0\end{array}$$

Întrebarea era dacă pot merge toți trei prietenii la petrecere. Răspunsul îl găsim în primul rând. Acesta corespunde cazului în care merg toți – lucru semnalat prin cele trei unu din primele trei coloane. Sunt îndeplinite toate condițiile? Prima da (coloana a patra), a doua de asemenea (coloana a cincea), dar ultima nu (ultima coloană), acolo este zero. Înseamnă că, dacă merg toți trei, nu va fi îndeplinită a treia condiție.

Căutăm, deci, acele rânduri în care pe pozițiile care reprezintă condițiile (adică ultimele trei coloane) sunt numai unu. Unu înseamnă că condiția este îndeplinită. Vedem că aceasta se întâmplă în două cazuri. Când merg Ioan și Petru, dar nu merge Matei, și apoi când merge doar Petru.

Poți calcula și altfel, adăugând în tabel formula ϕ, care va fi conjuncția celor trei condiții. Deci va arăta astfel: ϕ = ((M ⇒ I) ∧ (P ∨ (M ⇒ ¬I)) ∧ (P ⇔ (¬M ∨ ¬I))). Aceasta reprezintă ceea ce vrem – ca toate formulele (toate condițiile) să fie îndeplinite. Tabelul ar arăta atunci astfel:

$$\begin{array}{ccccccc}M& I& P& (M\Rightarrow I)& (P\vee (M\Rightarrow \mathrm{\neg }I))& (P\iff (\mathrm{\neg }M\vee \mathrm{\neg }I))& \varphi \\ 1& 1& 1& 1& 1& 0& 0\\ 1& 1& 0& 1& 0& 1& 0\\ 1& 0& 1& 0& 1& 1& 0\\ 1& 0& 0& 0& 1& 0& 0\\ 0& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$

Câteva exemple pentru metoda tabelului de adevăr

Pentru că am scris un program care poate construi automat întregul tabel dintr-o formulă dată, trebuie să îl folosesc cum se cuvine, de aceea urmează încă câteva formule rezolvate:

Formula: ((a ∧ ¬b) ∨ (b ∧ (b ⇒ a))). Tabelul:

$$\begin{array}{ccccc}a& b& (a\wedge \mathrm{\neg }b)& (b\wedge (b\Rightarrow a))& ((a\wedge \mathrm{\neg }b)\vee (b\wedge (b\Rightarrow a)))\\ 1& 1& 0& 1& 1\\ 1& 0& 1& 0& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0\end{array}$$

Formula: (a ∨ ¬a) ⇔ (b ∧ ¬b). Tabelul:

$$\begin{array}{ccccc}a& b& (a\vee \mathrm{\neg }a)& (b\wedge \mathrm{\neg }b)& ((a\vee \mathrm{\neg }a)\iff (b\wedge \mathrm{\neg }b))\\ 1& 1& 1& 0& 0\\ 1& 0& 1& 0& 0\\ 0& 1& 1& 0& 0\\ 0& 0& 1& 0& 0\end{array}$$

Formula: ¬(a ∨ b) ⇔ (¬b ∧ ¬a). Tabelul:

$$\begin{array}{ccccc}a& b& \mathrm{\neg }(a\vee b)& (\mathrm{\neg }b\wedge \mathrm{\neg }a)& (\mathrm{\neg }(a\vee b)\iff (\mathrm{\neg }b\wedge \mathrm{\neg }a))\\ 1& 1& 0& 0& 1\\ 1& 0& 0& 0& 1\\ 0& 1& 0& 0& 1\\ 0& 0& 1& 1& 1\end{array}$$

Formula: ϕ = (¬p ⇔ (q ∧ r)) ⇒ (p ∨ ¬(p ∧ q)). Tabelul:

$$\begin{array}{cccccccc}p& q& r& (q\wedge r)& \mathrm{\neg }(p\wedge q)& (\mathrm{\neg }p\iff (q\wedge r))& (p\vee \mathrm{\neg }(p\wedge q))& \varphi \\ 1& 1& 1& 1& 0& 0& 1& 1\\ 1& 1& 0& 0& 0& 1& 1& 1\\ 1& 0& 1& 0& 1& 1& 1& 1\\ 1& 0& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 0& 1& 0& 1& 1\\ 0& 0& 1& 0& 1& 0& 1& 1\\ 0& 0& 0& 0& 1& 0& 1& 1\end{array}$$

Formula: ϕ = ¬(p ⇔ ¬q) ∧ (r ⇒ ¬p) ∧ (p ∨ r). Tabelul:

$$\begin{array}{ccccccc}p& q& r& \mathrm{\neg }(p\iff \mathrm{\neg }q)& (r\Rightarrow \mathrm{\neg }p)& (p\vee r)& \varphi \\ 1& 1& 1& 1& 0& 1& 0\\ 1& 1& 0& 1& 1& 1& 1\\ 1& 0& 1& 0& 0& 1& 0\\ 1& 0& 0& 0& 1& 1& 0\\ 0& 1& 1& 0& 1& 1& 0\\ 0& 1& 0& 0& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$