Slides 04

Prévia do material em texto

1
Matemática Discreta
Aula nº 4
Francisco Restivo
2006-03-10
2
Argumentos:
Um argumento é constituído por um conjunto de proposições, 
chamadas premissas, e por uma outra proposição, chamada 
conclusão.
Um argumento é válido se a conclusão é uma consequência 
lógica da conjunção das premissas:
P1 Ù P2 Ù P3 Ù ... + Q
(P1 Ù P2 Ù P3 Ù ...) ® Q é um tautologia.
p: o cão morde o gato
q: o gato não gosta do cão
P1: p ® q
P2: p
Q: q
É válido?
2
3
Programa Boole
do livro Language, Proof & Logic, de Barwise e Etchmendy
4
Será válido o seguinte argumento?
O João sai se e só se lavar a louça.
Se o João sai então não vê televisão.
Então ou vê televisão ou lava a louça, mas nunca 
as duas coisas.
Basta um contra-exemplo:
NÃO É VÁLIDO!
3
5
Lógica de predicados
Um predicado é uma propriedade de um ou vários objectos ou 
indivíduos.
Uma proposição é constituída por um sujeito e por um predicado.
Predicados representam-se com letras maiúsculas
B: joga bem
G: ganha
Objectos ou indivíduos representam-se com letras 
minúsculas
d: Deco
p: Portugal
B(d) ® G(p)
Se Deco joga bem então Portugal ganha
6
Nomes
Numa proposição simples há um sujeito e um predicado: 
B(c): o Cristiano Ronaldo joga bem
c representa o nome de um sujeito concreto
Variáveis
Podemos usar uma variável x: B(x) 
não sabemos se esta proposição é verdadeira ou falsa!
Depende do valor concreto que x assumir.
Quantificadores
Quantificador universal: "x B(x) | para todos
Quantificador existencial: $x B(x) | existe pelo menos um
4
7
Exemplo:
Traduzir para linguagem lógica: Todos os ratos são cinzentos
Predicados: R e C
Tradução: "x [R(x) ® C(x)]
Outro exemplo:
Traduzir para linguagem lógica: Alguns ratos são cinzentos
Predicados: R e C
Tradução: $x [R(x) Ù C(x)]
Mais um exemplo:
Traduzir para linguagem lógica: Não há ratos verdes
Predicados: R e V
Tradução: ¬$x [R(x) Ù V(x)]
8
Predicados envolvendo dois sujeitos:
P(x, y): x + y = 7 | universo do discurso: os números reais
8 proposições diferentes:
"x $y P(x, y) V $y "x P(x, y) F
"y $x P(x, y) V $x "y P(x, y) F
"y "x P(x, y) F "x "y P(x, y) F (equivalentes)
$y $x P(x, y) V $x $y P(x, y) V (equivalentes)
Negação de funções proposicionais quantificadas:
¬"x F(x) º $x (¬F(x))
¬$x F(x) º "x ¬F(x)
Outras equivalências:
¬"x (¬F(x)) º $x F(x)
¬$x (¬F(x)) º "x F(x)
5
9
Argumentos em lógica de predicados:
Todos os que têm olhos verdes não são de confiar. O António 
tem olhos verdes. Logo, o António não é de confiar.
V(x): x tem olhos verdes
C(x): x é de confiar
a: António
"x [V(x) ® ¬C(x)]
V(a)
--
¬C(a)
Parece que sim. Como se prova?
Que regras são válidas?
10
Regras de inferência para quantificadores:
Especificação do universal: 
se "x F(x) é verdade, então F(a) é verdade para qualquer a
Generalização universal: 
se F(a) é verdade para qualquer a, então "x F(x) é verdade
Especificação do existencial: 
se $x F(x) é verdade, então existe um elemento a tal que F(a) 
é verdade
Generalização existencial: 
se existe um elemento a tal que F(a) é verdade, então $x F(x) 
é verdade
6
11
Outras regras de inferência:
(p Ù q) + p Simplificação
(p Ù q) + q Simplificação
p + (p Ú q) Adição
((p Ú q) Ù ¬p) + q Silogismo disjuntivo
((p ® q) Ù p) + q Modus ponens
((p ® q) Ù ¬q) + ¬p Modus tollens
((p ® q) Ù (q ® r) + (p ® r) Silogismo hipotético
(p ® q) + (p ® (q Ù p)) Absorção
12
A prova:
V(x): x tem olhos verdes
C(x): x é de confiar
a: António
1. "x [V(x) ® ¬C(x)] Premissa
2. V(a) Premissa
3. V(a) ® ¬C(a) Especificação do universal (1)
4. ¬C(a) Modus ponens (3, 2)