L0 Introduction
Main Course Topics
- Propositional Logic
- Sets, First-Order Logic
- Methods of Proofs
- Mathematical Induction
- Recursion
- Greatest Common Divisors
- Modular Arthmetic
- Chinese Remainder Theorem
- Graphs
- Graph Matching
- Graph Coloring
- Combinatorial Proofs and its Principles
- Counting by Mapping
- Cardinality
L1 Propositional Logic
Statement (Proposition)
A Statement is a sentence that is either True or False.
e.g. $2+2=4 \rightarrow \text{True}$
Non e.g. $x+y>0$, cause they are true for some values of $x$ and $y$, but false for others.
Logic Operators
NOT $\lnot$
Alternative notation: $\lnot P = \overline{P}$
| $P$ | $\lnot P$ |
|---|---|
| T | F |
| F | T |
AND $\land$
| $P$ | $Q$ | $P\land Q$ |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
OR $\lor$
| $P$ | $Q$ | $P\lor Q$ |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
XOR $\oplus$
Exclusive OR
| $P$ | $Q$ | $P\oplus Q$ |
|---|---|---|
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
De Morgan's Laws
Logical Equivalence: Two statements have the same truth table.
De Morgan's Laws:
$$ \lnot (P \land Q) \equiv \lnot P \lor \lnot Q $$ $$ \lnot (P \lor Q) \equiv \lnot P \land \lnot Q $$
Tautology and Contradiction
A tautology is a statement that is always true.
- e.g. $P \lor \lnot P$
A contradiction is a statement that is always false. (Negation of a tautology)
- e.g. $P \land \lnot P$
Conditinal Statement
If $\rightarrow$
If P then Q: $P \rightarrow Q \equiv \lnot P \lor Q$
| $P$ | $Q$ | $P \rightarrow Q$ |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
Convention: If we don't say anything wrong, then it is not false, and thus true.
Negation of If-Then: $\lnot(P \rightarrow Q) \equiv P \land \lnot Q$
Contrapositive: The contrapositive of $P \rightarrow Q$ is $\lnot Q \rightarrow \lnot P$
$$ P \rightarrow Q \equiv \lnot P \lor Q \equiv Q \lor \lnot P \equiv \lnot Q \rightarrow \lnot P $$
If and Only If $\iff$
P if Q means "if Q then P", or "Q implies P". We also say Q is a sufficient condition for P.
P only if Q means "if P then Q", or "P implies Q". We also say Q is a necessary condition for P.
P if and only if (iff) Q means P and Q are logically equivalent.
| $P$ | $Q$ | $P \iff Q$ |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
$$ P \iff Q \equiv (P \rightarrow Q) \land (Q \rightarrow P) \equiv (P \rightarrow Q) \land (\lnot P \rightarrow \lnot Q) $$
Argument
An argument is a sequence of statements.
All statements but the final one are called assumptions or hypothesis.
The final statement is called the conclusion.
An argument is valid if: whenever all the assumptions are true, then the conclusion is true. Or we say the conclusion follows from the assumptions.