Back to the on-screen lesson ·
The truth table as a procedure that always halts, the theorem that no such procedure exists for first-order validity, what semi-decidability gives instead, and how a reduction carries a result from one question to another.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to say what makes a question decidable, give the cost of the truth-table procedure and how it grows, say which questions the stated results settle with a halting procedure and which they do not, state what a semi-decision procedure does and does not give, order the steps of the truth-table procedure, and reduce one question to another.
You can build a truth table and you know that soundness and completeness make derivability and entailment coincide. This lesson asks a different kind of question about those relations: not whether they hold, but whether anything can be relied on to tell you so.
A procedure is a recipe with no choices left open, applied to an input. A question is decidable when some procedure halts on every instance with the right answer, and semi-decidable when some procedure halts on every yes instance and may run forever on the rest. A reduction turns one question into another by transforming the input and translating the answer back.
Propositional logic is decidable, and the truth table is the procedure: list the atoms, write the $2^n$ rows, fill the columns, read the answer. It halts on every input, which is what the word means. Tautologyhood, validity, equivalence and satisfiability are all decided by it, because each reduces to another: an argument is valid exactly when its corresponding conditional is a tautology, and a formula is a tautology exactly when its negation is unsatisfiable. First-order logic is different, and two separate results say how. Church's theorem states that no procedure decides, for every first-order sentence, whether it is valid. And the completeness theorem gives something weaker in its place: the derivations can be listed one after another, so a search through them halts on every valid sentence — first-order validity is semi-decidable. A semi-decision procedure confirms and never refutes: no length of running is evidence that the answer is no. Finally, decidable does not mean practical. The propositional procedure is guaranteed to finish and doubles in size with every atom.
Another way: steps
Another way: example
First-order validity: the yes instances have finite certificates, namely derivations, and completeness says every one of them has such a certificate. The no instances have no such certificate, and Church's theorem says no procedure supplies one.
The first error is reading semi-decidability as a decision procedure with a slow case, so that a long run is taken for a no; the definition promises nothing about the no instances, so a run of any length is silence rather than evidence. The second is reading decidable as practical: a procedure with $2^{100}$ steps decides its question. The third is treating Church's theorem as a claim about anything other than procedures — it says that no procedure decides a particular question about a particular formal language, and it is proved as a mathematical statement about that language.
Is the argument from $P \to Q$ and $\neg Q$ to $\neg P$ valid?
Turn it into one formula.
Build the corresponding conditional and run the tautology procedure on it: four rows.
One procedure, several questions.
It halts with yes. The reduction is what let a single procedure answer a question it was not written for.
Reductions do the travelling.
A search through derivations has been running on a first-order sentence for a long time.
Semi-decidable, not decidable.
Had the sentence been valid, completeness guarantees the search would halt — but it does not say when.
No bound is promised.
So the long run establishes nothing. A countermodel would establish invalidity; the search alone cannot.
Silence is not a no.
Two formulas are equivalent exactly when the biconditional between them is a tautology, and that holds exactly when its negation is unsatisfiable.
So form that negated biconditional, hand it over, and report equivalent exactly when the answer is not satisfiable.
A propositional formula is built from $2$ atoms. The truth-table procedure settles whether it is a tautology by examining every valuation. Complete the sentence.
The procedure examines r rows and then halts.
Match each question to the result that applies to it.
| Settled by a table of $2^n$ rows, which always halts with an answer | Settled by that same table, applied to the corresponding conditional | Settled by working through the structure, each quantifier a finite loop over the domain | Church's theorem states that no procedure decides it; a search halts on the valid ones only | |
|---|---|---|---|---|
| Whether a propositional formula is a tautology | ||||
| Whether a propositional argument is valid | ||||
| Whether a sentence is true in a given finite structure | ||||
| Whether a first-order sentence is valid |
Take these three results as given. First, the truth-table procedure decides every propositional question. Second, evaluating a sentence in a given finite structure always halts. Third, Church's theorem: no procedure decides, for every first-order sentence, whether it is valid. Mark every question below that one of these results settles with a procedure halting on every instance.
This task has no paper form; do it on a device.
A question is semi-decidable: there is a procedure that halts with *yes* on every instance whose answer is yes, and may run forever on the instances whose answer is no. What does having such a procedure let you do?
Put the four steps of the truth-table decision procedure into the order they are carried out.
Number the steps in order (write the number in the box):
Suppose you are handed a procedure that decides, for any formula, whether it is satisfiable. Put the four steps of the recipe that uses it to decide whether a formula is a tautology into order.
Number the steps in order (write the number in the box):
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
For each number of atoms, give the number of rows the table has, and the number it would have with one more atom.
| Rows | Rows with one more atom | |
|---|---|---|
| 2 atoms | ||
| 3 atoms | ||
| 4 atoms | ||
| 10 atoms |
You can say what decidable and semi-decidable mean and which of the questions in this course are which. Say in your own words why a search that has not halted establishes nothing.
8. Your turn: a procedure decides whether a formula is satisfiable. Does one decide whether two formulas are equivalent?, step 2