1.1 Review of basic propositional logic concepts

Propositional Logic Fundamentals

Propositional logic is the foundation of formal reasoning. It deals with declarative statements that are either true or false, and it uses logical connectives to build complex propositions from simpler ones. Since this is a Formal Logic II course, you should already be familiar with most of this material. This review sharpens those fundamentals and highlights the details that matter most going forward, especially around well-formed formulas, equivalence laws, and inference rules.

Basic Components and Truth Values

A proposition (or statement) is a declarative sentence that has exactly one truth value: true or false. "The sky is blue" is a proposition. "Close the door" is not, because commands don't carry truth values. Questions and exclamations are also excluded.

The five basic logical connectives:

• Negation ($\neg$): "not"
• Conjunction ($\wedge$): "and"
• Disjunction ($\vee$): "or" (inclusive or)
• Implication ($\rightarrow$): "if...then"
• Biconditional ($\leftrightarrow$): "if and only if"

Truth tables systematically determine the truth value of a compound proposition for every possible combination of truth values of its components. For $n$ propositional variables, the table has $2^n$ rows.

Two special categories of compound propositions worth remembering:

• A tautology is true under every possible assignment of truth values (e.g., $p \vee \neg p$).
• A contradiction is false under every possible assignment (e.g., $p \wedge \neg p$).

A proposition that is neither a tautology nor a contradiction is called a contingency.

Logical Equivalence

Two propositions are logically equivalent when they share the same truth value under every possible truth-value assignment to their components. This is denoted by $\equiv$ (some texts use $\Leftrightarrow$, but $\equiv$ is a metalogical symbol, not a connective within the object language).

A classic example: $p \rightarrow q \equiv \neg p \vee q$. You can verify this by constructing truth tables for both sides and confirming every row matches.

The key practical consequence: if two formulas are logically equivalent, you can substitute one for the other anywhere in a larger formula without changing that formula's truth value. This substitutability is what makes equivalence laws so powerful in proofs and simplifications.

Constructing Well-Formed Formulas

Propositional Variables and Atomic Formulas

Propositional variables, typically lowercase letters like $p$, $q$, $r$, stand in for simple propositions. For instance, let $p$ represent "It is raining" and $q$ represent "I have an umbrella."

An atomic formula is just a single propositional variable on its own (e.g., $p$, $q$). These are the most basic well-formed formulas and serve as the building blocks for everything more complex.

Formation Rules and Compound Formulas

A well-formed formula (wff) is any expression built from propositional variables and logical connectives according to the following recursive formation rules:

1. Every propositional variable is a wff.
2. If $\phi$ is a wff, then $\neg \phi$ is a wff.
3. If $\phi$ and $\psi$ are wffs, then $(\phi \wedge \psi)$, $(\phi \vee \psi)$, $(\phi \rightarrow \psi)$, and $(\phi \leftrightarrow \psi)$ are wffs.
4. Nothing else is a wff.

These rules guarantee that every wff is syntactically unambiguous. Compound formulas like $\neg p$, $p \wedge q$, and $(p \vee q) \rightarrow r$ are all built by applying these rules.

The main connective (or dominant operator) of a wff is the connective that was applied last in its construction. It governs the truth value of the entire formula. In $(p \wedge q) \rightarrow r$, the main connective is $\rightarrow$.

Parentheses disambiguate the order of operations. $(p \wedge q) \vee r$ and $p \wedge (q \vee r)$ have different truth tables. When parentheses are dropped, a standard precedence convention applies (from highest to lowest binding strength): $\neg$, $\wedge$, $\vee$, $\rightarrow$, $\leftrightarrow$. So $p \wedge q \vee r$ is read as $(p \wedge q) \vee r$.

Evaluating Truth Values

Key Equivalence Laws

The truth value of a complex proposition is fully determined by the truth values of its atomic components and the connectives joining them. Several equivalence laws let you transform formulas into simpler or more useful forms.

De Morgan's Laws describe how negation distributes over conjunction and disjunction:

• $\neg(p \wedge q) \equiv \neg p \vee \neg q$
• $\neg(p \vee q) \equiv \neg p \wedge \neg q$

In short: negating an "and" flips it to "or" (and vice versa), while negating each component.

Distributive Laws let you factor or expand, much like distribution in algebra:

• $p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$
• $p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$

Absorption Laws simplify formulas where a variable appears redundantly:

• $p \vee (p \wedge q) \equiv p$
• $p \wedge (p \vee q) \equiv p$

These are worth internalizing. In proofs, recognizing when an absorption or De Morgan's step applies can save you several lines of work.

Negation and Implication

The negation of $p$, written $\neg p$, simply flips the truth value: true becomes false, false becomes true.

Negating an implication is a common source of mistakes. The negation of $p \rightarrow q$ is not $\neg p \rightarrow \neg q$. Instead:

$\neg(p \rightarrow q) \equiv p \wedge \neg q$

Think of it this way: an implication $p \rightarrow q$ is false in exactly one case, when $p$ is true and $q$ is false. So its negation asserts precisely that case.

Example: The negation of "If it is raining, then I have an umbrella" is "It is raining and I do not have an umbrella."

The contrapositive of $p \rightarrow q$ is $\neg q \rightarrow \neg p$, and it is always logically equivalent to the original implication. Don't confuse the contrapositive with the converse ($q \rightarrow p$) or the inverse ($\neg p \rightarrow \neg q$), neither of which is equivalent to the original.

Rules of Inference for Derivation

Arguments and Valid Inference Rules

An argument in propositional logic consists of a set of premises and a conclusion. The argument is valid if, whenever all the premises are true, the conclusion must also be true. Validity is about the logical structure, not whether the premises are actually true in the real world.

Three inference rules you'll use constantly:

• Modus Ponens (Law of Detachment): From $p \rightarrow q$ and $p$, derive $q$.
• Modus Tollens: From $p \rightarrow q$ and $\neg q$, derive $\neg p$. (This works because modus tollens is essentially modus ponens applied to the contrapositive.)
• Hypothetical Syllogism: From $p \rightarrow q$ and $q \rightarrow r$, derive $p \rightarrow r$. This lets you chain implications together.

Resolution and Conjunction Introduction

Resolution is a powerful rule used heavily in automated theorem proving. It derives a new clause from two clauses that contain complementary literals (a literal is a propositional variable or its negation).

How resolution works, step by step:

1. Take two clauses, each written as a disjunction of literals.
2. Identify a variable that appears positive in one clause and negated in the other.
3. Remove that complementary pair and combine the remaining literals into a single disjunction.

Example: From $(p \vee q)$ and $(\neg p \vee r)$, the variable $p$ appears positive in the first clause and negated in the second. Removing the complementary pair and combining the rest gives $(q \vee r)$.

Conjunction Introduction (also called Adjunction) is straightforward: if you've derived $p$ and you've derived $q$ as separate results, you can combine them into $p \wedge q$. Simple, but essential for assembling conclusions in formal proofs.