Quantificadores e Predicados

Prévia do material em texto

Quantificadores, Predicados e Validade 
Quantificadores e Predicados 
Introdução 
 
A lógica proposicional não pode expressar adequadamente o significado de algumas 
proposições em matemática e em linguagem natural 
Por exemplo, suponha que "Todo computador conectado a rede esta funcionando". 
Funções proposicionais e quantificadores 
 
Seja A um conjunto dado. Uma função proposicional definida em A é uma expressão p(x) 
que tem a propriedade que p(a) é verdadeira ou falsa para cada a ϵ A. 
P(x) se torna uma declaração (com valor lógico) sempre que algum elemento a ϵ A é 
substituído pela variável x. 
O conjunto A é dito o domínio de p(x) e o conjunto 𝑇𝑝 de todos os elementos de A para os 
quais p(a) é verdadeira é chamado conjunto verdade de p(x). 
𝑻𝒑 = { 𝒙: 𝒙ϵ A, p(x) é verdade } ou 𝑻𝒑 = { 𝒙: p(x)} 
Funções proposicionais e quantificadores 
 
Exemplo: 
Ache o conjunto verdade de cada função proposicional p(x) definida no conjunto N dos 
inteiros positivos. 
a. Seja p(x) “x+ 2> 7”. O conjunto verdade é: 
• {x: x ϵ N, x + 2> 7} = { 6, 7, 8,…}. 
b. Seja p(x) “x + 5 < 3”. O conjunto verdade é: 
• {x: x ϵ N, x + 5 < 3} = Ø 
c. Seja p(x) “x + 5 > 1”. O conjunto verdade é: 
• {x: x ϵ N, x + 5 > 1} = N. 
Quantificador universal 
 
Seja p(x) uma função proposicional definida em um conjunto A. Considere as expressões 
 
∀𝒙 ∈ 𝑨 𝒑 𝒙 ∀𝒙, 𝒑(𝒙) 
 
Leia: “Para todo x em A, p(x)” como uma declaração verdadeira. 
 
Exemplo: 
A proposição ∀𝑛 ∈ 𝑁 𝑛 + 4 > 3 apresenta a solução: 
Verdadeira: pois {n: n + 4 > 3} = {1, 2, 3, …} = N. 
A proposição ∀𝑛 ∈ 𝑁 𝑛 + 2 > 8 apresenta a solução: 
Falsa: pois {n: n + 2 > 8} = {7, 8, …} ≠ N. 
 
 
Quantificador Existencial 
 
Seja p(x) uma função proposicional definida em um conjunto A. Considere as expressões 
 
∃𝒑 𝒙 ∃𝒙, 𝒑(𝒙) 
 
Leia: “Existe pelo menos um x em A, p(x)” como uma declaração verdadeira. 
 
Exemplo: 
A proposição ∃𝑛 ∈ 𝑁 𝑛 + 4 < 7 apresenta a solução: 
Verdadeira: pois {n: n + 4 < 7} = {1, 2}. 
A proposição ∃𝑛 ∈ 𝑁 𝑛 + 6 < 4 apresenta a solução: 
Falsa: pois {n: n + 6 < 4} = Ø ≠ N. 
 
 
Predicados 
 Sentenças que envolvem variáveis, tais como 
•"x > 3“ 
•"x = y + 3“ 
•"x + y = z“ 
•"computador x esta sob ataque de um hacker“ 
•"computador x esta funcionando" 
 não são verdadeiras nem falsas quando o valor das variáveis não e especificado. 
 A declaração "x maior que 3“ tem duas partes: 
•a variável x, é o sujeito da oração 
•o predicado "e maior que 3" 
 A declaração "x e maior que 3"pode ser representada por P(x) 
 A declaração recebe o nome de função proposicional P em x. 
Exemplos: 
 
Seja P(x) a declaração "x > 3". Quais os valores-verdade de P(4) e P(2)? 
 Solução: P(4) e a proposição "4 > 3"que e verdadeira. 
 P(2) e a proposição "2 > 3", que e falsa. 
 Seja Q(x; y) a declaração "x = y + 3". Quais os valores-verdade de Q(1; 2) e Q(3; 0)? 
 Solução: Q(1; 2) e a proposição "1 = 2 + 3", que e falsa. 
 Q(3; 0) e a proposição "3 = 0 + 3", que e verdadeira. 
 Considere a afirmação: if x > 0 then x := x + 1. 
