Unit 2: Logic
2024-07-12
AND
------- -------
------o o--------o o------
OR
-------
+---o o---+
| |
------+ +---
| ------- |
+---o o---+
Given this expression:
\[F = (A \lor B) \land (B\lor C)\] \[\eqalign{F&=& (A+B)(B+C)\\ &=&AB+AC+BB+BC\\ &=&AC +B(A+1+C)\\ &=&AC+B\\\]
Complete the chart
A | B | C | F |
---|---|---|---|
0 | 0 | 0 | 0 |
0 | 0 | 1 | 0 |
0 | 1 | 0 | 1 |
0 | 1 | 1 | 1 |
1 | 0 | 0 | 0 |
1 | 0 | 1 | 1 |
1 | 1 | 0 | 1 |
1 | 1 | 1 | 1 |
\[\eqalign{1)&A \lor \overline{A} &=& T&& && A+\overline{A} &=&1\\ 2)&A \lor {A} &=& A&& && A+A &=&A\\ 3)&A \lor F &=& A&& && A+0 &=&A\\ 4)&A \lor T &=& T&& && A+1 &=&1\\ 5)&A \land \overline{A} &=& F&& && A\cdot \overline{A} &=&0\\ 6)&A \land {A} &=& A&& && A\cdot A &=&A\\ 7)&A \land F &=& F&& && A\cdot 0 &=&0\\ 8)&A \land T &=& A&& && A\cdot 1 &=&A\\ }\]
\[\small\eqalign{9)&\quad A \land (B \lor \overline{B}) &=& A&& &&\qquad A\cdot (B + \overline{B}) &=&A\\ 10)&\qquad A \lor {A \land B}&=& A\land (T\lor B)&& &&\quad\qquad A+A\cdot B &=&A\cdot(1 + B)\\ & &=& A && && &=&A\\ 11)&\qquad\overline{A} \lor A\land B &=& \overline{A}\lor B&& &&\quad \overline{A} +A\cdot B &=&\overline{A}\\ 12)&\quad A \land (A\lor B) &=& A && && \qquad A \cdot (A + B)&=&A\\ 13)&\qquad A \lor \overline{A}\land B &=& A\lor B&& && \quad\qquad A + \overline{A}\cdot B &=& A+ B\\ 14)&\qquad\quad \overline{A\lor B} &=& \overline{A} \land \overline{B}&& && \qquad\qquad\overline{A + B} &=& \overline{A} \cdot \overline{B}\\ 15)&\qquad\quad\overline{A\land B} &=& \overline{A} \lor \overline{B}&& && \qquad\qquad\overline{A \cdot B} &=& \overline{A} + \overline{B}\\ }\]
\[\small\eqalign{16)&A \land B \lor \overline{B}\land C\lor A \land C&=& A\land B \lor \overline{B}\land C\\ & \quad A \cdot B + \overline{B}\cdot C + A \cdot C&=& A\cdot B + \overline{B}\cdot C\\}\]
Distributive law:
(A ∧ B) ∨ (C ∧ D) = (A ∨ C) ∧ (A ∨ D) ∧ (B ∨ C) ∧ (B ∨ D)
De Morgan’s law:
¬(A ∧ B) = ¬A ∨ ¬B
¬(A ∨ B) = ¬A ∧ ¬B
Commutative law:
A ∧ B = B ∧ A
A ∨ B = B ∨ A
Associative law:
(A ∧ B) ∧ C = A ∧ (B ∧ C)
(A ∨ B) ∨ C = A ∨ (B ∨ C)
Identity law:
A ∧ 1 = A
A ∨ 0 = A
Complement law:
A ∨ ¬A = 1
A ∧ ¬A = 0
\[\eqalign{F &=& ABC +\overline{A}\overline{B}\overline{C} + AB\overline{C} + \overline{A}\overline{C}\\ &=& ABC + AB\overline{C} + \overline{A}\overline{C} + \overline{A}\overline{B}\overline{C}\\ &=& AB(C + \overline{C}) + \overline{A}\overline{C}(1+\overline{B})\\ &=& AB + \overline{A}\overline{C}\\}\]
\[\eqalign{F &=& \overline{A}BC\overline{D} + \overline{A}BCD + A\overline{B}\overline{C}D +\\ && A\overline{B}CD + AB\overline{C}D + ABCD\\ &=& \overline{A}BC(\overline{D} + D) + A\overline{B}D(C+\overline{C})+\\ && ABD(C + \overline{C})\\ &=& \overline{A}BC + AD(\overline{B} + B)\\ &=&\overline{A}BC + AD\\}\]
\[\eqalign{F&=&(B+D)(C+D)(A+D)\\ &=&(BC + CD + BD + DD)(A+D)\\ &=&ABC + ABD + ACD + AD+BCD +BDD + DDD\\ &=&ABC + ABD + ACD + AD+BCD +BD + D\\ &=&ABC + D(AB +AC+ A+BC +B + 1)\\ &=&ABC+ D\\}\]
\[\tiny\begin{matrix} A&B&C&D&&ABC&&F_1&& B+D &C+D&A+D &&F_0\\ \hline 0&0&0&0&&0&&0&&0&0&0&&0\\ 0&0&0&1&&0&&1&&1&1&1&&1\\ 0&0&1&0&&0&&0&&1&0&0&&0\\ 0&0&1&1&&0&&1&&1&1&1&&1\\ 0&1&0&0&&0&&0&&0&0&0&&0\\ 0&1&0&1&&0&&1&&1&1&1&&1\\ 0&1&1&0&&0&&0&&1&0&0&&0\\ 0&1&1&1&&0&&1&&1&1&1&&1\\ 1&0&0&0&&0&&0&&0&1&0&&0\\ 1&0&0&1&&0&&1&&1&1&1&&1\\ 1&0&1&0&&0&&0&&1&1&0&&0\\ 1&0&1&1&&0&&1&&1&1&1&&1\\ 1&1&0&0&&0&&0&&0&1&0&&0\\ 1&1&0&1&&0&&1&&1&1&1&&1\\ 1&1&1&0&&1&&1&&1&1&1&&1\\ 1&1&1&1&&1&&1&&1&1&1&&1\\ \end{matrix}\]
\[\eqalign{F &=& \overline{(A+B)(\overline{A}+C)}\\ &=& \overline{(A+B)}+\overline{(\overline{A}+C)}\\ &=& \overline{A}\overline{B} +A\overline{C})\\ }\]
\[\eqalign{F&=& \overline{A\overline{B} +C}\\ &=&(\overline{A} +B)(\overline{C})\\ &=&\overline{A}\overline{C}+ B\overline C\\ &=&\overline{A}\overline{C}+ \overline{B}+ C\\}\]
\[\eqalign{F&=&(AB+\overline{C})+(\overline{A}+\overline{B})(C)\\ &=&(AB+\overline{C})+\overline{A}C+\overline{B}C\\}\]
Results are true for all combinations of input
A | B | C | A^B | !C | !AC | !BC | F |
---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 |
0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 |
1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 |
1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 |
AND/OR Gates: Requires 2 NOT, 3 AND, 1 OR gate (3 chips)
\[F= A\overline{B} + \overline{A}B\] NAND/NOR Gates: Requires 6 NAND, and 2 NOR gates (2 chips)
\[\tiny \eqalign{F &=& \hbox{nor}\left( \hbox{nor}\left( \hbox{nand}\left( \hbox{nand}\left(A, \hbox{nand}\left(B, 1\right) \right), 1\right), \hbox{nand}\left( \hbox{nand}\left(B, \hbox{nand}\left(A, 1\right) \right), 1\right) \right), 1\right)\\ &=& \left(\overline{ \left(\overline{ \left(\overline{ \left(\overline{A \cdot \left(\overline{B\cdot 1}\right) }\right)\cdot 1}\right) + \left(\overline{ \left(\overline{B\cdot \left(\overline{A\cdot 1}\right) }\right)\cdot 1}\right) }\right) + 0}\right)\\ &=& \left(A\cdot\overline{B} \right) + \left(B\cdot\overline{A} \right)\\ }\]
IT221 Discrete Math