Page 95 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Unit 6: Formalized Symbolic Logics

such as first-order Peano arithmetic and axiomatic set theory, including the canonical Zermelo – Notes
Fraenkel set theory (ZF), can be formalized as first-order theories.

Notes No first-order theory, however, has the strength to describe fully and categorically
structures with an infinite domain, such as the natural numbers or the real line. Categorical
axiom systems for these structures can be obtained in stronger logics such as second-order
logic.

Propositional Logic is concerned with propositions and their interrelationships. The notion of a
proposition here cannot be defined precisely. Roughly speaking, a proposition is a possible
condition of the world about which we want to say something. The condition need not be true
in order for us to talk about it. In fact, we might want to say that it is false or that it is true if some
other proposition is true. In this unit, we first look at the syntactic rules for the language of
Propositional Logic. We then look at semantic interpretation for the expressions specified by
these rules. Given this semantics, we define the concept of propositional entailment, which
identifies for us, at least in principle, all of the logical conclusions one can draw from any set of
propositional sentences.

Syntax

In Propositional Logic, there are two types of sentences – simple sentences and compound
sentences. Simple sentences express “atomic” propositions about the world. Compound sentences
express logical relationships between the simpler sentences of which they are composed. Simple
sentences in Propositional Logic are often called propositional constants or, sometimes, logical
constants. In what follows, we refer to a logical constant using a sequence of alphanumeric
characters beginning with a lower case character. For example, raining is a logical constant, as
are rAiNiNg and r32aining. Raining is not a logical constant because it begins with an upper
case character. 324567 fails because it begins with a number. Raining-or-snowing fails because it
contains non-alphanumeric characters. Compound sentences are formed from simpler sentences
and express relationships among the constituent sentences. There are six types of compound
sentences, viz. negations, conjunctions, disjunctions, implications, reductions, and equivalences.
A negation consists of the negation operator ¬ and a simple or compound sentence, called the
target. For example, given the sentence p, we can form the negation of p as shown below:
¬p
A conjunction is a sequence of sentences separated by occurrences of the ∧ operator and enclosed
in parentheses, as shown below. The constituent sentences are called conjuncts. For example, we
can form the conjunction of p and q as follows:
(p ∧ q)

A disjunction is a sequence of sentences separated by occurrences of the ∨ operator and enclosed
in parentheses. The constituent sentences are called disjuncts. For example, we can form the
disjunction of p and q as follows:
(p ∨ q)
An implication consists of a pair of sentences separated by the ⇒ operator and enclosed in
parentheses. The sentence to the left of the operator is called the antecedent, and the sentence to
the right is called the consequent. The implication of p and q is shown below:
(p ⇒ q)
A reduction is the reverse of an implication. It consists of a pair of sentences separated by the ⇐
operator and enclosed in parentheses. In this case, the sentence to the left of the operator is called

LOVELY PROFESSIONAL UNIVERSITY 89