Why is ~(P v Q) equivalent to (~P & ~Q)?

In summary, De Morgan's law states that two statements that are not both true are equivalent to a third statement that is both true and false.
  • #1
Coldie
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
 
Physics news on Phys.org
  • #2
I think you might want to look into De Morgan's Law.
 
  • #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?
 
  • #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:

1. What is discrete mathematics?

Discrete mathematics is a branch of mathematics that deals with mathematical structures and objects that are countable or distinct, rather than continuously varying.

2. What are some applications of discrete mathematics?

Discrete mathematics has various applications in computer science, including cryptography, coding theory, and algorithm design. It is also used in operations research, social sciences, and engineering.

3. What are the fundamental concepts in discrete mathematics?

The fundamental concepts in discrete mathematics include sets, relations, functions, graphs, and combinatorics. These concepts are used to analyze and solve problems in discrete structures.

4. How is discrete mathematics different from continuous mathematics?

Discrete mathematics deals with objects that have distinct or separated values, while continuous mathematics deals with objects that have a continuous range of values. Discrete mathematics is often applied to problems in computer science and engineering, while continuous mathematics is used in physics and other areas of science.

5. What are some common problem-solving techniques used in discrete mathematics?

Problem-solving techniques in discrete mathematics include mathematical induction, proof by contradiction, and combinatorial reasoning. These techniques are used to analyze and solve problems involving discrete structures and objects.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
4
Views
822
  • Introductory Physics Homework Help
Replies
5
Views
1K
Replies
5
Views
1K
  • Introductory Physics Homework Help
Replies
1
Views
846
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Introductory Physics Homework Help
Replies
4
Views
1K
  • Classical Physics
Replies
6
Views
504
  • Beyond the Standard Models
Replies
0
Views
898
Replies
24
Views
1K
Replies
1
Views
768
Back
Top