You can simplify logic circuits using the logical identities

University of Michigan - Ann Arbor

A circuit through which the wires carry T/F values and the gates hold logical operations (and : $$\land$$  ;  or : $$\lor$$  ;  not : $$\lnot$$  ;  etc.) .

You should ask:
- What is the circuit doing?
- Can it be simplified?

Logic Circuits

Using truth tables on large propositions would be very time consuming and difficult. This is why it is better to use logical identities which you can use to prove equivalences. They include:
- Distributive laws
- De Morgan's laws
- Associative laws
- Commutative  laws
- Double-negation law
- Identity laws
- Domination laws
- Idempotent Laws
- Implication laws
- Contrapositive law

Logical Identities (proving logical equivalences)

University of Michigan EECS 203 Lecture Notes

- $$\lnot$$ (p $$\land$$ q) $$\equiv$$ $$\lnot$$ p $$\lor$$ $$\lnot$$ q
- $$\lnot$$ (p $$\lor$$ q) $$\equiv$$ $$\lnot$$ p $$\land$$ $$\lnot$$ q

De Morgan's Laws (negating 'and' and 'or')

- p $$\lor$$ q $$\equiv$$ q $$\lor$$ p
- p $$\land$$ q $$\equiv$$ q $$\land$$ p

Commutative laws (logic)

- p $$\lor$$ (q $$\land$$ r) $$\equiv$$ (p $$\lor$$ q) $$\land$$ (p $$\lor$$ r)

- p $$\land$$ (q $$\lor$$ r) $$\equiv$$ (p $$\land$$ q) $$\lor$$ (p $$\land$$ r)

Distributive laws (logic)

Do you have paypal, or cash or a credit card?  
Do you have paypal or cash, or a credit card?
- p $$\lor$$ (q  $$\lor$$ r) $$\equiv$$ (p $$\lor$$ q) $$\lor$$ r

Do you have a jacket, umbrella and boots?  
Do you have a jacket and umbrella, and boots?
- p $$\land$$ (q $$\land$$ r) $$\equiv$$ (p $$\land$$ q) $$\land$$ r

Associative laws (logic)

- p $$\lor$$ FALSE $$\equiv$$ p
- p $$\land$$ TRUE $$\equiv$$ p

Identity laws (logic)

Double-negation law (logic)

- p $$\land$$ FALSE $$\equiv$$ FALSE
- p $$\lor$$ TRUE $$\equiv$$ TRUE

Domination laws (logic)

p $$\lor$$ p $$\equiv$$ p
p $$\land$$ p $$\equiv$$ p

Idempotent Laws (logic)

p $$\rightarrow$$ q $$\equiv$$ $$\lnot$$ p $$\rightarrow$$ $$\lnot$$ q

Contrapositive Law (logic)

(p $$\rightarrow$$ q) $$\equiv$$ ($$\lnot$$ p $$\lor$$ q)

Learn Before

Related