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 recognize 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.
| Term | What it means |
|---|---|
| Tautology | A formula true on every assignment. |
| Contradiction | A formula false on every assignment. |
| Contingent formula | A formula true on some assignments and false on others. |
| Satisfiable | True on at least one assignment; both tautologies and contingent formulas qualify. |
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.
A single false row refutes the claim that a formula is a tautology. A single true row refutes the claim that it is a contradiction. Neither row alone establishes contingency: for that, supply both a true row and a false row. With P -> Q, TT provides a true row and TF a false one, so the formula is contingent. No claim about how often P and Q occur in the world enters this classification.
A tautology can contain a complicated repeated part. Replacing P in P | ~P by Q & R gives (Q & R) | ~(Q & R), which remains true on every assignment. What matters is that the whole substituted formula repeats unchanged. Replacing only the second occurrence by a different formula can destroy the result.
Classical propositional logic uses two truth values here. The classification is relative to that explicit framework. A vague sentence, an unknown fact, and a formula with a mixture of true and false rows are different things. Not knowing whether a real-world claim is true does not give it a third truth value in these exercises.
Classifying a formula is a claim about its whole truth function, not the value it happens to have on a selected row. A tautology has no false assignment. A contradiction has no true assignment. A contingent formula has at least one of each. These possibilities divide the formulas of this classical language into three mutually exclusive classes. A formula cannot be both contingent and a tautology under the same semantics.
The evidence needed is asymmetric. To refute tautology, you only need one false row. To establish tautology by enumeration, you need every row true. To refute contradiction, one true row suffices; to establish contradiction by enumeration, every row must be false. Do not confuse a witness that defeats a universal claim with a sample that merely supports it. A large collection of true rows can still omit the one false row that matters.
Contingency has a compact witness pair. For P -> Q, the row P true, Q true makes the formula true, while P true, Q false makes it false. Those two calculations already establish that both values are possible. You need not display the other rows to prove contingency, although a complete table can be helpful for practice. The pair must use the same formula and the same fixed atom meanings.
Satisfiability asks a weaker question: is there any true row? A contingent formula is satisfiable because it has such a row. A tautology is also satisfiable because every assignment works. A contradiction is not satisfiable. Consequently, the labels 'satisfiable' and 'contingent' cannot be used interchangeably. Reporting satisfiability alone leaves open whether a formula also has false rows.
A true observation about the actual world does not settle these semantic categories. The sentence represented by P might be true today, but the atomic formula P still has a false assignment as well as a true one in its propositional table. Its contingency describes the permitted assignments of the formal model. It does not imply that today's observation is uncertain or that a well-established fact should be doubted.
You can sometimes establish a classification without calculating every entry individually. To test whether (P & Q) -> P could be false, demand a true antecedent and a false consequent. The antecedent's truth would require P true. The consequent's falsity would require P false. No single assignment can meet both requirements, so there is no falsifying row. This is an exhaustive structural argument because it examines the conditional's only route to falsity.
Compare (P | Q) -> P. Falsity requires P | Q true and P false. Those requirements are compatible: set Q true. The resulting assignment P false, Q true is a genuine false row. The failed tautology claim is now settled. To finish the classification, find a true row as well, such as P true and Q false. Together the two witnesses establish contingency.
For a conjunction claimed to be contradictory, search for a row making every conjunct true together. In P & ~P, the two demands conflict on the same atom. In P & ~Q, they do not: P true, Q false satisfies the formula. The mere presence of a negation does not create contradiction. What matters is whether all the truth requirements can be satisfied by one consistent assignment.
A search argument must account for every alternative it opens. To make P | Q true, either disjunct can suffice. Showing that one route fails does not show both fail. To prove no satisfying assignment exists, rule out every available route or give a complete table. Unexplored alternatives are a common reason an informal 'I could not make it true' does not establish contradiction.
The same discipline applies to compound substitutions. In (Q & R) | ~(Q & R), call the repeated inner formula A while analyzing the outer pattern. Either A is true or A is false; in either case A | ~A is true. The inner formula must be identical in both places. Replacing one occurrence by Q | R changes the pattern and invalidates this particular justification.
Negation reverses every value in a final column. Therefore negating a tautology produces a contradiction, and negating a contradiction produces a tautology. Negating a contingent formula preserves contingency because a mixed column remains mixed after reversal. The true and false counts exchange places, but neither count becomes zero when both were positive.
Counting satisfying assignments can make a classification transparent. With two distinct atoms, a formula with four true rows is tautological, one with zero true rows is contradictory, and one with one, two, or three true rows is contingent. With three atoms the corresponding total is eight. State the atom set before interpreting a count, because the total depends on how many independent inputs the table includes.
If you add an unused atom to the table, each old assignment appears twice, once for each value of the unused atom. The numbers of true and false rows both double, while the classification remains unchanged. P still has both true and false rows whether you list only P or also an irrelevant Q. This shows why a raw satisfying-row count is not a probability and why totals should accompany numerical reports.
A formula that matches every record in a dataset might be contingent. Perhaps the dataset simply lacks its falsifying cases. A formula that matches no current record might still be satisfiable. The formal table answers what is possible under the declared truth conditions; the dataset answers which records happen to be present. Keeping these questions separate is essential when using filters, policy conditions, or test cases as illustrations.
In a final classification explanation, identify the formula, provide the decisive evidence, and state the label warranted by that evidence. For contingency, give both witnesses or a mixed complete column. For an all-row label, give a complete table or a structural argument covering every route. This makes the result reviewable without asking the reader to trust your confidence or an unexplained label.
A document search tool offers two tags, Reviewed and Urgent. Let R and U mean that the corresponding tag is present. Someone enters R | ~R while trying to select documents needing attention. Its two-row table is T, T: either Reviewed is present or it is absent. The filter selects every document within the declared two-valued tag system. It is a tautology, so it does not narrow the collection at all.
A second filter R & ~R has the column F, F. It selects no document, because a tag cannot be both present and absent in the same record under the model. This is a contradiction. A third filter U & ~R is contingent: an urgent unreviewed record satisfies it, whereas an urgent reviewed record does not. That third filter actually distinguishes cases relevant to a review line.
Suppose the collection contains forty documents and the first filter returns forty. The count alone does not establish a tautology; a contingent condition could happen to hold of all forty. The table establishes the classification independently of the dataset. Conversely, zero returned records does not prove a contradiction; perhaps the collection currently has no urgent unreviewed documents.
The application depends on tags behaving as two-valued inputs. If the software has an additional missing or unknown state, its query semantics must be checked separately. The formal exercise is useful precisely because it states its assumptions. Do not transfer a classical two-valued result to an unspecified database system without checking those assumptions.
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.
Identify the distinct atom.
P | ~P uses P
The negated occurrence is not a new independent atom.
List its assignments.
P=T; P=F
These exhaust the two-valued possibilities.
Calculate the denial.
~P=F; ~P=T
Negation reverses each atomic value.
Calculate the disjunction.
T|F=T; F|T=T
At least one disjunct is true on each row.
State the classification.
Tautology: two true rows, no false rows
The entire column is true.
List the assignments.
PQ: TT,TF,FT,FF
The two atoms have four combinations.
Calculate the required denial.
~Q: F,T,F,T
Q is reversed on each row.
Evaluate the whole formula.
P & ~Q: F,T,F,F
Both conjuncts must hold together.
Identify a satisfying witness.
P=T,Q=F
This assignment makes the formula true.
Identify a falsifying witness.
P=T,Q=T
This assignment makes the denial false.
State both warranted results.
Contingent and satisfiable
It has both true and false rows, and therefore at least one true row.
State the tested formula.
(P & (P -> Q)) -> Q
The main connective is the outer conditional.
Demand its only false case.
P & (P -> Q)=T; Q=F
A conditional fails only with true antecedent and false consequent.
Unpack the antecedent.
P=T; P -> Q=T
A true conjunction requires both inputs true.
Combine the atomic demands.
P=T,Q=F
They must hold on one assignment.
Re-evaluate the inner arrow.
P -> Q=F
The demands give its unique false case.
Reject the incompatible requirements.
P -> Q cannot be both T and F
One formula has one value on an assignment.
Conclude the classification.
Tautology
The outer conditional has no possible falsifying assignment.
Evaluate the inner formula.
P & ~P: F,F
Its two conjuncts never hold together.
Negate each output.
~(P & ~P): T,T
Negation reverses the whole inner value.
Classify the complete column.
For (P & Q) -> P, calculate the full table in PQ order TT,TF,FT,FF. Write its true-row count, false-row count, and classification symbol. Use T for a tautology (all true), C for a contradiction (all false), and M for a contingent formula (mixed outputs).
True rows: b0
False rows: b1
Classification symbol: b2
Complete the worked classification of P | Q on all assignments of P,Q.
Calculate the final column.
T,T,T,F
Inclusive disjunction fails only when both inputs are false.
Count the true outputs.
true_count true rows
Every row with a true input satisfies the disjunction.
Count the false outputs and classify.
false_count false row; contingent
Both values occur, so neither all-row label applies.
For ~(P | ~P) & Q, calculate the full table in PQ order TT,TF,FT,FF. Write its true-row count, false-row count, and classification symbol. Use T for a tautology (all true), C for a contradiction (all false), and M for a contingent formula (mixed outputs).
True rows: b0
False rows: b1
Classification symbol: b2
For P <-> ~Q, calculate the full table in PQ order TT,TF,FT,FF. Write its true-row count, false-row count, and classification symbol. Use T for a tautology (all true), C for a contradiction (all false), and M for a contingent formula (mixed outputs).
True rows: b0
False rows: b1
Classification symbol: b2
Write a filter condition for an urgent document that is not reviewed. U means urgent and R means reviewed. Require both features.
Answer:
For P -> (Q -> P), calculate the full table in PQ order TT,TF,FT,FF. Write its true-row count, false-row count, and classification symbol. Use T for a tautology (all true), C for a contradiction (all false), and M for a contingent formula (mixed outputs).
True rows: b0
False rows: b1
Classification symbol: b2
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
For ~((P -> Q) <-> (~Q -> ~P)), calculate the full table in PQ order TT,TF,FT,FF. Write its true-row count, false-row count, and classification symbol. Use T for a tautology (all true), C for a contradiction (all false), and M for a contingent formula (mixed outputs).
True rows: b0
False rows: b1
Classification symbol: b2
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.
14. Classify a negated contradiction, step 3
tautology
Every assignment gives true.