1.10 Quantificadors

En la secció ‘Variables i constants’ hem escrit

reconeixent en aquesta expressió la llei commutativa de l’aritmètica. Si assumim que les variables designen nombres reals, aquest enunciat afirma que tots els nombres reals compleixen aquesta propietat i, en general, tots els enunciats d’aquest tipus que afirmen que objectes arbitraris d’una classe compleixen una determinada propietat, s’anomenen proposicions universals.

A vegades també ens trobem enunciats com

reconeixent en aquesta expressió que hi ha dos nombres que compleixen aquesta equació. En aquests casos diem que són proposicions existencials perquè afirmen l’existència d’objectes (en aquest cas, els nombres 1 i 2) que compleixen una certa propietat.

Fins ara, mitjançant els símbols lògics $\wedge,\vee,\lnot,\longrightarrow$ i $\longleftrightarrow$, hem vist com podem formalitzar molts enunciats de les matemàtiques i com podem conèixer que dos enunciats diferents tenen el mateix significat si són equivalents. També hem vist com la formalització ens pot ajudar a comprendre l’estructura lògica dels raonaments, i com els raonaments són vàlids amb l’ajut d’implicacions lògiques o regles d’inferència. Però amb tot això no n’hi ha prou per captar la totalitat del significat de molts enunciats de les matemàtiques. A l’inici d’aquesta secció hem vist com hi ha uns enunciats molt comuns a matemàtiques que cal estudiar amb més detall.

En efecte, imaginem que estem tractant un conjunt infinit $X$ de nombres enters. Considerem ara l’enunciat ‘Tots els elements de $X$ són senars’. Si volem formalitzar aquest enunciat, hauríem d’escriure

on $P(x)$ és el predicat ‘$x$ és senar’. I si volem formalitzar l’enunciat ‘Hi ha almenys un element de $X$ que és senar’, hauríem d’escriure

El problema d’aquestes dues expressions és que no s’acaben mai. Per superar-lo introduirem dos nous símbols $\exists$ i $\forall$. El símbol $\exists$, anomenat quantificador existencial, està en lloc de frases com ‘existeix’ o ‘hi ha un’. D’aquesta manera l’enunciat ‘Hi ha elements de $X$ que són senars’ podem escriure’l així

El símbol $\forall$, anomenat quantificador universal, està en lloc de frases com ‘per a tots’ o ‘per a cadascun’. D’aquesta manera l’enunciat ‘Tots els elements de $X$ són senars’ podem escriure’l així

Els exemples que hem donat a l’inici d’aquesta secció podem ara expressar-los d’aquesta manera:

que constitueix una proposició universal, i l’altre

que és una proposició existèncial.

L’enunciat ‘el quadrat d’un nombre real més petit o igual que 4’ és un predicat. Si $x$ és un nombre real, aleshores ‘$x^{2}\leq 4$’ és el predicat abreujat. L’enunciat ‘$x^{2}\leq 4$’ no és una proposició perquè no podem afirmar que sigui vertadera o falsa llevat que assignem a la varible lliure $x$ un valor real. Si representem per $P(x)$ aquest predicat, llavors $P(1)$ és una proposició vertadera, en canvi, $P(3)$ és falsa.

Hi ha una altra manera de fer que un predicat es converteixi en una proposició. Es fent que les seves variables lliures quedin lligades per quantificadors. Considerem que $P(x)$ el predicat anterior, aleshores ‘$\forall x\in\mathbb{R}$, $P(x)$’ és una proposició falsa, i en canvi, ‘$\exists x\in\mathbb{R}$, $P(x)$’ és vertadera.

Podem construir enunciats amb més d’un quantificador. Per exemple, considerem el predicat $Q(m,n)=$ ‘$m<n$’, on $m,n\in\mathbb{Z}$. Llavors, la proposició ‘$\forall m\in\mathbb{Z}\leavevmode\nobreak\ \exists n\in\mathbb{Z},m<n$’, escrita en català com ‘per a tot nombre enter $m$ existeix algun altre enter $n$ tal que $m<n$’, és vertadera. En efecte, donat qualsevol enter $m$, existeix $n=m+1$, també és enter i compleix la condició $m<n$.

L’ordre dels quantificadors és molt important perquè per exemple, canviant l’ordre de l’enunciat anterior, o sigui ‘$\exists m\in\mathbb{Z}\leavevmode\nobreak\ \forall n\in\mathbb{Z},m<n$’ es té una proposició falsa. És important també observar el paper que fan les variables lliures en una proposició que també en té de lligades. Amb relació al predicat anterior, considerem la proposició ‘$\exists m\in\mathbb{Z},$ $m<n$’, què és vertadera perquè només cal prendre $m=n-1$. Si ara posem $x$ en lloc de $m$ en la proposició, es té ‘$\exists x\in\mathbb{Z},$ $x<n$’ que té el mateix significat que l’anterior; de fet, els valors de $m$ o $x$ depenen sempre del valor que assignem a la variable lliure $n$, i, per tant, si aquesta expressió formés part d’una expressió més llarga, aquesta última no canviaria en el seu significat. En canvi, si substituïm la variable lliure $n$ per una altra $q$, la proposició ‘$\exists m\in\mathbb{Z},$ $m<q$’ pot canviar el significat d’una expressió més llarga de la qual en forma part, doncs ara $m$ depèn de $q$ i no de $n$.

