SLR15 - Boolean algebra

Rules of simplifying Karnaugh maps

• Boxes must be rectangles or squares

• No diagonal boxes

• Boxes must be as large as possible

• Boxes of 2ⁿ

• Boxes can overlap

How to determine simplified expression from boxes?

• Take each box in any order

• Take each variable in any order

• If digit in heading stay same, keep variable

• If digit in heading change, discard variable

De Morgan’s first law

NOT(A AND B) ≡ NOT A OR NOT B

De Morgan’s second law

NOT(A OR B) ≡ (NOT A) AND ( NOT B)

Association rule

• A V (B V C) ≡ A V B V C

• A Ʌ (B Ʌ C) ≡ A Ʌ B Ʌ C

Communication rule

A V B ≡ B V A

A Ʌ B ≡ B Ʌ A

Distribution

A Ʌ (B V C) ≡ (A Ʌ B) V (A Ʌ C)

A V (B Ʌ C) ≡ (A V B) V (A V C)

Absorpiton

A V (A Ʌ B) ≡ A

A Ʌ (A V B) ≡ A

Half adder

Full adder

D-type flip flop

• 1-bit memory device that is enabled & disabled by clock signal

• Output is only changed during clock’s rising edge