Predicate și cuantificatori

Un predicat este o afirmație care depinde de una sau mai multe variabile, luate dintr-o mulțime numită domeniu. $P(x)$: „$x^2=4$” devine propoziție când alegem un $x$ sau când precizăm câți $x$ dintr-un domeniu satisfac proprietatea. Cu $x=2$ este adevărată; cu $x=3$ este falsă.

Cuantificatorul universal $\forall$ înseamnă „pentru orice”, iar cel existențial $\exists$ înseamnă „există cel puțin unul”. Domeniul contează: „$\exists x\in \mathbb{R}$ cu $x^2=2$” este adevărat, dar „$\exists x\in \mathbb{Q}$ cu $x^2=2$” este fals. Un predicat cu două variabile, $P(x,y)$, poate fi cuantificat în ambele variabile, iar ordinea cuantificatorilor poate schimba sensul.

Exemplu rezolvat. Negația afirmației „orice întreg este pozitiv” se obține astfel.

1. Enunțul este $\forall n\in \mathbb{Z},n>0$.
2. Negăm „pentru orice” prin „există”.
3. Negăm proprietatea $n>0$ prin $n\le 0$.

Rezultă $\exists n\in \mathbb{Z},n\le 0$; $n=0$ confirmă negația.

Cuantificatorii transformă un predicat într-o propoziție și precizează câte valori trebuie să satisfacă proprietatea. Pentru un predicat $P(x)$ pe domeniul $D$, notăm cu $A=\{x\in D\mid P(x)\}$ mulțimea valorilor pentru care $P(x)$ este adevărat. Propoziția $\forall x\in D,P(x)$ este adevărată dacă și numai dacă $A=D$, iar propoziția $\exists x\in D,P(x)$ este adevărată dacă și numai dacă $A\ne \varnothing$. Scrierea $\exists !x\in D,P(x)$ înseamnă „există exact un $x$” și cere ca $A$ să aibă un singur element.

Exemplu rezolvat. Fie $P(x)$: „$x^2-5x+6=0$” pe domeniul $\mathbb{N}$.

1. Ecuația se scrie $(x-2)(x-3)=0$, deci $A=\{2;3\}$.
2. $\exists x\in \mathbb{N},P(x)$ este adevărată, fiindcă $A\ne \varnothing$; martorii sunt $2$ și $3$.
3. $\forall x\in \mathbb{N},P(x)$ este falsă, fiindcă $A\ne \mathbb{N}$; de exemplu $P(0)$ spune $6=0$.
4. $\exists !x\in \mathbb{N},P(x)$ este falsă, fiindcă $A$ are două elemente.

Negația schimbă cuantificatorul și neagă predicatul: $\neg (\forall x\in D,P(x))\iff \exists x\in D,\neg P(x)$, respectiv $\neg (\exists x\in D,P(x))\iff \forall x\in D,\neg P(x)$. Domeniul se păstrează la negare. Dacă predicatul este o implicație sau o conjuncție, se aplică și regulile conectorilor: negația lui „pentru orice $x$, dacă $P(x)$, atunci $Q(x)$” este „există $x$ pentru care $P(x)$ este adevărat și $Q(x)$ este fals”. De exemplu, negația propoziției „orice elev cu nota $10$ a fost premiat” este „există un elev cu nota $10$ care nu a fost premiat”.

Exemplu rezolvat. Stabilim valoarea de adevăr a propoziției $\forall x\in \mathbb{R},x^2-4x+5>0$ și scriem negația.

1. Completăm pătratul: $x^2-4x+5=(x-2{)}^2+1$.
2. Pentru orice real $x$, $(x-2{)}^2\ge 0$, deci $(x-2{)}^2+1\ge 1>0$. Propoziția este adevărată.
3. Negația este $\exists x\in \mathbb{R},x^2-4x+5\le 0$. Ea este falsă: nicio valoare a lui $x$ nu face expresia mai mică decât $1$.

Un predicat cu două variabile devine predicat cu o singură variabilă când o fixezi pe una dintre ele. Fie $P(x,y)$: „$x+y=5$” pe $\mathbb{N}$. Pentru $x=2$ rămâne „$2+y=5$”, adevărat numai pentru $y=3$. Propoziția $\exists x\exists y,P(x,y)$ este adevărată, dar $\forall x\exists y,P(x,y)$ este falsă: pentru $x=7$ ar trebui $y=-2$, care nu aparține lui $\mathbb{N}$.

Pentru variabile multiple, ordinea contează: alegerea dintr-un cuantificator existențial poate depinde de valorile universale care îl precedă, dar nu de cele care urmează. Existența unui singur obiect potrivit pentru toate valorile este o cerință mai puternică decât existența unui obiect posibil diferit pentru fiecare valoare.

Exemplu rezolvat. Comparăm două afirmații pe $\mathbb{R}$.

