Register to reply

How to proove De Morgan's Law for Logic?

by perdu
Tags: logic, morgan, proove
Share this thread:
perdu
#1
Apr18-05, 04:25 AM
P: 2
Without using Truth table

thanks folks

DeMorgan's Law:
~(P^Q)<=>~Pv~Q;
~(PvQ)<=>~P^~Q;
Phys.Org News Partner Science news on Phys.org
Suddenly, the sun is eerily quiet: Where did the sunspots go?
'Moral victories' might spare you from losing again
Mammoth and mastodon behavior was less roam, more stay at home
honestrosewater
#2
Apr18-05, 06:30 AM
PF Gold
honestrosewater's Avatar
P: 2,330
Several laws bear his name- which one do you want? Just write it out.
CRGreathouse
#3
Apr18-05, 07:23 AM
Sci Advisor
HW Helper
P: 3,684
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?)

perdu
#4
Apr18-05, 08:34 AM
P: 2
How to proove De Morgan's Law for Logic?

De Morgan's Law:
~(P^Q)<=>~Pv~Q;
~(PvQ)<=>~P^~Q;
BicycleTree
#5
Apr18-05, 10:55 AM
P: 552
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:

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.
BicycleTree
#6
Apr18-05, 11:59 AM
P: 552
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.
funkstar
#7
Apr19-05, 08:03 AM
P: 13
Quote Quote by CRGreathouse
(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]
gravenewworld
#8
Apr19-05, 09:49 PM
P: 1,404
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).
BicycleTree
#9
Apr20-05, 10:41 AM
P: 552
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?
ranjha
#10
Oct25-05, 12:22 PM
P: 5
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?
honestrosewater
#11
Oct25-05, 12:47 PM
PF Gold
honestrosewater's Avatar
P: 2,330
Quote Quote by ranjha
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.
wave
#12
Oct28-05, 01:13 AM
P: 97
Quote Quote by ranjha
Is there no easier way to prove DeMorgan's theorem without having to use EXPORTATION and DISJUNCTIVE SYLLOGISM rules?
Construct a PK proof.
AKG
#13
Oct29-05, 11:14 PM
Sci Advisor
HW Helper
P: 2,586
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
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
neil87
#14
Aug7-08, 12:57 AM
P: 1
Hi,
how to simplify (-p^q)v-(pvq) using the logical equivalence?
bettydlgc
#15
Dec11-08, 01:16 PM
P: 2
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)


Register to reply

Related Discussions
Prove De Morgan's LAw Set Theory, Logic, Probability, Statistics 14
How would you proove a^-n = 1/a^n? General Math 8
Siobhan Morgan's cosmology calculator has a new url Cosmology 5
Proove its a circumference Precalculus Mathematics Homework 13
How to proove this Linear & Abstract Algebra 11