Explain De-Morgan’s theorem with suitable example.

RGPV PYQ

De Morgan’s Theorems

De Morgan’s theorems are two fundamental rules in logic that describe the relationship between negation, conjunction, and disjunction. They are named after Augustus De Morgan, a Scottish mathematician and logician who formulated them in the mid-19th century.

First De Morgan’s Theorem:

Theorem: ¬(P∧Q)=(¬P)∨(¬Q)

This theorem states that the negation of a disjunction is equivalent to the conjunction of the negations of the individual propositions.

Example:

Consider the statement:

"It is not the case that it is either raining or windy today."

Using the first De Morgan’s theorem, we can rewrite this statement as:

It is raining or it is cold, or both.

This means that the statement “It is not the case that it is raining and it is cold” is equivalent to the statement “It is raining, or it is cold, or both”.

---

Second De Morgan’s Theorem:

Theorem: ¬(P∨Q)=(¬P)∧(¬Q)

This theorem states that the negation of a disjunction is equivalent to the conjunction of the negations of the individual propositions.

Example:

Consider the statement:

I am not going to the party or I am not going to the concert.

Using the second De Morgan’s theorem, we can rewrite this statement as:

I am going to the party and I am going to the concert.

This means that the statement “I am not going to the party or I am not going to the concert” is equivalent to the statement “I am going to the party and I am going to the concert”.

References:

• “Discrete Mathematics” by Ronald L. Graham, Bruce L. Graham, and Glenn F. Flanigan (2009): Chapter 4, Section 4.4
• “Logic for Computer Science” by John Hopcroft, Hennie M. Saphiro, and Jeffery D. Ullman (2006): Chapter 2, Section 2.2