UNIT 1

*) Logic and Proofs: Logic is the Science of reasoning. It helps us to understand and reason
about different mathematical statements. With rules of logic, we would be able to think about
mathematical statements and finally we would be able to prove or disprove those mathematical
statements precisely.
The Purpose of logic is to construct a valid argument.
The rules of mathematical logic specify methods of reasoning mathematical statements. Greek
philosopher, Aristotle, was the pioneer of logical reasoning. Logical reasoning provides the
theoretical base for many areas of mathematics and consequently computer science. It has
many practical applications in computer science like design of computing machines, artificial
intelligence, definition of data structures for programming languages etc.
Major Categories
Mathematical logics can be broadly categorized into three categories.
 Propositional Logic − Propositional Logic is concerned with statements to which the
truth values, "true" and "false", can be assigned. The purpose is to analyse these
statements either individually or in a composite manner.
 Predicate Logic − Predicate Logic deals with predicates, which are propositions
containing variables. A predicate represents an expression of one or more variables.
 Theory of Inference − To deduce new statements from the statements whose truth that
we already know, Rules of Inference are used. Rules of Inference provide the templates
or guidelines for constructing valid arguments from the statements that we already have.

*) Propositional Logic:
Proposition is a declarative sentence. (a sentence that is declaring a fact or stating an argument)
which can be either true or false but cannot be both.
Examples: Delhi is the capital of India
1+1=2
Sun rises in the east
Sentences which are not propositions
How are you?
X+1=2
What time is it?
 Send us your resume before 11 pm
*) Compound Propositions
Compound Propositions are the made by combining one or more propositions using Logical
Connectives.
Exam: Statement 1: Jack is good in playing food ball
Statement 2: He is representing his College at National Levels
Compound Proposition: Jack is good in playing football and he is representing his College at
National Level.

*) Propositional Variables:
The variables that are used to represent propositions are called propositional variables.
Example: p = Jack is good in playing food ball
q = He is representing his College at National Levels
These variables are represented by small alphabets such as p, q, r, s..

*) Logical Connectives:
A Logical connective is symbol used to connect two or more propositions.
A Logical Connective is a symbol which is used to connect two or more propositional or
predicate logics in such a manner that resultant logic depends only on the input logics and the
meaning of the connective used.
Generally there are five connectives which are:
 Negation/ NOT (¬)
 OR (∨)
 AND (∧)
 Implication / if-then (→) (Condition)
 Double implication If and only if (⇔). (Bi-condition)

Truth Table for Logical Connectives:

Negation/ NOT (¬)

Example: p - Today is Friday – This statement is represented by the variable p

¬p - Today is not Friday - The negation of p is represented by ¬p

OR (∨) (Disjunction)

Example: p – Today is Friday

q – It is raining today
P∨q – Today is Friday or it is raining today.
In this case, the conclusion becomes true if any one of the statement is true and conclusion
becomes false if both the statements are false.
AND (∧) (Conjunction)

Example: p – Today is Friday

q – It is raining today
P∧q – Today is Friday and it is raining today.
In this case, the conclusion becomes true if any both the statements are true and
conclusion becomes false if any of the statements are false.
Implication / if-then (→) (Condition)

Example: p – Today is Friday

q – I will go to City
p→q – if Today is Friday then I will go to City.
In this case, the conclusion becomes false if the first statement is true and second
statement is false. The conclusion becomes true in all other cases.
x y x&y x|y x^y
0 0 0 0 0
0 1 0 1 1
1 0 0 1 1
1 1 1 1 0

Double implication If and only if (↔). (Bi-condition)

Example: p – I will go to City

q – Today is Friday
p↔q –I will go to City if and only if today is Friday.
In this case, the conclusion becomes True if the both the statements are either true or
false. The conclusion becomes false if any one of the statement is false.

Truth Table for Bitwise AND, OR and XOR operators

*) Propositional Logic
Propositional Logic is the area of logic that studies the ways of joining and /or modifying
propositions to form more complicated propositions and it also studies the logical relationships
and properties derived from these combined or altered propositions.
*) Applications of Propositional Logic
1) Translating of English Sentences
Propositional Logic helps to remove any ambiguity in English sentences
English sentences are translated into compound propositions using propositional variables and
logical connectives
These compound propositions are analyzed to determine their truth value
Example:
"You can access the Internet from campus only if you are a computer science major or you are
not a freshman."
a = "You can access the Internet from campus,"
c = "You are a computer science major,"
f = "You are a freshman,"
The above English sentence can be translated in propositional logic as
a → (c ∨ ¬f)
2) Boolean Searches
Most search engines (e.g. google) uses propositional logic to find web pages on some subject
These searches are called Boolean Searches as logical connectives (AND, OR, NOT) are used
to match keywords in web pages
Example:
You type keywords - British Universities - in google search bar to search for universities in
Britain.
Google uses Britain AND Universities to look for pages containing the both keywords Britain
and Universities.
3) System Specifications
When developing/manufacturing a system (Software or Hardware), the
developers/manufacturers have to meet certain needs and specifications, which are usually
stated in English. But as English sentences can be ambiguous, developers/engineers translate
these system specifications into logical expressions to state specifications rigorously and
unambiguously.
Example: Let a, b, c, and d represent the sentences “The computer is within the local
network.“, “The computer has a valid login id.“, “The computer is under the use of
administrator.“, and “Internet is accessible to the computer.” So the complex sentence, “If the
computer is within the local network or it is not within the local network but has a valid login
id or it is under the use of administrator, then the Internet is accessible to the computer.” can
be expressed as (a ∨ (¬a ∧ b) ∨ c) -> d.
4) Logical Puzzles
Puzzles that are solved using reasoning and logic are called logical puzzles. They can be used
for brain exercises, recreational purposes, and for testing a person’s reasoning capabilities.
Solving such puzzles is generally tricky, but it can be done easily using propositional logic.
Some of the famous logic puzzles are the muddy children puzzle, Smullyan’s puzzles about
knights and knaves, etc.
Example:
Problem Statement: There is an island that has two kinds of inhabitants, knights, who always
tell the truth, and their opposites, knaves, who always lie. You encounter two people A and B.
Determine what are A and B if A says “B is a knave” and B says “Both of us are of same
types”?
Solution: Let p and q be the statements that A is a knight and B is a knight, respectively, so ¬p
and ¬q are the statements that A is a knave and B is a knave, respectively. Let’s assume A is a
knight, i.e., p is true. So A is telling the truth, which means ¬q is true. Now as B is a knave
whatever it is saying is a lie, i.e., (p ∧ q) ∨ (¬p ∧ ¬q) is false, which simply means if either of
them is a knave then the other one is a knight or vice-versa. Now, as per the assumption, this
statement is true. So we can conclude that A is a knight and B is a knave.
5) Boolean Searches
Another important application of propositional logic is Boolean searches. These searches use
techniques from propositional logic. Logical connectives are used extensively in searches of
large collections of information, such as indexes of Web Pages. In Boolean searches, the
connective AND is used to find records that contain both of the two terms, the connective OR
is used to find records that have either one or both of the terms, and the connective NOT, also
written as AND NOT, is used when we need to exclude a particular search term.
6) Logic/Computer Circuits
Logic gates or circuits are electronic devices that implement Boolean functions, i.e. it does a
logic operation on one or more bits of input and gives a bit as an output. They are the basic
building blocks of any digital system. The relationship between the input and output is based
on a certain propositional logic.
Example: Logic gates are named as AND gate, OR gate, NOT gate, etc. based on the names
of logical connectives AND, OR, NOT, etc. The output truth values for the given input bits for
these gates are the same as that those returned by the logical connectives.
*) Types of propositions based on Truth values
There are three types of propositions when classified according to their truth values
1) Tautology – A proposition which is always true, is called a tautology.
2) Contradiction – A proposition which is always false, is called a contradiction.
3) Contingency – A proposition that is neither a tautology nor a contradiction is called a
contingency.

*) Tautology
A Tautology is a formula which is always true for every value of its propositional variables.
Example − Prove [(A→B)∧A]→B[(A→B)∧A]→B is a tautology
The truth table is as follows

A B A→B (A → B) ∧ A [( A → B ) ∧ A] → B

True True True True True

True False False False True

False True True False True

False False True False True

*) Contradictions
A Contradiction is a formula which is always false for every value of its propositional variables.
Example − Prove (A∨B)∧[(¬A)∧(¬B)](A∨B)∧[(¬A)∧(¬B)] is a contradiction
The truth table is as follows

A B A∨B ¬A ¬B (¬ A) ∧ ( ¬ B) (A ∨ B) ∧ [( ¬ A) ∧ (¬ B)]

True True True False False False False

True False True False True False False

False True True True False False False

False False False True True True False

As we can see every value of (A∨B)∧[(¬A)∧(¬B)](A∨B)∧[(¬A)∧(¬B)] is “False”, it is a
contradiction.

*) Contingency
A Contingency is a formula which has both some true and some false values for every value of
its propositional variables.

Example − Prove (A∨B)∧(¬A)(A∨B)∧(¬A) a contingency

The truth table is as follows

A B A∨B ¬A (A ∨ B) ∧ (¬ A)

True True True False False

True False True False False

False True True True True

False False False True False

*) Propositional Equivalences
Compound Propositions that have the same truth values in all possible cases are called logically
equivalent.

Two statements X and Y are logically equivalent if any of the following two conditions hold
 The truth tables of each statement have the same truth values.
 The bi-conditional statement X⇔Y is a tautology.

Example − Prove ¬(A∨B)and[(¬A)∧(¬B are Logically equivalent

Testing by 1st method (Matching truth table)

A B A∨B ¬ (A ∨ B) ¬A ¬B [(¬ A) ∧ (¬ B)]

True True True False False False False

True False True False False True False

False True True False True False False

False False False True True True True

Here, we can see the truth values of ¬(A∨B)and[(¬A)∧(¬B)]¬(A∨B)and[(¬A)∧(¬B)] are same,

hence the statements are equivalent.

Testing by 2nd method (Bi-conditionality)

A B ¬ (A ∨ B ) [(¬ A) ∧ (¬ B)] [¬ (A ∨ B)] ⇔ [(¬ A ) ∧ (¬ B)]

True True False False True

True False False False True

False True False False True

False False True True True

As [¬(A∨B)]⇔[(¬A)∧(¬B)] [¬(A∨B)]⇔[(¬A)∧(¬B)] is a tautology, the statements are

equivalent.
Example: Show that ¬ (p ∨ (¬p ∧ q)) and ¬p ∧ ¬q are logically equivalent by developing a
series of logical equivalences.
¬ (p ∨ (¬p ∧ q)) ≡ ¬ p ∧ ¬ (¬p ∧ q)) By the Second De Morgan Law
≡ ¬ p ∧ [¬ (¬p) ∨ ¬q)] By the First De Morgan Law
≡ ¬ p ∧ (p∨ ¬q) By the Double negation Law
≡ (¬ p ∧ p) ∨ (¬ p ∧ q) By the Second Distributive Law
≡ F ∨ (¬ p ∧ q) because (¬ p ∧ p) is False
≡ (¬ p ∧ q) By the Identity law for False
*) PREDICATE LOGIC
Propositional logic cannot adequately express the meaning of statements in mathematics and
in natural language, therefore we need more powerful type of logic called Predicate Logic.

Predicate Logic − Predicate Logic deals with predicates, which are propositions containing
variables. A predicate represents an expression of one or more variables.

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 −

 Let E(x, y) denote "x = y"

 Let X(a, b, c) denote "a + b + c = 10"

Example: Let R(x,y,z) denote the statement “x+y=z”. What are the truth values of the
propositions R (1,2,3) and R(0,0,1)?
Ans. The proposition R(1,2,3) is obtained by setting x=1,y=2,z=3 in the statement R(x,y,z). we
see that R(1,2,3) is the statement “1+2=3”, which is true. Also note that R(0,0,1), which is the
statement “0+0=1”, is false.

*) Universe of Discourse or Domain: The relevant set of entities that are being dealt with by
quantifiers are known as Domain or Universe of Discourse.
Quantification: The Process of converting the Predicate into a Proposition. Predicate 
Proposition is Known as Quantification.
1) We can assign value to variables to change a predicate to a proposition
2) We can use quantifiers to change a predicate to a proposition

*) Quantifiers: Quantifiers are words that refer to quantities such as ”some” or ”all” and
tell for how many elements a given predicate is true. The variable of predicates is quantified
by quantifiers. There are two types of quantifier in predicate logic − Universal Quantifier and
Existential Quantifier.
*) Universal Quantifier
Universal quantifier states that the statements within its scope are true for every value of the
specific variable. It is denoted by the symbol ∀.
∀xP(x) is read as for every value of x, P(x) is true.
An element for which P(x) is false is called a counterexample of ∀xP(x)

Example 1: "Man is mortal" can be transformed into the propositional form ∀xP(x) where P(x)
is the predicate which denotes x is mortal and the universe of discourse is all men.

Example 2: What is the truth value of ∀xP(x), where P(x) is the statement “x2 < 10” and the
domain consists of the positive integers not exceeding 4?

Here the Domain is {1,2,3,4}

For integer 1: P(x): “x2 < 10” 1<10 is true
For integer 2: P(x): “x2 < 10” 4<10 is true
For integer 3: P(x): “x2 < 10” 9<10 is true
For integer 4: P(x): “x2 < 10” 16<10 is false. Since P(x) is not true for all the values ∀xP(x) is
false.

*) Existential Quantifier
Existential quantifier states that the statements within its scope are true for some values of the
specific variable. It is denoted by the symbol ∃.
∃xP(x) is read as for some values of x, P(x) is true.

Example 1: "Some people are dishonest" can be transformed into the propositional form
∃xP(x) where P(x) is the predicate which denotes x is dishonest and the universe of discourse
is some people.

Example 2: What is the truth value of ∃xP(x) where P(x) is the statement “x2 >10” and the
universe of discourse consists of the positive integers not exceeding 4?
Here the Domain is {1,2,3,4}
For integer 1: P(x): “x2 > 10” 1>10 is false
For integer 2: P(x): “x2 > 10” 4>10 is false
For integer 3: P(x): “x2 > 10” 9>10 is false
For integer 4: P(x): “x2 > 10” 16>10 is True. Since P(x) is true for all at least one value of
P(x), ∃xP(x) is true.

Statement When true? When False?

∀xP(x) P(x) is true for every x There is an x for which P(x) is false
∃xP(x) There is an x for which P(x) is True P(x) is false for every x

*) Free and Bound variables

Consider a Predicate formula having a part in form of (∃ x) P(x) of (x)P(x), then such part is
called x-bound part of the formula. Any occurrence of x in x-bound part is termed as bound
occurrence and any occurrence of x which is not x-bound is termed as free occurrence. See the
examples below -

 (∃ x) (P(x) ∧ Q(x))
 (∃ x) P(x) ∧ Q(x)
In first example, scope of (∃ x) is (P(x) ∧ Q(x)) and all occurrences of x are bound occurrences.
Whereas in second example, scope of (∃ x) is P(x) and last occurrence of x in Q(x) is a free
occurrence.

*) Negating Quantified Expressions:

Negation Equivalent Statement When Negation is True When Negation is True

¬∃ x P(x) ∀x ¬P(x) For every x, P(x) is false There is an x for which
P(x) is true
¬ ∀x ∃ x ¬ P(x) There is an x for which For every x, P(x) is true
P(x) P(x) is false
*) Nested Quantifiers:

Two quantifiers are said to be nested if one is within the scope of the other.

1. ∀𝑥∀(𝑥, 𝑦) – it can be considered as ∀𝑥𝑃(𝑥) where P(x) is a propositional function that is

denoted by ∀𝑦𝑃(𝑥, 𝑦)
2. ∀𝑥∃(𝑥, 𝑦) - it can be considered as ∀𝑥𝑃(𝑥) where P(x) is a propositional function that is
denoted by ∃𝑦𝑃(𝑥, 𝑦)
3. ∃𝑥∀(𝑥, 𝑦) - it can be considered as ∀𝑥𝑃(𝑥) where P(x) is a propositional function that is
dented by ∀𝑦𝑃(𝑥, 𝑦)
4. ∃𝑥∃(𝑥, 𝑦) - it can be considered as ∀𝑥𝑃(𝑥) where P(x) is a propositional function that is
denoted by ∃𝑦𝑃(𝑥, 𝑦)

Order doesn’t matter for 1 and 4 but order matters for 2 and 3

Example 1: Let Q(x,y,z) be the statement “x+y=z”. What are the truth values of the statements
∀𝑥∀𝑦∃z Q(x,y,z) and ∃z∀𝑥∀𝑦 Q(x,y,z), where the domain of all variables consists of all real
numbers?

Ans. ∀𝑥∀𝑦∃z Q(x,y,z) - Domain is all real numbers

Suppose that x and y are assigned values, then there exists a real number z such that x+y=z

∃z∀𝑥∀𝑦 Q(x,y,z) - Domain is all real numbers

There is a real number z such that for all real numbers x and for all real numbers y it is true that
x+y =z is false, because there is no value of z that satisfies the equation x+y=z for all values of
x and y.

*) Theory inference:
Argument: An argument in propositional logic is a sequence of propositions.
All but the final proposition in the argument are called premises and the final proposition is
called the conclusion.
An argument is valid if the truth of all its premises implies that the conclusion is true.
Inference theory is concerned with the inferring of a conclusion from certain hypothesis or
basic assumptions called premises, by applying certain principles of reasoning called rules of
inferences.
When a conclusion is derived from a set of premises by using rules of inferences, the process
of such derivation is called a formal proof. Any conclusion which is arrived at, by following
the rules of inferences is called a valid conclusion and the argument is called a valid
argument.

An argument form in propositional logic is a sequence of compound propositions involving

propositional variables. An argument form is valid if no matter which particular propositions
are substituted for the propositional variables in its premises, the conclusion is true if the
premises are all true.

We have different methods to show that argument form is valid.

When A and B are two statement formulas then B is said to logically follow A, or B is a valid
conclusion of the premise A, then if AB is a tautology.
Extending, a conclusion C is said to follow from a set of premises P1, P2, P3,……..Pn, if P1 ^
P2 ^ P3 ^….Pn C is a tautology.

1) Truth table technique:

If a set of premises and a conclusion are given, it is possible to determine whether the
conclusion follows from the premises by constructing relevant truth tables as in the following
problems.

Example 1: H1: ¬ P; H2: P˅Q; C: Q

P Q ¬P P˅Q
T T F T
T F F T
F T T T
F F T F
Consider only the rows having truth values in both premises, if the corresponding value of
conclusion is true, then we can say that the conclusion follows the premises.
Here in example 1, Conclusion C follows the premises H1 and H2.

Example 2: H1: PQ; H2: Q; C: P

P Q PQ
T T T
T F F
F T T
F F T

H1 and H2 are true in the first and third rows, but C is not true in the third row, hence it is not
a valid conclusion.

Example Problems:

1) H1: PQ; H2: P; C: Q (Valid)

2) H1: PQ; H2: ¬ P; C: Q (Invalid)
3) H1: PQ; H2: ¬(P˄Q); C: ¬ P (Valid)
4) H1: ¬ P; H2 ⟷; C: : ¬(P˄Q) (Valid)
5) H1: PQ; H2: Q; C: P (Invalid)

The truth table technique becomes tedious if the premises contain a large number of variables.
Therefore, we have rules of inferences. The basic rules of inference are Rule P and Rule T.
Rule P: A Premise may be introduced at any step in the derivation.
Rule T: A formula may be introduced in the derivation, if S is tautologically implied by one or
more preceding formulas in the derivation.

Implications:
1) P, PQ ⟹ Q Modes Ponens
2) ¬ Q, PQ ⟹ ¬ P Modes Tollens
3) PQ, QR ⟹ PR Hypothetical Syllogism
4) ¬ P, P˅Q ⟹ Q Disjunctive Syllogism
5) P ⟹ P˅Q Addition
6) P˄Q ⟹ P Simplification
7) P, Q ⟹ P˄Q Conjunction
8) P˅Q, ¬P˅R⟹Q˅R Resolution

Example1: Show that the hypotheses “it is not sunny this afternoon and it is colder than
yesterday”, “we will go swimming only if it is sunny”, if do not go swimming, then we will go
a trip” and “if we go a trip, then we will be home by sunset” lead to the conclusion “ we will
be home by sunset”.

Let the Propositions and the corresponding variables be

1) it is sunny this afternoon - p
2) it is colder than yesterday - q
3) we will go swimming – r
4) we will go a trip - s
5) we will be home by sunset – t

Then the hypothesis becomes - ¬p˄q , rp, ¬rs, st and conclusion t

Step Reason
1) ¬p˄q Hypothesis
2) ¬p Simplification using (1)
3) rp Hypothesis
4) ¬r Modus tollens using (2) and (3)
5) ¬rs Hypothesis
6) s Modus ponens using (4) and (5)
7) st Hypothesis
8) t Modus ponens using (6) and (7)
Example 2: Show that the hypothesis “if you send me an email message, then I will finish
writing the program”, if you do not send me an e-mail message, then I will go to sleep early”,
and “if I go to sleep early, then I will wake up feeling refreshed” lead to the conclusion “if I
don’t finish writing the program, then I will wake up feeling refreshed”.

Let the Propositions and the corresponding variables be

1) you send me an email message – p
2) I will finish writing the program – q
3) I will go to sleep early – r
4) I will wake up feeling refreshed – s
Then the hypothesis becomes - pq, ¬pr, rs and the conclusion is ¬qs
Step Reason
1) pq Hypothesis
2) ¬q¬p Contrapositive of (1)
3) ¬pr Hypothesis
4) ¬qr Hypothetical Syllogism using (2) and (3)
5) rs Hypothesis
6) ¬qs Hypothetical Syllogism using (4) and (5)

Example 3: Show that the following argument is valid. If Mohan is a lawyer, then he is
ambitious. If Mohan is an early riser, then he does not like idlies. If Mohan is ambitious, then
he is an early riser. Then if Mohan is a lawyer, then he does not like idlies.

Let the Propositions and the corresponding variables be

1) Mohan is a lawyer – p
2) Mohan is ambitious – q
3) Mohan is an early riser – r
4) Mohan likes idlies – s

Then the hypothesis becomes - pq, r¬s, qr and the conclusion is p¬s

Step Reason
1) pq Hypothesis
2) r¬s Hypothesis
3) qr Hypothesis
4) pr Hypothetical Syllogism using (1) and (3)
5) p¬s Hypothetical Syllogism using (4) and (2)

*) The Resolution Principle

The Resolution principle is used to prove whether an argument is correct or not
Literal: A variable or negation of a variable is called a literal
Clause: A clause is a disjunction of literals
Resolvant: For any two clauses C1 and C2, if c1 has a literal L1 and C2 has L2 which is the
complement of literal L1, then delete L1 and L2 from C1 and C2 and construct the disjunction
of remaining literals. The result so obtained is called the resolvant of C1 and C2.
Example 1: Let us suppose that
C1 = P ˅ Q ˅ R
C2 = ¬P ˅ S ˅ T
P and ¬P are complementary to each other. According to the definition of resolvant, delete P
and ¬P and take the disjunction of the remaining literals ie. Q ˅ R ˅ S ˅ T

The Resolution Principle: if we have an argument where P1, P2, P3…….Pn are the premises
and C is the conclusion, to get a proof using resolution principle, put P1, P2, P3…Pn in clause
form and add to it ¬Cin clause form. From this sequence, if 0 can be derived, the argument is
valid.
Example1: modus ponens
p
pq
ie, q
in the clause from C1 = p
C2 = ¬p ˅q (pq = ¬p ˅ q)
C3 = ¬q
C4 = q
C5 = 0
Example 2: Show that the following argument is correct.
If today is Tuesday, I have a test in Mathematics or Economics. If my Economics Professor is
Sick, I will not have a test in Economics. Today is Tuesday and my Economics Professor is
sick. Therefore, I have a test in Mathematics.
Convert into variables
1) Today is Tuesday – p
2) I have a test in Mathematics – q
3) I have a test in Economics – r
4) My Economics Professor is sick – s

So Premises are: p(q ˅ r), s ¬r, p˄s and conclusion is q

Write in clause form C1 = ¬p ˅ q ˅ r

C2 = ¬s ˅ ¬r
C3 = p
C4 = s
C5 = ¬q
C6 = ¬p ˅ q ˅ ¬s (From C1 and C2)
C7 = q ˅ ¬s (From C6 and C3)
C8 = q (From C7 and C4)
C9 = 0 (From C8 and C5)
Therefore the given argument is valid

*) Rules of Inference for Quantified Statements

Universal Instantiation: - This rule is used to conclude that P(c) is true when ∀𝑥 P(x) is true.
Example 1:
Determine whether the argument “ All students in this class understand logic. David is a student
in this class. Therefore, David understands logic” is correct or not.
Let us assume that
P(x) denotes “ x is a student in the class”
Q(x) denotes “x understands logic”
1) ∀𝑥 P(x) Q(x) Premise
2) P(David) Premise
3) P (David) Q(David) By Universal Instantiation from (1)
4) Q(David) By Modus Ponenes from (2) and (3)
Universal Generalization: - This rule states that ∀𝑥 P(x) is true, given the premise, P© is
true for and arbitrary C.
Existential Instantiation: - This rule allows us to conclude that there is some element c for
which P(c) is true when ∃xP(x) is true.
Existential Generalization: - This rule states that ∃xP(x) is true when for a particular element
c, P (c) is true. If we know for some element c in the domain, P© is true, we also know that
∃xP(x) is true.

*) Sets
Set - Definition
A set is an unordered collection of different elements. The objects in a set are called elements
or members of the set. A set is said to contain its elements.

Some Example of Sets

A set of all positive integers
A set of all the states in India
A set of all the lowercase letters of the alphabet

Representation of a Set
Sets can be represented in two ways:

Roster or Tabular Form

Set Builder Notation

1) Roster or Tabular Form

The set is represented by listing all the elements comprising it. The elements are enclosed
within braces and separated by commas.

Example 1 − Set of vowels in English alphabet, A = {a,e,i,o,u}

Example 2 − Set of odd numbers less than 10, B = {1,3,5,7,9}

2) Set Builder Notation

The set is defined by specifying a property that elements of the set have in common.
Example 1 − The set {a,e,i,o,u} is written as −

A={x:x is a vowel in English alphabet}

Example 2 − The set {1,3,5,7,9} is written as −

Some Important Sets

N − the set of all natural numbers = {1,2,3,4,.....}
Z − the set of all integers = {.....,−3,−2,−1,0,1,2,3,.....}
Z+ − the set of all positive integers
Q − the set of all rational numbers
R − the set of all real numbers
W − the set of all whole numbers - {0,1,2,3,4,.....}

*) Types of Sets
Sets can be classified into many types. Some of which are finite, infinite, subset, universal,
proper, singleton set, etc.
Finite Set
A set which contains a definite number of elements is called a finite set.
Example − S ={x|x∈N and 70>x>50}
Infinite Set
A set which contains infinite number of elements is called an infinite set.
Example – S={x|x∈N and x>10}
Subset
A set X is a subset of set Y (Written as X⊆Y) if every element of X is an element of set Y.
Example 1 − Let, X={1,2,3,4,5,6} and Y={1,2}. Here set Y is a subset of set X as all the
elements of set Y is in set X. Hence, we can write Y⊆X.
Proper Subset
The term “proper subset” can be defined as “subset of but not equal to”. A Set X is a proper
subset of set Y (Written as X⊂Y) if every element of X is an element of set Y and |X|<|Y|.
Example − Let, X={1,2,3,4,5,6} and Y={1,2}. Here set Y⊂X since all elements in Y are
contained in X too and X has at least one element is more than set Y
Universal Set
It is a collection of all elements in a particular context or application. All the sets in that context
or application are essentially subsets of this universal set. Universal sets are represented as U.
Example − We may define U as the set of all animals on earth. In this case, set of all mammals
is a subset of U, set of all fishes is a subset of U, set of all insects is a subset of U, and so on.
Empty Set or Null Set
An empty set contains no elements. It is denoted by ∅. As the number of elements in an empty
set is finite, empty set is a finite set. The cardinality of empty set or null set is zero.
Example − S={x|x∈N and 7<x<8}=∅
Singleton Set or Unit Set
Singleton set or unit set contains only one element. A singleton set is denoted by {s}.
Example − S={x|x∈N, 7<x<9} = {8}
Equal Set
If two sets contain the same elements they are said to be equal.
Example − If A={1,2,6} and B={6,1,2}, they are equal as every element of set A is an element
of set B and every element of set B is an element of set A.
Equivalent Set
If the cardinalities of two sets are same, they are called equivalent sets.
Example − If A={1,2,6} and B={16,17,22}, they are equivalent as cardinality of A is equal to
the cardinality of B. i.e. |A|=|B|=3
Cardinality of a Set
Cardinality of a set S, denoted by |S|, is the number of elements of the set. The number is also
referred as the cardinal number. If a set has an infinite number of elements, its cardinality is ∞.
Example − |{1,4,3,5}|=4,|{1,2,3,4,5,…}|=∞

*) Set Operations
1) Set Union
The union of sets A and B (denoted by A∪B) is the set of elements which are in A, in B, or in
both A and B. Hence, A∪B={x|x∈A OR x∈B}.
Example − If A={10,11,12,13} and B = {13,14,15}, then A∪B={10,11,12,13,14,15}. (The
common element occurs only once)
2) Set Intersection
The intersection of sets A and B (denoted by A∩B) is the set of elements which are in both A
and B. Hence, A∩B={x|x∈A AND x∈B}.
Example − If A={11,12,13} and B={13,14,15}, then A∩B={13}

3) Set Difference/ Relative Complement

The set difference of sets A and B (denoted by A–B) is the set of elements which are only in A
but not in B. Hence, A−B={x|x∈A AND x∉B}.
Example − If A={10,11,12,13} and B={13,14,15}, then (A−B)={10,11,12} and
(B−A)={14,15}. Here, we can see (A−B)≠(B−A)

4) Complement of a Set
The complement of a set A (denoted by A′) is the set of elements which are not in set A. Hence,
A′={x|x∉A}.
More specifically, A′=(U−A) where U is a universal set which contains all objects.
Example − If A={x|xbelongs to set of oddintegers} then A′={y|y doesnot belong to set of odd
integers}

5) Cartesian Product / Cross Product

The Cartesian product of n number of sets A1,A2,…An denoted as A1×A2⋯×An can be
defined as all possible ordered pairs (x1,x2,…xn) where x1∈A1,x2∈A2,…xn∈An
Example − If we take two sets A={a,b} and B={1,2},
The Cartesian product of A and B is written as − A×B={(a,1),(a,2),(b,1),(b,2)}
The Cartesian product of B and A is written as − B×A={(1,a),(1,b),(2,a),(2,b)}

6) Power Set
Power set of a set S is the set of all subsets of S including the empty set. The cardinality of a
power set of a set S of cardinality n is 2n. Power set is denoted as P(S).

Example
For a set S={a,b,c,d} let us calculate the subsets −
Subsets with 0 elements − {∅} (the empty set)
Subsets with 1 element − {a},{b},{c},{d}
Subsets with 2 elements − {a,b},{a,c},{a,d},{b,c},{b,d},{c,d}
Subsets with 3 elements − {a,b,c},{a,b,d},{a,c,d},{b,c,d}
Subsets with 4 elements − {a,b,c,d}

*) Functions
Definition 1: A function or mapping (Defined as f: X → Y) is a relationship from elements of
one set X to elements of another set Y (X and Y are non-empty sets). X is called Domain and
Y is called Codomain of function ‘f’.
Let A and B be two sets. A function f: A → B is a relation from A to B, such that there must
be an assignment of exactly one element of B to each element of A.

Examples:

1
A
1 A

B 2
B 2
C 3
C 3
D 4
D 4

(1) (2)
Figure 1 is not a function because although all the elements in the domain have an image in B,
it is not unique elements (c has two images 1 and 3).
Figure 2 is a function because all the elements in the domain have images in the co-domain B
and there is an assignment of exactly one element of B to each element of A.

Definition 2: If f is a function from A to B, we say that A is the domain of f and B is the

codomain of f. If f (a) = b, we say that b is the image of a and a is a preimage of b. The range,
or image of f is the set of all images of elements of A. Also, if f is a function from A to B, we
say that f maps A to B.

Example 1 :
Let A = {1, 2, 3, 4} and B = {1, 4, 9, 16, 25}
Let us consider the rule f(x) = x2 to map elements from A to B.
Then, we have
f(1) = 12 = 1
f(2) = 22 = 4
f(3) = 32 = 9
f(4) = 42 = 16

Clearly each element in A has a unique image in B.

So, f : A ---> B : f(x) = x2 is a function from A to B.
Here, we have
Domain (f) = A = {1, 2, 3, 4}
Co-Domain (f) = B = {1, 4, 9, 16, 25}
Range (f) = {1, 4, 9, 16}

Definition 3: Let f be a function from A to B and let S be a subset of A. The image of S under
the function f is the subset of B that consists of the images of the elements of S. We denote the
image of S by f (S), so f (S) = {t | ∃s ∈S (t = f (s))}.
We also use the shorthand {f (s) | s ∈ S} to denote this set.
Example 17: Let A = {a, b, c, d, e} and B = {1, 2, 3, 4} with f (a) = 2, f (b) = 1, f (c) = 4, f (d)
= 1, and f (e) = 1. The image of the subset S = {b, c, d} is the set f (S) = {1, 4}.

*) Types of Functions:
1) One-to-one or Injective functions
A function f: AB is said to be one-to-one function, if every element of A has a unique element
in B. In the below figure A1, B2, C3. A one-to-one function is also called an injective
function.

A 1
A 1 B 2
B 2 C
3
C 3 D

One-to-one Function Not a One-to-one Function

Example: Determine whether the function from {a,b,c,d} to {1,2,3,4,5}with f(a) =4, f(b)=5,
f(c) =1 and f(d) = 3 is one-to-one?

A 1

B 2D

C 3

D 4
5
Since for every element in the domain there is a unique element in the co-domain, it is a one-
to-one function.

2) Onto or Surjective function:

A function f: AB is said to be Onto or Surjective function, if every element of B has a pre-
image in A under f.
In other words, A function f: AB is said to be Onto or Surjective function, if and only if for
every element b∈B there is an element a∈A with f(a) = b. A function is called a Surjection if it
is onto.

A 1 A 1
B 2 B 2
C 3 C 3

Onto or Surjective function Not a Onto or Surjective function

Example: Is the function f(x) = x2 from the set of integers to the set of integers onto?
Ans. The function f is not onto because there is no integer x with x2 = -1, for instance.
3) One-to-one Correspondence or Bijection
A function f: AB is said to be One-to-one Correspondence or Bijection, if it is both one-to-
one function and onto.

A 1 A 1
B 2 B 2
C 3 3
C
D 4 4

(1) (2)

Figure (1) is a Bijection or one-to-one correspondence but figure (2) is not a Bijection or one-
to-one correspondence because it is not a Onto function (element 3 does not have an association
in the Domain).
Examples of Different types of Correspondences

4) Inverse Functions

Let f be a one-to-one correspondence from the set A to the set B. The inverse function of f is
the function that assigns to an element b belonging to B the unique element a in A such that
f(a) = b. The inverse function of f is denoted by f-1. Hence f-1(b) =a when f(a) = b.
A one-to-one correspondence is called invertible because we can define an inverse of this
function. A function is not invertible if it is not a one-to-one correspondence because the
inverse of such a function does not exist.

Example: Let f be the function from {a,b,c} to (1,2,3} such that f(a) = 2, f(b) = 3, f(c) = 1 is f
invertible and if it is what is the inverse?
The function f is invertible because it is one-to-one correspondence. The inverse function f-1
reverses the correspondence given by f, so f-1(1) = c, f-1(2) = a, f-1(3) = b

5) Composite Functions
Let g be a function from the set A to the set B and let f be a function from the set B to the set
C. The composition of the functions f and g, denoted by f o g, is defined by (f o g) (a) = f(g(a)).

Example: Let f and g be the functions from the set of integers to the set the of integers defined
by f(x) = 2x + 3 and g (x) = 3x + 2. What is the composition of f and g? what is the composition
of g and f?
f o g(x) = f(g(x)) = f(3x + 2) = 2(3x + 2) + 3 = 6x + 7
g o f (x) = g (f(x) = g (2x + 3) = 3 (2x + 3) + 2 = 6x + 11.
6) The Graph Functions:
Let f be a function from the set A to the set B. The graph of the function f is the se of ordered
pairs {(a, b) | a ∈ A and f(a) =b}

Example: Display the graph of the function f(n) = 2n + 1 from the set of integers to the set of
integers.

*) Sequence:
It is a set of numbers in a definite order according to some definite rule (or rules).
Each number of the set is called a term of the sequence and its length is the number of terms in
it.
For example:
2, 4, 6, 8 ...., 20 is a finite sequence obtained by adding 2 to the previous number.
10, 6, 2, -2, ..... is an infinite sequence obtained by subtracting 4 from the previous number.
A sequence is a discrete sttructure used to represent an ordered list. For Example, 1,2,3,5,8 is
sequence with five terms and 1,3,9,27,81.....is an infinite sequence.
Example1: Consider the sequence {an}, where an =1/n
The list of the terms of this sequence, beginning with a1, namely a1, a2, a3,a4…..starts with
1,1/2,1/3,1/4…
If the terms of a sequence can be described by a formula, then the sequence is called a
progression.
*) Arithmetic Progression
An arithmetic progression is a sequence of the form
a, a+d, a+2d, …….a+nd…where the initial term a and the common difference d are real
numbers.
An arithmetic progression is a discrete analogue of the linear function f(x) = dx +a
Example: 5, 10, 15, 20, 25…..(Initial value is 5 and common difference is 5)
*) Geometric Progression
A geometric progression is a sequence of the form a, ar, ar2…….arn…where the final term a
and the common ratio r are real numbers.
A geometric progression is a discrete analogue of the exponential function f(x)= arx
Example: 2, 4, 8, 16….(Initial value is 2 and common ratio is 2)

Example: Find the formula for the sequence with the following first five terms:
a) 1, 1/2, 1/4 , 1/8 – it is a geometric progression with a =1 and r = 1/2
b) 1, 3, 5, 7, 9 – This proposed sequence is an arithmetic progression with a =1 and d = 2
c) 1, -1, 1, -1, 1 – This proposed sequence is a geometric progression with a =1 and r = -1

*) Summations:
Summation of the terms of a sequence am, am+1, am+2….an.

Here, the index of summation runs through all integers starting with its lower limit m and
ending with its upper limit n.
Question: Find out the value of Σ 50<=k<=100 k2 ?