Table of Contents
PREDICATE AND QUANTIFIERS
A propositional function, or a predicate, in a variable x is a sentence p(x) involving x that becomes a proposition when we give x a definite value from the set of values it can take. We usually denote such functions by p(x), q(x), etc.
So, if p(x) is ‘x > 5’, then p(x) is not a proposition. But when we give x particular values, say x = 6 or x = 0, then we get propositions. Here, p(6) is a true proposition and p(0) is a false proposition.
Note: that a predicate is usually not a proposition. But, of course, every proposition is a prepositional function in the same way that every real number is a real-valued function, namely, the constant function.
Now, can all sentences be written in symbolic from by using only the logical connectives? What about sentences like ‘x is prime and x + 1 is prime for some x.’? How would you symbolize the phrase ‘for some x’, which we can rephrase as ‘there exists an x’? You must have come across this term often while studying mathematics. We use the symbol ‘∃’ to denote this quantifier, ‘there exists’. The way we use it is, for instance, to rewrite ‘There is at least one child in the class.’ as‘(∃ x in U)p(x)’, where p(x) is the sentence ‘x is in the class.’ and U is the set of all children.
Now suppose we take the negative of the proposition we have just stated. Wouldn’t it be ‘There is no child in the class.’? We could symbolize this as ‘for all x in U, q(x)’ where x ranges over all children and q(x) denotes the sentence ‘x is not in the class.’, i.e., q(x) ≡ ~ p(x).
We have a mathematical symbol for the quantifier ‘for all’, which is ‘∀’. So the proposition above can be written as ‘(∀ x ∈ U)q(x)’, or ‘q(x), ∀ x ∈ U’.
An example of the use of the existential quantifier is the true statement. (∃ x ∈ R) (x + 1 > 0), which is read as ‘There exists an x in R for which x + 1 > 0.’.
Another example is the false statement\left( \exists x\in N \right)\left( x-\frac{1}{2}=0 \right), which is read as ‘There exists an x in N for which x-\frac{1}{2}=0’.
| Example 01 |
Q. Let p(x) denotes the statement “x > 3”. Find the truth values of (i) p(2) and (ii) p(4)
Solution:
(i) p(2) is “2 > 3” which is not true. Therefore, p(2) is a proposition, whose truth value “False” (or “0”).
(ii) p(4) is “4 > 3”, which is true. Therefore the proposition p(4), has truth value “True” (or “1”).
N-place Predicate
(i) Consider the statements:
Rayan is a Mathematician
Shagnik is a Mathematician
Here the part “is a Mathematician” is the predicate. This is the 1-place predicate.
(ii) Consider the statements:
Subhadip is taller than Dhananjay.
Mexico is to the south of the USA.
The predicate “is taller than” and is to the south of” are 2-place predicates since the names of two objects are needed to complete a statement involving these predicates.
(iii) Consider the statement:
Pritam sits between Sohan and Tanoy.
The word “sits between” is a 3-place predicate.
In general, an N-place predicate requires n names of objects, which are to be inserted in fixed positions in order to obtain a statement.
LOGICAL QUANTIFICATION OF PROPOSITIONS
When all the variables in the propositional function are assigned values the resulting statement will have its truth value.
For example consider p\left( x \right):{{x}^{2}}\ge 0. If x is an integer, then the propositional function is true. So here we are assigning integer values to x in the propositional functionp\left( x \right).
Now we study a way to change propositional functions into propositions, which is called quantification, we study two types of quantification namely universal quantification and existential quantification.
Universe of Discourse or The Domain
The class of variables which are quantified stand for only those objects that are members of a particular set are called the universe of discourse or the domain.
Universal Quantification
The universal quantification of a given propositional function p\left( x \right)is the proposition given by “p\left( x \right)is true for all values of x in the universe of discourse”. We may use the notationp\left( x \right),\,\,or\,\forall x,p\left( x \right)\,\,or\,\left( x \right)p\left( x \right). We may read it as “for all x,p\left( x \right)” or “for every x,p\left( x \right)”.
| Example 02 |
(i) Express the following statement in the form of the proposition by using universal quantification. “Every student MCA class studied Discrete Mathematics”. (Use symbols)
What is the universe of discourse for this statement?
(ii) Symbolize the statement “x is taller than y” using universal quantifiers.
Solution:
(i) Let p(x): x has studied Discrete Mathematics, q(x): x is a student of MCA.
Now the given statement can be written as “p(x) for all x where x is a student in MCA class” or “p(x) for all x in q(x)”, or q\left( x \right)\to p\left( x \right)for all x or \forall x\left( q\left( x \right)\to p\left( x \right) \right).
The universe of discourse for this statement was “the set of all students of MCA class”.
(ii) Let g(x, y): x is taller than y
We can state as: For any x and for any y, if x is taller than y, then y is not taller than x.
Therefore using quantifier, we can write as \left( x \right)\left( y \right)\left( g\left( x,y \right)\to \sim g\left( x,y \right) \right)
Existential Quantification
The existential quantification of a propositional function p\left( x \right)is the proposition “there exists an element x in the universe of discourse such that p\left( x \right)is true”. We may use the notation ''\exists x\,p\left( x \right)''for existential quantification of p\left( x \right), we may read it as “there is an x such that p\left( x \right)” or “there exists at least one x such that p\left( x \right)” or “for some x,p\left( x \right)”.
| Example 03 |
Consider the following statements:
There exists a man.
Some men are clever.
Some real numbers are rational.
Solution:
Let us symbolize the expressions as:
M(x): x is a man, C(x): x is clever, R(x): x is real number, Q(x): x is a rational number.
Using existential quantifier, these can be written as:
\[\left( \exists x \right)\left( M\left( x \right) \right)\]
\[\left( \exists x \right)\left( M\left( x \right)\wedge C\left( x \right) \right)\]
\[\left( \exists x \right)\left( R\left( x \right)\wedge Q\left( x \right) \right)\]
Well-formed formula
A statement formula is an expression which is a string consisting of variables, parentheses and connective symbol is called well-formed formula (wff).
Rules of Well-formed formula
A well-formed formula can be generated by the following rules.
(i) A statement variable standing alone is wff.
(ii) If A is a wff then ~A is a wff.
(iii) If A and B are wff, then (A˄B), (A˅B), (A→B) and (A↔B) are wff.
(iv) A string of symbols containing the statement variables, connectives and parentheses is a wff if and only if it can be obtained by finitely many applications of the rules (i), (ii) and (iii).
Examples of some Well-formed formula
(i) \sim \left( P\wedge Q \right)
(ii) \sim \left( P\vee Q \right)
(iii) \left( P\to \left( P\vee Q \right) \right)
(iv) \left( P\to \left( Q\to P \right) \right)
(v) \left( \left( \left( P\to Q \right)\wedge \left( Q\to R \right) \right)\leftrightarrow \left( P\to R \right) \right)
Examples of some not Well-formed formula
(i) \sim P\wedge Q
(ii) \left( P\to Q \right)\to \left( \sim Q \right)
(iii) (P\to Q
(iv) \left( P\to Q \right)\to Q)
Propositional Logic |
Mathematical Induction |
