Propositional Logic

What Is Propositional Logic?

Propositional logic is the foundation of mathematical reasoning. A proposition is a declarative statement that is either true or false, but not both. For example, "The sun rises in the east" is a proposition (true), while "What time is it?" is not a proposition because it's a question.

We use uppercase letters like P, Q, R to represent propositions. The actual truth value they hold is called their truth value.

Logical Connectives

Connectives combine propositions into compound statements:

NOT (¬)     Negation:  ¬P (not P)
AND (∧)     Conjunction: P ∧ Q (P and Q)
OR (∨)      Disjunction: P ∨ Q (P or Q)
IMPLIES (→) Conditional: P → Q (if P then Q)
IFF (↔)     Biconditional: P ↔ Q (P if and only if Q)

Truth Tables

Truth tables show the truth value of a compound proposition for every possible combination of truth values of its components.

P | Q | P ∧ Q | P ∨ Q | P → Q | P ↔ Q
T | T |   T   |   T   |   T   |   T
T | F |   F   |   T   |   F   |   F
F | T |   F   |   T   |   T   |   F
F | F |   F   |   F   |   T   |   T

The Conditional Statement

The conditional P → Q is false only when P is true and Q is false. Think of it as a promise: "If it rains, I will carry an umbrella." The only time I broke my promise is if it rained and I didn't carry an umbrella.

P → Q  ≡  ¬P ∨ Q