15.2 Boolean Algebra and Logic Circuits

# Boolean algebra

- **Double Complement:** 
  $$
  \overline{\overline{\text{A}}}=A
  $$

- **Tautology/Identity Law:**
  $$
  1.A=A
  $$

$$
  0 + A = A
  $$

- **Tautology/Null Law:**
  $$
  0.A = 0
  $$

$$
  1 + A = 1
  $$

- **Tautology/Idempotent Law：**
  $$
  A.A = A
  $$

$$
  A + A = A
  $$

- **Tautology/Inverse Law:**
  $$
  A.\overline{\text{A}} = 0
  $$

$$
  A + \overline{\text{A}} = 1
  $$

- **Commutative Law:**
  $$
  A + B = B + A
  $$

$$
  A.B = B.A
  $$

- **Associative Law:**
  $$
  A + (B + C) = (A + B) + C
  $$

$$
  A.(B.C) = (A.B).C
  $$

- **Distributive Law:**
  $$
  A.(B + C) = A.B + A.C
  $$

$$
  A + (B.C) = (A + B).(A + C)
  $$

- **Adsorption Law:**
  $$
  A.(A + B) = A
  $$

$$
  A + A.B = A
  $$

$$
  A + \overline{\text{A}}.B = A +B
  $$

- **De Morgan’s Law:**
  $$
  \overline{\text{A.B}} = \overline{\text{A}} + \overline{\text{B}}
  $$

$$
  \overline{\text{(A + B)}} = \overline{\text{A}}.\overline{\text{B}}
  $$

# Further logic circuits

## Half adder

One of the basic operations in any computer is binary addition. The half adder circuit is the simplest circuit. This carries binary addition on 2 bits generating two outputs

» the sum bit (S)  » the carry bit (C).
![image.png](https://doc.tiegg.com/media/202504/d243713291724e5783422c72225fa2ef9554.png)

## Full adder

- join two half adders together to form a full adder
![image.png](https://doc.tiegg.com/media/202504/f5b3f380aa4948c2bceec4d645e66ec46477.png)

# Flip-Flops

##### The purpose of a flip-flop

To store a binary digit / (single) bit.

## SR flip-flops
![image.png](https://doc.tiegg.com/media/202504/d7d30c354f8d4887933ee6b89bc055836556.png)

## JK flip-flops

- JK flip flops are an improvement over SR flip flops.
- Invalid input combinations are eliminated in JK flip flops.
- All four combinations of input values (J and K) are valid in JK flip-flops.
- JK flip flops use a clock pulse for synchronization to ensure proper functioning.
- Advantages of JK flip flops include the validity of all input combinations, avoidance of unstable states, and increased stability compared to SR flip flops.
![截屏2025-04-28 12.59.16.png](https://doc.tiegg.com/media/202504/f8a9427c6cc44eed855ca707453487fe4146.png)

### Use of JK flip-flops

- Several JK flip-flops can be used to produce shift registers in a computer.
- A simple binary counter can be made by linking up several JK flip-flop circuits (this requires the toggle function).

# Karnaugh Maps

- **Karnaugh maps:** a method of obtaining a Boolean algebra expression from a truth table involving the
- Benefits of using Karnaugh Maps:
  - Minimises the number of Boolean expressions.
  - Minimises the number of Logic Gates used, thus providing a more efficient circuit.
- Methodology
  - Try to look for trends in the output, thus predicting the presence of a term in the final expression
  - Draw out a Karnaugh Map by filling in the truth table values into the table
  - Column labeling follows the Gray coding sequence
  - Select groups of ‘1’ bits in even quantities (2, 4, 6, etc.); if not possible, then consider a single input as a group
  - Note: Karnaugh Maps wrap around columns
  - Within each group, only the values that remain constant are retained

Summary of Grouping Rules

- A group must only contain 1s, no 0s
- A group can only be horizontal or vertical, not diagonal A group must contain 2' 1s (1, 2, 4, 8, etc.)
- Each group should be as large as possible
- Groups may overlap
- Groups may wrap around a table
- Every 1 must be in at least one group
- There should be as few groups as possible

**Examples**

![](/uploads/Theo/image-20240417141853036.png)

![](/uploads/Theo/image-20240417141900082.png)

![](/uploads/Theo/image-20240417141906498.png)

![](/uploads/Theo/image-20240417141913084.png)

![](/uploads/Theo/image-20240417141919030.png)