Proving De Morgan laws inductively?

  • Thread starter next__
  • Start date
  • Tags
    Laws
In summary, the conversation is about proving the De Morgan laws for propositions using an inductive proof method. The laws state that ( P(d1) ^ ... ^ P(dn) ) = ( - P(d1) ) v ... v ( - P(dn) ), and the conversation discusses how this can be done using algebraic and Boolean algebra principles. The use of induction is suggested, with the hint to treat the propositions as formulas in Boolean algebra and use the associative properties of the ^ and v operators.
  • #1
next__
1
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
  • #2
Hint: Treat the propositions as formulas in Boolean algebra and use the fact that the operators ^ and v are (individually) associative.
 

FAQ: Proving De Morgan laws inductively?

1. What are De Morgan laws?

The De Morgan laws are a set of two rules in Boolean algebra that describe the relationship between logical operations "AND" and "OR" when applied to two statements.

2. What is the significance of proving De Morgan laws inductively?

Proving De Morgan laws inductively provides a mathematical proof for the validity of these laws, which can then be applied in various fields such as computer science, logic, and mathematics.

3. How can De Morgan laws be proven inductively?

De Morgan laws can be proven inductively by using mathematical induction, which involves showing that the laws hold for a base case and then proving that they hold for all other cases.

4. What is the process for proving De Morgan laws inductively?

The process for proving De Morgan laws inductively involves first stating the base case, which is typically the simplest form of the laws, and then using mathematical induction to show that the laws hold for all other cases by assuming they hold for a certain case and then proving they hold for the next case.

5. Why is it important to prove De Morgan laws inductively?

Proving De Morgan laws inductively is important because it provides a rigorous proof for the validity of these laws, which allows for their application in various fields and ensures that logical operations are consistent and accurate.

Similar threads

Transformation rules in Boolean algebra
Replies
8
Views
2K
MHB Solving a Complex Logical Equivalence in CNF Form
Replies
3
Views
2K
MHB Natural deduction (negated implication)
Replies
8
Views
3K
I Translate compound proposition p → q (implication) to p↓q question
Replies
4
Views
1K
MHB How to Prove Predicate Logic Validity with Induction?
Replies
2
Views
2K
I Proving the Implication of p and (p -> q) to q without Truth Tables
Replies
3
Views
1K
I Understanding extinction probability in simple GWP
Replies
1
Views
442
Do these two statements imply an underlying induction proof?
Replies
7
Views
807
MHB Proving the symmetry of self complementary graphs with n=4k+1
Replies
1
Views
2K
Mathematical Induction with binomial sum
Replies
9
Views
780

Hot Threads

Recent Insights

Back
Top