Unit - 1
Sets and Propositions
The Inclusion-Exclusion principle can be stated as below-
Let A and B any two finite sets, then-
Meaning- Here if we have to find the number 
of elements in the union of A and B.
So, then we add n(A) and n(B) which means we are including these two.
And then we exclude 
.
Note- For three sets-
If we have three finite sets A, B and C then-
Example: Find the number of students at a college choosing at least one of the subjects from mathematics, physics and statistics.
The data is given as-
65 study maths, 45 study physics, 42 study statistics
20 study maths and physics, 25 study maths and statistics, 15 study physics and statistics and 8 study all the three subjects.
Sol.
Here we need to find 
Now by using Inclusion-Exclusion principle-
Which gives-
Therefore, we find that 100 students study at least one of the three subjects.
Key takeaways-
Mathematical induction is a mathematical technique is used to prove a statement, a theorem or a formula is true for every natural number.
The technique has two steps to prove any statement-
1. Base step (it proves that a statement is true for the initial value)
2. Inductive step (it proves that is the statement is true for n’th iteration then it is also true for 
iteration.
Example-1: 
Sol. here for n = 1, 1 = 1²
Now let us assume that the statement is true for n = k
Hence, we assume that 
is true.
Now we need to prove that
So that 
which satisfies the second step.
Hence-
Example-2: Prove 1+2+...+n=n(n+1)/2 using a proof by induction
Sol.
Let n=1: 1 = 1(1+1)/2 = 1(2)/2 = 1 is true,
Step-1: Assume n=k holds: 1+2+...+k=k(k+1)/2
Show n=k+1 holds: 1+2+...+k+(k+1) =(k+1) ((k+1) +1)/2
Substitute k with k+1 in the formula to get these lines. Notice that I write out what I want to prove.
Step-2: Now start with the left side of the equation
1+2+...+(k+1) =1+2+...+k+(k+1)
=k(k+1)/2 + (k+1)
=(k(k+1) + 2(k+1))/2 by 2/2=1 and distribution of division over addition
=(k+2) (k+1)/2 by distribution of multiplication over addition
=(k+1) (k+2)/2 by commutativity of multiplication.
Example-3: Prove the following by using the principle of mathematical induction for all n ∈ N-
Sol. Here, n = 1, 
, which is true
Step-1: Assume n = k holds-
Now show n = k + 1 also holds-
Consider-
Which is also true for n = k + 1.
Hence proved.
Strong inductions-
It is another form of mathematical induction. By using this we can prove that a propositional function, P(n) is true for all positive integers n.
Working steps-
1. Base step- this proves that the initial proposition P (1) is true.
2. it proves that the conditional statement [P (1) ∧P (2) ∧P (3) ∧⋯∧P(k)] →P(k+1) is true for positive integers k.
Key takeaways-
Mathematical induction is a mathematical technique is used to prove a statement, a theorem or a formula is true for every natural number.
Statement-
When a declarative sentence which is true or false but not both is called statement.
The truth values “true” and “false” of a statement are denoted by T ad F respectively. We can denote them by 0 and 1 as well.
Examples of statements are-
1. 2 + 11 = 12
2. Jaipur is in India
Truth table-
The table showing the truth values of a statement formula is called ‘truth table’.
The truth table for a given statement form displays the truth values that correspond to all possible combinations of truth values for its component statement variables.
Laws of formal-
1. Law of contradiction- According to the law of contradiction the same predicate cannot be both affirmed and denied precisely of the same subject
For every preposition p is not the same that p is both true and false.
2. Law of excluded middle- If p is a statement, then either p is true or p is false and there cannot be middle ground.
Connectives-
Statements in mathematical logic are combinations of simpler statements joined by words and phrases like ‘and’. ‘or’, ‘if and only if’, etc. These words and phrases are called logical connectives.
Disjunction-
Definition: The disjunction of two propositions p and q is the compound statement 10 Elementary Logic p or q, denoted by p ∨ q.
For example, ‘Aman has a house or Amit has a house’ Is the disjunction of p and q, where-
p: Aman has a house, and
q: Amit has a house.
Example: Obtain the truth value of the disjunction of ‘The earth is flat’. and ‘3 + 5 = 2’.
Solution: Let p denote ‘The earth is flat,’ and q denote ‘3 + 5 = 2’. Then we know that the truth values of both p and q are F. Therefore, the truth value of p ∨ q is F.
Example-Let p: 5 + 2 = 7, q: 9 + 2 = 10 then p ∨q: 5 + 2 = 7 or 9 + 2 = 10
Truth table for disjunction-
Exclusive disjunction-
The exclusive disjunction of two propositions p and q is the statement ‘Either p is true or q is true, but both are not true. Either p is true or q is true, but both are not true’. We denote this by p ⊕q.
Conjunction-
Definition: We call the compound statement ‘p and q’ the conjunction of the
Statements p and q. We denote this by p ∧q.
Example- ‘3 + 1 ≠ 7 ∧ 2 > 0’ is the conjunction of ‘3 + 1 ≠ 7’ and ‘2 > 0’.
Example-
Obtain the truth value of the conjunction of ‘2 ÷5 = 1’ and ‘Ramesh is in Jaipur’.
Solution: Let p: 2 ÷5 = 1, and
q: Ramesh is in Jaipur.
Then the truth value of p is F. Therefore, from Table 3 you will find that the truth
Value of p ∧ q is F.
Negation-
The negation of a proposition p is ‘not p’, denoted by ~p.
Example-
if p is ‘Smriti is at the station.’, then ~ p is ‘Smriti is not at the station’.
Similarly, if p is ‘No person can live without food.’, ~ p is ‘At least one person can live without food.’
Conditional connectives-
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.
Truth table for implication-
Definition for converse-
The converse of p → q is q → p. In this case we also say ‘p is necessary for q’, or ‘p if q’ when we combine an implication and its converse, then-
Let p and q be two propositions. The compound statements
(p→ q) ∧ (q → p) is the bi-conditional of p and q. We denote it by p ↔ q, and
(Read) as ‘p if and only q’.
We use ‘if and only ‘if’ as iff
We also say that ‘p implies and is implied by q’. or ‘p is necessary and sufficient
forq’.
Example- Pradeep will get good marks if and only if he studies regularly means that Pradeep will get good marks if he studies regularly and Pradeep studies regularly if he gets good marks.
Truth table for two-way implication-
Proposition-
A proposition (or statement) is a declarative statement which is true or false, but not both.
Example-
(i) Ice floats in water.
(ii) China is in Europe
(iii) 2 + 2 = 4
(iv) 2 + 2 = 5
Compound proposition-
Many propositions are composite, that is, composed of sub-propositions and various connectives discussed
Subsequently such composite propositions are called compound Propositions. A proposition is said to be primitive
if it cannot be broken down into simpler propositions, that is, if it is not composite.
Following two propositions are composite:
“Roses are red and violets are blue.” and “John is smart or he studies every night.”
Key takeaways
Basic logical operations-
1. Conjunction- p ⋀ q
Any two propositions can be combined by the word “and” to form a compound proposition called the conjunction of the original propositions. Symbolically,
p∧q
Read “p and q,” denotes the conjunction of p and q. Since p ∧q is a proposition it has a truth value, and this truth
Value depends only on the truth values of p and q.
Note- If p and q are true, then p ∧q is true; otherwise, p ∧q is false.
2. Disjunction, p ∨q
Any two propositions can be combined by the word “or” to form a compound proposition called the disjunction of the original propositions. Symbolically,
p∨q
Read “p or q,” denotes the disjunction of p and q. The truth value of p ∨q depends only on the truth values of p
And q as follows-
If p and q are false, then p ∨q is false; otherwise, p ∨q is true
Negation-
Given any proposition p, another proposition, called the negation of p, can be formed by writing “It is not true that . . .” or “It is false that . . .” before p or, if possible, by inserting in p the word “not.” Symbolically, the negation of p, read “not p,” is denoted by
￢p
The truth value of ￢p depends on the truth value of p as follows-
If p is true, then ￢p is false; and if p is false, then ￢p is true
Basic logical operations-
1. Conjunction- p ⋀ q
Any two propositions can be combined by the word “and” to form a compound proposition called the conjunction of the original propositions. Symbolically,
p∧q
Read “p and q,” denotes the conjunction of p and q. Since p ∧q is a proposition it has a truth value, and this truth
Value depends only on the truth values of p and q.
Note- If p and q are true, then p ∧q is true; otherwise, p ∧q is false.
2. Disjunction, p ∨q
Any two propositions can be combined by the word “or” to form a compound proposition called the disjunction of the original propositions. Symbolically,
p∨q
Read “p or q,” denotes the disjunction of p and q. The truth value of p ∨q depends only on the truth values of p
And q as follows-
If p and q are false, then p ∨q is false; otherwise, p ∨q is true
Negation-
Given any proposition p, another proposition, called the negation of p, can be formed by writing “It is not true that . . .” or “It is false that . . .” before p or, if possible, by inserting in p the word “not.” Symbolically, the negation of p, read “not p,” is denoted by
￢p
The truth value of ￢p depends on the truth value of p as follows-
If p is true, then ￢p is false; and if p is false, then ￢p is true
Key takeaways-
Conditional and bi-conditional statement-
The statements are of the form “if p then q”. such statements are called conditional statement and these are denoted by-
We read it as p implies q.
Example: If Jaipur is in Rajasthan, then 2 + 2 = 4
Example: Let p: She is a post graduate
q: She is a professor then,
Bi-conditional statement-
Another statement is of the form “p if and only if q”, such statement is called bi-conditional statement and it is denoted by-
The truth value for conditional and bi-conditional value are given in the following tables-
Example: Agra is in India, if and only if 3 + 3 = 6
Key takeaways-
We read it as p implies q.
2. Another statement is of the form “p if and only if q”, such statement is called bi-conditional statement and it is denoted by-
Logical equivalences-
Two propositions P (p, q, . . .) and Q (p, q, . . .) are said to be logically equivalent, or simply equivalent and denoted by
P (p, q, . . .) ≡ Q (p, q, . . .)
Note- the prepositions are logically equivalent.
Prepositions and truth tables-
Suppose P (p, q, . . .) denote an expression constructed from logical variables p, q, . . ., which take on the value
T or F which are true and false,
and the logical connectives ∧, ∨, and ￢and others. Such an expression P (p, q, . . .) will be called a proposition.
The main property of a proposition P (p, q, . . .) is that its truth value depends exclusively upon the truth values of its variables, that is, the truth value of a proposition is known once the truth value of each of its variables
is known. A simple concise way to show this relationship is through a truth table
Laws of prepositions-
The prepositions satisfy the following rules
Tautologies-
A tautology is a formula which is always true for every value of its propositional variables-
Contradiction-
A Contradiction is a formula which is always false for every value of its propositional variables.
Contingency-
A Contingency is a formula which has both some true and some false values for every value of its propositional variables.
Key takeaways-
P (p, q, . . .) ≡ Q (p, q, . . .)
2. The prepositions are logically equivalent.
3. A tautology is a formula which is always true for every value of its propositional variables
As we know that, we read in grammar predicate is the word in a sentence which expresses what is said of the object. It is a part of a declarative sentence describing the properties of an object or relation among objects.
In logic it has a wide role.
A predicate is an expression of one or more variables defined on some specific domain. A predicate with variables can be made a proposition by either assigning a value to the variable or by quantifying the variable.
The following are some examples of predicates −
Quantifiers provide a notation that allows us to quantify (count) how many objects in the universe of discourse satisfy the given predicate.
• Universal Quantifier ∀ - For all elements
• Existential Quantifier ∃ - There exists an element De Morgan’s Law for Quantifiers
• ¬∀xP(x) ≡∃x¬P(x)
• ¬∃xP(x) ≡∀x¬P(x)
Let P(x) be the statement “x spends more than five hours every weekday in class,” where the domain for x consists of all students. Express each of these quantifications in English.
a) ∃xP(x) There exists a student who spends more than five hours every weekday in class.
b) ∀xP(x) Every student spends more than five hours every weekday in class.
c) ∃x¬P(x) There exists a student who does not spend more than five hours every weekday in class.
d) ∀x¬P(x) No student spends more than five hours every weekday in class.
The symbols 
are called quantifiers, here 
is universal quantifier and 
is existential quantifier.
We read them as-
Universal quantifiers-
Let us consider the following proposition-
‘Every rational number is a real number’ can be re-written as. For every x, if x is a rational and number, then x is a real number. The phrase ‘for every x’ is called a universal quantifier.
Or
Let p(x) is a propositional function defined on a set A, consider the expression
Here the symbol which we read “for all” or “for every” is called universal quantifier.
The above statement can be written as-
That is, that the truth set of p(x) is the entire set A.
The expression p(x) is a condition itself and it has no truth value
It is symbolically denoted by 
.
If P (x) denotes a predicate, then the universal quantification for P (x), is the statement.
“For all values of x, P (x) is true”
Example: Let P(x): x + 6 < 10, then for all x
P (x) is a false statement because P (5) is not true.
Example: The preposition (
is false since {n | n + 2 > 8} = {7, 8, …...} ≠ N
Existential quantifiers:
The existential quantification for a predicate is the statement “There exists a value of x” for which P (x). The symbol 
, is used to denote the logical quantifier ‘there exists’ the phrases ‘There exists an x’, ‘There is a x’, for some x’ and ‘for at least one x’ have the same meaning. The existential quantifier for P (x) is denoted by 
x P (x).
Or
Let p(x) be a propositional function defined on a set A. consider an expression-
The symbol 
reads as there exists is called existential quantifier.
Key takeaways-
“For all values of x, P (x) is true”
4. Let p(x) be a propositional function defined on a set A. consider an expression-
The symbol 
reads as there exists is called existential quantifier.
The rules ‘Modus Ponens’ and ‘Hypothetical Syllogism’ are known as the fundamental rules of inference.
Modus ponens and modus tollens-
An argument form consisting of two premises and a conclusion is called a syllogism. The first and second premises are called the major premise and minor premise, respectively.
The most famous form of syllogism in logic is called modus ponens. It has the following form:
If p then q.
p
∴q
Example:
If the sum of the digits 469437 is divisible by 3
Then 469437 is divisible by 3.
Another valid argument form called modus tollens.
Modus tollens means- method of denying.
It has the following form-
If p then q.
∼q
∴∼p
For example-
If Rahim is tall, then Rahim is thick.
Rahim is not thick.
∴Rahim is not tall.
The rules of inference- (Modus ponens and modus tollens)
The theory of inference is a form of argument that is valid.
Modus ponens and modus tollens are both rules of inference.
The following results gives the rules of inference-
1. Modus ponens (Law of detachment)-
Let us consider the following argument-
If Ravi can fire, he will hit the target
Ravi can fire,
Therefore, he will hit the target.
In order to study the form of the argument, suppose p be the proposition ‘Ravi can fire’ and q be the proposition ‘Ravi will hit the target’.
Then the premises are p→q and p.
The conclusion is q.
Hence the form of argument-
To check the validity of this argument we will construct a truth table as follows-
By looking the second column (the conclusion) and the fourth column (the premises).
Whenever the premises are true in first row the conclusion is true.
Hence the argument is valid.
This is the form of valid argument and this law is called law of detachment because the conclusion q is detached from a premise.
We also call it as the law of direct inference.
2. Modus tollens (Law of detachment)-
Let us consider the following argument-
If Ravi can fire, he will hit the target.
Ravi will not hit the target.
Therefore, Ravi cannot fire.
The argument is of the form-
Key takeaways-
The most famous form of syllogism in logic is called modus ponens. It has the following form:
If p then q.
p
∴q
Direct proof:
This method is totally based on modus ponens.
We assume that P is true, and from the available information the conclusion q is shown to be true by valid reference.
We column (construct a chain of statements P, 
. where P is either a hypothesis of the theorem or an axiom and each of the implications
is either an axiom or is implied by the implication preceding it.
Example: The product of two odd integers is odd.
Sol.
Let consider there are two odd integers x and y, so our hypothesis is-
P: x and y are odd
We want to reach the conclusion-
q: xy is odd
let us first prove that
here x is odd, x = 2m + 1 for some integer m.
And y = 2n + 1 for some integers n.
Then-
Therefore, xy is odd
So, it is shown that-
Example: If x is a number such that 
then show that x = 3, x = 4 by direct proof.
Sol.
can be written as-
Hence 
Method of contraposition-
This is a very useful and powerful method in mathematics.
In the first method, we use the fact that the proposition 
is logically equivalent to its contrapositive 
Which means-
Example: For any integer n > 2, prove that n Prime 
n odd.
Sol.
Let
p: n Prime
q: n odd
then
~ q: n even
~ p: n not primes
If n is an even number greater than 2, then n = 2m for some integer m > 1. Thus, n is divisible by 2 and n 
therefore n cannot be prime thus we have ~q 
Which means if n is any number bigger than 2, then n cannot be prime.
Method of contradiction
The method of contradiction can be defined as follows-
In this method, to prove q is true, we start by assuming that q is false. Then, by a logical argument we arrive at a situation where a statement is true as well as false, which means
We reach a contradiction r 
for some statement that is always false. This can only happen when ~q false also. Therefore, q must be true.
This method is also known as reduction ad absurdum, which is a Latin phrase, because it depends on reducing a given assumption to an absurdity.
Example: Prove that 
is an irrational number.
Sol.
Let us suppose 
is a rational number, then-
Where p and q have no common factor.
Now square on both sides-
Hence p and q have common factor of 2, which is a contradiction to the statement that a and b have no common factors.
Hence our assumption that 
is rational leads to a contradiction. Thus 
is irrational.
References:
