How to proove De Morgan's Law for Logic?

  • Thread starter perdu
  • Start date
  • Tags
    Law Logic
In summary, DeMorgan's Law states that ~(P^Q)<=>~Pv~Q and ~(PvQ)<=>~P^~Q. It can be proven using the rules of exportation, modus ponens, modus tollens, disjunctive argument, conjunctive argument, simplification, and negation. Other laws that bear DeMorgan's name include ~(~P v ~Q) iff ~P&~Q and ~(~P & ~Q) iff ~P v ~Q. These laws can be proven using a PK proof or by using logical equivalences.
  • #1
perdu
2
0
How to proove De Morgan's Law for Logic??

Without using Truth table

thanks folks

DeMorgan's Law:
~(P^Q)<=>~Pv~Q;
~(PvQ)<=>~P^~Q;
 
Last edited:
Physics news on Phys.org
  • #2
Several laws bear his name- which one do you want? Just write it out.
 
  • #3
I imagine he wants

[tex]-\vee_{i=1}^nk_i=\wedge_{i=1}^n-k_i[/tex]

[tex]-\wedge_{i=1}^nk_i=\vee_{i=1}^n-k_i[/tex]

(I used - for not; how do you get the proper symbol?)
 
  • #4
De Morgan's Law:
~(P^Q)<=>~Pv~Q;
~(PvQ)<=>~P^~Q;
 
  • #5
Well, here's a way to prove the first implication of the first law, ~(p&q) --> ~p v ~q

Here the indented lines following an assumption indicate the scope of the assumption:

Code:
1. Assume ~(p&q) v (~r&r)
   2. (p&q) --> (~r&r) (1, material implication)
   3. p --> (q --> (~r&r)) (2, exportation)
   4. p --> (~q v (~r&r)) (3, material implication)
   5. ~p v (~q v (~r&r)) (4, material implication)
   6. (~p v ~q) v (~r&r) (5, association)
7. (~(p&q) v (~r&r)) --> ((~p v ~q) v (~r&r)) (1-6, conditional proof)

8. Assume ~r&r
(assumption of line 8 has no scope beyond itself)
9. ~(~r&r) (8, reductio ad absurdum)

10. Assume ~(p&q)
   11. ~(p&q) v (~r&r) (10, addition)
   12. (~p v ~q) v (~r&r) (7, modus ponens)
   13. ~p v ~q (9, 12, disjunctive syllogism)
14. ~(p&q) --> (~p v ~q) (10-13, conditional proof)

The second half of the first DeMorgan's law, (~p v ~q) --> ~(p&q),
can be proved similarly.
 
  • #6
The key to that proof was the use of exportation to get line 7. Both halves of the second DeMorgan's law can also be proved by the same general idea, though it's slightly trickier.
 
  • #7
CRGreathouse said:
(I used - for not; how do you get the proper symbol?)
\neg in LaTeX (for negate).

Example:

[tex] \neg \exists x . P(x) \Leftrightarrow \forall x. \neg P(x) [/tex]
 
  • #8
The way I learned this is that is follows from the semantic defintion of truth.

Say you you have an interpretation M and a sentence F
by definition

M|= ~F iff not M|=F
M|= (F&G) iff M|= F and M|=G
M|= (FvG) iff M|= F or M|=G

Thus a consequence of the definition of truth for negation and of two junctions is the fact that (F&G) is true iff ~(~Fv~G) is true, and (FvG) is true iff ~(~F&~G) is true.

You have ~(PvQ) iff ~P&~Q, which would be equivalent to ~(FvG) iff ~~(~F&~G), which is the same as saying ~(FvG) iff (~F&~G).
 
  • #9
Thus a consequence of the definition of truth for negation and of two junctions is the fact that (F&G) is true iff ~(~Fv~G) is true, and (FvG) is true iff ~(~F&~G) is true.
How do you reason that?
 
Last edited:
  • #10
Is there no easier way to prove DeMorgan's theorem without having to use EXPORTATION and DISJUNCTIVE SYLLOGISM rules? Is there a way to prove this Law by just using modus ponens, modus tollens, disjunctive argument, conjunctive argument, simplification, and so on?
 
  • #11
ranjha said:
Is there no easier way to prove DeMorgan's theorem without having to use EXPORTATION and DISJUNCTIVE SYLLOGISM rules? Is there a way to prove this Law by just using modus ponens, modus tollens, disjunctive argument, conjunctive argument, simplification, and so on?
What is "and so on"? What rules do you have? Just write them out, provide a link, or tell us the name of the system, if you know it; it shouldn't take but a few minutes. :smile:
 
  • #12
ranjha said:
Is there no easier way to prove DeMorgan's theorem without having to use EXPORTATION and DISJUNCTIVE SYLLOGISM rules?

Construct a PK proof.
 
  • #13
Code:
1  | ~(P & Q)            assumption
...|-------------------- 
2  || ~(~P v ~Q)         assumption
...||------------------- 
3  ||| P                 assumption
...|||------------------
4  |||| Q                assumption
...||||-----------------
5  |||| P & Q            3, 4 conjunction introduction
6  |||| ~(P & Q)         1, repitition
7  ||| ~Q                4-6 negation introduction 
8  ||| ~P v ~Q           7, disjunction introduction
9  ||| ~(~P v ~Q)        2, repitition
10 || ~P                 3-9, negation introduction
11 || ~P v ~Q            10, disjunction introduction
12 || ~(~P v ~Q)         2, repitition
13 | ~P v ~Q             2-12 negation elimination
Code:
1  | ~P v ~Q               assumption
...|----------------------- 
2  || ~P                   assumption
...||---------------------- 
3  ||| P & Q               assumption
...|||---------------------
4  ||| P                   3, conjunction elimination
5  ||| ~P                  2, repitition
6  || ~(P & Q)             3-5, negation introduction
7  || ~Q                   assumption
...||----------------------
8  ||| P & Q               assumption
...|||---------------------
9  ||| Q                   8, conjunction elimination
10 ||| ~Q                  7, repitition
11 || ~(P & Q)             8-10 negation introduction
12 | ~(P & Q)              1, 2-5, 7-11 disjunction elimination
 
Last edited:
  • #14


Hi,
how to simplify (-p^q)v-(pvq) using the logical equivalence?
 
  • #15


How do you prove the following? I understand that it is part of demorgans law.. but how do i get rid of the double negative?

-(-A v -B) therefore (A & B)
 

Related to How to proove De Morgan's Law for Logic?

What is De Morgan's Law?

De Morgan's Law is a fundamental law in logic that states that the negation of a conjunction (AND) is logically equivalent to the disjunction (OR) of the negations of the individual statements. It also states that the negation of a disjunction is logically equivalent to the conjunction of the negations of the individual statements.

How do I prove De Morgan's Law for Logic?

To prove De Morgan's Law for Logic, you can use the truth table method. First, construct a truth table with four columns for two statements and their conjunction/disjunction, and two additional columns for the negation of each statement. Next, fill in the truth values for all possible combinations of the statements. Finally, compare the truth values for the conjunction/disjunction and the negations. If they are equivalent, then De Morgan's Law is proven.

Why is De Morgan's Law important in logic?

De Morgan's Law is important in logic because it allows us to simplify complex statements and make logical deductions. It also helps us to understand the logical relationships between different statements and their negations.

Is De Morgan's Law applicable to all types of statements?

Yes, De Morgan's Law is applicable to all types of statements in logic, including simple statements, compound statements, and quantified statements.

Can De Morgan's Law be extended to more than two statements?

Yes, De Morgan's Law can be extended to more than two statements. This is known as De Morgan's Law for n statements, and it states that the negation of a conjunction of n statements is equivalent to the disjunction of the negations of the individual statements, and the negation of a disjunction of n statements is equivalent to the conjunction of the negations of the individual statements.

Similar threads

  • Programming and Computer Science
Replies
7
Views
4K
  • Calculus and Beyond Homework Help
Replies
24
Views
4K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
  • Quantum Interpretations and Foundations
Replies
9
Views
2K
  • Calculus and Beyond Homework Help
Replies
6
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
14
Views
4K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
11
Views
1K
Back
Top