Symbolic
Logic ∴

§0What Logic Actually Is

Symbolic logic (also called formal or mathematical logic) is the study of reasoning carried out by replacing ordinary language with precise symbols. By stripping arguments down to their bare structure, we can decide whether a conclusion must follow from its premises — independently of what the sentences happen to be about.

The central object of study is the argument: a set of statements (the premises) offered in support of another statement (the conclusion).

Consider:

This is valid: granting the premises, the conclusion is inescapable. It is also sound, because the premises are in fact true. Crucially, the same form — "All A are B; x is an A; so x is B" — is valid no matter what A, B, and x stand for. That portable structure is exactly what symbolic logic isolates.

This course builds upward in two great layers: propositional logic (reasoning about whole statements joined by connectives), then predicate logic (reasoning about objects, properties, and quantity). Along the way you'll use live tools that compute the very things textbooks ask you to do by hand.

§1Propositional Logic

Propositional logic (or sentential logic) treats simple statements as indivisible atoms and studies how their truth values combine. We abbreviate atomic propositions with capital letters — by convention P, Q, R, S…

For instance, let P = "It is raining" and Q = "The ground is wet." We then build compound propositions by joining atoms with logical connectives, e.g. P → Q ("if it is raining, then the ground is wet").

Well-formed formulas

Not every string of symbols counts. A well-formed formula (WFF) is built by these recursive rules:

1. Every propositional variable (P, Q, R, …) is a WFF.
2. If φ is a WFF, then ¬φ is a WFF.
3. If φ and ψ are WFFs, then (φ ∧ ψ), (φ ∨ ψ), (φ → ψ), and (φ ↔ ψ) are WFFs.
4. Nothing else is a WFF.

So ¬(P ∧ Q) → R is well-formed; P ¬ ∧ Q is gibberish.

Operator precedence

To avoid drowning in parentheses, connectives bind in a fixed order — tightest first:

Thus ¬P ∧ Q → R reads as ((¬P) ∧ Q) → R. When in doubt, add parentheses — the truth-table engine below honours exactly this precedence.

§2The Five Connectives

Each connective is defined entirely by how it maps the truth values of its parts to a truth value for the whole — they are truth-functional. Here is the complete catalogue.

Negation ¬ (NOT)

Flips truth value. ¬P is true exactly when P is false.

Conjunction ∧ (AND)

P ∧ Q is true only when both conjuncts are true.

Disjunction ∨ (OR)

P ∨ Q is true when at least one disjunct is true. This is inclusive or — true also when both hold. (Exclusive "or" is a separate, derived connective ⊕.)

Conditional → (IF…THEN)

P → Q ("if P then Q") is false in exactly one case: when the antecedent P is true but the consequent Q is false. A famous consequence is vacuous truth — if P is false, P → Q is automatically true. ("If the moon is cheese, then 2+2=5" is, formally, true.)

Biconditional ↔ (IF AND ONLY IF)

P ↔ Q is true when both sides have the same truth value.

§3Truth Tables

A truth table lists every possible combination of truth values for the atomic variables and computes the resulting value of a formula in each case. With n variables there are 2ⁿ rows — the exhaustive set of possible worlds.

The four base binary connectives, side by side:

To evaluate a complex formula by hand, you compute inner sub-formulas first and work outward — exactly mirroring operator precedence. The engine in the next section does this automatically and shows you every intermediate column.

⚙Live Truth-Table Engine

Type any well-formed formula. The engine tokenizes it, parses it into a syntax tree (respecting precedence), generates all 2ⁿ rows, fills in every sub-formula column, and classifies the result.

§5Tautology, Contradiction, Contingency

Looking at the final column of a truth table, every formula falls into exactly one of three categories:

Tautologies are the "logical truths" — the theorems guaranteed by form alone. Try P | ~P and P & ~P in the engine above to see the engine label each one.

A formula is satisfiable if it is true in at least one row (i.e. not a contradiction), and unsatisfiable if it is a contradiction. Deciding satisfiability is the famous SAT problem at the heart of computer science.

