Expressions related by $\leftrightarrow$ have the same truth value in every case and can replace one another.

Relative to a fixed universe $U$, $\overline{A}$ contains the elements of $U$ that are not in $A$.

Negation interchanges paired operations, such as AND with OR and intersection with union.

A form in which negations occur only directly on basic propositions.

Classical and intuitionistic logic

The equivalence $\neg(P \land Q) \leftrightarrow (\neg P \lor \neg Q)$ holds classically, but not generally intuitionistically.

Discrete mathematicsLesson 2 of 2 in the course Boolean algebra and logic gates

De Morgan's Laws in Logic, Set Theory, and Boolean Algebra

5 flashcards · 5 quiz questions · 5 match pairs · 5 fill-in sentences · English

Save course

Lesson progress

0 / 5

Your progress is kept in this browser only.Sign up to save it

Summary

De Morgan's laws describe how negation changes a statement involving AND or OR. They are useful whenever a logical condition needs to be rewritten without changing its meaning.

$\neg(A \land B) \equiv (\neg A) \lor (\neg B)$

In words: not both A and B means not A or not B. The OR here is inclusive: it is true if one or both of its statements are true.

All flashcards

Logical equivalence: Expressions related by $\leftrightarrow$ have the same truth value in every case and can replace one another.
Set complement: Relative to a fixed universe $U$ , $\overline{A}$ contains the elements of $U$ that are not in $A$ .
De Morgan duality: Negation interchanges paired operations, such as AND with OR and intersection with union.
Negation normal form: A form in which negations occur only directly on basic propositions.
Classical and intuitionistic logic: The equivalence $\neg(P \land Q) \leftrightarrow (\neg P \lor \neg Q)$ holds classically, but not generally intuitionistically.

Quiz questions

In logic, what does $X \vdash Y$ mean?Answer: $Y$ follows from $X$ .
For sets $A$ and $B$ , which expression is equivalent to the set difference $A - B$ ?Answer: $A \cap \overline{B}$
Which expression is equivalent to the modal formula $\Diamond p$ ?Answer: $\neg\Box\neg p$
What does the symbol $\leftrightarrow$ express between two logical formulas?Answer: They have the same truth value in every case.
In classical logic, which formula expresses that every object has property $P$ ?Answer: $\neg\exists x\,\neg P(x)$

Based on the Wikipedia article De Morgan's laws, licensed CC BY-SA 4.0. Adapted into a summary, flashcards and quizzes.

All Discrete mathematics lessons

Discrete mathematicsBinary Relations: Operations, Properties, Functions, and Applications5 flashcards · 5 quiz questions · 4 gamesPlay free →Discrete mathematicsPigeonhole Principle: Counting, Collisions, and Applications5 flashcards · 5 quiz questions · 4 gamesPlay free →

Summary

All flashcards

Quiz questions

More in Discrete mathematics