apresentacao da aula 14

Prévia do material em texto

CCT0350 – MATEMÁTICA APLICADA A COMPUTAÇÃO
Aula 14: Cálculo dos Predicados
1
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
Negação de Fórmulas Quantificadas
Da definição de fórmula dada podemos perceber que um quantificador universal ou 
existencial pode ser precedido de uma negação. 
Regra da Negação do Quantificador Universal (~ ∀)
Uma fórmula do tipo ~( ∀x)b gera uma linha na qual escrevemos a fórmula ( ∀x)~b. 
2
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
Teorema: A negação de uma proposição da forma ∀x ∊ D, Q(x) é equivalente 
logicamente a proposição da forma  x ∊ D | ~Q(x). 
Temos: ~( ∀x ∊ D, Q(x))   x ∊ D | ~Q(x).
Exemplo:
P: ∀ número primo p, p é impar
3
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
Teorema: A negação de uma proposição da forma ∀x ∊ D, Q(x) é equivalente 
logicamente a proposição da forma  x ∊ D | ~Q(x). 
Simbolicamente temos: ~( ∀x ∊ D, Q(x))   x ∊ D | ~Q(x).
Exemplo:
P: ∀ número primo p, p é impar
~P:  um número primo p| p não é impar
4
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
Teorema: A negação de uma proposição da forma ∀x ∊ D, Q(x) é equivalente 
logicamente a proposição da forma  x ∊ D | ~Q(x). 
Simbolicamente temos: ~( ∀x ∊ D, Q(x))   x ∊ D | ~Q(x).
Exemplo:
P: ∀ número primo p, p é impar
~P:  um número primo p| p não é impar
Exemplo:
P: Alguns peixes respiram ar.
5
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
Teorema: A negação de uma proposição da forma ∀x ∊ D, Q(x) é equivalente 
logicamente a proposição da forma  x ∊ D | ~Q(x). 
Simbolicamente temos: ~( ∀x ∊ D, Q(x))   x ∊ D | ~Q(x).
Exemplo:
P: ∀ número primo p, p é impar
~P:  um número primo p| p não é impar
Exemplo:
P: Alguns peixes respiram ar.
~P: Nenhum peixe respira ar.
6
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
Teorema: A negação de uma proposição da forma ∀x ∊ D, Q(x) é equivalente logicamente a proposição da forma  x ∊ D | ~Q(x). Simbolicamente temos: ~( ∀x ∊ D, Q(x))   x ∊ D | ~Q(x).
Exemplo:
P: ∀ número primo p, p é impar
~P:  um número primo p| p não é impar
Exemplo:
P: Alguns peixes respiram ar.
~P: Nenhum peixe respira ar.
Observação: é errado dizer alguns peixes não respiram ar.
7
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
 Regra da Negação do Quantificador Existencial (~  ) 
 Uma fórmula do tipo ~( x)b gera uma linha na qual escrevemos a fórmula (∀ x)~b. 
Teorema: A negação de uma proposição da forma x ∊ D,Q(x) é equivalente 
logicamente a proposição da forma ∀ x ∊ D | ~Q(x). 
Temos: ~( x ∊D, Q(x))  ∀ x ∊ D | ~Q(x). 
8
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
 Regra da Negação do Quantificador Existencial (~  ) 
 Uma fórmula do tipo ~( x)b gera uma linha na qual escrevemos a fórmula (∀ x)~b. 
Teorema: A negação de uma proposição da forma x ∊ D,Q(x) é equivalente logicamente a proposição da forma ∀ x ∊ D | ~Q(x). 
Simbolicamente temos: ~( x ∊D, Q(x))  ∀ x ∊ D | ~Q(x). 
Exemplo:
P:  um triangulo tal que a soma dos ângulos de T é igual a 100 graus.
9
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
 Regra da Negação do Quantificador Existencial (~  ) 
 Uma fórmula do tipo ~( x)b gera uma linha na qual escrevemos a fórmula (∀ x)~b. 
Teorema: A negação de uma proposição da forma x ∊ D,Q(x) é equivalente logicamente a proposição da forma ∀ x ∊ D | ~Q(x). 
Simbolicamente temos: ~( x ∊D, Q(x))  ∀ x ∊ D | ~Q(x). 
Exemplo:
P:  um triangulo tal que a soma dos ângulos de T é igual a 100 graus.
~P: ∀ triângulos T, a soma dos ângulos de T não é igual a 200 graus.
10
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
Temos: ~(∀ x,P(x)  Q(x))   x | ~(P(x)  Q(x));
Podemos decompor em uma sentença conjuntiva: ~(P(x)  Q(x))  P(x)^ ~Q(x).
substituindo temos: ~(∀ x,P(x)  Q(x))   x | (P(x) ^ ~Q(x));
 Exemplo:
