Logic and Propositions

Every proof you will ever read, every line of code a compiler checks, and every legal contract that hinges on "if and only if" rests on the same quiet machinery: propositional and predicate logic. Logic is the study of valid reasoning — how the truth of some statements forces the truth of others, independent of what the statements are actually about. Once you can strip an argument down to its logical skeleton, you can decide whether it holds without being fooled by persuasive wording.

This page teaches that skeleton from the ground up: how to recognize a proposition, how connectives combine them, how truth tables mechanize reasoning, why "if... then" behaves so strangely, and how quantifiers let us make claims about entire universes of objects. Master this and the rest of discrete mathematics — proofs, sets, Boolean algebra, circuit design — becomes far less mysterious.

Learning Objectives

• Distinguish propositions from sentences that have no truth value.
• Build and read truth tables for the five core connectives.
• Translate English implications into logic and identify converse, inverse, and contrapositive.
• Prove logical equivalences and recognize tautologies and contradictions.
• Use universal and existential quantifiers and negate them correctly.
• Trace how Boole and Frege turned reasoning into a calculus.

Quick Answer

A proposition is a declarative statement that is definitely either true or false, never both. We combine propositions using connectives: NOT ($\neg$), AND ($\wedge$), OR ($\vee$), IMPLIES ($\rightarrow$), and IF-AND-ONLY-IF ($\leftrightarrow$). A truth table lists every combination of input truth values and the resulting output, letting us compute meaning mechanically. Two statements are logically equivalent when they have identical truth tables; a statement always true is a tautology. Quantifiers extend this to statements about many objects: "for all" ($\forall$) and "there exists" ($\exists$). Together these tools let us express and verify arguments with the precision of arithmetic.

Where It Came From

For over two thousand years, "logic" meant Aristotle's syllogisms — rigid verbal templates like "All men are mortal; Socrates is a man; therefore Socrates is mortal." It worked, but it was clumsy: arguments had to be squeezed into a handful of fixed forms, and there was no way to calculate whether a complicated argument was valid.

The breakthrough came from a specific frustration: mathematicians in the 1800s wanted reasoning itself to be as reliable and mechanical as algebra. In 1847, and more fully in his 1854 book An Investigation of the Laws of Thought, the English mathematician George Boole made the daring move of treating logic as algebra. He let symbols stand for classes or propositions and defined operations on them so that "and," "or," and "not" obeyed algebraic-style laws. Suddenly you could solve logical problems the way you solve equations. This is the direct ancestor of the Boolean algebra inside every digital computer.

