Logic - 4

COMP109 Lectures 2020-12-03

Digital Logic Circuits

In Series

This circuit produces similar results to an AND gate:

In Parallel

This circuit produces similar results to an OR gate:

Modern computers use logic gates.

Basic Logic Gates

AND Gate

$P$	$Q$	$R$
1	1	1
1	0	0
0	1	0
0	0	0

OR Gate

$P$	$Q$	$R$
1	1	1
1	0	1
0	1	1
0	0	0

NOT Gate

$P$	$R$
1	0
0	1

Rules for a Combinatorial Circuit

• Never combine two input wires.
• A single input wire can be split partway and used as input for two separate gates.
• An output wire can be used as input.
• No output of a gate can eventually feed back into that gate.

There are some additional examples in the video that I haven’t covered here as they are very logical.

Multi-Input Gates

If you want to and together multiple values you can either use a multi-input package or string together a multi-gate package. Here are two equivalent diagrams:

Designing a Circuit for a Given Input/Output Table

Say you have the following table of inputs and outputs you want to have in a circuit:

Input	Input	Input	Output
P	Q	R	S
1	1	1	1
1	1	0	1
1	0	1	1
1	0	0	0
0	1	1	0
0	1	0	0
0	0	1	0
0	0	0	0

1. View all the lines where the output is given.
2. From these construct a formulas with all inputs where the output is satisfied AND-ed together.
3. OR all these atoms together.

This will give you:

\[(P\wedge Q \wedge R)\vee(P\wedge\neg Q\wedge R)\vee(P\wedge Q\wedge\neg R)\]

This is the disjunctive normal form (DNF).

You can then convert this into a circuit diagram:

This formula and diagram can be simplified to give the following:

\[P\wedge (Q\vee R)\]

You can see this from investigating the table.

Circuit Equivalence

Two circuits are equivalent if they produce the same output given the same input.

Logical Equivalence

Two formulas $P$ and $Q$ are called equivalent if they have the same truth value under every possible interpretation. In other words, $P$ and $Q$Q are equivalent if $I(p)=I(Q)$ for every interpretation $I$. This is denoted by:

\[P\equiv Q\]

Theorem

The relation $\equiv$ is an equivalence relation on $\mathcal{P}$.

Proof

• $\equiv$ is reflexive, since, trivially, $I(P)=I(P)$ for every interpretation $I$.
• $\equiv$ is transitive, since $P\equiv Q$ and $Q\equiv R$ implies $P\equiv R$.
• $\equiv$ is symmetric, since $P\equiv Q$ implies $Q\equiv P$.

Useful Equivalences

Associative Laws

\(\begin{aligned} (P\vee (Q\vee R))&\equiv((P\vee Q)\vee R)\\ (P\wedge (Q\wedge R))&\equiv((P\wedge Q)\wedge R) \end{aligned}\)

Commutative Laws

\(\begin{aligned} (P\vee Q)&\equiv (Q\vee P)\\ (P\wedge Q)&\equiv (Q\wedge P) \end{aligned}\)

Identity Laws

\(\begin{aligned} (P\vee\bot)&\equiv P\\ (P\vee\top)&\equiv \top\\ (P\wedge\top)&\equiv P\\ (P\wedge\bot)&\equiv \bot \end{aligned}\)

Distributive Laws

\(\begin{aligned} (P\wedge(Q\vee R))&\equiv((P\wedge Q)\vee(P\wedge R))\\ (P\vee(Q\wedge R))&\equiv((P\vee Q)\wedge(P\vee R)) \end{aligned}\)

Complement Laws

\(\begin{aligned} P\vee\neg P&\equiv\top\\ \neg\top&\equiv\bot\\ \neg\neg P&\equiv P\\ P\wedge\neg P&\equiv\bot\\ \neg\bot&\equiv\top \end{aligned}\)

De Morgan’s Laws

\(\begin{aligned} \neg(P\vee Q)&\equiv(\neg P\wedge \neg Q)\\ \neg(P\wedge Q)&\equiv(\neg P\vee \neg Q) \end{aligned}\)