Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "De Morgan's Laws"
(Proof of both of De Morgan's laws using truth tables.)
 
Line 5: Line 5:
  
 
In fact, '''all''' dual operators will interchange upon negation. So we can also say that for any [[proposition]] P, <math>\neg\forall x \: P(x) \equiv \exists x \:\neg  P(x)</math>, because <math>\forall</math> is dual with <math>\exists</math>. Also, <math>\neg\exists x \:P(x) \equiv \forall x \:\neg P(x)</math>.  
 
In fact, '''all''' dual operators will interchange upon negation. So we can also say that for any [[proposition]] P, <math>\neg\forall x \: P(x) \equiv \exists x \:\neg  P(x)</math>, because <math>\forall</math> is dual with <math>\exists</math>. Also, <math>\neg\exists x \:P(x) \equiv \forall x \:\neg P(x)</math>.  
 +
 +
==Proof==
 +
Any two propositions <math>p</math> and <math>q</math> have four possible combinations of truth values. We can therefore prove that two propositions stated in terms of <math>p</math> and <math>q</math> are equivalent by proving that they hold the same value in each of the four cases.
 +
 +
In the following truth table, <math>\top</math> indicates "true" and <math>\bot</math> indicates "false".
 +
 +
{| class="wikitable"
 +
|- style="text-align: center;"
 +
| <math>p</math> || <math>q</math> || <math>\neg p</math> || <math>\neg q</math> || <math>p \vee q</math> || <math>p \wedge q</math> || <math>\neg(p\vee q)</math> || <math>\neg p \wedge \neg q</math> || <math>\neg(p\wedge q)</math> || <math>\neg p \vee \neg q</math>
 +
|- style="text-align: center;"
 +
| <math>\top</math> || <math>\top</math> || <math>\bot</math> || <math>\bot</math> || <math>\top</math> || <math>\top</math> || <math>\bot</math> || <math>\bot</math> || <math>\bot</math> || <math>\bot</math>
 +
|- style="text-align: center;"
 +
| <math>\top</math> || <math>\bot</math> || <math>\bot</math> || <math>\top</math> || <math>\top</math> || <math>\bot</math> || <math>\bot</math> || <math>\bot</math> || <math>\top</math> || <math>\top</math>
 +
|- style="text-align: center;"
 +
| <math>\bot</math> || <math>\top</math> || <math>\top</math> || <math>\bot</math> || <math>\top</math> || <math>\bot</math> || <math>\bot</math> || <math>\bot</math> || <math>\top</math> || <math>\top</math>
 +
|- style="text-align: center;"
 +
| <math>\bot</math> || <math>\bot</math> || <math>\top</math> || <math>\top</math> || <math>\bot</math> || <math>\bot</math> || <math>\top</math> || <math>\top</math> || <math>\top</math> || <math>\top</math>
 +
|}
 +
 +
Hence <math>\neg(p\vee q) \Longleftrightarrow \neg p \wedge \neg q</math> and <math>\neg(p\wedge q) \Longleftrightarrow \neg p \vee \neg q</math>.
  
 
{{stub}}
 
{{stub}}
 
._.
 
._.

Latest revision as of 18:53, 19 February 2022

De Morgan's Laws are two very important laws in the fields of set theory and boolean algebra.

Statement

For any two mathematical statements $p$ and $q$, $\neg(p\vee q) \Longleftrightarrow \neg p \wedge \neg q$. The dual of this statement is also true, that is, $\neg(p\wedge q) \Longleftrightarrow \neg p \vee \neg q$. Also, for any two sets $A$ and $B$, $\overline{A\cup B} = \overline A \cap \overline B$. Again, the dual is true, for $\overline{A\cap B} = \overline A \cup \overline B$.

In fact, all dual operators will interchange upon negation. So we can also say that for any proposition P, $\neg\forall x \: P(x) \equiv \exists x \:\neg P(x)$, because $\forall$ is dual with $\exists$. Also, $\neg\exists x \:P(x) \equiv \forall x \:\neg P(x)$.

Proof

Any two propositions $p$ and $q$ have four possible combinations of truth values. We can therefore prove that two propositions stated in terms of $p$ and $q$ are equivalent by proving that they hold the same value in each of the four cases.

In the following truth table, $\top$ indicates "true" and $\bot$ indicates "false".

$p$ $q$ $\neg p$ $\neg q$ $p \vee q$ $p \wedge q$ $\neg(p\vee q)$ $\neg p \wedge \neg q$ $\neg(p\wedge q)$ $\neg p \vee \neg q$
$\top$ $\top$ $\bot$ $\bot$ $\top$ $\top$ $\bot$ $\bot$ $\bot$ $\bot$
$\top$ $\bot$ $\bot$ $\top$ $\top$ $\bot$ $\bot$ $\bot$ $\top$ $\top$
$\bot$ $\top$ $\top$ $\bot$ $\top$ $\bot$ $\bot$ $\bot$ $\top$ $\top$
$\bot$ $\bot$ $\top$ $\top$ $\bot$ $\bot$ $\top$ $\top$ $\top$ $\top$

Hence $\neg(p\vee q) \Longleftrightarrow \neg p \wedge \neg q$ and $\neg(p\wedge q) \Longleftrightarrow \neg p \vee \neg q$.

This article is a stub. Help us out by expanding it. ._.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=De_Morgan%27s_Laws&oldid=171604"