1.1 Propositional logic

Logic begins with statements that are already complete enough to be judged true or false. That sounds simple, but the distinction matters throughout the course: once a statement is not yet closed, it cannot be treated as a proposition.

Propositions and truth values

Definition

Proposition

A proposition is a statement with a definite truth value. It is either true or false, and nothing in between.

The point of the definition is not to make logic abstract for its own sake. It is to separate statements that can be tested from statements that are still unfinished.

Examples:

• $2 + 2 = 4$ is a proposition.
• Every even number is divisible by 2 is a proposition.
• Open the window. is not a proposition, because it is a command.
• $x + 1 = 3$ is not yet a proposition if $x$ has not been fixed.

Common mistake

A formula with a free variable is not automatically a proposition

If the truth of a sentence still depends on an unspecified variable, then the sentence is open, not closed. You must either assign a value to the variable or bind it later with a quantifier.

Worked example

Decide which statements are propositions

Consider the following three statements:

1. $7$ is prime.
2. $x + 1 = 3$.
3. Please close the door.

Statement 1 is a proposition, and it is true. Statement 2 is not a proposition yet, because its truth value depends on the choice of $x$: at $x = 2$ it is true, while at $x = 0$ it is false. Statement 3 is not a proposition, because it is a request rather than a claim. A formula such as $x^2 + 1 > 0$ over the real numbers is different: it is true for every real $x$, but it is still an open sentence until $x$ is assigned or quantified.

Logic only starts after the sentence is definite enough to be checked. A sentence that still needs a missing variable is not ready for truth-table analysis.

The Boolean alphabet

The course uses five connectives repeatedly:

These are not just informal abbreviations. They are the basic symbols of the logic language, and they are the tools used to build more complicated statements.

The precedence convention is only partial:

1. $¬$
2. $∧$ and $∨$ at the same level
3. $→$ and $↔$

There is no precedence between $∧$ and $∨$, so a mixed expression using both is ambiguous until parentheses are supplied. This example makes the issue visible:

Worked example

Parse a formula before reading it

The string $¬A ∧ B ∨ C$ has two possible readings:

$$\neg A \land B \lor C$$

It may mean $(¬A ∧ B) ∨ C$, which says that either $A$ is false and $B$ is true, or $C$ is true. It may instead mean $¬A ∧ (B ∨ C)$, which says that $A$ is false and at least one of $B$ and $C$ is true. These are different formulas.

If you meant something else, you must say so explicitly with parentheses.

Logic formulas are precise objects. Parentheses are not decoration; they decide what the statement actually says.

Syntax, scope, and truth functions

A well-formed formula is built recursively. An atomic proposition such as $A$ is a formula. If $φ$ is a formula, then $¬φ$ is a formula and uses exactly one operand. If $φ$ and $ψ$ are formulas, then $(φ ∧ ψ)$, $(φ ∨ ψ)$, $(φ → ψ)$, and $(φ ↔ ψ)$ are formulas, each with exactly two complete operands. Thus a string such as $P ∧ ∨ Q$ is not a formula. This construction rule explains why a command or an open sentence cannot be inserted as though it were an atom: it has no fixed truth value for the truth function to evaluate.

Worked example

Read nested scope before calculating

The expression $A → B ∧ ¬C$ is parsed as $A → (B ∧ ¬C)$, because negation binds first and conjunction binds before implication. It is false only when $A$ is true while $B ∧ ¬C$ is false. By contrast, $(A → B) ∧ ¬C$ requires both the implication and $¬C$ to be true. The two formulas have the same three letters but different outermost connectives, so they require different final columns.

In particular, $A → B ∧ ¬C$ is unambiguous because $¬$ is evaluated before $∧$, and $∧$ before $→$; it means $A → (B ∧ ¬C)$. Similarly, $¬A ↔ B ∨ C$ means $¬A ↔ (B ∨ C)$, because $∨$ is evaluated before $↔$. The biconditional compares the value of $¬A$ with the value of $B ∨ C$; it is not a shorthand for negating the whole disjunction.

Once a formula has been parsed, an assignment gives each atomic letter either $T$ or $F$. The connectives then determine one value for every subformula, working from the inside out. Thus a formula has a truth function: the same assignment to its letters must always produce the same final value, regardless of the English story used to motivate those letters. Truth-table rows are the finite record of that function.