§6Logical Equivalence & the Laws

Two formulas are logically equivalent (written φ ≡ ψ) when they have identical truth values in every row — equivalently, when φ ↔ ψ is a tautology. Equivalences are the algebra of logic: they let you rewrite formulas while preserving meaning.

The standard equivalences

§7Arguments & Validity

We can now make "valid" mathematically precise. An argument with premises P₁, P₂, …, Pₙ and conclusion C is valid if and only if there is no row of the joint truth table in which all premises are true while the conclusion is false.

Equivalently: an argument is valid iff the single conditional (P₁ ∧ … ∧ Pₙ) → C is a tautology. The checker below implements the critical-row method and reports any counterexample it finds.

⚙Argument Validity Checker

Enter your premises (separated by commas or semicolons) and a single conclusion. The tool builds the joint table, highlights the critical rows, and delivers a verdict — with a counterexample if the argument fails.

Try "Affirming the Consequent" (premises P -> Q, Q; conclusion P) — a classic fallacy the checker will expose with a counterexample row.

§9Rules of Inference & Natural Deduction

Truth tables decide validity by brute force, but they explode (2ⁿ rows). Natural deduction instead derives the conclusion step-by-step using a small set of always-valid rules of inference. Each rule is itself a valid argument form.

A worked proof

Prove R from premises P → Q, Q → R, and P:

1.  P → Q        (premise)
2.  Q → R        (premise)
3.  P            (premise)
4.  Q            (1, 3, Modus Ponens)
5.  R            (2, 4, Modus Ponens)   ∴ proved

Conditional & indirect proof

Two power techniques: in conditional proof you assume the antecedent, derive the consequent, then discharge the assumption to conclude P → Q. In indirect proof (reductio ad absurdum) you assume the negation of your goal and derive a contradiction (R ∧ ¬R), which establishes the goal.

§10Predicate Logic

Propositional logic can't see inside a statement. It treats "All cats are mammals" and "Some cats are black" as unrelated atoms. Predicate logic (first-order logic) opens the atom up, exposing objects, their properties, and relations — and adds quantifiers to talk about how many.

The new vocabulary

• Constants — names of specific objects: a, b, c (e.g. s = Socrates).
• Variables — placeholders ranging over a domain: x, y, z.
• Predicates — properties/relations applied to terms: Cat(x), Loves(x, y).
• Universal quantifier ∀ — "for all": ∀x means "for every x."
• Existential quantifier ∃ — "there exists": ∃x means "for at least one x."

Translating English

Quantifier negation

The quantifiers are dual to one another — De Morgan's laws lifted to the predicate level:

Over a finite domain, the quantifiers collapse into ordinary connectives: ∀x P(x) becomes a big conjunction P(a)∧P(b)∧… and ∃x P(x) becomes a big disjunction P(a)∨P(b)∨…. That fact is exactly what lets us model quantifiers in Octave with all() and any() — see the lab below.

§11Normal Forms

Any propositional formula can be rewritten into standardized shapes, useful for proofs, circuit design, and automated solvers.

Literal

A variable or its negation: P or ¬P.

Disjunctive Normal Form (DNF)

An OR of ANDs of literals — a "sum of products": (P ∧ ¬Q) ∨ (¬P ∧ R). You can read a DNF straight off the true rows of a truth table.

Conjunctive Normal Form (CNF)

An AND of ORs of literals — a "product of sums": (P ∨ ¬Q) ∧ (¬P ∨ R). CNF is the input format for SAT solvers.

§12The GNU Octave Logic Lab

GNU Octave is a free, open-source numerical environment (largely compatible with MATLAB). Its element-wise logical operators make it a superb scratchpad for propositional logic: truth values are just 1 (true) and 0 (false), and a whole column of a truth table is a vector. Copy any block below into Octave and run it.

Lab 1 — The four connectives as columns

% Truth values: 1 = true, 0 = false. Order rows T,T / T,F / F,T / F,F
P = [1; 1; 0; 0];
Q = [1; 0; 1; 0];

