Lògica proposicional i de predicats: taules de veritat, quantificadors i negacions

La lògica no és un tema més: és l'idioma en què estan escrits tots els altres. Si saps negar correctament una cadena de quantificadors, definicions com la de límit o la de continuïtat deixen de ser fórmules que es memoritzen i passen a ser frases que es llegeixen. I si no ho saps, cada demostració per contradicció comença amb un error.

Connectius i taules de veritat

Una proposició és un enunciat al qual es pot assignar un valor de veritat. Els connectius bàsics són la negació, la conjunció, la disjunció inclusiva, la implicació i l'equivalència. La taula completa és aquesta:

$p$	$q$	$\neg p$	$p\land q$	$p\lor q$	$p\Rightarrow q$	$p\Leftrightarrow q$
V	V	F	V	V	V	V
V	F	F	F	V	F	F
F	V	V	F	V	V	F
F	F	V	F	F	V	V

Les tres files destacades són les que costen. La implicació només és falsa quan l'antecedent és cert i el conseqüent fals. Si l'antecedent és fals, la implicació és certa passi el que passi: «si $2+2=5$, llavors jo soc el rei» és una proposició certa. Això sobta la primera vegada, però és exactament el que necessites perquè funcionin els teoremes amb hipòtesis: un teorema no diu res sobre els casos que no compleixen les hipòtesis.

Una altra precisió important: la implicació no afirma causalitat. És una relació entre valors de veritat, no entre causes.

Equivalències que has de tenir automatitzades

Una tautologia és certa amb qualsevol assignació de valors; una contradicció és falsa sempre. Dues fórmules són equivalents si tenen la mateixa taula de veritat. Les identitats que faràs servir cada dia:

$$p\Rightarrow q \equiv \neg p\lor q, \qquad \neg(p\land q)\equiv \neg p\lor\neg q, \qquad \neg(p\lor q)\equiv \neg p\land\neg q.$$

Les dues últimes són les lleis de De Morgan: en negar, es canvia el connectiu i es neguen les parts. I de la primera se'n dedueix la que més apareix en demostracions:

$$\neg(p\Rightarrow q)\equiv p\land \neg q.$$

La negació d'una implicació no és una implicació: és una conjunció. Per negar «si plou, m'emporto el paraigua» has de dir «plou i no m'emporto el paraigua», no «si plou, no m'emporto el paraigua».

Quantificadors i domini

Un predicat es converteix en proposició quan fixes la variable o la quantifiques sobre un domini. El quantificador universal exigeix tots els elements; l'existencial n'exigeix almenys un. El domini forma part de l'enunciat: «existeix $x$ amb $x^2 = 2$» és fals als racionals i cert als reals.

La regla de negació és mecànica i val la pena memoritzar-la com un procediment: recorres la cadena d'esquerra a dreta, canvies cada universal per existencial i cada existencial per universal, i al final negues el predicat.

$$\neg\big(\forall x\,P(x)\big)\equiv \exists x\,\neg P(x), \qquad \neg\big(\exists x\,P(x)\big)\equiv \forall x\,\neg P(x).$$

L'ordre dels quantificadors no es pot canviar. Als reals, «per a tot $x$ existeix $y$ amb $y > x$» és cert (pren $y = x+1$). Però «existeix $y$ tal que per a tot $x$ es compleix $y > x$» és fals: seria un número més gran que tots, i triant $x = y$ ja falla. La diferència és que el testimoni de l'existencial pot dependre de les variables universals anteriors, mai de les posteriors.

Arguments vàlids

Un argument amb unes premisses i una conclusió és vàlid si la implicació de la conjunció de premisses cap a la conclusió és una tautologia. Atenció: validesa no és veritat. Un argument vàlid amb premisses falses pot tenir conclusió falsa; el que garanteix la validesa és que si les premisses són certes, la conclusió ho ha de ser.

Les dues regles bàsiques són el modus ponens (de $p$ i $p\Rightarrow q$ es dedueix $q$) i el modus tollens (de $\neg q$ i $p\Rightarrow q$ es dedueix $\neg p$). Les dues fal·làcies bessones, que no són vàlides, són afirmar el conseqüent i negar l'antecedent.

Formes normals

Tota fórmula es pot escriure en forma normal disjuntiva: prens una conjunció de literals per cada fila certa de la taula de veritat i en fas la disjunció. La forma normal conjuntiva és el procediment dual amb les files falses. Aquestes formes són el pont entre la lògica i els circuits digitals i els problemes de satisfactibilitat, però no garanteixen cap representació curta: el nombre de termes pot créixer exponencialment.

Exercici resolt: negar un enunciat amb dos quantificadors

Nega: «per a tot enter $n$ existeix un enter $m$ tal que $m > n$ i $m$ és parell».

Pas 1 — simbolitzar. $\forall n\in\mathbb{Z}\ \exists m\in\mathbb{Z}: (m>n)\land(m \text{ parell})$.

Pas 2 — canviar els quantificadors i negar el predicat. La negació d'una conjunció és la disjunció de les negacions:

$$\exists n\in\mathbb{Z}\ \forall m\in\mathbb{Z}: (m\leq n)\lor(m \text{ senar}).$$

Pas 3 — en paraules. «Existeix un enter $n$ tal que tot enter $m$ o bé no supera $n$, o bé és senar».

Pas 4 — quin és cert? L'original. Donat qualsevol $n$, pots prendre $m = 2(|n|+1)$, que és parell i és més gran que $n$. La negació és, doncs, falsa.

Exercici resolt: validesa amb taula de veritat

És vàlid l'argument «si estudio, aprovo; no he aprovat; per tant no he estudiat»?

Simbolitzat: de $p\Rightarrow q$ i $\neg q$ es dedueix $\neg p$. És exactament el modus tollens.

Comprovació. Si les dues premisses són certes, mira la taula de la implicació: l'única fila amb $q$ fals i $p\Rightarrow q$ cert és la quarta, on $p$ també és fals. Per tant $\neg p$ és cert i l'argument és vàlid.

Compara'l amb la fal·làcia bessona. «Si estudio, aprovo; no he estudiat; per tant no he aprovat» no és vàlid: és negar l'antecedent. A la tercera fila de la taula, $p$ és fals, la implicació és certa i tanmateix $q$ és cert. Pots aprovar sense estudiar sense que la premissa quedi violada.