Lista 16 - quantificadores

Prévia do material em texto

Lo´gica com Quantificadores - Sec¸o˜es 1.3, 1.4, 1.5
1) Considere os predicados:
P (x): x e´ par.
Q(x): x e´ menor do que 5.
R(x): x e´ primo.
Determine o maior subconjunto de U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} onde cada proposic¸a˜o e´ verda-
deira:
(a) P (x) =⇒ Q(x) ∨R(x)
(b) (¬P (x)⇔ Q(x)) ∧R(x)
2) Encontre um domı´nio e predicados tais que cada uma das proposic¸o˜es abaixo seja verdadeira.
(a) ∃xP (x) ∧ ∃xQ(x) ∧ ¬∃xP (x) ∧Q(x)
(b) ∃x¬(P (x) ∨Q(x)) ∧ ∀xP (x)→ Q(x)
(c) ∃x∃yP (x, y) ∧ ∃x∃y¬P (x, y)
(d) ∃x∀yP (x, y) ∧ ∃y∃x¬P (x, y) ∧ ∃y∀xP (x)
3) Encontre um domı´nio e predicados tais que cada uma das proposic¸o˜es do exerc´ıcio anterior seja
falsa.
4) V ou F?
(a) Dado o universo U = {−1, 0, 1} e o predicado P (x, y) : x2 = y,
e´ verdade que ∃x∀yP (x, y)
(b) Dado o universo U = {−1, 0, 1} e o predicado P (x, y) : x2 = y,
e´ verdade que ∀x∃yP (x, y)
(c) Dado o universo U = {−1, 0, 1} e o predicado Q(x, y) : x + y > 0,
e´ verdade que ∃x∀yQ(x, y)
(d) Dado o universo U = {−1, 0, 1} e o predicado Q(x, y) : x + y > 0,
e´ verdade que ∀x∃yQ(x, y)
5) Escreva as frases abaixo usando s´ımbolos lo´gicos. Voceˆ pode usar apenas nu´meros, pareˆnteses,
letras para serem os nomes das varia´veis, e os s´ımbolos: ∀ ∃ = · + ∧ ∨ ¬ →. Em todos os ı´tens, o
domı´nio e´ N. O ı´tem (a) e (b) ja´ esta´ feito, como exemplo.
(a) Todos os nu´meros sa˜o iguais a 4. Resposta: ∀x : x = 4
(b) Na˜o existe nenhum nu´mero igual ao seu quadrado. Resposta: ∀x : ¬(x = x · x)
(c) Nu´meros diferentes teˆm sucessores diferentes.
(d) x e´ mu´ltiplo de y
(e) x e´ primo.
(f) x e´ uma poteˆncia de 2.
1
(g) 1729 e´ a soma de dois cubos.
(h) Nenhuma soma de dois cubos e´ tambe´m um cubo.
(i) x e´ par.
(j) x e´ ı´mpar.
(k) 8 e´ maior do que x.
Para os pro´ximos itens, voceˆ pode usar a frase “x e´ primo” (ou qualquer outro nome de varia´vel
que quiser) ale´m dos s´ımbolos permitidos, caso ja´ tenha feito o item (e). Ou seja, voceˆ na˜o precisa
escrever “x e´ primo” com s´ımbolos lo´gicos va´rias vezes, basta uma vez!
(l) Todos os nu´meros ı´mpares sa˜o primos.
(m) Existe algum nu´mero primo maior do que 700.
(n) Existem infinitos nu´meros primos.
Quais dos ı´tens anteriores possuem varia´veis livres?
6) Escreva as frases abaixo usando s´ımbolos lo´gicos. Voceˆ pode usar apenas nu´meros, pareˆnteses,
letras para serem os nomes das varia´veis, e os s´ımbolos: ∀ ∃ = ·+ ∧ ∨ ¬ →.
(a) ∃!x : P (x)
(b) p⊗ q
(c) p↔ q
7) Escreva uma proposic¸a˜o que, quando verdadeira, indica que o domı´nio e´ um conjunto com pelo
menos 3 elementos. Voceˆ so´ pode usar os mesmos simbolos do exerc´ıcio anterior.
8) Decida se os argumentos sa˜o va´lidos
(a)
∀x : P (x)→ Q(x)
∀x : P (x)
−−−−−−−−
∀x : Q(x)
(b)
∀x : P (x)→ Q(x)
∃x : P (x)
−−−−−−−−
∀x : Q(x)
(c)
∀x : P (x)→ Q(x)
∃x : P (x)
−−−−−−−−
∃x : Q(x)
(d)
∃x : P (x)→ Q(x)
∃x : P (x)
−−−−−−−−
∃x : Q(x)
(e)
∀x : P (x)→ Q(x)
∀x : ¬Q(x)
−−−−−−−−
∀x : ¬P (x)
(f)
∀x : P (x)→ Q(x)
∀x : ¬(Q(x) ∧R(x))
∀x : R(x)
−−−−−−−−−−
∀x : ¬P (x)
2
(g)
∀x : P (x) ∧Q(x)
∀x : R(x)→ ¬Q(x)
∀x : S(x)→ ¬P (x)
−−−−−−−−−−−−−−−−
∀x : (S(x)→ Q(x)) ∧ (R(x)→ P (x))
(h)
∀x : P (x) ∧Q(x)
∀x : R(x)→ ¬Q(x)
∀x : S(x)→ ¬P (x)
−−−−−−−−−−−−−−−−
∃x : (S(x)→ Q(x)) ∧ (R(x)→ P (x))
9) Decida se os argumentos sa˜o va´lidos
a)
∀x[P (x)→ (Q(x) ∨R(x))]
∃x[P (x) ∧Q(x)]
∃x[P (x) ∧R(x)]
−−−−−−−−−−−−−
∀xP (x)
b)
∀x[R(x) ∨ S(x)]
∀x[R(x)→ P (x)]
∃x[S(x) ∧ ¬P (x)]
−−−−−−−−−−−−−
∃x∀y[P (x)→ Q(y)]
c)
∀x[P (x)→ ¬(Q(x) ∨R(x))]
∃x[P (x) ∧Q(x)]
∃x[Q(x) ∨R(x)]
−−−−−−−−−−−−−
∃x[¬P (x)] ∧ ∃x[¬R(x)]
d)
∀x∃y[P (x, y)]
∀x∀yP (x, y)→ Q(x)
∀x[Q(x)]
−−−−−−−−−−−−−
∃x[¬P (x)] ∧ ∃x[¬R(x)]
e)
∀x[P (x)→ Q(x)]
¬∃x[Q(x)]
∀x[¬(Q(x) ∧R(x))]
−−−−−−−−−−−
¬∃x[R(x)→ P (x)]
f)
∀x[R(x) ∨ S(x)]
∀x[R(x)→ P (x)]
∃x[S(x) ∧ ¬P (x)]
−−−−−−−−−
∀y∃x[P (x)→ Q(y)]
10) Suponha um domı´nio na˜o vazio. Suponha tambe´m que e´ verdadeira a proposic¸a˜o:
∃x∀yP (x, y).
O que podemos concluir sobre as seguintes proposic¸o˜es?
∃x∃yP (x, y)
∀x∀yP (x, y)
∀x∃yP (x, y)
11) Suponha um domı´nio na˜o vazio. Suponha tambe´m que e´ falsa a proposic¸a˜o:
∀x∀yP (x, y).
O que podemos concluir sobre as seguintes proposic¸o˜es?
∃x∃yP (x, y)
∃x∀yP (x, y)
∀x∃yP (x, y)
3
12) Encontre um predicado P (x, y) e domı´nios X e Y para suas duas varia´veis tais que as seguintes
proposic¸o˜es sejam todas simultaneamente verdadeiras.
(Note que os conjuntos X e Y devem ser conjuntos nume´ricos, para que as comparac¸o˜es como
x1 < x2 fac¸am sentido.)
∀x1∀x2∀y1∀y2 : (P (x1, y1) ∧ P (x2, y2) ∧ (x1 < x2))→ (y1 < y2)
∃z : (z ∈ X ∧ z /∈ Y )
∀x∃y :P (x, y)
13) Encontre um predicado P (x, y) e domı´nios X e Y para suas duas varia´veis tais que as pro-
posic¸o˜es do item anterior sejam todas simultaneamente verdadeiras, e tambe´m seja verdadeira a pro-
posic¸a˜o ∀z : z ∈ Y → z ∈ X.
14) Nas questo˜es de mu´ltipla escolha abaixo, ale´m de marcar a resposta certa, tambe´m reescreva
a pergunta e a resposta certa usando s´ımbolos lo´gicos e quantificadores, definindo predicados conforme
necessa´rio.
14.1) Supondo a verdade da sentenc¸a aberta: Alguns investigados sa˜o advogados mas nem todos
os investigados teˆm domic´ılio conhecido. Podemos deduzir a verdade da alternativa:
(a) Todos investigados sa˜o advogados e teˆm domic´ılio conhecido.
(b) Todos investigados sa˜o advogados e na˜o teˆm domic´ılio conhecido.
(c) Alguns investigados sa˜o advogados e teˆm domic´ılio conhecido.
(d) Alguns investigados sa˜o advogados e alguns investigados teˆm domic´ılio conhecido.
(e) Alguns investigados sa˜o advogados e alguns investigados na˜o teˆm domic´ılio conhecido.
14.2) Todas as pessoas que conhecem os irma˜os Bernardo e Bianca gostam de Bianca. Entretanto,
algumas pessoas que conhecem Bianca na˜o gostam dela. E´ correto concluir que:
(a) todos os que conhecem Bianca gostam dela;
(b) ningue´m gosta de Bianca;
(c) alguns que conhecem Bianca na˜o conhecem Bernardo;
(d) quem conhece Bernardo gosta de Bianca;
(e) so´ quem conhece Bernardo e Bianca conhece Bianca.
14.3) Considere a afirmac¸a˜o: “Toda pessoa que faz exerc´ıcios na˜o tem pressa˜o alta”. De acordo
com essa afirmac¸a˜o e´ correto concluir que
(a) se uma pessoa tem pressa˜o alta enta˜o na˜o faz exerc´ıcios.
(b) se uma pessoa na˜o faz exerc´ıcios enta˜o tem pressa˜o alta.
(c) se uma pessoa na˜o tem pressa˜o alta enta˜o faz exerc´ıcios.
(d) existem pessoas que fazem exerc´ıcios e que teˆm pressa˜o alta.
(e) na˜o existe pessoa que na˜o tenha pressa˜o alta e na˜o fac¸a exerc´ıcios.
14.4) Considere como verdadeira a proposic¸a˜o: “Nenhum matema´tico e´ na˜o diale´tico”. Laura
enuncia que tal proposic¸a˜o implica, necessariamente, que
I. se Carlos e´ matema´tico, enta˜o ele e´ diale´tico.
II. se Pedro e´ diale´tico, enta˜o e´ matema´tico.
III. se Luiz na˜o e´ diale´tico, enta˜o na˜o e´ matema´tico.
IV. se Renato na˜o e´ matema´tico, enta˜o na˜o e´ diale´tico.
Das implicac¸o˜es enunciadas por Laura, esta˜o corretas APENAS
(a) I e III.
(b) I e II.
(c) III e IV.
(d) II e III.
(e) II e IV.
4