Cálculo de Predicados
Frank Coelho de Alcantara -2020
Revisão: alfabeto
Verdade: $True \Leftrightarrow \top$; $False \Leftrightarrow \bot \}$.
Conjunto de símbolos para variáveis: $\{x; y; z; ...\}$ ou $\{x_1; x_2; x_3; ...\}$.
Conjunto de símbolos para constantes: $\{a; b; c; ...\}$ ou $\{a_1; a_2; a_3; ...\}$.
Conjunto de símbolos para funções: $\{a; b; c; ...\}$ ou $\{a_1; a_2; a_3; ...\}$.
Conjunto de símbolos para proposições: $\{p; q; r; ...\}$ ou $\{p_1; p_2; p_3; ...\}$.
Conjunto de símbolos para predicados: $\{P; Q; R; ...\}$ ou $\{P_1; P_2; P_3; ...\}$.
Operadores, ou conectivos: $\{\neg ; \vee ; \wedge ; \rightarrow; \leftrightarrow \}$
Quantificadores: $\{\forall ; \exists\} $
Símbolos de pontuação: $\{,;);(\}$.
Revisão: funções, predicados, aridade
Funções: mapeamento de valores de um domínio em outro.
Predicados: qualidades, relações ou propriedades, dos elementos de um determinado domínio.
Aridade: funções e predicados possuem argumentos. A aridade representa o número de argumentos. Se a aridade
de uma função for zero, teremos constantes. Se a aridade de um predicado for zero, teremos uma proposição.
Revisão: quantificadores
Quantificador universal: $\forall$ que leremos: para todo. Usaremos para generalização: $\forall xP(x)$ que leremos
para todo e qualquer $x$, $x$ tem o predicado $P$. Que representa sentenças como:
- Todo homem é mortal.
- Todos os homens são mortais.
- Os homens são mortais.
- Homens são sempre mortais.
- Se é homem, então é mortal.
Quantificador existencial: $\exists$ que leremos: existe um. Usaremos para a especialização: $\exists xP(x)$ que
leremos existe um $x$, tal que $x$ tem o predicado $P$. Que representa sentenças como:
- Existe homem inteligente.
- Há homens inteligentes.
- Há pelo menos um homem inteligente.
- Algum homem é inteligente.
Só para lembrar
A linguagem natural permite a criação de sentenças com um valor verdade: a capital do Paraná é Curitiba.
Ou permite a criação de sentenças cujo valor é um objeto: qual a capital do paraná?.
Na lógica de predicados teremos:
Termos: sentenças que representam objetos.
Fórmulas: sentenças que representam um valor verdade.
O cálculo de predicados opera com termos e fórmulas para representar sentenças em busca de sua verdade.
Sentenças
Procuramos uma lógica que permita expressar:
- Todo flamenguista é um campeão. Sílvia é flamenguista. Logo, Sílvia é campeã.
- A adição de dois números ímpares quaisquer é um número par.
- Acesso a esse recinto é permitido somente para as pessoas autorizadas ou conhecidas de pessoas autorizadas
Procuramos uma lógica que permita expressar sentenças, mais adequadas a linguagem natural. As sentenças possuem sujeito – predicado – objeto
Termos
Variáveis, ou constantes, são termos.
Se $x_1, x_2, ... , x_n$ são termos e $f$ é um símbolo de uma função n-ária, teremos:
$f(x_1, x_2, ... , x_n)$ como sendo um termo.
- Variáveis: $x$ e $y$.
- Constantes: $a$ e $b$ (função zero-ária).
- Funções: $f(x, a)$, (função binária).
- Funções: $g(y, f(x, a), c)$, função ternária com um termo binário e dois constantes .
Variáveis, constantes e funções são termos.
Predicados e Termos:
Usando a aritmética como exemplo:
- Funções: $+, −, \times, \div$.
- Constantes: $1, 2, . . . , 9, 0$.
- Termos: $x, 9, y, 8$. $+(5, 8)$ e $+(−(8, 7), 3)$.
Funções predicativas diversas:
- $Idade(pessoa)$: $Idade(Márcia)=21$.
- $População(cidade)$: $População(Curitiba)>2000000$
- $Irmãs(pessoa, pessoa)$: $Irmãs(Márcia, Jane)$
- $Gato(animal)$: $Gato(Thor)$
Os termos têm funções parecidas com as funções de substantivos e pronomes nas linguagens naturais.
Átomos
As verdades, $True, T, \top $ e $False, F, \bot$ são átomos.
Se $\{t_1, t_2, ..., t_n\}$ são termos e $P$ é um predicado, com qualquer aridade então: $P(t_1, t_2, ..., t_n)$ é um átomo. Exemplos:
- Verdades: $T$ e $F$.
- Predicados: $P$ e $Gato$.
- Função Predicativa: $g(y, f(x, a), c)$.
- Função: $ =; \geq$.
- Função Predicativa: $\geq(-(4,2), 3) \Leftrightarrow \bot$ .
- Função Predicativa: $\neq(\times(4,2), 7) \Leftrightarrow \top$.
Fórmulas Bem Formadas
Assim como na lógica proposicional, temos um conjunto de regras para a criação de fórmulas:
- Todo átomo é uma Fórmula Bem Formada.
- Se $P$ é uma Fórmula Bem Formada, então $\neg P$ é uma Fórmula Bem Formada
- Se $P$ e $Q$ são Fórmulas Bem Formadas, então $P\vee Q; P\wedge Q; P\rightarrow Q$ e $P\leftrightarrow Q$ são Fórmulas Bem Formadas.
- Se $P$ é uma Fórmula Bem Formada e $x$ uma variável, então $\forall xP$ e $\exists xP$ são Fórmulas Bem Formadas.
- Não existe nenhuma outra Fórmula Bem Formada.
Toda concatenação de símbolos na lógica de predicados, que seja uma Fórmula Bem Formada, será uma expressão.
Subtermo e subfórmula
São lexemas usados para definir as partes da fórmula:
- Se $P = x$, então $x$ é subtermo de $P$.
- Se $P = f(t_1, t_2, ..., t_n)$, então $t_i$ e $f(t_1, t_2, ..., t_n)$ são subtermos de $P$.
- Se $t_1$ é subtermo de $t_2$ e $t_2$ é subtermo de $P$, então $t_1$ é subtermo de $P$.
- Se $Q$ é uma Fórmula Bem Formada e $P = \neg Q$, então $Q$ e $\neg Q$ são subfórmulas de $P$.
- Se $Q$ e $R$ são Fórmulas Bem Formadas e $P$ é uma das operação $(Q\vee R; Q\wedge R; Q\rightarrow R; Q\leftrightarrow R)$,
então $Q$, $R$, e $P$ são subfórmulas de $P$.
- Se $P$ é uma Fórmula Bem Formada, $x$ uma variável, então $\forall xP$ e $\exists xP$ são subfórmulas de $P$.
- Se $R$ é subfórmula de $Q$ e $Q$ é subfórmula de $P$, então $R$ é subfórmula de $P$;
Todo subtermo e subfórmula são subexpressões.
Exemplo 1
Considerando que o nosso domínio, ou contexto, ou universo, seja formado pelo conjunto dos números reais ${\rm I\!R}$
e que os símbolos $\times ; -, 0$ e $1$ tenham o mesmo significado da aritmética; Traduza para o português as seguintes Fórmulas Bem Formadas.
- $\forall x(x \times 0=0)$
- R. Para todo e qualquer número real $x$, teremos $x$ vezes $0$ igual a $0$.
- $\forall x(x \times x - x =0 \rightarrow (x = 0 \vee x = 1))$
- R. Para todo e qualquer número real $x$, se $x$ vezes $x$ menos $x$ igual a $0$ então $x$ igual a zero ou $x$ igual a 1.
- $\forall x \exists y(x \times y = 1)$
- R. Para todo e qualquer número real $x$, existe um número real $y$ tal que $x$ vezes $y$ igual a 1.
Exemplo 2
Considerando que o nosso domínio, ou contexto, ou universo, seja formado pelo conjunto dos números naturais ${\mathbb{N}}$
que $f(x)$ signifique $x + 1$, and $g(x)$ signifique $x = 0$. Traduza para o português as seguintes Fórmulas Bem Formadas.
- $\forall x\neg g(f(x))$
- R. Para todo e qualquer número natural $x$, não é verdade que $x$ mais $1$ é igual a $0$.
- R. Ou: para todo e qualquer número natural $x$, $x$ mais $1$ é diferente de $0$.
- $\exists xg(f(x))$
- R. Existe um número natural $x$, tal que $x$ mais $1$ é igual $0$.
- $\exists x\neg g(f(x))$
- R. Existe um número natural $x$, tal que $x$ mais $1$ é diferente de $0$.
Exemplo 3
Considerando que o contexto é composto de todos os seres humanos e que o predicado $L(x,y)$ representa $x$ ama $y$, ou que
$y$ é amado por $x$. Podemos usar os quantificadores universais para representar diversos conceitos:
- $\forall x\forall y L(x,y)$: todo mundo ama todo mundo.
- $\forall y\forall x L(x,y)$: ou todo mundo é amado por todo mundo.
- Estas sentenças significam a mesma coisa.
- $\exists x \exists y L(x,y)$: alguém ama alguém.
- $\exists y \exists x L(x,y)$: alguém é amado por alguém.
- Estas sentenças significam a mesma coisa.
- $\forall x\exists y L(x,y)$: todo mundo ama alguém.
- $\forall y\exists x L(x,y)$: todo mundo é amado por alguém.
- Estas sentenças NÃO significam a mesma coisa. "Todas as pessoas tem alguém que ama"; "Todas as pessoas tem alguém que as amam".
- $\exists x\forall y L(x,y)$: alguém ama todo mundo.
- $\exists y\forall x L(x,y)$. alguém é amado por todo mundo.
- Estas sentenças NÃO significam a mesma coisa.
Exemplo 4
Traduza para cálculo predicativo as seguintes sentenças:
- Considerando como universo os números naturais traduza: Para todos números naturais $n$, $n$ é menor ou igual a $n$ elevado ao quadrado.
- Se $f(x) = x^2$ e $P(x,y)$ representar o predicado $x\leq y$ teremos:
- $\forall xP(x,f(x))$. O que está perfeito no nosso formalismo.
- Mas, podemos aceitar as regras da álgebra e escrever: $\forall n(n\leq n^2)$. O que é aceitável.
- Considerando como universo os números reais traduza: Para todos números naturais $n$, $n$ é menor ou igual a $n$ elevado ao quadrado.
- Neste caso, primeiro precisamos indicar que $n$ é um número natural: $N(x)$ então teremos
- $\forall x(N(x)\rightarrow P(x,f(x)))$.
Exemplo 5
Considerando o domínio sendo formado por todos os seres humanos, traduza para o cálculo predicativo o seguinte silogismo:
- Sócrates é um homem. Todos os homens têm nariz grande. Sócrates tem nariz grande.
- Vamos representar o predicado ser um homem por $H(x)$.
- Vamos representar o predicado nariz grande por $N(x)$.
- Vamos representar Sócrates pela constante $s$.
- Teremos: $H(s)$; $\forall x(H(x)\rightarrow N(x))$; $N(s)$.
- Considerando como universo os números reais traduza: Para todos números naturais $n$, $n$ é menor ou igual a $n$ elevado ao quadrado.
- Neste caso, primeiro precisamos indicar que $n$ é um número natural: $N(x)$ então teremos
- $\forall x(N(x)\rightarrow P(x,f(x)))$.
Variáveis Livres
Usamos parênteses para definir a parte da fórmula que é afetada pelos quantificadores. O fragmento entre parênteses
é chamado de escopo do quantificador:
- $\forall x(P(x)\rightarrow \forall y(R(x) \vee Q(y)))\vee B(x)$
- O Escopo de $\forall x$ é dado por $(P(x)\rightarrow \forall y(R(x) \vee Q(y)))$
- O Escopo de $\forall y$ é dado por $(R(x) \vee Q(y))$
Toda a variável que ocorre no escopo de um quantificador é dita Ligada a este quantificador. Todas as variáveis em uma
Fórmula Bem Formada que não está ligada a um quantificador é dita Livre.
- $\forall x(P(x)\rightarrow \forall y(R(x) \vee Q(y)))\vee B(x)$
- Apenas $B(x)$ é livre.
Uma fórmula sem variáveis livres é chamada de Fórmula Fechada ou Sentença .
Exemplo 6
$P(x,y)$ tem duas variáveis livres $x$ e $y$.
$\exists yP(x,y)$ tem uma variável livre $x$.
$\forall x\exists yP(x,y)$ é fechada.
O fechamento universal de $P(x,y)$ é $\forall x\forall yP(x,y)$.
O fechamento existencial de $P(x,y)$ é $\exists x\exists yP(x,y)$.
Em $\forall xP(x)\wedge Q(x)$, $x$ é ligada em $P(x)$ e é livre em $Q(x)$.
Interpretação
No cálculo proposicional vimos que as fórmulas são interpretadas a partir de fórmulas atômicas em busca da verdade da fórmula composta.
No cálculo predicativo, uma analogia válida seria partir das fórmulas atômicas até encontrar o valor verdade da fórmula composta.
Neste caso, contudo, as fórmulas atômicas contém variáveis e constantes que devem ser avaliadas em um determinado domínio.
Uma vez que o domínio é considerado as fórmulas podem ser interpretadas.
O fechamento existencial de $P(x,y)$ é $\exists x\exists yP(x,y)$.
Nós só definiremos validade em fórmulas fechadas.