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

Advertisements

Contrapositive of P implies Q

pimpliesqcontrapositive

Converse: Q => P

The converse of P=>Q  is Q=>P

The Premise(P) and the Conclusion(Q) switch places. The Conclusion becomes the Premise, the Premise becomes the Conclusion.

Inverse: not P => not Q

The inverse of P=>Q  is (not P => not Q)
Negate both the Premise(P) and the Conclusion(Q)

Contrapositive: not Q => not P

The Contrapositive of P=>Q  is (not Q => not P)
Contrapositive a combination of the converse and the inverse. To get the Contrapositive just Negate and switch The Premise(P) and The Conclusion(Q).

Example

P = The Traffic Light is Green

Q = The Car Drives over the crossing

P => Q is then:

If the I fall into the lake, then I get wet.

The Contratpositive of P => Q is then: not Q => not P is then:

If I am not wet, then I did not fall into the lake.