Se P(x), que e "x > 0"for verdadeiro o comando "x := x + 1"e executado. Caso contrário, o 
valor de x não é incrementado. 
Seja A(x) a declaração "O computador x está sendo invadido por um hacker". Invadidos: 
[CS2, MATH1]. 
 Quais os valores-verdade de A(CS1); A(CS2) e A(MATH1)? 
CS1 = Falso, CS2 = Verdadeiro e Math1 = Verdadeiro. 
Quanticadores 
 Definição: A quantificação universal de P(x) é a afirmação "P(x) é válida para todos os 
valores de x do domínio". 
 A notação P(x) indica a quantificação universal de P(x). 
 Seja P(x) a declaração "x + 1 > x". Qual é o valor-verdade da quantificação P(x), no domínio 
de todos os números reais? 
 Solução: Como P(x) é verdadeira para todo número real x a quantificação P(x) é verdadeira. 
 A quantificação universal pode ser expressa de outras maneiras: 
• “para todos os" 
• "para cada" 
• "dado qualquer" 
• "para qualquer 
Quantificadores 
 Seja Q(x) a declaração "x < 2". Qual e o valor verdade da quantificação xQ(x), no domínio 
de todos os números reais? 
 Solução: Q(x) não e verdadeira para todo numero real x, porque Q(3) e falsa. 
 O que significa dizer xN(x) se N(x) é "O computador x esta conectado a rede“ e o 
domínio são todos os computadores do campus? 
 Solução: A declaração xN(x) significa que, para todo computador x no campus, x esta 
conectado a rede. 
 "Todo computador no campus esta conectado a rede". Verdadeira. 
Quantificadores 
 Definição: A quantificação existencial de P(x) e a armação "Existe um elemento x no 
domínio tal que P(x) e válida". 
 A notação ƎxP(x) indica a quantificação existencial de P(x). 
 Seja P(x) a declaração "x > 3". Qual e o valor-verdade da quantificação ƎxP(x), no domínio 
de todos os números reais? 
 Solução: Como P(x) e verdadeira para alguns números reais, por exemplo x = 4, a 
quantificação ƎxP(x) e verdadeira. 
 A quantificação existencial pode ser expressa de outras maneiras: 
"existe um“ 
"existe pelo menos um“ 
"para algum x" 
 A notação ƎxP(x) indica que "Existe pelo menos um x tal que P(x) e verdadeira". 
Quantificadores 
 Seja Q(x) a declaração "x = x + 1". Qual e o valor verdade da quantificação ƎxQ(x), no 
domínio de todos os números reais? 
 Solução: Como Q(x) e falsa para todos os números reais, a quantificação não e verdadeira. 
 Qual o valor-verdade de ƎxP(x), em que P(x) e a proposição "𝑥2 > 10" e o domínio e o 
conjunto dos inteiros positivos que não excedem 4? 
 Solução: Como o domínio e 1; 2; 3; 4, a proposição ƎxP(x) e verdadeira. 
Negando Expressões Quantificadas 
 Seja a declaração "Todo estudante na sua classe teve aulas de cálculo.". Esta declaração 
pode ser expressa por xP(x) em que P(x) e a declaração "x teve aulas de calculo“ e o 
domínio consiste de todos os estudantes de sua classe. 
 A negação desta declaração e "Existe um estudante em sua classe que não teve aula de 
cálculo". 
 Seja a declaração "Existe um estudante na sua classe que teve aulas de calculo." 
 A negação desta declaração e "Todo estudante nesta classe não teve aulas de calculo." 
Descreva cada um dos conjuntos a seguir: 
Suponha que A é dado por: 
 
 
 
Calcule A. 
 
A = {0, 1, 8} 
Suponha que B é dado por: 
 
 
 
Calcule B. 
 
