Lógica de Predicados - SOL -...

Lógica de Predicados

Conteúdo

� Correção dos Exercícios (Rosen – 47)� Prioridade dos Quantificadores (Rosen 38)� Ligando Variáveis (Rosen 38) � Predicados com duas variáveis. � Equivalências lógicas (Rosen 39)� Negando expressões com quantificadores

(Rosen 39)

Exercícios – Rosen 47

8)Transcreva estas proposições para o português, em que R(x) é “x é um coelho” e H(x) é “x salta” e o domínio são todos os animais.

a) �x(R(x) � H(x))

Exercícios – Rosen 47

8)Transcreva estas proposições para o português, em que R(x) é “x é um coelho” e H(x) é “x salta” e o domínio são todos os animais.

a) �x(R(x) � H(x)) Todo coelho salta.

Exercícios – Rosen 47

8)Transcreva estas proposições para o português, em que R(x) é “x é um coelho” e H(x) é “x salta” e o domínio são todos os animais.

a) �x(R(x) � H(x)) Todo coelho salta.b) �x(R(x) ^ H(x))

Exercícios – Rosen 47

8)Transcreva estas proposições para o português, em que R(x) é “x é um coelho” e H(x) é “x salta” e o domínio são todos os animais.

a) �x(R(x) � H(x)) Todo coelho salta.b) �x(R(x) ^ H(x)) Todos os animais são

coelhos e saltam

Exercícios – Rosen 47

8)Transcreva estas proposições para o português, em que R(x) é “x é um coelho” e H(x) é “x salta” e o domínio são todos os animais.

a) �x(R(x) � H(x)) Todo coelho salta.b) �x(R(x) ^ H(x)) Todos os animais são

coelhos e saltamc) �x(R(x) � H(x))

Exercícios – Rosen 47

8)Transcreva estas proposições para o português, em que R(x) é “x é um coelho” e H(x) é “x salta” e o domínio são todos os animais.

a) �x(R(x) � H(x)) Todo coelho salta.b) �x(R(x) ^ H(x)) Todos os animais são

coelhos e saltamc) �x(R(x) � H(x)) Existe um animal que se é

coelho então ele salta.

Exercícios – Rosen 47

8)Transcreva estas proposições para o português, em que R(x) é “x é um coelho” e H(x) é “x salta” e o domínio são todos os animais.

a) �x(R(x) � H(x)) Todo coelho salta.b) �x(R(x) ^ H(x)) Todos os animais são

coelhos e saltamc) �x(R(x) � H(x)) Existe um animal que se é

coelho então ele salta.d) �x(R(x) ^ H(x))

Exercícios – Rosen 47

8)Transcreva estas proposições para o português, em que R(x) é “x é um coelho” e H(x) é “x salta” e o domínio são todos os animais.

a) �x(R(x) � H(x)) Todo coelho salta.b) �x(R(x) ^ H(x)) Todos os animais são

coelhos e saltamc) �x(R(x) � H(x)) Existe um animal que se é

coelho então ele salta.d) �x(R(x) ^ H(x)) Existe um coelho que salta

Exercícios – Rosen 47

9) Considere P(x) como a proposição “x fala russo” e considere Q(x) como a proposição “x sabe a linguagem computacional C++”. Expresse cada uma dessas sentenças em termos de P(x), Q(x), quantificadores e conectivos lógicos. O domínio para quantificadores são todos os estudantes de sua escola.

Exercícios – Rosen 47

9) Considere P(x) = “x fala russo” Q(x)=“x sabe a linguagem C++”. Domínio ={todos os estudantes de sua escola}

a) Há um estudante em sua escola que fala russo e sabe C++.

Exercícios – Rosen 47

9)P(x) = “x fala russo” Q(x)=“x sabe a linguagem C++”. Domínio ={todos os estudantes de sua escola}

a) Há um estudante em sua escola que fala russo e sabe C++.

�x (P(x) ^ Q(x))

Exercícios – Rosen 47

9)P(x) = “x fala russo” Q(x)=“x sabe a linguagem C++”. Domínio ={todos os estudantes de sua escola}

b) Há um estudante em sua escola que fala russo mas não sabe C++.

Exercícios – Rosen 47

9)P(x) = “x fala russo” Q(x)=“x sabe a linguagem C++”. Domínio ={todos os estudantes de sua escola}

b) Há um estudante em sua escola que fala russo mas não sabe C++.

�x (P(x) ^ ~Q(x))

Exercícios – Rosen 47

9)P(x) = “x fala russo” Q(x)=“x sabe a linguagem C++”. Domínio ={todos os estudantes de sua escola}

