Logic for Computer Science and Artificial Intelligence

Chapter 3

Propositional Logic

The first logic we shall study is propositional logic (PL or PC), and although this logic has a limited expressive power, its wide variety of applications along with its role in the foundations of automation of first-order logic makes it an essential topic to study.

DEFINITION 3.1.– (proposition 1). A statement or an expression (i.e. a syntactically correct sequence of characters) that expresses a relation between several objects (terms) is a proposition.

For most of the material in this course, the following definition will be sufficient.

DEFINITION 3.2.– (proposition 2). A proposition is a statement or expression to which one (and only one) true value can be assigned.

REMARK 3.1.– Later on (see section 10.1), we shall see other possible values that can be assigned to a proposition.

EXAMPLE 3.1.– (declarative and imperative sentences).

“The factorial of 0 is 1” is a proposition.

“The factorial of 1 is 1” is a proposition.

“The factorial of n(n > 1) is n - 1 times the factorial of n - 2” is a proposition.

“Go to label LAB” is not a proposition.

“Store value 3 at the index labelled by x” is not a proposition.

We shall use two approaches to study PL (one semantical and the other syntactic). In both cases, we need a language.

3.1. Syntax and semantics

The key notion in the semantical approach is that of interpretation. In the syntactical approach (see section 3.3), it will be that of symbolic manipulation (which implies: independent of all meaning). ...