Back to the on-screen lesson ·
The three things a final column can look like, how to settle which by trying to falsify a formula, and why substitution preserves the answer.
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 classify a formula as a tautology, a contradiction or contingent, decide satisfiability and count the valuations that satisfy a formula, settle a classification by attempting a falsifying row rather than by filling a whole table, and recognise a substitution instance of a schema you have already settled.
You can build a truth table and read its final column. Classification is the first thing that column is for: three labels, each of them a statement about how many rows come out true.
A tautology is true under every valuation; a contradiction under none; a formula is contingent when it is neither. A formula is satisfiable when some valuation makes it true, and valid — as a single formula rather than as an argument — is another word for tautology.
The final column of a table can look three ways, and the three labels are exactly those three looks. All T: the formula is a tautology, true no matter what its atoms mean. All F: a contradiction. A mixture: contingent. Two facts make the classification easier than filling in a whole table. First, the labels are linked: $\phi$ is a tautology exactly when $\neg \phi$ is a contradiction, and $\phi$ is satisfiable exactly when $\neg \phi$ is not a tautology. Second, a single row settles half the question — one F rules out tautology, one T rules out contradiction — so the efficient method is to try to make the formula false, and if that fails, to try to make it true. Finally, the classification survives substitution: replace the atoms of a tautology by any formulas you like, uniformly, and the result is a tautology, because the argument that it could not be made false never looked at what the atoms were.
Another way: steps
Another way: example
$(P \vee Q) \to P$: to falsify it, make $P \vee Q$ true and $P$ false, so $Q$ must be true. That row exists, so it is not a tautology. Making $P$ true makes it true, so it is contingent.
The first mistake is calling a formula a tautology because it is true on the rows that were checked; a tautology is a claim about every row, so the checking has to be exhaustive or replaced by an argument. The second is confusing a contradiction with a formula that is merely false — false on this row is a fact about the valuation, while contradiction is a fact about the formula. The third is expecting the label to depend on what the atoms stand for, which it never does.
$(P \wedge (P \to Q)) \to Q$: suppose it is false.
Assume what you are testing for.
Then $Q$ is false and $P \wedge (P \to Q)$ is true, so $P$ is true and $P \to Q$ is true.
Work backwards through the connectives.
But $P$ true and $Q$ false makes $P \to Q$ false. The route closes, so it is a tautology.
No falsifying row exists.
$P \wedge \neg P$ is a contradiction: no row makes both halves true.
All F.
So $\neg (P \wedge \neg P)$ is true on every row, and it is a tautology.
Negating turns all F into all T.
A contingent formula's negation is contingent too, because a mixture stays a mixture.
The third label is its own opposite.
To falsify it, $\neg P$ must be true and $P \to Q$ false; the second needs $P$ true.
That asks for $P$ to be both false and true, so no such row exists and the formula is a tautology.
Is $P \vee \neg P$ a tautology, a contradiction, or contingent?
Give the column of (P & (P -> Q)) -> Q over the four rows for $P$ and $Q$, in the usual order.
| P | Q | (P & (P -> Q)) -> Q |
|---|---|---|
Mark every formula below that is a tautology.
This task has no paper form; do it on a device.
How many of the four valuations of $P$ and $Q$ satisfy $(P \wedge (P \to Q)) \to Q$?
Answer:
Match each word to the condition it puts on the formula's column.
| True on every row | True on no row | True on some rows and false on others | True on at least one row | |
|---|---|---|---|---|
| Tautology | ||||
| Contradiction | ||||
| Contingent | ||||
| Satisfiable |
Give the column of ((P | Q) & ((P | Q) -> R)) -> R. The atoms are $P$, $Q$, $R$ in that order, so there are eight rows.
| P | Q | R | ((P | Q) & ((P | Q) -> R)) -> R |
|---|---|---|---|
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Each formula below is over $P$ and $Q$, so each has four rows. Give the number of rows on which it is true.
| Rows out of four where it is true | |
|---|---|
| $P \wedge Q$ | |
| $P \to Q$ | |
| $P \wedge \neg P$ | |
| $P \to P$ |
You can classify a formula, count its satisfying valuations, and justify a tautology by showing no falsifying row exists. Say in your own words why a formula is a tautology exactly when its negation is unsatisfiable.
8. Your turn: classify $\neg P \to (P \to Q)$, step 2