Discrete Mathematics for Dummies


Logical Identities

Identities are used to simplify logical expressions.

P <=> P v P = indempotence of OR. A binary operation is called idempotent if, whenever it is applied to two equal values, it gives that value as the result. For example, the operation giving the maximum value of two values is idempotent: max(x, x) = x. see Wikipedia

P <=> P ^ P = indempotence of AND. Same as above for AND.

(P v Q) <=> (Q v P) = Commutativity of OR. Commutativity is the property that changing the order of something does not change the end result. see Wikipedia

(P ^ Q) <=> (Q ^ P) = Commutativity of AND. Same as above for AND.

((P v Q) v R) <=> (P  v (Q v R)) = Associativity of OR. Associativity within an expression containing two or more of the same associative operators in a row, the order that the operations are performed does not matter as long as the sequence of the operands is not changed. That is, rearranging the parentheses in such an expression will not change its value. see Wikipedia

((P ^ Q) ^ R) <=> (P  ^ (Q ^ R)) = Associativity of AND. Same as above for AND.

not(P v Q) <=> (not P ^ not Q) = De Morgans Laws. This brings the negative from outside the brackets to inside the brackets on both sides of the operator and changes the operator from OR to AND. For example if P = The Traffic lights are red, and Q = The car drives over the crossing, then P v Q = The Traffic lights are red or the car drives over to crossing. not(P OR Q) is <=> the traffic lights are not green AND the car is not driving over the crossing.  see Wikipedia

not(P ^ Q) <=> (not P v not Q) = De Morgans Laws. This brings the negative from outside the brackets to inside the brackets on both sides of the operator and changes the operator from AND to OR. See example above. see also Wikipedia

(P ^ (Q v R)) <=> ((P ^ Q) v (P ^ R)) = Distributivity of AND over OR. see Wikipedia

(P v (Q ^ R)) <=> ((P v Q) ^ (P v R)) = Distributivity of OR over AND. see Wikipedia

P <=> not(not P) = Double Negation.

(P v 1) <=> 1

(P ^ 1) <=> P

(P v 0) <=> P

(P ^ 0) <=> 0

(P ^ not P) = 0  This is a Contradiction

(P v not P) = 1  This is a Tautology

(P => Q) <=> (notP v Q) = Implication.

(P <=> Q) <=> (P => Q) ^ (Q => P) = Equivalence

((P ^ Q) => R) <=> (P => (Q => R)) = Exportation

Picture 5

((P => Q) ^ (P => notQ) ) <=> notP = Absurdity

This is the law that is used to prove theorems by contradiction.

(P => Q) <=> (notQ => notP) <=> Contrapositivity




Follow

Get every new post delivered to your Inbox.