A useful habit is to write the intended atomic meanings beside the formula before computing. If $A$ means “the file is saved” and $B$ means “the program closes,” then $A → B$ has a clear scope and direction; silently reversing the meanings would create a different argument even though the symbols look familiar.

Truth tables and equivalence

A Boolean formula can be evaluated once the truth values of its component propositions are known. That is what a truth table records.

Theorem

Useful equivalences

The following equivalences are standard and should become automatic:

$$P → Q \equiv ¬P ∨ Q$$$$P ↔ Q \equiv (P → Q) ∧ (Q → P)$$$$¬(P ∧ Q) \equiv ¬P ∨ ¬Q$$$$¬(P ∨ Q) \equiv ¬P ∧ ¬Q$$$$¬¬P \equiv P$$

These are not philosophy statements. They are truth-table identities.

Worked example

Check implication with a truth table

The implication $P → Q$ is false in exactly one case: when $P$ is true and $Q$ is false. In every other case it is true.

$P$	$Q$	$P → Q$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$T$
$F$	$F$	$T$

So $P → Q$ does not mean that $P$ and $Q$ are both true. It means that the case $P$ true and $Q$ false is ruled out.

Many students read $P → Q$ as a causal sentence. In logic, it is not a story about cause and effect. It is a truth condition.

Rules of inference

Several deduction patterns appear repeatedly in proof writing.

Theorem

Common inference patterns

If $P → Q$ and $P$ are true, then $Q$ is true. This is modus ponens.

If $P → Q$ and $¬Q$ are true, then $¬P$ is true. This is modus tollens.

If $P → Q$ and $Q → R$ are true, then $P → R$ is true. This is hypothetical syllogism.

If $P ∨ Q$ and $¬P$ are true, then $Q$ is true. This is disjunctive syllogism.

These patterns are important because they are the logic version of a valid calculation. If the premises are true, the conclusion must also be true.

Worked example

A valid chain of implications

Suppose you know

$$A → B,\qquad B → C,\qquad A.$$

Then you may conclude $B$ from the first and third statements, and then $C$ from the second statement.

The conclusion $C$ follows from the premises because every step preserves truth.

This is a two-step use of modus ponens. First $A$ gives $B$, then $B$ gives $C$.

Common mistake

Do not confuse valid and invalid implication patterns

From $P → Q$ and $Q$, you cannot conclude $P$. That fallacy is called affirming the consequent.

From $P → Q$ and $¬P$, you cannot conclude $¬Q$. That fallacy is called denying the antecedent.

A countermodel for denying the antecedent

For the argument $P → Q$, $¬P$, therefore $¬Q$, choose $P = F$ and $Q = T$. The implication is true because its antecedent is false, and $¬P$ is true, but $¬Q$ is false. This one assignment satisfies both premises and refutes the conclusion, so the argument is invalid.

Translating conditions into formulas

A Boolean letter stands for a complete proposition, while a connective records how complete propositions are combined. Translation therefore has two stages: decide what each letter means, then preserve the scope of the English words when choosing connectives and parentheses.

Worked example

Necessary and sufficient conditions

Let $D$ mean “the integer is divisible by 4” and let $E$ mean “the integer is even.” The statement “divisibility by 4 is sufficient for evenness” is $D → E$. The same relationship can be worded “evenness is necessary for divisibility by 4”: if $D$ holds, $E$ must hold. The order of the words changes, but the arrow still points from the condition being assumed to the condition that must follow.

The converse, $E → D$, is a different claim and is not licensed by the original sentence. The integer 2 is a counterexample: it is even but not divisible by 4.

A phrase such as “A and B, or C” must be translated with its intended grouping. Because $∧$ and $∨$ share one precedence level in the course convention, $A ∧ B ∨ C$ is ambiguous. Write $(A ∧ B) ∨ C$ for “either $A$ and $B$, or $C$,” and write $A ∧ (B ∨ C)$ for “$A$, and either $B$ or $C$.” The two formulas can have different truth values, so grouping must be settled before the table.

What validity asks

An argument has premises and a conclusion. It is valid when every assignment that makes all the premises true also makes the conclusion true. This is a claim about a relationship between formulas, not a claim that the premises are actually true in the world.

Theorem

Validity by the forbidden row

