Visual Tools
Calculators
Tables
Mathematical Keyboard
Converters
Other Tools

Semantics




Introduction to Semantics in Propositional Logic

The semantics of propositional logic concerns the meaning of logical expressions—specifically, how their truth values are determined under different interpretations. This page introduces the foundational semantic concepts necessary to evaluate, categorize, and reason about logical formulas.

You will begin by exploring the truth-functional nature of propositional logic: how the truth value of a compound proposition is derived from its components. From there, the page discusses how propositions can be classified as tautologies (always true), contradictions (always false), or contingent (true in some cases, false in others).

You will also examine logical equivalences, which identify when two expressions always yield the same truth value, and are fundamental to simplifying and transforming logical formulas.

A dedicated section on logical implication explains conditional statements like "p→qp \rightarrow q" in both syntactic and semantic terms. Common misconceptions, properties of implication, and its use in proofs are addressed clearly.

Each section is supported by examples, truth tables, and conceptual explanations designed to connect formal definitions to intuitive reasoning. Together, these topics form a complete picture of how meaning is assigned to logical statements in propositional systems.


Logical Equivalences

Logical equivalence is a relation between two statements in propositional logic that have the same truth value for every combination of truth values of their individual components.
If two propositions AA and BB are logically equivalent, we write:A≡BA≡B.
This means that for every possible truth assignment,AA and BB yield the same truth value.
Pitfall: Checking only some rows
Calling p→qp \to q and q→pq \to p equivalent because they agree at p=q=Tp = q = T and p=q=Fp = q = F misses the row p=Tp = T, q=Fq = F, where p→qp \to q is F and q→pq \to p is T. One differing row is enough, so they are not equivalent.
To test two formulas for equivalence, build one truth table with a column for each formula and compare the two columns row by row. With nn variables the table has 2n2^n rows, so two variables give four rows and three variables give eight. The verdict depends on all of these rows taken together, not on any single one of them.
Logical equivalences form the foundation of propositional logic laws. Many logical laws are logical equivalences that help us simplify, manipulate, or prove logical expressions.
However, not all logical equivalences are laws. Some are specific derivations that are still true but are not considered "fundamental" enough to be named as laws.
Fact: Sixty letters outlast any truth table
Each new letter doubles the rows: 3030 letters already give 230=1,073,741,8242^{30} = 1{,}073{,}741{,}824 rows, and 6060 letters give more than 101810^{18}. Checked at a million rows a second, that table would take about 36,50036{,}500 years.
Logical equivalences are essential in mathematical logic, shaping both syntax and semantics. Syntactically, they allow transformations between logically identical formulas, crucial for normal forms like CNF and DNF. Semantically, they ensure truth preservation across interpretations, making them fundamental in truth tables and model theory. In proof techniques, equivalences justify valid transformations within formal systems, aiding in inferences and proof simplifications. By bridging truth conditions with formal derivations, logical equivalences unify reasoning in propositional logic, predicate logic, and beyond.
Check our equivalence validator tool to polish your practical understanding of logical equivalences.

Learn More

Contingency, Tautology or Contradiction

Some formulas are true whatever their letters stand for, some can never be true, and most depend on the facts.
In classical propositional logic, every proposition falls into one of three categories based on its truth value across all possible interpretations:
The truth-table column of a formula shows which of the three it is.
formulap = T, q = Tp = T, q = Fp = F, q = Tp = F, q = Fcolumn
p ∨ ¬pTTTTall T
p ∧ ¬pFFFFall F
p ∨ qTTTFmixed
p ∧ qTFFFmixed
Only the whole column decides. p∧qp \land q is F in three rows, but it is T in the first one, so it is not always false.
All T, all F, or a mixture — there is no fourth possibility.
These three categories exhaust all possibilities for a proposition in classical logic. Every proposition must be one of these.
The definition
A proposition is a tautology when it is true in every row of its truth table, a contradiction when it is false in every row, and a contingency when it is true in some rows and false in others.
To place a formula in one of the three categories, evaluate it in every row of its truth table and look at the whole column of results. A column with T in every row marks a tautology, and a column with F in every row marks a contradiction. Any mixture of T and F, however uneven, marks a contingency.
So p∨¬pp \lor \neg p is a tautology, p∧¬pp \land \neg p is a contradiction, and p∨qp \lor q and p∧qp \land q are contingencies.
Each category matches a property: tautologies are valid, contradictions are unsatisfiable, contingencies are satisfiable.

