UNIT – 1

Mathematical Logic and

Set Theory
 Syllabus
• Propositional Logic
• Applications of Propositional Logic
• Propositional Equivalences
• Predicates and Quantifiers
• Nested Quantifiers
• Rules of Inference
• Introduction to Proofs
• Proof Methods and Strategy Sets
• Combination of sets
• Venn Diagrams
• Finite and Infinite sets, Uncountably infinite sets,
• Principle of inclusion and exclusion, multisets .
 Syllabus

• Propositional Logic
• Applications of Propositional Logic
• Propositional Equivalences
• Predicates and Quantifiers
• Nested Quantifiers
• Rules of Inference
• Introduction to Proofs
• Proof Methods and Strategy Sets
• Combination of sets
• Venn Diagrams
• Finite and Infinite sets, Uncountably infinite sets,
• Principle of inclusion and exclusion, multisets .
 Proposition
• Proposition: It is basic building block of logic.
Definition: A statement or proposition is a declarative sentence that is either
True (T) or False (F), but not both.

Example:
1. It is raining
2. 1 + 1 = 2
3. Do you study everyday?
4. 5 – x = 4
5. Listen to me.
 Proposition
• Proposition: letters are used to denote propositions. Some conventional
letters are p,q,r,s,….

Example:
1. p: It is raining
2. q: 1 + 1 = 2
3. r: Do you study everyday?
4. s: 5 – x = 4
5. a: Listen to me.
 Producing new Proposition
• Producing new proposition: new propositions can be produced from
those we already have.
• These methods were discussed by English mathematician George Boole
in 1854 in his book of Thelaw of thought
• New propositions are called compound propositions
• Compound propositions are formed from existing propositions using
logical operators.
 Truth Table
• Truth Table: Truth table displays the relationship between the truth
values of propositions.
• It determine truth values of propositions constructed from simpler
propositions
 Negation of Proposition
• Negation of Proposition: if 𝑝 is the statement, the negation of 𝒑 is the
statement not 𝒑 , denoted by ~𝒑.
• Sometimes ¬𝒑 , 𝒑
• ~𝒑: “it is not the case that 𝑝”
Example:
𝒑: “it is Friday”  ~𝒑: “it is not Friday”

Truth table for Negation of

Proposition
𝒑 ~𝒑
T F
F T
 Conjunction of Proposition
• Conjunction of Proposition: if 𝑝 and 𝑞 are statements, the conjunction of
𝒑 and 𝒒 is the compound statement 𝒑 and 𝒒 , denoted by 𝒑 ∧ 𝒒.
Example:
𝒑: “Today is Friday” and 𝒒: “It is raining today”
Truth table for conjunction of Proposition
𝒑 𝒒 𝒑 ∧𝒒
T T T
T F F
F T F
F F F

This proposition is true on rainy Fridays and is false on any day that is not
Friday and on Fridays when it does not rain.
 Disjunction of Proposition
• Disjunction of Proposition: if 𝑝 and 𝑞 are statements, the disjunction of
𝒑 or 𝒒 is the compound statement 𝒑 or 𝒒 , denoted by 𝒑 ∨ 𝒒.
Example:
𝒑: “Today is Friday” and 𝒒: “It is raining today”
Truth table for disjunction of Proposition
𝒑 𝒒 𝒑 ∨𝒒
T T T
T F T
F T T
F F F

This proposition is true on any day that is either Friday or Rainy day. It is only
false on days that are not Friday when it is also does not rain.
 Implication of Proposition
• Implication of Proposition: if 𝑝 and 𝑞 are statements, the compound
statement "𝒑 then 𝒒" , denoted by 𝒑 → 𝒒, is called conditional
statement or implication.
• The statement 𝒑 is called antecedent or hypothesis and 𝒒 is called
consequent or conclusion.
• A useful of way to remember that an implication is true when its
hypothesis is false is to think of a contrast or an obligation.
• If condition specified by such statement is false, no obligation is in
force.
 Implication of Proposition
• Because implication arise in many places in mathematical reasoning, a wide
variety of terminology is used to express 𝑝 → 𝑞.
• Some of common ways of expressing the implication are:
o “if 𝑝, then 𝑞”
o “𝑝, implies 𝑞”
o “if 𝑝, 𝑞”
o “𝑝 only if 𝑞”
o “𝑝 is sufficient for 𝑞”
o “𝑞 if 𝑝”
o “𝑞 whenver 𝑝”
o “𝑞 is necessary for 𝑝”
 Implication of Proposition
Example:
𝒑: “Today is Friday” and 𝒒: “It is raining today”

Truth table for implication of

𝒑Proposition 𝒒 𝒑 →𝒒
T T T
T F F
F T T
F F T

This proposition is true on any day that is either Friday or Rainy day. It is
only false on days that are not Friday when it is also does not rain.
 Implication of Proposition
Example:
𝒑: “2+2=4” and 𝒒: “x:=x+1”
if ‘x=0’ before this statement encountered?
Solution:
Since 2+2=4 is true, the assignment statement x:=x+1 is executed.
Hence x has the value 0+1=1 after this statement is encountered
 Related Implication of Propositions
• There are some related implications that can be formed from 𝒑 → 𝒒

• Implication of Proposition: if 𝒑 → 𝒒, is an implication, then

• The converse of 𝒑 → 𝒒 is the implication of 𝒒 → 𝒑
• The inverse of 𝒑 → 𝒒 is the implication of ¬𝒑 → ¬𝒒
• The contrapositive of 𝒑 → 𝒒 is the implication of ¬𝒒 → ¬𝒑
 Related Implication of Propositions
Example:
“if today is Thursday, then I have a testtoday”

Solution:
The converse is “if I have a test today, then today isThursday”

The contrapositive is “if I do have a test today, then today is not

Thursday”
 Bidirectional of Proposition
• Bidirectional of Proposition: if 𝑝 and 𝑞 are statements, the compound
statement “𝒑 if and only if 𝒒” , denoted by 𝒑 ↔ 𝒒 is called an
bidirectional.

The bidirectional is true when both implications 𝒑 → 𝒒 and 𝒒 → 𝒑 are

true. Because of this, the terminology “𝒑 if and only if 𝒒” is used in
bidirectional
 Bidirectional of Proposition
Example:

Truth table for bidirectional of

𝒑Proposition 𝒒 𝒑 ↔𝒒
T T T
T F F
F T F
F F T
 An examples on Compound Proposition
Example: Construct a truth table for (𝑝 ∧ 𝑞) ∨ ¬𝑝

A B C D E

𝒑 𝒒 𝑝 ∧𝑞 ¬𝑝 (𝑝 ∧ 𝑞) ∨ ¬𝑝
T T T F T
T F F F F
F T F T T
F F F T T
 More examples on Compound Proposition
Example 1: (𝑝 → 𝑞) ↔ (¬𝑞 → ¬𝑝
)
Example 2: 𝑝 → (¬𝑞 ∨ 𝑟)
Example 3: (𝑝 → 𝑞) ∨ (¬𝑝 → 𝑟
) Example 4:(𝑝 → 𝑞) ∧ (¬𝑝 →
𝑟) Example 5:(𝑝 → 𝑞) ↔ (𝑞
→ 𝑝)
 Syllabus

• Propositional Logic
• Applications of Propositional Logic
• Propositional Equivalences
• Predicates and Quantifiers
• Nested Quantifiers
• Rules of Inference
• Introduction to Proofs
• Proof Methods and Strategy Sets
• Combination of sets
• Venn Diagrams
• Finite and Infinite sets, Uncountably infinite sets,
• Principle of inclusion and exclusion, multisets .
 Applications of Propositional Logic
• Translating English Sentences
• System Specifications
• Boolean Searches
• Logic Puzzles
• Logic Circuits
 Translating English Sentences
• Why it is required
• Toremove ambiguity
• Manipulate expressions ( easy in logical sentences)
• Able to solve puzzles
• Example: Youare not allowed to drive vehicle if your age is less than 18
years or you have no age proof.
 Translating English Sentences
• Example:
Youare not allowed to drive vehicle if your age is less than 18 years or
you have no age proof
Step-1: Find the connectives which are connecting two propositions
together
Step-2: Rename the propositions
Let: q: “you are allowed to drive vehicle”
r: “ your age is less than 18”
s: “you have age proof”
 Translating English Sentences
• Example:
Youare not allowed to drive vehicle if your age is less than 18 years or
you have no age proof.
Step-1: Find the connectives which are connecting two propositions
together
Step-2: Rename the propositions
Let: q: “you are allowed to drive vehicle”
r: “ your age is less than 18”
s: “you have age proof”
(𝑟 ∨ ¬𝑠) → 𝑞
 System Specifications
• Translating sentences in natural language(such as English) into logical
expressions is required for hardware and software system.
• Example: Express the specification
• The automated reply cannot be sent when the file system is full.
 Consistent System Specifications
• A list of propositions is consistent if it is possible to assign truth values
to the proposition variables, so that each proposition is true.
 Consistent System Specifications
• Example: Are these propositions consistent
[Link] diagnostic message is stored in the buffer or it is retransmitted.
[Link] diagnostic message is not stored in the buffer
[Link] diagnostic message is stored in the buffer, then it is retransmitted
If p-diagnostic message is stored in the buffer
q-diagnostic message is retransmitted
 Consistent System Specifications
• Solution: Are these propositions consistent
[Link] diagnostic message is stored in the buffer or it is retransmitted (
𝑝 ∨ 𝑞).
2. The diagnostic message is not stored in the buffer (¬𝑝)
[Link] diagnostic message is stored in the buffer, then it is retransmitted
(p → 𝑞)
If p-diagnostic message is stored in the buffer
q-diagnostic message is retransmitted
When p is false and q is true, all statements are true
So, the specification is consistent.
 Consistent System Specifications
• Solution: Are these propositions consistent
[Link] diagnostic message is stored in the buffer or it is retransmitted (
𝑝 ∨ 𝑞).
2. The diagnostic message is not stored in the buffer (¬𝑝)
[Link] diagnostic message is stored in the buffer, then it is retransmitted
(p → 𝑞)
4. The diagnostic message is not transmitted
If p-diagnostic message is stored in the buffer
q-diagnostic message is retransmitted

So, the specification is not consistent.

 Boolean Searches
• Used for searches of large collection of information such as indexes of
web pages
• Ex: While searching about universities, we can look for pages matching
Pune, Mumbai and Nagpur universities
 Logic Circuit
• Propositional logic can be applied to the design of computer
hardware.
• Basic logic gates are used.
• We can also use combinations of these gates to built complicated
circuits
• Example: Built a digital circuit that produces the output
(p ˅ ¬ r) ˄ (¬ p ˅(q ˅ ¬ r) when given input bits are p, q, r.
 Syllabus

• Propositional Logic
• Applications of Propositional Logic
• Propositional Equivalences
• Predicates and Quantifiers
• Nested Quantifiers
• Rules of Inference
• Introduction to Proofs
• Proof Methods and Strategy Sets
• Combination of sets
• Venn Diagrams
• Finite and Infinite sets, Uncountably infinite sets,
• Principle of inclusion and exclusion, multisets .
 Tautology, Contradiction and Contingency
• Tautology: A compound proposition is always true, no matter what the
truth values of propositions that occur in it, is called tautology.
• Contradiction: A compound proposition is always false, is called
contradiction.
• Contingency : A compound proposition is that is neither a tautology nor a
contradiction is called contingency.
 Tautology, Contradiction and Contingency
Example: Tautology and Contradiction of (𝑝 ∨ ¬𝑝) and (𝑝 ∧ ¬𝑝)

Tautology Contradiction
𝒑 ¬𝑝 (𝑝 ∨¬𝑝) (𝑝 ∧ ¬𝑝)
T F T F
F T T F
 Logical Equivalence
• Logical Equivalent: Compound propositions that have the same
truth values in all possible cases are called Logical Equivalent.
Example: The proposition 𝑝 and 𝑞 are called logically equivalent if
(𝑝 ↔ 𝑞) is tautology.
𝒑 𝒒 𝒑 ↔𝒒
T T T
T F F
F T F
F F T
 Logical Equivalence
• Logical Equivalent: one way to determine whether two propositions are
equivalent is to use truth table.
Example: Show that ¬ 𝑝 ∨ 𝑞 and (¬𝑝 ∧ ¬𝑞) are logically
equivalent.
A B C D E F G

𝒑 𝒒 𝑝 ∨𝑞 ¬ 𝑝 ∨𝑞 ¬𝑝 ¬𝑞 (¬𝑝 ∧ ¬𝑞)

T T T F F F F
T F T F F T F
F T T F T F F
F F F T T T T
 Logical Equivalence

Example: Show that (¬𝑝 ∨ 𝑞) and (𝑝 → 𝑞) are logically equivalent.

A B C D E

𝒑 𝒒 ¬𝑝 (¬𝑝 ∨ 𝑞) (𝑝 → 𝑞)
T T F T T
T F F F F
F T T T T
F F T T T
 More examples on Equivalence
Example 1: (𝑝 ∨ 𝑞 ∧ 𝑟 𝑎𝑛𝑑 (𝑝 ∨ 𝑞) ∧ (𝑝 ∨ 𝑟)
Example 2: 𝑝 → 𝑞 𝑎𝑛𝑑 (¬𝑞 → ¬𝑝)
Example 3: 𝑝 ∨ 𝑞 𝑎𝑛𝑑 (𝑞 ∨𝑝)
Example 4: 𝑝 → 𝑞 𝑎𝑛𝑑 (¬𝑝 ∨𝑞)
Example 5: ¬𝑝 ∨ (¬𝑝 ∧ 𝑞 )𝑎𝑛𝑑 (¬𝑝 ∧¬𝑞)
Example 6: show that 𝑎𝑛𝑑 (𝑝 ∧ 𝑞) ↔ 𝑝 ∨ 𝑞 is tautology
 Syllabus

• Propositional Logic
• Applications of Propositional Logic
• Propositional Equivalences
• Predicates and Quantifiers
• Nested Quantifiers
• Rules of Inference
• Introduction to Proofs
• Proof Methods and Strategy Sets
• Combination of sets
• Venn Diagrams
• Finite and Infinite sets, Uncountably infinite sets,
• Principle of inclusion and exclusion, multisets .
 Predicates
• Predicates: Sometimes because of involving variables such as “x>3”,
“x=y=5” can not predict truth value of statement suchas true or false.
• The statement “x is greater than 3” has two parts.
• The first part is variable ‘x’  subject of statement
• Second part is ‘is greater than 3’predicate (property of subject)
• Notation: 𝑷(𝒙)
where, Pdenote predicate ‘is greater than 3’
x is a variable
• Once value is assigned to ‘x’, the statement 𝑃 (𝑥) becomes a
proposition and has a truth value.
 Predicates
• Example: Let 𝑃 (𝑥) denote statement “x>5”, what are truth values of P(1)
and P(10).
• P(1) : 1 > 5  False
• P(10) : 10 > 5  True

• Example: Let 𝑃(𝑥, y) denote statement “x=y+5”, what are truth values of
P(6,1) and P(10,5).
• P(6,1) : 6= 5+1  True
• P(10,5) : 10 =5+ 5  True

• Example: Let 𝑃(𝑥, y, z) denote statement “x+y=z”, what are truth values of
P(1,2,3).
• P(1,2,3) : 1 +2=3  True
 Predicates
• Statement of form P(x1, x2, x3… xn) is the value of proposition function
Pat the n-tuple (x1, x2, x3… xn) and Pis called as predicate.

•Example: consider the statement

if x > 0; then x:=x+1
 Quantifiers
• Quantifier: It is another way to create proposition from propositional
function.
• Two types of quantification
• Universal Quantifier
• Existential Quantifier
 Universal Quantifier
• Universal Quantifier: Many mathematical statements asserts that is true for
all values. Suchstatement is expressed using universal quantification.
• 𝑃(𝑥) is true for all values of x in the universe of discourse.
• Definition: The universal quantification of 𝑃(𝑥) the proposition
“𝑃(𝑥) is true for all values of x in the universe discourse”
• Notation: ∀𝑃(𝑥)
here, ∀  universal quantifier of 𝑃(𝑥)
Read as:
“for all 𝑥 of 𝑃(𝑥)” or “for every 𝑥 of 𝑃(𝑥)”
 Universal Quantifier
• Example: “Every apple is red”
let 𝑃(𝑥) denote the statement “𝑥 is red”
Then, statement “Every apple is red” can be expressed as ∀𝑷(𝒙)

• Question: Let 𝑃(𝑥) is the statement “x+1>x”. What is truth value of

quantification ∀𝑃(𝑥)
• Answer: True

• Question: Let 𝑃 (𝑥) is the statement “x<2”. What is truth value of

quantification ∀𝑃(𝑥)
• Answer: False
 Existential Quantifier
• Existential Quantifier: Many mathematical statements asserts that is there is
an element with a certain property. Such statement is expressed using
existential quantification.
• 𝑃(𝑥) is true for at least one value of x in the universe of discourse.
• Definition: The existential quantification of 𝑃(𝑥) the proposition
“There exists an element 𝑥 in the universe discourse such that 𝑃(𝑥) is true”
• Notation: ∃𝑃(𝑥)
here, ∃  existential quantifier of 𝑃(𝑥)
Read as:
“There is 𝑥 suchthat 𝑃(𝑥)” or “There is at least one 𝑥 such that 𝑃(𝑥)”
or “for some 𝑥 𝑃(𝑥) ”
 Existential Quantifier
• Example: “Some apples are red”
let 𝑃(𝑥) denote the statement “𝑥 are red”
Then, statement “Some apples are red” can be expressed as ∃ 𝑷(𝒙)

• Question: Let 𝑃 (𝑥) is the statement “x>3”. What is truth value of

quantification ∃ 𝑃(𝑥)
• Answer: since “x>3” is true for instance, when x=4

• Question: Let 𝑃(𝑥) is the statement “x=x+1”. What is truth value of

quantification ∃ 𝑃(𝑥)
• Answer: False
 Quantifiers

Statement When True When False

∀𝑃(𝑥) 𝑃 𝑥 is true for every 𝑥 There is 𝑥 for which 𝑃(𝑥)
is false

∃𝑃(𝑥) There is 𝑥 for which 𝑃(𝑥) 𝑃 𝑥 is false for every 𝑥

is true
 Negating Quantifiers
• Every student in your class has taken a course in calculus.”
• P(x)is the statement “x has taken a course in calculus”.
∀ x P ( x )
• Negation: –“It is not the case that every student in your class has taken a
course in calculus.”
 ¬∀xP(x)
• This is equivalent to “There is a student in your class who has not taken a
course in calculus.”
 ∃x¬P(x).
• This example illustrates the following logical equivalence:
¬ ∀ x P ( x ) ↔ ∃x¬P(x).
 De Morgan’s Law for Quantifiers

Negation Equivalent When negation is When False

Statement True?
¬∃x𝑃(𝑥) ∀x¬𝑃(𝑥) For every 𝑥, 𝑃 There is 𝑥 for
𝑥 which 𝑃(𝑥) is true
is false

¬∀x𝑃(𝑥) ∃x¬𝑃(𝑥) There is 𝑥 for 𝑃 𝑥 is true for

which 𝑃(𝑥) is false every 𝑥
 Negating Quantifiers : Example

There is an honest politician

• H(x): “x is honest.”
• “There is an honest politician” is represented by ∃xH(x),
• Negation: ¬∃xH(x), ∀x¬H(x) (All politicians are not honest)
 Negating Quantifiers : Example

All Americans eat cheeseburgers

• C(x):x eat cheeseburgers
• Domain: All americans
• ∀xC(x)–Negation: ¬∀xC(x), ∃x ¬C(x)
• (SomeAmerican does not eat cheeseburgers / “There is an American
who does not eat cheeseburgers.”)
 Negating Quantifiers : Example

• Express each of these statements using quantifiers. Then form the

negation of the statement, so that no negation is to left of quantifier.
Express the negation in English statement
• Some old dogs can learn new tricks
• No rabbits know calculus
• Every bird can fly
• There is no dog that can talk
• There is no one in this class who knows French and Russian
 Negating Quantifiers : Solution

Some old dogs can learn new tricks

• T(x): x can learn new tricks
• Domain :old dogs.
• Our original statement is : ∃xT(x).
• Negation : ¬∃xT(x).
• which we must to rewrite in the required manner as∀x¬T(x).
 Negating Quantifiers : Solution

No rabbit knows calculus.

• Let C(x): xknows calculus,
• let the domain be Rabbits.
• Our original statement is ¬∃x C(x). .
• Negation is: ∃x C(x). (i.e., There exists a Rabitwho knows the calculus),
 Negating Quantifiers : Solution

Every bird can fly.

• Let F(x): x can fly,
• let the domain be birds.
• Our original statement is ∀x F(x).
• Negation is: ¬∀x F(x). (i.e., not all birds can fly),
• which we must to rewrite in the required manner as ∃x¬F(x) . ("There is a
bird who cannot fly.“)
 Negating Quantifiers : Solution

There is no dog that can talk

• Let T(x): x can talk,
• let the domain be dogs.
• Our original statement is ∀x ¬T(x).
• Negation is: ∃x T(x). (i.e., There exist a dog who can talk),
 Negating Quantifiers : Solution

There is no one in this class who knows French and Russian

• F(x) : x knows French
• R(x): x knows Russian
• Domain: Class
• Original statement: ∀x(¬ F(x)˄¬ R(x)) or ¬∃x( F(x)˄ R(x))
• Negation: ¬∀x(¬ F(x)˄ ¬ R(x))
• ∃x( F(x)˄ R(x))
 Quantifier Example
• Question: Let 𝑃(𝑥) is the statement “x spends more than 5 hrs every
day in class”. Domain is ‘all students’. Express following quantification in
English
• ∃𝑃 𝑥
• ∀𝑃 𝑥
• ∃𝑥¬ 𝑃(𝑥)
• ∀𝑥¬𝑃 𝑥
 Quantifier Example: Solution
• Question: Let 𝑃(𝑥) is the statement “x spends more than 5 hrs every
day in class”. Domain is ‘all students’. Express following quantification in
English
• ∃ 𝑃 𝑥 : There is a student who spends more than 5 hrs every week day in
class
• ∀ 𝑃 𝑥 : Every student spends more than 5 hrs every week day in class
• ∃𝑥¬ 𝑃(𝑥): There is a student who does not more than 5 hrs every week day in
class
• ∀𝑥¬𝑃 𝑥 : No students spends more than 5 hrs every week day in class (or
Every student spends less than or equal to five hrs every week day in class)
 Quantifier Example
• Question: Let 𝑃(𝑥) is the statement “the word x contains the letter a”.
What are truth values
• 𝑃 𝑜𝑟𝑎𝑛𝑔𝑒
• 𝑃 𝑙𝑒𝑚𝑜𝑛
• 𝑃 𝑡𝑟𝑢𝑒
• 𝑃 𝑓𝑎𝑙𝑠𝑒
 Quantifier Example: Solution
• Question: Let 𝑃(𝑥) is the statement “the word x contains the letter a”.
What are truth values
• 𝑃 𝑜𝑟𝑎𝑛𝑔𝑒 
• 𝑃 𝑙𝑒𝑚𝑜𝑛 
• 𝑃 𝑡𝑟𝑢𝑒 true
 
false 
• 𝑃 𝑓𝑎𝑙𝑠𝑒 false
 
true
 Quantifier Example
• Question: Translate these statements in English
C 𝑥 : x is a comedian
F 𝑥 : x is funny
and the domain consists of all people.
• ∀𝑥𝐶 𝑥 → 𝐹(𝑥
• ∀𝑥𝐶 𝑥 )
• ∃𝑥𝐶 𝑥 ∨ 𝐹(𝑥)
• ∃𝑥𝐶 𝑥 → 𝐹(𝑥
)
∧ 𝐹(𝑥)
 Quantifier Example : Solution
• Question: Translate these statements in English
C 𝑥 : x is a comedian
F 𝑥 : x is funny
and the domain consists of all people.
• ∀𝑥𝐶 𝑥 → 𝐹 𝑥 : for every x, if x is a comedian, then x is funny. "Every
comedian is funny."
• ∀𝑥𝐶 𝑥 ∨ 𝐹 𝑥 : Every comedian are funny”, Every person is a funny comedian
• ∃𝑥𝐶 𝑥 → 𝐹 (𝑥): "There exists a person such that ifs/he is a comedian,
then s/he is funny."
• ∃𝑥𝐶 𝑥 ∧ 𝐹 (𝑥): “There exists a funny comedian" or "Some comedians are
funny" or–"Some funny people are comedians."
 Quantifier Example
• Question:
• P 𝑥 : x can speak Russian
• Q 𝑥 : x knows the computer language c++
• Domain-All students at your school1.
• There is a student at your school who can speak Russian and who knows c++
• There is a student at your school who can speak Russian but doesn’t know c++
• Every student at your school either can speak Russian or knows c++
• No student at your school can speak Russian or know c++
 Quantifier Example
• Question:
• P 𝑥 ; x=x2 ,if the domain consist of int what are these truth values?
• P(0)
• P(1)
• P(2)
• P(-1)
• ∃x P(x)
• ∀x P(x)
 Syllabus

• Propositional Logic
• Applications of Propositional Logic
• Propositional Equivalences
• Predicates and Quantifiers
• Nested Quantifiers
• Rules of Inference
• Introduction to Proofs
• Proof Methods and Strategy Sets
• Combination of sets
• Venn Diagrams
• Finite and Infinite sets, Uncountably infinite sets,
• Principle of inclusion and exclusion, multisets .
 Nested Quantifier
• When quantifier is used on the variable 𝑥 or when we assign a value
to this variable, the occurrence of variable is bound.
• An occurrence of a variable is not bound by quantifiers or set to
particular value is said to be free.
• All variables that occur in propositional function must be bound to turn
into proposition.
• This can be done using combination of universal quantifiers, existential
quantifiers and value assignment.
• In such case, order of quantifiers is important.
 Nested Quantifier
• Question: let 𝑃(𝑥, y) be the statement “x+y=y+x”. What is truth value
of quantification ∀x∀𝑦𝑃(𝑥, y) ?
• Answer: for all real numbers 𝑥 and y, it is true that “x+y=y+x”. Hence
truth value is TRUE
 Nested Quantifier
• Question: let 𝑃(𝑥, y) be the statement “x+y=0”. What is truth value of
quantification ∃y∀x𝑃(𝑥, y) and ∀x∃𝑦𝑃(𝑥, y) ?

• Answer: ∃y∀x𝑃 𝑥, y  False

∀x∃𝑦𝑃(𝑥, y)  True
 Nested Quantifier

Statement When True When False

∀x∀𝑦𝑃(𝑥, y) 𝑃 𝑥, y is true for every pair There is a pair 𝑥, y for which
𝑥, y 𝑃(𝑥, y) isfalse
∀x∃𝑦𝑃(𝑥, y) For every 𝑥 there is 𝑦for There is a 𝑥 such that 𝑃(𝑥, y) is
which 𝑃(𝑥, y) is true false for every y
∃x∀𝑦𝑃(𝑥, y) There is a 𝑥 for which 𝑃(𝑥, y) is For every 𝑥 there is 𝑦 for which
true for every y 𝑃(𝑥, y) isfalse

∃x∃𝑦𝑃(𝑥, y) There is a pair 𝑥, y for which 𝑃 𝑥, y is false for every pair

𝑃(𝑥, y) istrue 𝑥, y
 Syllabus

• Propositional Logic
• Applications of Propositional Logic
• Propositional Equivalences
• Predicates and Quantifiers
• Nested Quantifiers
• Rules of Inference
• Introduction to Proofs
• Proof Methods and Strategy Sets
• Combination of sets
• Venn Diagrams
• Finite and Infinite sets, Uncountably infinite sets,
• Principle of inclusion and exclusion, multisets .
 Rules of Inferences
• An argument in propositional logic is sequence of propositions.
• All but the final propositions in the argument are called premises and
final proposition is called conclusion.
• An argument is valid if the truth of all premises implies that the
conclusion is true.
 Rules of Inferences
• Example:
• “if you have a current password, then you can log onto network”
𝑃: “if you have a current password”
Therefore
𝑄: “you can log onto network”

Then argument is in form

𝑃 →𝑄
𝑃
-----------------------
𝑄
 Rules of Inferences

Rule of Tautology Name

Interferen
ce

𝑃 →𝑄 (𝑃 ∧ P → 𝑄 ) → 𝑄 Modus Ponens
𝑃
-
𝑄
 Rules of Inferences

Rule of Tautology Name

Interferen
ce

¬𝑄 (¬𝑄 ∧ P → 𝑄 ) → ¬𝑃 Modus Tollens

𝑃 →𝑄
-
¬𝑃
 Rules of Inferences

Rule of Tautology Name

Interferen
ce

𝑃 → ( P → 𝑄 ∧ Q → 𝑅) → P → 𝑅 Hypothetical Syllogism
𝑄 Q
→𝑅
-
𝑃 →𝑅
 Rules of Inferences

Rule of Tautology Name

Interferen
ce

𝑃 ∨𝑄 ( P ∨ 𝑄 ∧ ¬𝑃) → 𝑄 Disjunctive Syllogism

¬𝑃
-
𝑄
 Rules of Inferences

Rule of Tautology Name

Interferen
ce

𝑃 →𝑄 ( P ∧𝑄 ) → 𝑃 Simplification
-
𝑃
 Rules of Inferences

Rule of Tautology Name

Interferen
ce

𝑃 ( P) ∧ ( 𝑄 ) → (P ∧ 𝑄 ) Conjunction
𝑄
-
P ∧𝑄
 Rules of Inferences
• Example:
• State which rule of inference is the basis of the following argument.
“it is freezing and raining. Therefore, it is freezing ”

• Example:
• State which rule of inference is the basis of the following
argument.
“if it rains today, then we will not have barbecue today. If we do
not have a barbecue today, then we will have a barbecue
tomorrow. Therefore, if it rains today, then we will have a barbecue
tomorrow”
 Rules of Inferences : Example
“ Raja works hard”, “If Raja works hard, then he is a dull boy” and “If Raja is
a dull boy then he will not get the job”
We need to conclude that “Raja will not get the job”
• Solution:
• H-Raja works hard
• D-Raja is a dull boy
• J-Raja will get the job
[Link] work hard –H
[Link] Raja works hard, then he is a dull boy : H→D
[Link] Raja is a dull boy then he will not get the job: D → ¬J
There are three premises and one conclusion. Solve any two premises at a
time.
 Rules of Inferences : Example
• If we solve first two (H and H → D), we will get D ( By using Modus
Pones rule)
• Then we can solve D and third premise (D → ¬ J), we will get ~J ( By
using Modus Pones rule)
• ¬ J – “Raja will not get the job”
 Rules of Inferences : Exercise
• “ If it does not rain or it is not foggy, then sailing race will be held and
life saving demo will go on”
• “If the sailing race is held, then the trophy will be awarded”
•“The trophy was not awarded”
Conclusion: It rained
 Rules of Inferences : Exercise
Show that the premises
• “It is not sunny this afternoon and it is colder than yesterday,”
• “We will go swimming only if it is sunny,”
• “If we do not go swimming, then we will take a canoe trip,” and
• “If we take a canoe trip, then we will be home by sunset”
conclusion “We will be home by sunset”
 Rules of Inferences : Exercise
• Show that the premises
• “If you send me an e-mail 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”
• conclusion “If I do not finish writing the program, then I will wake up
feeling refreshed.”
 Syllabus

• Propositional Logic
• Applications of Propositional Logic
• Propositional Equivalences
• Predicates and Quantifiers
• Nested Quantifiers
• Rules of Inference
• Introduction to Proofs
• Proof Methods and Strategy Sets
• Combination of sets
• Venn Diagrams
• Finite and Infinite sets, Uncountably infinite sets,
• Principle of inclusion and exclusion, multisets .
 Introduction to Proofs

• Methods of proving theorems

• Direct Method
• Indirect Method
• Proof by Contrapositive
• Proof by contradiction
 Direct Proof Method

• A direct proof shows that

• a conditional statement p → q is true by showing that if p is true, then
q must also be true,
• so that the combination p true and q false never occurs
 Direct Proof Method

• Theorem: 1+2+3+......+n = n(n+1)/2

• Proof:
Let x = 1+2+3+......+n (1)
Then x = n + (n-1) + (n-2) + (n-3) + …..+1 (2)
So,
2x = (n+1) + (n+1) + (n+1) +….. +(n+1)
= n(n+1) (adding 1& 2)
Therefore,
x = n(n+1)/2
 Direct Proof Method : Exercise

• Theorem: the product of two odd integers is odd

• Let x and y be two odd numbers
• X=(2n+1), y=(2m+1)
• Theorem: sumof two odd integers is even
 Indirect Proof Method

• Two types of indirect proof method

• Proof by Contrapositive
• Proof by Contradiction
 Proof by Contrapositive
Method
• Toprove a statement of form p → q , do following
• Form the contrapositive. In particular p and q
• Prove directly that, ¬q →¬p
 Proof by Contrapositive
Method
• Example: Prove by contrapositive: if x2 -6x +5 is even, then x is odd \

• Solution: suppose x is even, then we want to show that x2 -6x +5 is

odd.
Write x=2a. Then,
x2 -6x +5 = (2a)2 -6(2a) +5
= 4a2 -12a +5
= 2(2a2 -6a +2)+1
therefore, x2 -6x +5 is odd
 Proof by Contrapositive
Method : Exercise
• Example: Prove that n2 is odd, n is odd.
• Assume: P: n2 is odd, Q :n is odd

Proof by Contrapositive (¬Q → ¬P)

• ¬P: n2 is even
• ¬Q: n is even

Solve it mathematically
• n=2x--------n is even
• n2 = 4 x2 = 2(2 x2) =2a------- n2 is even
(¬Q → ¬P)
Hence P → Q (By logical equivalence)
 Proof by Contrapositive
Method : Exercise
• Example: If x,y belongs to integers such that x, y is odd then x and y
are odd
• Example: Prove that, P- if 3n+2 is odd, Q-n is odd, by method of
contrapositive
 Proof by Contradiction
Method
• p→ q
• We assume that q is false. (¬q is true)
• Contradiction: This can happen only when ¬q is false---implies q must
be true.
 Proof by Contradiction
Method
• Example:
• p:3n+2 is odd, q: n is odd
• p->q
• Assume q is false----(¬q) ----n is even
• (3n+2)=3(2k)+2=6k+2=2(3k+1)=2a-----(3n+2) is even