Logical Connectives

definitions
discrete-math
logic
propositional-logic

Logic is the study of reasoning, and the language of symbolic logic is what lets us analyse ordinary sentences, test arguments for validity, construct proofs for complex arguments, and identify incorrect proofs and common fallacies. This note covers the first layer of that language: statements, the three basic connectives, and the truth tables that define them.

Statements

A statement (or proposition) is a sentence that is either true or false, but not both. Represented by variables \(p, q, r, \dots\)

Sentence Statement? Why
“6 is odd.” Yes — and it is false Definitely one of T/F, and we can say which
“It is raining.” Yes Which value it takes depends on the circumstances — it could be either — but in any given circumstance it is definitely one or the other
“\(x\) is odd.” No Its truth depends on the unspecified \(x\), so it has no truth value on its own
“Is it raining?” No A question is not true or false
“She is happy.” No Not objectively true or false

The row worth pausing on is “It is raining.” A sentence does not stop being a statement just because you personally don’t know which value it has. What disqualifies “\(x\) is odd.” is different: it has a free variable, so there is nothing to be true about until \(x\) is fixed. Sentences of that shape are predicates, and the machinery for turning them into statements is quantifiers — see quantified-statements.

Basic connectives

Connective Symbol Alt. symbol
not \(\sim\) \(\neg\)
and \(\land\)
or (inclusive) \(\lor\)

\(\sim\) and \(\neg\) are both common symbols for “not”. This course writes \(\sim\), and so does the examination formula page, so that is what these notes use.

\(p \lor q\) is true when \(p\) is true, \(q\) is true, or both (“inclusive or”).

The defining truth tables

These three must be known by heart:

\(p\) \(q\) \(p \land q\) \(p \lor q\)
T T T T
T F F T
F T F T
F F F F
\(p\) \(\sim p\)
T F
F T

Inclusive vs exclusive in English

Ordinary English uses “or” both ways:

  • “Would you like red or white wine?” — reads as exclusive; you’re expected to pick one.
  • “Would you like milk or sugar with your tea?” — reads as inclusive; both is a perfectly good answer.

\(\lor\) is always the inclusive one.

Translating English into symbols

Translating between English and mathematics is difficult, and three English words carry most of that difficulty:

English Symbolic Note
but \(\land\) Carries a contrast in English, none in logic — “it is not cold but it is snowing” is \(\sim p \land q\)
neither \(A\) nor \(B\) \(\sim(A \lor B)\), equivalently \(\sim A \land \sim B\) “Neither … nor” is the negation of an “or” statement — the De Morgan rewrite is why the two forms agree (see logical-equivalence-laws)
or \(\lor\) Always inclusive, whatever the English suggests

Worked. Let \(p\) = “it is cold”, \(q\) = “it is snowing”, \(r\) = “it is sunny”.

English Symbolic
It is not cold but it is snowing. \(\sim p \land q\)
It is neither snowing nor cold, but it is sunny. \(\sim(q \lor p) \land r \;\equiv\; (\sim q \,\land\sim p) \land r\)

and back the other way:

Symbolic English
\(\sim q \land p\) It is not snowing and it is cold.
\((p \land q) \lor r\) It is cold and snowing, or it is sunny. (Inclusive — a cold, snowing, sunny day satisfies it.)

Are “It is not cold but it is snowing” and “It is snowing and it is not cold” equivalent? Yes, by the commutative law: \(\sim p \land q \equiv q \,\land\sim p\). The English word order changes and the meaning does not.

Exclusive or (\(\oplus\))

“One or the other, but not both”, often written XOR:

\[p \oplus q \equiv (p \lor q) \land \sim(p \land q)\]

Laid beside the two inclusive connectives, so the differences are visible in one place:

\(p\) \(q\) \(p \land q\) \(p \lor q\) \(p \oplus q\)
T T T T F
T F F T T
F T F T T
F F F F F

\(\oplus\) is equivalent to neither of them:

\[p \oplus q \;\not\equiv\; p \lor q \qquad\qquad p \oplus q \;\not\equiv\; p \land q\]

\(\oplus\) agrees with \(\lor\) everywhere except the “both” row, and agrees with \(\land\) only on the row where neither holds.

Order of operations

  1. \(\sim\) first.
  2. \(\land, \lor\) equal second — parenthesise, else left to right.

\(\to\) and \(\leftrightarrow\) join as an equal third tier; see conditional-statements.

Worked. Take the statement form

\[(p \land q) \lor \sim (r \lor p) \land s\]

Because \(\sim\) binds first, the \(\sim\) takes only \((r \lor p)\); the remaining \(\lor\) and \(\land\) are then resolved left to right. So it means

\[\big((p \land q) \lor (\sim (r \lor p))\big) \land s\]

which is a different statement form from \((p \land q) \lor \big((\sim (r \lor p)) \land s\big)\) — the reading you would get by assuming \(\land\) binds tighter than \(\lor\). In this course they are equal in precedence, so that assumption is wrong here. Write the parentheses.

Truth tables

A truth table shows the truth value of a statement form for all possible truth values of its statement variables. A statement form with \(n\) variables has \(2^n\) rows, where \(n\) counts the distinct letters, not the occurrences.

Take \((p \land q) \land (q \land r)\). Each unique letter is a variable, so there are 3 variables \(p, q, r\) — not 2 and not 4 — and the table has \(2^3 = 8\) rows. The repeated \(q\) does not add one.

Standard truth table form

Construct your truth tables in standard form so that (i) you are sure you have covered all combinations of the truth values of the statement variables, and (ii) it is easy for someone to check your work.

Standard form fixes the row order: the first variable is T for the whole top half and F for the whole bottom half, and each later variable halves the run again, so the last variable alternates T, F every row.

Figure 1: Standard truth table form for one, two and three variables. Each new variable doubles the number of rows and halves the run of like values — 4, 2, 1 for three variables — so the pattern is fixed and completeness is checkable at a glance. The rings mark that pattern on the three-variable table. The narrow amber column separates the variables from the statement-form column.

The four-variable table extends the same pattern: \(p\) runs T for eight rows then F for eight, \(q\) in blocks of four, \(r\) in blocks of two, \(s\) alternating — \(2^4 = 16\) rows.

For how to build the intermediate columns of a compound form, and the convention of numbering them in evaluation order, see the worked table in 2026-07-30-logical-form-and-equivalence.

See also