,
, 
, 
, ...
Syntactic and Semantic Foundations
of Predicate Logic
The Syntactic ``Alphabet''
0. ``Atomic'' sentences that are not atoms: true, false
1. Atoms: p , q , r , m , n , s , ,
, , , ...
2. Logical connectives: 
, 
, 
, 
,
(and the lesser ones like backward arrow, inequivalent)
3. Punctuation symbols: ( and ) and , (``comma'')
``NEW'' INGREDIENTS
4. Constants: a , b , c , d , 
, 
, ...
5. (Non-boolean) variables: u , w , x , y , z , 
,
, ...
Note: The constants and variables together are called terms.
6. n-place predicate symbols:
A( ) , B( ) , C( ) , D( ) , 
( ) , ...
(1-place predicates)
A( , ) , B( , ) , ... (2-place predicates), etc.
Note: The propositional variables ("atoms", to distinguish them from the non-boolean variables) p , q , r , ... may also be regarded as ``0-place predicate symbols''. Whereas, semantically, a 2-place predicate says something about a relationship between two elements of a set, a 0-place predicate just ``says something'' (which may be true or false, in a given state), but says nothing about the elements of the set in question. For instance, if the discussion is about the set of integers, and I say, ``I like potatoes'', then that is a statement with a truth value (true!! forever!), but it has nothing to do with the set of integers.
7. Quantifiers: 
, 
- these come with their
own punctuational baggage -
| (``such that''), and :
(pronounced
as a silent pause, after , and either the same way, or as
``and'', after , depending on how that symbol is pronounced)
Well-formed formulas (wffs) and sentences
of predicate logic
Just as we defined sentences recursively in propositional logic, we now define wffs recursively:
0. true and false are wffs.
Atoms are wffs.
An n-place predicate symbol fed with n terms is a wff.
(The wff's listed so far are ``indivisible'' ones - they have no ``compound'' structure, no ``main connective'', as do all wff's mentioned below in this list.)
1. If P is a wff, then so is 
.
2. If P and Q are wffs, then so are 
,
, 
, 
(and the others
involving the lesser connectives).
(As in propositional logic, here too we usually drop the outer parentheses that appear when the main binary connective is used, as in item 2., here.)
3. If 
and 
are wffs, and x is a (non-boolean)
variable, then the ``quantifications''
,
,
, and
are wffs.
(We may abbreviate the latter two as
and
.)
4. Nothing else is a wff.
A sentence is a wff that has no free occurrences of variables. In logic, one is interested really only in sentences, but it is also necessary to talk about general wffs occasionally, in a precise development of the subject.
So much for a start on the syntax of predicate logic. Next comes the semantics.
In propositional logic, one has the ``standard models'' for interpreting the uninterpreted strings of symbols that we recursively defined as sentences (we have the notion of truth value assignments, of states, of the truth table definitions of the connectives, etc.). In prop. logic, a model, or interpretation, is a state. Life is much more complicated in predicate logic. For one thing, there is now no such thing as ``standard models''. There is an endless assortment of models of limitlessly different sorts, all equally ``good''.
The rough idea now is that we want to interpret our sentences as
assertions about a certain set U and elements of that set,
subsets of that set, binary relations on the set,
ternary relations on
U , etc. ``Pure'', ``bare bones'' predicate logic, as discussed in
Chapter 9 of Gries-Schneider, stops there. One can go further and
introduce ``predicate logic with equality and function symbols'',
``typed predicate logic'', ``theories'', in which certain predicate
symbols and function symbols are singled out for special roles in
supplemental axioms of the logic, etc. We may not have time for much
beyond pure predicate logic.
Don't judge the typist by the appearance of this file solely. The filtre used to convert TeX documents to html is lacking some important features.