We first introduced the concept of a proposition as a statement that has a (constant or variable) truth value, TRUE or FALSE. We often represent propositions with arbitrary mathematical variables such as p, q, etc. Atomic propositions correspond to simple sentences such as "It is raining" or "1+1=2". Compound propositions are built up from atomic propositions using logical connectives or operators. So far, we introduced the following logical operators:
| Operator name: | Propositional logic symbol: | Example usage: | Meaning of example: | C symbol: |
| NOT | ¬ | ¬p | "p is not true" | ! |
| AND | /\ | p /\ q | "p and q are both true" | && |
| OR | \/ | p \/ q | "Either p or q is true, or both are true." | || |
The truth values of compound propositions that are built from simpler propositions using these operators can be defined in terms of the truth values of the simpler propositions, using truth tables, as follows:
| Cases | Truth values of... | |||||
| # | p | q | ¬p | p /\ q | p \/ q | |
| 0 | F | F | T | F | F | |
| 1 | F | T | T | F | T | |
| 2 | T | F | F | F | T | |
| 3 | T | T | F | T | T | |
We learned that a truth table has 1 row for every possible assignment of truth values to the atomic propositions that are involved in a given compound proposition. A compound proposition containing N different atomic propositions would thus require 2N rows to write out its truth table fully. So truth tables are only practical for relatively simple compound propositions.