To test premises $P_1, ..., P_n$ and conclusion $Q$, search for an assignment on which every $P_i$ is true and $Q$ is false. If such a row exists, it is a countermodel and the argument is invalid. If no such row exists, the argument is valid. Equivalently, the formula

$$(P_1 \land \cdots \land P_n) \to Q$$

is a tautology.

Worked example

A countermodel for affirming the consequent

Suppose the premises are $P → Q$ and $Q$, with conclusion $P$. Choose $P = F$ and $Q = T$. Then $P → Q$ is true because its antecedent is false, and the second premise $Q$ is true, but the conclusion $P$ is false. One row is enough to refute validity. A row where a premise is false cannot do that job, because validity only requires the conclusion on rows where all premises hold.

This also explains why logical equivalence and inference validity must be kept separate. $φ ≡ ψ$ says that two formulas have matching truth values on every row. The argument φ, therefore ψ says only that no row has $φ$ true and $ψ$ false; it is valid whenever $φ → ψ$ is a tautology. The converse implication need not be valid unless $ψ → φ$ is also a tautology.

Negating and simplifying a claim

Negation changes the whole claim in its scope. To negate “$P$ and $Q$,” use $¬(P ∧ Q)$, not $¬P ∧ ¬Q$; De Morgan's law then gives the equivalent formula $¬P ∨ ¬Q$. Likewise, $¬(P → Q)$ is true exactly on the implication's one false row, so

$$¬(P → Q) \equiv P \land ¬Q.$$

Worked example

Rewrite a negated implication

To rewrite $¬(A → B)$ without an implication symbol, first use $A → B ≡ ¬A ∨ B$:

$$¬(A → B) \equiv ¬(¬A ∨ B) \equiv ¬¬A \land ¬B \equiv A \land ¬B.$$

The result says exactly that the antecedent is true while the conclusion is false. This is why a failed implication supplies the countermodel row for an argument.

These rewrites are a controlled simplification procedure: remove an implication, push negations through a conjunction or disjunction with De Morgan's laws, and cancel double negations. Every step is an equivalence, so the resulting formula has the same truth function as the original.

Implication, countermodels, and proof direction

An implication does not assert its hypothesis or claim causation. Its truth condition excludes exactly the assignment with a true hypothesis and false conclusion. The converse reverses the arrow; the contrapositive reverses it and negates both sides.

Contrapositive derivation

The implication $P\to Q$ equals $\neg P\lor Q$. The contrapositive $\neg Q\to\neg P$ equals $\neg\neg Q\lor\neg P$, hence $Q\lor\neg P$. Commutativity gives the original disjunction, so the two formulas are equivalent for every assignment.

Worked example

Distinguish a converse from a contrapositive

For rain and wet ground, let $P$ mean “it is raining” and $Q$ mean “the ground is wet.” The converse $Q\to P$ says that wet ground guarantees rain; it is a different claim and can fail when a sprinkler makes the ground wet. The contrapositive $\neg Q\to\neg P$ says that dry ground implies no rain and is equivalent to the original implication.

Modus tollens checks both premises

Assume $P\to Q$ and $\neg Q$ are true. The second premise forces $Q=F$. If $P=T$, the first premise would be false. Therefore $P=F$, so $\neg P$ follows. It is the first premise that excludes the row $(T,F)$; both premises must be retained when checking validity.

Quick checks

Checkpoint

Is $¬A ∧ B ∨ C$ unambiguous under the course convention? If not, give both bracketings.

Remember that $¬$ binds first, while $∧$ and $∨$ share a precedence level.

Solution · Answer

It is ambiguous. The two bracketings are $(¬A ∧ B) ∨ C$ and $¬A ∧ (B ∨ C)$.

Checkpoint

Which of the following is logically equivalent to $P → Q$: $¬P ∨ Q$ or $P ∧ Q$?

Check the truth condition of implication.

Solution · Answer

$¬P ∨ Q$ is equivalent to $P → Q$.

Checkpoint

Is the argument $P → Q$, $Q$, therefore $P$ valid?

Test the conclusion against the case where $P$ is false.

Solution · Answer

No. It is invalid, and the fallacy is affirming the consequent.

Explore the truth conditions

Use the interactive table to test formulas against the truth values you assign.

Next: calculate with truth tables

Continue with 1.2 Truth tables and equivalence. It turns the syntax and truth rules here into a complete method for checking formulas.