Aula 13

Prévia do material em texto

CCT0350 – MATEMÁTICA APLICADA A COMPUTAÇÃO 
Aula 13: Cálculo dos Predicados 
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 
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) 
 
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. 
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. 
 
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. 
 
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. 
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". 
 
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. 
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“. 
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. 
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).” 
 
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) 
 
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? 
 
 
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. 
 
 
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. 
 
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: 
 
a) 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. 
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. 
MATEMÁTICA APLICADA A COMPUTAÇÃO 
Cálculodos 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. 
 
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) 
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 
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 
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 
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 
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 ? 
 
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. 
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=Propo
si%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 
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 
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.