Discrete Mathematics problem

84
0
Hi,

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!
Coldie
 
321
0
I think you might want to look into De Morgan's Law.
 
84
0
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?
 

honestrosewater

wrapt in a willow
Gold Member
1,996
4
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:

The Physics Forums Way

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top