Tuesday, August 12, 2008

MATHEMATICAL LOGIC

© Moreniche

Introduction

One of the main aims of logic is to provide rules by which one can determine whether any particular argument or reasoning is valid (correct).

Logic is concerned with all kinds of reasonings, whether they are legal arguments or mathematical proofs or conclusions in a scientific theory based upon a set of hypothesis. Based on the diversity of their application, these rules are called rules of inference. In logic we are concerned with the forms of the arguments. The theory of inference is formulated in such a way that one should be able to decide about the validity of an argument by following the rules mechanically and independently of our own feelings about the argument.

Any collection of rules or any theory needs a language. In this language these rules or theory can be explained. Natural languages are not used, and are not suitable for this purpose. Therefore, a formal language (object language) is developed and syntax is well defined in the object language. Symbols are used to define clearly in the object language. The object language requires the use of another language. We can use any of the natural languages like English to form the statements. Here English is called meta language.

1.1.2 Atomic Statements

The object language consists of a set of declarative sentences. These declarative sentences are called primary or atomic or primitive statements. These statements have only two truth vales TRUE (T or 1) and FALSE (F or 0). The atomic statements are denoted by the symbols A, B, C, D, E, …

The atomic statements are joined by using symbols, connectives and parenthesis. The connected statements are called declarative sentences.

If declarative sentences assume only one truth-value T or F, those sentences are called statements. Atomic statements are those which do not contain any connectives.

Consider the following examples :

1. India is a country.

2. London is the capital of Japan.

3. This statement is true.

4. Open the gate.

5. Madurai is an old city.

6. Man will reach Mars by 2020.

Statements (1) and (2) have truth values true and false respectively. (3) is not a statement and one can not assign a definite truth value T or F. (4) is a command and not a statement. (5) is true in some part of the world and false in certain other parts. It is a statement. The truth-value of (6) could be determined only in the year 2020 or earlier if a man reaches Mars before that date.

Proposition : A proposition is a statement that is either true or false but not both.

Generally name is used as a name of the object.

Consider an example :

7. This chair is small.

"This chair" is used as a name of the object.

Consider another example :

8. Srinivasan is a good man.

9. "Srinivasan" contains ten letters.

The quality of a person is defined in (8) and the person’s name is Srinivasan. In (9), "Srinivasan" is used as a name of this name. (9) is about a name and not about a person.

1.1.3 Connectives

By using connectives, molecular or compound statements are formed from atomic statements. The statements are denoted by the capital letters A, B, C, D, E, …

Example 1:

Let A be a proposition.

A : Mr. Bill Clinton went to the White House.

1.1.4 Negation

The symbol ‘ù ’ is used to denote the negation. Alternate symbols used in the literature are ‘~’, a bar or "NOT", so that ù P is written as ~P, or NOT P.

Example 2:

B : I went to my native place yesterday.

ù B: I did not go to my native place yesterday.

Truth table 1.1.4

P

ùP

T

F

F

T

1.1.5 Conjunction

The conjunction of two statements A and B is the statement A Ù B which is read as "A and B". The statement A Ù B has truth value T whenever both A and B have truth value T; otherwise it has the truth value F.

Truth table 1.1.5

A

B

A Ù B

T

T

T

T

F

F

F

T

F

F

F

F

A : The University is conducting 25 Under Graduate courses.

B : It has 15 Post Graduate courses.

Solution:

The University is conducting 25 Under Graduate courses and it has 15

Post Graduate courses.

1.1.6 Disjunction

Let A and B be propositions. The disjunction of two statements A and B is the statement A Ú B Ú B which is read as "A or B". The proposition has the truth value F only when both A and B have the truth value F; otherwise it is true.

Truth table 1.1.6

A

B

A Ú B

T

T

T

T

F

T

F

T

T

F

F

F

Consider an example :

Baskaran shall play cricket or hockey tomorrow.

The statement and have 22 possible combinations of truth values. If there are n distinct components in a statement, then the proposition has 2n possible combinations of truth values in order to obtain the truth table. A statement formula has no truth value. In the construction of formulas, the parenthesis will be used.

For example,

1. ù ( ) means negation of .

2. means disjunction of and

means conjunction of and

1.1.7 Conditional and Bi-conditional

Consider two statements A and B. The statement is called conditional statement and is read as "If A, then B". The statement has truth value F when B has F and A has T; otherwise it has T. A is called antecedent and B the consequent in .

Truth table 1.1.7(a)

A

B

A ® B

T

T

T

T

F

F

F

T

T

F

F

T

is represented by any one of the following :

1. B is necessary for A.

2. A is sufficient for B.

3. B if A.

4. A only if B.

5. A implies B.

Write the following statement in symbolic form.

Example 1:

If Sindhu either reads the book or Vimal does the homework, then Viji will take the book to the college.

Solution:

Denoting the statement as

A : Sindhu reads the book.

B : Vimal does the home work.

C : Viji takes the book to the college.

Symbolic form:

Example 2:

If there is a fire, then the forest will be destroyed.

Solution:

Denoting the statement as

A : There is a fire.

B : The forest will be destroyed.

Symbolic form:

The statement A B is called bi-conditional statement. It is translated as "A is necessary and sufficient for B". The statement A B has truth value T when both A and B has T or F. Otherwise it has truth value F.

Truth table 1.1.7(b)

A

B

A B

T

T

T

T

F

F

F

T

F

F

F

T

Example 3:

Construct truth table for (A® B) Ù (B® A)

A

B

A ® B

B ® A

(A® B) Ù (B® A)

T

T

T

T

T

T

F

F

T

F

F

T

T

F

F

F

F

T

T

T

1.1.8 Well-formed formulas (wff)

A well-formed formula is nothing but a recursive definition of a statement formula. By applying the following rules a wff can be generated.

1. A statement variable standing alone is a wff.

2. If A is a wff, then ù A is a wff.

3. If A and B are wffs, then AÙ B, AÚ B, A® B and A B are wffs.

4. A string of symbols containing the statement variables, connectives and parenthesis is a wff.

Example : ù AÚB, AÚ ù B, A®(B C), A® (B®C)

1.1.9 Tautologies

A statement formula which is true regardless of the truth values of the statements which replace the variables in it is called a universally valid formula or a tautology or a logical truth. A statement formula which is false regardless of the truth values of the statements which replace the variables in it is called a contradiction. The negation of contradiction is a tautology.

Consider two statement formulas, which are tautologies. If we assign any truth values to the variables of A and B, then the truth values of both A and B will be T. Therefore, the truth values of A Ù B will be T, so that A Ù B will be a tautology.

A statement ‘A’ is said to tautologically imply a statement ‘B’ if and only if is a tautology. We shall denote this ideas by which is read as "A implies B".

1.1.10 Equivalence of Formulas

  1. ù ùP is equivalent to P.
  2. P Ú P is equivalent to P.
  3. P Ú ùP is equivalent to Q Ú ù Q.
  4. ( P Ú ùP ) Ú Q is equivalent to Q.

The equivalence of two formulas A and B is written as "AÛ B" which is read as "A is equivalent to B".

Examples:

  1. P® Q Û ùP Ú Q.

P Q Û (P® Q) Ù (Q® P)

1 comment:

divya said...

looking very odd!