Propositional Logic · step 9 of 13

Satisfiability & counter-valuations

A formula is satisfiable if some valuation makes it true, and unsatisfiable if none does. Satisfiability is the computational heart of propositional logic — SAT was the first problem proved NP-complete — and in exams it shows up as the fastest way to settle a claim: to refute "A is a tautology" or "Γ ⊨ B", you exhibit one valuation, not an argument.

Practise satisfiability & counter-valuations free → All Propositional Logic subtopics

✓ Unlimited questions · marked criterion by criterion · no card needed

Method: how to approach it

The order below is what examiners expect to see, and each step carries its own marks.

Turn the claim into a satisfiability questionA is a tautology iff ¬A is unsatisfiable. Γ ⊨ B iff Γ ∪ {¬B} is unsatisfiable. Refuting either means satisfying the corresponding set.
Force the constrained parts firstAny clause that is a single literal fixes that variable immediately. Propagate that value everywhere before guessing anything — this is unit propagation.
Guess, propagate, backtrackPick an unassigned variable, assign it, propagate the consequences, and undo the choice if a clause becomes false. This is DPLL in miniature.
State the valuation in fullGive a value for every variable and verify each premise evaluates to true. An unverified assignment is not a refutation.

Worked example

Is (p ∨ q) ∧ (¬p ∨ r) ∧ ¬r satisfiable?

The unit clause ¬r forces r = F.
With r = F, the clause (¬p ∨ r) needs ¬p, so p = F.
With p = F, the clause (p ∨ q) needs q, so q = T.
Check: (F ∨ T) = T, (T ∨ F) = T, ¬F = T — all three conjuncts hold.

Answer. Yes — satisfiable, with p = F, q = T, r = F.

Where marks get dropped

These are the specific errors that cost credit on satisfiability & counter-valuations questions — QED's rubric penalises each of them separately.

Giving a partial valuation. Leaving a variable unassigned means the formula has not actually been evaluated, and the refutation is incomplete.
Confusing satisfiable with valid. Every tautology is satisfiable, but most satisfiable formulas are not tautologies — the two words are not interchangeable.
Stopping at the first assignment that works for some clauses. All conjuncts must be checked before declaring success.

Practise this until it is automatic

Unlimited fresh questions

QED generates new satisfiability & counter-valuations problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.

Marked like an examiner

Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.

Answer in real notation

A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.

Saved to your library

Every question you generate is kept and re-takeable as a timed exam, and your Propositional Logic mastery is tracked so you know when this is exam-ready.

Satisfiability & counter-valuations — frequently asked questions

What is unit propagation?

When a clause has exactly one unassigned literal left and is not yet satisfied, that literal must be true. Propagating these forced assignments is what makes SAT solvers fast in practice.

How is satisfiability related to validity?

They are dual. A is valid exactly when ¬A is unsatisfiable, so any method for one settles the other by negating first.

Why does SAT matter beyond logic exams?

Hardware verification, scheduling, program analysis and cryptanalysis all reduce to SAT. Modern solvers handle millions of clauses despite the problem being NP-complete.

The rest of Propositional Logic

Connectives, truth tables, equivalences and normal forms. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make satisfiability & counter-valuations exam-proof?

Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.

Start practising free →