Logic

Overview

Logic studies form, not content. Two arguments with different topics can share a form, and if the form is valid, every instance is valid; if the form is invalid, a counterexample with true premises and false conclusion refutes it. This is why logicians use symbols: symbols strip away distracting content and reveal form. A proposition is a declarative sentence that is true or false, as opposed to questions, commands, and exclamations, which are not truth-apt. An argument is a set of propositions, the premises, offered in support of another proposition, the conclusion, marked by indicator words like therefore, since, and because, though indicators can mislead and must be checked against the reasoning itself. Validity is a property of the relation between premises and conclusion: an argument is valid when it is impossible for premises to be true and conclusion false at once. Soundness adds true premises to validity. A valid argument can have false premises and a false conclusion, and an invalid argument can have true premises and a true conclusion by accident; neither fact changes validity. Enthymemes are arguments with an unstated premise or conclusion, and charitable reconstruction supplies the missing part in its strongest plausible form before judging validity. Informal fallacies, like ad hominem, straw man, false dilemma, slippery slope, and begging the question, are errors of relevance or presumption rather than of form, and they are distinguished from formal fallacies, like affirming the consequent or denying the antecedent, which are invalid forms. Keep this map in mind: every question in this unit asks either what form an argument has, whether that form is valid, or what method decides the question.

Propositions and categorical syllogism

Categorical propositions relate two classes, the subject class and the predicate class, in four standard forms. The A proposition, all S are P, is universal affirmative: every member of S is in P. The E proposition, no S are P, is universal negative: no member of S is in P. The I proposition, some S are P, is particular affirmative: at least one member of S is in P, where some means at least one and does not exclude all. The O proposition, some S are not P, is particular negative: at least one member of S is outside P. Distribution is the key concept: a term is distributed when the proposition says something about every member of its class. In A, the subject is distributed and the predicate is not; in E, both are distributed; in I, neither is distributed; in O, the predicate is distributed and the subject is not. The square of opposition maps relations between propositions with the same subject and predicate: contradictories, A and O, and E and I, cannot both be true or both false; contraries, A and E, cannot both be true but can both be false; subcontraries, I and O, cannot both be false but can both be true; and subalternation, from universal to particular of the same quality, holds only if the subject class is non-empty, which is the existential import problem that modern logic treats differently from traditional logic. A categorical syllogism has three terms and three propositions: the major premise contains the major term, the predicate of the conclusion; the minor premise contains the minor term, the subject of the conclusion; and the middle term appears in both premises and links them but not in the conclusion. Mood is the sequence of proposition types, such as AAA or EIO, and figure is the position of the middle term: first figure has middle as subject of major and predicate of minor, second figure has middle as predicate in both, third figure has middle as subject in both, and fourth figure has middle as predicate of major and subject of minor. Validity is tested by six rules in the traditional system: the middle term must be distributed at least once, no term distributed in the conclusion may be undistributed in its premise, no syllogism may have two negative premises, a negative premise requires a negative conclusion and vice versa, no syllogism with two particular premises is valid in the modern sense without existential assumptions, and a particular conclusion requires a particular premise in the modern sense. Venn diagrams offer a visual test: shade areas that are empty according to the premises and mark an X in areas that are non-empty, then check whether the conclusion information is already present in the diagram. The fifteen traditionally valid moods, including Barbara, Celarent, Darii, and Ferio in the first figure, are worth memorising as patterns, but the rules and diagrams generalise to any mood, and examination questions often present a syllogism in non-standard word order that must first be translated into standard form before mood and figure can be read off.

Truth-functions and quantification

