Topic: Propositional logic.

Originally the 2-value Boolean logic was developed by John Boole (England, 1823-1864) to explore which Natural language statements are logically sound and which are not. For some decades this mathematical tool had no practical application. Later it was found that the 2-value Boolean logic is very convenient for performance description of electrical circuits with switches, compute electronic circuits and other systems.

Definitions:

A statement is any sentence that can be true of false(has a truth value).

" Kharkov is a city." (true)

" Now it is summer." (false) statements

" Some birds can fly." (true)

" Go home! " (order) not statements

" What is your name? " (question)

" What I am saying is not true"

" A barber shaves everybody who do not shave themselves"

These are paradoxical statements: they have hidden contradiction. It is impossible to say if they are true of false.

Statements can be simple or compound.

" Today is Friday."

" It is sunny now."

" 2+3=5"

" 2+2=6"

Compound statements are made up of one or more simple (or compound) statements that are linked together by connectives. Five basic connectives:

- not

- and

- or

- if...then...

-if and only if...

Examples of compound statements:

- It is not Monday.

- It is raining and the sky is cloudy.

- If today is Saturday then I must not go to work.

- 5* x=5 if and only if x=1.

- if x=2 and y=3 then x+y=100.

- The sun is not shining if and only if tomorrow is Saturday and there are no clouds in the sky.

Note: A compound statement does not have to make much sense.

An inductive (formal) definition of a compound statement:

1) All simple statements are compound statements.

2) If S and T are compound statements then

a) (not S) is a compound statement

b) (S and T) is a compound statement

c) (S or T) is a compound statement

d) (if S then T) is a compound statement

e) (S if and only if T) is a compound statement

3) Nothing is a compound statement unless it can be obtained by a finite number of applications of steps 1 and 2.

Note: Mathematical logic cannot tell if a simple statement is true or false. This we must decide by other means. The goal of the mathematical logic is to tell us whether a compound statement is true or false, depending on the truth values of its simple statements.

Example:

" Today it is Wednesday and it is raining."

statement p statement q

The structure of the above compound statement in a symbolic form:.

Here p, q are simple statements.

Note: In mathematical logic it is the logical structure of a compound statement that is important, not its individual simple statements.

" I am a teacher and 2+2=5"

All have the same logical structure and may be viewed as the same statement from logical point of view.

The precise meaning of each of the five basic connectives is defined by such truth tables:

conjunction (p q) disjunction (p q) negation ~p

p è q (conditional) p ç è q (biconditional)

Note: Sentences: " if p then q ", " p only if q ", " p implies q " all have the same logical meaning.

Note: Lines 3 and 4 in the table for pè q represent such a common sense concept: " If an assumption is wrong then any conclusion is acceptable because nobody bothers to consider it."

Ex: If 2*2=5 then I am mother of Napoleon. (true)

If 2*2=5 then 3*2=6. (true)

In such cases we should not consider what is after " then".

Examples of transforming compound statements into symbolic forms:

" John is in the library or he is not at the book store." (1)

p=" John is in the library"

q= " John is in the book store."

The symbolic form of statement (1): p ~q.

" If today is Monday or it is not raining then we can go to the store". (2)

p=" Today is Monday."

q= " it is raining".

z=" we can go to the store"

The symbolic form for statement (2): p ~q è r.

Ex: Let p=" I study", q=" I will pass the course."

The formula (pè q) (~p è ~q) is the symbolic form of the statement:

" If I study, then I will pass this course and if I do not study, then I will not pass this course"

Note: Letters p, q, etc, in symbolic forms are called statement variables of the compound statement.

Self test questions:

1.) Which of the following are statements?

a)All men are created equal.

b)John.

c) No smoking

d) Are you ready?

2.) Find the negation of the following statements:

a) All fish can swim.

b) Today is not Friday.

c) It is not true that today is not a holiday.

3.) Let p=" I am a teacher" and let q=" 2+2=5"

a) I am not a teacher nor is 2=2+5.

b) If am not a teacher then 2+2 5.