Teorie

Teorie: formule echivalente și negarea enunțurilor

Publicat · de

Deschide PDF

Rezumat

Două formule sunt echivalente când au aceleași valori de adevăr pe fiecare linie a tabelului, iar o tautologie este adevărată pe toate liniile. Legile lui De Morgan arată cum se neagă un enunț compus: „și” devine „sau”, iar negația lui „dacă $p$, atunci $q$” este „$p$ și non $q$”. O implicație și contrara reciprocei ei au mereu aceeași valoare.

1. Formule propoziționale

Se formează din propoziții $p,\ q,\ r,\ \ldots$, operatori logici și paranteze. Ordinea operatorilor: non, $\land$, $\vee$, $\rightarrow$, $\leftrightarrow$. Pentru $n$ variabile, tabelul de adevăr are $2^{n}$ linii.

2. Tautologii. Formule echivalente

Definiții

Tautologie = formulă adevărată pentru orice valori ale variabilelor. Exemple: $p \vee \overline{p}$, $p \rightarrow p$.

$A \equiv B$ („$A$ este echivalentă cu $B$”): $A$ și $B$ au aceleași valori de adevăr pe fiecare linie.

Exemplu: $p \rightarrow q \equiv \overline{p} \vee q$.

3. Reguli de negare

Regula Formula
dubla negație $\overline{\overline{p}} \equiv p$
legile lui De Morgan

$\overline{p \land q} \equiv \overline{p} \vee \overline{q}$

$\overline{p \vee q} \equiv \overline{p} \land \overline{q}$
negația implicației $\overline{p \rightarrow q} \equiv p \land \overline{q}$

Verificare pentru $\overline{p \land q} \equiv \overline{p} \vee \overline{q}$:

$p$ $q$ $p \land q$ $\overline{p \land q}$ $\overline{p}$ $\overline{q}$ $\overline{p} \vee \overline{q}$
$1$ $1$ $1$ $0$ $0$ $0$ $0$
$1$ $0$ $0$ $1$ $0$ $1$ $1$
$0$ $1$ $0$ $1$ $1$ $0$ $1$
$0$ $0$ $0$ $1$ $1$ $1$ $1$

Negarea relațiilor: $=$ devine $\neq$; $<$ devine $\geq$; $>$ devine $\leq$; $\in$ devine $\notin$.

4. Negarea enunțurilor – exemple

  • „$x > 0$ și $y > 0$” → „$x \leq 0$ sau $y \leq 0$”.
  • „$x = 1$ sau $x = 2$” → „$x \neq 1$ și $x \neq 2$”.
  • „Dacă plouă, iau umbrela” → „Plouă și nu iau umbrela”.

5. Reciproca și contrara unei implicații

Definiții

Pentru implicația $p \rightarrow q$: reciproca $q \rightarrow p$; contrara $\overline{p} \rightarrow \overline{q}$; contrara reciprocei $\overline{q} \rightarrow \overline{p}$.

$p$ $q$ $p \rightarrow q$ $q \rightarrow p$ $\overline{p} \rightarrow \overline{q}$ $\overline{q} \rightarrow \overline{p}$
$1$ $1$ $1$ $1$ $1$ $1$
$1$ $0$ $0$ $1$ $1$ $0$
$0$ $1$ $1$ $0$ $0$ $1$
$0$ $0$ $1$ $1$ $1$ $1$

Reține

$p \rightarrow q \equiv \overline{q} \rightarrow \overline{p}$ și $q \rightarrow p \equiv \overline{p} \rightarrow \overline{q}$. O implicație și reciproca ei pot avea valori diferite.

Exemplu

„Dacă $n \vdots 4$, atunci $n \vdots 2$” – adevărată; reciproca „Dacă $n \vdots 2$, atunci $n \vdots 4$” – falsă ($n = 6$); contrara reciprocei „Dacă $n$ nu este divizibil cu $2$, atunci nu este divizibil cu $4$” – adevărată.

Întrebări frecvente

Care este negația unei implicații?

Negația lui „dacă $p$, atunci $q$” este „$p$ și non $q$”: $\overline{p \rightarrow q} \equiv p \land \overline{q}$. Implicația este falsă doar când ipoteza este adevărată și concluzia falsă, iar negația spune exact acest lucru. O greșeală frecventă este să scrii „dacă non $p$, atunci non $q$”: aceea este contrara, nu negația.

Ce spun legile lui De Morgan?

Negația unei conjuncții este disjuncția negațiilor, iar negația unei disjuncții este conjuncția negațiilor: $\overline{p \land q} \equiv \overline{p} \vee \overline{q}$ și $\overline{p \vee q} \equiv \overline{p} \land \overline{q}$. Când negi un enunț, „și” devine „sau”, iar „sau” devine „și”.

Care este diferența dintre reciprocă și contrara reciprocei?

Pentru $p \rightarrow q$, reciproca este $q \rightarrow p$, iar contrara reciprocei este $\overline{q} \rightarrow \overline{p}$. Contrara reciprocei are mereu aceeași valoare de adevăr ca implicația inițială; reciproca poate avea altă valoare. Pe această echivalență se sprijină metoda reducerii la absurd.

Cum verific dacă două formule sunt echivalente?

Construiești tabelul de adevăr pentru ambele formule, cu toate cele $2^{n}$ combinații de valori ale celor $n$ variabile. Dacă cele două coloane coincid pe fiecare linie, formulele sunt echivalente și scrii $A \equiv B$. O singură linie diferită ajunge pentru a arăta că nu sunt echivalente.