LOGICA 2

Prévia do material em texto

Lo´gica de Predicados Refereˆncias
Matema´tica Discreta
Lo´gica de Predicados
Profa. Sheila Morais de Almeida
DAINF-UTFPR-PG
agosto - 2016
Lo´gica de Predicados Refereˆncias
Quantificadores
Como expressar a sentenc¸a “Para todo nu´mero inteiro x , o valor de
x e´ positivo.” usando lo´gica proposicional?
Esta sentenc¸a conte´m duas caracter´ısticas distintas das anteriores:
• quantificadores,
• e predicados.
Lo´gica de Predicados Refereˆncias
Quantificadores
Quantificadores
Quantificadores sa˜o expresso˜es como “para todo”, “para cada”,
“para algum”, que dizem de alguma forma quantos objetos teˆm
uma certa propriedade.
Lo´gica de Predicados Refereˆncias
Quantificador Universal
∀x
Leˆ-se: para todo x , para cada x , todo x .
(∀x)(x > 0) representa a sentec¸a:
“Para todo nu´mero inteiro x , o valor de x e´ positivo.”
Lo´gica de Predicados Refereˆncias
Quantificador Universal
(∀x)(x > 0)
O quantificador e sua varia´vel sempre aparecem entre pareˆnteses.
Em seguida, outro par de pareˆnteses conte´m a propriedade, ou
predicado, referente a`quela varia´vel.
Quando o predicado na˜o foi definido, escreve-se: (∀x)P(x).
Lo´gica de Predicados Refereˆncias
Quantificador Universal
(∀x)(x > 0)
O valor-verdade da expressa˜o depende do dom´ınio da varia´vel.
Se o dom´ınio sa˜o os nu´meros inteiros positivos, enta˜o a expressa˜o
acima e´ verdadeira.
Se o dom´ınio sa˜o todos os nu´meros inteiros, enta˜o a expressa˜o
acima e´ falsa.
Lo´gica de Predicados Refereˆncias
Quantificador Universal
(∀x)P(x)
O valor-verdade da expressa˜o depende do dom´ınio da varia´vel.
Se o dom´ınio sa˜o todos os livros da biblioteca da UTFPR - Ponta
Grossa e o predicado, P(x), diz que x tem capa vermelha, enta˜o a
expressa˜o e´ falsa.
Lo´gica de Predicados Refereˆncias
Quantificador Universal
Deˆ o valor-verdade da expressa˜o (∀x)P(x) em cada uma das
interpretac¸o˜es:
• P(x) e´ a propriedade de que x e´ amarelo e o dom´ınio e´ o
conjunto de todas as flores. falso
• P(x) e´ a propriedade de que x e´ uma planta e o dom´ınio e´ o
conjunto de todas as flores. verdadeiro
• P(x) e´ a propriedade de que x e´ positivo ou negativo e o
dom´ınio e´ o conjunto dos nu´meros inteiros. falso
Lo´gica de Predicados Refereˆncias
Quantificador Universal
Deˆ o valor-verdade da expressa˜o (∀x)P(x) em cada uma das
interpretac¸o˜es:
• P(x) e´ a propriedade de que x e´ amarelo e o dom´ınio e´ o
conjunto de todas as flores. falso
• P(x) e´ a propriedade de que x e´ uma planta e o dom´ınio e´ o
conjunto de todas as flores. verdadeiro
• P(x) e´ a propriedade de que x e´ positivo ou negativo e o
dom´ınio e´ o conjunto dos nu´meros inteiros. falso
Lo´gica de Predicados Refereˆncias
Quantificador Existencial
∃x
Leˆ-se: para algum x , existe um x , pelo menos um x .
(∃x)(x > 0) representa a sentec¸a:
“Algum nu´mero inteiro x e´ positivo.”
Lo´gica de Predicados Refereˆncias
Quantificador Existencial
(∃x)(x > 0)
Da mesma forma, o valor-verdade da expressa˜o depende do
dom´ınio da varia´vel.
Se o dom´ınio conte´m um nu´mero positivo, enta˜o a expressa˜o e´
verdadeira.
Caso contra´rio, e´ falsa.
Lo´gica de Predicados Refereˆncias
Quantificador Existencial
(∃x)P(x)
O valor-verdade da expressa˜o depende do dom´ınio da varia´vel.
Se o dom´ınio sa˜o todos os livros da biblioteca da UTFPR - Ponta
Grossa e o predicado diz x tem capa vermelha, enta˜o a expressa˜o e´
verdadeira.
(Deve existir algum livro com capa vermelha na biblioteca!)
Lo´gica de Predicados Refereˆncias
Quantificadores - Interpretac¸a˜o
Exemplo: A expressa˜o (∀x)(∃y)Q(x , y) deve ser lida da seguinte
forma:
“Para cada x existe um y tal que a propriedade Q(x , y) e´
satisfeita.”
Deˆ o valor verdade da expressa˜o (∀x)(∃y)Q(x , y) para a seguinte
interpretac¸a˜o:
• Q(x , y) e´ a propriedade de que x < y e o dom´ınio e´ o
conjunto de todos os inteiros. verdadeiro
Lo´gica de Predicados Refereˆncias
Quantificadores - Interpretac¸a˜o
Exemplo: A expressa˜o (∀x)(∃y)Q(x , y) deve ser lida da seguinte
forma:
“Para cada x existe um y tal que a propriedade Q(x , y) e´
satisfeita.”
Deˆ o valor verdade da expressa˜o (∀x)(∃y)Q(x , y) para a seguinte
interpretac¸a˜o:
• Q(x , y) e´ a propriedade de que x < y e o dom´ınio e´ o
conjunto de todos os inteiros. verdadeiro
Lo´gica de Predicados Refereˆncias
Quantificadores - Interpretac¸a˜o
Deˆ o valor verdade da expressa˜o (∃x)(∀y)Q(x , y) para a seguinte
interpretac¸a˜o:
• Q(x , y) e´ a propriedade de que x < y e o dom´ınio e´ o
conjunto de todos os inteiros. falso
Conclusa˜o: a ordem dos quantificadores faz diferenc¸a.
Lo´gica de Predicados Refereˆncias
Quantificadores - Interpretac¸a˜o
Deˆ o valor verdade da expressa˜o (∃x)(∀y)Q(x , y) para a seguinte
interpretac¸a˜o:
• Q(x , y) e´ a propriedade de que x < y e o dom´ınio e´ o
conjunto de todos os inteiros. falso
Conclusa˜o: a ordem dos quantificadores faz diferenc¸a.
Lo´gica de Predicados Refereˆncias
Quantificadores - Interpretac¸a˜o
Constantes podem fazer parte do predicado.
Exemplo: o valor-verdade da expressa˜o (∀x)Q(x , 5) quando
Q(x , y) e´ a propriedade de que x < y e o dom´ınio de x e´ o
conjunto de todos os inteiros e´ ...falso
Exemplo: o valor-verdade da expressa˜o (∃y)Q(5, y) quando
Q(x , y) e´ a propriedade de que x < y e o dom´ınio de y e´ o
conjunto de todos os inteiros e´ ...verdade
Lo´gica de Predicados Refereˆncias
Quantificadores - Interpretac¸a˜o
Constantes podem fazer parte do predicado.
Exemplo: o valor-verdade da expressa˜o (∀x)Q(x , 5) quando
Q(x , y) e´ a propriedade de que x < y e o dom´ınio de x e´ o
conjunto de todos os inteiros e´ falso.
Exemplo: o valor-verdade da expressa˜o (∃y)Q(5, y) quando
Q(x , y) e´ a propriedade de que x < y e o dom´ınio de y e´ o
conjunto de todos os inteiros e´ verdade.
Lo´gica de Predicados Refereˆncias
Predicados bem formados
Expresso˜es devem obedecer regras de sintaxe para serem
predicados bem formados:
P(x)(∀x) ∧ (∃y) na˜o e´ um predicado bem formado.
• P(x) ∨ Q(y) (na˜o e´ predicado, na˜o tem quantificadores).
• (∀x)(P(x)→ Q(x)) e´ predicado bem formado e o escopo de
∀x e´ P(x)→ Q(x).
Lo´gica de Predicados Refereˆncias
Predicados bem formados
• (∀x)((∃y)(P(x , y) ∧ Q(x , y))→ R(x)) e´ predicado bem
formado.
• o escopo do quantificador ∀x e´
(∃y)[P(x , y) ∧ Q(x , y)]→ R(x);
• o escopo do quantificador ∃y e´ P(x , y) ∧ Q(x , y).
Lo´gica de Predicados Refereˆncias
Predicados bem formados
• (∃x)S(x) ∨ (∀y)T (y) e´ predicado bem formado.
Lo´gica de Predicados Refereˆncias
Varia´veis livres
Se uma varia´vel aparece em alguma fo´rmula bem formada e na˜o
faz parte de nenhum quantificador, enta˜o e´ uma varia´vel livre.
Exemplo: y e´ uma varia´vel livre em (∀x)[Q(x , y)→ (∃y)R(x , y)],
porque y ocorre pela primeira vez sem estar acompanhado de um
quantificador.
Nem sempre expresso˜es que conteˆm varia´veis livres teˆm
valor-verdade definido. (Lembre que sem valor-verdade definido
na˜o e´ sentenc¸a lo´gica!)
Lo´gica de Predicados Refereˆncias
Varia´veis livres
Exemplo: Considere o dom´ınio de todos os nu´meros inteiros.
P(x) : x > 0
Qual o valor verdade de P(y) ∧ P(5)?
Qual o valor verdade de P(y) ∨ P(5)?
Lo´gica de Predicados Refereˆncias
Varia´veis livres
Exemplo: Considere o dom´ınio de todos os nu´meros inteiros.
P(x) : x > 0
Qual o valor verdade de P(y) ∧ P(5)? indefinido
Qual o valor verdade de P(y) ∨ P(5)? verdade
Nos dois casos, y e´ uma varia´vel livre, na˜o esta´ associada a um
quantificador.
Lo´gica de Predicados Refereˆncias
Escopo dos quantificadores
Exemplo Para a fo´rmula bem formada:
(∀x)(∃y)[S(x , y) ∧ L(y , a)].
O escopode (∃y) e´ S(x , y) ∧ L(y , a).
O escopo de (∀x) e´ (∃y)[S(x , y) ∧ L(y , a).
Considere a interpretac¸a˜o onde o dom´ınio sa˜o todas as cidades
brasileiras; S(x , y) e´ a propriedade de que x e y esta˜o no mesmo
estado; e L(y , z) e´ a propriedade de que y e z comec¸am com a
mesma letra; e a e´ uma constante com o valor “Americana”.
Qual o valor-verdade nessa interpretac¸a˜o da wff?
Lo´gica de Predicados Refereˆncias
Traduc¸a˜o
Muitas frases podem ser escritas por predicados lo´gicos.
Considere a frase: “Todo papagaio e´ feio.”
E´ o mesmo que dizer: “Para qualquer coisa, se essa coisa e´ um
papagaio, enta˜o e´ feio.”
Lo´gica de Predicados Refereˆncias
Traduc¸a˜o
Muitas frases podem ser escritas por predicados lo´gicos.
Considere a frase: “Todo papagaio e´ feio.”
E´ o mesmo que dizer: “Para qualquer coisa, se essa coisa e´ um
papagaio, enta˜o e´ feia.”
Sejam P(x) : x e´ um papagaio e F (x) : x e´ feia.
Simbolicamente: (∀x)(P(x)→ F (x)).
Lo´gica de Predicados Refereˆncias
Traduc¸a˜o
Dica da Gersting: “o quantificador universal e o conectivo de
implicac¸a˜o quase sempre esta˜o juntos.”
Poder´ıamos substituir, neste contexto, (∀x)(P(x)→ F (x)) por
(∀x)(P(x) ∧ F (x))? Na˜o! nem tudo no mundo e´ papagaio
feio!
Lo´gica de Predicados Refereˆncias
Traduc¸a˜o
Dica da Gersting: “o quantificador universal e o conectivo de
implicac¸a˜o quase sempre esta˜o juntos.”
Poder´ıamos substituir, neste contexto, (∀x)(P(x)→ F (x)) por
(∀x)(P(x) ∧ F (x))? Na˜o! nem tudo no mundo e´ papagaio
feio!
Lo´gica de Predicados Refereˆncias
Traduc¸a˜o
Considere a frase: “Existe um papagaio feio.”
E´ o mesmo que dizer: “Existe uma coisa, que e´ um papagaio e e´
feia.”
Sejam P(x) : x e´ um papagaio e F (x) : x e´ feia.
Simbolicamente: (∃x)(P(x) ∧ F (x)).
Lo´gica de Predicados Refereˆncias
Traduc¸a˜o
Dica da Gersting: “o quantificador existencial e o conectivo ∧
quase sempre esta˜o juntos.”
Poder´ıamos substituir, neste contexto, (∃x)(P(x) ∧ F (x)) por
(∃x)(P(x)→ F (x))?
Lo´gica de Predicados Refereˆncias
Traduc¸a˜o
Poder´ıamos substituir, neste contexto, (∃x)(P(x) ∧ F (x)) por
(∃x)(P(x)→ F (x))?
O que precisa acontecer para que nosso predicado seja verdade?
Se na˜o existirem papagaios e´ verdade. Mas existem...
Enta˜o, para ser verdade, se existe um papagaio, ele tem que ser
feio. Mas isso na˜o e´ (sempre) verdade!
Enta˜o essa traduc¸a˜o esta´ mal feita.
Lo´gica de Predicados Refereˆncias
Traduc¸a˜o
A palavra “so´” e´ bastante problema´tica. Sua posic¸a˜o na frase,
muda completamente o significado da mesma:
So´ Joa˜o ama Maria.
Joa˜o so´ ama Maria.
Joa˜o ama so´ Maria.
Lo´gica de Predicados Refereˆncias
Traduc¸a˜o
Reescrevendo:
So´ Joa˜o ama Maria. Se alguma coisa ama Maria, enta˜o essa coisa
e´ Joa˜o.
Joa˜o so´ ama Maria. Se Joa˜o faz alguma coisa, enta˜o essa coisa e´
amar Maria.
Joa˜o ama so´ Maria. Se Joa˜o ama alguma coisa, enta˜o essa coisa e´
Maria.
Lo´gica de Predicados Refereˆncias
Traduc¸a˜o
Pra´tica:
Considere: S(x) : x e´ um estudante, I (x) : x e´ inteligente, e
M(x) : x gosta de mu´sica.
Escreva predicados bem formados para as seguintes sentenc¸as (o
dom´ınio sa˜o todas as pessoas):
1 Todos os estudantes sa˜o inteligentes.
2 Alguns estudantes inteligentes gostam de mu´sica.
3 Todos que gostam de mu´sica sa˜o estudantes estu´pidos.
4 So´ estudantes inteligentes gostam de mu´sica.
Lo´gica de Predicados Refereˆncias
Refereˆncias
GERSTING, Judith L. Mathematical Structures for Computer
Science 5th Ed.
	Lógica de Predicados
	Quantificadores
	Referências