P: ∀ pessoas p, se p é loura então p tem olhos azuis.
~P:  uma pessoa p tal que p é loura e p não tem olhos azuis.
11
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
Verdade por " default" 
Uma proposição da forma ∀x ∊D, se P(x) então Q(x) é chamada de verdade 
por “default" se P(x) é falso para cada x em D.
Exemplo: Sejam cinco bolas azuis, cinco brancas e um prato.
1- três bolas azuis e uma branca são colocadas no prato.
P: todas as bolas no prato são azuis.
P é falso já que é possível identificar uma bola branca no prato.
12
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
A Proposição é falsa se sua negação for verdadeira. 
A negação é: 
		~P: Existe pelo menos uma bola no prato que não é azul.
~P só é verdadeira se houver (existir) no prato uma bola que não seja azul. 
Como não existe, a negação é falsa e assim a proposição é verdadeira por default.
13
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
A Proposição é falsa se sua negação for verdadeira. 
A negação é: 
		~P: Existe pelo menos uma bola no prato que não é azul.
~P só é verdadeira se houver (existir) no prato uma bola que não seja azul. Como não
existe, a negação é falsa e assim a proposição é verdadeira por default.
 Exemplo: Qual a negação de P.
P: ∀ pessoas x ,  uma pessoa y tal que x ama y.
Para a sentença ser falsa temos que ter que a propriedade não será valida para todas as pessoas.
14
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
A Proposição é falsa se sua negação for verdadeira. 
A negação é: 
		~P: Existe pelo menos uma bola no prato que não é azul.
~P só é verdadeira se houver (existir) no prato uma bola que não seja azul. Como não
existe, a negação é falsa e assim a proposição é verdadeira por default.
 Exemplo: Qual a negação de P.
P: ∀ pessoas x ,  uma pessoa y tal que x ama y.
Para a sentença ser falsa temos que ter que a propriedade não será valida para todas as pessoas.
~P:  uma pessoa x tal que ~( uma pessoa y tal que x ama y)   uma pessoa x tal que ∀ pessoas y, x não ama y.
15
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
 
Regra geral:
P: ∀ x  y tal que C(x,y)
~P:  x tal que ∀ y, ~C(x,y)
Exemplo:
P: ∀ inteiro n,  um inteiro k tal que n = 2k
16
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
 
Regra geral:
P: ∀ x  y tal que C(x,y)
~P:  x tal que ∀ y, ~C(x,y)
Exemplo:
P: ∀ inteiro n,  um inteiro k tal que n = 2k
~P:  um inteiro n tal que ∀ inteiro k, n  2k.
17
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
Regra geral:
 
P: x ∀y tal que ∀y,C(x,y)
~P: ∀ x,  y tal que ~C(x,y)
Exemplo:
P:  uma pessoa x tal que ∀ pessoas y, x ama y
~P: ∀ pessoas x,  uma pessoa y tal que x não ama y.
18
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
 
Proposição universal é uma generalização da conjunção (^)
∀x ∊ D, Q(x)  Q(x1) ^Q(x2)^...^Q(xn)
Exemplo: Q(x) : x.x, D = {0,1} 
∀ x ∊D, Q(x)  Q(0) ^Q(1)
19
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
Proposição universal é uma generalização da conjunção ():
 x ∊ D tal que Q(x)  Q(x1)  Q(x2)  ...  Q(xn)
Exemplo: Q(x) : x+x, D = {0,1}
 x ∊ D tal que Q(x)  Q(0)  Q(1)
20
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculodos Predicados
Seja a proposição condicional universal (PCU): 
Exemplo: ∀ x ∊ R, se x > 2 então x2 > 4.
21
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
Seja a proposição condicional universal (PCU): 
Exemplo: ∀ x ∊ R, se x > 2 então x2 > 4.
Exemplo:
22
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
Seja a proposição condicional universal (PCU): 
Exemplo: ∀ x ∊ R, se x > 2 então x2 > 4.
Exemplo:
Exemplo : 
23
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
Exemplo: a fórmula ( ∀x)P(x) e o conjunto universo U={a,b,c}. É evidente que nesse
caso temos: (∀ x)P(x)  P(a) ^ P(b) ^ P(c).
Podemos considerar então que:
~(∀ x)P(x)  ~(P(a) ^ P(b) ^ P(c))  ~P(a)  ~P(b)  ~P(c)
o qual significa que existe no mínimo um objeto em U tal que ~P(x), ou seja, ~(∀ x)P(x)  ( x) ~P(x) ou ainda, de modo geral, para uma fórmula a qualquer temos:
~(∀ x) a  ( x) ~a
24
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
Da equivalência anterior segue imediatamente que:
 
