Frank Coelho de Alcantara -2020
Considere um universo formado por todas as pessoas do mundo em que existam os predicados:. progenitor, representado por P; sexo masculino representado por M; sexo Feminino representado por F. Além de todos os possíveis predicados que existem nas relações humanas, e o seguinte conjunto de predicados atômicos já definidos:
| $M(Paulo)$ | $M(Marcos)$ | $M(Breno)$ | $M(Augusto)$ |
| $M(Carlos)$ | $F(Márcia)$ | $F(Ana)$ | $F(Jéssica)$ |
| $F(Karen)$ | $F(Bianca)$ | $F(Sandra)$ | $P(Paulo, Marcos)$ |
| $P(Carlos, Bianca)$ | $P(Paulo, Sandra)$ | $P(Paulo, Sandra)$ | $P(Karen, Bianca)$ |
| $P(Márcia, Jéssica)$ | $P(Márcia, Paulo)$ | $P(Ana, Marcos)$ | $P(Karen, Ana)$ |
Descubra quem é o pai de Marcos, observe que Pai é um predicado novo, e escreva uma expressão em lógica de predicados para expressar esta verdade.
O pai de Marcos é Paulo: $P(x,Marcos) \wedge M(x)\rightarrow Pai(Paulo,Marcos)$ ou $$\exists xP(M(x)\rightarrow Pai(x,Marcos)$$
Em lógica de predicados usamos a mesma precedência da lógica proposicional: $$\{\neg, \wedge, \vee, \rightarrow, \leftrightarrow\}$$
Mas agora incluíndo os quantificadores com a maior precedência:$$\{\forall, \exists, \neg, \wedge, \vee, \rightarrow, \leftrightarrow\}$$
Não existe precedência entre os próprios quantificadores em $\forall x \exists y$ o $\exists $ é o escopo de $\forall$. E lembre-se que a ordem dos quantificadores não pode ser alterada.
Chamamos de modelo a tradução em linguagem natural de uma expressão em cálculo predicativo desde que:
Dada a expressão $\forall x \exists y(P(x, y) ∨ B(x))$ é possível escrever um número indeterminado de modelos:
Você pode construir qualquer outro modelo que sua imaginação permitir desde que todos os requisitos para a construção de modelos sejam cumpridos.
| Declaração | Quando Verdadeiro | Quando Falso |
|---|---|---|
| $\forall xP(x)$ | $P(x)$ é verdadeiro para todos os $x$. | Existe pelo menos um $x$ para o qual $P(x)$ é falso. |
| $\exists xP(x)$ | Existe um $x$ para o qual $P(x)$ é verdadeiro. | $P(x)$ é falso para todo $x$. |
Claramente, a verdade será descoberta em um domínio. Considere $P(x)$ representando o predicado menor que 2 neste caso considerando o conjunto dos números reais. Qual o valor verdade para $\forall xP(x)$?
$P(x)$ não é verdadeiro para qualquer $x$ pertencente aos reais já que para qualquer instância deste predicado para $x>2$ ele não será verdade. O valor $x=3$ é um contra exemplo que mostra a falsidade deste predicado.
Suponha que $Q(x)$ represente $x^2 > 0$. Prove que a expressão $\forall xQ(x)$ é falsa no universo dos números inteiros.
Para provar que uma expressão utilizando o quantificador universal $\forall$ é falsa basta encontrar um $x$, no universo dos inteiros para o qual $x^2 > 0$ é falso. Neste caso o contra exemplo é o zero já que $0^2 = 0$.
Observe também que quando os elementos de um determinado universo podem ser contados, $x_1, x_2, x_3, ... x_n$, o quantificador universal de um $P(x)$ qualquer $\forall xP(x)$ é equivalente à: $P(x_1) \wedge P(x_2) \wedge P(x_3)... \wedge P(x_n)$. Já que esta conjunção só será verdadeira se $P(x)$ for verdadeiro para todo e qualquer $x$ deste universo.
Considere o domínio dos números naturais não maiores que $4$ e determine o valor verdade de $\forall xR(x)$ onde $R(x)$ representa $x^2 \leq 10$.
Neste caso, como o domínio é pequeno, podemos utilizar a equivalência a conjunção.
$\forall xR(x)$ será verdade só, e somente só, $P(x_1)\wedge P(x_2)\wedge P(x_3)\wedge P(x_4)$ for verdadeiro.
No caso, $P(1)\wedge P(2)\wedge P(3)\wedge P(4)$ então termos $1^2 =1, 2^2 = 4, 3^2=9, 4^2 =16$, claramente a última interpretação é falsa.
Logo a expressão $\forall xR(x)$ é falsa no universo determinado se $R(x)$ representa $x^2 \leq 10$.
Considere o domínio dos números reais e que $P(x)$ representa $x \geq 3$ e determine a verdade de $\exists xP(x)$.
Como existem interpretações no domínio dos reais onde $x \geq 3$ é verdadeiro, como os valores $3,4,5,...$ esta expressão é verdadeira.
Lembre-se $\exists x$ é lido como existe um então basta um caso para que este quantificador indique a verdade. Lembre-se também que esta expressão só seria falsa se não existisse nenhum $x$ no domínio dos reais que atendesse o predicado $R(x)$ conforme definido neste exemplo.
Por fim, existe uma equivalência entre o $\exists xP(x)$ quando estes valores são enumeráveis e a disjunção. De tal forma que:
$\exists xP(x) \equiv P(x_1)\vee P(x_2)\vee P(x_3)\vee ... P(x_n)$
Considere o domínio dos números naturais não maiores que $4$ e determine o valor verdade de $\exists xR(x)$ onde $R(x)$ representa $x^2 \leq 10$
Como no domínio composto por $\{1,2,3,4\}$ a expressão $\exists xR(x)$ onde $R(x)$ representa $x^2 \leq 10$ será equivalente a disjunção:
$P(x_1)\vee P(x_2)\vee P(x_3)\vee ... P(x_n)$
$\exists xR(x)$ onde $R(x)$ representa $x^2 \leq 10$ é verdadeira já que ela será verdade para as interpretações $\{1,2,3\}$ e bastava que uma fosse verdadeira.
Os quantificadores existencial e universal são muito importantes na matemática e, com ele podemos representar todas as condições envolvendo quantidades em raciocínio lógico. Contudo, existe uma representação $\exists!$ especial. Este ponto de exclamação não faz parte da linguagem da lógica predicativa, como definimos anteriormente, mas tem aplicação na prova de teoremas representando expressões: Existe um único $x$ para o qual $P(x)$ é verdadeiro. E pode ser utilizado para representar expressões diversas como:
Expressões envolvendo quantificadores e predicados serão equivalentes em um mesmo domínio se, e somente se, estas expressões tiverem o mesmo valor verdade em todas as interpretações possíveis no domínio dado. Usaremos $\equiv$ para indicar a equivalência lógica.
Prove que $\forall x(P(x)\wedge Q(x))$ e $\forall xP(x) \wedge \forall xQ(x)$ são equivalentes em um mesmo domínio dado. Esta é a prova da propriedade distributiva do quantificador universal $\forall$. Precisamos provar duas situações:
Suponha que $\forall x(P(x)\wedge Q(x))$ é verdadeiro. Isto significa que dado um $a$ qualquer, $P(a) \wedge Q(a)$ é verdadeiro. Então, $P(a)$ e $Q(a)$ é verdadeiro. Como $P(a)$ e $Q(a)$ é verdadeiro para todos os valores no domínio, Podemos concluir que $\forall xP(x)$ e $\forall xQ(x)$ são ambos verdadeiros. Ou seja: $\forall x(P(x)\wedge Q(x))$ é verdadeiro.
Suponha que $\forall xP(x) \wedge \forall xQ(x)$ é verdadeiro. Neste caso $\forall xP(x)$ é verdadeiro e $\forall xQ(x)$ também é verdadeiro. Então, se $a$ está no mesmo domínio, temos $P(a)$ é verdadeiro e $Q(a)$ verdadeiro por que $P(x)$ e $Q(x)$ são ambos verdadeiros para todos os elementos do domínio. Consequentemente, para todo o $a$, $P(a) ∧ Q(a)$ é verdadeiro. Ou seja, $\forall x(P(x) ∧ Q(x))$ é verdadeiro.
Logo: $\forall x(P(x)\wedge Q(x)) \equiv \forall xP(x) \wedge \forall xQ(x)$
Todos os alunos da turma fizeram cálculo pode ser representado por $\forall xP(x)$.
A negação seria: nem todos os estudantes da turma fizeram cálculo. Como representar isso?.
A expressão Fez cálculo é o predicado logo: $\exists x \neg(P)$. Formalmente: $$\neg \forall xP(x) \equiv \exists x \neg(P)$$
Da mesma forma teremos: $$\neg \exists xP(x) \equiv \forall x \neg(P)$$
Escreva o raciocínio que permite garantir que a última expressão é verdadeira.
As regras da negação de quantificadores são chamadas de Leis de De Morgan para Quantificadores.
| Declaração | Negação | Quando a Negação é verdadeira | Quando a Negação é falsa |
|---|---|---|---|
| $\neg \exists xP(x)$ | $\forall x \neg P(x)$ | Para todo $x$ $P(x)$ é falso. | Existe um $x$ para o qual $x$ $P(x)$ é verdadeiro. |
| $\neg \forall xP(x)$ | $\exists x \neg P(x)$ | Existe um $x$ para o qual $P(x)$ é falso. | $P(x)$ é verdadeiro para todo $x$. |
Isto acontece porque quando temos um universo enumerável com $n$ elementos onde $n>1$ as regras para a negação de quantificadores obedecem exatamente as mesmas propriedades que observamos no cálculo proposicional. $\neg \forall xP(x) \equiv \neg (P(x_1) \wedge P(x_2) \equiv (\neg P(x_1) \vee \neg P(x_2))$
Escreva no seu caderno a equivalência da negação do quantificador existencial.
Represente formalmente a expressão: existe um político honesto, no domínio formado por todos os políticos e a sua negação. Sem esquecer de expressar a negação em português.
Considere o predicado $P(x)$ como: ser honesto. Neste caso a expressão pode ser representada por: $\exists xP(x)$.
A negação de $\exists xP(x)$ representada por $\neg \exists xP(x)$ é equivalente a $\forall x \neg P(x)$
Que em português é lida por: todos os políticos são desonestos
Considerando o universo dos números reais, qual a negação das expressões $\forall x(x^2 > x)$ e $\exists x(x^2 = 2)$.
Este é o exercício participativo de hoje. Observe que temos que representar de forma clara e podemos usar as regras da aritmética.
Prolog, linguagem criada nos anos 1970 para o estudo de inteligência artificial.
Define dois tipos de declaração:
Vamos ao código!!!
Começamos a aula de hoje com um exemplo, sua tarefa será rodar este exemplo em Prolog.