Propositional logic treats compound statements as truth-functions: their truth value is determined solely by the truth values of their components and the connective used. Negation reverses truth value. Conjunction is true only when both conjuncts are true. Disjunction, in its inclusive sense, is true when at least one disjunct is true, and false only when both are false; exclusive disjunction, true when exactly one is true, must be distinguished and is not the default reading of or in logic. Implication is the most misunderstood connective: p implies q is false only when p is true and q is false, and true in all other cases, including when p is false. This material reading captures the truth-functional core of if then but not its causal or relevance aspects, which is why paradoxes of material implication, like a false antecedent implying anything, surprise beginners. The biconditional is true when both sides share a truth value. A truth table lists every assignment of truth values to atomic propositions and computes the compound value row by row; a tautology is true on every row, a contradiction false on every row, and a contingency true on some rows and false on others. Two statements are equivalent when they share a truth value on every row, and an argument is valid when there is no row where all premises are true and the conclusion false. De Morgan laws state that not p and q is equivalent to not p or not q, and not p or q is equivalent to not p and not q; implication is equivalent to not p or q; and double negation returns the original. Quantification extends this system to domains. The universal quantifier, for all x, states that a property holds for every member of the domain, and the existential quantifier, there exists x, states that it holds for at least one member. Scope matters: for all x there exists y such that x loves y means everyone loves someone, possibly different someones, while there exists y such that for all x, x loves y means one person is loved by everyone, a much stronger claim. Negating quantifiers swaps them: not for all x, P(x) is equivalent to there exists x, not P(x), and not there exists x, P(x) is equivalent to for all x, not P(x). Multiple generality, as in every boy loves some girl, requires careful translation of scope and of which quantifier governs which variable. Identity adds the claim that two terms pick out the same object, and definite descriptions can be analysed with quantifiers and identity, as Russell showed. Quantified logic has no finite truth table, because domains may be infinite, so decision requires proof methods or countermodels rather than brute enumeration.

Symbolic logic and decision procedures

Symbolic logic provides mechanical methods for deciding validity. The truth-table method is a decision procedure for propositional logic: it is finite, since n atomic propositions generate two to the power n rows, and it decides tautology, contradiction, equivalence, and validity by inspection. Its cost is exponential growth, so it is practical for small problems and conceptual for large ones. The truth-tree method, or tableau, is more efficient in practice: to test an argument, list premises and the negation of the conclusion, then decompose compounds by rules that branch when a disjunction or negated conjunction is present and stack when a conjunction or negated disjunction is present. A branch closes when it contains both a statement and its negation; if every branch closes, the original argument is valid, because no assignment makes premises true and conclusion false; if a branch stays open, its literals give a counterexample. Natural deduction proves validity by deriving the conclusion from premises using introduction and elimination rules for each connective: conjunction introduction and elimination, disjunction introduction and elimination by cases, implication introduction by conditional proof and elimination by modus ponens, negation introduction by reductio and elimination by double negation, and biconditional rules. Quantifier rules add universal instantiation, from all to a particular instance; universal generalisation, from an arbitrary instance to all, provided the instance is genuinely arbitrary; existential instantiation, introducing a new name for a witness; and existential generalisation, from an instance to some. The restriction on universal generalisation and existential instantiation is the source of most proof errors: generalising from a name that depends on an assumption, or instantiating two existentials with the same name, produces invalid proofs. Normal forms provide another decision route: every propositional formula can be converted to conjunctive normal form, a conjunction of disjunctions of literals, or disjunctive normal form, a disjunction of conjunctions, by eliminating biconditionals and implications, pushing negations inward by De Morgan laws, and distributing. Satisfiability, whether some assignment makes a formula true, is the dual of validity, and the connection is direct: an argument is valid exactly when the conjunction of premises with the negated conclusion is unsatisfiable. Predicate logic, unlike propositional logic, is undecidable in general: Church and Turing showed no mechanical procedure decides validity for all quantified formulas, though fragments, like monadic predicate logic, are decidable, and proof systems are complete in the sense that every valid formula has a proof, even though no procedure can always find it or always refute invalid ones in finite time. Informal fallacies complete the unit: affirming the consequent, from if p then q and q to p, and denying the antecedent, from if p then q and not p to not q, are invalid forms, while modus ponens and modus tollens are valid. Begging the question assumes the conclusion in a premise, equivocation shifts the meaning of a term mid-argument, and ad hominem attacks the person instead of the argument.

Four categorical propositions

Basic truth-functions