Predicate și cuantificatori

De îndată ce pui un număr în locul lui $x$, enunțul devine o propoziție. Un astfel de enunț, cu o variabilă, se numește predicat.

Îl notăm $p(x)$. Aici $p(x)$ este „$x + 2 = 9$”, cu $x \in \mathbb{Z}$, iar $p(7)$ e adevărată și $p(5)$ e falsă.

Luăm predicatul $p(x)$: „$x$ divide 5”, unde $x$ e număr întreg. Pentru ce valori ale lui $x$ e adevărat?

5 se împarte exact doar la $1$, $-1$, $5$ și $-5$. Pentru orice alt $x$, de exemplu $0$, $2$ sau $10$, $p(x)$ e falsă.

Mulțimea $A = \{-5, -1, 1, 5\}$ se numește mulțimea de adevăr a lui $p(x)$: e mulțimea tuturor valorilor pentru care predicatul e adevărat.

Lucrăm în $M = \{1, 2, \dots, 12\}$ cu două predicate:

$p(x)$: „$x$ e par”, cu mulțimea de adevăr $A = \{2, 4, 6, 8, 10, 12\}$;

$q(x)$: „$x$ e multiplu de 3”, cu $B = \{3, 6, 9, 12\}$.

Fiecare operație logică colorează altă zonă din desen:

Rămânem în $M = \{1, 2, \dots, 12\}$, cu $A$ (numerele pare) și $B$ (multiplii de 3).

Care numere sunt pare sau multipli de 3? 4 e par, deci intră. 9 e multiplu de 3, deci intră și el. 6 e și par, și multiplu de 3: intră, pentru că „sau” acceptă și varianta „amândouă”. Pe dinafară rămân doar 1, 5, 7 și 11.

Tot în $M = \{1, 2, \dots, 12\}$, luăm $p(x)$: „${9 \mid x}$” și $q(x)$: „${3 \mid x}$”. Mulțimile lor de adevăr sunt $A = \{9\}$ și $B = \{3, 6, 9, 12\}$.

Orice multiplu de 9 e și multiplu de 3, pentru că $9 = 3 \cdot 3$. În desen, cercul lui $A$ stă în întregime în cercul lui $B$:

„Există $x \in \mathbb{N}$ astfel încât $x + 2 = 9$.” E adevărată: $x = 7$ merge. Un singur exemplu ajunge.

„Există $x \in \mathbb{N}$ astfel încât $x + 9 = 2$.” Singurul număr care ar merge e $x = -7$, dar $-7 \notin \mathbb{N}$. Deci propoziția e falsă.

Ca să arăți că un „există” e fals, nu ajunge un exemplu care nu merge: trebuie să arăți că niciun $x$ nu merge.

„Toate numerele prime sunt impare.” 3, 5, 7, 11 sunt impare… dar 2 e prim și par. Un singur număr care nu se potrivește, și propoziția e falsă.

„Pentru orice $x \in \mathbb{R}$, $x^2 > x$.” Merge pentru $x = 2$ ${(4 > 2)}$ și pentru $x = -1$ ${(1 > -1)}$. Dar pentru $x = 0{,}5$: ${0{,}5^2 = 0{,}25}$, iar $0{,}25 < 0{,}5$. Propoziția e falsă.

Un exemplu care arată că o propoziție cu „oricare” e falsă se numește contraexemplu.

Ca „Toți elevii sunt prezenți” să fie falsă, ajunge un elev absent. De aceea negația ei e un „există”.

Ca „Există un elev cu nota 10” să fie falsă, niciun elev nu trebuie să aibă 10, adică toți au sub 10. De aceea negația ei e un „toți”.

„Fiecare elev are o bancă” — fiecare stă în banca lui, iar băncile pot fi diferite. Într-o clasă obișnuită e adevărat.

„Există o bancă pentru toți elevii” — o singură bancă în care stau toți. E fals: 25 de elevi nu încap într-o bancă.

Aceleași cuvinte, în altă ordine, spun altceva.

În matematică: ${(\forall a \in \mathbb{N})(\exists b \in \mathbb{N})}\ a < b$ e adevărată. Pentru orice $a$ alegi $b = a + 1$: $b$ poate depinde de $a$.

${(\exists b \in \mathbb{N})(\forall a \in \mathbb{N})}\ a < b$ e falsă. Un astfel de $b$ ar trebui ales primul și ar trebui să fie mai mare decât orice număr natural, chiar și decât el însuși: pentru $a = b$ ar trebui $b < b$.

Un predicat pe o mulțime $M$ (numită universul predicatului) este un enunț care conține una sau mai multe variabile și care, când variabilele sunt înlocuite cu elemente din $M$, devine propoziție.

Mulțimea de adevăr a predicatului $p(x)$ (manualul îi spune și domeniu de adevăr) este submulțimea lui $M$ formată din valorile $x$ pentru care $p(x)$ e adevărată.

Cuantificatorul existențial: $(\exists x)\,p(x)$ sau $(\exists x \in E)\,p(x)$, „există cel puțin un $x$ astfel încât $p(x)$” (propoziție existențială).

Cuantificatorul universal: $(\forall x)\,p(x)$ sau $(\forall x \in E)\,p(x)$, „oricare ar fi $x$, $p(x)$” (propoziție universală).