2
$\begingroup$

I am reading chapter-6 of the textbook forall x: Calgary. Quoting from the textbook:

  1. Every sentence letter is a sentence.
  2. If $\mathscr A$ is a sentence, then $\lnot \mathscr A$ is a sentence.
  3. If $\mathscr A$ and $\mathscr B$ are sentences, then $\mathscr{(A\land B)}$ is a sentence.
  4. If $\mathscr A$ and $\mathscr B$ are sentences, then $\mathscr{(A\lor B)}$ is a sentence.
  5. If $\mathscr A$ and $\mathscr B$ are sentences, then $\mathscr{(A\rightarrow B)}$ is a sentence.
  6. If $\mathscr A$ and $\mathscr B$ are sentences, then $\mathscr{(A\leftrightarrow B)}$ is a sentence.
  7. Nothing else is a sentence.

Just as the inductive definition allows complex sentences to be built up from simpler parts, the definition allows us to decompose sentences into their simpler parts. Once we get down to sentence letters, then we know we are ok.

The author then goes on to give examples of how we can check whether some expression is a sentence or not. But the author only gives examples of expression which are sentences.

My problem is how will we show that expressions like $(A\lor B \land C)$ or $(\lnot A (B \lor C))$ (which I know is not a sentence) are not sentences by the rules given by the author? Or are the rules given by the author insufficient for deciding if they are sentences or not?

$\endgroup$

1 Answer 1

3
$\begingroup$

Your examples are easy, assuming $A$, $B$ and $C$ are sentence letters. According to the rules above, any sentence is either a sentence letter or of the form $\neg\mathscr{A}$ or of the form $(\mathscr{A}\circ\mathscr{B})$, where $\circ\in\{\wedge,\vee,\rightarrow,\leftrightarrow\}$. Neither $\left(A\vee B\wedge C\right)$ nor $\left(\neg A\left(B\vee C\right)\right)$ is of any of these forms, so, they are not, strictly speaking, sentences. Of course, if you have conventions, like "introducing parenthesis from left to right, for operations with equal scope", and if $\vee$ an $\wedge$ are of equal scope, then $\left(A\vee B\wedge C\right)$ is actually $\left(\left(A\vee B\right)\wedge C\right)$, and it is a sentence. But, in order to apply the formal rules, first you have to transform the formulas into their formal forms.

If everything is completely formal, then what you are asking can be checked by an algorithm. Here is a rough sketch: First check if the whole formula is an atomic sentence (here, sentence letter). If it is, return "It is a sentence". Else, check if the first symbol is "$\neg$", "$($" or none of them. If it is "$\neg$", then your formula must be of the form $\neg\mathscr{A}$. Then, everything that follows "$\neg$" must be $\mathscr{A}$, so the check procedure is called again, upon $\mathscr{A}$. If it starts with a parenthesis "$($", it must be of the form $(\mathscr{A}\circ\mathscr{B})$. Check if there is a closing parenthesis "$)$" and if there is one of $\wedge,\vee,\rightarrow,\leftrightarrow$, (call it "$\circ$") somewhere in the middle. If not, then return "it is not a sentence". If it is, then everything that lies between "$($" and "$\circ$" should be $\mathscr{A}$, and everything that lies between "$\circ$" and "$)$" should be $\mathscr{B}$. So, the check procedure is called again, first on $\mathscr{A}$, and then on $\mathscr{B}$. If the first symbol is neither "$\neg$" nor "$($", then return "It is not a sentence". This is a recursive procedure, which calls it self until it reach an atomic sentence or a dead end. If it reaches a dead end, then the verdict is "It is not a sentence", otherwise, the verdict is "It is a sentence".

For example, let us examine $\left(\left(A\vee B\right)\wedge C\right)$:

  1. It is not an atomic sentence.
  2. It begins with "$($", so it must be of the form $(\mathscr{A}\circ\mathscr{B})$.
  3. Indeed, it closes with "$)$", "$\circ$" is "$\wedge$", $\mathscr{A}$ is "$\left(A\vee B\right)$" and $\mathscr{B}$ is "$C$".
  4. Calling the procedure upon $\mathscr{A}$.
  5. It is not an atomic sentence.
  6. It begins with "$($", so it must be of the form $(\mathscr{A}\circ\mathscr{B})$.
  7. Indeed, it closes with "$)$", "$\circ$" is "$\vee$", $\mathscr{A}$ is "$A$" and $\mathscr{B}$ is "$B$".
  8. Calling the procedure upon $\mathscr{A}$.
  9. This is $A$. It is an atomic sentence.
  10. Ending procedure.
  11. Calling the procedure upon $\mathscr{B}$.
  12. This is $B.$ It is an atomic sentence.
  13. Ending procedure (returns to previews level).
  14. Calling the procedure upon $\mathscr{B}$.
  15. This is $C$. It is an atomic sentence.
  16. Ending procedure. Result: "It is a sentence".

On the other hand, let us examine $\left(A\vee B\wedge C\right)$:

  1. It is not an atomic sentence.
  2. It begins with "$($", so it must be of the form $(\mathscr{A}\circ\mathscr{B})$.
  3. Indeed, it closes with "$)$" But here, it can not decide between "$\vee$" and "$\wedge$". Dead end.
  4. Ending procedure. Result: "It is not a sentence".

Even if it the procedure can decide between "$\vee$" and "$\wedge$", (for example, if it works with the first logical operation it finds), then it will stop in a later step, when it will find that "$B\wedge C$" does not begin neither with "$\neg$" nor with "$($".

$\endgroup$
3
  • $\begingroup$ If you treat the expressions as formal strings, then $(A\vee B\wedge C)$ does formally match either $(\mathscr{A}\vee\mathscr{B})$ with $\mathscr{A} = A$, $\mathscr{B} = B\wedge C$ or $(\mathscr{A}\wedge\mathscr{B})$ with $\mathscr{A}=A\vee B$ and $\mathscr{B}=C$. So in the first case, you would need to descend to showing that $B\wedge C$ is not a sentence. Similarly, $(\lnot A(B\vee C))$ could match $\mathscr{A}\vee \mathscr{B}$ with $\mathscr{A} = \lnot A(B$ and $\mathscr{B} = C)$, and you'd need to choose one of those to show is not a sentence. $\endgroup$ Jun 1, 2021 at 1:18
  • $\begingroup$ @DanielSchepler Well, as I said, this is only a rough sketch. With $\left(A\vee B\wedge C\right)$, exactly because this is ambiguous, the procedure may end or not, depending on the details. If it does not end, it will end in a later stage, because $B\wedge C$ (or $A\vee B$ etc) is not a sentence: it does not begin neither with "$\neg$" nor with "$($". I have actually written a proof checker in c++ which uses similar rules. It works fine. But it surely has a lot more elaboration than I present here. $\endgroup$ Jun 1, 2021 at 1:46
  • $\begingroup$ Thanks, your answer is perfect. $\endgroup$
    – Navneet
    Jun 1, 2021 at 2:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.