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

University of Michigan - Ann Arbor

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)

http://people.math.gatech.edu/~ecroot/2406_2012/basic_logic.pdf

Propositional Equivalences Worksheet

- $$\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)

You can simplify logic circuits using the logical identities

Simplifying Logic Circuits using Logic Identities

- 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)

Contrapositive Law (logic)

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

Learn Before

Related