Logica propozițională (sau logica enunțurilor) constituie nivelul fundamental al logicii matematice și furnizează aparatul formal necesar analizei riguroase a raționamentului deductiv. Ea studiază propozițiile, adică enunțurile declarative cărora li se poate asocia în mod univoc o valoare de adevăr, precum și combinațiile acestora prin intermediul conectorilor logici.
În această lucrare prezentăm o expunere sistematică și completă: limbaj formal, sintaxă, semantică adevăr-funcțională, echivalențe și legi fundamentale, tautologii și consecință logică, forme normale, sisteme deductive și teoremele metalogice de corectitudine și completitudine.
Cuprins
- Propoziții și Limbaj Formal
- Sintaxa Formulelor Bine Formate
- Semantică și Interpretări
- Conectori Logici și Completitudine Funcțională
- Tabele de Adevăr
- Echivalențe Logice
- Legi Fundamentale
- Tautologii, Satisfiabilitate și Consecință Logică
- Forme Normale (FNC și FND)
- Sisteme Deductive
- Corectitudine și Completitudine
- Exemple Avansate
Propoziții și Limbaj Formal
O propoziție (sau enunț) este o frază declarativă cu sens deplin care, în virtutea principiului bivalenței, primește în mod univoc una și numai una dintre cele două valori de adevăr: adevărat (\(A\) sau \(1\)) sau fals (\(F\) sau \(0\)).
O propoziție se numește atomică (sau enunț simplu) dacă nu conține în interior alte propoziții legate prin operatori logici. Propozițiile obținute prin combinarea propozițiilor atomice cu ajutorul conectorilor logici se numesc compuse (sau moleculare).
Se fixează o mulțime numărabilă de variabile propoziționale, notate în general cu litere latine mici:
\[ \mathcal{P} = \{p_1, p_2, p_3, \dots\} = \{p, q, r, \dots\} \]
Limbajul logicii propoziționale \(\mathcal{L}\) este alcătuit din următoarele simboluri:
- variabilele propoziționale din \(\mathcal{P}\);
- conectorii logici: \(\neg,\ \land,\ \lor,\ \rightarrow,\ \leftrightarrow\);
- simbolurile auxiliare: paranteze rotunde \((,\ )\).
Sintaxa Formulelor Bine Formate
Mulțimea \(\mathcal{F}\) a formulelor bine formate (fbf) este cea mai mică mulțime de șiruri de caractere peste alfabetul lui \(\mathcal{L}\), definită inductiv prin următoarele clauze:
- Clauza de bază: orice variabilă propozițională \(p \in \mathcal{P}\) este o fbf;
- Clauze inductive:
- dacă \(A \in \mathcal{F}\), atunci \((\neg A) \in \mathcal{F}\);
- dacă \(A, B \in \mathcal{F}\), atunci \((A \land B),\ (A \lor B),\ (A \rightarrow B),\ (A \leftrightarrow B) \in \mathcal{F}\);
- Clauza de închidere: niciun alt șir de caractere nu este o fbf.
În notație BNF, gramatica limbajului se scrie:
\[ A ::= p \mid (\neg A) \mid (A \land A) \mid (A \lor A) \mid (A \rightarrow A) \mid (A \leftrightarrow A) \]
Prin convenție de precedență, conectorii au următoarea ordine descrescătoare de precedență următoarea ordine descrescătoare de legătură, care permite omiterea parantezelor fără ambiguitate:
\[ \neg \;>\; \land \;>\; \lor \;>\; \rightarrow \;>\; \leftrightarrow \]
Observație. În timp ce precedența lui \(\neg\) față de toți ceilalți conectori și cea a lui \(\rightarrow,\ \leftrightarrow\) ca mai puțin legători sunt universal acceptate, ordinea relativă dintre \(\land\) și \(\lor\) nu este uniformă în literatură: unii autori (prin analogie cu \(\cdot\) și \(+\) din algebra Boole) acordă lui \(\land\) prioritate superioară față de \(\lor\), în timp ce alții (de exemplu Mendelson) le consideră la același nivel și impun paranteze explicite. Prin urmare, pentru a evita orice ambiguitate, este bună practică să se expliciteze parantezele între \(\land\) și \(\lor\): se va scrie, de exemplu, \( (A \land B) \lor C \) în locul lui \( A \land B \lor C \).
Principiul inducției structurale asupra fbf afirmă că, pentru a demonstra o proprietate \(P\) pentru orice \(A \in \mathcal{F}\), este suficient să se verifice:
- (baza) \(P\) are loc pentru orice propoziție atomică;
- (pasul inductiv) \(P\) se păstrează prin aplicarea fiecărui conector.
Semantică și Interpretări
Semantica logicii propoziționale este vero-funcțională: valoarea de adevăr a unei formule compuse este determinată în mod univoc de valorile de adevăr ale subformulelor sale.
O interpretare (sau evaluare, ori atribuire) este o funcție:
\[ v : \mathcal{P} \to \{A, F\} \]
care se extinde în mod unic la o funcție \(\hat{v} : \mathcal{F} \to \{A, F\}\) prin intermediul următoarelor clauze recursive:
- \( \hat{v}(\neg A) = A \iff \hat{v}(A) = F \);
- \( \hat{v}(A \land B) = A \iff \hat{v}(A) = A \text{ și } \hat{v}(B) = A \);
- \( \hat{v}(A \lor B) = A \iff \hat{v}(A) = A \text{ sau } \hat{v}(B) = A \) (eventual ambele);
- \( \hat{v}(A \rightarrow B) = F \iff \hat{v}(A) = A \text{ și } \hat{v}(B) = F \);
- \( \hat{v}(A \leftrightarrow B) = A \iff \hat{v}(A) = \hat{v}(B) \).
Dacă o formulă conține \(n\) variabile propoziționale distincte, numărul interpretărilor posibile (restrânse la acele variabile) este \(2^n\).
Observație importantă. Conectorul \(\lor\) reprezintă disjuncția inclusivă (corespunzătoare latinescului vel): \(A \lor B\) este adevărată atunci când cel puțin una dintre cele două propoziții este adevărată, inclusiv cazul în care ambele sunt adevărate. Ea trebuie distinsă de disjuncția exclusivă (corespunzătoare latinescului aut, notată \(\oplus\) sau XOR), în care \(A \oplus B\) este adevărată dacă și numai dacă \(A\) și \(B\) au valori de adevăr diferite. În simboluri:
\[ A \oplus B \;\equiv\; (A \lor B) \land \neg(A \land B) \;\equiv\; \neg(A \leftrightarrow B) \]
În limba română, conjuncția „sau" este ambiguă între cele două sensuri; logica formală elimină această ambiguitate adoptând în mod implicit lectura inclusivă.
Conectori Logici și Completitudine Funcțională
Conectorii logici sunt operatori adevăr-funcționali, adică funcții \(\{A,F\}^n \to \{A,F\}\):
- negația \(\neg\) este un operator unar;
- conjuncția \(\land\), disjuncția \(\lor\), implicația \(\rightarrow\) și dubla implicație (sau bicondiționalul) \(\leftrightarrow\) sunt operatori binari.
O mulțime de conectori se numește funcțional completă dacă orice funcție de adevăr \(\{A,F\}^n \to \{A,F\}\) poate fi exprimată prin combinații ale acestor conectori. Sunt mulțimi funcțional complete:
\[ \{\neg, \land, \lor\}, \quad \{\neg, \land\}, \quad \{\neg, \lor\}, \quad \{\neg, \rightarrow\} \]
Mai mult, există conectori binari singulari suficienți pentru a exprima orice funcție de adevăr: NAND a lui Sheffer, notată \(\uparrow\), și NOR a lui Peirce, notată \(\downarrow\).
Definițiile semantice justifică următoarele reduceri, care arată că \(\rightarrow\) și \(\leftrightarrow\) sunt definibile pornind de la \(\{\neg, \land, \lor\}\):
\[ A \rightarrow B \equiv \neg A \lor B \]
\[ A \leftrightarrow B \equiv (A \rightarrow B) \land (B \rightarrow A) \equiv (A \land B) \lor (\neg A \land \neg B) \]
Tabele de Adevăr
Un tabel de adevăr este reprezentarea tabelară a funcției vero-funcționale asociate unei formule. Pentru o formulă cu \(n\) variabile distincte, tabelul are \(2^n\) linii, câte una pentru fiecare interpretare posibilă.
Tabelele de adevăr ale conectorilor fundamentali sunt:
| \(A\) | \(B\) | \(\neg A\) | \(A \land B\) | \(A \lor B\) | \(A \rightarrow B\) | \(A \leftrightarrow B\) |
|---|---|---|---|---|---|---|
| A | A | F | A | A | A | A |
| A | F | F | F | A | F | F |
| F | A | A | F | A | A | F |
| F | F | A | F | F | A | A |
Se observă că implicația \(A \rightarrow B\) este falsă exclusiv în cazul în care antecedentul \(A\) este adevărat și consecventul \(B\) este fals: aceasta este singura linie în care ea ia valoarea \(F\).
Echivalențe Logice
Două formule \(A\) și \(B\) se numesc logic echivalente, notație \(A \equiv B\), dacă iau aceeași valoare de adevăr în orice interpretare:
\[ A \equiv B \iff \forall v,\ \hat{v}(A) = \hat{v}(B) \]
Relația \(\equiv\) este o relație de echivalență pe mulțimea \(\mathcal{F}\) (reflexivă, simetrică, tranzitivă) și este o congruență: are loc teorema de substituție, conform căreia dacă \(A \equiv B\) și \(C[A]\) este o formulă ce conține \(A\) ca subformulă, atunci \(C[A] \equiv C[B]\), unde \(C[B]\) este formula obținută înlocuind (o apariție a) lui \(A\) cu \(B\) în \(C\).
Este esențial să se distingă \(\equiv\) (relație metalingvistică între formule) de \(\leftrightarrow\) (conector al limbajului): are loc
\[ A \equiv B \iff \models A \leftrightarrow B \]
adică \(A\) și \(B\) sunt logic echivalente dacă și numai dacă formula \(A \leftrightarrow B\) este o tautologie.
Legi Fundamentale
Următoarele echivalențe, demonstrabile prin tabele de adevăr, constituie legile fundamentale ale calculului propozițional (cu \(\top\) se notează o tautologie, cu \(\bot\) o contradicție):
- Idempotența: \(A \land A \equiv A\), \(\quad A \lor A \equiv A\)
- Comutativitatea: \(A \land B \equiv B \land A\), \(\quad A \lor B \equiv B \lor A\)
- Asociativitatea: \((A \land B) \land C \equiv A \land (B \land C)\), și analog pentru \(\lor\)
- Distributivitatea: \(A \land (B \lor C) \equiv (A \land B) \lor (A \land C)\), \(\quad A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)\)
- Dubla negație: \(\neg \neg A \equiv A\)
- Legile lui De Morgan: \(\neg(A \land B) \equiv \neg A \lor \neg B\), \(\quad \neg(A \lor B) \equiv \neg A \land \neg B\)
- Absorbția: \(A \land (A \lor B) \equiv A\), \(\quad A \lor (A \land B) \equiv A\)
- Identitatea: \(A \land \top \equiv A\), \(\quad A \lor \bot \equiv A\)
- Dominarea: \(A \lor \top \equiv \top\), \(\quad A \land \bot \equiv \bot\)
- Terțul exclus: \(A \lor \neg A \equiv \top\)
- Non-contradicția: \(A \land \neg A \equiv \bot\)
- Contrapozitivul: \(A \rightarrow B \equiv \neg B \rightarrow \neg A\)
- Exportarea: \((A \land B) \rightarrow C \equiv A \rightarrow (B \rightarrow C)\)
Tautologii, Satisfiabilitate și Consecință Logică
Fie \(A \in \mathcal{F}\). Se spune că:
- \(A\) este o tautologie (sau formulă logic validă), notație \(\models A\), dacă \(\hat{v}(A) = A\) pentru orice interpretare \(v\);
- \(A\) este o contradicție (sau formulă nesatisfiabilă) dacă \(\hat{v}(A) = F\) pentru orice \(v\);
- \(A\) este satisfiabilă dacă există cel puțin o interpretare \(v\) astfel încât \(\hat{v}(A) = A\);
- \(A\) este contingentă dacă este satisfiabilă, dar nu este o tautologie.
Cele patru categorii sunt legate prin:
\[ A \text{ este tautologie} \iff \neg A \text{ este contradicție} \]
Fie \(\Gamma \subseteq \mathcal{F}\) o mulțime de formule (eventual infinită) și \(B \in \mathcal{F}\). Se spune că \(B\) este consecință logică (semantică) a lui \(\Gamma\), notație
\[ \Gamma \models B \]
dacă pentru orice interpretare \(v\) care satisface \(\hat{v}(A) = A\) pentru orice \(A \in \Gamma\), are loc \(\hat{v}(B) = A\). Cu alte cuvinte: orice model al lui \(\Gamma\) este și un model al lui \(B\).
Teorema de deducție semantică:
\[ \Gamma \cup \{A\} \models B \iff \Gamma \models A \rightarrow B \]
În particular, luând \(\Gamma = \emptyset\), obținem că \(A \models B\) dacă și numai dacă \(\models A \rightarrow B\).
Forme Normale (FNC și FND)
Se numește literal o variabilă propozițională sau negația ei: \(p\) sau \(\neg p\). În consecință:
- o clauză disjunctivă este o disjuncție de literali: \(\ell_1 \lor \ell_2 \lor \dots \lor \ell_k\);
- o clauză conjunctivă este o conjuncție de literali: \(\ell_1 \land \ell_2 \land \dots \land \ell_k\).
O formulă este în:
- Formă Normală Conjunctivă (FNC) dacă este o conjuncție de clauze disjunctive;
- Formă Normală Disjunctivă (FND) dacă este o disjuncție de clauze conjunctive.
Teoremă (existența formelor normale): orice formulă \(A \in \mathcal{F}\) este logic echivalentă cu o formulă în FNC și cu o formulă în FND.
Procedura de reducere:
- eliminarea bicondiționalului: \(A \leftrightarrow B \equiv (A \rightarrow B) \land (B \rightarrow A)\);
- eliminarea implicației: \(A \rightarrow B \equiv \neg A \lor B\);
- aducerea negațiilor direct în fața variabilelor (prin legile lui De Morgan și dubla negație), obținând forma normală negativă (FNN);
- aplicarea distributivității pentru a obține forma dorită: \(\lor\) față de \(\land\) pentru FND, \(\land\) față de \(\lor\) pentru FNC.
Exemplu:
\[ A \rightarrow (B \lor C) \;\equiv\; \neg A \lor (B \lor C) \;\equiv\; \neg A \lor B \lor C \]
rezultatul este simultan în FNC (o singură clauză disjunctivă) și în FND (disjuncție de clauze conjunctive reduse la literali individuali).
Sisteme Deductive
Un sistem deductiv (sau calcul logic) este un aparat pur sintactic alcătuit din axiome și reguli de inferență, care permite derivarea formulelor din premise fără a face referire la semantică. Noțiunea fundamentală este cea de derivabilitate: se scrie
\[ \Gamma \vdash A \]
pentru a indica că există o derivare a formulei \(A\) din premisele \(\Gamma\) în sistemul considerat.
Cele mai răspândite sisteme deductive pentru logica propozițională sunt:
- Sisteme axiomatice (de tip Hilbert-Frege): câteva scheme axiomatice și o singură regulă (modus ponens);
- Deducția naturală (Gentzen, Prawitz): reguli de introducere și eliminare pentru fiecare conector;
- Calculul secvenților (Gentzen): reguli pentru secvenți de forma \(\Gamma \Rightarrow \Delta\);
- Tablouri semantice (Beth, Smullyan): metodă de refutare prin arbori.
Cele mai importante reguli de inferență sunt:
Modus Ponens (eliminarea lui \(\rightarrow\)):
\[ \dfrac{A \qquad A \rightarrow B}{B} \]
Modus Tollens (contrapozitivul):
\[ \dfrac{A \rightarrow B \qquad \neg B}{\neg A} \]
Silogismul ipotetic (tranzitivitatea implicației):
\[ \dfrac{A \rightarrow B \qquad B \rightarrow C}{A \rightarrow C} \]
Silogismul disjunctiv:
\[ \dfrac{A \lor B \qquad \neg A}{B} \]
Introducerea și eliminarea conjuncției:
\[ \dfrac{A \qquad B}{A \land B} \qquad\qquad \dfrac{A \land B}{A} \qquad\qquad \dfrac{A \land B}{B} \]
Reducerea la absurd (demonstrație prin contradicție):
\[ \dfrac{\Gamma, \neg A \vdash \bot}{\Gamma \vdash A} \]
Corectitudine și Completitudine
Relația dintre derivabilitatea sintactică \(\vdash\) și consecința semantică \(\models\) este exprimată de cele două teoreme metalogice fundamentale ale logicii propoziționale.
Teorema de corectitudine (soundness): pentru orice \(\Gamma \subseteq \mathcal{F}\) și orice \(A \in \mathcal{F}\):
\[ \Gamma \vdash A \;\Longrightarrow\; \Gamma \models A \]
Tot ceea ce este derivabil sintactic este în mod efectiv o consecință semantică a premiselor.
Teorema de completitudine (Post, 1921): pentru orice \(\Gamma \subseteq \mathcal{F}\) și orice \(A \in \mathcal{F}\):
\[ \Gamma \models A \;\Longrightarrow\; \Gamma \vdash A \]
Orice consecință semantică poate fi efectiv derivată în cadrul calculului.
Combinând cele două rezultate, se obține echivalența dintre sintaxă și semantică:
\[ \Gamma \vdash A \iff \Gamma \models A \]
Acestora li se adaugă alte două rezultate metalogice de importanță:
- Teorema de compacitate: \(\Gamma\) este satisfiabilă dacă și numai dacă orice submulțime finită a sa este satisfiabilă;
- Decidabilitatea: există un algoritm (de exemplu, metoda tabelelor de adevăr) care, în timp finit, stabilește dacă o formulă dată este sau nu o tautologie.
Exemple Avansate
Exemplul 1 — Reducere la formă normală
Să se reducă \( (A \rightarrow B) \land \neg B \) în FNC și FND.
Rezultat
FNC: \( (\neg A \lor B) \land \neg B \) — FND: \( \neg A \land \neg B \)
Rezolvare
Eliminăm implicația prin \( A \rightarrow B \equiv \neg A \lor B \):
\[ (A \rightarrow B) \land \neg B \;\equiv\; (\neg A \lor B) \land \neg B \]
care se află deja în FNC (conjuncție a două clauze disjunctive). Pentru a obține FND aplicăm distributivitatea lui \(\land\) față de \(\lor\):
\[ (\neg A \lor B) \land \neg B \;\equiv\; (\neg A \land \neg B) \lor (B \land \neg B) \;\equiv\; \neg A \land \neg B \]
deoarece \( B \land \neg B \equiv \bot \) prin legea non-contradicției. Rezultatul \( \neg A \land \neg B \) este o FND degenerată: este vorba de o singură clauză conjunctivă, interpretabilă ca disjuncție cu un singur termen. Prin convenție, o singură clauză conjunctivă se consideră în FND (după cum o singură clauză disjunctivă se consideră în FNC), chiar dacă nu apare în mod explicit niciun \(\lor\).
Exemplul 2 — Verificarea unei tautologii (silogismul ipotetic)
Să se demonstreze că \( ((A \rightarrow B) \land (B \rightarrow C)) \rightarrow (A \rightarrow C) \) este o tautologie.
Rezolvare
Procedăm prin reducere la absurd: presupunem că există o interpretare \(v\) care face formula falsă. Pentru ca o implicație să fie falsă, antecedentul trebuie să fie adevărat și consecventul fals, deci:
- \( \hat{v}((A \rightarrow B) \land (B \rightarrow C)) = A \), deci \( \hat{v}(A \rightarrow B) = A \) și \( \hat{v}(B \rightarrow C) = A \);
- \( \hat{v}(A \rightarrow C) = F \), de unde \( \hat{v}(A) = A \) și \( \hat{v}(C) = F \).
Din \( \hat{v}(A) = A \) și \( \hat{v}(A \rightarrow B) = A \) rezultă \( \hat{v}(B) = A \) (altfel implicația ar fi falsă). Din \( \hat{v}(B) = A \) și \( \hat{v}(B \rightarrow C) = A \) rezultă \( \hat{v}(C) = A \), contradicție cu \( \hat{v}(C) = F \). Prin urmare formula este o tautologie.
Exemplul 3 — Consecință logică și regula de rezoluție
Să se verifice că \( \{A \lor B,\ \neg A \lor C\} \models B \lor C \).
Rezolvare
Fie \(v\) o interpretare care satisface ambele premise. Distingem două cazuri în funcție de valoarea lui \( \hat{v}(A) \):
- dacă \( \hat{v}(A) = A \), atunci din \( \hat{v}(\neg A \lor C) = A \) rezultă în mod necesar \( \hat{v}(C) = A \), și deci \( \hat{v}(B \lor C) = A \);
- dacă \( \hat{v}(A) = F \), atunci din \( \hat{v}(A \lor B) = A \) rezultă \( \hat{v}(B) = A \), și deci \( \hat{v}(B \lor C) = A \).
În ambele cazuri \( \hat{v}(B \lor C) = A \), ceea ce demonstrează consecința logică. Acest principiu constituie regula de rezoluție, la baza metodelor automate de demonstrare: din clauzele \( A \lor B \) și \( \neg A \lor C \) se deduce rezolventa \( B \lor C \).
Logica propozițională reprezintă primul nivel de formalizare a raționamentului matematic. Cu toată expresivitatea ei limitată — incapabilă să descrie structura internă a propozițiilor — ea furnizează instrumentele conceptuale fundamentale pentru abordarea logicii de ordinul întâi, a teoriilor axiomatice, a metalogicii și a structurilor algebrice asociate (algebre Boole, rețele). Stăpânirea ei este o condiție prealabilă indispensabilă pentru orice studiu riguros al matematicii și al informaticii teoretice.