2.1 Propositions and Logical Connectives

Chapter 1 ended with definitions containing the words “and,” “or,” and “not.” For example, an element belongs to $A\cap B$ when it is in $A$ and in $B$. We understood those words informally. This chapter turns them into a language in which every statement has an exact meaning.

We begin with the smallest unit of logic—a statement that can be true or false—and then learn how to combine statements.

By the end of this section, you will be able to:

• distinguish propositions from questions, commands, and statements with missing information;

• assign letters such as $p$ and $q$ to propositions;

• read and evaluate negation, conjunction, disjunction, and exclusive disjunction;

• use parentheses and precedence to remove ambiguity.

A proposition makes one definite claim

A proposition is a declarative sentence that has exactly one truth value: true, written $\mathrm{T}$, or false, written $\mathrm{F}$.

Consider two examples:

The letter before the colon is a short name for the proposition. Proposition $p$ is true and proposition $q$ is false. A false sentence can still be a proposition: being a proposition means that a truth value is well-defined, not that the sentence is correct.

Before classifying a sentence, ask two questions in order:

1. Is it asserting a fact rather than asking a question or giving a command?

2. Has enough information been supplied to decide one truth value?

The following comparison shows why both questions matter:

The last example is called an open statement. If we replace $x$ by $6$, it becomes the true proposition $6>4$. If we replace $x$ by $2$, it becomes the false proposition $2>4$. The symbol $x$ is a variable: a placeholder that may receive different values.

An open statement can become a proposition in two common ways:

• assign a specific value to every variable;

• state how the variables are to be considered, using a quantifier such as “for every” or “there exists.”

Section 2.3 will introduce quantifiers carefully. For now, the important boundary is simple: if an unspecified variable can change the truth value, the sentence does not yet have one definite truth value.

In the investigation game, do not sort by whether a sentence sounds believable. First decide whether it asserts a fact; then check whether all needed information is fixed. The card “$10<3$” belongs in the proposition file even though its truth value is false.

From atomic propositions to compound propositions

A proposition treated as one indivisible claim is called an atomic proposition. The letters $p$ and $q$ can stand for atomic propositions such as

A logical connective combines or modifies propositions. The result is a compound proposition. Its truth value is determined entirely by the truth values of its parts and by the connective used.

Negation reverses one truth value

The negation of $p$ is written $\neg p$ and read “not $p$.” It reverses the truth value:

If $p$ means “the sensor is active,” then $\neg p$ means “the sensor is not active.” Negation applies to a complete proposition. Parentheses show the boundary when the proposition is compound:

means “it is not the case that both $p$ and $q$ are true.”

Conjunction requires both parts

The conjunction of $p$ and $q$ is written

and read “$p$ and $q$.” It is true only when both parts are true.

If $p$ means “the badge is valid” and $q$ means “the PIN is correct,” then an access rule requiring both checks is $p\land q$. A single failed check makes the conjunction false.

Disjunction requires at least one part

The disjunction of $p$ and $q$ is written

and read “$p$ or $q$.” In standard mathematical logic, “or” is inclusive: the disjunction is true when $p$ is true, when $q$ is true, or when both are true. It is false only when both parts are false.

This matches the union from Chapter 1. An element lies in $A\cup B$ if it belongs to $A$ or $B$, including the overlap.

Everyday language sometimes uses “or” to mean “one but not both.” That operation is exclusive disjunction, often called XOR and written here as $p\oplus q$. It is true when the two truth values differ.

The table lists all four possible assignments to $p$ and $q$. Section 2.2 will explain how to construct such a truth table rather than merely read one.

Evaluate a compound proposition from the inside out

Suppose $p=\mathrm{T}$ and $q=\mathrm{F}$. Evaluate

Work in small steps:

1. Since $q=\mathrm{F}$, negation gives $\neg q=\mathrm{T}$.

2. Since at least one of $p$ and $q$ is true, $p\lor q=\mathrm{T}$.

3. The final conjunction is $\mathrm{T}\land\mathrm{T}$, so the complete expression is true.

Parentheses tell us which part forms one unit. When parentheses are omitted, this course uses the precedence order

Thus $\neg p\land q$ means $(\neg p)\land q$, not $\neg(p\land q)$. When a reader might hesitate, add parentheses even if a precedence rule technically makes them optional. Clear notation is part of correct reasoning.

A reliable evaluation procedure is:

1. record the truth value of each atomic proposition;

2. evaluate the innermost parentheses;

3. apply negations;

4. evaluate conjunctions, then disjunctions;

5. write the final truth value and keep the intermediate values so the result can be checked.

The circuit bench treats truth as a signal. Test all four input worlds, not just the one currently glowing. Two circuits behave the same only if their four-output fingerprints match everywhere; this observation will become the definition of logical equivalence in Section 2.2.

Bridge to the next section

We can now evaluate a compound proposition after someone supplies truth values for $p$ and $q$. But how can we prove that a rule works for every possible assignment? Section 2.2 organizes all possible worlds into truth tables, then uses them to explain implication and logical equivalence.