1.2 quantificadores
recordar que uma fórmula é uma declaração cujo valor da verdade pode depender dos valores de algumas variáveis. Por exemplo,
” $x\le 5 \land x> 3$”
é verdadeiro para $x = 4$ e falso para$x = 6$. Compare isso com a instrução
“Para cada $x$, $x\le 5 \x terra>3$,”
o que é definitivamente falso e a instrução
“existe $x$ tal que $x\le 5 \x terra>3$,”
o que é definitivamente verdadeiro. A frase “for every $x$” (sometimes “for all $x$”) é um quantificador universal da calleda e é denotado por $\forall x$. A frase “existe um $X$ tal que” é chamado de quantificador existencial e é denotado por $\existe x$. Uma fórmula que contém variáveis não é simplytrue ou falso a menos que cada uma dessas variáveis esteja ligada por um quantificador. Se uma variável não está ligada, a verdade da fórmula depende do valor atribuído à variável do universo do discurso.
nós fomos cuidadosos na secção 1.1 para definir os valores de verdade de afirmações compostas precisamente. Nós fazemos o mesmo para$\forall x\,P(x)$ e $\existe x\,P(x)$, embora os significados pretendidos destes são claros.
the Universal Quantifier
A sentence $\forall x\, P(x)$ is true if and only if $P (x)$ is true nomatter what value (from the universe of discourse) is substituted for $x$.
exemplo 1.2.1
$ \ bullet$ \forall x (x^2\ge 0)$,i.e., “o quadrado de qualquer número não é negativo.”
$\bullet$ $ \forall x\,\forall y (x+y=y+x)$, i.e., a lei comutativa da adição.
$ \ bullet$ \forall x\,\forall y\,\forall z (((x+y)+z=x+(y+z))$,i.e., a lei associativa da adição.
$\square$
a forma “tudo”.O quantificador universal é frequentemente encontrado no seguinte contexto:$$\forall x (P(x)\implica Q(x)),$$que pode ser lido, “Todo $x$ satisfazer $P(x)$, também, satisfazer$Q(x)$.”Os parêntesis são cruciais aqui; certifique-se que compreende a diferença entre a forma “todos” e $\forall x\,P(x)\implica\forall x\,Q(x)$ e $(\forall x\,P(x))\implica Q(x)$.
a última fórmula também pode ser escrita como $\forall x\, P(x)\impliesQ (x)$, o que quer dizer que o quantificador universal tem maior precedência do que o condicional; para evitar mal-entendidos,é melhor incluir os parênteses. O Significado desta fórmula pode não ser claro no início. O $x$ em $P(x)$ está vinculado pelo quantificador universal, mas o $x$ em $Q (x)$ não está. A fórmula$(\forall x\a,P(x))\implica Q(x)$ tem o mesmo significado como $(\forallx\,P(x))\implica Q(y)$, e a sua verdade depende do valor assignedto a variável $Q(\cdot)$.
exemplo 1.2.2
$ \ bullet$ $ \forall x$ ($x$ é um quadrado $ \implica$ x$ é um retângulo), ou seja, “todos os quadrados são retângulos.”
$\bullet$ $\forall x$ ($x$ vidas em Walla Walla $\implica$ $x$ vive em Washington), i.é., “toda pessoa que vive em Walla Walla vive em Washington.
$\square$
esta construção às vezes é usada para expressar a sentença amatemática da forma “se isto, então aquilo”, com um quantificador”compreendido”.
exemplo 1.2.3
$\bullet$ If we say, ” if $x$ is negative, so is its cube, “weusually mean” every negative $X$ has a negative cube.”Este deve ser escrito simbolicamente como$\forall x ((x
$\bullet$ “Se dois números têm o mesmo quadrado, então eles têm o mesmo valor absoluto” deve ser escrito como$\forall x\,\forall y ((x^2=y^2)\implica(\vert x\vert = \vert y\vert))$.
$\bullet$ “Se $x=y$, então $x+z=y+z$” deve ser escrito como $\forall x\,\forally\,\forall z ((x=y)\implica (x+z=y+z))$.
$\quadrado$
Se $S$ é um conjunto, a frase “todo $x$ em $S$ satisfaz $P(x)$” iswritten formalmente como$$\forall x ((x\S)\implica P(x))$$ Para maior clareza e brevidade, este é geralmente escrito $\forall x\,{\in}\S\(P(x))$. Para compreender e manipular a fórmula $\forallx\,{\in}\,S\, (P(x))$ apropriadamente, você às vezes vai precisar de”unabbreviver” isto, reescrevendo-o como $\forall x ((x\in s)\impliesP(x))$.
Exemplo 1.2.4
$\bullet$ $\forall x\in\sqrt x\ge x)$significa $\forall x (x\in \implica \sqrt x\ge x).$
$\bullet$ $\forall x
$\quadrado$
O Quantificador Existencial
Uma frase, $\existe x\a,P(x)$ é verdadeiro se, e somente se, existe pelo leastone valor de $x$ (a partir de um universo de discurso) que faz o $P(x)$ true.
exemplo 1.2.5
$ \ bullet$ \ existe x (x \ge x^2)$é verdadeiro, uma vez que $x=0$ é uma solução. Há muitos outros.
$ \ bullet$ \exists x\,\exists y (x^2+y^2=2xy)$ is true since$x=y=1$ is one of many solutions.
$\square$
a forma “alguns”. O quantificador existencialé frequentemente encontrado no seguinte contexto: $$\existe x\(P(x)\land Q(x)),$$ que pode ser lido, “alguns $x$ satisfazendo $P(x)$ alsomatiza $Q(x)$.”
Exemplo 1.2.6
$\bullet$ $\existe x\, \hbox{($x$ é um professor de $\terras$ $x$ é um republicano)}$, i.é., “um professor é um republicano.”
$ \ bullet$ \existe x\, \hbox {($x$ é um número primo $\land$ x$ é par)}$, ou seja, ” algum número primo é par.”
$\quadrado$
à primeira vista parecer que “cerca de $x$ satisfazer $P(x)$satisfaz $Q(x)$” deve ser traduzido como$$\existe x (P(x)\implica Q(x)),$$, como o quantificador universal. Para ver por que isso não funciona,suponha que $P(x)=\hbox{“$x$ is an apple”}$ and $Q(x)=\hbox{“$x$ is anorange.”} $ A frase “algumas maçãs são laranjas” é certamente false, mas$\existe x (P(x)\implica Q(x))$$é verdadeiro. Para ver isto, suponha que $x_0 $ é uma laranja em particular. Então$P (x_0) \ implica Q (x_0)$ avalia para $\hbox{F}\implica \hbox{T}$,que é T, e o quantificador existencial é satisfeito.
usamos abreviaturas do “Alguns”formam-se muito como aquelas para a forma” todos”.
Exemplo 1.2.7
$\bullet$ $\existe x
$\bullet$ $ \existe x\in (2x^2+x =1)$ significa $ \existe x ((x\in )\terra (2x^2+x=1))$$\quadrado$
Se $\forall$ corresponde a “todos” e $\existe$ corresponde a “alguns”não precisamos de um terceiro quantificador para corresponder com o “nada”? Como mostra a seguir, isso não é necessário:
exemplo 1.2.8
$\bullet$ “No democrats are republicans,” can be written $\forall x$ ($x$ is a democrat $\implies$ x $is not a republican).
$\bullet$ “Nenhum triângulos são retângulos,” pode ser escrito $\forall x$ ($x$ é um triângulo $\implica$ $x$ não é um retângulo).
$\square$
em geral, a afirmação “no $x$ satisfaz $P(x)$ satisfaz $Q(x)$” pode ser escrita $\forall x (P(x)\implica \lnot Q(x)).$$ $ (Você pode se perguntar Por que não usamos $\lnot \existe x\,(P(x)\land Q(x))$. Na verdade, poderíamos—é equivalente a $\forall x (P(x)\implica \lnot Q(x))$.)
Exercises 1.2
in these problems, assume the universe of discourse is thereal numbers.
Ex 1.2.1 Express the following as formulas involving quantificators:
a) qualquer número elevado à quarta potência não é negativo.
B) algum número elevado à terceira potência é negativo.
c) o seno de um ângulo é sempre entre $ + 1$ e $ -1$.
d) o Secante de um ângulo nunca está estritamente entre $ + 1$ e $ -1$.
Ex 1.2.2 suponha que $X$ e$ Y $ são conjuntos. Express the following as formulas involving quantificers.
a) todo elemento de $X$ é um elemento de $ Y$.
B) algum elemento de $X$ é um elemento de $Y$.
c) algum elemento de $X$ não é um elemento de $Y$.
d) nenhum elemento de $X$ é um elemento de $Y$.
Ex 1.2.3 Recall (from calculus) that a function $F$ is increasing if$$ \forall a \forall b (a
a) $f$ is decreasing.
B) $ F$ é constante.
C) $F $ tem um zero.As seguintes leis expressam simbolicamente::A) a lei comutativa da multiplicação (1933) a lei associativa da multiplicação (1933) a lei associativa da multiplicação (1933) a lei distributiva (1933) a lei distributiva (1933) a 5082 (3991) Ex 1.2.5 são as seguintes sentenças verdadeiras ou falsas?
a) $\forall x \forall y (x
b) $\forall x \forall y \forall z\ne 0 (xz=yz\implica x=y)$
c) $\existe x
d) $\existe x \existe y \existe z (x^2+y^2+z^2=2xy-2+2z)$
Ex 1.2.6 Suponha que $P(x)$ e $Q(y)$ são fórmulas.
a) é $\forall x \forall y (P (x) \ implica Q(y))$equivalente a $\forall x(P(x)) \implica \forall y(Q (y)$?
B) Is $\exists x \ exists y (p (x)\land Q (y))$equivalent to $\exists x(P(x)) \land \exists y(Q(y)$?