Logic

What logic studies

Logic asks when a conclusion really follows from what you already accept. Its building block is the statement: a complete sentence making a claim that is either true or false.^{[1, 8]} In an argument, the statements offered in support are the premises, and the judgment drawn from them is the conclusion.^[1]

Today logic is a branch of both mathematics and philosophy,^[11] and a central branch of computer science.^[11]

How it works: connectives and truth tables

Simple statements are joined into compound statements by connectives.^[2] Each one is defined by a rule for when the result is true:

• Not (negation, ~p) flips the truth value: when p is true, ~p is false, and the other way round.^{[1, 3]}
• And (conjunction, p ∧ q) is true only when both parts are true.^{[2, 3]}
• Or (disjunction, p ∨ q) means the inclusive or unless stated otherwise: it is false only when both parts are false.^{[2, 3]}
• If p, then q (the conditional, p → q) is false only when p is true and q is false.^{[2, 4]}
• p if and only if q (the biconditional, p ↔ q) is true when p and q match: both true or both false.^[2]

The symbols follow the OpenStax textbook listed in the sources.

A truth table lists all the possible truth values of the parts of a statement, and the result for each.^[3] Two statements give 2 × 2 = 4 combinations, by the multiplication principle.^[3]

p	q	p ∧ q	p ∨ q	p → q	p ↔ q
T	T	T	T	T	T
T	F	F	T	F	F
F	T	F	T	T	F
F	F	F	F	T	T

For example, take p: 4 + 7 = 11, q: 11 − 3 = 7 and r: 7 × 11 = 77.^[3] Since 11 − 3 is 8, q is false while p and r are true, so “p and r” is true but “p and q” is false.^[3]

Two statements are logically equivalent when the biconditional joining them is true in every row of its truth table.^[5] De Morgan’s laws are examples: “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”.^[6] An if-then statement is also equivalent to its contrapositive, “if not q, then not p”.^[5]

Statements about groups use quantifiers such as all, some and none: all squares are rectangles, only some rectangles are squares, and no squares are circles.^[1]

Valid, sound, deductive, inductive

An argument is valid if its conclusion follows from its premises, whether those premises are true or false.^[3] It is sound if it is valid and all its premises are true.^{[7, 12]}

Deductive arguments draw specific conclusions from general premises, while inductive arguments draw a general conclusion from a pattern of specific cases.^[7] Familiar valid deductive arguments include syllogisms such as: “All humans are living beings. All living beings are mortal. Therefore, all humans are mortal.”^[12]

Some argument forms are always valid. The law of detachment (modus ponens) says that if “p → q” and p are both true, then q must be true.^[7] Another valid form is modus tollens, the law of denying the consequent.^[7] Because “if p, then q” is equivalent to “if not q, then not p”, learning that q is false lets you conclude that p is false.^{[5, 7]}

Induction works differently. Seeing the sun rise in the east every day so far leads to the conclusion that it will rise there tomorrow.^[12] Unlike deduction, induction is thought to be ampliative: its conclusion goes beyond what the premises contain.^[12] That is why inductive arguments are usually judged strong or weak rather than proved.^[1]

Logic and proof

An axiom is a statement accepted as true without proof.^{[8, 10]} A proof is a sequence of logical deductions from axioms and previously proved statements, and a statement that has been proved is a theorem.^{[8, 10]} This approach, going back to Euclid and now called the axiomatic method, remains the foundation of mathematics today.^[8]

Checking examples is not proof. The formula n² + n + 41 gives a prime number for every n from 0 up to 39, where it gives 1,601.^[8] But you can’t check a claim about an infinite set by checking a finite set of its elements, however large.^[8] Yet n = 40 gives 40² + 40 + 41 = 1,681 = 41 × 41, which is not prime.

History

Aristotle’s logical works contain the earliest formal study of logic that we have.^[13] His theory of the syllogism deals with inferences from two premises, each a categorical sentence, sharing exactly one term.^[13] The Stanford Encyclopedia of Philosophy notes that very few today would call it an adequate basis for understanding science, mathematics or even everyday reasoning.^[13]

George Boole (1815–1864) reduced logic to an algebra, bringing it into mathematics, first in The Mathematical Analysis of Logic (1847).^{[14, 17]} His Laws of Thought followed, dated 1854 by MacTutor and 1853 by OpenStax.^{[17, 6]} Claude Shannon described an interpretation of propositional logic in which sentence letters stand for circuits, and his work greatly helped circuit design.^[15]

In 1879, Gottlob Frege published his Begriffsschrift (“Concept Script”), the first presentation of what we would now recognise as a logical system with negation, implication and universal quantification.^{[18, 16]} Frege aimed to show that mathematics is reducible to logic, a thesis called logicism, but Russell pointed out that the Russell paradox gave a contradiction in Frege’s system of axioms.^[18]

Common misconceptions

“A valid argument has a true conclusion.” An argument can be valid without being true.^[7] Soundness is the extra requirement that every premise is true.^{[7, 12]}

“If an argument sounds convincing, it must be good.” A false or deceptive argument is called a fallacy.^[7] Hasty generalization presents a weak inductive argument;^[7] equivocation exploits the ambiguity of a word; and appeal to authority cites an authority instead of giving reasons.^[12]

Going further

On this map, logic sits beside Geometry and Philosophy. The free Stanford Encyclopedia of Philosophy, listed below, goes deeper.