apresentacao da aula 13

Prévia do material em texto

CCT0350 – MATEMÁTICA APLICADA A COMPUTAÇÃO
Aula 13: Cálculo dos Predicados
1
MATEMÁTICA APLICADA A COMPUTAÇÃO
AULA 13: Cálculo dos Predicados
 A lógica proposicional não pode expressar adequadamente o significado das proposições em matemática e em linguagem natural.
Exemplo: "Todo computador conectado à rede da universidade está funcionando apropriadamente.“
Novos símbolos na linguagem do Cálculo Proposicional: 
linguagem do Cálculo de Predicados de 1a Ordem.
Teremos conectivos do cálculo proposicional e os parênteses, mais alguns novos símbolos .
Cálculo dos Predicados
2
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 13: Cálculo dos Predicados
 Predicados. Conjunto Universo. Conjunto Verdade;
Novos símbolos:
 variáveis: x,y,z,…
 constantes : a,b,c,...
 símbolos de predicados: P , Q , R , S ,....
 quantificadores : ∀(universal) , (existencial) 
3
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 13: Cálculo dos Predicados
 Predicados. Conjunto Universo. Conjunto Verdade;
Novos símbolos:
 termos: as variáveis e as constantes são designadas pelo nome genérico de termos os
quais serão designados por t1 , t2 , ...,tn ...
 variáveis representam objetos que não estão identificados no Universo considerado
("alguém", "algo" etc.);
 constantes representam objetos identificados do Universo ("João", "o ponto A" etc. );
 símbolos de predicados representam propriedades ou relações entre os objetos do
Universo.
4
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 13: Cálculo dos Predicados
 Exemplos: Observe a expressão: "x é maior que 3".
Essa declaração não é nem verdadeira e nem falsa quando o valor das variáveis não são especificadas.
5
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 13: Cálculo dos Predicados
 Exemplos: Observe a expressão: "x é maior que 3".
Essa declaração não é nem verdadeira e nem falsa quando o valor das variáveis não são especificadas.
Podemos destacar que a declaração possui duas partes:
1a parte: a variável x é o sujeito da declaração
2a parte: o predicado, " é maior que 3" – refere-se a uma propriedade que o sujeito pode ter.
6
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 13: Cálculo dos Predicados
 Exemplos: Observe a expressão: "x é maior que 3".
Essa declaração não é nem verdadeira e nem falsa quando o valor das variáveis não são especificadas.
Podemos destacar que a declaração possui duas partes:
1a parte: a variável x é o sujeito da declaração
2a parte: o predicado, " é maior que 3" – refere-se a uma propriedade que o sujeito pode ter.
Tomaremos P(x) como " x é maior de 3". P indicará o predicado e x a variável.
A declaração, ou afirmação, é também chamada de o valor da função proposicional P em x. Uma vez que um valor é dado para a variável x, a declaração P(x) torna-se uma proposição e tem um valor-verdade.
7
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 13: Cálculo dos Predicados
 Exemplos: "Maria é inteligente" 
 I(m) - "m" está identificando Maria e "I" a propriedade de "ser inteligente".
"Alguém gosta de Maria" : G(x,m) ;
G representa a relação "gostar de" e "x“ representa "alguém".
8
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 13: Cálculo dos Predicados
 Generalisando:
 P(x) : significa que x tem a propriedade P.
 ∀ ( x)P(x): significa que a propriedade P vale para todo x, ou ainda, que todos os objetos do Universo considerado tem a propriedade P.
 ( x)P(x): significa que algum x tem a propriedade P, ou ainda, que existe no mínimo um objeto do Universo considerado que tem a propriedade P.
9
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 13: Cálculo dos Predicados
Símbolos de predicados serão:
 unários 
 binários 
 n-ários 
