eduKateSG · Mathematical Logic · Worked learning guide
Find the reasoning step you need
Separate an impossible set of requirements from a false individual claim, locate a minimal conflict and repair the premises without hiding what changed.
1. Ask whether the premises can be true together
3. Find a conflict that no pairwise check reveals
5. Understand classical explosion without treating it as evidence
7. Test a quantified conflict with a shared witness
9. Practise with conflict certificates and repairs
Full chapter index · Practice and checking · Mathematical Logic subject guide
Several individually possible requirements can become impossible when combined. Mathematical logic gives a precise question for that situation: is there one interpretation in which all the requirements hold together?
This guide separates satisfiability, proof-theoretic consistency and truth in a chosen model. It uses original examples to show how a conflict can be distributed across several premises, why a minimal conflict is not necessarily the smallest one, and what a repair actually changes.
The setting is classical propositional and first-order logic with standard nonempty domains. Start with Mathematical Logic for the wider subject. The practical aim is to identify the exact combination that fails, then state the evidence or priority needed before changing it.
Chapter index
Chapters 1–4
Chapters 5–8
Chapters 9–10
A set Γ of sentences is satisfiable when at least one interpretation makes every sentence in Γ true. Such an interpretation is a model of Γ. Unsatisfiable means there is no common model.
This is not the same as asking whether each sentence has some model of its own. The witnesses must be shared across the whole set.
Let p mean a room is open and q mean a supervisor is present. Consider p, p → q, and ¬q. The first requires an open room; the second requires supervision whenever it is open; the third rules out supervision. No truth assignment satisfies all three.
Each sentence alone is satisfiable. Each pair is also satisfiable. The conflict appears only when all three are combined.
Supply a model when one exists
For {p → q, ¬q}, set p = false and q = false. Both premises are true. Adding p destroys satisfiability.
A model is a concrete certificate of compatibility in this small propositional case. Check every premise in the same assignment. Switching assignments between premises does not provide a common model.
For first-order sentences, the common interpretation must also share its domain, predicate meanings, name assignments and functions. A premise about P cannot quietly change P’s meaning to accommodate another premise.
The gold standard is to state what counts as one shared setting. Requirements referring to different dates, rooms or people may need separate variables or relation arguments. A contradiction produced by accidentally merging different contexts is a translation problem, rather than a discovered impossibility in the original situation.
Satisfiability is semantic: it concerns models. Proof-theoretic consistency concerns what a specified calculus derives. In a standard classical calculus, one formulation says Γ is consistent when Γ does not derive a contradiction symbol ⊥.
For a sound and complete first-order proof calculus with the intended classical semantics, these notions agree: Γ is satisfiable exactly when it is consistent. The equivalence depends on the connection between the proof system and its semantics.
A weak or unsound rule system should not inherit this guarantee merely because its rules are written formally. The proof-theoretic claim must identify the calculus.
Truth in one model is another question
A satisfiable set may be false in the particular model that describes the current situation. For example, {p} has a model, but it is false under an assignment where p is false.
Thus a successful compatibility check does not establish that the premises accurately describe the world. It establishes that their joint truth is possible under the specified semantics.
A useful report separates three results: a common model exists, the formal system does not derive contradiction, and the factual premises have supporting evidence. The first two can be connected by metatheorems; the third still requires observation or other evidence.
This distinction matters when using logic to review a plan. A compatible plan can be impractical, unaffordable or based on inaccurate assumptions. Logic can reveal a contradiction without supplying every fact needed for a decision.
The repair is to give each assessment its proper name. “Consistent” should not become a general compliment meaning true, complete, fair or operationally ready.
Consider Γ = {p, p → q, q → r, ¬r}. If p is true, q follows; then r follows, contradicting ¬r. The set is unsatisfiable.
Remove any one premise and a model becomes available. Without p, choose p = q = r = false. Without p → q, choose p = true, q = r = false. Without q → r, choose p = q = true and r = false. Without ¬r, choose all three true.
| Premise removed | p | q | r |
|---|---|---|---|
| p | False | False | False |
| p → q | True | False | False |
| q → r | True | True | False |
| ¬r | True | True | True |
These assignments verify that every proper subset is satisfiable: any smaller proper subset lies inside one of the displayed three-premise subsets, whose model also satisfies the smaller subset.
The conflict is therefore spread across a chain. Looking only for a visibly adjacent sentence and its negation would miss it.
Pairwise compatibility is weaker
Every pair in Γ is satisfiable, but the full set is not. Pairwise tests can be useful diagnostics while remaining insufficient for joint compatibility.
An analogous mistake arises when separate teams each approve two requirements without checking the combined specification. The formal example does not claim every real planning conflict has this exact shape; it isolates why local agreement need not combine globally.
A complete explanation should show the contradiction and the removal models. The contradiction proves incompatibility. The models prove that every listed premise contributes to this particular minimal conflict.
A minimal unsatisfiable subset is unsatisfiable, but removing any one of its premises makes it satisfiable. Minimal describes inclusion: no proper subset remains a conflict.
A minimum-cardinality unsatisfiable subset has the fewest premises among all unsatisfiable subsets of the full set. It is minimal, but another minimal conflict can contain more premises.
For an original example, let Δ contain {p, ¬p} as well as {q, q → r, ¬r}. The pair {p, ¬p} is a two-premise minimal conflict. The three-premise set involving q and r is also minimal.
The minimum conflict size is two, yet a procedure could correctly return the three-premise minimal conflict. Its output would be minimal without being smallest.
What a conflict report should say
State whether the returned set is merely unsatisfiable, inclusion-minimal, or guaranteed smallest by cardinality. A label such as “the core” may conceal this distinction.
There may also be several different conflicts. Repairing one does not guarantee the whole premise set becomes satisfiable. In Δ, removing p fixes the first conflict but leaves the q–r conflict intact.
A robust repair rechecks the entire revised set. It also records which premises were changed and why. The mathematical core identifies a tension; it does not decide which factual claim or policy should be abandoned.
For learning, ask the student to provide one model after each proposed repair. If they cannot, the conflict may remain elsewhere. A successful model verifies the repaired set’s compatibility, rather than merely showing that one familiar contradiction disappeared.
In classical logic, an inconsistent premise set entails every sentence. If no interpretation satisfies Γ, there is no interpretation making all of Γ true while a proposed conclusion C is false. The semantic consequence condition is satisfied for any C.
A standard classical proof system also permits deriving arbitrary C from contradiction. This principle is often called explosion.
The result does not mean contradictory evidence establishes every real-world claim. It means the classical consequence relation no longer distinguishes conclusions once the premises have no common model.
Why the distinction matters
From {p, ¬p}, classical logic can derive q. It can also derive ¬q. Reporting only q would conceal that the premise set supports its opposite as well.
The useful response is to inspect and repair the premises, not to treat the desired derived sentence as independently confirmed. A proof remains conditional on its starting assumptions.
Other logics, including paraconsistent systems, handle inconsistency differently. Their rules and semantics must be specified. One should not remove explosion from a classical calculus informally and assume every other theorem remains unchanged.
This guide stays within classical logic. Its practical recommendation is about interpretation: an inconsistent specification needs diagnosis before its consequences are used as ordinary support for a decision.
A learner should explain both sides: the derivation may be formally licensed, while the premises fail to describe a jointly possible situation. The mathematical assessment and the evidential assessment perform different jobs.
A repair might remove a premise, weaken a universal rule, correct a factual statement or separate contexts that were mistakenly combined. These changes produce different revised theories.
For {p, p → q, ¬q}, removing p allows a closed unsupervised room. Removing ¬q permits an open supervised room. Removing the conditional permits an open unsupervised room. All three repairs restore satisfiability, but their practical meanings differ.
Logic alone does not rank them. Evidence may show whether the room is open; policy may determine whether the supervision rule is negotiable; a faulty sensor may explain the negative report.
Avoid a hidden change of meaning
Changing q from “supervisor present now” to “supervisor assigned sometime today” can remove an apparent contradiction by changing the predicate. That may be a legitimate clarification, but it must be stated.
Likewise, “every submission was checked” and “not every submission was checked” conflict only when the population and time interval match. If they concern different periods, formalise that distinction.
A good repair record retains the original premises, the conflicting subset, the chosen modification, the reason for the modification and a model of the revised set.
The model should satisfy every remaining condition. A repair that makes the desired conclusion true while leaving another premise false has not completed the compatibility task.
This sequence keeps mathematical reasoning connected with responsible judgment. Identify the tension formally, resolve the factual or priority question through appropriate evidence, and then verify the revised logical specification.
Let the premises be ∀x(P(x) → Q(x)), ∃x P(x), and ∀x ¬Q(x). The existential premise supplies a P-object. The first universal makes that same object Q. The last universal denies Q of every object. The set is unsatisfiable.
Remove the existence premise and a model appears: take a one-object domain with P and Q both empty. Both universal conditions are true. This shows exactly why existence contributes to the conflict.
Remove the first universal instead, and a one-object model with P true and Q false works. Remove the final universal, and a one-object model with both P and Q true works. These three checks show the conflict is inclusion-minimal.
Compare a superficially similar compatible set
The premises ∃x P(x), ∃x ¬Q(x), and ∀x(P(x) → Q(x)) can be jointly true. Use two objects u and v. Let P = {u} and Q = {u}. The P-witness u has Q, while v supplies the witness to ¬Q.
The difference is that “some object lacks Q” does not say the P-witness lacks Q. Merging those witnesses would create a conflict that the actual premises do not contain.
This is why propositional labels must preserve the internal structure when quantifiers matter. Treating every existential claim as though it concerned one fixed person or object can manufacture an inconsistency. Before diagnosing a real requirement set, ask whether the claims require a shared witness or merely permit one.
A satisfiable theory need not determine every sentence. For Γ = {p → q}, one model has p = q = true and another has p = q = false. The theory leaves p undecided.
It also permits p = false and q = true. Thus the relation between the conditions is constrained, while their actual truth values remain partly open.
A model supplied by a solver is one compatible setting. It is not automatically the only setting, the most likely setting or a prediction. Ask whether a conclusion holds in every Γ-model before calling it a consequence.
A useful three-result report
For a proposed C, Γ ∪ {¬C} unsatisfiable establishes Γ ⊨ C. If Γ ∪ {C} is unsatisfiable, Γ entails ¬C. If both extensions are satisfiable, the premises leave C undecided.
This classification assumes Γ itself is satisfiable if the alternatives are to be mutually informative. If Γ is already inconsistent, both extensions are unsatisfiable, and classical entailment supports both C and ¬C.
The check connects conflict diagnosis with inference. First establish whether the premises can coexist; then ask which additional claims they force. Reversing that order can make consequences of an inconsistent set appear more informative than they are.
Exercise 1: a three-premise conflict
Show {p ∨ q, ¬p, ¬q} is unsatisfiable. The disjunction needs at least one true letter, while the other two premises make both false. Removing any one premise permits a model, so the set is minimal.
Exercise 2: compatible without being actual
The premise set {p → q, ¬p} is satisfiable. For example, p = false and q = false works. It does not entail ¬q: p = false and q = true is another model.
Exercise 3: two independent conflicts
Take {p, ¬p, q, q → r, ¬r}. Remove only ¬p. Is the result satisfiable? No. The q–r conflict remains. Removing ¬p and ¬r permits p = q = r = true.
Exercise 4: minimal versus smallest
Identify two minimal conflicts in that set. They are {p, ¬p} and {q, q → r, ¬r}. The first is smaller, but both are inclusion-minimal.
Transfer check
Write three hypothetical requirements using p and q. Find a common truth assignment or prove none exists. If there is a conflict, propose two different repairs and explain their meanings.
Finish with a model for each revised set. Then identify which evidence or decision would be needed to choose a repair in a real setting. Compatibility testing does not supply that choice automatically.
Frequently asked questions
Does individually satisfiable mean jointly satisfiable? No. Different sentences may need incompatible assignments.
Is every minimal conflict the smallest conflict? No. Minimal concerns removing premises; minimum concerns cardinality.
Does a consistent set have to be factually true? No. Compatibility and factual accuracy are different assessments.
Does classical explosion certify arbitrary claims about the world? No. It reveals that inconsistent premises provide no useful discrimination among classical consequences.
Connected reading
Return to Mathematical Logic. The countermodel guide explains shared interpretations, while proof dependencies explains how conclusions retain assumptions.
Sources and scope
Semantic and proof-theoretic distinctions were checked against forall x: Calgary, Proofs and Semantics and its Soundness chapter, accessed 22 October 2026. The requirement sets, removal models and repair examples are original teaching constructions. This guide uses classical consequence and makes no claim that a logical conflict alone determines an institutional or factual priority.
Contents · Previous chapter · Continue to Mathematical Logic
Explore models, proofs and their limits
Compactness and finite satisfiability