1. Tautology

A proposition that is always true, no matter what.
Example
                                                p∨¬pp \lor \neg p
("Either it will rain or it won’t"—this is always true.)
Validity and Tautologies
A proposition is valid if it is true in all possible interpretations—in other words, if it is a tautology.
If a proposition is valid, it means there is no possible scenario where it is false.

p∨¬pp∨¬p
(Law of the Excluded Middle) is valid because it’s always true.

2. Contradiction

A proposition that is always false, no matter what.
Example
                                                p∧¬pp \land \neg p
("It is raining and it is not raining"—this is never true.)
Unsatisfiability and Contradictions
A proposition is unsatisfiable if it is false in every possible interpretation—which means it is a contradiction.

p∧¬pp∧¬p is unsatisfiable because there is no way to make it true.

3. Contingency

A proposition that is sometimes true and sometimes false, depending on the values of its variables. Example:

p∨qp \lor q
(If p is "It will rain" and q is "It will snow," this can be true or false depending on the weather.)
Satisfiability and Contingencies
A proposition is satisfiable if there is at least one interpretation where it is true. Otherwise it would be a contradiction.
A contingent proposition (one that is sometimes true and sometimes false) is always satisfiable because it has at least one true case.

p∨qp∨q is satisfiable because it’s true in cases where either pp or qq is true.
Understanding Propositional Logic CategoriesContingencyTautologyPropositions that can be true or falsePropositions that are always trueContradictionPropositions that are always false
Not always true does not mean always false — and proving "never true" takes every row.
Pitfall: Treating not always true as always false
Calling p∧qp \land q a contradiction because it is F in three of its four rows ignores the row p=Tp = T, q=Tq = T, where it is T. Not a tautology only means F in at least one row; p∧qp \land q is a contingency.
Sorting a formula into its category is a search over assignments. A single row with T is enough to show that a formula is satisfiable, and that row is checked in moments once it has been found. Showing that a formula is unsatisfiable is harder: every one of the 2n2^n rows has to come out F, and the number of rows doubles with each new variable.
Fact: The first NP-complete problem
Deciding whether a formula is satisfiable was the first problem proved NP-complete, by Stephen Cook in 1971. A fast method for it would give a fast method for every problem whose answers can be checked quickly, and none is known.
The rest of the page covers logical implication and common pitfalls.

Logical Implication

Logical implication is a core semantic construct in propositional logic, expressing conditional relationships between propositions. The implication page introduces the formal definition of implication (p→qp \rightarrow q), along with common notation styles used in logic and mathematics.

A truth table illustrates how implication behaves under all combinations of truth values for its components. From there, several key properties are discussed, including reflexivity, transitivity, contraposition, and the equivalence to the disjunction form (¬p∨q\neg p \lor q). These properties are essential for both understanding logical behavior and applying simplification techniques in formal proofs.

To aid learners, the page also addresses common misconceptions—such as the counterintuitive truth of implications with false antecedents—and provides clarification on why implication is not a symmetric relationship.

Finally, the practical role of implication in proof strategies is outlined, emphasizing its use in direct reasoning, contrapositive arguments, and proofs by contradiction. Altogether, this resource provides a well-rounded foundation for understanding how conditional statements function within the semantic framework of propositional logic.
Learn More

Common Pitfalls

