2.1 Lògica

Exercici 2.1.

Reformuleu els enunciats següents fent ús de variables i constants: (a) El producte de dos nombres parells és parell; (b) Donat un nombre real no negatiu, busqueu dos nombres reals la diferència dels seus quadrats no sigui més gran que el nombre donat.

Solució: (a) Si simbolitzem per $P$ el predicat “ser parell”, aleshores podem escriure:

\forall x,y\left(P\left(x\right)\wedge P\left(y\right)\longrightarrow P\left(x% \cdot y\right)\right)\text{.}

Observa que també podem escriure:

\forall x\left(P\left(x\right)\longleftrightarrow\left(\exists k\right)\left(k% \in\mathbb{Z}\wedge x=2k\right)\right)\text{.}

(b) Suposem donat un nombre real $\delta\geq 0$ , o sigui no negatiu, aleshores podem escriure:

\exists x,y\left(x,y\in\mathbb{R}\wedge x^{2}-y^{2}\leq\delta\right)\text{.}

$\square$

Exercici 2.2.

Quines de les expressions següents són proposicions i quines predicats? (a) $4<3$ ; (b) $y>7$ ; (c) $x+y=z$ .

Solució: (a) És una proposició perquè és un enunciat vertader; (b) És un predicat perquè és un enunciat que conté una variable $y$ i si li assignem un valor es té una proposició; (c) És un predicat de tres variables $x,y$ i $z$ . Assignant valors a les tres variables s’obté una proposició. $\square$

Exercici 2.3.

Quins dels següents enunciats són predicats i quins no ho són? Justifica la teva resposta. (a) $x$ és un divisor de 210; (b) El producte dels nombres $x$ i $y$ ; (c) La suma de dos nombres es menor que $1$ .

Solució: (a) És un predicat de una variable $x$ que és vertader quan, per exemple, $x$ pren el valor $7$ , i fals quan, per exemple, és $8$ ; (b) No és predicat perquè quan assignem valors a les variables $x$ i $y$ no s’obté una proposició. De fet, l’enunciat és l’expressió algebraica $x\cdot y$ ; (c) És un predicat que conté dues variables. Podem expressar-lo com $x+y<1$ . És clar que quan donme valors a $x$ i $y$ s’obté una proposició. $\square$

Exercici 2.4.

Considereu els enunciats següents: $p=$ “Estic content”, $q=$ “Estic veient una pel·lícula” i $r=$ “Estic menjant espagueti”. Expresseu en paraules els enunciats següents: (a) $\left(q\vee r\right)\longrightarrow p$ ; (b) $\left(p\wedge\lnot q\right)\longleftrightarrow\left(q\vee r\right)$ .

Solució: (a) Estic content quan veig una pel·lícula o mengo espagueti; (b) Veig una pel·lícula o mengo espagueti només si estic content sense veure una pel·lícula. $\square$

Exercici 2.5.

Analitza les formes lògiques dels enunciats següents: (a) El joc es cancel·larà si plou o neva; (b) Tenir almenys deu persones és una condició necessària i suficient per a la conferència que s’està impartint; (c) Si en Miquel va anar a la botiga, llavors tenim ous a casa, si no no en tenim.

Solució: (a) Si $C=$ “El joc serà cancel·lat”, $P=$ “Plou” i $N=$ “Està nevant”. Aleshores l’enunciat “El joc es cancel·larà si plou o neva” es la proposició $C\leftrightarrow(P\vee N)$ .

(b) Si $P=$ “Hi ha almenys deu persones” i $C=$ “La conferència es donarà”. Aleshores l’enunciat “Tenir almenys deu persones és una condició necessària i suficient per a la conferència que s’està impartint” és la proposició $P\longleftrightarrow C$ .

(c) Si $B=$ “Miquel va anar a la botiga” i $C=$ “Hi ha ous a casa". Aleshores, l’enunciat “Si en Miquel va anar a la botiga, llavors tenim ous a casa, si no no en tenim” és la proposició $(B\rightarrow C)\wedge(\lnot B\rightarrow\lnot C)$ . Això és equivalent a $B\longleftrightarrow C$ perquè per la llei del contrarecíproc s’obté $(B\rightarrow C)\wedge(C\rightarrow B)$ , què és alhora equivalent al que hem dit. $\square$

Exercici 2.6.

Considereu els enunciats següents: $p=$ “L’Eduard té els cabells vermells”, $q=$ “L’Eduard té un nas gran” i $r=$ “A l’Eduard li agrada menjar crispetes”. Tradueix els enunciats següents a símbols: (a) “L’Eduard té els cabells vermells i no té un nas gran”; (b) “No és el cas que l’Eduard tingui un nas gran o li agradi menjar crispetes”.

Solució: (a) $p\wedge\lnot q$ ; (b) $\lnot(q\vee r)$ . $\square$