Boole's system, however, could not gracefully handle statements like "every number has a successor," where the reasoning depends on quantity and the relationship between objects. In 1879 the German logician Gottlob Frege published Begriffsschrift ("concept-script"), inventing the notation of quantifiers and variables and building the first true predicate logic. Frege's goal was ambitious — to show that all of arithmetic could be derived from pure logic. That program ran into trouble (Russell's paradox), but the language Frege created became the foundation of all modern logic, mathematics, and computer science. Boole gave us the calculus of true/false; Frege gave us the grammar of "all" and "some."

Propositions and the Five Connectives

A proposition is a declarative sentence with a definite truth value.

• "7 is a prime number." — proposition (true).
• "The Moon is made of cheese." — proposition (false).
• "Is it raining?" — not a proposition (a question).
• "$x + 2 = 5$." — not a proposition on its own; its truth depends on $x$. This is a predicate, resolved later by quantifiers.

We denote propositions with letters $p, q, r$ and combine them with logical connectives:

Name	Symbol	English	True when...
Negation	$\neg p$	"not $p$"	$p$ is false
Conjunction	$p \wedge q$	"$p$ and $q$"	both are true
Disjunction	$p \vee q$	"$p$ or $q$"	at least one is true
Implication	$p \rightarrow q$	"if $p$ then $q$"	see below
Biconditional	$p \leftrightarrow q$	"$p$ if and only if $q$"	both have the same value

Note that mathematical "or" is inclusive: $p \vee q$ is true even when both are true. Everyday "coffee or tea" is usually exclusive, which is a common source of confusion.

Worked example. Let $p$ = "It is cold" and $q$ = "It is raining." Then $\neg p \wedge q$ reads "It is not cold and it is raining," which is true only on a warm, rainy day. If today is cold and dry, then $p$ is true and $q$ is false, so $\neg p$ is false, and $\neg p \wedge q$ is false.

Truth Tables

A truth table enumerates every possible assignment of truth values to the inputs. With $n$ propositions there are $2^n$ rows. Here are the five core connectives:

$p$	$q$	$\neg p$	$p \wedge q$	$p \vee q$	$p \rightarrow q$	$p \leftrightarrow q$
T	T	F	T	T	T	T
T	F	F	F	T	F	F
F	T	T	F	T	T	F
F	F	T	F	F	T	T

Worked example — a compound statement. Let us build the table for $(p \wedge q) \rightarrow p$.

$p$	$q$	$p \wedge q$	$(p \wedge q) \rightarrow p$
T	T	T	T
T	F	F	T
F	T	F	T
F	F	F	T

The last column is true in every row. A statement that is true under every assignment is a tautology. One false in every row is a contradiction (for example, $p \wedge \neg p$). Everything else is a contingency.

Implication: The Trickiest Connective

The implication $p \rightarrow q$ ("if $p$, then $q$") is where most students stumble. Look again at its truth table: it is false in only one situation — when the hypothesis $p$ is true but the conclusion $q$ is false. In particular, when $p$ is false, $p \rightarrow q$ is automatically true, regardless of $q$. This is called vacuous truth.

Why? Think of a promise: "If you finish your homework, I'll give you $5." The only way you can accuse me of breaking that promise is if you finish the homework ($p$ true) and I withhold the money ($q$ false). If you never finish the homework, I have broken no promise no matter what I do — the statement stays true.

From any implication we can form three relatives. Let $p \rightarrow q$ be "If it is a dog, then it is a mammal."

Name	Form	Statement
Original	$p \rightarrow q$	If dog, then mammal (true)
Converse	$q \rightarrow p$	If mammal, then dog (false)
Inverse	$\neg p \rightarrow \neg q$	If not dog, then not mammal (false)
Contrapositive	$\neg q \rightarrow \neg p$	If not mammal, then not dog (true)

Key fact: a statement and its contrapositive are always logically equivalent, and the converse and inverse are equivalent to each other. Confusing a statement with its converse is one of the most common reasoning errors in everyday life.

Logical Equivalence

Two compound statements are logically equivalent, written $P \equiv Q$, when they have the same truth value in every row of the truth table. Equivalences are the "algebraic identities" of logic. The most important are De Morgan's laws:

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

In words: "not (A and B)" means "not A or not B." Negating "and" flips it to "or," and each piece gets negated.

Worked example — verify a De Morgan law.

$p$	$q$	$p \wedge q$	$\neg(p \wedge q)$	$\neg p$	$\neg q$	$\neg p \vee \neg q$
T	T	T	F	F	F	F
T	F	F	T	F	T	T
F	T	F	T	T	F	T
F	F	F	T	T	T	T

The fourth and last columns match in every row, so $\neg(p \wedge q) \equiv \neg p \vee \neg q$. A second essential equivalence rewrites implication using only OR and NOT:

$p \rightarrow q \equiv \neg p \vee q$

This identity is how logic gates and SAT solvers handle implications internally.

Quantifiers

Predicates like $P(x): x > 3$ have no truth value until we say which $x$ we mean. Quantifiers do this over a domain of discourse.

• Universal quantifier $\forall x\, P(x)$: "for all $x$, $P(x)$." True only if $P$ holds for every element.
• Existential quantifier $\exists x\, P(x)$: "there exists $x$ such that $P(x)$." True if $P$ holds for at least one element.

Worked example. Domain = the integers.

• $\forall x\,(x^2 \ge 0)$ is true — every integer squared is nonnegative.
• $\forall x\,(x > 0)$ is false — a single counterexample, say $x = -1$, kills a universal claim.
• $\exists x\,(x^2 = 9)$ is true — witness $x = 3$ (or $x = -3$).
• $\exists x\,(x^2 = 2)$ is false — no integer squares to 2.

Negating quantifiers follows a clean rule: push the negation inside and flip the quantifier.

$\neg \forall x\, P(x) \equiv \exists x\, \neg P(x)$ $\neg \exists x\, P(x) \equiv \forall x\, \neg P(x)$

So the negation of "all swans are white" is not "no swans are white" — it is "there exists a swan that is not white." One black swan is enough. Order also matters when quantifiers mix: $\forall x\, \exists y\,(y > x)$ ("every number has something bigger," true for integers) is very different from $\exists y\, \forall x\,(y > x)$ ("some number is bigger than everything," false).

Real-World Applications

• Digital circuits. Every logic gate (AND, OR, NOT, NAND) is a physical connective. Boolean algebra minimizes gate count, directly shrinking chip size and power draw.
• Programming. Conditionals, loop guards, and short-circuit evaluation (&&, ||) are propositional logic. De Morgan's laws are used constantly to simplify and correctly negate conditions.
• Databases. SQL WHERE clauses are predicate logic; query optimizers rewrite them using logical equivalences to run faster.
• Formal verification. Aerospace and cryptographic software is proven correct by SAT/SMT solvers that mechanically check propositional formulas over billions of cases.
• Law and contracts. "Unless," "provided that," and "if and only if" have precise logical meanings; ambiguity between a condition and its converse causes real disputes.

Common Mistakes

1. Confusing a statement with its converse. Students assume "if $p$ then $q$" also means "if $q$ then $p$." Wrong: "if it rains, the ground is wet" does not imply "if the ground is wet, it rained" (a sprinkler wets it too). Correction: only the contrapositive is guaranteed equivalent.

2. Reading "or" as exclusive. Learners mark $p \vee q$ false when both are true. Wrong: mathematical OR is inclusive, true when at least one holds. Correction: exclusive or (XOR) is a separate connective, false when both are true.

3. Negating a universal into another universal. People negate "all students passed" as "all students failed." Wrong: the true negation is "some student did not pass." Correction: apply $\neg\forall x\,P(x) \equiv \exists x\,\neg P(x)$ — negation flips the quantifier and negates the predicate.

Comparison and Connections

Concept	Deals with	True when	Key tool
Proposition	fixed statement	inherently T or F	truth value
Predicate	statement with a variable	undefined until bound	quantifier
Implication $\rightarrow$	conditional	false only if T$\rightarrow$F	contrapositive
Biconditional $\leftrightarrow$	equivalence of two props	both same value	truth table
Logical equivalence $\equiv$	two whole formulas	identical truth tables	De Morgan, algebra

Propositional logic is the foundation for Boolean algebra and set theory (AND/OR mirror intersection/union), while predicate logic with quantifiers underlies all rigorous mathematical proof and the design of proof techniques like induction and contradiction.

Practice Questions

Recall

State the one row of the truth table where $p \rightarrow q$ is false. Answer: When $p$ is true and $q$ is false.

Understanding

Write the contrapositive of "If a number is divisible by 6, then it is divisible by 3," and say whether it is true. Answer: "If a number is not divisible by 3, then it is not divisible by 6." True — it is equivalent to the original, which is true.

Application

Use a truth table to decide whether $p \rightarrow q$ and $\neg q \rightarrow \neg p$ are equivalent. Guidance: Build both columns. They match T, F, T, T across the four rows, confirming a statement and its contrapositive are equivalent.

Analysis

Negate the statement $\forall x\, \exists y\,(x + y = 0)$ over the integers and determine which version is true. Answer: The negation is $\exists x\, \forall y\,(x + y \ne 0)$. The original is true (each $x$ has additive inverse $y = -x$), so its negation is false.

FAQ

Is "This sentence is false" a proposition? No. If it were true it would be false, and vice versa — it has no consistent truth value. Such self-referential paradoxes are excluded from propositional logic.

Why is a false hypothesis considered to make an implication true? Because an implication only promises something when the hypothesis holds. If the hypothesis is false, no promise is engaged, so nothing was broken — we default to true. This "vacuous truth" keeps the logic consistent.

What is the difference between $\rightarrow$ and $\leftrightarrow$? $p \rightarrow q$ is one-directional: $p$ guarantees $q$ but not the reverse. $p \leftrightarrow q$ requires both directions, so it is true exactly when $p$ and $q$ share the same truth value.

How do I know if two statements are logically equivalent? Build their truth tables. If the final columns are identical in every row, they are equivalent. Alternatively, transform one into the other using known laws like De Morgan's and $p \rightarrow q \equiv \neg p \vee q$.

Does the order of quantifiers really matter? Yes, when you mix $\forall$ and $\exists$. "For every person there is a mother" is true; "there is one mother of every person" is false. Swapping the order can change truth entirely.

Quick Revision

• Proposition: declarative statement, definitely T or F.
• Connectives: $\neg$ (not), $\wedge$ (and), $\vee$ (inclusive or), $\rightarrow$ (implies), $\leftrightarrow$ (iff).
• Implication false only when T $\rightarrow$ F; equivalently $p \rightarrow q \equiv \neg p \vee q$.
• Contrapositive $\neg q \rightarrow \neg p$ is equivalent to $p \rightarrow q$; converse and inverse are not.
• De Morgan: $\neg(p \wedge q) \equiv \neg p \vee \neg q$ and $\neg(p \vee q) \equiv \neg p \wedge \neg q$.
• Tautology = always true; contradiction = always false.
• Quantifier negation: $\neg\forall x\,P \equiv \exists x\,\neg P$; $\neg\exists x\,P \equiv \forall x\,\neg P$.
• Truth table for $n$ propositions has $2^n$ rows.

Related Topics

Prerequisites

• Discrete Mathematics overview

Related Topics

• Set Theory (AND/OR mirror intersection and union)
• Boolean Algebra (the algebra of true/false and digital circuits)

Next Topics

• Proof techniques: induction, contradiction, and contrapositive proofs
• Mathematics subject index