The propositional calculus, often called zeroeth order logic, governs the use of logical connectives like “and”, “or” and “if … then”. It does not concern itself with quantifiers, like “for all” or “there exists”, which belong to first order logic. It does not concern itself with the meaning of the statements combined with those connectives. It should be noted though that it can only be expected to behave as expected when those statements are either definitely true or false. It does not cope well with statements like “this statement is false.”
Our language for zeroeth order logic will consist of variables and logical operators. We’ll use lower case letters, starting with \({ p }\) for variables and single symbols for logicial operators. In particular we’ll use \({ ∧ }\) for “and”, \({ ∨ }\) for “or”, and \({ ¬ }\) for “not”. The grammar will also allow the use of \({ ⊃ }\) for “implies”, \({ ⊼ }\) for “nand”, \({ ⊻ }\) for “nor”, \({ ≡ }\) for “if and only if”, \({ ≢ }\) for “xor”, and \({ ⊂ }\) for “if”, but we’ll only ever use the first two of those, will use the second only briefly. We’ll use an infix notation but, having learned our lesson from the last chapter, we’ll use a fully parenthesised version rather than relying on precedence and associativity rules. To make it easier to spot matching parentheses we’ll use not just \({ ( }\) and \({ ) }\) but also \({ [ }\) and \({ ] }\) and \({ \{ }\) and \({ \} }\). These are to be regarded as fully equivalent though. Anywhere they appear in the following discussion any of the above pairs may be replaced with any other. We’ll use the lower case latin letters \({ p }\), \({ q }\), \({ r }\), \({ s }\) and \({ u }\) for variables. We skip \({ t }\) because some authors use it as a Boolean constant, signifying the value “true”, although we won’t do that.
The weird symbols for logical operators are unfamilar at first sight but forcing all symbols to be single characters shortens formulae, makes a lexical analyser unnecessary and allows us to dispense with whitespace as a way of separating symbols.
For theoretical purposes it’s convenient to allow an infinite number of variables so we’ll also allow adding arbitrarily many exclamation points to these letters to create new variables, like \({ p }\), \({ p ! }\), \({ p ! ! }\), etc. We’ll never actually encounter an example where we run out of latin letters though, so this will remain just a theoretical possibility. Some treatments of zeroeth order logic also have constants symbols for the values “true” and “false” but we won’t introduce those.
Our grammar is then
%start statement
%%
statement : expression
;
expression : variable
| ( expression binop expression )
| [ expression binop expression ]
| { expression binop expression }
| ( ¬ expression )
| [ ¬ expression ]
| { ¬ expression }
;
variable : letter
| variable !
;
letter : p | q | r | s | u
;
binop : ∧ | ∨ | ⊃ | ⊼ | ⊻ | ≡ | ≢ | ⊂
;The spaces separate symbols in the specification. They aren’t part of the language. Single characters are all terminal symbols.
binop is short for binary operator and includes the
operators ∧, ∨, ⊃, ⊼, ⊻, ≡, ≢, ⊂. If they look like junk in the listing
above then that’s because few monospaced fonts include those glyphs.
We could have taken expression as the start symbol and
dispensed with statement entirely. It will be convenient to
have the distinction when we talk about rules of inference though. Every
statement is an expression but not every
expression is a statement. When we discuss the
rule of substitution, for example, it’s important that when we
substitute an expression for a variable in a statement that we replace
all occurences of that variable in the the statement, not just all in
some particular expression occuring in the statement.
There are certain symbols which are not part of our language but which we will use for talking about the language. We’ll use the upper case latin letters \({ P }\), \({ Q }\), \({ R }\), \({ S }\) and \({ U }\) to stand for arbitrary expressions. This is particularly useful in stating rules of inference. One commonly used rule of inference, for example, says that from statements of the form \({ P }\) and \({ ( P ⊃ Q ) }\) we can deduce the statement \({ Q }\). Here any expression incan be substituted for \({ P }\) and \({ Q }\). \({ P }\) and \({ Q }\) themselves though do not belong to the language. It’s understood, as discussed above, that different types of brackets are interchangeable so an instance of the rule above would be that from \({ ( r ∧ s ) }\) and \({ [ ( r ∧ s ) ⊃ ( r ∨ s ) ] }\) we can deduce \({ ( r ∨ s ) }\). This saves us from needing to repeat each rule three times, once for each set of brackets.