1.8 Equivalència lògica

Si $A$ i $B$ són dues formes proposicionals, llavors es diu que $A$ i $B$ són equivalents lògicament quan la forma $A\longleftrightarrow B$ és tautologia. Com la implicació lògica, l’equivalència és una relació entre formes proposicionals que denotem per $\Longleftrightarrow$ . D’aquesta manera, quan escrivim $A\Longleftrightarrow B$ , que llegim " $A$ és equivalent a $B$ "o " $A$ i $B$ són equivalents", significa que $A\longleftrightarrow B$ és tautologia.

A la pràctica, el fet de tenir l’equivalència $A\Longleftrightarrow B$ permet fer el següent argument: Si $A\Longleftrightarrow B$ , i $A$ (resp. $B$ ) és tautologia, aleshores necessàriament $B$ (resp. $A$ ) és tautologia, i també, d’aquí surt una interpretació molt comuna en matemàtiques: quan $A\Longleftrightarrow B$ , aleshores es diu que $A$ és condició necessària i suficient per $B$ o a l’inrevés. De fet, això es dedueix de l’equivalència següent: $A\longleftrightarrow B\Longleftrightarrow\left(A\longrightarrow B\right)\wedge% \left(B\longrightarrow A\right)$ perquè

$A$	$B$	$\alpha=A\longrightarrow B$	$\beta=B\longrightarrow A$	$\gamma=A\longleftrightarrow B$	$\alpha\wedge\beta$	$\gamma\longleftrightarrow\left(\alpha\wedge\beta\right)$
V	V	V	V	V	V	V
V	F	F	V	F	F	V
F	V	V	F	F	F	V
F	F	V	V	V	V	V

A continuació s’enumeren algunes equivalències lògiques que seran particularment útils i al seu costat el nom pel qual són conegudes:

1.

$\lnot\left(\lnot A\right)\Longleftrightarrow A$ (llei de la doble negació)
2.

$A\wedge B\Longleftrightarrow B\wedge A$ (llei commutativa de $\wedge$ )
3.

$A\vee B\Longleftrightarrow B\vee A$ (llei commutativa de $\vee$ )
4.

$\left(A\wedge B\right)\wedge C\Longleftrightarrow A\wedge\left(B\wedge C\right)$ (llei associativa de $\wedge$ )
5.

$\left(A\vee B\right)\vee C\Longleftrightarrow A\vee\left(B\vee C\right)$ (llei associativa de $\vee$ )
6.

$A\vee\left(B\wedge C\right)\Longleftrightarrow\left(A\vee B\right)\wedge\left(% A\vee C\right)$ (llei distributiva de $\vee$ respecte de $\wedge$ )
7.

$A\wedge\left(B\vee C\right)\Longleftrightarrow\left(A\wedge B\right)\vee\left(% A\wedge C\right)$ (llei distributiva de $\wedge$ respecte de $\vee$ )
8.

$A\longrightarrow B\Longleftrightarrow\lnot A\vee B$
9.

$A\longrightarrow B\Longleftrightarrow\lnot B\longrightarrow\lnot A$ (llei del contrarecíproc)
10.

$A\longleftrightarrow B\Longleftrightarrow\left(A\longrightarrow B\right)\wedge% \left(B\longrightarrow A\right)$ (llei del bicondicional)
11.

$\left(A\vee B\right)\longrightarrow C\Longleftrightarrow\left(A\longrightarrow C% \right)\wedge\left(B\longrightarrow C\right)$
12.

$A\longrightarrow\left(B\wedge C\right)\Longleftrightarrow\left(A% \longrightarrow B\right)\wedge\left(A\longrightarrow C\right)$
13.

$\lnot(A\wedge B)\Longleftrightarrow\lnot A\vee\lnot B$ (llei de De Morgan)
14.

$\lnot(A\vee B)\Longleftrightarrow\lnot A\wedge\lnot B$ (llei de De Morgan)

Algunes d’aquestes lleis tenen molt d’interès quan volem fer demostracions. La llei de la doble negació a la pràctica es usa de la següent manera: volem provar que $p$ és vertadera. Per a fer-ho, suposem com hipòtesi que $\lnot p$ és vertadera, i deduïm contradicció, i, per tant, $\lnot\left(\lnot p\right)$ és vertadera. Ara bé, $\lnot\left(\lnot p\right)$ i $p$ són equivalents i, per tant, $p$ és vertadera. Aquesta manera de demostrar un enunciat matemàtic serà tractada amb més detall més endavant.

Es diu recíproc de la proposició $p\longrightarrow q$ a la proposició $q\longrightarrow p$ , i contrarecíproc a la proposició $\lnot q\longrightarrow\lnot p$ . La llei del contrarecíproc també és la base de moltes demostracions. A la pràctica es usa de la següent manera: volem provar que $p$ implica $q$ . Per a fer-ho, observem que és més senzill provar que $\lnot q$ implica $\lnot p$ , i, per tant, és cert que $p$ implica $q$ . Tractarem aquesta forma de demostració més en detall més endavant.