Two slips account for many wrong answers on the topics of this page. Each is marked where it happens in the sections above; here each is worked through in full, with the wrong and the right working side by side.
DownloadPNG2×PDF
1Checking only some rows
Two formulas are tested for equivalence on a few rows only, and because they agree there, they are called equivalent. Equivalence asks for the same truth value in every row of the truth table, so a single row where they differ settles the question.
Start
For p→qp \to q and q→pq \to p, the row p=Tp = T, q=Tq = T gives T and T, and the row p=Fp = F, q=Fq = F gives T and T.
Wrong turn
Error here
The formulas agree in both rows, so they are called equivalent.
Right path
List all four rows for (p,q)(p, q), namely (T,T)(T, T), (T,F)(T, F), (F,T)(F, T), (F,F)(F, F). The column of p→qp \to q is T, F, T, T and the column of q→pq \to p is T, T, F, T. The columns differ in the rows (T,F)(T, F) and (F,T)(F, T), so p→q≢q→pp \to q \not\equiv q \to p.
Why it happensThe rows where both variables have the same value are the first ones that come to mind, and there the two formulas look alike. The rows with mixed values are exactly the ones that tell them apart.
How to checkCount the rows before comparing: 2n2^n rows for nn variables. Equivalence holds only if the two columns match in all of them, which is the same as the biconditional of the two formulas being a tautology.
2Treating not always true as always false
A formula that is not a tautology is put straight into the contradiction category. Not being always true only means being false in at least one row; the formula may still be true in other rows, and then it is a contingency.
Start
p∧qp \land q is F at p=Tp = T, q=Fq = F, at p=Fp = F, q=Tq = T and at p=Fp = F, q=Fq = F.
Wrong turn
Error here
It is not a tautology, so it is called a contradiction and unsatisfiable.
Right path
The column of p∧qp \land q for (T,T)(T, T), (T,F)(T, F), (F,T)(F, T), (F,F)(F, F) is T, F, F, F. The single T in the row p=Tp = T, q=Tq = T makes it satisfiable, and the three F values make it not a tautology. It is a contingency.
Why it happensTautology and contradiction are presented as a pair of opposites, so the middle category is easy to forget. A column that is mostly F also looks like a column that is all F.
How to checkLook for one row with T and one row with F. If both exist, the formula is a contingency; only a column with no T at all marks a contradiction.
Common pitfalls in semantics·/logic/propositional-logic/semanticsLearn Math Class
Both slips stop the truth table early. An equivalence must hold in all 2n2^n rows, and a formula that is not a tautology is a contradiction only if no row at all makes it true. Counting the rows first, then looking for one T and one F, catches both.

Skills You Should Learn

Each skill opens its step-by-step method page.
Logic methods
  • Build a truth tableList all 2n2^n rows, add one column per subformula from the inside out, and fill each column with the rule of its connective.
  • Check whether a formula is a tautologyShow a formula is true in every row: build its truth table, or assume one row makes it false and reach a clash.
  • Check whether a formula is a contradictionShow a formula is false in every row with a truth table, or reduce it with the laws to a clash of the form A∧¬AA \land \neg A.
  • Rewrite an implication without the arrowSingle ruleAn arrow has to go before you can use De Morgan, distribute, or reach a normal form: P→QP \to Q, (P∧Q)→R(P \land Q) \to R, ¬P→Q\neg P \to Q.

Semantics FAQ

How many rows does a truth table have?

+
2n2^n for a formula with nn letters, since each letter can be T or F independently of the others: two letters give 44 rows and three give 88. Every new letter doubles the count, so 3030 letters already give 230=1,073,741,8242^{30} = 1{,}073{,}741{,}824 rows, and 6060 letters give more than 101810^{18}. Checked at a million rows a second, that table would take about 36,50036{,}500 years.Read more →

Are two formulas equivalent if they agree on a few rows?

+
No. Equivalence needs the same truth value in every one of the 2n2^n rows, and one row where they differ settles it. p→qp \to q and q→pq \to p agree at p=q=Tp = q = T and at p=q=Fp = q = F, but at p=Tp = T, q=Fq = F the first is F and the second is T. Their full columns, T, F, T, T against T, T, F, T, differ in two rows. Two formulas are equivalent exactly when their biconditional is a tautology.Read more →

Why is it easier to show a formula is satisfiable than unsatisfiable?

+
Because the first needs one row and the second needs every row. A single assignment that makes the formula T proves it satisfiable, and once found, that row is checked in moments: for p∧qp \land q, the row p=Tp = T, q=Tq = T is enough. Proving a formula unsatisfiable means showing that all 2n2^n rows come out F, and the number of rows doubles with each new letter.Read more →

What was the first NP-complete problem?

+
Satisfiability: deciding whether a propositional formula is true in at least one row of its truth table. Stephen Cook proved it NP-complete in 1971. A fast method for it would give a fast method for every problem whose answers can be checked quickly, and none is known. Trying every row is not fast: a formula with nn letters has 2n2^n rows.Read more →