Anonymous
Anonymous asked in Science & MathematicsMathematics · 1 year ago

Discrete math - negate proposition using the quantifier negation?

I'm asked to negate the following proposition using the quantifier negation rules. No negation operations are to appear before any of the quantifiers in the expression that is created. The issue is I'm not quite understanding what this means. All I'm given in my notes relating to negation quantifiers are the following formulas and their proofs:

∃xP(x)=¬∀x¬P(x)

∀xP(x)=¬∃x¬P(x)

I'm not quite sure how to take this information and apply it to a proposition or really, I don't quite understand what my end goal of this question is supposed to be.

This is the proposition I'm given to work with. I'd appreciate if someone taught me step by step how to solve these types of questions. You can make up your own proposition if you'd like, but I'm really confused and would appreciate some sort of example. The results I found online seemed really complex and confusing.

Given proposition:

∃𝑥 (𝐷(𝑥) → (𝐶(𝑥) ∨ F(x)))

1 Answer

Relevance
  • 1 year ago
    Favorite Answer

    The negation of that expression is:

    ∼∃x(D(x) → (C(x) ∧ F(x)))

    But that form has the negation of a quantifier ∼∃x(...) and you're asked to come up with an equivalent expression that doesn't have any such thing. That's where your negation-of-a-quantifier formulas find some use. In this case, you know that ∼∃x(P) is equivalent to ∀x(∼P) for any expression P, right? So

    ∼∃x(D(x) → (C(x) ∧ F(x))) = ∀x∼((D(x) → (C(x) ∧ F(x))))

    That's all that the assignment directly asked you to do, but it's usual to simplify results. I'd continue with the negation of an implication: ∼(P→Q) = P∧∼Q so that:

    = ∀x(D(x) ∧ ∼(C(x) ∧ F(x)))

    Then use De Morgan to simplify the negation of a conjunction:

    = ∀x(D(x) ∧ (∼C(x) ∨ ∼F(x)))

Still have questions? Get your answers by asking now.