Exercícios Resolvidos de Lógica de Primeira Ordem e Modelos Semânticos

1 40 Passe as frases abaixo para fórmulas da Lógica de Primeira Ordem A fórmula deve ser a mais representativa possível isto é ela deve conter conectivos correspondentes a palavras da frase como ou se então etc Sem esta observação cada frase poderia ser representada por uma única variável Considere que o ou é o da Lógica Utilize Ax y para x ama y Cx para x faz computação isto é na estrutura contendo todas as pessoas os predicados A e C possuem este significado Será necessário utilizar símbolos de constante deixe bem clara a associação dos símbolos às pessoas A única justificativa exigida é a associação de símbolos de constante a constantes a João ama Maria que não ama ninguém b existe alguém que ama todo mundo e que não é amado por pelo menos uma pessoa c quem faz computação ama pelo menos uma pessoa d Maria ama alguém que chamaremos de x que faz computação e x ama Maria Esta pessoa x ama apenas mais uma pessoa que é diferente de Maria e que não faz computação 2 30 Todas as estruturas e fórmulas desta questão utilizam a linguagem associada ao vocabulário V P Q R no qual P e Q são símbolos de predicado unários e R é símbolo de predicado binário Todas as estruturas da sua resposta devem utilizar um conjunto universo de tamanho 4 e que contenha um subconjunto das seis primeiras letras do seu nome completo Então se o seu nome for Ana Maria Silva o universo será a n m r i s lembrando conjuntos não possuem elementos repetidos ou a n m r Justifique ambos os itens baseado na definição de verdade em uma estrutura Minhas iniciais c j e l a Faça uma estrutura M1 que seja modelo para x Px y x y Rx y Utilize o nome M1 na sua resposta Os predicados P e R de M1 devem obedecer a algumas restrições P M1 P R M2² R b Faça uma estrutura M2 que seja modelo para x Px Qx y Ry x Os predicados P e Q de M2 devem obedecer a algumas restrições P M2 P Q M2 Q Utilize o nome M2 na sua resposta A justificativa deste item precisa ser mais elaborada Necessariamente faça o diagrama do grafo desta estrutura M2 considerando R a relação que dá origem ao grafo Circule os elementos dos predicados P e Q no diagrama do grafo como é feito em um diagrama de Venn 3 30 Utilizando os grafos abaixo mostre que a G1 Ex y Ey z Ex z b G2 z Ex y Ey x Ex z Ey z O predicado binário E é representado graficamente por uma seta Isto é G1 Ex y se há uma seta do vértice x para o vértice y Isto é x y E O conjunto universo de um grafo são o conjunto de seus vértices Na resposta para provar que um grafo é ou não é modelo você deve deixar claro quais vértices e arestas tornam a fórmula verdadeira ou falsa naquele grafo Além disto você deve explicar o seu raciocínio justificar Questão 1 a João ama Maria que não ama ninguém Aj m y Am y b existe alguém que ama todo mundo e que não é amado por pelo menos uma pessoa x y Ax y z Az x c quem faz computação ama pelo menos uma pessoa x Cx y Ax y d Maria ama alguém que chamaremos de x que faz computação e x ama Maria Esta pessoa x ama apenas mais uma pessoa que é diferente de Maria e que não faz computação x Am x Cx Ax m y Ax y y m Cy z Ax z z m z y Questão 2 a Vamos começar definindo os termos O universo da nossa estrutura será um subconjunto das seis primeiras letras das suas iniciais c j e l Portanto o universo U é c j e l A sentença que queremos modelar é x Px y x y Rx y Esta sentença diz que Existe um elemento x tal que P é verdadeiro para x Para todo y se y é diferente de x então Rx y é verdadeiro Vamos definir nossa estrutura M1 O universo de M1 é U c j e l Para a definição dos predicados precisamos obedecer às restrições P U P R 𝑈2 R Uma possível definição é P em M1 c apenas o elemento c satisfaz o predicado P R em M1 c j c e c l c está relacionado com todos os outros elementos do universo Agora vamos verificar se M1 é um modelo para a sentença x Px é verdadeiro em M1 porque c é um elemento de P em M1 y y x Rx y é verdadeiro em M1 porque Para y j Rc j é verdadeiro Para y e Rc e é verdadeiro Para y l Rc l é verdadeiro Para y c a condição y x é satisfeita pois x y Portanto a estrutura M1 é um modelo para a sentença dada e satisfaz todas as restrições especificadas b A sentença dada é x Px Qx y Ry x Para criar uma estrutura M2 que satisfaça essa sentença usaremos as seguintes definições Universo U de M2 U j o a v i t Definição dos predicados P Q e R P é um conjunto que não é vazio e não é igual a U Vamos definir P de M2 j o Q também não pode ser vazio ou igual a U Como todo elemento de P também deve pertencer a Q vamos definir Q de M2 j o a R deve conectar um elemento y para cada elemento x em P Então vamos definir R de M2 a j v o i j t o Representação do Grafo Aqui representaremos a relação R usando setas Por exemplo a relação a j é representada por uma seta apontando de a para j Explicação da Representação do Grafo Cada letra do universo U é representada como um nó A relação R é representada por setas Por exemplo há uma seta apontando de a para j para representar a relação R entre a e j Os elementos de P são circulados em vermelho e os de Q em verde Note que como Q contém todos os elementos de P os círculos vermelhos de P ficarão dentro dos círculos verdes de Q para aqueles elementos que pertencem a ambos Questão 3 G1 Vertices a b c d Arestas representadas por setas a b a c c d Fórmula para G1 Ex y Ey z Ex z Se há uma seta do vértice x para o vértice y e uma seta do vértice y para o vértice z então deveria haver uma seta do vértice x para o vértice z Verificando a validade para G1 Vamos verificar cada par de arestas para ver se esta fórmula é satisfeita Considerando setas de a para b e de b para c Não existe uma seta de b para c então esta combinação não viola a fórmula Considerando setas de a para b e de b para d Da mesma forma não existe uma seta de b para d então esta combinação não viola a fórmula Considerando setas de a para c e de c para d Há uma seta de a para c e de c para d De acordo com a fórmula deveria haver uma seta de a para d No entanto essa seta não existe no grafo G1 Conclusão para G1 G1 não é um modelo da fórmula Ex y Ey z Ex z porque não atende à condição onde se há uma seta de a para c e de c para d deveria haver uma seta de a para d G2 Vertices a b c Arestas representadas por setas a b a c b a b c Fórmula para G2 zEx y Ey x Ex z Ey z Se há uma seta de x para y e de y para x então há setas de x e y para algum z que pode ou não ser um dos dois Verificando a validade para G2 Considerando a b e b a Há uma seta de a para b e uma seta de b para a Então segundo a fórmula deveria haver setas de a e b para algum z No grafo G2 z pode ser c pois temos setas a c e b c Conclusão para G2 G2 é um modelo da fórmula zEx y Ey x Ex z Ey z porque ele atende à condição onde se há setas mútuas entre a e b existem setas de a e b para um terceiro vértice que neste caso é c Questão 1 a João ama Maria que não ama ninguém Aj m y Am y b existe alguém que ama todo mundo e que não é amado por pelo menos uma pessoa x y Ax y z Az x c quem faz computação ama pelo menos uma pessoa x Cx y Ax y d Maria ama alguém que chamaremos de x que faz computação e x ama Maria Esta pessoa x ama apenas mais uma pessoa que é diferente de Maria e que não faz computação x Am x Cx Ax m y Ax y y m Cy z Ax z z m z y Questão 2 a Vamos começar definindo os termos O universo da nossa estrutura será um subconjunto das seis primeiras letras das suas iniciais c j e l Portanto o universo U é c j e l A sentença que queremos modelar é x Px y x y Rx y Esta sentença diz que Existe um elemento x tal que P é verdadeiro para x Para todo y se y é diferente de x então Rx y é verdadeiro Vamos definir nossa estrutura M1 O universo de M1 é U c j e l Para a definição dos predicados precisamos obedecer às restrições P U P R U 2 R Uma possível definição é P em M1 c apenas o elemento c satisfaz o predicado P R em M1 c j c e c l c está relacionado com todos os outros elementos do universo Agora vamos verificar se M1 é um modelo para a sentença x Px é verdadeiro em M1 porque c é um elemento de P em M1 y y x Rx y é verdadeiro em M1 porque Para y j Rc j é verdadeiro Para y e Rc e é verdadeiro Para y l Rc l é verdadeiro Para y c a condição y x é satisfeita pois x y Portanto a estrutura M1 é um modelo para a sentença dada e satisfaz todas as restrições especificadas b A sentença dada é x Px Qx y Ry x Para criar uma estrutura M2 que satisfaça essa sentença usaremos as seguintes definições Universo U de M2 U j o a v i t Definição dos predicados P Q e R P é um conjunto que não é vazio e não é igual a U Vamos definir P de M2 j o Q também não pode ser vazio ou igual a U Como todo elemento de P também deve pertencer a Q vamos definir Q de M2 j o a R deve conectar um elemento y para cada elemento x em P Então vamos definir R de M2 a j v o i j t o Representação do Grafo Aqui representaremos a relação R usando setas Por exemplo a relação a j é representada por uma seta apontando de a para j Explicação da Representação do Grafo Cada letra do universo U é representada como um nó A relação R é representada por setas Por exemplo há uma seta apontando de a para j para representar a relação R entre a e j Os elementos de P são circulados em vermelho e os de Q em verde Note que como Q contém todos os elementos de P os círculos vermelhos de P ficarão dentro dos círculos verdes de Q para aqueles elementos que pertencem a ambos Questão 3 G1 Vertices a b c d Arestas representadas por setas a b a c c d Fórmula para G1 Ex y Ey z Ex z Se há uma seta do vértice x para o vértice y e uma seta do vértice y para o vértice z então deveria haver uma seta do vértice x para o vértice z Verificando a validade para G1 Vamos verificar cada par de arestas para ver se esta fórmula é satisfeita Considerando setas de a para b e de b para c Não existe uma seta de b para c então esta combinação não viola a fórmula Considerando setas de a para b e de b para d Da mesma forma não existe uma seta de b para d então esta combinação não viola a fórmula Considerando setas de a para c e de c para d Há uma seta de a para c e de c para d De acordo com a fórmula deveria haver uma seta de a para d No entanto essa seta não existe no grafo G1 Conclusão para G1 G1 não é um modelo da fórmula Ex y Ey z Ex z porque não atende à condição onde se há uma seta de a para c e de c para d deveria haver uma seta de a para d G2 Vertices a b c Arestas representadas por setas a b a c b a b c Fórmula para G2 zEx y Ey x Ex z Ey z Se há uma seta de x para y e de y para x então há setas de x e y para algum z que pode ou não ser um dos dois Verificando a validade para G2 Considerando a b e b a Há uma seta de a para b e uma seta de b para a Então segundo a fórmula deveria haver setas de a e b para algum z No grafo G2 z pode ser c pois temos setas a c e b c Conclusão para G2 G2 é um modelo da fórmula zEx y Ey x Ex z Ey z porque ele atende à condição onde se há setas mútuas entre a e b existem setas de a e b para um terceiro vértice que neste caso é c