1. Afirmația $\forall x\exists y,y>x$ este adevărată: după alegerea lui $x$, construim $y=x+1$.
2. Afirmația $\exists y\forall x,y>x$ ar cere un real mai mare decât toate numerele reale.
3. Pentru orice candidat $y$, alegem $x=y+1$, care îl depășește.
4. A doua afirmație este falsă; schimbarea ordinii a modificat sensul și valoarea de adevăr.

Exemplu rezolvat. Scriem negația propoziției $\forall x\in \mathbb{R},(x>2\Rightarrow x^2>4)$ și stabilim valorile de adevăr.

1. Negația unei implicații $p\Rightarrow q$ este $p\wedge \neg q$, deci negația este $\exists x\in \mathbb{R},x>2\wedge x^2\le 4$.
2. Propoziția inițială este adevărată: din $x>2>0$ rezultă $x^2>4$.
3. Negația este falsă, fiindcă niciun real mai mare decât $2$ nu are pătratul cel mult $4$.

Problemă. Care dintre propoziții este adevărată?

• a) $\forall x\in \mathbb{R},x^2>x$
• b) $\forall x\in \mathbb{Z}\exists y\in \mathbb{Z},xy=1$
• c) $\exists x\in \mathbb{Q},x^2=3$
• d) $\exists y\in \mathbb{Z}\forall x\in \mathbb{Z},x+y=x$
• e) $\exists x\in \mathbb{N}\forall y\in \mathbb{N},x>y$
• f) $\forall x\in \mathbb{R},|x|>0$

Rezolvare. La propozițiile universale căutăm întâi un contraexemplu printre valorile uzuale: $0$, $1$, numerele negative, fracțiile. Verificăm fiecare propoziție. La a), $x=0$ dă $0>0$, fals. La b), $x=2$ ar cere $y=\frac{1}{2}\notin \mathbb{Z}$. La c), $x^2=3$ are soluțiile $\pm \sqrt{3}$, care sunt iraționale. La e), pentru $y=x$ obținem $x>x$, fals, deci niciun număr natural nu este mai mare decât toate. La f), $x=0$ dă $|0|=0$, nu un număr pozitiv. La d), alegem $y=0$: pentru orice întreg $x$, $x+0=x$. Singura propoziție adevărată este d).

Variantele greșite pornesc din verificări incomplete. La a) se încearcă numai $x=3$, unde $9>3$, și se uită $x=0$ și $x=\frac{1}{2}$. La b) se confundă $\mathbb{Z}$ cu $\mathbb{Q}$, unde $y=\frac{1}{x}$ ar exista pentru $x\ne 0$. La c) se confundă $\mathbb{Q}$ cu $\mathbb{R}$. La e) se crede că există un cel mai mare număr natural. La f) se uită că $0$ este real.

Problemă. Negăm propoziția $\forall x\in \mathbb{R}\exists y\in \mathbb{R},x+y>0$. Negația este $\exists x\in \mathbb{R}\forall y\in \mathbb{R},x+y\le 0$. Propoziția inițială este adevărată, deoarece alegerea $y=1-x$ dă $x+y=1>0$. Negația este deci falsă: niciun real fix nu face toate aceste sume nepozitive.

Problemă. Fie $P(x)$: „$x^2<x$” pe $\mathbb{R}$. Inecuația se scrie $x(x-1)<0$, deci $P(x)$ este adevărat exact pentru $x\in (0;1)$. Propoziția $\exists x\in \mathbb{R},P(x)$ este adevărată, de exemplu pentru $x=\frac{1}{2}$, unde $\frac{1}{4}<\frac{1}{2}$. Propoziția $\forall x\in \mathbb{R},P(x)$ este falsă: pentru $x=2$ se obține $4<2$, fals.

Greșeli frecvente

• Greșit: negația lui „toate numerele din listă sunt pozitive” este „toate sunt negative”.
  Corect: „există cel puțin un număr care este mai mic sau egal cu zero”.
• Greșit: $\exists x\in \mathbb{R},x^2=2$ devine falsă fiindcă nu există soluție rațională.
  Corect: domeniul este real, iar $\sqrt{2}$ este un exemplu admis.
• Greșit: $\forall x\exists y,y>x$ și $\exists y\forall x,y>x$ spun același lucru, deoarece cuantificatorii „se pot muta”.
  Corect: prima este adevărată în $\mathbb{R}$, a doua este falsă; ordinea schimbă sensul.
• Greșit: negația lui „există un elev cu nota $10$” este „există un elev fără nota $10$”.
  Corect: negația este „niciun elev nu are nota $10$”, adică orice elev are altă notă.
• Greșit: propoziția $\forall x\in \mathbb{R},x^2\ge x$ este adevărată, deoarece este adevărată pentru $x=2$ și $x=3$.
  Corect: câteva exemple nu dovedesc o propoziție universală; la $x=\frac{1}{2}$ avem $\frac{1}{4}<\frac{1}{2}$.

Înainte și după