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.

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). ...

Start Free Trial

No credit card required