O colecție progresivă de 20 de exerciții rezolvate despre logica propozițională, concepută pentru a învăța să recunoaștem propozițiile, să formalizăm enunțurile, să construim tabele de adevăr și să utilizăm corect principalii conectori logici.
Fiecare exercițiu este rezolvat pas cu pas, cu atenție acordată semnificației formulelor și nu doar rezultatului final. Obiectivul este să învățăm să raționăm riguros asupra valorii de adevăr a enunțurilor și asupra relațiilor logice dintre propoziții.
Reamintim că o propoziție este un enunț declarativ căruia i se poate atribui, în mod neambiguu, una și numai una dintre valorile de adevăr:
\[ V \quad \text{sau} \quad F \]
Principalii conectori ai logicii propoziționale sunt:
\[ \neg,\quad \land,\quad \lor,\quad \rightarrow,\quad \leftrightarrow \]
Aceștia permit construirea de propoziții compuse pornind de la propoziții mai simple.
Exercițiul 1 — nivel ★☆☆☆☆
Stabilește care dintre următoarele enunțuri sunt propoziții:
\[ \text{a) } 7>3 \]
\[ \text{b) } \text{Închide ușa.} \]
\[ \text{c) } 5+2=10 \]
\[ \text{d) } x+1=4 \]
Soluție
Enunțurile a) și c) sunt propoziții. Enunțurile b) și d) nu sunt propoziții.
Rezolvare
Pentru a stabili dacă un enunț este o propoziție, trebuie să ne întrebăm dacă acesta posedă o valoare de adevăr bine determinată, adică dacă este adevărat sau fals.
Să considerăm primul enunț:
\[ 7>3 \]
Acest enunț este declarativ și putem stabili clar că este adevărat. Deci este o propoziție.
Să considerăm acum:
\[ \text{Închide ușa.} \]
Acesta nu este un enunț declarativ, ci un ordin. Nu are sens să spunem că este adevărat sau fals. Prin urmare, nu este o propoziție.
Al treilea enunț este:
\[ 5+2=10 \]
Este un enunț declarativ. Putem stabili că este fals, deoarece:
\[ 5+2=7 \]
Chiar și un enunț fals poate fi o propoziție: ceea ce contează este să aibă o valoare de adevăr determinată.
În sfârșit, să considerăm:
\[ x+1=4 \]
Acest enunț conține o variabilă liberă, \(x\). Fără a specifica valoarea lui \(x\), nu putem stabili dacă este adevărat sau fals.
De exemplu, dacă \(x=3\), enunțul este adevărat; dacă \(x=0\), enunțul este fals.
Deci, așa cum este scris, nu este o propoziție.
Rezumând:
\[ \text{a) propoziție adevărată} \]
\[ \text{b) nu este propoziție} \]
\[ \text{c) propoziție falsă} \]
\[ \text{d) nu este propoziție} \]
Exercițiul 2 — nivel ★☆☆☆☆
Stabilește dacă următoarele propoziții sunt atomice sau compuse:
\[ \text{a) } 4 \text{ este par} \]
\[ \text{b) } 4 \text{ este par și } 5 \text{ este impar} \]
\[ \text{c) } \text{Nu plouă} \]
\[ \text{d) } \text{Dacă studiez, atunci trec examenul} \]
Soluție
a) atomică; b) compusă; c) compusă; d) compusă.
Rezolvare
O propoziție este atomică atunci când nu conține conectori logici și nu este obținută prin combinarea unor propoziții mai simple.
O propoziție este compusă atunci când conține cel puțin un conector logic, explicit sau implicit.
Să considerăm:
\[ 4 \text{ este par} \]
Această propoziție nu este construită prin combinarea altor propoziții. Este deci atomică.
Să considerăm acum:
\[ 4 \text{ este par și } 5 \text{ este impar} \]
Aici apar două propoziții:
\[ 4 \text{ este par} \]
și:
\[ 5 \text{ este impar} \]
unite prin cuvântul „și”, care corespunde conectorului logic de conjuncție:
\[ \land \]
Deci propoziția este compusă.
Propoziția:
\[ \text{Nu plouă} \]
conține o negație. Dacă notăm cu \(p\) propoziția „plouă”, atunci „nu plouă” se scrie:
\[ \neg p \]
Deci este compusă.
În sfârșit:
\[ \text{Dacă studiez, atunci trec examenul} \]
conține o implicație logică. Dacă punem:
\[ p = \text{studiez} \]
și:
\[ q = \text{trec examenul} \]
atunci propoziția se reprezintă ca:
\[ p \rightarrow q \]
Deci este compusă.
Exercițiul 3 — nivel ★☆☆☆☆
Tradu în simboluri logice următoarea propoziție:
„Marco studiază și Laura citește.”
Folosește:
\[ p = \text{Marco studiază} \]
\[ q = \text{Laura citește} \]
Soluție
\[ p \land q \]
Rezolvare
Propoziția conține două enunțuri simple.
Primul este:
\[ \text{Marco studiază} \]
care este notat cu:
\[ p \]
Al doilea este:
\[ \text{Laura citește} \]
care este notat cu:
\[ q \]
Cuvântul „și” indică faptul că cele două propoziții trebuie să fie adevărate simultan.
În logica propozițională aceasta corespunde conjuncției:
\[ \land \]
Prin urmare, propoziția:
„Marco studiază și Laura citește”
se traduce prin:
\[ p \land q \]
Exercițiul 4 — nivel ★☆☆☆☆
Tradu în simboluri logice următoarea propoziție:
„Dacă plouă, atunci rămân acasă.”
Folosește:
\[ p = \text{plouă} \]
\[ q = \text{rămân acasă} \]
Soluție
\[ p \rightarrow q \]
Rezolvare
Fraza conține o structură condițională:
„Dacă ..., atunci ...”
În logica propozițională această structură este reprezentată prin implicație:
\[ \rightarrow \]
Antecedentul este propoziția care urmează după cuvântul „dacă”:
\[ p = \text{plouă} \]
Consecventul este propoziția care urmează după „atunci”:
\[ q = \text{rămân acasă} \]
Deci propoziția:
„Dacă plouă, atunci rămân acasă”
se traduce prin:
\[ p \rightarrow q \]
Este important de observat că \(p\rightarrow q\) nu înseamnă că \(p\) și \(q\) sunt ambele adevărate, ci că adevărul lui \(p\) obligă la adevărul lui \(q\).
Exercițiul 5 — nivel ★★☆☆☆
Tradu în limbaj natural formula:
\[ \neg p \lor q \]
știind că:
\[ p = \text{studiez} \]
\[ q = \text{trec examenul} \]
Soluție
„Nu studiez sau trec examenul.”
Rezolvare
Formula este:
\[ \neg p \lor q \]
Să analizăm simbolurile unul câte unul.
Propoziția \(p\) înseamnă:
\[ \text{studiez} \]
Deci:
\[ \neg p \]
înseamnă:
\[ \text{nu studiez} \]
Propoziția \(q\) înseamnă:
\[ \text{trec examenul} \]
Conectorul:
\[ \lor \]
reprezintă disjuncția inclusivă, adică „sau”.
De aceea:
\[ \neg p \lor q \]
se citește:
„Nu studiez sau trec examenul.”
În logică, această disjuncție este adevărată și în cazul în care ambele propoziții sunt adevărate, adică atunci când este adevărat că nu studiez și este adevărat că trec examenul.
Exercițiul 6 — nivel ★★☆☆☆
Construiește tabelul de adevăr al formulei:
\[ p \land q \]
Soluție
| \(p\) | \(q\) | \(p \land q\) |
|---|---|---|
| V | V | V |
| V | F | F |
| F | V | F |
| F | F | F |
Rezolvare
Formula conține două variabile propoziționale:
\[ p \qquad \text{și} \qquad q \]
Un tabel de adevăr cu două variabile trebuie să conțină:
\[ 2^2=4 \]
interpretări posibile.
Conectorul:
\[ \land \]
reprezintă conjuncția logică.
Conjuncția este adevărată numai atunci când ambele propoziții sunt adevărate simultan.
Să analizăm cele patru rânduri.
În primul rând:
\[ p=V \qquad q=V \]
ambele propoziții sunt adevărate, deci:
\[ p\land q = V \]
În al doilea rând:
\[ p=V \qquad q=F \]
una dintre propoziții este falsă. În consecință, conjuncția este falsă:
\[ p\land q = F \]
Același lucru se întâmplă în al treilea rând:
\[ p=F \qquad q=V \]
deoarece nu ambele propoziții sunt adevărate.
În sfârșit, în ultimul rând:
\[ p=F \qquad q=F \]
ambele sunt false, deci și conjuncția este falsă.
Conchidem deci că:
\[ p\land q \]
este adevărată exclusiv în cazul:
\[ p=V \qquad q=V \]
Exercițiul 7 — nivel ★★☆☆☆
Construiește tabelul de adevăr al formulei:
\[ p \lor q \]
Soluție
| \(p\) | \(q\) | \(p \lor q\) |
|---|---|---|
| V | V | V |
| V | F | V |
| F | V | V |
| F | F | F |
Rezolvare
Simbolul:
\[ \lor \]
reprezintă disjuncția logică inclusivă.
Disjuncția este adevărată când cel puțin una dintre cele două propoziții este adevărată.
Și în acest caz, deoarece variabilele sunt două, trebuie să considerăm:
\[ 2^2=4 \]
interpretări posibile.
În primul rând:
\[ p=V \qquad q=V \]
ambele propoziții sunt adevărate. Deci:
\[ p\lor q = V \]
În al doilea rând:
\[ p=V \qquad q=F \]
cel puțin una dintre propoziții este adevărată, deci:
\[ p\lor q = V \]
În al treilea rând:
\[ p=F \qquad q=V \]
și aici cel puțin una dintre propoziții este adevărată. Prin urmare:
\[ p\lor q = V \]
Doar în ultimul rând:
\[ p=F \qquad q=F \]
ambele propoziții sunt false.
În consecință:
\[ p\lor q = F \]
Conchidem deci că disjuncția inclusivă este falsă numai atunci când ambele propoziții sunt false.
Exercițiul 8 — nivel ★★☆☆☆
Construiește tabelul de adevăr al formulei:
\[ p \rightarrow q \]
Soluție
| \(p\) | \(q\) | \(p \rightarrow q\) |
|---|---|---|
| V | V | V |
| V | F | F |
| F | V | V |
| F | F | V |
Rezolvare
Implicația:
\[ p\rightarrow q \]
se citește:
„dacă \(p\), atunci \(q\)”.
Acest conector este adesea cel mai delicat de interpretat corect.
Implicația este falsă exclusiv în cazul în care:
\[ p=V \]
și simultan:
\[ q=F \]
Într-adevăr, în acest caz antecedentul este adevărat, dar consecventul este fals, deci promisiunea logică conținută în implicație este încălcată.
Să analizăm cele patru posibilități.
Primul rând:
\[ p=V \qquad q=V \]
Implicația este adevărată.
Al doilea rând:
\[ p=V \qquad q=F \]
Acesta este singurul caz în care implicația este falsă:
\[ p\rightarrow q = F \]
Al treilea rând:
\[ p=F \qquad q=V \]
Implicația este considerată adevărată.
Într-adevăr, când antecedentul este fals, implicația nu este încălcată.
Al patrulea rând:
\[ p=F \qquad q=F \]
Și aici implicația este adevărată, tot pentru că antecedentul este fals.
Conchidem deci că:
\[ p\rightarrow q \]
este falsă numai când:
\[ p=V \qquad \text{și} \qquad q=F \]
Exercițiul 9 — nivel ★★★☆☆
Determină valoarea de adevăr a formulei:
\[ (p\land q)\rightarrow r \]
în interpretarea:
\[ p=V,\qquad q=F,\qquad r=F \]
Soluție
Formula este adevărată.
Rezolvare
Să considerăm formula:
\[ (p\land q)\rightarrow r \]
Pentru a evalua corect formula trebuie să procedăm din interior spre exterior.
Subformula cea mai internă este:
\[ p\land q \]
Substituim valorile atribuite:
\[ p=V,\qquad q=F \]
Obținem:
\[ V\land F \]
O conjuncție este adevărată numai dacă ambele propoziții sunt adevărate.
Deoarece una dintre ele este falsă, rezultă:
\[ p\land q = F \]
Formula inițială devine deci:
\[ F\rightarrow F \]
Reamintim că o implicație este falsă numai când antecedentul este adevărat și consecventul este fals.
Aici antecedentul este fals.
Prin urmare:
\[ F\rightarrow F = V \]
Conchidem deci că formula este adevărată.
Exercițiul 10 — nivel ★★★☆☆
Verifică prin tabel de adevăr că:
\[ \neg(p\land q)\equiv \neg p \lor \neg q \]
Soluție
Cele două formule au aceleași valori de adevăr în orice interpretare, deci sunt logic echivalente.
Rezolvare
Pentru a demonstra că două formule sunt logic echivalente trebuie să verificăm că iau întotdeauna aceeași valoare de adevăr.
Construim deci un tabel de adevăr complet.
| \(p\) | \(q\) | \(p\land q\) | \(\neg(p\land q)\) | \(\neg p\) | \(\neg q\) | \(\neg p\lor \neg q\) |
|---|---|---|---|---|---|---|
| V | V | V | F | F | F | F |
| V | F | F | V | F | V | V |
| F | V | F | V | V | F | V |
| F | F | F | V | V | V | V |
Observăm acum ultimele două coloane:
\[ \neg(p\land q) \]
și:
\[ \neg p\lor\neg q \]
Ele coincid în toate rândurile tabelului.
În consecință:
\[ \neg(p\land q)\equiv \neg p\lor\neg q \]
Această echivalență poartă numele de prima lege De Morgan.
Exercițiul 11 — nivel ★★★☆☆
Verifică prin tabel de adevăr că:
\[ p\rightarrow q \equiv \neg p \lor q \]
Soluție
Cele două formule au aceleași valori de adevăr în orice interpretare, deci sunt logic echivalente.
Rezolvare
Vrem să comparăm cele două formule:
\[ p\rightarrow q \]
și:
\[ \neg p \lor q \]
Două formule sunt logic echivalente dacă iau aceeași valoare de adevăr în toate interpretările posibile.
Deoarece apar două variabile propoziționale, \(p\) și \(q\), trebuie să considerăm:
\[ 2^2=4 \]
interpretări.
| \(p\) | \(q\) | \(p\rightarrow 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 |
Comparăm acum coloana lui \(p\rightarrow q\) cu coloana lui \(\neg p\lor q\).
Valorile sunt identice în fiecare rând:
\[ V,\ F,\ V,\ V \]
Deci cele două formule sunt logic echivalente:
\[ p\rightarrow q \equiv \neg p \lor q \]
Această echivalență este foarte importantă deoarece permite eliminarea implicației și rescrierea ei folosind doar negație și disjuncție.
Exercițiul 12 — nivel ★★★☆☆
Stabilește dacă formula:
\[ p\lor\neg p \]
este o tautologie, o contradicție sau o formulă contingentă.
Soluție
Formula este o tautologie.
Rezolvare
O formulă este o tautologie dacă este adevărată în orice interpretare.
O formulă este o contradicție dacă este falsă în orice interpretare.
O formulă este contingentă dacă este adevărată în unele interpretări și falsă în altele.
Considerăm:
\[ p\lor\neg p \]
Formula conține o singură variabilă propozițională, deci trebuie să considerăm:
\[ 2^1=2 \]
interpretări.
| \(p\) | \(\neg p\) | \(p\lor\neg p\) |
|---|---|---|
| V | F | V |
| F | V | V |
În primul rând \(p\) este adevărată și deci disjuncția este adevărată.
În al doilea rând \(p\) este falsă, dar \(\neg p\) este adevărată; deci și în acest caz disjuncția este adevărată.
Formula este adevărată în toate interpretările.
Prin urmare:
\[ p\lor\neg p \]
este o tautologie.
Această tautologie poartă numele de principiul terțului exclus.
Exercițiul 13 — nivel ★★★☆☆
Stabilește dacă formula:
\[ p\land\neg p \]
este o tautologie, o contradicție sau o formulă contingentă.
Soluție
Formula este o contradicție.
Rezolvare
Considerăm formula:
\[ p\land\neg p \]
Ea afirmă simultan \(p\) și negația sa.
Construim tabelul de adevăr.
| \(p\) | \(\neg p\) | \(p\land\neg p\) |
|---|---|---|
| V | F | F |
| F | V | F |
În primul rând \(p\) este adevărată, dar \(\neg p\) este falsă. Conjuncția este deci falsă.
În al doilea rând \(p\) este falsă, în timp ce \(\neg p\) este adevărată. Și în acest caz conjuncția este falsă.
Formula este falsă în orice interpretare.
Prin urmare:
\[ p\land\neg p \]
este o contradicție.
Această lege poartă numele de principiul non-contradicției.
Exercițiul 14 — nivel ★★★★☆
Stabilește dacă formula:
\[ p\rightarrow(p\lor q) \]
este o tautologie, o contradicție sau o formulă contingentă.
Soluție
Formula este o tautologie.
Rezolvare
Pentru a clasifica formula trebuie să construim tabelul său de adevăr complet.
Formula este:
\[ p\rightarrow(p\lor q) \]
Subformula internă de calculat este:
\[ p\lor q \]
Construim tabelul:
| \(p\) | \(q\) | \(p\lor q\) | \(p\rightarrow(p\lor q)\) |
|---|---|---|---|
| V | V | V | V |
| V | F | V | V |
| F | V | V | V |
| F | F | F | V |
Analizăm coloana finală.
Ea conține numai valori adevărate:
\[ V,\ V,\ V,\ V \]
Deci formula este adevărată în orice interpretare.
Prin urmare:
\[ p\rightarrow(p\lor q) \]
este o tautologie.
Din punct de vedere intuitiv, dacă \(p\) este adevărată, atunci este cu siguranță adevărată și disjuncția \(p\lor q\), deoarece o disjuncție inclusivă este adevărată când cel puțin una dintre componentele sale este adevărată.
Exercițiul 15 — nivel ★★★★☆
Stabilește dacă formula:
\[ (p\land q)\rightarrow p \]
este o tautologie, o contradicție sau o formulă contingentă.
Soluție
Formula este o tautologie.
Rezolvare
Formula de analizat este:
\[ (p\land q)\rightarrow p \]
Ea conține o conjuncție în primul membru al implicației. Înainte de a evalua implicația, trebuie deci să calculăm:
\[ p\land q \]
Construim tabelul de adevăr complet:
| \(p\) | \(q\) | \(p\land q\) | \((p\land q)\rightarrow p\) |
|---|---|---|---|
| V | V | V | V |
| V | F | F | V |
| F | V | F | V |
| F | F | F | V |
Observăm coloana finală:
\[ V,\ V,\ V,\ V \]
Formula este adevărată în toate interpretările.
Deci:
\[ (p\land q)\rightarrow p \]
este o tautologie.
Semnificația logică este simplă: dacă sunt adevărate simultan \(p\) și \(q\), atunci în special este adevărată \(p\).
Exercițiul 16 — nivel ★★★★☆
Verifică dacă:
\[ p\land q \models p \]
Soluție
Da, \(p\) este consecință logică a lui \(p\land q\).
Rezolvare
Scrierea:
\[ p\land q \models p \]
înseamnă că orice interpretare care face adevărată premisa \(p\land q\) face adevărată și concluzia \(p\).
Trebuie deci să considerăm interpretările în care:
\[ p\land q \]
este adevărată.
O conjuncție este adevărată numai când ambii membrii săi sunt adevărați. Deci:
\[ p\land q = V \quad \Longleftrightarrow \quad p=V \ \text{și}\ q=V \]
În orice interpretare în care \(p\land q\) este adevărată, rezultă în mod necesar:
\[ p=V \]
Deci nu există nicio interpretare în care premisa să fie adevărată și concluzia să fie falsă.
Prin urmare:
\[ p\land q \models p \]
Exercițiul 17 — nivel ★★★★☆
Verifică dacă:
\[ p \models p\lor q \]
Soluție
Da, \(p\lor q\) este consecință logică a lui \(p\).
Rezolvare
Scrierea:
\[ p \models p\lor q \]
înseamnă că orice interpretare care face adevărată premisa \(p\) trebuie să facă adevărată și concluzia \(p\lor q\).
Presupunem deci că premisa este adevărată:
\[ p=V \]
Concluzia este:
\[ p\lor q \]
O disjuncție inclusivă este adevărată când cel puțin una dintre cele două propoziții este adevărată.
Deoarece \(p\) este deja adevărată, disjuncția:
\[ p\lor q \]
este în mod necesar adevărată, indiferent de valoarea lui \(q\).
Într-adevăr:
\[ V\lor V=V \]
și:
\[ V\lor F=V \]
Deci orice model al lui \(p\) este și model al lui \(p\lor q\).
Prin urmare:
\[ p \models p\lor q \]
Exercițiul 18 — nivel ★★★★★
Verifică dacă:
\[ p\rightarrow q,\ p \models q \]
Soluție
Da, \(q\) este consecință logică a premiselor \(p\rightarrow q\) și \(p\).
Rezolvare
Scrierea:
\[ p\rightarrow q,\ p \models q \]
înseamnă că orice interpretare care face adevărate ambele premise trebuie să facă adevărată și concluzia.
Premisele sunt:
\[ p\rightarrow q \]
și:
\[ p \]
Presupunem deci că ambele sunt adevărate.
Din a doua premisă știm că:
\[ p=V \]
În plus, prima premisă afirmă că:
\[ p\rightarrow q=V \]
Reamintim că o implicație cu antecedent adevărat este adevărată numai dacă și consecventul este adevărat.
Deoarece antecedentul \(p\) este adevărat, pentru a menține implicația adevărată trebuie în mod necesar ca:
\[ q=V \]
Deci orice interpretare care face adevărate premisele face adevărată și concluzia.
Prin urmare:
\[ p\rightarrow q,\ p \models q \]
Aceasta este forma semantică a modus ponens.
Exercițiul 19 — nivel ★★★★★
Redu formula următoare folosind echivalențele logice:
\[ \neg(p\rightarrow q) \]
Soluție
\[ \neg(p\rightarrow q)\equiv p\land\neg q \]
Rezolvare
Pornim de la formula:
\[ \neg(p\rightarrow q) \]
Pentru a o simplifica, eliminăm mai întâi implicația.
Reamintim echivalența fundamentală:
\[ p\rightarrow q \equiv \neg p\lor q \]
Substituind obținem:
\[ \neg(p\rightarrow q)\equiv \neg(\neg p\lor q) \]
Acum aplicăm legea De Morgan:
\[ \neg(A\lor B)\equiv \neg A\land\neg B \]
În cazul nostru:
\[ A=\neg p \qquad \text{și} \qquad B=q \]
Deci:
\[ \neg(\neg p\lor q)\equiv \neg\neg p\land\neg q \]
În final folosim dubla negație:
\[ \neg\neg p\equiv p \]
Obținem:
\[ \neg(p\rightarrow q)\equiv p\land\neg q \]
Rezultatul este coerent și cu semnificația implicației: \(p\rightarrow q\) este falsă numai când \(p\) este adevărată și \(q\) este falsă.
Exercițiul 20 — nivel ★★★★★
Transformă formula:
\[ p\rightarrow(q\lor r) \]
într-o formulă echivalentă fără conectorul \(\rightarrow\).
Soluție
\[ p\rightarrow(q\lor r)\equiv \neg p\lor q\lor r \]
Rezolvare
Formula de plecare este:
\[ p\rightarrow(q\lor r) \]
Vrem să eliminăm conectorul de implicație.
Folosim echivalența:
\[ A\rightarrow B\equiv \neg A\lor B \]
În cazul nostru:
\[ A=p \]
și:
\[ B=q\lor r \]
Aplicând echivalența obținem:
\[ p\rightarrow(q\lor r)\equiv \neg p\lor(q\lor r) \]
Datorită asociativității disjuncției, putem omite parantezele:
\[ \neg p\lor(q\lor r)\equiv \neg p\lor q\lor r \]
Deci formula echivalentă fără implicație este:
\[ \neg p\lor q\lor r \]
Această formulă este o clauză disjunctivă, adică o disjuncție de literali, și poate fi văzută și ca o formă normală conjunctivă compusă dintr-o singură clauză.