Back to the on-screen lesson ·
Laying the rows out in standard order, filling one column per subformula, and reading what the last column says.
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 lay out the rows of a truth table in standard order for two or three atoms, write a column for each subformula and fill it from the columns already written, count the rows on which a formula is true, and combine two columns without knowing the formulas they belong to.
You can find the main connective of a formula and you know what each connective demands of a row. A truth table is those two facts used systematically: one row per valuation, one column per subformula.
A valuation assigns T or F to every atom; a table has one row per valuation. A column records the value of one subformula across all the rows. Standard row order runs from all-true at the top to all-false at the bottom, the first atom changing slowest.
A formula over $n$ atoms has $2^n$ valuations, and the table has one row for each. The standard order is the one this course always uses: the first atom is T for the top half of the rows and F for the bottom half, the second alternates in blocks of half that size, and the last alternates every row. Then a column is written for each subformula, innermost first, and the last column is the formula itself. Every entry is decided by the entries to its left on the same row, and by nothing else — this is what compositionality means, and it is why the method works for a formula of any length. Reading the finished column answers every question the unit will ask: no F at all and the formula is a tautology, no T and it is a contradiction, and two formulas with the same column are equivalent.
Another way: steps
Another way: example
$\neg (P \wedge \neg Q)$ over two atoms: the columns are $Q$, then $\neg Q$, then $P \wedge \neg Q$, then the whole formula. The conjunction holds on the second row alone, so the formula is F there and T on the other three.
Almost every wrong table is one of three things. Rows are missed, because they were written down in an order that was invented row by row rather than laid out first. The conditional's two false-antecedent rows are marked F, on the thought that a promise about nothing must be broken rather than kept. Or the whole formula's column is attempted directly, without the intermediate columns, at which point a single slip is invisible.
$(P \to Q) \wedge P$ over $P, Q$. Columns: $P \to Q$, then the conjunction.
Innermost first.
$P \to Q$ is T, F, T, T. The conjunction needs $P$ as well, and $P$ is T on the top two rows only.
Each entry from the row beside it.
So the conjunction is T, F, F, F: it holds on the top row alone.
Read the last column.
$(P \wedge Q) \to R$ has eight rows. $P \wedge Q$ holds on the top two rows only.
The antecedent first.
A conditional fails only where its antecedent holds and its consequent does not, so only rows one and two can fail, and row two has $R$ false.
Look only where failure is possible.
The column is T, F and then six more Ts.
Six rows needed no work at all.
$\neg P$ is F, F, T, T. The disjunction needs at least one half.
So the column is T, F, T, T — the same column as $P \to Q$, which is not a coincidence and will be the first equivalence of the next lesson.
Give the column of P & (Q | R). The atoms are $P$, $Q$, $R$ in that order, so there are eight rows, running from all true down to all false.
| P | Q | R | P & (Q | R) |
|---|---|---|---|
Complete the table for $P \to \neg Q$. Fill the two atom columns in the standard order and then the formula's own column. Write T or F in each cell.
| $P$ | $Q$ | $P \to \neg Q$ | |
|---|---|---|---|
| Row 1 | |||
| Row 2 | |||
| Row 3 | |||
| Row 4 |
The atoms are $P$ and $Q$, so the table has four rows. On how many of them is $P \wedge Q$ true?
Answer:
Put these four columns of the table for $\neg (P \wedge \neg Q)$ in the order they can be filled in.
Number the steps in order (write the number in the box):
The rows are in the usual order. Match each formula to its column.
| T, F, F, F | T, T, T, F | T, F, T, T | T, F, F, T | |
|---|---|---|---|---|
| $P \wedge Q$ | ||||
| $P \vee Q$ | ||||
| $P \to Q$ | ||||
| $P \leftrightarrow Q$ |
Two formulas $\phi$ and $\psi$ over the same atoms have the columns shown. You are not told what they are. Fill in the columns of $\phi \wedge \psi$ and $\phi \to \psi$.
| $\phi$ | $\psi$ | $\phi \wedge \psi$ | $\phi \to \psi$ | |
|---|---|---|---|---|
| Row 1 | T | T | ||
| Row 2 | F | T | ||
| Row 3 | T | F | ||
| Row 4 | F | F |
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Give the column of ~P | (Q & R). The atoms are $P$, $Q$, $R$ in that order, so there are eight rows, running from all true down to all false.
| P | Q | R | ~P | (Q & R) |
|---|---|---|---|
You can build a full truth table for a formula of two or three atoms and read the result off the final column. Say in your own words why the value of a compound formula on a row depends on nothing but the values of its parts on that row.
8. Your turn: the column of $\neg P \vee Q$, step 2