NOT_P  = ~P;                 % negation
AND_PQ = P & Q;              % conjunction
OR_PQ  = P | Q;              % disjunction (inclusive)
XOR_PQ = xor(P, Q);          % exclusive or
IMP_PQ = ~P | Q;             % conditional  P -> Q  ==  ~P | Q
IFF_PQ = (P == Q);           % biconditional P <-> Q

% Print as one labelled matrix
disp('  P  Q | ~P  P&Q  P|Q  xor  P->Q P<->Q');
disp([P Q NOT_P AND_PQ OR_PQ XOR_PQ IMP_PQ IFF_PQ]);

Lab 2 — A reusable truth-table generator

This function produces all 2ⁿ input combinations (true-first ordering), so you can append any computed column.

function combos = truth_combos(n)
  % All combinations of n truth values, ordered T...F per column.
  % dec2bin gives binary strings; subtracting '0' makes a numeric matrix.
  combos = dec2bin((2^n - 1):-1:0) - '0';
end

% --- usage: truth table for  (P -> Q) & (Q -> R) ---
C = truth_combos(3);
P = C(:,1); Q = C(:,2); R = C(:,3);
result = (~P | Q) & (~Q | R);
disp('  P  Q  R | (P->Q)&(Q->R)');
disp([P Q R result]);

Lab 3 — Detecting tautologies & contradictions

C = truth_combos(1);  P = C(:,1);

excluded_middle = P | ~P;       % P v ~P
contradiction   = P & ~P;       % P & ~P

printf('P v ~P  is tautology?     %d\n', all(excluded_middle));
printf('P & ~P  is contradiction? %d\n', ~any(contradiction));
% all(col)==1 -> tautology ;  any(col)==0 -> contradiction

Lab 4 — Verifying De Morgan's law

C = truth_combos(2);  P = C(:,1); Q = C(:,2);

lhs = ~(P & Q);        % ¬(P ∧ Q)
rhs = ~P | ~Q;         % ¬P ∨ ¬Q

if isequal(lhs, rhs)
  disp('De Morgan confirmed: the two columns are identical.');
else
  disp('Columns differ — not equivalent.');
end

Lab 5 — Testing an argument for validity

An argument is valid iff no row has all premises true but the conclusion false.

% Argument:  P->Q ,  Q->R   ∴  P->R   (Hypothetical Syllogism)
C = truth_combos(3);
P = C(:,1); Q = C(:,2); R = C(:,3);

prem1 = ~P | Q;            % P -> Q
prem2 = ~Q | R;            % Q -> R
concl = ~P | R;            % P -> R

critical    = prem1 & prem2;        % rows where all premises hold
counterex   = critical & ~concl;    % premises true, conclusion false
isValid     = ~any(counterex);

printf('Argument is valid? %d\n', isValid);
if any(counterex)
  disp('Counterexample rows (P Q R):');
  disp(C(counterex, :));
end

Lab 6 — Quantifiers over a finite domain

Here all() realises ∀ and any() realises ∃.

% Domain = {1,2,3,4,5}; predicates Even(x) and Positive(x)
domain   = 1:5;
Even     = mod(domain, 2) == 0;     % [0 1 0 1 0]
Positive = domain > 0;             % [1 1 1 1 1]

printf('∃x Even(x)      : %d\n', any(Even));      % true
printf('∀x Even(x)      : %d\n', all(Even));      % false
printf('∀x Positive(x)  : %d\n', all(Positive));  % true

% ∀x (Even(x) -> Positive(x))  — all evens are positive
printf('∀x(Even->Pos)   : %d\n', all(~Even | Positive));
% Quantifier negation:  ¬∀x Even(x)  ==  ∃x ¬Even(x)
printf('¬∀ == ∃¬ ?      : %d\n', (~all(Even)) == any(~Even));

⚙Self-Test Quiz

Eight questions spanning the whole course. Click an answer to see instant feedback and an explanation.

§Symbol & Syntax Reference