Fazendo y = 0, temos x = 0; 
Fazendo y = 1, temos x = 0, 1 
Fazendo y = 2, temos x = 0, 1, 2 
Então, B consiste em todos os inteiros não negativos menores ou iguais a algum inteiro 
não negativo, o que significa: 
B = N 
Suponha que C é dado por: 
 
 
 
Calcule C. 
 
C = {0} 
 
Zero é o único inteiro não negativo que é menor ou igual a todos os inteiros não 
negativos. 
Sejam: 
 
A = { x I x ∈ N e x ≥ 5} 
B = {10, 12, 16, 20} 
C= { x / (∃y)(y ∈ N e x = 2y} 
 
Quais as proposições abaixo são verdadeiras? 
 
a. B ⊆ C 
b. A ⊆ C 
c. B ⊂ A 
d. 26 ∈ C 
e. {11, 12,13} ⊆ A 
f. { 11, 12, 13} ⊂ C 
g. {x I x ∈ N e x < 20} ⊂ B. 
Verdadeira 
Falsa 
Falsa 
Verdadeira 
Falsa 
Falsa 
Falsa 
Sejam: 
 A = {x I x ∈ N* e x é par} 
 B = {x I (∃y)(y ∈ N e x = 2y + 1} 
Subconjuntos de N. estabeleça as relações de união e interseção entre os conjuntos. 
O conjunto A ={2, 4, 6, 8,....} 
O conjunto B ={1, 3, 5, 7,...} 
Então: 
A ⋃ B = N* ......... A’= B. 
A ⋂ B = 𝞥........... são disjuntos. 
Exemplo: 
Justifique o valor verdade de cada uma das proposições quantificadas: 
• ∀𝑛 ∈ 𝑁 𝑛 < 1 
• ∃𝑛 ∈ 𝑁 𝑛 < 1 
 
• ∀𝑛 ∈ 𝑁 𝑛! < 10 
• ∃𝑛 ∈ 𝑁 𝑛!< 10 
• 
• ∀𝑛 ∈ 𝑁 ∗ 𝑛 + 1 > 1 . 
• ∃𝑛 ∈ 𝑁 ∗ 𝑛 + 1 > 1 
 
• ∀𝑛 ∈ 𝑁 ∗ 2𝑛 é 𝑝𝑎𝑟 . 
• ∃𝑛 ∈ 𝑁 ∗ 2𝑛 é 𝑝𝑎𝑟 
Observe que, nos itens acima, sempre 
que uma proposição quantificada 
universalmente é verdadeira, a mesma 
proposição, mas quantificada 
existencialmente, também é 
verdadeira. Esta observação vale 
sempre? 
• ∀𝑛 ∈ 𝑁 𝑛 < 1 é 𝑓𝑎𝑙𝑠𝑎. 
• ∃𝑛 ∈ 𝑁 𝑛 < 1 é 𝑣𝑒𝑟𝑑𝑎𝑑𝑒𝑖𝑟𝑎. 
 
• ∀𝑛 ∈ 𝑁 𝑛! < 10 é 𝑓𝑎𝑙𝑠𝑎. 
• ∃𝑛 ∈ 𝑁 𝑛! < 10 é 𝑣𝑒𝑟𝑑𝑎𝑑𝑒𝑖𝑟𝑎. 
 
• ∀𝑛 ∈ 𝑁 ∗ 𝑛 + 1 > 1 é 𝑣𝑒𝑟𝑑𝑎𝑑𝑒𝑖𝑟𝑎. 
• ∃𝑛 ∈ 𝑁 ∗ 𝑛 + 1 > 1 é 𝑣𝑒𝑟𝑑𝑎𝑑𝑒𝑖𝑟𝑎. 
 
• ∀𝑛 ∈ 𝑁 ∗ 2𝑛 é 𝑝𝑎𝑟 é 𝑣𝑒𝑟𝑑𝑎𝑑𝑒𝑖𝑟𝑎. 
• ∃𝑛 ∈ 𝑁 ∗ 2𝑛 é 𝑝𝑎𝑟 é 𝑣𝑒𝑟𝑑𝑎𝑑𝑒𝑖𝑟𝑎.