Exercici 2.7.

Construeix les taules de veritat de les següents expressions lògiques: (a) $(p\wedge q)\vee\lnot p$ ; (b) $\lnot p\longrightarrow\lnot(q\vee r)$ .

Solució: (a)

$p$	$q$	$\lnot p$	$p\wedge q$	$(p\wedge q)\vee\lnot p$
V	V	F	V	V
V	F	F	F	F
F	V	V	F	V
F	F	V	F	V

(b)

$p$	$q$	$r$	$\lnot p$	$q\wedge r$	$\lnot(q\vee r)$	$\lnot p\longrightarrow\lnot(q\vee r)$
V	V	V	F	V	F	V
V	V	F	F	F	V	V
V	F	V	F	F	V	V
V	F	F	F	F	V	V
F	V	V	V	V	F	F
F	V	F	V	F	V	V
F	F	V	V	F	V	V
F	F	F	V	F	V	V

$\square$

Exercici 2.8.

Considerem els predicats $P(x,y)=$ ‘ $x+y=4$ ’ i $Q(x,y)=$ ‘ $x<y$ ’. Troba els valors de veritat de les següents expressions lògiques: (a) $\lnot P(x,y)\vee Q(x,y)$ i (b) $\lnot(P(x,y)\longleftrightarrow Q(x,y))$ quan usem els valos següents (1) $x=1,y=3$ ; (2) $x=2,y=1$ .

Solució: (a) Considerem $\lnot P(x,y)\vee Q(x,y)$ , aleshores es tenen les proposicions: (1) $\lnot P(1,3)\vee Q(1,3)$ què és vertadera doncs $Q(1,3)$ ho és al complir-se $1<3$ ; (2) $\lnot(P(1,3)\longleftrightarrow Q(1,3))$ què és falsa doncs $P(1,3)\longleftrightarrow Q(1,3)$ es vertadera al complir-se $1+3=4$ i $1<3$ .

(b) Considerem el cas en que $x=2$ i $y=1$ . Aleshores (1) $\lnot P(2,1)\vee Q(2,1)$ és vertadera doncs $\lnot P(2,1)$ ho és al complir-se $2+1\neq 4$ ; (2) $\lnot(P(2,1)\longleftrightarrow Q(2,1))$ és falsa doncs $P(2,1)$ i $Q(2,1)$ són ambdues falses. $\square$

Exercici 2.9.

Proveu les implicacions següents: (a) $(A\longrightarrow B)\wedge\lnot B\Longrightarrow\lnot A$ ; (b) $\left(A\longrightarrow B\right)\wedge\left(B\longrightarrow C\right)% \Longrightarrow A\longrightarrow C$ .

Solució: (a) Per veure que $(A\longrightarrow B)\wedge\lnot B\Longrightarrow\lnot A$ hem de comprovar que $\left((A\longrightarrow B)\wedge\lnot B\right)$ $\longrightarrow\lnot A$ és tautologia. Construïm la taula de veritat corresponent:

$A$	$B$	$\lnot A$	$\lnot B$	$A$ $\longrightarrow$ $B$	$(A\longrightarrow B)\wedge\lnot B$	$\left((A\longrightarrow B)\wedge\lnot B\right)$ $\longrightarrow\lnot A$
V	V	F	F	V	F	V
V	F	F	V	F	F	V
F	V	V	F	V	F	V
F	F	V	V	V	V	V

i s’obté una tautologia doncs veiem que l’última columna només té el valor V.

(b) Per veure que $\left(A\longrightarrow B\right)\wedge\left(B\longrightarrow C\right)% \Longrightarrow A\longrightarrow C$ hem de comprovar que $\left(\left(A\longrightarrow B\right)\wedge\left(B\longrightarrow C\right)\right)$ $\longrightarrow\left(A\longrightarrow C\right)$ és tautologia. Construïm la taula de veritat corresponent prenent $\alpha=A\longrightarrow B$ , $\beta=B\longrightarrow C$ i $\gamma=A\longrightarrow C$ :

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

i surt que és tautologia com era d’esperar. $\square$

Exercici 2.10.

Proveu les equivalències lògiques següents: (a) $A\longrightarrow B\Longleftrightarrow\lnot A\vee B$ ; (b) $A\longrightarrow\left(B\wedge C\right)\Longleftrightarrow\left(A% \longrightarrow B\right)\wedge\left(A\longrightarrow C\right)$ .

Solució: (a) Per veure que $A\longrightarrow B\Longleftrightarrow\lnot A\vee B$ hem de comprovar que $(A\longrightarrow B)\longleftrightarrow\left(\lnot A\vee B\right)$ és tautologia. Construïm la taula de veritat corresponent:

