Propositional Logic

A system that deals with Proposition (statements).

Proposition

A declarative sentence that is either true or false (but not both) is a proposition.

Also known as a statement.

These sentences would be considered propositions:

  • It is Thursday today (true).
  • I am 14 years old (false).
  • 1 + 1 = 3 (false).

Usually denoted using lowercase letters pp, qq, rr, ss or tt.

p = It rained yesterday. q = I am happy.

The truthfulness or falsity of a proposition is called its Truth Value. Denoted by TT or FF, or 1 and 0 in computer science.

We can use connectives to change or combine the meaning of propositions. For example, ¬p\neg p negates the value of p. If it's true, it becomes false and vice versa.

Truth Table

A truth table allows us to consider all possible combinations of proposition logic systems.

For example, consider ¬p\neg p:

pp ¬p\neg p
1 0
0 1

We can use truth tables to help us understand the truth values of other connectives within propositional logic.

Connective

Negation (NOT)

Symbol: ¬p\neg p

An operator that negates a proposition.

  • pp = I will pass my exam.
  • ¬ p\neg \ p = I will NOT pass my exam.

In Boolean Algebra, it's equivalent to 1T(p)1 - T(p)

Truth table

pp ¬p\neg p
1 0
0 1

Disjunction (OR)

Symbol: pqp \lor q

True when p OR q is true.

Truth table

pp qq pqp \lor q
1 0 1
0 1 1
1 1 1
0 0 0

Equivalent to max(T(p),T(q))\max(T(p), T(q))

Conjunction (AND)

Symbol: pqp \land q

True only when p AND q is true.

Truth table:

pp qq pqp \land q
1 0 0
0 1 0
1 1 1
0 0 0

Equivalent to multiplication T(p)×T(q)T(p) \times T(q)

Implication (If...Then)

Symbol: pqp \rightarrow q

If p is true, then q is true.

Truth table

pp qq pqp \rightarrow q
1 1 1
0 1 1
1 0 0
0 0 1

Think of it as a promise. Only false when promise is broken.

Bi-conditional: \leftrightarrow

Symbol: pqp \leftrightarrow q

Truth table

pp qq pqp \leftrightarrow q
1 1 1
0 1 0
1 0 0
0 0 1

Equivalent to equality check: T(p)=T(q)T(p) = T(q)

Exclusive-Or

Symbol: pqp \oplus q

p or q but not both.

Also called XOR.

Truth Table

pp qq pqp \oplus q
1 1 0
0 1 1
1 0 1
0 0 0

Truth table is opposite of bi-conditional.

Operator Precendence

  1. ¬\neg
  2. \land
  3. \lor
  4. \rightarrow
  5. \leftrightarrow

Tautology

A statement that is always true.

For example: p¬pp \lor \neg p is always true.

pp ¬p\neg p p¬pp \lor \neg p
1 0 1
0 1 1

Consistent

A formula that is true in at least one scenario.

Contradiction

A formula that is never true.

For example: p¬pp \land \neg p

pp ¬p\neg p p¬pp \land \neg p
1 0 0
0 1 0

Also called "inconsistent".

Equivalence

If two formula are equivalent if they have identical truth tables.

Denoted by: \equiv

ABA \equiv B means A and B have the same Truth Table.

Note: equivalence is relation, not connective.

Can prove De Morgan's Laws using a truth table.

¬(pq)¬p¬q\neg (p \land q) \equiv \neg p \lor \neg q

pp qq ¬(pq)\neg (p \land q) ¬p\neg p ¬q\neg q ¬p¬q\neg p \lor \neg q
1 1 0 0 0 0
1 0 1 0 1 1
0 1 1 1 0 1
0 0 1 1 1 1

(pq)(¬pq)(p \rightarrow q) \equiv (\neg p \land q)

Laws of logic

See Laws of Logic.


Backlinks