Back to the on-screen lesson ·
Atoms, the five connectives, the formation rules, and finding the main connective of a formula.
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 which strings the formation rules build, find the main connective of a formula and the subformulas it joins, read a formula written with precedence rather than brackets, and give the column a connective has over the rows of a truth table.
You have written mathematical statements with and, or, not and if ... then, and you have used a truth table to settle whether an implication holds. This lesson makes the language itself the object of study: which strings count as statements, and how one is put together.
An atom is a statement letter, written $P$, $Q$, $R$; it stands for a whole statement and has no parts. A formula is a string the formation rules build. A subformula is a formula that occurs inside another. The main connective is the one applied last. Scope is how much of the formula a connective reaches. A valuation assigns a truth value to each atom.
The language has atoms $P, Q, R, \ldots$ and five connectives: $\neg$, $\wedge$, $\vee$, $\to$, $\leftrightarrow$. The formation rules say what a formula is, and they are the whole definition: every atom is a formula; if $\phi$ is a formula then so is $\neg \phi$; if $\phi$ and $\psi$ are formulas then so is $(\phi \wedge \psi)$, and likewise for $\vee$, $\to$ and $\leftrightarrow$; and nothing else is a formula. Because every formula is built by those rules, every formula has exactly one main connective, the one applied last, and the pieces it joins are its immediate subformulas. Outer brackets are usually dropped and precedence used instead: $\neg$ binds tightest, then $\wedge$ and $\vee$, then $\to$ and $\leftrightarrow$. A valuation gives each atom a value, and the truth tables of the connectives then fix the value of every formula built from them: $\phi \to \psi$ is false on one row only, the row where $\phi$ is true and $\psi$ false.
Another way: steps
Another way: example
$\neg P \to Q \wedge R$ has main connective $\to$: negation reaches only $P$ and conjunction binds tighter than the arrow, so the two pieces are $\neg P$ and $Q \wedge R$.
Two mistakes are worth naming. The first is reading precedence as word order: in $P \vee Q \to R$ the arrow is the main connective, even though it is written last, because it has the widest scope. The second is treating $\neg$ as reaching to the end of the formula; $\neg P \wedge Q$ is a conjunction whose left half is negated, not the negation of a conjunction, and the two differ on the row where $P$ and $Q$ are both false.
$(P \wedge Q) \to \neg R$: no bracket encloses the whole string.
Nothing to strip.
The conjunction is inside a bracket and the negation reaches only $R$, so the arrow is applied last.
Widest scope wins.
Main connective $\to$; immediate subformulas $P \wedge Q$ and $\neg R$.
Split and repeat.
$P \wedge \vee Q$: ask which rule was applied last.
Work backwards from the rules.
Whichever binary connective you pick, one of its two sides is not a formula, so no rule produces the string.
No last rule, no formula.
The negation is followed immediately by a bracket, so it reaches exactly $P \to Q$ and no further.
That leaves $\neg (P \to Q)$ and $R$ joined by $\wedge$, so the main connective is the conjunction.
Match each connective to the demand it makes on a row of the truth table.
| Swaps the value of the one formula it is applied to | Both halves hold | At least one half holds, and both is allowed | The first half never holds while the second one fails | The two halves agree, whichever way they agree | |
|---|---|---|---|---|---|
| $\neg P$ | |||||
| $P \wedge Q$ | |||||
| $P \vee Q$ | |||||
| $P \to Q$ | |||||
| $P \leftrightarrow Q$ |
Complete the column for P | Q — read 'or'. The rows are in the usual order: both true, then $P$ true and $Q$ false, then $Q$ only, then neither.
| P | Q | P | Q |
|---|---|---|
Which connective is the main connective of $(P \to Q) \leftrightarrow \neg R$ — the one applied last?
Mark every string below that the formation rules build.
This task has no paper form; do it on a device.
A formula is built from $3$ different atoms. Complete the sentence.
Its truth table has r rows.
A formula is written with $7$ occurrences of atoms and no negation signs at all. How many occurrences of binary connectives does it have?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Here are four stages in the construction of $\neg (P \wedge (Q \to R))$. Put them in the order the formation rules produce them.
Number the steps in order (write the number in the box):
You can decide whether a string is a formula, find its main connective, and write the column of each connective. Say in your own words why every formula has exactly one main connective.
8. Your turn: the main connective of $\neg (P \to Q) \wedge R$, step 2