|
A formal system consists of:
- A finite set of symbols or vocabulary, S
.
- A set expressions that are formed from the vocabulary.
This set of expressions is a subset of S*
- Rules of inference.
For example, if the vocabulary is the set of words:
{ Jim, is, old }
then the set of possible expressions that could
be formed using concatenation to combine (i.e,
putting one element after another) the elements of this vocabulary
are:
{Jim, is, old,
Jim Jim, Jim is, Jim old,
is Jim, is is, is old,
old Jim, old is, old old,
Jim Jim Jim, Jim is Jim, Jim old Jim,
is Jim Jim, is is Jim, is old Jim,
old Jim Jim, old is Jim, old old Jim,
Jim Jim is, Jim is is, Jim old is,
is Jim is, is is is, is old is,
old Jim is, old is is, old old is,
Jim Jim old, Jim is old, Jim old old,
is Jim old, is is old, is old old,
old Jim old, old is old, old old old
...}
The set of possible expressions is referred to as S* and is simply the set of all combinations
of the elements of the vocabulary of length n where n = 1, 2,
3, 4, ... We have explicitly shown the sets of possible expressions
of length 1, 2 and 3 for this three element vocabulary. There
are 3 expressions of length 1; 9 of length 2, and 27 of length
3. In general, if the vocabulary has n elements then the total
number of possible expressions of length j or less is given by
the summation over j of n to the jth power.
Thus, for this example, the total would be 39 for j =3, 120 for
j = 4, 363 for j = 5, 1092 for j = 6 and so on.
This is an example of what is called a combinatoric
system. In this system concatenation provides a basis for generating
the set of all of the possible combinations that can be obtained
from a base vocabulary. However, in a formal system not
all possible expressions are legal or syntactically
correct expressions. Only the expressions in bold above would
be syntactically correct if this formal system used the syntax
of our natural language.
|
|
In order to illustrate the notion of inference in a
formal system, I have provided a different example. Here the
vocabulary is
{ |, +, = }
where | is a 'stick' which I am interpreting as a mark denoting
1.Then this vocabulary can be thought of as one that can be used
to describe ordinary addition. In this case, I have computed
all of S* that is of
length 5 or less. The items in bold face represent those that
are syntactically correct expressions. ( I may have missed some!)
Those that are in bold and in italics and underlined are expressions
that while syntactically correct would violate the rules of addition.
If we were to generate more of the possible expressions we would
find the expressions:
| + | = | | and | | = | + |
this is an example of a pattern which could be used to define
a rule of inference; namely, whenever you encounter the expression
on the left you may infer or derive the expression on the right.
This rule of inference is valid in addition because the operation
of + is commutative. Note that this rule of inference can be
stated by simply making reference to the syntax (or "shape")
of the statements. We don't have to "understand" addition.
{|, +, =,
| |, | +, | =,
+ |, + +, + =,
= |, = +, = =,
| | |, | + |, | = |,
+ | |, + + |, + = |,
= | |, = + |, = = |,
| | +, | + +, | = +,
+ | +, + + +, + = +,
= | +, = + +, = = +,
| | =, | + =, | = =,
+ | =, + + =, + = =,
= | =, = + =, = = =,
| | | |, | + | |, | =
| |,
+ | | |, + + | |, + = | |,
= | | |, = + | |, = = | |,
| | + |, | + + |, | = + |,
+ | + |, + + + |, + = + |,
= | + |, = + + |, = = + |,
| | = |, | + = |, | = = |,
+ | = |, + + = |, + = = |,
= | = |, = + = |, = = = |,
| | | +, | + | +, | = | +,
+ | | +, + + | +, + = | +,
= | | +, = + | +, = = | +,
| | + +, | + + +, | = + +,
+ | + +, + + + +, + = + +,
= | + +, = + + +, = = + +,
| | = +, | + = +, | = = +,
+ | = +, + + = +, + = = +,
= | = +, = + = +, = = = +,
| | | =, | + | =, | = | =,
+ | | =, + + | =, + = | =,
= | | =, = + | =, = = | =,
| | + =, | + + =, | = + =,
+ | + =, + + + =, + = + =,
= | + =, = + + =, = = + =,
| | = =, | + = =, | = = =,
+ | = =, + + = =, + = = =,
= | = =, = + = =, = = = =,
| | | | |, | + | | |, | = | | |,
+ | | | |, + + | | |, + = | | |,
= | | | |, = + | | |, = = | | |,
| | + | |, | + + | |, | = + | |,
+ | + | |, + + + | |, + = + | |,
= | + | |, = + + | |, = = + | |,
| | = | |, | + = | |, | = = | |,
+ | = | |, + + = | |, + = = | |,
= | = | |, = + = | |, = = = | |,
| | | + |, | + | + |, | = | + |,
+ | | + |, + + | + |, + = | + |,
= | | + |, = + | + |, = = | + |,
| | + + |, | + + + |, | = + + |,
+ | + + |, + + + + |, + = + + |,
= | + + |, = + + + |, = = + + |,
| | = + |, | + = + |, | = = + |,
+ | = + |, + + = + |, + = = + |,
= | = + |, = + = + |, = = = + |,
| | | = |, | + | = |, | = | = |,
+ | | = |, + + | = |, + = | = |,
= | | = |, = + | = |, = = | = |,
| | + = |, | + + = |, | = + = |,
+ | + = |, + + + = |, + = + = |,
= | + = |, = + + = |, = = + = |,
| | = = |, | + = = |, | = = = |,
+ | = = |, + + = = |, + = = = |,
= | = = |, = + = = |, = = = = |,
| | | | +, | + | | +, | = | | +,
+ | | | +, + + | | +, + = | | +,
= | | | +, = + | | +, = = | | +,
| | + | +, | + + | +, | = + | +,
+ | + | +, + + + | +, + = + | +,
= | + | +, = + + | +, = = + | +,
| | = | +, | + = | +, | = = | +,
+ | = | +, + + = | +, + = = | +,
= | = | +, = + = | +, = = = | +,
| | | + +, | + | + +, | = | + +,
+ | | + +, + + | + +, + = | + +,
= | | + +, = + | + +, = = | + +,
| | + + +, | + + + +, | = + + +,
+ | + + +, + + + + +, + = + + +,
= | + + +, = + + + +, = = + + +,
| | = + +, | + = + +, | = = + +,
+ | = + +, + + = + +, + = = + +,
= | = + +, = + = + +, = = = + +,
| | | = +, | + | = +, | = | = +,
+ | | = +, + + | = +, + = | = +,
= | | = +, = + | = +, = = | = +,
| | + = +, | + + = +, | = + = +,
+ | + = +, + + + = +, + = + = +,
= | + = +, = + + = +, = = + = +,
| | = = +, | + = = +, | = = = +,
+ | = = +, + + = = +, + = = = +,
= | = = +, = + = = +, = = = = +,
| | | | =, | + | | =, | = | | =,
+ | | | =, + + | | =, + = | | =,
= | | | =, = + | | =, = = | | =,
| | + | =, | + + | =, | = + | =,
+ | + | =, + + + | =, + = + | =,
= | + | =, = + + | =, = = + | =,
| | = | =, | + = | =, | = = | =,
+ | = | =, + + = | =, + = = | =,
= | = | =, = + = | =, = = = | =,
| | | + =, | + | + =, | = | + =,
+ | | + =, + + | + =, + = | + =,
= | | + =, = + | + =, = = | + =,
| | + + =, | + + + =, | = + + =,
+ | + + =, + + + + =, + = + + =,
= | + + =, = + + + =, = = + + =,
| | = + =, | + = + =, | = = + =,
+ | = + =, + + = + =, + = = + =,
= | = + =, = + = + =, = = = + =,
| | | = =, | + | = =, | = | = =,
+ | | = =, + + | = =, + = | = =,
= | | = =, = + | = =, = = | = =,
| | + = =, | + + = =, | = + = =,
+ | + = =, + + + = =, + = + = =,
= | + = =, = + + = =, = = + = =,
| | = = =, | + = = =, | = = = =,
+ | = = =, + + = = =, + = = = =,
= | = = =, = + = = =, = = = = = }
|