Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Discrete Mathematics problem

  1. Sep 23, 2005 #1

    For one of the questions in my Discrete Mathematics course, I have to find what property of a formula makes its dual formula also its negative. With a dual formula, the logical operators of "^" and "v" are reversed, the former meaning "and" and the latter meaning "or". With its negative, all the letters in the equation are simply given a negative sign in front of them, turning positives into negatives and vice versa.

    I hope someone can help!
  2. jcsd
  3. Sep 23, 2005 #2
    I think you might want to look into De Morgan's Law.
  4. Sep 23, 2005 #3
    Thanks, I can see now that the basic formula for DeMorgan is one for which the dual is also its negative. (-pvq) is equivalent to -p^-q. I'm still not sure why or how to explain it, though. Can you give me a hint? Does it simply have to be two statements on either side of an ^ or v?
  5. Sep 24, 2005 #4


    User Avatar
    Gold Member

    Well, there are several ways of explaining it. Have you tried looking at a truth table as a guide?

    [tex]\begin{array}{|c|c|c|c|c|c|c|}\hline P&Q&\neg P&\neg Q&(P \wedge Q)&\neg (P \wedge Q)&(\neg P \vee \neg Q) \\ \hline T&T&F&F&T&F&F \\ \hline T&F&F&T&F&T&T \\ \hline F&T&T&F&F&T&T \\ \hline F&F&T&T&F&T&T \\ \hline\end{array}[/tex]

    (~P v ~Q) is true when ~P is true or* ~Q is true.
    What's another way of saying that ~P is true? Answer: P is false.
    What's another way of saying that ~Q is true? Answer: Q is false.
    So in other words, (~P v ~Q) is true when P is false or Q is false.

    ~(P & Q) is true when it is not the case that P and Q are both true.
    Well, if they aren't both true, then at least one of them must be false.
    So in other words, ~(P & Q) is true when P is false or Q is false.

    Make sense? Can you explain why ~(P v Q) is equivalent to (~P & ~Q)?

    *all ors are inclusive (x or y or both)
    Last edited: Sep 24, 2005
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook