Loading...

​​Discussion 0A

​​Ming Li

​​mingyli@berkeley.edu

​​OH: Th 3 to 4pm in Soda 651

​​Discussion: TuTh 5 to 6pm in Dwinelle 105

​​Logistics: Piazza and sp19@eecs70.org

​​Introductions

• ​​your name

• ​​one interesting thing you did over break

• ​​one movie you are embarrassed to have not seen yet

​​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$​

• ​​when ​​$P$​ is false, the implication is true regardless of ​​$Q$​. this is called a vacuous statement

• ​​​​$\text{hypothesis} \Rightarrow \text{conclusion}$​

• ​​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)$​

​​