22-7-25 - Lecture

This unit is pure mathematics

Course Outline

Assessments

Assessment	Value	Date
Quiz	25%	Week 5 Lecture
Quiz	25%	Week 11 Lecture
Exam	50%	Exam period

Propositional Logic

Symbols

$\wedge$ - AND (\wedge)
$\vee$ - OR (\vee)
$\oplus$ - XOR (\oplus)
$\neg$ - NOT (\neg)
$\to$ - Implies (\to or \rightarrow)
$\leftrightarrow$ - Biconditional (\leftrightarrow)
$\equiv$ - Equivalent (\equiv)
$\iff$ - Biconditional or equivalent (\Leftrightarrow)

Precedence

See slide 29 from Lecture 1.

Truth Tables

E.g. XOR table

p	q	$p\oplus q$
T	T	F
T	F	T
F	T	T
F	F	F

Terminology

Tautology - proposition that is always true
Contradiction - proposition that is always false
Contingency - proposition that can be true or false

Common Logical Equivalence

De Morgan’s laws
$\neg (p\wedge q)\iff \neg p\vee \neg q$
$\neg (p\vee q)\iff \neg p\wedge \neg q$
Commutative
$p\wedge q\iff q\wedge p$
$p\vee q\iff q\vee p$
Associative
$(p\wedge q)\wedge r\iff p\wedge (q\wedge r)$
$(p\vee q)\vee r\iff p\vee (q\vee r)$
Distributive
$p\wedge (q\vee r)\iff (p\wedge q)\vee (p\wedge r)$
$p\vee (q\wedge r)\iff (p\vee q)\wedge (p\vee r)$

t is tautology, c is contradiction
Identity
$p\wedge t\iff p$
$p\vee c\iff p$
Universal Bound
$p\vee t\iff t$
$p\wedge c<=>c$
Negation
$p\wedge \neg p\iff c$
$p\vee \neg p\iff t$
Double Negation
$\neg (\neg p)\iff p$
Idempotent
$p\wedge p\iff p$
$p\vee p\iff p$
Absorption
$p\vee (p\wedge q)\iff p$
$p\wedge (p\vee q)\iff p$