$A$	$B$	$\lnot A$	$A$ $\longrightarrow$ $B$	$\lnot A\vee B$	$(A\longrightarrow B)\longleftrightarrow\left(\lnot A\vee B\right)$
V	V	F	V	V	V
V	F	F	F	F	V
F	V	V	V	V	V
F	F	V	V	V	V

i s’obté una tautologia doncs veiem que l’última columna només té el valor V.

(b) Per veure que $A\longrightarrow\left(B\wedge C\right)\Longleftrightarrow\left(A% \longrightarrow B\right)\wedge\left(A\longrightarrow C\right)$ hem de comprovar que $(A\longrightarrow\left(B\wedge C\right))\longleftrightarrow\left(\left(A% \longrightarrow B\right)\wedge\left(A\longrightarrow C\right)\right)$ és tautologia. Construïm la taula de veritat corresponent, prenent $\alpha=A\longrightarrow B$ , $\beta=A\longrightarrow C$ i $\gamma=A\longrightarrow\left(B\wedge C\right)$ :

$A$	$B$	$C$	$\alpha$	$B\wedge C$	$\beta$	$\gamma$	$\delta=\alpha\wedge\beta$	$\gamma\longleftrightarrow\delta$
V	V	V	V	V	V	V	V	V
V	V	F	V	F	F	F	F	V
V	F	V	F	F	V	F	F	V
V	F	F	F	F	F	F	F	V
F	V	V	V	V	V	V	V	V
F	V	F	V	F	V	V	V	V
F	F	V	V	F	V	V	V	V
F	F	F	V	F	V	V	V	V

i surt que és tautologia com era d’esperar. $\square$

Exercici 2.11.

Simplifiqueu les afirmacions següents. Podeu fer ús de les equivalències de l’exercicicici anterior a més de les equivalències comentades a teoria i pràctica: (a) $X\longrightarrow\left(X\wedge Y\right)$ ; (b) $\lnot\left(X\vee Y\right)\wedge Y$ .

Solució: (a) Aplicant la primera equivalència de l’apartat anterior es té: $X\longrightarrow\left(X\wedge Y\right)\Longleftrightarrow\lnot X\vee\left(X% \wedge Y\right)$ . Aplicant ara la llei distributiva de $\vee$ respecte de $\wedge$ s’obté

\lnot X\vee\left(X\wedge Y\right)\Longleftrightarrow\left(\lnot X\vee X\right)% \wedge\left(\lnot X\vee Y\right)

Ara bé, $\lnot X\vee X$ és tautologia. Per tant, $\left(\lnot X\vee X\right)\wedge\left(\lnot X\vee Y\right)\Longleftrightarrow% \lnot X\vee Y$ . Com a consequència tenim que $X\longrightarrow\left(X\wedge Y\right)\Longleftrightarrow X\longrightarrow Y$ , doncs $\lnot X\vee Y\Longleftrightarrow X\longrightarrow Y$ .

(b) Aplicant les lleis de De Morgan es té:

\lnot\left(X\vee Y\right)\wedge Y\Longleftrightarrow\left(\lnot X\wedge\lnot Y% \right)\vee Y.

Ara, aplicant la llei distributiva de $\vee$ respecte de $\wedge$ , s’obté

\lnot\left(X\vee Y\right)\wedge Y\Longleftrightarrow\left(\lnot X\vee Y\right)% \wedge\left(\lnot Y\vee Y\right).

Finalment, com $\lnot Y\vee Y$ és tautologia i $\lnot X\vee Y\Longleftrightarrow X\longrightarrow Y$ , es té

\lnot\left(X\vee Y\right)\wedge Y\Longleftrightarrow X\longrightarrow Y\text{.}

$\square$

Exercici 2.12.

Escriu la negació dels enunciats següents: (a) $3>5$ o $7\leq 8$ ; (b) Si $x=3$ , llavors $x^{2}=5$ ; (c) $a-b=c$ si i només si $a=b+c$ .

Solució: (a) Aplicant la llei de de Morgan, $3\leq 5$ o $7>8$ .

(b) L’enunciat és de la forma $A\longrightarrow B$ , aleshores la seva negació és $\lnot\left(A\longrightarrow B\right)\,$ . Ara bé, sabem que $A\longrightarrow B\Longleftrightarrow\lnot A\vee B$ i aplicant de nou la llei de De Morgan es té $\lnot\left(A\longrightarrow B\right)\Longleftrightarrow A\wedge\lnot B$ . Per tant, la negació de l’enunciat és $x=3$ i $x^{2}\neq 5$ .

(c) Observem primer que $a-b=c$ és equivalent a $a=b+c$ . Per tant, l’enunciat és tautològic i de la forma $A\longleftrightarrow A$ , aleshores la seva negació és contradicció: $a-b=c$ i $a\neq b+c$ . $\square$