Introdução ao Cálculo de Predicados

Frank Coelho de Alcantara -2020   

Todo Homem é Mortal

A proposição Todo homem é mortal inclui um conceito que ainda não havia sido explorado nesta disciplina.

Ser homem e ser mortal são qualidades, ou predicados.

Podemos representar esta expressão na forma Todo $H$ é $M$.

Mais interessante, podemos escolher uma variável $x$ para representar um homem qualquer que caiba no conceito Todo homem.

Agora podemos escrever Qualquer que seja $x$, se $x$ é homem, então $x$ é Mortal.

$\forall x(H(x)\rightarrow M(x))$

Lógica de Primeira Ordem

Chamamos de Cálculo Predicativo, ou de Lógica de Primeira Ordem a lógica que inclui símbolos para indicar qualidades e quantidades.

Aos símbolos de quantidade chamaremos de quantificadores e usaremos, inicialmente $\forall$ e $\exists$.

$\forall$ que leremos como para todo ou qualquer que seja.

$\exists$ que leremos existe ou algum.

O Cálculo Predicativo, ou lógica de Primeira Ordem, fará uso de todas as equivalências e regras de inferência que vimos no Cálculo Proposicional.

Alfabeto

O Cálculo Predicativo é uma linguagem e, como tal, precisa de um alfabeto.

$\Sigma_{LPO} = \{\neg, \vee, \wedge, \rightarrow, \leftrightarrow, \{A, B, C, D...\},\{a, b, c, d,...\},\{x, y, z, w,...\}, (, )\}$

Usaremos letras maiúsculas para indicar predicados e letras minúsculas para indicar indivíduos, ou individualidade.

Se for necessário poderemos usar símbolos da matemática para complementar o predicado como: $=$ e $\neq$.

A individualidade pode ser determinada na forma de constantes (um indivíduo especifico) ou de variáveis (uma classe de indivíduos).

Definições

Um predicado é uma declaração que contém variáveis, as variáveis predicativas, e podem ser verdadeiros ou falsos dependendo do valor destas variáveis.

$P(x)$ representando $x^2$ é maior que $x$ é um predicado. Ele contém uma variável $x$ e pode ser falso ou, não.

Uma vez que um predicado seja instanciado, ou seja, suas variáveis assumem valores, ele se torna uma proposição.

O domínio de um predicado é definido por todos os valores que suas variáveis possam assumir.

Para $P(x)$ o domínio poderia ser representado por todos os números inteiros, ou reais, ou racionais,...

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

Exemplo 1

Considere o predicado maior que representado por $MQ$ de variáveis no domínio dos números inteiros.

Podemos definir a fórmula $MQ(x,y)$.

  1. Se $x=4$ e $y=3$ então $MQ(x,y) \Rightarrow T$
  2. Se $x=1$ e $y=2$ então $MQ(x,y) \Rightarrow F$

Uma vez que tenha sido instanciado o predicado se torna uma proposição.

Quantificador Universal

$\forall$ é o quantificador universal, lido como para todos ou qualquer que seja. Em um Domínio $D$, para a variável $x$, podemos definir um predicado $P$ verdadeiro por:

$\forall x \in D, P(x)$

Que é uma generalização para expressões do tipo:

$\forall x \in \rm I\!R, (x^2 \geq 0)$

Quantificador Existencial

$\exists$ é o quantificador existencial, lido como existe ou existe um ou ainda para algum. Em um Domínio $D$, para a variável $x$, podemos definir um predicado $P$ verdadeiro por:

$\exists x \in D, P(x)$

O predicado $P(x)$ será verdadeiro se existir pelo menos um $x$ que atenda o domínio $D$

O Predicado pássaros $(p)$ são brabos $(B)$ será verdadeiro se $\exists xB(x) $

Quantificadores Aninhados

Domínio: $C$ para coelhos e $Ta$ para tartarugas.

Predicado: $MR$ para mais rápido.

Considere: TODOS os coelhos são mais rápidos que TODAS as tartarugas.

$\forall x \in C \wedge \forall y \in Ta \therefore MR(x,y) \Rightarrow T$

Considere: Existe UM coelho mais rápidos que TODAS as tartarugas.

$\exists x \in C \wedge \forall y \in Ta \therefore MR(x,y) \Rightarrow T$

Fugindo um pouco da matemática e permanecendo na lógica.

$MR(\forall xC(x), \forall y Ta(y))$

$MR(\exists xC(x),\forall y Ta(y))$

Universo do Discurso

Definimos um discurso, ou contexto, ou domínio, como sendo o conjunto de valores com os quais será possível avaliar o valor verdade de uma fórmula. Considere:

  1. Constantes: $s$ para Sílvia, $d$ para Dani e $j$ para Jane.
  2. Predicados: $P$ para é professor e $A$ para é aluno.
  3. Relações: $J$ para lecionam juntos e $N$ para é mais novo.