c) Todo estudante em sua escola ou fala russo ou sabe C++.

Exercícios – Rosen 47

9)P(x) = “x fala russo” Q(x)=“x sabe a linguagem C++”. Domínio ={todos os estudantes de sua escola}

c) Todo estudante em sua escola ou fala russo ou sabe C++.

�x (P(x) v Q(x))

Exercícios – Rosen 47

9)P(x) = “x fala russo” Q(x)=“x sabe a linguagem C++”. Domínio ={todos os estudantes de sua escola}

d) Nenhum estudante em sua escola fala russo ou sabe C++.

Exercícios – Rosen 47

9)P(x) = “x fala russo” Q(x)=“x sabe a linguagem C++”. Domínio ={todos os estudantes de sua escola}

d) Nenhum estudante em sua escola fala russo ou sabe C++.

�x ~(P(x) v Q(x))

Prioridade dos Quantificadores

� Os quantificadores ��e � têm prioridade maior que todos os operadores lógicos do cálculo proposicional.

�x P(x) v Q(x) �� (�x P(x)) v Q(x) �x P(x) v Q(x) � ��x (P(x) v Q(x))

Prioridade dos Quantificadores

� Os quantificadores ��e � têm prioridade maior que todos os operadores lógicos do cálculo proposicional.

�x P(x) v Q(x) �� (�x P(x)) v Q(x) �x P(x) v Q(x) � ��x (P(x) v Q(x))

Isso nos mostra o conceito de variável ligada

Prioridade dos Quantificadores

� Os quantificadores ��e � têm prioridade maior que todos os operadores lógicos do cálculo proposicional.

�x P(x) v Q(x) �� (�x P(x)) v Q(x) �x P(x) v Q(x) � ��x (P(x) v Q(x))

E o conceito de escopo de uma variável

Variável Ligada

�x (x+y = 1)

x é ligada

� Quando um quantificador é usado na variável x, dizemos que essa ocorrência da variável é ligada.

Variável Livre

�x (x+y = 1)

x é ligada

� Uma ocorrência de uma variável que não é ligada por um quantificador ou não representa um conjunto de valores particulares é chamada de variável livre (y).

Variável Livre

�x (x+y = 1)

x é ligada

� Todas as variáveis que ocorrem em um função proposicional devem ser ligadas ou devem representar um conjunto de valores particulares para ser uma proposição.

Não é uma proposição, pois y é variável livre

Escopo

�x (P(x) ^ Q(x)) v �x R(x)

� É a parte da expressão lógica à qual um quantificador é aplicado.

Escopo Escopo

Escopo não se sobrepõe.

Escopo

�x (P(x) ^ Q(x)) v �y R(y)

� É a parte da expressão lógica à qual um quantificador é aplicado.

� Uma variável é livre se não está sob o escopo de algum quantificador.

Escopo Escopo

Escopo não se sobrepõe. Pode ser y ao invés de x.

Dúvidas!!!

� Dúvidas sobre Variável Livre, Variável Ligada e Escopo????

Refrescar a Mente!!!

�Na aula passada traduzimos as seguintes sentenças:Todo estudante desta classe estudou lógicaeTodo estudante da classe visitou Canadá ou México!!!

Predicados com duas variáveis

Para cada estudante desta classe, x estudou lógica.

C(x) = “x estudou lógica”S(x) = “x é estudante desta classe”

Vamos reformular nossa primeira frase: Todo estudante desta classe estudou lógica

Predicados com duas variáveis

Para cada estudante desta classe, x estudou lógica.

C(x) = “x estudou lógica”S(x) = “x é estudante desta classe”

Domínio 1: {estudantes desta classe}�x C(x)

Predicados com duas variáveis

Para cada estudante desta classe, x estudou lógica.

C(x) = “x estudou lógica”S(x) = “x é estudante desta classe”

Domínio 1: {estudantes desta classe}�x C(x)

Domínio 2: {todas as pessoas}�x (S(x) � C(x))

Predicados com duas variáveis

Para cada estudante desta classe, x estudou lógica.

C(x) = “x estudou lógica”S(x) = “x é estudante desta classe”

Q(x,y) = “estudante x estudou matéria y”

Agora vamos definir uma novo predicado !!!

Predicados com duas variáveis

Para cada estudante desta classe, x estudou lógica.

Q(x,y) = “estudante x estudou matéria y”

Domínio 1: {estudantes desta classe}�x Q(x,lógica)

Predicados com duas variáveis

