Predicate Logic - Using the 3 Rules

Question

I have a question which I'm struggling to get to grips with.

Here are my predicates:

Px = “x is a person”

and

Kxy = "x knows y's business"

and the question is:

"Write the negation of the sentence ∀ x • ∀ y • Px ∧ Py ⇒ ¬ Kxy in a form without any “¬ ” symbols, showing how you used the laws of logic to transform it."

I know of the 3 rules: negation, implication, and de Morgan's Law. I've used these rules/ law(s) on much simpler questions in the past however I'm not too sure on how to apply them to this question.

Answer 1

The negation of :

$∀x ∀y (Px ∧ Py \to \lnot Kxy)$

is :

$\lnot ∀x ∀y (Px ∧ Py \to \lnot Kxy)$.

Using the equivalence between $\lnot \forall$ and $\exists \lnot$, we can rewrite the last formula as :

$\exists x \exists y \lnot (Px ∧ Py \to \lnot Kxy)$.

Now we apply the "propositional" equivalence between $\lnot(p \to q)$ and $(p \land \lnot q)$ to get :

$\exists x \exists y (Px ∧ Py \land \lnot \lnot Kxy)$

and finally, by double negation :

$\exists x \exists y (Px ∧ Py \land Kxy)$.

Answer 2

Turn the "implies" into an "or". Then the inside becomes $\neg Px\lor\neg Py\lor\neg Kxy$. So the negation is: $$\exists x\exists y (Px\land Py\land Kxy)$$

Answer 3

Well first recall that:

$ ¬ (A \wedge B) \equiv ¬A \vee ¬B \\ A \rightarrow B \equiv ¬A \vee B $

So,

$ ¬ ( Px \wedge Py \rightarrow ¬Kxy) \equiv ¬( ¬(Px \wedge Py) \vee (¬Kxy) ) \equiv (Px \wedge Py) \wedge Kxy $