aula4 Predicados e Quantificadores - Prof César

Prévia do material em texto

' $
PREDICADOS E QUANTIFICADORES
Prof. Ce´sar Francisco de Moura Couto
Matema´tica Discreta
& %
' $
CEFET-MG Predicados e Quantificadores
Traduzindo do Portugueˆs para Expresso˜es Lo´gicas
• Expresse a sentenc¸a ”Todo estudante desta classe estudou ca´lculo”, usando predicados e
quantificadores.
• Soluc¸a˜o: Identificac¸a˜o do quantificador
– ”Para cada estudante desta classe, este estudante estudou ca´lculo.”
• Introduc¸a˜o da varia´vel do predicado.
– ”Para cada estudante x desta classe, x estudou ca´lculo.”
• C(x) e´ o predicado ”x estudo ca´lculo”. Para o dom´ınio de estudantes desta classe, a sentenc¸a
pode ser traduzida para ∀xC(x).
• E para o dom´ınio de todas as pessoas?
– ”Para cada pessoa x, se x e´ um estudante desta classe, enta˜o x estudou ca´lculo.”
• Esta sentenc¸a pode ser traduzida para ∀x(S(x)→ C(x)).
• A sentenc¸a ∀x(S(x) ∧ C(x)), esta´ correta?
Prof. Ce´sar Francisco de Moura Couto 1& %
' $
CEFET-MG Predicados e Quantificadores
Traduzindo do Portugueˆs para Expresso˜es Lo´gicas
• Expresse a sentenc¸a ”Algum estudante da classe visitou o Me´xico”e ”Todo estudante da classe
visitou o Canada´ ou Me´xico”.
• Soluc¸a˜o: Identificac¸a˜o do quantificador
– ”Existe um estudante da classe com a propriedade de que o estudante visitou o Me´xico.”
• Introduc¸a˜o da varia´vel do predicado.
– ”Existe um estudante x da classe com a propriedade de que x visitou o Me´xico.”
•M(x) e´ o predicado ”x visitou o Me´xico”. Para o dom´ınio de estudantes desta classe, a
sentenc¸a pode ser traduzida para ∃xM(x).
• E para o dom´ınio de todas as pessoas?
– ”Existe uma pessoa x que tem as propriedades de x ser estudante da classe e x visitou o
Me´xico.”
• Esta sentenc¸a pode ser traduzida para ∃x(S(x)→M(x)).
Prof. Ce´sar Francisco de Moura Couto 2& %
' $
CEFET-MG Predicados e Quantificadores
Traduzindo do Portugueˆs para Expresso˜es Lo´gicas
• Expresse a sentenc¸a ”Todo estudante da classe visitou o Canada´ ou Me´xico”.
• Soluc¸a˜o: Identificac¸a˜o do quantificador e introduc¸a˜o da varia´vel do predicado.
– ”Para cada estudante x, x tem a propriedade de ter visitado o Me´xico ou Canada´.”
• C(x) e´ o predicado ”x visitou o Canada´”, M(x) e´ o predicado ”x visitou o Me´xico”. Para o
dom´ınio de estudantes desta classe, a sentenc¸a pode ser traduzida para ∃x(C(x) ∨M(x)).
• E para o dom´ınio de todas as pessoas?
– ”Para cada pessoa x, se x e´ estudante da classe, enta˜o x tem a propriedade de x ter
visitado o Me´xico ou x ter visitado o Canada´.”
• Esta sentenc¸a pode ser traduzida para ∀x(S(x)→ (C(x) ∨M(x)).
Prof. Ce´sar Francisco de Moura Couto 3& %
' $
CEFET-MG Predicados e Quantificadores
Premissas e Conclusa˜o
• Expresse as sentenc¸as abaixo usando predicados e quantificadores, assumindo que o dom´ınio seja
todas as criaturas.
– ”Todos os leo˜es sa˜o selvagens.”
– ”Alguns leo˜es na˜o bebem cafe´.”
– ”Algumas criaturas selvagens na˜o bebem cafe´.”
• Soluc¸a˜o: Sejam P (x), Q(x) e R(x) as sentenc¸as ”x e´ um lea˜o”, ”x e´ selvagem”e ”x bebe
cafe´”.
– ∀x(P (x)→ Q(x))
– ∃x(P (x) ∧ ¬R(x)
– ∃x(Q(x) ∧ ¬R(x))
Prof. Ce´sar Francisco de Moura Couto 4& %
' $
CEFET-MG Predicados e Quantificadores
Premissas e Conclusa˜o
• Expresse as sentenc¸as abaixo usando predicados e quantificadores, assumindo que seja todos os
pa´ssaros.
– ”Todos os beija-flores sa˜o ricamente coloridos.”
– ”Nenhum pa´ssaro grande vive de ne´ctar”
– ”Pa´ssaros que na˜o vivem de ne´ctar sa˜o mono´tonos nas cores.”
– ”Beija-flores sa˜o pequenos”
• Soluc¸a˜o: Sejam P (x), Q(x), R(x) e S(x) as sentenc¸as ”x e´ um beija-flor”, ”x e´ grande”,
”x vive de nectar”e ”x e´ ricamente colorido”.
– ∀x(P (x)→ S(x))
– ¬∃x(Q(x) ∧R(x)
– ∀x(¬R(x)→ ¬S(x))
– ∀x(P (x)→ ¬Q(x))
Prof. Ce´sar Francisco de Moura Couto 5& %