A propriedade que os predicados representam podem ser, respectivamente um, dois ou mais objetos do universo e dizemos também que o símbolo de predicado tem peso 1, peso 2 ... ou peso n.
OBS.: Um símbolo de predicados 0-ário (peso zero) identifica-se com um dos símbolos de predicado; 
Exemplo: "chove" podemos simbolizar "C“.
10
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 13: Cálculo dos Predicados
As fórmulas mais simples do Cálculo de Predicados de 1a Ordem são chamadas 
de fórmulas atômicas.
Definição: Se P for um símbolo de predicado de peso n e se t1 , t2 , ...,tn forem termos então P(t1 , t2 , ...,tn ) é uma fórmula atômica.
11
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 13: Cálculo dos Predicados
Quantificadores
Definição: A quantificação universal de P(x) é a afirmação 
		"P(x) é valida para todos os valores de x do domínio.”
Definição: A quantificação existencial de P(x) é a proposição 
		"Existe um elemento x no domínio tal que P(x).”
12
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 13: Cálculo dos Predicados
ESCOPO DE UM QUANTIFICADOR: 
Se a é uma fórmula e x uma variável, então em (∀x) a ou em ( x) a são fórmulas e dizemos que a é o escopo do quantificador (∀ x) ou ( x).
Exemplo: na fórmula ( y) : (∀ x)(R(y,b,t) (∀ z) P(z,a)) temos os seguintes quantificadores e seus respectivos escopos:
( y) : (∀ x)(R(y,b,t)  (∀ z) P(z,a))
(∀ x) : (R(y,b,t) (∀ z) P(z,a))
(∀ z) : P(z,a)
13
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 13: Cálculo dos Predicados
Exemplo: Seja P(x) a declaração "x+1 > x". Qual é o valor-verdade da quantificação ∀x
P(x), no domínio de todos os números reais?
14
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 13: Cálculo dos Predicados
Exemplo: Seja P(x) a declaração "x+1 > x". Qual é o valor-verdade da quantificação ∀x
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 ∀ x P(x), é verdadeira.
15
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 13: Cálculo dos Predicados
Observação: 
 Em geral, é assumido implicitamente que todos os domínios dos quantificadores são não vazios. 
 Se o domínio é vazio então ∀ x P(x), é verdadeira para toda proposição P(x), uma vez que não há elemento no domínio para o qual P(x) é falsa.
Observação:
 xP(x) é falsa se e somente se não existe elemento x no domínio para o qual P(x) é verdadeira, ou seja,  x P(x) é falsa se, e somente se, P(x) é falsa para todo elemento do domínio.