Para cada estudante desta classe, x estudou lógica.

Q(x,y) = “estudante x estudou matéria y”

Domínio 1: {estudantes desta classe}�x Q(x,lógica)

Domínio 2: {todas as pessoas}�x (S(x) � Q(x, lógica))

Predicados com duas variáveis

Algum estudante da classe visitou Canadá ou México.

V(x,y) = “x visitou o país y”

�x (V(x,México) v V(x,Canadá))

Equivalências (S ����T)

� Sentenças que envolvem predicados e quantificadores são logicamente equivalentes se e somente se elas têm o mesmo valor verdade quaisquer que sejam os predicados substituídos nessas sentenças e qualquer que seja o domínio para as variáveis nessas funções proposicionais.

Equivalências

� �x(P(x) ^ Q(x)) ��x P(x) ^ �x Q(x)� �x(P(x) v Q(x)) ���x P(x) v �x Q(x)

Equivalências

� �x(P(x) ^ Q(x)) ��x P(x) ^ �x Q(x)� �x(P(x) v Q(x)) ���x P(x) v �x Q(x)

� �x(P(x) v Q(x)) � �x P(x) v �x Q(x)� �x(P(x) ^ Q(x)) � ��x P(x) ^ �x Q(x)

CUIDADO!!!!

Negando Expressões Quantificadas

� Não é o caso de todos os estudantes desta classe terem feito aulas de lógica.

~�x P(x)

Negando Expressões Quantificadas

� Não é o caso de todos os estudantes desta classe terem feito aulas de lógica.

~�x P(x)

� Existe um estudante desta classe que não teve aula de lógica.

�x ~P(x)

Podemos reformular a frase para:

Negando Expressões Quantificadas

� Não é o caso de todos os estudantes desta classe terem feito aulas de lógica.

~�x P(x)� Existe um estudante desta classe que não

teve aula de lógica.�x ~P(x)

~�x P(x) ���x ~P(x)

Ilustramos que:

Negando Expressões Quantificadas

� Existe um estudante na classe que teve aulas de calculo.

�x P(x)� Não é o caso de existir um estudante na

classe que teve aulas de calculo.~�x P(x)

Negando Expressões Quantificadas

� Não é o caso de existir um estudante na classe que teve aulas de calculo.

~�x P(x)

� Todo os estudantes nesta classe não tiveram aulas de calculo.

�x ~P(x)

Podemos reformular a frase para:

Negando Expressões Quantificadas

� Não é o caso de existir um estudante na classe que teve aulas de calculo.

~�x P(x)Todo os estudantes nesta classe não tiveram

aulas de calculo.�x ~P(x)

~�x P(x) � �x ~P(x) Ilustramos que:

Negando Expressões Quantificadas

� As regras para negações de quantificadoressão chamadas de Leis de De Morgan para quantificadores.

~�x P(x) ���x ~P(x)~�x P(x) � �x ~P(x)

Exercícios

1) Quais as negações de:a) “Existe um político honesto”b) “Todos os brasileiros comem churrasco”

3) Negar �x (x2 > x)4) Negar �x (x2 = x)5) Mostre que:

~�x (P(x)�Q(x)) ���x (P(x) ^ ~Q(x))

Exercício 1)

1) “Existe um político honesto”H(x) = “x é honesto”Domínio = {todos os políticos}

Como fica a proposição???

Exercício 1)

1) “Existe um político honesto”H(x) = “x é honesto”Domínio = {todos os políticos}

�x H(x)

Exercício 1)

1) “Existe um político honesto”H(x) = “x é honesto”Domínio = {todos os políticos}

�x H(x) negando ~�x H(x)

Exercício 1)

1) “Existe um político honesto”H(x) = “x é honesto”Domínio = {todos os políticos}

�x H(x) negando ~�x H(x) Sabemos que ~�x H(x) � �x ~P(x)Então podemos dizer que: ....

Exercício 1)

1) “Existe um político honesto”H(x) = “x é honesto”Domínio = {todos os políticos}

�x H(x) negando ~�x H(x) Sabemos que ~�x H(x) � �x ~P(x)Então podemos dizer que:Todos os políticos são desonestos.

Exercícios

1) Quais as negações de:a) “Existe um político honesto”b) “Todos os brasileiros comem churrasco”

3) Negar �x (x2 > x)4) Negar �x (x2 = x)5) Mostre que:

~�x (P(x)�Q(x)) ���x (P(x) ^ ~Q(x))6) Rosen pg 47 exercícios: 6c, 6d, 6e, 6f7) Rosen pg 48 exercício 34