Page 101 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Unit 6: Formalized Symbolic Logics

This diagram shows the syntactic entities which may be constructed from formal languages. The Notes
symbols and strings of symbols may be broadly divided into nonsense and well-formed formulas.
A formal language can be thought of as identical to the set of its well-formed formulas. The set
of well-formed formulas may be broadly divided into theorems and non-theorems. A key use of
formulas is in propositional logic and predicate logics such as first-order logic. In those contexts,
a formula is a string of symbols ϕ for which it makes sense to ask “is ϕ true?”, once any free
variables in ϕ have been instantiated. In formal logic, proofs can be represented by sequences of
formulas with certain properties, and the final formula in the sequence is what is proven.
Although the term “formula” may be used for written marks (for instance, on a piece of paper or
chalkboard), it is more precisely understood as the sequence being expressed, with the marks
being a token instance of formula. It is not necessary for the existence of a formula that there be
any actual tokens of it. A formal language may thus have an infinite number of formulas
regardless whether each formula has a token instance. Moreover, a single formula may have
more than one token instance, if it is written more than once. Formulas are quite often interpreted
as propositions (as, for instance, in propositional logic). However formulas are syntactic entities,
and as such must be specified in a formal language without regard to any interpretation of them.
An interpreted formula may be the name of something, an adjective, an adverb, a preposition,
a phrase, a clause, an imperative sentence, a string of sentences, a string of names, etc.

Notes A formula may even turn out to be nonsense, if the symbols of the language are
specified so that it does. Furthermore, a formula need not be given any interpretation.

An expression P(t ,…,t ) where P is a predicate symbol of arity n and t ,…t are terms is a WFF
1 n 1 n
If S is a WFF then so is ¬S
If S and S are WFFs then so is S ^ S
1 2 1 2
If S and S are WFFs then so is S ^ S
1 2 1 2
If S and S are WFFs then so is S ^ S
1 2 1 2
If x is a variable and S is a WFF then so is " x. S
We say that any occurrence of x in S is bound.
If x is a variable and S is a WFF then so is $ x. S

We say that any occurrence of x in S is bound.
WFF may still contain unbound variables, for example:
" x. teaches(x, y) ^ Lecturer(x)

This can cause us problems when we try and interpret them as it’s not clear what we
should do with the variable.
To cope with this we define a further class of formulae known as sentences.

A sentence is a WFF with no unbound (or free) variables.
Any variable occurring in the formula is bound by a quantifier

LOVELY PROFESSIONAL UNIVERSITY 95