Poderemos ter:

  1. $P(s)$ indicando que Sílvia é professora.
  2. $\neg A(d)$ indicando que Dani não é aluna.
  3. $J(s,d)$ indicando que Sílvia e Dani lecionam juntas.
  4. $N(d,j)$ indicando que Dani é mais nova que Jane.

Linguagem

Considere o mesmo contexto definido anteriormente:

  1. Constantes: $s$ para Sílvia, $d$ para Dani e $j$ para Jane.
  2. Predicados: $P$ para é professor e $A$ para é aluno.
  3. Relações: $J$ para lecionam juntos e $N$ para é mais novo.

Poderemos ter:

  1. $J(s,d)$ e $J(d,s)$ representam o mesmo conceito.
  2. $N(d,j)$ e $N(j,d)$ representam conceitos diferentes.

A explicitação da forma define o conceito representado.

Variáveis

Podemos nos manter no contexto anteriormente definido e extrapolar usando variáveis:

  1. Constantes: $s$ para Sílvia, $d$ para Dani e $j$ para Jane.
  2. Predicados: $P$ para é professor e $A$ para é aluno.
  3. Relações: $J$ para lecionam juntos e $N$ para é mais novo.

Poderemos ter:

  1. $P(x)$ indicando que um membro genérico deste universo $x$ é professor.
  2. $J(x,y)$ indicando que $x$ é mais novo que $y$.
  3. $\neg A(y)$ indicando que um membro genérico deste universo $y$ não é aluno.

As sentenças definidas por variáveis são chamadas de sentenças abertas.

Exemplo 2

Considere as seguintes sentenças e tente representar segundo a lógica de primeira ordem.

  1. Existem números naturais que são pares.
  2. $x$ representa números naturais e $P$ o predicado ser par.
  3. $\exists xP(x)$

  

  1. Hipátia é mulher.
  2. $h$ representa Hipátia e $M$ o predicado ser mulher.
  3. $M(h)$

Sim! Existem expressões sem quantificador.

Aridade de predicados

$M(h)$ representando Hipátia é mulher o predicado ser mulher tem aridade um.

$J(x,y)$ indicando que $x$ é mais novo que $y$ o predicado ser mais novo tem aridade dois.

Paulo ($p$) Ama ($A$) Graça $g$ é representado por $A(p,g)$, e o predicado Amar tem aridade dois.

Não há limites para a aridade de um determinado predicado.

Paulo ama alguém poderia ser representado por $\exists xA(p,x)$.

Exemplo 3

Qual o significado das seguintes fórmulas? Considerando que $C$ representa o predicado Comprou.

  1. $\exists x C(Silvia,x)$.
  2. $\exists x C(Silvia,x)\Rightarrow $ Silvia comprou alguma coisa.
  3. $\forall x C(Silvia,x)\rightarrow \forall x C(Sandra, x)$.
  4. $\forall x C(Silvia,x)\rightarrow \forall x C(Sandra, x) \Rightarrow $ Tudo que Silvia comprou Sandra comprou.
  5. $\exists x \forall y C(x,y)$.
  6. $\exists x \forall y C(x,y) \Rightarrow $ Alguém comprou alguma coisa.

Exemplo 4

Considere o domínio composto apenas de pessoas.

  1. Maria ama todo mundo.
  2. $\forall x Ama(Maria,x)$
  3. Ou $\forall x (Ama(Maria,x))$ parênteses extras devem ser evitados.

