fuck this shit

Boolean Logic 254261 Computer ArchitectureWansuree Massagram, Ph.D.Department of Computer Science and IT

Outline• Boolean values• Boolean operations• Boolean expressions• Boolean laws• Boolean algebra• Boolean function synthesis• TheoremW. Massagram 254261 2

Boolean Values OFF ON Binary FTW. Massagram NY 3 01 254261

Boolean Operations• Basic: AND, OR, NOT• Derived: NAND, NOR, XOR, XNORW. Massagram 254261 4

AND x y AND 000 ������ AND ������ 010 ������ ∧ ������ 100 ������ ⋅ ������ 111 ������ ∩ ������W. Massagram 254261 5

OR x y OR 000 ������ OR ������ 011 ������ ∨ ������ 101 ������ + ������ 111 ������ ∪ ������W. Massagram 254261 6

NOT x NOT 01 NOT x 10 ¬������ ������′ ������̅W. Massagram 254261 7

NAND, NOR, XOR, XNOR NAND NOR XOR XNOR xy ������ ⋅ ������ ������ + ������ ������ ⊕ ������ ������ ⊕ ������ 001101 011010 101010 110001W. Massagram 254261 8

Boolean Expressions 0 + 1 ⋅ 1 = 0 + 1 = 1� = 0W. Massagram 254261 9

Boolean Functions������ ������, ������, ������ = ������ ⋅ ������ + ������̅ ⋅ ������ Formula xyz f Truth table 0000 0011 0100 0111 1000 1010 1101 1111W. Massagram 254261 10

Boolean LawsW. Massagram 254261 11

Law Formula 12Commutative ������ ⋅ ������ = ������ ⋅ ������Associative ������ + ������ = ������ + ������ ������ ⋅ ������ ⋅ ������ = ������ ⋅ ������ ⋅ ������Distributive ������ + ������ + ������ = ������ + ������ + ������ ������ ⋅ ������ + ������ = ������ ⋅ ������ + ������ ⋅ ������Identity ������ + ������ ⋅ ������ = ������ + ������ ⋅ ������ + ������Idempotence ������ ⋅ 1 = ������ ������ + 0 = ������Absorption ������ ⋅ ������ = ������ ������ + ������ = ������Complementation ������ ⋅ ������ + ������ = ������Double negation ������ + ������ ⋅ ������ = ������De Morgan ������ ⋅ ������̅ = 0 ������ + ������̅ = 1W. Massagram ������̿ = ������ ������ ⋅ ������ = ������̅ + ������� 254261 ������ + ������ = ������̅ ⋅ �������

Boolean Algebra ������̅ ⋅ ������ + ������ =?W. Massagram 254261 13

Boolean Algebra������̅ ⋅ ������ + ������ =? y f 0 0 x 1 1 0 0 1 0 1 1 1 1 ������ + ������W. Massagram 254261 14

Boolean Function Synthesis• Boolean expression to truth table ������ ������, ������, ������ = ������ ⋅ ������ + (������̅ ⋅ ������) xyz f 0000 0011 0100 0111 1000 1010 1101 1111W. Massagram 254261 15

Boolean Function Synthesis• truth table to Boolean expressionW. Massagram xyz f 16 0000 0011 0100 0111 1000 1010 1101 1111 254261

Truth Table to Boolean Expression xyz f 0000 0 0 1 1 ������̅ ⋅ ������� ⋅ ������ 0100 0 1 1 1 ������̅ ⋅ ������ ⋅ ������ 1000 1010 1 1 0 1 ������ ⋅ ������ ⋅ ������̅ 1 1 1 1 ������ ⋅ ������ ⋅ ������������̅ ⋅ ������� ⋅ ������ + ������̅ ⋅ ������ ⋅ ������ + ������ ⋅ ������ ⋅ ������̅ + ������ ⋅ ������ ⋅ ������ Sum of ProductsW. Massagram 254261 17

Truth Table to Boolean Expression ������ ������, ������, ������ = ������ ⋅ ������ + (������̅ ⋅ ������)W. Massagram xyz f 18 0000 0011 0100 0111 1000 1010 1101 1111 254261

Theorem“Any Boolean function can be represented usingand expression containing AND, OR, and NOToperations.”Proof: ������ + ������ = ������̅ ⋅ �������W. Massagram 254261 19

NAND Q X 1 Y XY 1 00 1 01 0 10 11������ NAND ������ = ������ ⋅ ������W. Massagram 254261 20

Theorem“Any Boolean function can be represented usingand expression containing NAND operations.”Proof: ������ + ������ = ������ ⋅ ������ ⋅ ������ ⋅ ������W. Massagram 254261 21