Statements and Connectives

Main idea

A proposition is a statement that's definitely true or definitely false. Words like "and," "or" and "not" glue simple statements into bigger ones, and since each piece can only be T or F, you can check every possibility in a truth table.

Connectives

{\htmlData{sym=0}{\neg p}}, \qquad {\htmlData{sym=1}{p \wedge q}}, \qquad {\htmlData{sym=2}{p \vee q}}, \qquad {\htmlData{sym=3}{p \oplus q}}

What the symbols mean

$\neg p$
Not p
True exactly when p is false.
$p \wedge q$
p and q
True only when both p and q are true.
$p \vee q$
p or q
Inclusive or: true when at least one of them is true.
$p \oplus q$
Exclusive or
True when exactly one of them is true.

Explanation

A proposition is simply a sentence that's either true or false, and a connective is a word like "and," "or" or "not" that glues propositions into bigger ones. The name "connective" is literal: it connects statements, the way "and" connects two clauses in a sentence. All of this is the bedrock of every proof you'll write and every if-statement in code. Symbols like $\neg p$ (not p), $p \wedge q$ (p and q), $p \vee q$ (p or q) and $p \oplus q$ (one or the other, but not both) look like a new alphabet, but they're just shorthand for those words. The only new idea is being completely precise about when the combined sentence is true. Bear with the notation for a page and it'll feel natural.

Logic starts with sentences you can grade. "7 is prime" and "Paris is in Spain" are propositions: the first is true, the second is false, and there's no in-between. "Close the door" isn't one, because you can't call an order true or false. "x > 3" isn't one either, at least until somebody tells you what x is.

We'll use letters such as $p$ and $q$ for propositions, and connectives to combine them, the same way $+$ and $\times$ combine numbers. Here's the nice part: each letter has only two possible values, so you can list every case. That list is a truth table. Each new letter doubles the number of cases, so two letters need $2^2 = 4$ rows and $n$ letters need $2^n$ :

$p$	$q$	$p \wedge q$	$p \vee q$	$p \oplus q$
T	T	T	T	F
T	F	F	T	T
F	T	F	T	T
F	F	F	F	F

A common mistake. It's tempting to read $p \vee q$ the way you'd read "soup or salad" on a menu, where you get one but not both. In math it doesn't work that way: $p \vee q$ always means at least one, and it's true when both are true. That's the inclusive or. When you really do mean exactly one, you use the exclusive or, $p \oplus q$ . Compare the last two columns of the table: they differ only in the top row.

Compound statements nest, too. To evaluate $\neg(p \wedge q) \vee r$ you work from the inside out, just like you would with $(2 + 3) \times 4$ in arithmetic.

See it

c

1.00

Think of each point as one situation: inside the left circle p is true, inside the right circle q is true. Slide c through 1 = p ∧ q, 2 = p ∨ q, 3 = p ⊕ q and 4 = ¬p, and the shading shows where each statement holds. Notice that ∨ includes the overlap and ⊕ cuts it out.

Worked examples

Example 1

Let $p$ be "it is raining" and $q$ be "I have an umbrella." Write "it is raining and I don't have an umbrella" in symbols.

1
"I don't have an umbrella" is the negation of $q$ , so it's $\neg q$ .

Example 2

Build the truth table of $p \vee \neg q$ .

1
List the four rows of $p$ and $q$ , then flip the $q$ column to get $\neg q$ : F, T, F, T.

Practice

Type your answer and check it. Solve them all to complete the lesson.

Problem 1+5 XP

How many rows does a truth table with 3 propositional variables have?

Problem 2+5 XP

If $p$ is true and $q$ is false, what is the value of $p \wedge q$ ?

Problem 3+5 XP

If $p$ is false and $q$ is true, what is the value of $p \oplus q$ ?

Problem 4+5 XP

In how many of the four rows is $p \vee q$ true?

Problem 5+5 XP

A smart-home rule turns the porch light on when motion is detected and it's dark, or when the alarm is armed: $(m \wedge d) \vee a$ . For how many of the 8 combinations of $m$ , $d$ and $a$ is the light on?

Problem 6+5 XP

A truth table with $n$ variables has $2^n$ rows. How many variables does a truth table with 1024 rows have?

Challenge problem+25 XP

The hardest one here. Get it, and you've got this lesson.

A two-input connective is any rule giving T or F for each of the four rows of $(p, q)$ . How many different two-input connectives are there? How many three-input ones? Enter both.

Where it's used

Search engines, database queries and the chips in every computer combine true/false conditions with exactly these connectives.

Adding Numbers with Logic GatesDiscrete · Electrical Engineering

Implications, Converses and Contrapositives