Ara volem veure la negació de proposicions amb quantificadors. Per exemple, considerem el predicat $Q=$ ‘tenir els ulls blaus’. Llavors, si suposem que la variable $x$ té per domini el conjunt de totes les persones, l’enunciat ‘Totes les persones tenen els ulls blaus’ s’escriu així: $\left(\forall x\right)Q(x)$. La negació d’aquest enunciat és ‘No totes les persones tenen els ulls blaus’ que s’escriu com $\lnot\left(\forall x\right)Q(x)$. És clar que aquest últim enunciat també el podem escriure com ‘Hi ha alguna persona que no te els ulls blaus’, que simbòlicament ho escrivim així: $\left(\exists x\right)\lnot Q\left(x\right)$.

Considerem ara el cas d’una proposició existencial. Considerem l’enunciat ‘Existeix una solució real en l’equació $x^{3}+x=0$’. Si suposem que el domini de la variable $x$ són els nombres reals, aleshores escrivim aquesta proposició així: $\left(\exists x\right)\left(x^{3}+x=0\right)$. La negació d’aquesta proposició és ‘Cap nombre real és solució de l’equació $x^{3}+x=0$’, que s’escriu així: $\left(\forall x\right)\left(x^{3}+x\neq 0\right)$.

Podem resumir els dos casos anteriors d’aquesta manera: Si $P(x)$ és un predicat i el domini de la variable $x$ és el conjunt $U$, aleshores es compleixen les següents equivalències:

• •
  ​

  $\lnot\left(\forall x\in U,P(x)\right)\Longleftrightarrow\exists x\in U,\lnot P\left(x\right)$

• •
  ​

  $\lnot\left(\exists x\in U,P\left(x\right)\right)\Longleftrightarrow\forall x\in U,\lnot P\left(x\right)$

A diferència de les equivalències discutides a la secció 1.8, no podem utilitzar taules de veritat per verificar aquestes equivalències, tot i que són certes, basant-se en els significats dels quantificadors. Podem utilitzar les equivalències anteriors per negar proposicions amb més d’un quantificador. Per exemple, suposem que $f$ és una funció real de variable i considerem l’enunciat ‘Per a cada nombre real $x$, existeix un nombre real $y$ tal que $f(x)=y$’; simbòlicament s’escriu com $\left(\forall x\right)\left(\exists y\right)\left(f(x)=y\right)$. La seva negació és

i, reformulant aquesta última expressió en català es té: ‘Existeix un nombre real $x$ tal que per a tot nombre real $y$ es compleix $f(x)\neq y$’.

Finalment, passem a les regles d’inferència amb quantificadors. Hi ha quatre regles d’inferència d’aquest tipus i, tot i que el seu ús requereix una mica més de cura que les regles d’inferència de la secció 1.9, s’utilitzen amb el mateix propòsit, que és mostrar la validesa dels raonaments lògics.

EQU:

$\left(\forall x\in U\right)P(x)$

$P(a)$

(Eliminació Quantificador Universal)

on $a$ és qualsevol element de $U$.

IQU:

$P(b)$

$\left(\forall x\in U\right)P(x)$

(Introducció Quantificador Universal)

on $b$ és un element arbitrari de $U$.

EQE:

$\left(\exists x\in U\right)P(x)$

$P(c)$

(Eliminació Quantificador Existencial)

on $c$ és un element de $U$ però el símbol ‘$c$’ no ha d’haver aparagut en el argument abans.

IQE:

$P(d)$

$\left(\exists x\in U\right)P(x)$

(Introducció Quantificador Existencial)

on $d$ és un element de $U$.

En la regla EQE volem destacar el fet que $c$ no fa referència a cap símbol que ja s’ha utilitzat en l’argument. Per tant, hem de triar una lletra nova, en lloc d’una que ja s’utilitzi per a una altra cosa.

Un exemple de raonament lògic senzill que implica quantificadors és el següent:

‘A cada gat simpàtic i intel·ligent li agrada el fetge picat. Tots els gats siamesos són agradables. Hi ha un gat siamès al qual no li agrada el fetge picat. Per tant, hi ha un gat estúpid.’

Formalitzem els enunciats del raonament. Per facilitar l’escriptura, considerem que la variable $x$ té per domini el conjunt de tots els gats. Denotem per $S$, $I$, $F$ i $G$ els predicats ‘és simpàtic o agradable’, $I$, ‘és intel·ligent’, $F$, ‘agrada el fetge picat’, i $G$, ‘és gat siamès’, respectivament. Aleshores, el raonament podem simbolitzar-lo d’aquesta manera:

Fem ara la deducció per provar la seva validesa:

Tinguem en compte que a la línia (4) hem escollit alguna lletra com ‘$a$’ que no s’utilitzava abans d’aquesta línia, perquè apliquem la regla EQE.

Solució:  No és correcte, perquè en el pas 5 el símbol ‘$a$’ ha aparagut abans.   $\square$