1.2 Well-formed formulas

Because we want to talk abstractly about how to reason, we don’t want to confine ourselves to particular propositions but to explore what can be said about all propositions. For that reason we introduce propositional variables: symbols that represent a proposition. Traditionally lower case English letters $p$, $q$, $r$, …are used for propositional variables, or letters with subscripts $p_1,p_2,\mathrm{\dots }$

In additional to propositional variables, the language we use will have symbols for some of the logical connectives we discussed before.

• •

  $\wedge$ represents and.

• •

  $\vee$ represents or.

• •

  $\to$ or $⟹$ represents implies.

• •

  $\mathrm{\neg }$ represents not.

Finally, we will also use brackets: ( and ).

We’ve now got the “letters” of our language: propositional variables, connective symbols, and brackets. Just like the letters a, b, c…z can be used to make English sentences, we can now build what we will call formulas, like $(p\vee q)$, or $(p⟹(q\wedge (\mathrm{\neg }r)))$. But just like eifaefeaioj is a legitimate string of letters that isn’t a meaningful word, $\wedge ⟹pq)\mathrm{\neg }$ doesn’t seem like something we can give a useful logical interpretation to. Collections of propositional variables, connectives, and brackets to which we can give a sensible meaning will be called well-formed formulas, and we are going to see next what the rules are for a formula to be well-formed.

We need rules to say which strings of connectives, brackets, and variables are well-formed formulas, or WFFs for short. We do this by specifying rules for constructing WFFs. By definition, something is a WFF if and only if it can be constructed using these rules.

1. 1.

   A propositional variable is a WFF.

2. 2.

   If $\varphi$ and $\psi$ are any two WFFs then

   • 2.1

     $(\varphi \wedge \psi )$ is a WFF,

   • 2.2

     $(\varphi \vee \psi )$ is a WFF,

   • 2.3

     $(\varphi ⟹\psi )$ is a WFF, and

   • 2.4

     $\mathrm{\neg }\varphi$ is a WFF.

Suppose $p$ and $q$ are propositional variables. Then the following are WFFs:

• •

  $p$ is a WFF because of rule 1.

• •

  $(p⟹q)$ is a WFF by using rule 1 twice then rule 2.3.

• •

  $\mathrm{\neg }r$ by using rule 1 then rule 2.4.

• •

  $((p⟹q)\vee \mathrm{\neg }r)$ is a WFF as rule 1 says $p$, $q$, $r$ are WFFs, rule 2.3 and rule 2.4 say that $(p⟹q)$ and $\mathrm{\neg }r$ are WFFs, and finally rule 2.2 says the whole thing is a WFF.

• •

  $\mathrm{\neg }\mathrm{\neg }(p⟹q)$ by rule 1, then rule 2.3, then rule 2.4 twice.

Only things that can be built using the rules are WFFs. You can’t build

$$r\wedge ⟹pq)\mathrm{\neg }$$

using the rules above (can you prove it?), so it’s not a WFF. You can’t even build $p\vee q$ or $(p\wedge q\wedge r)$, so these aren’t WFFs either.