Back to the on-screen lesson ·
Reading a disjunctive normal form off a column, recognising the shape, and how few connectives a language needs to express every truth function.
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 how many disjuncts a normal form needs, read the column of a formula already in normal form, build a formula with any column you are given, recognise whether a formula is in disjunctive normal form, count the truth functions of a given number of arguments, and explain why one connective can express them all.
You can build a table and rewrite a formula by named laws. A normal form is what those two abilities produce when they are pointed at each other: a table read backwards into a formula of a fixed shape.
A literal is an atom or a negated atom. A formula is in disjunctive normal form when it is a disjunction of conjunctions of literals, and in conjunctive normal form when it is a conjunction of disjunctions of literals. A set of connectives is functionally complete when every truth function can be written with it alone. The Sheffer stroke $\uparrow$ is the connective read 'not both'.
Any column can be turned back into a formula. Take each row where the formula is to be true and write the conjunction of literals that names that row — the atom where the row has T, its negation where the row has F. That conjunction is true on that row and on no other, so the disjunction of all of them is true on exactly the wanted rows. The result is the disjunctive normal form; the mirror construction from the false rows gives the conjunctive normal form. Two consequences follow. First, every truth function is expressible, so the language leaves nothing out. Second, the construction uses only $\neg$, $\wedge$ and $\vee$, so those three are functionally complete; De Morgan removes the $\vee$, leaving $\{\neg, \wedge\}$, and a single connective can express both of those. A formula with all F in its column is the one exception to the recipe, and is written as an explicit contradiction.
Another way: steps
Another way: example
$P \leftrightarrow Q$ is true on the rows $(T, T)$ and $(F, F)$, so its disjunctive normal form is $(P \wedge Q) \vee (\neg P \wedge \neg Q)$.
The first error is writing the conjunctions from the false rows rather than the true ones; that construction is correct, but it produces the conjunctive normal form and each row must then be negated throughout. The second is thinking a normal form is the shortest equivalent formula — it is usually much longer, and shortness was never what was wanted. The third is calling a formula complete when a set of connectives is meant: completeness here is a property of a set of symbols, not of a formula.
Wanted column T, T, F, T over $P, Q$: the T rows are the first, second and fourth.
Work from the T rows only.
They give $P \wedge Q$, $P \wedge \neg Q$ and $\neg P \wedge \neg Q$.
One conjunction per row.
Disjoined, that is the normal form. It is longer than the equivalent $\neg (\neg P \wedge Q)$, and that is expected.
Normal, not short.
$\neg P$ is $P \uparrow P$: 'not both $P$ and $P$' fails exactly when $P$ holds.
Negation first.
$P \wedge Q$ is $(P \uparrow Q) \uparrow (P \uparrow Q)$, the negation of 'not both'.
Then conjunction.
Since $\{\neg, \wedge\}$ is complete and both are expressible, $\uparrow$ alone is complete.
Complete by reduction.
Its column is F, F, F, T, so there is one row to name: the bottom one.
That row gives $\neg P \wedge \neg Q$, which is the whole normal form — one disjunct, no disjunction needed.
How many disjuncts does the disjunctive normal form of $\neg P \wedge \neg Q$ have, over the atoms $P$ and $Q$?
Answer:
Give the column of (P & Q) | (P & ~Q) | (~P & Q) over the four rows for $P$ and $Q$.
| P | Q | (P & Q) | (P & ~Q) | (~P & Q) |
|---|---|---|
A latch is to be open in exactly the situations marked T below, where P is “the switch is up” and Q is “the door is closed”. The four rows are in the usual order — both, switch only, door only, neither — and the wanted column is T, T, F, T. Write a formula that is true in exactly those situations.
Answer:
Match each formula to an equivalent one that uses only negation and conjunction.
| $\neg (\neg P \wedge \neg Q)$ | $\neg (P \wedge \neg Q)$ | $\neg (P \wedge \neg Q) \wedge \neg (Q \wedge \neg P)$ | $\neg (P \wedge Q)$ | |
|---|---|---|---|---|
| $P \vee Q$ | ||||
| $P \to Q$ | ||||
| $P \leftrightarrow Q$ | ||||
| $P \uparrow Q$, read 'not both' |
Mark every formula below that is already in disjunctive normal form.
This task has no paper form; do it on a device.
At fewest, how many binary connectives does a language need in order to express every truth function?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
A truth function of $1$ arguments is a rule that gives an output for every combination of inputs. Complete the sentence.
There are m different truth functions of that many arguments.
You can turn a column into a disjunctive normal form and back, and say what it means for a set of connectives to be functionally complete. Say in your own words why every truth function is expressible in this language.
8. Your turn: the disjunctive normal form of $\neg (P \vee Q)$, step 2