1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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