Proving De Morgan laws inductively?

  • Context: Graduate 
  • Thread starter Thread starter next__
  • Start date Start date
  • Tags Tags
    Laws
Click For Summary
SUMMARY

The discussion focuses on proving De Morgan's laws inductively for propositions, specifically the equivalence of conjunction and disjunction for all n ≥ 2. The laws state that (P(d1) ∧ ... ∧ P(dn)) = (¬P(d1)) ∨ ... ∨ (¬P(dn)). Participants emphasize using Boolean algebra and the properties of the operators ∧ (AND) and ∨ (OR), which are associative. The inductive proof method is suggested as a suitable approach for establishing the validity of these laws.

PREREQUISITES
  • Understanding of Boolean algebra
  • Familiarity with inductive proof techniques
  • Knowledge of De Morgan's laws
  • Concept of associative properties of logical operators
NEXT STEPS
  • Study inductive proofs in mathematical logic
  • Explore Boolean algebra operations and their properties
  • Review examples of De Morgan's laws in propositional logic
  • Learn about the application of induction in algebraic structures
USEFUL FOR

Students of mathematics, computer scientists, and anyone interested in formal logic and proof techniques, particularly in the context of Boolean algebra and propositional logic.

next__
Messages
1
Reaction score
0
How can I prove <by induction> the following De Morgan laws are valid for all n >= 2

- ( P(d1) ^ ... ^ P(dn) ) = ( - P(d1) ) v ... v ( - P(dn) )

knowing that -(p^q)=(-p)v(-q) and -((p)v(q))=(-p)^(-q) ?

I can use the inductive proof method on algebra/math theorems that have to do with variables, numbers, series, sums, etc. but I don't know what to do with propositions. Help, anyone?

I know how to prove the De Morgan laws when it comes to sets, I can also do it by deduction, but I'm just curious as to how you'd go about doing this inductively.
 
Physics news on Phys.org
Hint: Treat the propositions as formulas in Boolean algebra and use the fact that the operators ^ and v are (individually) associative.
 

Similar threads

Undergrad Transformation rules in Boolean algebra
  • · Replies 8 ·
Replies
8
Views
2K
MHB Solving a Complex Logical Equivalence in CNF Form
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Why Did My Logical Equivalence Proof Fail?
  • · Replies 2 ·
Replies
2
Views
2K
MHB Natural deduction (negated implication)
  • · Replies 8 ·
Replies
8
Views
4K
Undergrad Translate compound proposition p → q (implication) to p↓q question
  • · Replies 4 ·
Replies
4
Views
2K
MHB How to Prove Predicate Logic Validity with Induction?
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Proving the Implication of p and (p -> q) to q without Truth Tables
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Proving propositions involving "if and only if"
  • · Replies 19 ·
Replies
19
Views
2K
Undergrad Proving Theorems Not in "If-Then" Form
  • · Replies 7 ·
Replies
7
Views
2K
Do these two statements imply an underlying induction proof?
  • · Replies 7 ·
Replies
7
Views
1K