Page 94 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Introduction to Artificial Intelligence & Expert Systems

Notes Formal systems, like other syntactic entities may be defined without any interpretation given to
it (as being, for instance, a system of arithmetic). A formula A is a syntactic consequence within
some formal system FS of a set Γ of formulas if there is a derivation in formal system FS of A
from the set Γ.

Γ A
FS
Syntactic consequence does not depend on any interpretation of the formal system.

Syntactic Completeness of a Formal System

A formal system S is syntactically complete (also deductively complete, maximally complete,
negation complete or simply complete) if for each formula A of the language of the system
either A or ¬A is a theorem of S. In another sense, a formal system is syntactically complete if no
unprovable axiom can be added to it as an axiom without introducing an inconsistency. Truth-
functional propositional logic and first-order predicate logic are semantically complete, but not
syntactically complete (for example the propositional logic statement consisting of a single
variable “a” is not a theorem, and neither is its negation, but these are not tautologies). Gödel’s
incompleteness theorem shows that no recursive system that is sufficiently powerful, such as
the Peano axioms, can be both consistent and complete.

Self Assessment

State whether the following statements are true or false:
1. A formal systems is a syntactic entity which consists of a set of finite strings of symbols
which are its words.
2. Formation rules are a precise description of which strings of symbols are the well-formed
formulas of a formal language.

6.2 Syntax and Semantics for First-order Logic (FOL)

First-order logic is a formal system used in mathematics, philosophy, linguistics, and computer
science. It is also known as first-order predicate calculus, the lower predicate calculus, quantification
theory, and predicate logic (a less precise term). First-order logic is distinguished from
propositional logic by its use of quantified variables. A theory about some topic is usually first-
order logic together with a specified domain of discourse over which the quantified variables
range, finitely many functions which map from that domain into it, finitely many predicates
defined on that domain, and a recursive set of axioms which are believed to hold for those
things. Sometimes “theory” is understood in a more formal sense, which is just a set of sentences
in first-order logic.
The adjective “first-order” distinguishes first-order logic from higher-order logic in which
there are predicates having predicates or functions as arguments, or in which one or both of
predicate quantifiers or function quantifiers are permitted. In first-order theories, predicates are
often associated with sets. In interpreted higher-order theories, predicates may be interpreted as
sets of sets. There are many deductive systems for first-order logic that are sound (all provable
statements are true) and complete (all true statements are provable). Although the logical
consequence relation is only semi decidable, much progress has been made in automated theorem
proving in first-order logic. First-order logic also satisfies several met logical theorems that
make it amenable to analysis in proof theory, such as the Löwenheim – Skolem theorem and the
compactness theorem. First-order logic is of great importance to the foundations of mathematics,
because it is the standard formal logic for axiomatic systems. Many common axiomatic systems,

88 LOVELY PROFESSIONAL UNIVERSITY