Propositional Logic as a System of Inference Rules

Q: What is propositional logic

Propositional logic is a logical system that combines statements with definite truth values (propositions) using the connectives $\land$ (and), $\lor$ (or), $\to$ (implies), and $\neg$ (not). It does not look inside the internal structure of a proposition (who, what); it treats only the connections between propositions, and is the simplest logic.

Q: What does it mean to view logic as a system of inference rules

Instead of computing 'when it is true' with truth tables, you give each connective inference rules specifying 'how it may be used,' and build a proof as a sequence of rule applications. For example, if $A$ and $B$ hold, then $A \land B$ holds. This treats logic as a game of symbol manipulation, and leads directly to natural deduction and proof assistants.

Seeing it as "derivable / not derivable" rather than via truth tables

Introduction (high school to first-year university)

Goal of this page

Review the connectives $\land, \lor, \to, \neg$ and adopt the viewpoint of seeing propositional logic not as "something computed with truth tables" but as "something derived by inference rules." Also grasp its relation to truth tables.

1. Propositions and connectives

A proposition is a statement that is definitely true or false. Propositional logic does not enter the inside of a proposition (subject, predicate, etc.); it represents propositions by letters $p, q, r, \dots$ and treats only how they are joined. The tools for joining them are the connectives.

Definition: connectives

$\neg A$: negation (not $A$)
$A \land B$: conjunction ($A$ and $B$)
$A \lor B$: disjunction ($A$ or $B$)
$A \to B$: implication (if $A$ then $B$)

The intuitive meaning of the connectives is also covered in Proof: Logical Operations. In this chapter we step into the view that gives them not "meaning" but "rules of use."

2. Two views of propositional logic

There are broadly two ways to define propositional logic.

Definition by semantics (truth tables)

Assign true $\top$ / false $\bot$ to each propositional variable, and compute the truth of the whole formula according to the connectives' truth tables. A formula that is true under every assignment is a tautology. This is the semantic side, in the sense of Syntax and Semantics.

Definition by syntax (inference rules)

Give each connective inference rules specifying "when it may be introduced and how it may be used," and derive formulas by stacking up rule applications. A derived formula is a theorem. This is the syntactic side, in the sense of Syntax and Semantics.

This series emphasizes the latter, because a definition by inference rules is complete using only symbol manipulation and can be checked mechanically. The predicate logic, natural deduction, and proof assistants of later chapters are all extensions of this "derive by the rules" stance.

3. The shape of an inference rule

An inference rule is written with the premises above a horizontal line and the conclusion below. Read it as "if everything above holds, then the bottom holds."

Example: conjunction and modus ponens

Conjunction introduction (if $A$ and $B$ hold, then $A \land B$ holds):

$$\dfrac{A \qquad B}{A \land B}$$

Implication elimination (modus ponens; from $A \to B$ and $A$, infer $B$):

$$\dfrac{A \to B \qquad A}{B}$$

These are not "the result of computing a truth table"; they are given as rules from the start. Without considering the meaning of the formulas at all, you may apply them whenever the shapes match. This mechanical nature is the heart of the syntactic stance. Giving each connective introduction and elimination rules systematically yields natural deduction, treated in detail in Basic: Natural Deduction.

Figure 1: A small proof applying an inference rule twice. Each step's correctness can be confirmed by the shape of the symbols alone.

4. Relation to truth tables

Semantics (truth tables) and syntax (inference rules) are different definitions, but in classical propositional logic they define the same set of propositions. That is, the following holds.

Soundness and completeness of classical propositional logic (outline)

For a formula $A$, "$A$ is derivable by the inference rules ($\vdash A$)" is equivalent to "$A$ is a tautology ($\models A$, true under every assignment)."

That "derivable by the rules" and "always true" coincide is not obvious; it is a theorem requiring proof. This is the subject of Soundness and Completeness.

Summary

Key points

Propositional logic: represent propositions by letters and join them with $\neg, \land, \lor, \to$
Logic has two definitions: semantics (truth tables) and syntax (inference rules)
Inference rules specify "if the premises hold, the conclusion holds" by the shape of the symbols alone
In classical propositional logic, "derivable" and "always true" coincide (soundness and completeness)

Frequently asked questions

What is propositional logic?

A logical system that combines statements with definite truth values (propositions) using the connectives $\land$ (and), $\lor$ (or), $\to$ (implies), $\neg$ (not). It does not enter the internal structure of a proposition; it treats only the connections between propositions, and is the simplest logic.

What does it mean to view logic as a system of inference rules?

Instead of computing "when it is true" with truth tables, you give each connective inference rules for "how it may be used," and build a proof as a sequence of rule applications — e.g., if $A$ and $B$ hold then $A \land B$. This treats logic as symbol manipulation and leads directly to natural deduction and proof assistants.

Which is correct, truth tables or inference rules?

Both are correct ways to define propositional logic: truth tables give the semantics (when it is true), inference rules give the syntax (what can be derived). In classical propositional logic the two coincide (soundness and completeness): "true in every row" and "derivable by the rules" define the same propositions.