What is it??
It is a foundation which gives precise meaning to mathematical statements. It is the basis on which proofs and arguments rest (well, we are not referring to those court room arguments for sure. However, even those, we believe, could be expressed in terms of Mathematical Logic).
INTRODUCTION
The basic building blocks of logic are – PROPOSITIONS.
1. Propositions (or Statements)
A proposition is a statement that can be either true or false.
For example, consider the following statements:
1. Delhi is the capital of India.
2. 5 multiplied by 10 is 15.
3. How much time is remaining?
4. x + 1 = 2.
First two statements are propositions. Statement 1 has the truth value true while statement 2 has truth value false.
The third and fourth statements are not propositions. Sentence 3 is not a statement as it cannot be assigned any truth value. While 4th sentence can take either true or false value depending on the value of x.
NOTE: Truth values are denoted by letters. The truth value True is denoted by T while false is denoted by F (capitalized values only).
Propositions are also denoted by letters. Commonly used letters are p, q, r… etc. (both small/ upper case letters).
Connectives (Propositional Connectives or Logical connectives)
Propositional connectives can be used to produce new propositions from those that we already have. We present here those which might ever be used during your engineering grad course:
Negation (NOT)
Let P be a proposition. Then the negation of P:
“It is not the case that P” is another proposition. It is denoted by: ¬P and is read as “not P”.
Its truth table is:
|
P |
¬P |
|
F |
T |
|
T |
F |
Conjunction (AND)
If P and Q are two propositions then the conjunction of P and Q is the proposition: “P and Q”, which is denoted by P Ʌ Q. This new proposition will be true only when both P and Q are true.
Its truth table is:
|
P |
Q |
P Ʌ Q |
|
F |
F |
F |
|
F |
T |
F |
|
T |
F |
F |
|
T |
T |
T |
Disjunction (OR)
If P and Q are two propositions then the disjunction of P and Q is the proposition: “P or Q”, denoted by
P V Q. This new proposition will be true when at least P or Q is true.
Its truth table is:
|
P |
Q |
P V Q |
|
F |
F |
F |
|
F |
T |
T |
|
T |
F |
T |
|
T |
T |
T |
Implication (IF… THEN…)
Implication is denoted by P→Q and is read as “P implies Q” or in other words “If P Then Q”. Its truth table is as follows:
|
P |
Q |
P→Q |
|
F |
F |
T |
|
F |
T |
T |
|
T |
F |
F |
|
T |
T |
T |
It is also equivalent to ¬P V Q.
Terms like Hypothesis (or antecedent or premise) are also used for P, while Q is also termed as Conclusion (or consequence).
The implication can be thought of as a contract validation/ obligation between the two propositions. Consider the statement “If you earn more than 2 Lac. Rupees, you must file income tax return”. For this statement P can be taken as “Earn more than 2 lac Rupees” and Q can be taken as “File income tax return”. Then the statement is an implication P→Q. In this case whenever P is true, then for the contract/ obligation to hold, Q must also be true. One would violate the contract only if one earns more than 2 Lac Rupees (P is true) and does not file the income tax return (Q is false). In all the other cases the contract holds true.
The proposition Q→P is the converse of P→Q.
Also, ¬Q→P is called the Contrapositive of P→Q.
IF and Only IF (iff)
It is a bi-conditional logical connective between the statements. It is denoted by P ↔ Q. This connective can be likened to the standard IF… THEN condition combined with its reverse IF, i.e. P ↔ Q is equivalent to an implication between P and Q from both sides (P→Q Ʌ Q→P). This can be seen from the truth table below:
|
P |
Q |
P ↔ Q |
P→Q Ʌ Q→P |
|
F |
F |
T |
T |
|
F |
T |
F |
F |
|
T |
F |
F |
F |
|
T |
T |
T |
T |
As a continuation of the example used for ‘implication’ above, let’s consider the sample statement again with bi-conditional logic this time:
“You must file income tax return if and only if you earn more than 2Lac Rupees”.
Now the above statement may be thought of as a combination of the below two statements:
“If you earn more than 2Lac Rupees then you must file income tax return”.
And
“If you file income tax return then you must earn (or your income must be) at least 2Lac Rupees”.