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 forall y forall x(P(x, y) vee Q(x, y))

Passo 1

Beleza, vamos resolver essa questão de lógica! O enunciado pede para reescrever a sentença lógica de forma que a negação ( neg) apareça só dentro dos predicados, ou seja, não pode estar diretamente antes dos quantificadores ou de operadores lógicos como o “ou” ( vee). Para isso, vamos usar algumas regras da lógica proposicional e quantificadores.

Passo 2

Primeiro, olhamos para a sentença original:
neg forall y forall x (P(x, y) vee Q(x, y))
Essa expressão começa com uma negação seguida de dois quantificadores universais ( forall). Nosso objetivo é “empurrar” essa negação para dentro, até os predicados.

Passo 3

A primeira coisa a fazer é lidar com a negação dos quantificadores. Sabemos que:
neg forall y phi(y) equiv exists y neg phi(y)
Aplicando isso à nossa expressão:
neg forall y forall x (P(x, y) vee Q(x, y)) equiv exists y neg forall x (P(x, y) vee Q(x, y))

Passo 4

Vamos aplicar a mesma regra novamente para o próximo quantificador:
neg forall x phi(x) equiv exists x neg phi(x)
Então, continuamos:
exists y neg forall x (P(x, y) vee Q(x, y)) equiv exists y exists x neg (P(x, y) vee Q(x, y))

Passo 5

Agora, precisamos lidar com a negação da disjunção dentro dos parênteses. Sabemos que:
neg (A vee B) equiv neg A wed>= neg B
Aplicando isso à nossa expressão:
exists y exists x (neg P(x, y) wed>= neg Q(x, y))

Resposta

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

Exercícios relacionados