16
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 13: Cálculo dos Predicados
Variáveis Livres e Ligadas. Alcance do Quantificador;
Definição:
OCORRÊNCIAS LIVRE E LIGADA DE UMA VARIÁVEL: 
Uma ocorrência de uma variável x em uma fórmula é ligada se x é uma variável de um quantificador na fórmula ou x está no escopo de um quantificador (∀x) ou (x) na fórmula. Caso contrário a ocorrência de x é livre.
17
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 13: Cálculo dos Predicados
Variáveis Livres e Ligadas. Alcance do Quantificador;
Definção:
b) VARIÁVEL LIGADA (LIVRE):
Se a ocorrência de x é ligada (livre) em uma fórmula, dizemos que x é variável ligada (livre) na fórmula. Assim uma variável pode ser livre ou ligada numa mesma fórmula.
Exemplo:Na fórmula ( y)((∀ x) R(y,b,t) (∀ z) P(x,a)) temos cinco variáveis que estão numeradas onde:
		( y)((∀ x) R(y,b,t) (∀ z) são ligadas e P(x,a) é livre. 
Vemos que x ocorre livre e ligada na mesma fórmula.
18
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 13: Cálculo dos Predicados
Variáveis Livres e Ligadas. Alcance do Quantificador;
Definição:
SENTENÇA: Uma fórmula em que não há ocorrências livres de variáveis chamamos de sentença.
TERMO LIVRE PARA UMA VARIÁVEL: Um termo t é livre para a variável y na fórmula a se, quando se substitui as ocorrências livres de y por t, as ocorrências de t em a assim obtidas ocorrem livres.
Exemplos: x é livre para y em P(y).Exemplos: x não é livre para y em ( ∀x)P(y).
Observação: 
1. x é livre para x em qualquer fórmula.
2. qualquer termo é livre para x numa fórmula a se em a não há ocorrência livre de x.
19
MATEMÁTICA APLICADA A COMPUTAÇÃO
Cálculo dos Predicados
AULA 13: Cálculo dos Predicados
Alcance de um quantificador 
O alcance de um quantificador que ocorre numa fórmula é o próprio quantificador junto com a mais pequena fórmula que o segue.
 Uma ocorrência de uma variável, v , em uma fórmula diz-se muda se estiver no alcance de um quantificador ∀ v ou  v . Caso contrário diz-se livre.
 Uma variável diz-se muda em uma fórmula se tiver pelo menos uma ocorrência muda nessa fórmula. 
 Uma variável diz-se livre em uma fórmula se tiver pelo menos uma ocorrência livre nessa fórmula.
 Uma fórmula sem variáveis livres é uma proposição (ou sentença). Caso contrário é uma expressão proposicioal (ou condição)
20
MATEMÁTICA APLICADA A COMPUTAÇÃO
AULA 13: Cálculo dos Predicados
Sugestão de resolução dos exercícios propostos.
1- Seja Q(x) a declaração "x < 2". Qual o valor-verdade da quantificação ∀ x Q(x), em
que o domínio consiste em todos os números reais ?
Exercícios Propostos
21
MATEMÁTICA APLICADA A COMPUTAÇÃO
AULA 13: Cálculo dos Predicados
Sugestão de resolução dos exercícios propostos.
1- Seja Q(x) a declaração "x < 2". Qual o valor-verdade da quantificação ∀ x Q(x), em
que o domínio consiste em todos os números reais ?
Solução: 
Q(x) não é verdadeira para todo número real x, porque por exemplo Q(3) é falsa, isto é x = 3 é um contra-exemplo para declaração ∀ x Q(x).
 Logo ∀ x Q(x) é falsa.
Exercícios Propostos
22
MATEMÁTICA APLICADA A COMPUTAÇÃO
AULA 13: Cálculo dos Predicados
Sugestão de resolução dos exercícios propostos.
2) Seja P(x) a expressão "x > 3". Qual o valor-verdade da quantificação  xP(x) no
domínio dos números reais ?
Exercícios Propostos
23
MATEMÁTICA APLICADA A COMPUTAÇÃO
AULA 13: Cálculo dos Predicados
Sugestão de resolução dos exercícios propostos.
2) Seja P(x) a expressão "x > 3". Qual o valor-verdade da quantificação  xP(x) no 
domínio dos números reais ?
Solução:
 Como "x > 3" é verdadeira para algum número reais, exemplo x = 4, a quantificação existencial de P(x), que é  xP(x), é verdadeira.
Exercícios Propostos
24
MATEMÁTICA APLICADA A COMPUTAÇÃO
AULA 13: Cálculo dos Predicados
Exercícios Propostos
Sugestão de resolução dos exercícios propostos.
3) Seja Q(x) a expressão "x = x + 1". Qual o valor-verdade da quantificação  xQ(x) 
no domínio dos números reais ?
25
MATEMÁTICA APLICADA A COMPUTAÇÃO
AULA 13: Cálculo dos Predicados
Exercícios Propostos
Sugestão de resolução dos exercícios propostos.
3) Seja Q(x) a expressão "x = x + 1". Qual o valor-verdade da quantificação  xQ(x) no domínio dos números reais ?
Solução: 
Como Q(x) é falsa para todos os número reais, a quantificação existencial de Q(x), que é  xQ(x), é falsa.
26
MATEMÁTICA APLICADA A COMPUTAÇÃO
AULA 13: 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
27
MATEMÁTICA APLICADA A COMPUTAÇÃO
AULA 13: 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
28
VAMOS AOS PRÓXIMOS PASSOS?
 
Unidade 7 - Cálculo dos Predicados
7.4. Negação de Fórmulas Quantificadas;
7.5. Relações Lógicas;
7.6. Argumento e Regras de Inferência Adicionais.
29