BMAT205L_Module 1 1
Discrete Mathematics
➢ It is the study of mathematical structures that are fundamentally
discrete in nature and it does not require the notion of continuity.
➢ It is also called Decision Mathematics or Finite Mathematics.
• It is used in programming languages, software development,
cryptography, algorithms etc. Due to its application in Computer
Science, it has become popular in recent decades.
• Discrete Mathematics covers some important concepts such as Set
Theory, Logic, Permutation, Combination and Graph Theory.
BMAT205L_Module 1 2
Module 1: Mathematical Logic
Statements and Notation-Connectives - Tautologies-Equivalence -
Implications - Normal forms - The Theory of Inference for the
Statement Calculus - Predicate Calculus - Inference Theory of the
Predicate Calculus
BMAT205L_Module 1 3
Books for References
BMAT205L_Module 1 4
BMAT205L_Module 1 5
BMAT205L_Module 1 6
BMAT205L_Module 1 7
BMAT205L_Module 1 8
BMAT205L_Module 1 9
BMAT205L_Module 1 10
BMAT205L_Module 1 11
BMAT205L_Module 1 12
True
BMAT205L_Module 1 13
BMAT205L_Module 1 14
BMAT205L_Module 1 15
BMAT205L_Module 1 16
BMAT205L_Module 1 17
BMAT205L_Module 1 18
BMAT205L_Module 1 19
Problems for Practice
BMAT205L_Module 1 20
BMAT205L_Module 1 21
Contingency
A compound proposition that is neither a tautology nor a contradiction is called
a contingency.
BMAT205L_Module 1 22
Example:
𝑷 𝑸 𝑷∨𝑸 𝑷 ∨ ¬𝑷 𝑷 ∧ ¬𝑷
1 1 1 1 0
1 0 1 1 0
0 1 1 1 0
0 0 0 1 0
Contingency
Tautology
Contradiction
BMAT205L_Module 1 23
Valid, Satisfiable and Unsatisfiable
BMAT205L_Module 1 24
BMAT205L_Module 1 25
BMAT205L_Module 1 26
BMAT205L_Module 1 27
Logical Equivalence (𝑃 ≡ 𝑄 or 𝑃 ⇔ Q)
❖The two compound propositions 𝑃 and 𝑄 are called logically
equivalent if and only if the truth values of 𝑃 and 𝑄 are equal.
❖Equivalently, two compound propositions 𝑃 and 𝑄 are called
logically equivalent if 𝑃 ↔ 𝑄 is a tautology.
❖It is denoted by 𝑃 ≡ 𝑄 or 𝑃 ⇔ Q.
BMAT205L_Module 1 28
BMAT205L_Module 1 29
BMAT205L_Module 1 30
Negation
Law
BMAT205L_Module 1 31
BMAT205L_Module 1 32
1
BMAT205L_Module 1 33
2
BMAT205L_Module 1 34
3
BMAT205L_Module 1 35
(Solve using Truth tables and using logical laws)
BMAT205L_Module 1 36
BMAT205L_Module 1 37
Normal Form
1. The problem of determining, in a finite number of steps,
whether a given statement formula is tautology or a
contradiction or contingency is known as a decision problem.
2. The solution of the decision problem may not be simple in
general. Also the construction of truth tables may not be
practical, even with the aid of a computer.
3. Therefore consider other procedures known as reduction to
normal forms.
BMAT205L_Module 1 38
BMAT205L_Module 1 39
BMAT205L_Module 1 40
BMAT205L_Module 1 41
BMAT205L_Module 1 42
Minterms and Maxterms
1. Minterms or Boolean conjunctions of 𝑃 and 𝑄:
P∧Q
P ∧ ¬Q
¬P ∧ Q
¬P ∧ ¬Q
2. Maxterms or Boolean disjunctions of 𝑃 and 𝑄:
P∨Q
P ∨ ¬Q
¬P ∨ Q
¬P ∨ ¬Q
BMAT205L_Module 1 43
BMAT205L_Module 1 44
• Each minterm has the truth value 𝑻 for exactly one combination
of the truth values of the variables 𝑃 and 𝑄.
• If the truth table of any formula containing only the variables 𝑃
and 𝑄 is known, then one can easily obtain an equivalent formula
which consists of a disjunction of some of the minterms.
• Each maxterm has the truth value 𝑭 for exactly one combination
of the truth values of the variables 𝑃 and 𝑄.
• If the truth table of any formula containing only the variables 𝑃
and 𝑄 is known, then one can easily obtain an equivalent formula
which consists of a conjunction of some of the maxterms
BMAT205L_Module 1 45
Methods to find PDNF and PCNF
BMAT205L_Module 1 46
BMAT205L_Module 1 47
BMAT205L_Module 1 48
BMAT205L_Module 1 49
BMAT205L_Module 1 50
Note:
1. No.of truth value T appears in the statement formula is same as
the no.of minterms appears in its PDNF. Hence if all the
minterms appears in its PDNF then the given statement formula
is a tautology and is a valid formula.
2. No.of truth value F appears in the statement formula is same as
the no.of maxterms appears in its PCNF. Hence if all the
maxterms appears in its PCNF then the given statement formula
is a contradiction and is an unsatisfiable formula.
BMAT205L_Module 1 51
Problems for Practice:
BMAT205L_Module 1 52
BMAT205L_Module 1 53
Basic Terminologies
❖ Premise is a proposition on the basis of which we would able to
draw a conclusion.
➢ We can think of premise as an evidence or assumption.
Therefore, initially we assume something is true and on the
basis of that assumption we draw some conclusion.
❖ Conclusion is a proposition that is reached from the given set of
premises.
➢ We can think of it as the result of the assumptions that we
made in an argument.
If Premises then Conclusion
BMAT205L_Module 1 54
Argument – Valid and Invalid
❖ Argument is sequence of statements that ends with a conclusion or
it is a set of one(or more) premises and a conclusion.
❖ Valid Argument: An argument is said to be valid argument if and
only if it is not possible to make all premises true and a conclusion
false.
❖ Invalid Argument: An argument is said to be an invalid argument if
it is not a valid argument.
55
BMAT205L_Module 1
Valid Argument Invalid Argument
𝑝→𝑞 𝑝→𝑞
𝑝 𝑞
∴𝑞 ∴𝑝
or or
((𝑝 → 𝑞) ∧ 𝑝) → 𝑞 ((𝑝 → 𝑞) ∧ 𝑞) → 𝑝
BMAT205L_Module 1 56
Inference and Rules of Inference
❖ Inference is a conclusion(s) derived on the basis of the
evidence(s).
❖ Rules of Inference are the templates for constructing valid
arguments.
BMAT205L_Module 1 57
Types of Inference Rules
or (𝑝 ∧ 𝑞) → 𝑞
or 𝑞
BMAT205L_Module 1 58
𝑝→𝑞 𝑝 → 𝑞 ∧ ¬𝑞 → 𝑟 →𝑞∨𝑟 Resolution
¬𝑞 → 𝑟
∴𝑞∨𝑟
BMAT205L_Module 1 59
𝑷 𝑸 𝑷→𝑸 𝑷∧ 𝑷→𝑸 𝑷∧ 𝑷→𝑸 →𝑸
0 0 1 0 1
0 1 1 0 1
1 0 0 0 1
1 1 1 1 1
BMAT205L_Module 1 60
BMAT205L_Module 1 61
Direct and Indirect Proof
Step 1: Assume ¬𝑪 is True
Step 2: Arrive at a stage that a set of premises is inconsistent
(i.e.) 𝒑 ∧ ¬𝒑 or 𝒒 ∧ ¬𝒒 or 𝒓 ∧ ¬𝒓 is False
BMAT205L_Module 1 62
BMAT205L_Module 1 63
BMAT205L_Module 1 64
BMAT205L_Module 1 65
Direct and Indirect Proof
Step 1: Assume ¬𝑪 is True
Step 2: Arrive at a stage that a set of premises is inconsistent
(i.e.) 𝒑 ∧ ¬𝒑 or 𝒒 ∧ ¬𝒒 or 𝒓 ∧ ¬𝒓 is False
BMAT205L_Module 1 66
Indirect Proof
BMAT205L_Module 1 67
Example
BMAT205L_Module 1 68
BMAT205L_Module 1 69
Here, ¬(Conclusion) = ¬𝑟 leads to a contradiction.
Hence 𝑝 → 𝑞, q → 𝑟, ¬ BMAT205L_Module
𝑝 ∧ 𝑟 , 𝑝 ∨1 𝑟 ⟹ 𝑟 is valid. 70
Practice
BMAT205L_Module 1 71
BMAT205L_Module 1 72
BMAT205L_Module 1 73
BMAT205L_Module 1 74
BMAT205L_Module 1 75
BMAT205L_Module 1 76
BMAT205L_Module 1 77
Statement: “𝑥 is greater than 10”
What is the truth value of this
statement?
Is it True or False for all 𝑥 values?
Is it True or False for some 𝑥 values?
Is this a Proposition ?
If not, then how to make it as a
Proposition?
BMAT205L_Module 1 78
BMAT205L_Module 1 79
BMAT205L_Module 1 80
Predicate logic:
Predicate Logic is a logical extension of propositional logic. Also
known as First order logic.
Domain or Universe of discourse:
UOD or Domain of a predicate variable is the collection of all possible
values that the variable may take.
BMAT205L_Module 1 81
BMAT205L_Module 1 82
BMAT205L_Module 1 83
BMAT205L_Module 1 84
BMAT205L_Module 1 85
Universal Quantifiers
vs
Existential Quantifiers
BMAT205L_Module 1 86
BMAT205L_Module 1 87
BMAT205L_Module 1 88
BMAT205L_Module 1 89
Universal Quantifiers
{(-x)^2 = x^2 }
BMAT205L_Module 1 90
Existential Quantifiers
BMAT205L_Module 1 91
BMAT205L_Module 1 92
BMAT205L_Module 1 93
BMAT205L_Module 1 94
BMAT205L_Module 1 95
BMAT205L_Module 1 96
BMAT205L_Module 1 97
Valid Formulas and Equivalences
• Let 𝐴 and 𝐵 be any two predicate formulas defined over a
particular domain 𝐷. When each of the variables appearing in 𝐴
and 𝐵 is replaced by any element of 𝐷, if the resulting statements
have the same truth values, then 𝐴 and 𝐵 are said to be equivalent
to each other over 𝐷.
• It is denoted by 𝐴 ≡ 𝐵 or 𝐴 ⇔ 𝐵 over 𝐷
Eg: 𝑷(𝒙) → 𝑸(𝒙) ≡ ¬𝑷(𝒙) ∨ 𝑸(𝒙)
BMAT205L_Module 1 98
Predicate calculus from Statement calculus
Logically valid formulas in predicate calculus can be obtained from
tautologies of propositional calculus by replacing primary
propositions such as 𝑝, 𝑞, 𝑟 by propositional functions
𝑃 𝑥 , 𝑄 𝑥 , 𝑅(𝑥).
Eg: 𝒑 ∨ ¬𝒑 ≡ 𝑻
Now we replace 𝒑 by a propositional function ∀𝒙 𝑷(𝒙)
Therefore we have, ∀𝒙 𝑷(𝒙) ∨ ¬(∀𝒙 𝑷(𝒙)) ≡ 𝑻
BMAT205L_Module 1 99
Inference Theory of Predicate Calculus
• Three basic rules Rule P, Rule T and Rule CP of inference used
in statement calculus can also be used in predicate calculus.
• The indirect method can also be used in predicate calculus.
• We need some additional rules for predicate calculus such as
➢ Rule US
Used to eliminate quantifiers (∀ 𝑎𝑛𝑑 ∃)
➢ Rule ES
➢ Rule UG
Used to include quantifiers (∀ 𝑎𝑛𝑑 ∃)
➢ Rule EG
Note: Note:
• US stands for Universal Specification • UG stands for Universal Generalization
• ES stands for Existential Specification • EG1 stands for Existential Generalization
BMAT205L_Module 100
Rule US and Rule ES
Rule US: If ∀𝑥 𝑃(𝑥) is true, then we can conclude that 𝑃(𝑐) is true
where 𝑐 is an arbitrary element of the domain. This is also called as
universal instantiation.
Rule ES: If ∃𝑥 𝑃(𝑥) is true, then we can conclude that there is a
particular element 𝑐 in the domain for which 𝑃(𝑐) is true. This is
also called as existential instantiation.
BMAT205L_Module 1 101
Rule UG and Rule EG
Rule UG: If 𝑐 is an arbitrary element in the domain for which 𝑃(𝑐)
is true, then we can conclude that ∀𝑥 𝑃(𝑥) is true.
Rule EG: If there is a particular element 𝑐 in the domain for which
𝑃(𝑐) is true then we can conclude that ∃𝑥 𝑃(𝑥) is true.
BMAT205L_Module 1 102
BMAT205L_Module 1 103
Problem 1:
BMAT205L_Module 1 104
Problem 2:
BMAT205L_Module 1 105
Problems using Rules
BMAT205L_Module 1 106
BMAT205L_Module 1 107
BMAT205L_Module 1 108
Problems using Rules
Problem 2:
𝑃 𝑥 → 𝑄 𝑥 ≡ ¬𝑄 𝑥 → ¬𝑃 𝑥
Hypothetical 𝑃 𝑥 →𝑄 𝑥
𝑃(𝑥) → ¬𝑅(𝑥)
Syllogism 𝑄(𝑥) → ¬𝑅(𝑥)
BMAT205L_Module 1 109
Problem 3:
BMAT205L_Module 1 110
Solution:
(6)
BMAT205L_Module 1 111
Problem 4:
BMAT205L_Module 1 112
Practice Problems
BMAT205L_Module 1 113
Thank You
BMAT205L_Module 1 114
