# Discussion 0A

• OH: Th 3 to 4pm in Soda 651
• Discussion: TuTh 5 to 6pm in Dwinelle 105
• Logistics: Piazza and sp19@eecs70.org

# Review

## Propositional Logic

• proposition: statement that evaluates to true or false
• conjunction: $P \land Q$, $P \text{ and } Q$
• disjunction: $P \lor Q$, $P \text{ or } Q$
• negation: $\lnot P$, $\text{not } P$
• implication: $P \Rightarrow Q$, $\lnot P \lor Q$
• or $\text{hypothesis} \Rightarrow \text{conclusion}$
• when $P$ is false, the implication is true regardless of $Q$. this is called a vacuous statement
• given an implication $P \Rightarrow Q$
• contrapositive: $\lnot Q \Rightarrow \lnot P$
• has the same truth value: $(P \Rightarrow Q) \equiv (\lnot P \lor Q) \equiv (Q \lor \lnot P) \equiv (\lnot Q \Rightarrow \lnot P)$
• converse: $Q \Rightarrow P$
• not necessarily the same truth value
• $P \equiv Q$ means both $P \Rightarrow Q$ and $Q \Rightarrow P$

## Quantifiers

• universal quantifier: $\forall$, for all
• $\forall x P(x)$ is whether $P(x)$ evaluates to true for all values of $x$
• existential quantifier: $\exists$, there exists
• $\exists x P(x)$ is whether $P(x)$ evaluates to true for some value of $x$

## Negation

• $$\lnot (P \land Q) \equiv (\lnot P \lor \lnot Q)$$
• $$\lnot (P \lor Q) \equiv (\lnot P \land \lnot Q)$$
• $$\lnot (\forall x P(x)) \equiv \exists x \lnot P(x)$$
• $$\lnot (\exists x P(x)) \equiv \forall x \lnot P(x)$$