1. What logic studies
Logic is the study of valid reasoning. In mathematics, it provides the language and rules used to build definitions, state theorems, and prove conclusions from assumptions.
At a high level, logic separates three ideas:
Syntax: the symbols and formulas you are allowed to write.
Semantics: what those formulas mean, and when they are true.
Inference: the rules that let you derive new statements from old ones.
The main goal is to decide whether an argument is valid: if the premises are true, must the conclusion be true?
Two levels of reasoning
| Level | Focus | Example |
|---|---|---|
| Propositional | Whole statements and connectives | $P \to Q$ |
| Predicate | Objects, properties, and quantifiers | $\forall x\, (x > 0 \to x^2 > 0)$ |
Logic is also the foundation for:
Set theory
Algebraic proof techniques
Computer science and Boolean circuits
Formal verification and programming language semantics
2. Propositions and truth values
A proposition is a declarative statement that is either true or false, but not both.
Examples:
"$7$ is prime." is a proposition.
"Close the door." is not a proposition.
"$x > 3$" is not a proposition until $x$ is specified or quantified.
A proposition is assigned one of two truth values:
$T$ for true
$F$ for false
Atomic and compound propositions
Atomic propositions are basic statements such as $P$, $Q$, or $R$.
Compound propositions are built from atomic propositions using logical connectives.
Example:
Truth tables
Truth tables list the truth value of a compound proposition for every combination of inputs.
They are the most direct way to test equivalence or validity for small propositional formulas.
Interactive visual
Truth table explorer
Switch the proposition values and connective to see how the truth table changes row by row.
| P | Q | Value | Row |
|---|---|---|---|
| F | F | F | 1 |
| F | T | F | 2 |
| T | F | F | 3 |
| T | T | T | 4 |
The highlighted row shows the current input combination and output.
3. Logical connectives
The standard connectives are negation, conjunction, disjunction, implication, and biconditional.
Negation
Meaning: "not $P$".
Truth table:
| $P$ | $\neg P$ |
|---|---|
| T | F |
| F | T |
Conjunction
Meaning: "$P$ and $Q$". True only when both parts are true.
| $P$ | $Q$ | $P \land Q$ |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Disjunction
Meaning: "$P$ or $Q$" in the inclusive sense: at least one is true.
| $P$ | $Q$ | $P \lor Q$ |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Implication
Meaning: "if $P$, then $Q$." It is false only when $P$ is true and $Q$ is false.
| $P$ | $Q$ | $P \to Q$ |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
This truth table often surprises people. The statement does not claim that $P$ causes $Q$; it only says the truth of $P$ cannot occur without $Q$.
Equivalent readings of $P \to Q$:
$P$ implies $Q$
If $P$, then $Q$
$P$ only if $Q$
$P$ is sufficient for $Q$
$Q$ is necessary for $P$
Biconditional
Meaning: "$P$ if and only if $Q$." True when both statements have the same truth value.
| $P$ | $Q$ | $P \leftrightarrow Q$ |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
Exclusive or
The exclusive or is often written as $P \oplus Q$.
It is true when exactly one of $P$ and $Q$ is true.
4. Logical equivalence and algebra of propositions
Two propositions are logically equivalent if they have the same truth table.
Write this as:
Equivalent formulas can replace each other in proofs and simplification.
Core equivalences
Double negation
De Morgan's laws
Implication
Contrapositive
Biconditional
Distributive laws
Identity and domination
Idempotent laws
Complement laws
Tautology, contradiction, contingency
A tautology is always true.
A contradiction is always false.
A contingency is sometimes true and sometimes false.
Examples:
is a tautology.
is a contradiction.
Common implication patterns
Converse of $P \to Q$ is $Q \to P$.
Inverse is $\neg P \to \neg Q$.
Contrapositive is $\neg Q \to \neg P$.
Only the contrapositive is logically equivalent to the original implication.
5. Predicates and quantifiers
Predicate logic extends propositional logic by allowing statements about objects.
A predicate is a statement with variables, such as:
When a variable is assigned a value, the predicate becomes a proposition.
Quantifiers
Universal quantifier
Meaning: "for all $x$, $P(x)$ holds."
Existential quantifier
Meaning: "there exists at least one $x$ such that $P(x)$ holds."
Negating quantifiers
Negation flips the quantifier and negates the predicate:
These are among the most important rules in logic.
Order matters
In general,
is not equivalent to
Example:
For every person, there exists a friend.
There exists one person who is friend to everyone.
These say different things.
Domain of discourse
The meaning of a quantified statement depends on the domain.
Example:
is true over the real numbers, integers, and natural numbers, but not meaningful without a specified domain.
6. Rules of inference
Rules of inference describe valid argument forms.
Propositional rules
Modus ponens
Modus tollens
Hypothetical syllogism
Disjunctive syllogism
Addition
Simplification
Conjunction
Resolution
Quantifier rules
Universal instantiation
From $\forall x\, P(x)$, infer $P(c)$ for any specific $c$ in the domain.
Universal generalization
If $P(c)$ is true for an arbitrary element $c$, infer $\forall x\, P(x)$.
Existential instantiation
From $\exists x\, P(x)$, introduce a new symbol $c$ with $P(c)$.
Existential generalization
From $P(c)$, infer $\exists x\, P(x)$.
Valid argument form
An argument is valid when no case exists where all premises are true and the conclusion is false.
To test validity, you can use:
Truth tables for small propositional arguments
Equivalence transformations
Formal proof rules
Counterexamples
7. Proof methods
Direct proof
Assume the hypotheses and derive the conclusion step by step.
Typical structure:
Assume the given premises.
Apply definitions and known theorems.
Reach the desired statement.
Example target:
Assume $P$ and show $Q$.
Contrapositive proof
To prove $P \to Q$, prove the equivalent statement:
This is often useful when the negated conclusion is easier to work with.
Proof by contradiction
Assume the statement is false and derive a contradiction.
To prove $P$, assume $\neg P$ and show an impossibility.
This method is powerful, but do not confuse a contradiction inside the proof with a contradiction in the actual statement.
Proof by cases
Split into exhaustive cases and prove the conclusion in each one.
If $P \lor Q$ is known, prove the result separately under $P$ and under $Q$.
Biconditional proofs
To prove $P \leftrightarrow Q$, prove both directions:
Counterexample
To disprove a universal statement, it is enough to find one counterexample.
Example:
To disprove "all even numbers are prime," use $4$.
8. Normal forms and simplification
Normal forms standardize formulas so they can be compared or processed systematically.
Conjunctive normal form
A formula is in conjunctive normal form (CNF) if it is an AND of OR-clauses.
Example:
Disjunctive normal form
A formula is in disjunctive normal form (DNF) if it is an OR of AND-terms.
Example:
How to simplify a formula
A reliable workflow is:
Remove biconditionals.
Replace implications using $P \to Q \equiv \neg P \lor Q$.
Push negations inward with De Morgan's laws.
Use distributive laws to reach CNF or DNF.
Cancel tautological or contradictory pieces.
Example transformation
Convert
into an equivalent formula.
Solution:
Tautology checking
A formula is a tautology if its negation is unsatisfiable.
Equivalently, to test whether $\phi$ is always true, check whether $\neg \phi$ can ever be true.
9. Logic and sets
Set operations mirror logical connectives closely.
Let $A$ and $B$ be subsets of a universe $U$.
| Logic | Sets |
|---|---|
| $P \land Q$ | $A \cap B$ |
| $P \lor Q$ | $A \cup B$ |
| $\neg P$ | $A^c$ or $U \setminus A$ |
| $P \to Q$ | $A \subseteq B$ |
| $P \leftrightarrow Q$ | $A = B$ |
De Morgan for sets
These are direct analogues of the logical laws.
Subset proof pattern
To prove $A \subseteq B$:
Let $x \in A$ be arbitrary.
Show $x \in B$.
Conclude $A \subseteq B$.
This is the set-theoretic version of a universal implication proof.
10. Satisfiability and consistency
A formula is satisfiable if there exists at least one assignment of truth values that makes it true.
A set of formulas is consistent if all of them can be true at the same time.
Relationships
Unsatisfiable means no assignment makes the formula true.
A contradiction is unsatisfiable.
A tautology is true under every assignment.
Why satisfiability matters
Satisfiability is central in:
Automated theorem proving
Circuit design
Constraint solving
Verification of software and hardware
Quick checks
A formula is unsatisfiable if you can derive both $P$ and $\neg P$ from it, or if every simplification path leads to contradiction.
A formula may be satisfiable even when it is not a tautology.
Example:
is satisfiable but not a tautology.
11. Common pitfalls
Confusing implication with causation
$P \to Q$ is a logical relation, not a causal claim.
Mixing up converse and contrapositive
Only the contrapositive is equivalent to the original implication.
Negating quantifiers incorrectly
Remember:
not $\forall x\, \neg P(x)$.
Ignoring the domain
A quantified statement can change meaning if the domain changes.
Using existential instantiation carelessly
When you instantiate $\exists x\, P(x)$, the symbol you introduce must represent an arbitrary witness, not a special value you are free to reuse later.
Treating "or" as exclusive by default
In mathematics, $\lor$ is usually inclusive unless explicitly stated otherwise.
Assuming converse laws
From $P \to Q$, you cannot conclude $Q \to P$.
12. Problem-solving workflow
When solving a logic problem, work in this order:
Identify whether the task is propositional logic, predicate logic, set logic, or proof construction.
Rewrite the statement into symbols if helpful.
Expand definitions of implication, biconditional, and quantifiers.
Simplify using equivalence laws.
Choose the right proof method.
Check edge cases and counterexamples.
Translate the result back into plain language.
Workflow examples
To prove an implication
If the goal is $P \to Q$:
Assume $P$.
Derive $Q$.
Or prove $\neg Q \to \neg P$.
To disprove a universal claim
If the claim is $\forall x\, P(x)$:
Find one $x$ such that $\neg P(x)$.
To prove equality of sets
Show both inclusions:
To negate a statement
Apply negation rules mechanically:
Flip $\forall$ to $\exists$
Flip $\exists$ to $\forall$
Apply De Morgan's laws
Negate the innermost predicate
13. Formula sheet
Core equivalences
Quantifiers
Standard inference rules
Set analogues
Quick reminders
A universal statement is disproved by one counterexample.
A biconditional needs both directions.
The contrapositive preserves meaning; the converse does not.
Nested quantifiers are order-sensitive.
Always state the domain when quantifiers are involved.
Sources
Stewart, Calculus: Early Transcendentals
Lay, Linear Algebra and Its Applications
Rosen, Discrete Mathematics and Its Applications
Boyce and DiPrima, Elementary Differential Equations and Boundary Value Problems
Blitzstein and Hwang, Introduction to Probability