Finalment, fem alguns comentaris sobre la llei del bicondicional. Quan s’ha de demostrar una equivalencia $p\longleftrightarrow q$ , la llei del bicondicional permet fer-ho de la següent manera: primer, provem que $p$ implica $q$ , i després, el recíproc, es a dir, que $q$ implica $p$ . Es habitual en matemàtiques dir-ho d’alguna d’aquestes maneres: (1) $p$ és condició necessària i suficient per $q$ o (2) si $p$ , llavors $q$ , i recíprocament.

Per a completar aquesta secció provarem les lleis 10 i 12. Per demostrar 10 hem de comprovar que $\left(A\longleftrightarrow B\right)\longleftrightarrow\left(A\longrightarrow B% \right)\wedge\left(B\longrightarrow A\right)$ és tautologia. En efecte, constriuïm la matriu i s’obté tautologia

$A$	$B$	$\alpha=A$ $\longrightarrow$ $B$	$\beta=B\longrightarrow A$	$\gamma=A\longleftrightarrow B$	$\alpha\wedge\beta$	$\gamma\longleftrightarrow\left(\alpha\wedge\beta\right)$
V	V	V	V	V	V	V
V	F	F	V	F	F	V
F	V	V	F	F	F	V
F	F	V	V	V	V	V

Per demostrar 11 hem de comprovar que $\lnot(A\wedge B)\longleftrightarrow\left(\lnot A\vee\lnot B\right)$ és tautologia. En efecte, constriuïm la matriu i s’obté tautologia

\begin{tabular}[]{llllllll}$A$&$B$&$A\wedge B$&$\lnot A$&$\lnot B$&$\alpha=% \lnot\left(A\wedge B\right)\,$&$\beta=\lnot A\vee\lnot B$&$\alpha% \longleftrightarrow\beta$\\ \hline\cr\lx@intercol\hfil V\hfil\lx@intercol &\lx@intercol\hfil V\hfil% \lx@intercol\vrule\lx@intercol &\lx@intercol\hfil V\hfil\lx@intercol &% \lx@intercol\hfil F\hfil\lx@intercol &\lx@intercol\hfil F\hfil\lx@intercol &% \lx@intercol\hfil F\hfil\lx@intercol &\lx@intercol\hfil F\hfil\lx@intercol &% \lx@intercol\hfil V\hfil\lx@intercol \\ \lx@intercol\hfil V\hfil\lx@intercol &\lx@intercol\hfil F\hfil\lx@intercol% \vrule\lx@intercol &\lx@intercol\hfil F\hfil\lx@intercol &\lx@intercol\hfil F% \hfil\lx@intercol &\lx@intercol\hfil V\hfil\lx@intercol &\lx@intercol\hfil V% \hfil\lx@intercol &\lx@intercol\hfil V\hfil\lx@intercol &\lx@intercol\hfil V% \hfil\lx@intercol \\ \lx@intercol\hfil F\hfil\lx@intercol &\lx@intercol\hfil V\hfil\lx@intercol% \vrule\lx@intercol &\lx@intercol\hfil F\hfil\lx@intercol &\lx@intercol\hfil V% \hfil\lx@intercol &\lx@intercol\hfil F\hfil\lx@intercol &\lx@intercol\hfil V% \hfil\lx@intercol &\lx@intercol\hfil V\hfil\lx@intercol &\lx@intercol\hfil V% \hfil\lx@intercol \\ \lx@intercol\hfil F\hfil\lx@intercol &\lx@intercol\hfil F\hfil\lx@intercol% \vrule\lx@intercol &\lx@intercol\hfil F\hfil\lx@intercol &\lx@intercol\hfil V% \hfil\lx@intercol &\lx@intercol\hfil V\hfil\lx@intercol &\lx@intercol\hfil V% \hfil\lx@intercol &\lx@intercol\hfil V\hfil\lx@intercol &\lx@intercol\hfil V% \hfil\lx@intercol\end{tabular}.

Les altres és demostran de la mateixa manera.

Exemple 1.5.

Escriu fent ús de les connectives les proposicions següents: (1) S’ha de revisar. Per exemple, la proposició ‘un nombre natural és parell si i només si el seu quadrat és parell’ és el bicondicional: $P(n)$ si i nomes si $P(n^{2})$ , on $P$ és el predicat ‘ser un nombre natural parell’. (2) És necessàri que $x$ sigui un nombre real no negativo perquè $\sqrt{x}$ sigui real; (3) És suficient que $n=3$ perquè $n^{2}-5n+6=0$ ; (4) $n^{2}-5n+6=0$ precisament si $n=2$ o $n=3$ ; (5) $\left|a\right|=\left|b\right|$ sii $a=\pm b$ .

Solució: La proposició (1) es pot expressar com la implicació: $\sqrt{x}$ és real $\Longrightarrow x$ real i $x\geq 0$ ; la proposició (2) és la implicació: $n=3$ $\Longrightarrow$ $n^{2}-5n+6=0$ ; la proposició (3) és el bicondicional: $n^{2}-5n+6=0$ $\Longleftrightarrow$ $n=2$ o $n=3$ , i, la proposició (4) és també un bicondicional: $\left|a\right|=\left|b\right|$ $\Longleftrightarrow$ $a=\pm b$ . $\square$