Considere o domínio composto de qualquer coisa onde Maria só ame pessoas.

  1. Maria ama todo mundo.
  2. Teremos que explicitar todo mundo como todas as pessoas.
  3. $\forall x(Pessoa(x)\rightarrow Ama(Maria,x)$

Cuidado $\forall x(Pessoa(x)\wedge Ama(Maria,x)$ significa que tudo no universo é uma pessoa e Maria as ama.

Exercício 1

Qual o significado das seguintes fórmulas? Considerando que $C$ representa o predicado Comprou.

  1. $C(Silvia,dvd)$
  2. $\forall x (C(Silvia,x)\rightarrow C(Sandra, x))$
  3. $\forall x \exists y C(x,y)$

Exemplo 5

Defina a fórmula para cada uma das seguintes sentenças, considerando os predicados E para estudante, I para inteligente, C para cursar e A para amar:

  1. Todos os estudantes são inteligentes.
  2. Todos os estudantes são inteligentes. $\forall x(E(x)\rightarrow I(x))$
  3. Existe um estudante inteligente.
  4. Existe um estudante inteligente. $\exists x(E(x)\wedge I(x))$
  5. Sandra cursa Lógica ou Interpretadores.
  6. Sandra cursa Lógica ou Interpretadores. $C(Sandra, Lógica)\vee C(Sandra, Interpretadores)$
  7. Jane cursa Lógica e Interpretadores.
  8. Jane cursa Lógica e Interpretadores. $C(Jane, Lógica)\wedge C(Jane, Interpretadores)$
  9. Nenhum estudante ama Silvia.
  10. Nenhum estudante ama Silvia. $\neg \exists x (E(x) \wedge A(x,Silvia)$

Exercício 2

Defina a fórmula para cada uma das seguintes sentenças, considerando os predicados E para estudante, I para inteligente, C para cursar e A para amar:

  1. Existe um estudante.
  2. Ana é uma estudante.
  3. Paula cursa Lógica se não cursar Interpretadores.
  4. Jéssica não cursa Lógica.

Exemplo 6

Defina a fórmula para cada uma das seguintes sentenças, considerando os predicados E para estudante, I para inteligente, C para cursar e A para amar:

  1. Todo estudante ama algum estudante.
  2. Todo estudante ama algum estudante. $\forall x(E(x)\rightarrow \exists y(E(y)\wedge A(x,y)))$
  3. Todo estudante ama outro estudante.
  4. Todo estudante ama outro estudante. $\forall x(E(x)\rightarrow \exists y(E(y)\wedge \neg (x=y) \wedge A(x,y)))$
  5. Existe um estudante que é amado por todos os outros estudantes.
  6. Existe um estudante que é amado por todos os outros estudantes. $\exists x(E(x)\wedge \forall y((E(y)\wedge \neg (x=y)) \rightarrow A(x,y))) $

Exercício 3

Defina a fórmula para cada uma das seguintes sentenças, considerando que o domínio é composto de pessoas:

  1. Ninguém fala.
  2. Todo mundo se ama.
  3. Todo mundo ama todo mundo.
  4. Todo mundo ama todo mundo, exceto a si mesmo.
  5. Todo estudante sorri.
  6. Todo estudante exceto Paula, sorri.
  7. Todo mundo fala ou anda.
  8. Todo estudante fala ou anda.
  9. Todo estudante que anda fala.
  10. Todo estudante que ama Maria é feliz.

Respostas dos Exercícios

Exercício 1

Qual o significado das seguintes fórmulas? Considerando que $C$ representa o predicado Comprou.

  1. $C(Silvia,dvd) \Rightarrow $ Silvia comprou um dvd.
  2. $\forall x (C(Silvia,x)\rightarrow C(Sandra, x)) \Rightarrow $ Silvia comprou o mesmo que Sandra.
  3. $\forall x \exists y C(x,y) \Rightarrow $ Todos compraram alguma coisa.

Exercício 2

Defina a fórmula para cada uma das seguintes sentenças, considerando os predicados E para estudante, I para inteligente, C para cursar e A para amar:

  1. Existe um estudante. $\exists xE(x)$
  2. Ana é uma estudante. $E(Ana)$
  3. Paula cursa Lógica se não cursar Interpretadores. $C(Paula, Lógica)\leftrightarrow \neg C(Paula, Interpretadores)$
  4. Jéssica não cursa Lógica. $\neg C(Jéssica, Lógica)$

Exercício 3

Defina a fórmula para cada uma das seguintes sentenças, considerando que o domínio é composto de pessoas:

  1. Ninguém fala. $\neg \forall xFala(x)$ ou $\neg \exists xFala(x)$
  2. Todo mundo se ama. $\forall xAma(x,x)$
  3. Todo mundo ama todo mundo. $\forall x \forall y Ama(x,y)$
  4. Todo mundo ama todo mundo, exceto a si mesmo. $\forall x \forall y (\neg(x=y)\rightarrow Ama(x,y))$ ou $\forall x \forall y ((x\neq y)\rightarrow Ama(x,y))$
  5. Todo estudante sorri. $\forall x (Estudante(x)\rightarrow Sorri(x))$
  6. Todo estudante exceto Paula, sorri. $\forall x(Estudante(x)\rightarrow ((x \neq Paula) \leftrightarrow Sorri(x))$
  7. Todo mundo fala ou anda. $\forall x(Fala(x)\vee Anda(x))$
  8. Todo estudante fala ou anda. $\forall x(Estudante(x)\rightarrow (Fala(x)\vee Anda(x)))$
  9. Todo estudante que anda fala. $\forall x((Estudante(x) \wedge Anda(x))\rightarrow Fala(x))$ ou $\forall x(Estudante(x) \rightarrow (Anda(x)\rightarrow Fala(x)))$
  10. Todo estudante que ama Maria é feliz. $\forall x((Estudante(x) \wedge Ama(x,Maria))\rightarrow Feliz(x))$