Numerical Systems

Introduction Positional Notation Converting Between Bases Binary Addition Binary Multiplication Challenges (Python) Challenges (Java)

Modular Arithmatic

Introduction The Modulus Operator Cyphers Modular Arithmetic Modular Inverse Challenges (Java)

Algorithms

Introduction Algorithms Time Functions Asymptotic Complexity Summation Challenges

Propositional Logic

Introduction Propositional Logic Conjunction and Disjunction Implication and Equivalence Bitwise Operators Challenges

Set Theory

Introduction Sets Subsets and Supersets Set Operations Challenges

Graph Theory

Introduction Graphs Directed Graphs Structure of Language Search Trees Neural networks Game Object Trees Challenges Graph Question Generator

Proof

Introduction Proof Proof by Cases Proof by Contradiction Proof by Induction Challenges

Maths to Code

Maths to Code Challenges Question Generator

Descriptive Statistics

Introduction Statistics Measures of Central Tendency Measures of Spread Data Visualisation Correlation Challenges

Probability

Introduction Probability Basics Combinatorics Probability Trees Law of Total Probability Bayes Rule Challenges

Inferential Statistics

Introduction Probability Distributions Samples and Populations Hypothesis Testing Z Scores Student's T-Test Challenges

De Morgan's Laws

De Morgan’s laws are a set of laws in logic, set theory, and other branches of mathematics. They allow us to write conjunction and disjunction, or set union and set intersection, solely is terms of the other. Basically, that “not dogs and cats” is the same as “not dogs or not cats”. We will look at these laws in Set Theory.

Watch the video and then answer the questions below.

Video not yet available

Key Points

DeMorgans laws can be expressed in English as:

the complement of the union of two sets is the same as the intersection of their complements; and
the complement of the intersection of two sets is the same as the union of their complements.

They can be written formally in set theory as follows:

\[ (A \cap B)^C = A^C \cup B^C \]

\[ (A \cup B)^C = A^C \cap B^C \]

De Morgans Laws in Propositional Logic

The same laws can be expressed in propositional logic

Conjunction can be expressed using negation and disjunction.
Disjunction can be expressed using negation and conjunction.

\[ \neg (P \wedge Q) \iff \neg P \vee \neg Q \]

\[ \neg (P \vee Q) \iff \neg P \wedge \neg Q \]

Questions

1. Check your knowledge

Set example for De Morgan’s Laws

Use the sets A and B with the Universe set U.

A = { 1, 2, 3, 4 }
B =       { 3, 4, 5, 6 }
U = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }

(A ∪ B)^c {}
A^c ∩ B^c {}
(A ∩ B)^c {}
A^c ∪ B^c {}

Check Answers

Truth tables for De Morgan’s Laws

p	q	¬(p∧q)	¬p ∨ ¬q)
T	T
T	F
F	T
F	F

p	q	¬(p∨q)	¬p ∧ ¬q)
T	T
T	F
F	T
F	F