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:

  1. Todo flamenguista é um campeão. Sílvia é flamenguista. Logo, Sílvia é campeã.
  2. A adição de dois números ímpares quaisquer é um número par.
  3. 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.

  1. Variáveis: $x$ e $y$.
  2. Constantes: $a$ e $b$ (função zero-ária).
  3. Funções: $f(x, a)$, (função binária).
  4. 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:

  1. Funções: $+, −, \times, \div$.
  2. Constantes: $1, 2, . . . , 9, 0$.
  3. Termos: $x, 9, y, 8$. $+(5, 8)$ e $+(−(8, 7), 3)$.

Funções predicativas diversas:

  1. $Idade(pessoa)$: $Idade(Márcia)=21$.
  2. $População(cidade)$: $População(Curitiba)>2000000$
  3. $Irmãs(pessoa, pessoa)$: $Irmãs(Márcia, Jane)$
  4. $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:

  1. Verdades: $T$ e $F$.
  2. Predicados: $P$ e $Gato$.
  3. Função Predicativa: $g(y, f(x, a), c)$.
  4. Função: $ =; \geq$.
  5. Função Predicativa: $\geq(-(4,2), 3) \Leftrightarrow \bot$ .
  6. 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:

  1. Todo átomo é uma Fórmula Bem Formada.
  2. Se $P$ é uma Fórmula Bem Formada, então $\neg P$ é uma Fórmula Bem Formada
  3. 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.
  4. 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.
  5. 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:

  1. Se $P = x$, então $x$ é subtermo de $P$.
  2. 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$.
  3. Se $t_1$ é subtermo de $t_2$ e $t_2$ é subtermo de $P$, então $t_1$ é subtermo de $P$.
  4. Se $Q$ é uma Fórmula Bem Formada e $P = \neg Q$, então $Q$ e $\neg Q$ são subfórmulas de $P$.
  5. 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$.
  6. Se $P$ é uma Fórmula Bem Formada, $x$ uma variável, então $\forall xP$ e $\exists xP$ são subfórmulas de $P$.
  7. 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.