IT221 Discrete Math

Example

\[if\ \underbrace{x\ equals\ 2}_{\underbrace{x=2}_Q}\ \underbrace{or}_{\lor}\ \underbrace{x\ equals -2}_{\underbrace{x=-2}_{R}},\ \underbrace{then}_{\therefore}\ \underbrace{x^2 \ equal\ 4}_{\underbrace{x^2 = 4}_{S}}\]

\[Q \lor R\ \therefore\ S\] \[Q \lor R \rightarrow S\]

Variations

\[\neg Q \land \neg R \therefore \neg S\]

\[\neg Q \land \neg R \rightarrow \neg S\]

\[(x \ne 2) \land (x\ne -2) \therefore (x^2 \ne 4)\]

Slide 1-2

Slide 3-4

Slide 5-6

Slide 7-8

Slide 9-10

Slide 11-12

Slide 13

Example 1

Original Expressiom

\[\neg (A \land B) \land (B \lor C)\]

Solution

\[\small\eqalign{ \neg (A \land B) \land (B \lor C)\\ \\ (\neg A \lor \neg B) \land (B \lor C)\\ \\ (\neg A\land B) \lor (\neg A \land C) \lor (\neg B \land B) \lor (\neg B \land C)\\ \\ (\neg A\land B) \lor (\neg A \land C) \lor (\neg B \land C)\\ \\ \neg A\land (B \lor C) \lor (\neg B \land C)\\ }\]

Example 2

Original Expressiom

\[(A \lor B) \land (B \lor C)\]

Solution

\[\small\eqalign{(A \lor B) \land (B \lor C)\\ \\ (A\land B) \lor (A \land C) \lor (B \land B) \lor (B\land C)\\ \\ (A\land B) \lor (A \land C) \lor B \lor (B\land C)\\ \\ (A\land B) \lor (A \land C) \lor B \land ( 1 \lor C)\\ \\ (A \land C) \lor B\land (B \lor A)\\ \\ (A \land C) \lor B\land (1 \lor A)\\ \\ (A \land C) \lor B\\ }\]

Example 3

Original expression

\[\small\neg(\neg A\land (B\lor \neg C))\land(A\lor\neg B\lor C)\land\neg(\neg A\land\neg B\land \neg C)\]

Solution

\[\small\eqalign{\neg(\neg A\land (B\lor \neg C))\land(A\lor\neg B\lor C)\land\neg(\neg A\land\neg B\land \neg C)\\ \\ \neg(\neg A\land (B\lor \neg C))\land(A\lor\neg B\lor C)\land(\neg\neg A\lor\neg\neg B\lor \neg\neg C)\\ \\ \neg(\neg A\land (B\lor \neg C))\land(A\lor\neg B\lor C)\land(A\lor B\lor C)\\ \\ (\neg\neg A\lor \neg(B\lor \neg C))\land(A\lor\neg B\lor C)\land(A\lor B\lor C)\\ \\ (A\lor \neg(B\lor \neg C))\land(A\lor\neg B\lor C)\land(A\lor B\lor C)\\ \\ (A\lor (\neg B\land \neg\neg C))\land(A\lor\neg B\lor C)\land(A\lor B\lor C)\\ \\ (A\lor (\neg B\land C))\land(A\lor\neg B\lor C)\land(A\lor B\lor C)\\ \\ (A\lor (\neg B\land C))\land [(A \land A) \lor (A\land B) \lor (A\land C)\lor\\ (\neg B\land A) \lor (\neg B\land B)\lor (\neg B\land C)\lor\\ (C\land A)\lor (C\land B)\lor(C\land C)]\\ \\ (A\lor (\neg B\land C))\land [A\lor (A\land B) \lor (A\land C)\lor\\ (\neg B\land A) \lor (\neg B\land C)\lor\\ (B\land C)\lor C]\\ \\ (A\lor (\neg B\land C))\land [A\land (1\lor B \lor C \lor \neg B) \lor\\ (\neg B\land C)\lor (B\land C)\lor C]\\ \\ (A\lor (\neg B\land C))\land [A \lor\\ C\land (\neg B\lor B\lor 1)]\\ \\ (A\lor (\neg B\land C))\land (A \lor C)\\ \\ (A\land A)\lor (A\land C) \lor (A\land \neg B\land C) \lor (\neg B\land C\land C)\\ \\ (A)\lor (A\land C) \lor (A\land \neg B\land C) \lor (\neg B\land C)\\ \\ A\land(1\lor C \lor \neg B\land C) \lor (\neg B\land C)\\ \\ A \lor (\neg B\land C)\\ \\ }\]

Homework Assignment

Simplify the following expressions:

Expression 1:

\[ \neg\ ((\neg A \land \neg B) \lor (A \land B)) \]

Expression 2:

\[ \neg\ (A \land (B + C)) \lor (\neg A \land B) \lor (\neg C\land \neg(A+B)) \] Expression 3:

\[ (A \lor B)\land (B\lor C) \]

Expression 4:

\[ \neg((\neg A \land \neg B) \lor (A \land B)) \] Expression 5:

\[ \neg(A\lor (B\lor C))\lor (\neg A \land B) \lor (\neg C\land \neg(A \lor B)) \]

Precedence

\[\matrix{Operator & Precedence\\ \neg & 1 \\ \land & 2\\ \lor & 3 \\ \rightarrow & 4\\ \leftrightarrow & 5\\ }\]

\[\neg p \land q \equiv (\neg p) \land q\]

\[\neg p \land q \not\equiv \neg (p \land q)\]