1.2 Quantificatori
Ricordano che una formula è un’istruzione il cui valore di veritàpuò dipendere dai valori di alcune variabili. Ad esempio,
“x x\le 5 \ land x> 3$”
è vero per x x= 4 false e falso per x x = 6$. Confronta questo con l’istruzione
” Per ogni land x,, x x\le 5 \land x>3$,”
che è sicuramente falso e l’istruzione
” Esiste un x x such tale che x x\le 5 \ land x>3$,”
che è sicuramente vero. La frase “per ogni $x$”(a volte “per tutte le $x$”) è calleda quantificatore universale e viene indicata con $\forall x$. La frase “thereexists un x x such tale che” è chiamato un existentialquantifier ed è denotedby exists \ exists x$. Una formula che contiene variabili non è simplytrue o false a meno che ciascuna di queste variabili non sia vincolata da un quantificatore. Se una variabile non è vincolata, la verità della formula dipende dal valore assegnato alla variabile dall’universo del discorso.
Siamo stati attenti nella sezione 1.1 a definire con precisione i valori di verità delle affermazioni composte. Facciamo lo stesso perall\forall x\,P(x) and e exists\exists x\,P(x)$, anche se i significati previsti di questi sono chiari.
Il Quantificatore Universale
Una frase $\forall x\,P(x)$ è vera se e solo se $P(x)$ è vero nomatter che valore (dall’universo di discorso), è sostituito $x$.
Esempio 1.2.1
bullet\bullet for\forall x (x^2\ge 0) i,cioè “il quadrato di qualsiasi numero non è negativo.”
bullet\bullet for\forall x\,\forall y (x+y=y+x) i, cioè la legge commutativa dell’addizione.
bullet\bullet for\forall x\,\forall y\, \ forall z ((x+y)+z=x+(y+z)) i,cioè la legge associativa dell’addizione.
$\quadrato$
Il modulo “tutti”.Il quantificatore universale si incontra spesso nel seguente contesto:$$\forall x (P(x)\implica Q(x)),$$che può essere letta, “Tutte le $x$ soddisfacente $P(x)$ soddisfare$Q(x)$.”Le parentesi sono cruciali qui; assicurati di aver compreso la differenza tra il modulo “tutto” e \\forall x\, P(x)\implica\forall x\, Q(x) and e and (\forall x\, P(x)) \ implica Q(x)$.
Quest’ultima formula potrebbe anche essere scritta come for\forall x\,P(x)\implicesq(x)$, vale a dire che il quantificatore universale ha una precedenza superiore al condizionale; per evitare fraintendimenti,è meglio includere le parentesi. Il significato di questa formulamight non essere chiaro in un primo momento. La $x$ in $P(x)$ è vincolato da theuniversal quantificatore, ma la $x$ in $Q(x)$ non. La formula$(\forall x\,P(x))\implica Q(x)$ ha lo stesso significato di $(\forallx\P(x))\implica Q(y)$, e la sua verità dipende dal valore assegnatoa la variabile $Q(\cdot)$.
Esempio 1.2.2
$\bullet$ $\forall x$ ($x$ è un quadrato $\implica$ $x$ è un rettangolo),vale a dire, “tutte le piazze sono rettangoli.”
$\bullet$ $\forall x$ ($x$ vive in Walla Walla $\implica$ $x$ vive a Washington), vale a dire, “ogni persona che vive in Walla Walla vive a Washington.”
\ \ quadrato$
Questa costruzione a volte è usata per esprimere una frase matematica della forma “se questo, allora quello”, con un quantificatore “compreso”.
Esempio 1.2.3
$\bullet$ Se diciamo: “se $x$ è negativo, quindi è il suo cubo,” weusually significa “ogni negativo $x$ è negativo cubo.”Questo dovrebbe essere scritto simbolicamente come\ \ forall x ((x
\ \ bullet “”Se due numeri hanno lo stesso quadrato, allora hanno lo stesso valore assoluto” dovrebbe essere scritto come\\forall x\,\forall y ((x^2=y^2)\implica (\vert x \vert = \vert y \ vert))$.
$\bullet$ “Se $x=y$, allora $x+z=y+z$” dovrebbe essere scritto come $\forall x\,\forally\,\forall z ((x=y)\implies (x+z=y+z))$.
$\square$
Se $S$ è un insieme, la frase “ogni $x$ in $S$ soddisfa $P(x)$” iswritten formalmente come$$\forall x ((x\in S)\implica P(x))$$ Per chiarezza e brevità, questo di solito è scritto $\forall x\,{\i}\,S\,(P(x))$. Per comprendere e manipolare correttamente la formula properly\forallx\,{\in}\,S\, (P(x)) properly, a volte è necessario”unabbreviate”, riscrivendolo come \\forall x ((x\in S) \ implicesp(x))$.
Esempio 1.2.4
bullet\bullet \\forall x\in (\sqrt x\ge x) stands sta per\\forall x (x \in\implica \ sqrt x \ ge x).$
$\bullet$ $\forall x
$\square$
Il Quantificatore Esistenziale
Una frase $\exists x\,P(x)$ è vera se e solo se c’è leastone valore di $x$ (dall’universo di discorso) che rende $P(x)$ true.
Esempio 1.2.5
bullet\bullet exists\exists x (x \ge x^2) is è vero poiché x x=0 is è una soluzione. Ce ne sono molti altri.
bullet\bullet exists\exists x\,\exists y (x^2+y^2=2xy) is è vero poiché x x=y=1 is è una delle tante soluzioni.
$\quadrato$
La forma “alcuni”. Il existentialquantifier si incontra spesso nel seguente contesto: $$\exists x\(P(x)\land Q(x)),$$ che può essere letta, “Per $x$ soddisfacente $P(x)$ alsosatisfies $Q(x)$.”
Esempio 1.2.6
$\bullet$ $\exists x\, \hbox{($x$ è un professore $\terra$ $x$ è un repubblicano)}$, cioè, “un professore che è un repubblicano.”
$\bullet$ $\exists x\, \hbox{($x$ è un numero primo $\terra$ $x$ è ancora)}$, cioè,”qualche numero primo è anche.”
$\square$
può sembrare a prima vista che “Alcuni di $x$ soddisfacente $P(x)$soddisfa $Q(x)$” dovrebbe essere tradotto come$$\exists x (P(x)\implica Q(x)),$$come il quantificatore universale. Per capire perché questo non funziona,supponiamo che $P(x)=\hbox{“$x$ è una mela”}$ e $Q(x)=\hbox{“$x$ è anorange.”}} La frase “alcune mele sono arance” è certamentefalse, ma exists\esiste x (P(x)\implica Q (x)) $ $ è vero. Per vedere questo supponiamo che x x_0 is sia un particolare arancione. Quindi P P(x_0) \implica Q(x_0) evalu valuta$\hbox{F} \implica \ hbox{T}$, che è T, e il quantificatore esistenziale è soddisfatto.
Usiamo abbreviazioni del modulo “alcuni”molto simili a quelle del modulo” tutti”.
Esempio 1.2.7
$\bullet$ $\exists x
$\bullet$ $ \exists x\in (2x^2+x =1)$ sta per $ \exists x ((x\a )\land (2x^2+x=1))$$\square$
Se $\forall$ corrisponde a “tutti” e $\exists$ corrisponde a “qualche”abbiamo bisogno di un terzo del quantificatore corrispondere a “nessuno”? Come mostra quanto segue, questo non è necessario:
Esempio 1.2.8
$\bullet$ “Non democratici, repubblicani,” può essere scritto $\forall x$ ($x$ è un democristiano $\implica$ $x$ non è un repubblicano).
$\bullet$ “triangoli sono rettangoli,” può essere scritto $\forall x$ ($x$ è un triangolo $\implica$ $x$ non è un rettangolo).
$\square$
In generale, l’affermazione “nessun $x$ soddisfacente $P(x)$ soddisfa $Q(x)$” può essere scritto $$\forall x (P(x)\comporta \lnot Q(x)).$ $(Potresti chiederti perché non usiamo x \lnot \ exists x\, (P (x)\land Q(x))$. In effetti, potremmo-è equivalente a \ \ forall x (P (x) \ implica \ lnot Q(x))$.)
Esercizi 1.2
In questi problemi, supponiamo che l’universo del discorso sia il numero reale.
Ex 1.2.1 Esprimere le seguenti formule con quantificatori:
a) Qualsiasi numero elevato alla quarta potenza non è negativo.
b) Qualche numero elevato alla terza potenza è negativo.
c) Il seno di un angolo è sempre compreso tra $ + 1 and e $-1..
d) La secante di un angolo non è mai strettamente compresa tra + + 1 and e $-1..
Ex 1.2.2 Supponiamo che sets X and e Y Y are siano insiemi. Esprimere quanto segue come formule che coinvolgono quantificatori.
a) Ogni elemento di X X is è un elemento di Y Y..
b) Qualche elemento di X X is è un elemento di Y Y..
c) Qualche elemento di X X is non è un elemento di Y Y..
d) Nessun elemento di X X is è un elemento di Y Y..
Ex 1.2.3 Richiamo (dal calcolo) che una funzione f f is sta aumentando se if \forall a \forall b (a
a) f f is sta diminuendo.
b) f f is è costante.
c) f f has ha uno zero.
Ex 1.2.4 Esprimere simbolicamente le seguenti leggi:
a) la legge commutativa della moltiplicazione
b) la legge associativa della moltiplicazione
c) la legge distributiva
Ex 1.2.5 Le seguenti frasi sono vere o false?
a) $\forall x \forall y (x
b) $\forall x \forall y \forall z\ne 0 (xz=yz\implica x=y)$
c) $\exists x
d) $\exists x \exists y \esiste z (x^2+y^2+z^2=2xy-2+2z)$
Ex 1.2.6 Supponiamo che $P(x)$ e $Q(y)$ sono le formule.
a) È equivalent\forall x \forall y (P(x)\implica Q(y)) equivalent equivalente a \\forall x(P(x)) \implica \ forall y(Q(y))$?
b) È equivalent \exists x\exists y (P(x) \land Q(y)) equivalent equivalente a equivalent \exists x(P(x)) \land \ exists y(Q(y))$?