Table of Contents
PROPOSITIONS – Propositional Logic
First, you have to know that what is Proposition or what is Propositional Logic?
‘An elephant weighs more than a human being.’ When you read this declarative sentence, you can immediately decide whether it is true or false. And so can anyone else. Also, it wouldn’t happen that some people say that the statement is true and some others say that it is false. Everybody would have the same answer. So this sentence is either universally true or universally false.
It is a declarative sentence which is either true or false, but not both. In mathematical logic we call such sentences statements or propositions.
Would you say that the following are propositions?
‘Watch the film.
‘How wonderful!’
‘What did you say?’
Actually, none of them are declarative sentences. (The first one is an order, the second an exclamation, and the third is a question.) And therefore, none of them are propositions.
Now for some mathematical propositions! You must have studied and created many of them while doing mathematics. Some examples are
Two plus two equals four.
Two plus two equals five.
x + y > 0 for x > 0 and y > 0.
A set with n elements has 2n subsets.
Now consider the algebraic sentence ‘x + y > 0’. Is this a proposition? Are we in a position to determine whether it is true or false? Not unless we know the values that x and y can take. For example, it is false for
x = 1, y = -2 and true if x = 1, y = 0. Therefore,
‘x + y > 0’ is not a proposition, while
‘x + y > 0 for x > 0, y > 0’ is a proposition.
LOGICAL CONNECTIVES
When you’re talking to someone, do you use very simple sentences only? Don’t you use more complicated ones which are joined by words like ‘and’, ‘or’, etc? In the same way, most statements in mathematical logic are combinations of simpler statements joined by words and phrases like ‘and’. ‘or’, ‘if … then’. ‘if and only if’, etc. These words and phrases are called logical connectives. There are 6 such connectives, which we shall discuss one by one.
Disjunction
The disjunction of two propositions p and q is the compound statement p or q, denoted by p ∨ q.
For example, ‘Zarina has written a book or Singh has written a book.’ Is the disjunction of p and q, where
p: Zarina has written a book, and
q: Singh has written a book.
Similarly, if p denotes ‘ 2 > 0’ and q denotes ‘2 < 5’, then p ∨ q denotes the statement
‘2 is greater than 0 or 2 is less than 5.’.
Conjunction
We call the compound statement ‘p and q’ the conjunction of the statements p and q. We denote this by p ∧ q.
For instance, ‘3 + 1 ≠ 7 ∧ 2 > 0’ is the conjunction of ‘3 + 1 ≠ 7’ and ‘2 > 0’. Similarly, ‘2 + 1 = 3 ∧ 3 = 5’ is the conjunction of ‘2 + 1 = 3’ and ‘3 = 5’.
Negation
The negation of a proposition p is ‘not p’, denoted by ~p.
For example, if p is ‘Dolly is at the study center.’, then ~ p is ‘Dolly is not at the study center’. Similarly, if p is ‘No person can live without oxygen.’, ~ p is ‘At least one person can live without oxygen.’.
Conditional / Implication / if-then
Given any two propositions p and q, we denote the statement ‘If p, then q’ by p → q. We also read this as ‘p implies q’. or ‘p is sufficient for q’, or ‘p only if q’. We also call p the hypothesis and q the conclusion. Further, a statement of the form p → q is called a conditional statement or a conditional proposition.
So, for example, in the conditional proposition ‘If m is in Z, then m belongs to Q.’ the hypothesis is ‘m ∈ Z’ and the conclusion is ‘m ∈ Q’.
Biconditional / If and only if
Let p and q be two propositions. The compound statement (p → q) ∧(q → p) is the biconditional of p and q. We denote it by p ↔ q, and read it as ‘p if and only q’.
For example, ‘Sudha will gain weight if and only if she eats regularly.’ Means that ‘Sudha will gain weight if she eats regularly and Sudha will eat regularly if she gains weight.
The rule of precedence
The order of preference in which the connectives are applied in a formula of propositions that has no brackets is
i) ~
ii) ∧
iii) ∨ and ⊕
iv) → and ↔
LOGICAL EQUIVALENCE
We call two propositions r and s logically equivalent provided they have the same truth value for every choice of truth values of simple propositions involved in them. We denote this fact by r ≡ s.
We find out in the following table.
So, from the above table we find that ( p → q) ≡ (~ q → ~ p).
| Example 01 |
Q. For any two propositions p and q, show that ~ (p ∨ q) ≡ ~ p ∧ ~ q.
Solution: Consider the following truth table
You can see that the last two columns of the above table are identical. Thus, the truth valuesof ~ ( p ∨ q) and ~ p ∧ ~ q agree for every choice of truth values of p and q. Therefore, ~ (p ∨ q) ≡ ~ p ∧ ~ q.
The equivalence you have just seen is one of De Morgan’s laws. You might have already come across these laws in your previous studies of basic Mathematics.
The other law due to De Morgan is similar: ~ (p ∧ q) ≡ ~ p ∨ ~ q.
In fact, there are several such laws about equivalent propositions. Some of them are the following, where, as usual, p, q and r denote propositions.
a) Double negation law: ~ (~ p) ≡ p
b) Idempotent laws: p ∧ p ≡ p, p ∨ p ≡ p
c) Commutativity: p ∨ q ≡ q ∨ p, p ∧ q ≡ q ∧ p
d) Associativity: (p ∨ q) ∨ r ≡ p ∨ (q ∨ r), (p ∧ q) ∧ r ≡ p ∧ ( q ∧ r)
e) Distributivity: p ∨ ( q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r), p ∧ ( q ∨ r) ≡ (p ∧ q) ∨ ( p ∧ r)
Tautology
A compound proposition that is true for all possible truth values of the simple propositions involved in it is called a tautology.
Contradiction
A proposition that is false for all possible truth values of the simple propositions that constitute it is called a contradiction.
| Example 02 |
Q. Verify that p ∧ q ∧ ~ p is a contradiction and p → q ↔ ~ p ∨ q is a tautology.
Solution: Let us simultaneously draw up the truth tables of these two propositions below.
Predicate and Quantifiers |