(2). ~( ∀x)~P(x)  ( x)P(x)
(3). ~( x)P(x)  (∀ x)~P(x)
(4). ~( x)~P(x)  (∀ x)P(x)
25
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
Relações Lógicas
Os elementos básicos da sintaxe do cálculo de predicados são símbolos que se referem a:
 objetos
 relações 
 funções
Termos: são expressões lógicas que se referem a um objeto.
Uma sentença atômica será composta por um predicado, aplicado a um ou mais termos.
Fórmulas serão compostas por predicados ligados através de conectivos lógicos.
26
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
Quantificador Universal (∀x P(x) )
Lê-se para todo x, P(x) ou para qualquer x, P(x).
Quantificador Existencial (x P(x))
Lê-se para algum x, P(x) ou existe x, P(x).
Exemplos: Todo homem é mortal : ∀x (Homem(x)  Mortal(x))
27
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
Teorema:
Generalização da Lei de De Morgan para os quantificadores:
~ ∀x P(x)   x ~P(x)
~  x P(x)  ∀ x ~P(x)
Exemplo:
	“Não é todo homem que é egoísta”
 		equivale a 
“Existe pelo menos um homem que não é egoísta”
28
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
Argumento e Regras de Inferência Adicionais
Procedimento de inferência em lógica de predicados é semelhante ao visto em lógica
proposicional, porém mais complex.
1- presença dos quantificadores
2- presença de variáveis
Este procedimento leva em conta duas noções fundamentais:
a) Substituição
b) Unificação
29
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
Argumento e Regras de Inferência Adicionais.
Uma substituição é um conjunto finito de associações entre variáveis e expressões tais que:
1- cada variável é associada no máximo com uma única expressão.
2- nenhuma variável com uma expressão associada ocorre no escopo de qualquer outra expressão.
Cada variável é associada no máximo com uma única expressão:
a) nenhuma variável com uma expressão
b) associada ocorre no escopo de qualquer outra expressão
30
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
Unificação
Trata-se do processo que determina se duas expressões podem se tornar idênticas 
se suas variáveis forem substituídas de modo apropriado.
31
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
Regras de Inferência
A primeira regra de inferência: Instanciação Universal (IU)
Se todos os objetos de um dado universo possuem uma dada propriedade,
então um objeto particular desse universo também possui essa propriedade.
Podemos escrever: 
onde  é uma fórmula que resulta de  pela substituição de cada ocorrência da variável 
livre u por um termo t, é uma regra de inferência, ou seja, é uma implicação tautológica.
32
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
Regras de Inferência
Exemplo:
Todos os homens são mortais.
Sócrates é um homem.
Logo, Sócrates é mortal.
33
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
Regras de Inferência
Exemplo:
Todos os homens são mortais.
Sócrates é um homem.
Logo, Sócrates é mortal.
34
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
 
No passo 3, a Instanciação Universal consistiu em substituir, a premissa 1, x por Sócrates.
35
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
 
A segunda regra de inferência: Generalização Universal (GU)
Se um objeto, arbitrariamente escolhido dentre um universo, tiver uma certa propriedade, todos os objetos desse universo terão essa propriedade 
onde  é uma fórmula e w um objeto arbitrariamente escolhido, é uma regra de inferência.
Exemplo:
Todos os humanos são mortais.
Todos os gregos são humanos.
Logo, todos os gregos são mortais.
36
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
 
Nos passos 3 e 4 a instanciação universal substitui x pelo mesmo elemento k, como as premissas 
são verdadeiras para todo x, são verdadeiras para x = k.
No passo 5, diz que determinado k é grego, então k é mortal. k é qualquer objeto do universo. 
No passo 6 estamos afirmando se qualquer objeto do universo é grego, então esse objeto é mortal.
37
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
 
Terceira regra de inferência: Generalização Existencial (GE)
O que é verdadeiro para um dado objeto, é verdadeiro para algum objeto.
onde w é constante ou variável, u é variável, e w resulta de  u pela substituição das ocorrências
livres de u por w; se w for uma variável, deve ocorrer livre em  w nos locais em que u ocorrer livre 
em  u.
38
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
 
Exemplo:
Todos os tigres são animais ferozes.
Tita é um tigre.
Logo, existem animais ferozes.
39
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
 
Quarta regra de inferência: Instanciação Existencial(IE)
O que é verdadeiro para algum objeto, é verdadeiro para um dado objeto, 
desde que esse objeto não tenha sido utilizado anteriormente na dedução.
Exemplo:
Todos os tigres são ferozes.
Alguns animais são tigres.
Logo, alguns animais são ferozes.
40
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
 
Exemplo:
Todos os tigres são ferozes.
Alguns animais são tigres.
Logo, alguns animais são ferozes.
41
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
 
Cuidados: 
 ao aplicar a Instanciação Existencial,certifique-se que o termo a ser utilizado não tenha sido utilizado anteriormente na dedução;
 não aplicar Generalização Universal às variáveis introduzidas por Instanciação Existencial.
Isso decorre do fato de que não se pode generalizar um fato verdadeiro apenas para algum elemento; isto é, de x Fx não podemos inferir ∀x Fx.
Há muitos argumentos que não podem ser demonstrados, verificados ou testados com o
uso exclusivo das Regras de Inferência, assim, torna-se necessário recorrer a um princípio da inferência adicional, a Regra da Substituição de proposições equivalentes.
42
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
 
43
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
 
44
MATEMÁTICAAPLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 14: Cálculo dos Predicados
 
Exemplo: Demonstração de que é valido o argumento
45
MATEMÁTICA APLICADA A COMPUTAÇÃO
AULA 14: Cálculo dos Predicados
Sugestão de resolução dos exercícios propostos.
1- Demonstre que a proposição é valida: p  q, r  ~q p  ~r
Exercícios Propostos
46
MATEMÁTICA APLICADA A COMPUTAÇÃO
AULA 14: Cálculo dos Predicados
Sugestão de resolução dos exercícios propostos.
Exercícios Propostos
1- Demonstre que a proposição é valida: p  q, r  ~q p  ~r
47
MATEMÁTICA APLICADA A COMPUTAÇÃO
AULA 14: Cálculo dos Predicados
2- Escreva os argumentos de forma adequada:
1- Todos os gatos tem garras.
2- Tom é um gato.
3- Tom tem garras.
Sugestão de resolução dos exercícios propostos.
Exercícios Propostos
48
MATEMÁTICA APLICADA A COMPUTAÇÃO
AULA 14: Cálculo dos Predicados
Sugestão de resolução dos exercícios propostos.
Exercícios Propostos
2- Escreva os argumentos de forma adequada :
1- Todos os gatos tem garras.
2- Tom é um gato.
3- Tom tem garras.
Solução:
49
MATEMÁTICA APLICADA A COMPUTAÇÃO
AULA 14: Cálculo dos Predicados
Demonstre formalmente:
Sugestão de resolução dos exercícios propostos.
Exercícios Propostos
50
MATEMÁTICA APLICADA A COMPUTAÇÃO
AULA 14: Cálculo dos Predicados
Sugestão de resolução dos exercícios propostos.
Exercícios Propostos
Demonstre formalmente:
51
MATEMÁTICA APLICADA A COMPUTAÇÃO
AULA 14: Cálculo dos Predicados
Indicação de Leitura Específica
 Recomendamos a leitura do capítulo referente Teoria de Conjuntos no material didático.
 Acesse a Biblioteca Virtual da Estácio e pesquise mais exercícios nos livros de Teoria de Conjuntos disponíveis.
Sugestão de material:
http://www.otricolor.com/images/noticias/1278/Inicia%E7%E3o%20a%20L%F3gica%20Matem%E1tica.%20Edegard%20Filho.%20Editota%20Nobel%20(1).pdf
https://www.google.com.br/?gfe_rd=cr&ei=TdqhVaOOEeGB8QeEu4DIDA&gws_rd=ssl#q=Proposi%C3%A7%C3%B5es+Simples
http://www.feata.edu.br/downloads/revistas/avessodoavesso/v3_artigo04_logica.pdf
http://uol.iesde.com.br/aprovaconcursos/demo_aprova_concursos/raciocinio_logico_01.pdf
Indicação de Leitura
52
MATEMÁTICA APLICADA A COMPUTAÇÃO
AULA 14: Cálculo dos Predicados
Indicação de Leitura Específica
Sugestão de leitura:
https://docente.ifrn.edu.br/cleonelima/disciplinas/fundamentos-de-programacao-2.8401.1m/fundamentos-de-logica-e-algoritmos-1.8401.1v/apostila-equivalencias-logicas
Indicação de Leitura
53
VAMOS AOS PRÓXIMOS PASSOS?
 
Unidade 7 - Métodos de Demonstração
7.1. Vacuidade. Trivial. Direta. Indireta;
7.2. Contradição ou Redução ao Absurdo.
54