Table of Contents
Mathematical Statements and Truth Tables:
Logical expressions are often used in algorithms and mathematical proofs. In order to express ideas, we use sentences of a particular kind. A knowledge of these sentences is thus necessary for a study of the language of valid reasoning. It is also necessary to have the truth values of these sentences. In some of these sentences, we use quantifying words or simply quantifiers like ‘some’, ‘none’, ‘all’ etc., or another type of logical quantifiers like ‘for every’ and ‘there exists’.
In mathematics, two types of quantifiers are used. Quantifiers that indicate all the elements of a certain set are known as universal quantifiers. On the other hand, the quantifiers which indicate the existence of at least one element in a certain set are referred to as existential quantifiers. Universal quantifiers are ‘every’, ‘all’, ‘each’, ‘none’ etc. ‘Some’ and ‘at least one’ are existential quantifiers.
The universal quantifiers are represented by the symbol ‘∀’. Thus, ‘∀x’ means ‘for all x’ or ‘for every x’. The existential quantifiers are denoted by the symbol ‘∃’. Thus ‘∃x’ means’ for at least one x’ or ‘for some x’ or ‘there exists an x’.
Clearly, ‘∀ x ∈ N, x = x’ denotes the mathematical statement ‘for all x belonging to the set of natural numbers, x = x’.
Also, ‘∃ x ∈ W, x < 2’ means ‘there exists at least one x in W such that x < 2’.
A statement or a proposition is a declarative sentence that is either true or false, but not both. We consider the following sentences:
(i) Mumbai is in India.
(ii) 3 < 6.
(iii) x = -1 is a solution of x2 – x – 2 = 0.
(iv) 4 + 4 = 10.
(v) Where do you live?
(vi) Go to your class.
Here, the sentences (i) to (iv) are propositions but (v) and (vi) are not (as they are neither true nor false).
Propositions may be primitive or compound. A proposition that cannot be broken into simpler propositions is known as a primitive proposition. The above propositions, (i) to (iv), are all primitive propositions. The proposition ‘Boats sail on the rivers and ships sail on the seas’ is a compound proposition containing the sub-propositions ‘Boats sail on the rivers’ and ‘ships sail on the seas’. Here, the word ‘and’ has been used as a connective. Some of the connectives which are frequently used in logical analysis and in mathematics are given below.
|if….then||⇒ or →||conditional or implication|
|if and only if (iff)||⟺ or ⟷||biconditional or equivalence|
A few examples of conjunctions (compounds propositions with ‘and’) are:
- David is sickly and she is tall.
- Andrew is in class ten and ten is a natural number.
- Sophia is a good girl and Amelia is a teacher.
- 2x + 7 = 15 and x + 4 < 9.
Here are some examples of disjunctions (compounds propositions with ‘or’):
- Arnold is a sportsman or he is tall.
- Emma is in her room or she is reading.
- Olivia is beautiful or two is an even prime.
- x – 3 > 4 or 2y + 5 < 3.
Truth and Falsity of Statements:
Consider the following statements:
- 3 + 2 < 7.
- The sum moves around the earth.
- Two and two make four.
- 4 + (6 ÷ 2) x 2 = 12.
Clearly, statements (1) and (3) are true whereas those given by (2) and (4) are false. It is to be noted that in the language of mathematics ‘true means universally true without exception’. Thus, the statement ‘Virat Kholi is the best batsman in India’ cannot be accepted as a true statement as there may be difference in opinion regarding this.
In the above examples, we say that the truth value of each of the statements given by (1) and (3) is true (T), and the truth value of each of the statements given by (2) and (4) is false (F).
In logical analysis, we are basically concerned with the truth and falsity of sentences. The truth value of a compound proposition is completely determined by the truth values of its sub-propositions (components) together with the way in which they are connected to form the compound proposition. Obviously, then, the compound statement p ∧ q is true only when each of its component statements p and q is true. This follows directly from our concept of operations with sets as A ∩ B implies the set with those elements which are contained in both A and B.
The connective ‘or’ can be used either in an exclusive sense or in an inclusive sense. When used in an exclusive sense, the word ‘or’ means one of the two and not both. For example, the compound proposition ‘A natural number is even or odd’ states that the number must be either even or odd. It cannot be both. Now consider the statement ‘Emma is in her room or she is reading’. Clearly, she could be both in her room or reading. Obviously, here, the connective ‘or’ has been used in an inclusive sense. In mathematics, however, the double usage of ‘or’ has been avoided. The mathematicians use it only in the inclusive sense. Thus, a disjunction (a compound proposition with connective ‘or’) is true if either of its components is true or both the components are true. Obviously, the disjunction p ∨ q is false only when both its components p and q are false. The concept of A ∪ B is helpful in this regard.
Truth tables are convenient ways of summarizing the truth values in logical analysis. A truth table expresses all possible pairs of the components along with the resulting truth values of the compound statements.
The truth tables of a conjunction and a disjunction are shown below.
Truth Table for p ∧ q (conjunction):
|p||q||p ∧ q|
Truth Table for p ∨ q (conjunction):
|p||q||p ∨ q|
The negation of a simple sentence is formed by using the connective ‘not’ with the main verb of the original statement. The negation of a statement p is denoted by ~ p. Thus, the negation of x + 2 = 5 is x + 2 ≠ 5. The negation of the statements ‘x + 1 > 4’ and ‘Simran is in class VI’ are and ‘Sneha is not in class VI’ respectively. It is important to remember in this case that the words which we think as opposite in our daily usage may not indicate logical negation. Thus, the word ‘bad’ cannot be used logically as the negation of ‘good’. Logical negations, are formed by preceding the word with ‘not’. Different symbols like p’, p̄, ~ p and ~ p are used to denote the negation of the statement p. The truth table for p and ~ p is shown below. It is wise to note that the negation of the phrase ‘for all’ is the phrase ‘there exists’ i.e., ∃ is the negation of ∀.
Truth Table for p and ~ p:
Example 1: If p and q are two statements then construct the truth table for ~ p ⇒ ~ q.
|p||q||~ p||~ q||~ p ⇒ ~ q|
Example 2: Construct the truth table for each of the following compound statements:
(i) ~ p ⇒ (p ∧ q)
|p||q||~ p||~ q||~ p ⇒ (p ∧ q)|
(ii) (p ∧ q) ⇒ ~ p
|p||q||p ∧ q||~ p||(p ∧ q) ⇒ ~ p|
(iii) (p ⇒ q) ⟺ (~ q ⟺ ~ p)
|p||q||~ p||~ q||p ⇒ q||~ q ⟺ ~ p||c1 ⟺ c2|
(iv) (p ⇒ q) ⇒ r
|p||q||r||p ⇒ q||(p ⇒ q) ⇒ r|
(v) (p ∧ q) ⟺ r
|p||q||r||p ∧ q||(p ∧ q) ⟺ r|