Propositional Logic --- Level A

Subjects to be Learned

• how to construct complex propositions i.e. syntax of proposition

Contents

Syntax of propositions

First it is informally shown how complex propositions are constructed from simple ones. Then proposition is defined rigorously by recursive definition.

In everyday life we often combine propositions to form more complex propositions without paying much attention to them. For example combining "Grass is green", and "The sun is red" we say something like "Grass is green and the sun is red", "If the sun is red, grass is green", "The sun is red and the grass is not green" etc. Here "Grass is green", and "The sun is red" are propositions, and form them using connectives "and", "if... then ..." and "not" a little more complex propositions are formed. These new propositions can in turn be combined with other propositions to construct more complex propositions. They then can be combined to form even more complex propositions. This process of obtaining more and more complex propositions can be described more generally as follows:

Let X and Y represent arbitrary propositions. Then
[ X],   [X Y],  [X Y],   [X Y],   and   [X Y]
are propositions.

Note that X and Y here represent an arbitrary proposition.

Example : [ P -> [Q V R] ] is a proposition and it is obtained by first constructing [Q V R] by applying [X V Y] to propositions Q and R, then by applying [ X -> Y ] to the two propositions P and [Q V R].


Note: Rigorously speaking X and Y above are place holders for propositions, and so they are not exactly a proposition. They are called a propositional variable, and propositions formed from them using connectives are called a propositional form. However, we are not going to distinguish them here, and both specific propositions such as "2 is greater than 1" and propositional forms such as (P Q) are going to be called a proposition.

Rigorous Definition of Proposition (Propositional Form) --- Syntax Rules for Proposition

Proposition can be described in a more rigorous way using recursive definition as follows:

A proposition (also called propositional form) here is a template for propositions. It is a 'legal' form for propositions. Every proposition must take one of these forms. It shows how larger more complex propositions can be generated from simpler ones in general terms. Here they are defined as a set.

The set of propositions is the set that satisfies the following three clauses:

1. Basis Clause: The truth values 'true' and 'false', and all propositional variables such as P and Q are a proposition. Here a propositional variable is a variable that takes an individual specific proposition as its value.

2. Inductive Claus: If E and F are propositions, then , , , , and are propositions.
3. Extremal Clause: Nothing is a proposition unless it is obtained by 1. and 2.

Note : As you might have noticed, [ ] and ( ) are used interchangeably for propositions.

Example

, where P, Q, R, and S are propositional variables, is a proposition because it can be obtained by first generating , and by applying the inductive clause to the propositional variables P and Q, and R and S, respectively, then by combining them with agian applying the inductive clause.

Test Your Understanding of Construction of Propositions