Introduction of Logic and Proofs

UNIT I: LOGIC AND PROOFS

SYLLABUS

Propositional Logic Propositional equivalences Predicates and Quantifiers - Nested Quantifiers - Rules of inference introduction to proofs – Proof  methods and strategy.

INTRODUCTION

A proposition is a declarative sentence that is either true or false, but not both. The area of logic that deals with propositions is called the propositional calculus or propositional logic. It was first developed systematically by the Greek philosopher Aristotle more than 2300 years ago.

English mathematician George Boole discussed new propositions from those that we already have, in his book "The Laws of Thought" in 1854.

Many mathematical statements are constructed by combining one or more propositions. New propositions called compound propositions, are formed from existing propositions using logical operators.

PROPOSITIONS

Definition

A proposition (statement) is a declarative sentence that is either true or false, but not both.

Example

1. Chennai is the capital of Tamil Nadu [True]

2. 1+5 = 6 [True]

3. 2+7 = 10 [False]

4. Delhi is in America. [False]

Note: Here we will not use declarative sentences that can be simultaneously true and false, we are ruling out certain "self-contradictory statements".

Examples

1. This statement is false [we cannot say True or False]

2. Do you speak English? is a question, not a statement.

3. Obey orders, is a command, not a statement.

4. x + 4 = 2 is neither true nor false.

In the above sentences we cannot assign true or false.

Notation :

P, Q, R, S ... are used to denote propositions.

T is used to denote True proposition.

F is used to denote False proposition.

Definition :

Atomic statements: [Primary statements] [Simple]

Declarative sentences which cannot be further split into simpler sentences are called Atomic statements (also called primary statements or primitive statements)

Example: Rama is a boy.

EXERCISE

1. Define proposition.

2. Define atomic statement.

3. Which of the following are statements.

(a) x2+x+1 = 0  [Ans. Statement]

 (b) There will be snow in January. [Ans. Statement]

(c) If stock prices fall, then I will lose money. [Ans. Statement]

(d) Study logic. [Ans. not a statement]

(e) Close the box. [Ans. not a statement]

 (f) Do you speak Telugu ? [Ans. not a statement]90oi

4. Which of these sentences are propositions? What are the truth values of those that are propositions ?

(a) 2 + 3 = 5 [Ans. proposition, T]

(b) 5+ 7 = 10 [Ans. proposition, F]

(c) What time is it? [Ans. Not proposition]

(d) x + 2 = 11 [Ans. Not proposition]

(e) Answer this question. [Ans. Not proposition]

(f) x + y = y +x for every pair of real numbers x and y. [Ans. proposition, T]