HackMD - Collaborative Markdown Knowledge Base

## Tutorial：Propositional Equivalence    TA: John, ZHANG ZIHAO(mc05374@um.edu.mo) Teacher: Prof. XU   *2021.9.3* CISC1002 Discrete Structure   ###### [Online link](https://hackmd.io/@zihol/cisc1002_01) --- ### Agenda 1. Brief review of the content in the lecture 2. Practice 3. Assignment Policy and Release 4. Some Remarks   *Q&A panel is open for any time* --- ### Brief review of the content in lecture + Propositional Logic + Propositional Equivalences ---- #### Terms Proposition, compound propositions, conjunction, dis-conjunction, negation, truth table, only if, if and only if, tautology, contradiction, contingency, logical equivalence, --- #### Propositional Logic $\wedge$ Conjunction/And $\vee$ Disconjuntion/Or(inclusive or) $\oplus$ Exclusive or ---- $p \oplus q$ Truth Table | p | q | exclusice-or | | ------ | ------ | ------| | T | T | F | | T | F | T | | F | T | T | | F | F | F | ---- $p \to q$ Truth Table | p | q | Conditional Statements | | ------ | ------ | ------| | T | T | T | | T | F | F | | F | T | T | | F | F | T | ---- + CONVERSE, CONTRAPOSITIVE, AND INVERSE + Precedence of Logical Operators negation > And > Or > implication --- #### Propositional Equivalences  *Table 6, page 27*   Identity laws $$ p \wedge \textbf{T} \equiv p \\ p \vee \textbf{F} \equiv p $$ Domination laws $$ p \vee \textbf{T} \equiv \textbf{T} \\ p \wedge \textbf{F} \equiv \textbf{F} $$ ----  Idempotent laws $$ p \wedge p \equiv p \\ p \vee p \equiv p $$ Double negation law $$ \neg(\neg P) \equiv p $$ Commutative laws $$ p \vee q \equiv q \vee p \\ p \wedge q \equiv q \wedge p $$ ----  Associative laws $$ (p \wedge q)\wedge r \equiv p \wedge (q \wedge r) \\ (p \vee q)\vee r \equiv p \vee (q \vee r) $$ Distributive laws $$ (p \vee r) \wedge (q \vee r) \equiv ( p \wedge q ) \vee r \\ (p \wedge r) \vee (q \wedge r) \equiv ( p \vee q ) \wedge r $$ De Morgan's laws $$ \neg ( p \wedge q ) \equiv (\neg p) \vee (\neg q) \\\neg ( p \vee q ) \equiv (\neg p) \wedge (\neg q) $$ ----  Absorption laws $$ p \vee (p \wedge q) \equiv p \\p \wedge (p \vee q) \equiv p $$ Negation laws $$ p \vee \neg p \equiv \textbf{T} \\ p \wedge \neg p \equiv \textbf{F} $$ --- ### Practice (a) $$ (p \wedge q) \to p $$ | p | q | $p \wedge q$ | $(p \wedge q) \to p$ | | --- | --- | --- | --- | | T | T | T | T | | T | F | F | T | | F | T | F | T | | F | F | F | T | $$ p \to (p \vee q) $$ | p | q | $p \vee q$ | $p \to (p \vee q)$ | | --- | --- | --- | --- | | T | T | T | T | | T | F | T | T | | F | T | T | T | | F | F | F | T | $$ \neg p \to (p \to q) $$ $$ (p \wedge q) \to (p \to q) $$ $$ \neg(p \to q) \to p $$ $$ \neg(p \to q) \to \neg p $$ | p | q | $p \to q$ | $\neg (p \to q)$ | $\neg p$ | $\neg(p \to q) \to \neg p$ | | --- | --- | --- | --- | --- | --- | | T | T | T | F | F | T | | T | F | F | T | F | T | | F | T | T | F | T | T | | F | F | T | F | T | T | $$ p \leftrightarrows q \\ (p \wedge q) \vee (\neg p \wedge \neg q) $$ | p | q | $p \leftrightarrows q$ | | --- | --- | --- | | T | T | T | | T | F | F | | F | T | F | | F | F | T | | p | q | ($p \wedge q$) | --- ### Assignment Policy and Release --- ### Appedix: Common Latex symbol  | Symbol | Meaning | Latex | | ------ | ------ | ------| | $\neg p \qquad \bar{p}$ | negation/not | \neg p \qquad \bar{p} | | $\wedge$ | conjunction | \wedge or \land| | $\vee$ | disjunction | \vee or \lor | | $\oplus$ | exclusive/or | \oplus | | $\to$ | implication | \rightarrow or \to | | $\leftrightarrow$ | negation/not | \leftrightarrow | | $\equiv$ | logically equivalent | \equiv | ----  (Cont.) | Symbol | Meaning | Latex | | ------ | ------ | ------| | $\gets$ | B if A | \leftarrow or \gets | | $\longrightarrow$ | ... | \longrightarrow | | $\in$ | in | \in | | $\notin$ | not in | \notin | | $\forall$ | universal quantifier | \forall | | $\exists$ | existential quantifier | \exists | | $\because \qquad \therefore$ | because therefore | \because \therefore | ----  (Cont.) | Symbol | Meaning | Latex | | ------ | ------ | ------| | $\cup$ | Union | \cup | | $\cap$ | Intersection | \cap | | $\overline{Subtraction}$ | Subtraction | \overline{Subtraction} | | $\subset$ | subset | \subset | | $\subseteq$ | true subset | \subseteq | | $\emptyset$ | empty set | \emptyset | --- ## Thank you ... ###### tags: `cisc1002`