Reescreva cada uma das sentenças abaixo de modo que o símbolo de negação apareça somente dentro de predicado, ou seja, de modo que nenhuma negação esteja à frente de um quantificador ou de uma proposição envolvendo operadores lógicos.

UNIVERSIDADE FEDERAL DE MATO GROSSO DO SUL FACULDADE DE COMPUTAÇÃO

neg(exists x exists y neg P(x, y) wed>= forall x forall y Q(x, y))

Passo 1

Beleza, vamos começar entendendo o que a questão está pedindo. A gente tem uma expressão lógica com negações e quantificadores, e a missão é reescrever essa expressão de modo que todas as negações fiquem dentro dos predicados. Ou seja, nada de negação na frente dos quantificadores ou de operadores lógicos. Para isso, vamos precisar usar as leis de De Morgan e as regras de negação dos quantificadores da lógica. Vamos lá!

Passo 2

Primeiro, vamos dar uma olhada na expressão original:
neg(exists x exists y neg P(x, y) wed>= forall x forall y Q(x, y))
Aqui, temos uma negação que abrange toda a expressão dentro dos parênteses, que por sua vez tem um “e” lógico ( wed>=) conectando dois quantificadores: um existencial ( exists) e um universal ( forall).

Passo 3

Vamos aplicar a negação na expressão dentro dos parênteses. Para isso, usamos a Lei de De Morgan, que nos diz que:
neg(A wed>= B) equiv neg A vee neg B
Então, aplicando isso na nossa expressão:
neg(exists x exists y neg P(x, y) wed>= forall x forall y Q(x, y)) equiv neg(exists x exists y neg P(x, y)) vee neg(forall x forall y Q(x, y))

Passo 4

Agora, vamos focar em cada negação separadamente. Primeiro, a negação de um quantificador existencial:
neg(exists x exists y neg P(x, y)) equiv forall x forall y neg(neg P(x, y))
Aqui, usamos a regra que a negação de “existe” é “para todo”. E a dupla negação neg(neg P(x, y)) simplifica para P(x, y).

Passo 5

Simplificando a primeira parte:
forall x forall y neg(neg P(x, y)) equiv forall x forall y P(x, y)

Passo 6

Agora, vamos tratar a segunda negação:
neg(forall x forall y Q(x, y)) equiv exists x exists y neg Q(x, y)
Aqui, usamos a regra que a negação de “para todo” é “existe”.

Passo 7

Substituindo as duas partes na nossa expressão original:
forall x forall y P(x, y) vee exists x exists y neg Q(x, y)

Resposta

A expressão reescrita com as negações somente dentro dos predicados fica:
forall x forall y P(x, y) vee exists x exists y neg Q(x, y)

Exercícios relacionados