Propositional Logic - Syntax

Why have a formal representation if not for cool symbols? Each atomic statement we formalize as a variable. Normally we use small letters in the English alphabet starting with \( p \): $$ p,q,r,s,\dots $$ The connectives we translate as thus

• Conjunction we write as \( \land \).
• Disjunction we write as \( \lor \).
• Implication we write as \( \rightarrow \).
• Negation we write as \( \neg \).

Now we can formalize the sentence "If I have a cat, then I do not have a dog". Let \( p = have\ cat \), let \( q = have\ dog \), and we get $$ p \rightarrow \neg q $$

In order to construct more and more complex expressions from atomic ones we need what is called a grammar (or a syntax). We use Greek letters \( \phi,\psi,\dots \) to denote formulas. These are just any combination of connectives and atomic variables we can form using this grammar. The grammar is just a set of rules on how we can combine. It seems reasonable that an expression like $$ p\ q \rightarrow \land q )) $$ should lead to a syntax error. We combine as follows. By \( \phi \rightarrow ... \) we mean that \( \phi \) is a formula variable that can take on the form of what is right of the arrow. First of all we have $$ \phi \rightarrow p,q,r,\dots $$ That is a formula \( \phi \) can take on the form of any of the atomic variables. Conversely any atomic variable is a formula. Next we are concerned with the connectives: $$ \phi \rightarrow \phi \land \phi | \phi \lor \phi | \phi \rightarrow \phi | \neg \phi $$ Here | means that we can choose freely between the right and the left expression of that bar. So $$ p \land q $$ is a formula since $$ \phi \land \psi $$ is a formula. Finally we want to include parentheses $$ \phi \rightarrow ( \phi ) $$ Any \( \phi \) on the right side of the arrow in the above we can substitute with any of these expressions. This is called syntactic parsing using formal grammars like BNF. Without going deeper into this we can just use it to state that $$ p \rightarrow q \land (r \lor q) $$ is well formed whereas $$ p ( \rightarrow q) $$ isn't.

Lastly we can introduce binding conventions. We say that \( \neg \) binds more tightly than \( \land \) and \( \lor \) which binds more tightly than \( \rightarrow \). \( \rightarrow \), as opposed to the other connectives, is right associative. That is we read \( p \rightarrow q \rightarrow r \) as \( p \rightarrow (p \rightarrow r) \).