next up previous
Next: Semantics Up: Equational Logic Previous: Equational Logic

Syntax

The syntax of an equational logic is very simple. The basic kind of formulae you write is of the form:

tex2html_wrap_inline169

where tex2html_wrap_inline171 and tex2html_wrap_inline173 are quantifier-free expressions, usually typed. tex2html_wrap_inline171 and tex2html_wrap_inline173 may or may not have variables in them. It's important that tex2html_wrap_inline171 and tex2html_wrap_inline173 are quantifier-free because any variables that do appear in tex2html_wrap_inline171 and tex2html_wrap_inline173 are implicitly universally quantified.

You can think of the = (equal) symbol as just a very special predicate symbol in a predicate logic. We very well could have introduced a word for this predicate, e.g., equal, and have written tex2html_wrap_inline189 instead of the equation above. Here, we are appealing to your intuition by using the symbol = and treating it as a binary infix operator rather than a prefix operator.

In a typed logic, the expressions on the right and left hand sides of = have to be of the same type for the whole expression to make sense. You can write

tex2html_wrap_inline147
tex2html_wrap_inline197

since for both equations the right and left hand sides both evaluate to integers but writing

tex2html_wrap_inline199
tex2html_wrap_inline201

is utter nonsense.

In a typed logic, we usually assume that for each type there is a special = symbol but we don't usually introduce different notation for each. In other words, I don't write tex2html_wrap_inline205 and tex2html_wrap_inline207 to distinguish between equality for integers and equality for colors. There is often one important exception, and that is for boolean expressions. You will see that many people use the tex2html_wrap_inline209 symbol (pronounced ``is equivalent to'') to denote equality between boolean expressions.gif So you can write things like

tex2html_wrap_inline215
tex2html_wrap_inline217



Norman Papernick
Fri Mar 15 12:00:46 EST 1996