Basic Mathematical Logic I for IITJEE and Math and Physics Olympiads

It is necessary to think clearly and to communicate precisely. Whereas in the arts and other disciplines, there is no room for ambiguity in the mathematical sciences. Here’s a primer on logic for aspirants of IITJEE, and Mathematics and Physics Olympiads.

Reference: 

1) Introduction to General Topology  by K.D. Joshi

2) Topology by Munkres

Mathematics is a language. For example, language of physics. If Math is regarded as a language, then logic is its grammar. In other words, logical precision has the same importance in Math as grammatical correctness in a language.

I. Statements and their Truth Values:

A statement is a declarative sentence, conveying a definite meaning, which may be either true or false but not both simultaneously. Incomplete sentences, questions and exclamations are not statements.

Some examples of statements are:

i) John is intelligent.

ii) If there is life on Mars, then the postman delivers a letter.

iii) Either grandmother chews gum, or missiles are costly.

iv) Every man is mortal.

v) All men are mortal.

vi) There is a man, who is eight feet tall.

vii) Every even integer greater than 2 can be expressed as a sum of 2 prime numbers.

viii) Every man with six legs is intelligent.

Some remarks on the above:

Statements 4 and 5 are statements about all the members of a class. So, in order to produce a counter-example, we say “there exists a man who  is not mortal” or in polished English, “there exists a man who is immortal”. By truth value of a statement, we mean, unambiguously, whether it is true or false (no grey areas here; it’s all black and white!!), Truth value is known to electrical engineers or computer scientists/engineers as digital logic or binary logic. (Actually, math students will recall here boolean laws of thought or set theory).  A conjecture is a statement whose truth value is not known at present. Thus, statement (vii) is the famous Goldbach conjecture. Statement six talks about a six-legged man, and of course, there is no such man (at least on earth!) and hence, we cannot produce a counter example, and hence, the statement is said to be vacuously true. Note also says that statement (ii) sounds strange. This statement is only mathematical “if then” statement; it is not a statement of cause and effect in the physical universe subject to laws of physics/chemistry/biology ! So, also the next statement.

Can the following be valid statements?

  • Will it rain
  • Oh! those heavy rains.
  • I am telling you a lie.

Out of the above, the first two are not statements, obviously. The third statement refers to itself, and hence, is circular, and is called a paradox.

II) Negation, Conjunction, Disjunction and their values:

IIa) Negation: To negate a statement, technically speaking, simply put a NOT in front of the whole statement. The negation of a statement is its counter-example.

Here’s an interesting example: consider the statement, “John is very intelligent”. The negation is not “John is very dull”. The original statement refers to degrees of intelligence. So, the correct negation is “John is not very intelligent”.

Consider the following statement: For every x \in A,, statement P holds. The negation of this statement is as follows: For at least one x \in A, statement P does not hold. Equivalently, there exists some x \in A such that statement P does not hold.

IIb) Disjunction or the meaning of “OR”:

In ordinary, everyday, colloquial English, the word “OR” is ambiguous. Sometimes, the statement “P or Q” means “P or Q or both” and sometimes, it means “P or Q but not both”. (EEs and CS engineers know this as inclusive OR and Exclusive OR). Usually, one decides from the context, which meaning is intended. For example, suppose I spoke two students as follows:

“Mr. Smith, every student registered for this course has taken either a course in linear algebra or a course in analysis.”

“Mr. Jones, either you get a grade of at least 70 on the final exam, or you will flunk this course.”

In the context, Mr. Smith knows perfectly well that I  mean ” everyone has had linear algebra or analysis or both”, and Mr. Jones knows I mean “either he gets at least 70 or he flunks, but not both.” Indeed, Mr. Jones would be exceedingly unhappy if both statements turned out to be true!!

In math, one cannot tolerate such ambiguity. In math, “or” always means “P or Q or both”. If we mean “P or Q or both, but not both”, we have to state it explicitly.

Meaning of “if …then”:

In everyday English, a statement of the form “if…then” is ambiguous. It always means if P is true, then Q is true. Sometimes, that is all it means, other times it means something more; that, if P is false, Q must be false. Usually, one decides from the context which interpretation is correct.

Examples:

“Mr. Smith, if any student registered for this course has not taken a course in linear algebra, then he has taken a course in analysis.”

“Mr. Jones, if you get a grade below 70 on the final, you are going to flunk this course.”

In the context, Mr. Smith understands that if a student in this course has not  had linear algebra, then he has taken analysis, but if he has had linear algebra, he may or may not have taken analysis as well. And, Mr. Jones knows that  if he gets a grade below 70, he will flunk the course, but if he gets a grade of at least 70, he will pass.

In math, if p, then q means the following: if p is true, q is true. But, if p is false, q may be either true or false. 

Contrapositive of a statement:

A statement of the form “if p, then q” is same as “if NOT q, then NOT p”. The latter is called its contrapositive. Many a times, it is easier to prove the contrapositive of a statement rather than the original statement!!

Example: If x < 0, then x^{3} \neq 0.

Contrapositive: if x ^{3}=0, then it is not true that x > 0.

Example: If x^{2}<0, then x=23.

Contrapositive: if x \neq 23, then it is not true that x^{2}<0

Converse of a statement:

The converse of a statement of the form “if p, then q” is “if q, then p”. Note that a statement and its converse are not the same.

Example: If a function is differentiable, then it is continuous. But, the converse is true. (that, if a function is continuous, it is differentiable).

Note: A definition is always if and only if; that is, if p, then q AND if q, then p.

 

 

 

 

 

 

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s