Discrete Structures
Lecture#01
By
Dr. Inayat Khan
PhD (Web Engineering)
Assistant Professor of Computer Science
UET Mardan
What is Discrete Structures
• Discrete Structure concerns processes that consist of a sequence of
individual steps.
• Discrete Structure
• Is the branch of mathematics dealing with objects that can assume only
distinct, separated values.
Course Objective
• It will provide students of computer science with several topics and
ideas that will help them to develop and analyze algorithms
• To enable them to think about and solve problems in new ways
LOGIC
• Logic is the study of the principles and methods that distinguish
between a valid and an invalid argument.
• SIMPLE STATEMENT:
• A statement is a declarative sentence that is either true or false but not both.
• A statement is also referred to as a proposition
• EXAMPLES:
• a. 2+2 = 4,
• b. It is Sunday today
LOGIC
• If a proposition is true, we say that it has a truth value of "true”.
• If a proposition is false, its truth value is "false".
• The truth values “true” and “false” are, respectively, denoted by the
letters T and F.
Logic
• EXAMPLES:
• Propositions
• 1) Grass is green.
• 2) 4 + 2 = 6
• 3) 4 + 2 = 7
• 4) There are four fingers in a hand.
• Not Propositions
• 1) Close the door.
• 2) x is greater than 2.
• 3) He is very rich
Logic
• UNDERSTANDING STATEMENTS
1) x + 2 is positive. Not a statement
2) May I come in? Not a statement
3) Logic is interesting. A statement
4) It is hot today. A statement
5) -1 > 0 A statement
6) x + y = 12 Not a statement
Logic
• COMPOUND STATEMENT
• Simple statements could be used to build a compound statement.
• LOGICAL CONNECTIVES
• EXAMPLES:
1. “3 + 2 = 5” and “Lahore is a city in Pakistan”
2. “The grass is green” or “ It is hot today”
3. “Discrete Mathematics is not difficult to me”
• AND, OR, NOT are called LOGICAL CONNECTIVES
SYMBOLIC REPRESENTATION
• Statements are symbolically represented by letters such as p, q, r,...
• EXAMPLES:
• p = “Islamabad is the capital of Pakistan” q = “17 is divisible by 3”
Logic
• EXAMPLES
• p = “Islamabad is the capital of Pakistan”
• q = “17 is divisible by 3”
• p ∧ q = “Islamabad is the capital of Pakistan and 17 is divisible by 3”
• p ∨ q = “Islamabad is the capital of Pakistan or 17 is divisible by 3”
• ~p = “It is not the case that Islamabad is the capital of Pakistan”
• or simply “Islamabad is not the capital of Pakistan”
Translating From English To Symbols
• Let p = “It is hot”, and q = “ It is sunny”
SENTENCE SYMBOLIC FORM
1.It is not hot. ~p
2.It is hot and sunny. p ∧q
3.It is hot or sunny. p∨q
4.It is not hot but sunny. ~ p ∧q
5.It is neither hot nor sunny. ~p∧~q
Translating From English To Symbols
• EXAMPLE
• Let
• h = “Zia is healthy”
• w = “Zia is wealthy”
• s = “Zia is wise”
• Translate the compound statements to symbolic form:
1) Zia is healthy and wealthy but not wise.
(h ∧ w) ∧ (~ s)
2) Zia is not wealthy but he is healthy and wise.
~ w ∧ (h ∧ s)
3) Zia is neither healthy, wealthy nor wise.
~h∧~w∧~s
Translating From English To Symbols
• Let
• m = “Ali is good in Mathematics”
• c = “Ali is a Computer Science student”
• Translate the following statement forms into plain English:
1 ~c Ali is not a Computer Science student
2 C∨m Ali is a Computer Science student or good in Maths.
3 m∧~c Ali is good in Maths but not a Computer Science student
• A convenient method for analyzing a compound statement is to make
a truth table for it.
Truth Table
• A truth table specifies the truth value of a compound proposition for
all possible truth values of its constituent propositions.
• NEGATION (~):
• If p is a statement variable, then negation of p, “not p”, is denoted as “~p”
• It has opposite truth value from p i.e., if p is true, then ~ p is false;
• if p is false, then ~ p is true.
p ~p
T F
F T
CONJUNCTION (∧):
• If p and q are statements, then the conjunction of p and q is “p and
q”, denoted as “p ∧ q”.
• Remarks
• p ∧ q is true only when both p and q are true.
• If either p or q is false, or both are false, then p ∧ q is false.
CONJUNCTION (∧):
• TRUTH TABLE FOR p ∧ q
p q p∧q
T T T
T F F
F T F
F F F
DISJUNCTION (∨) or INCLUSIVE
OR
• If p & q are statements, then the disjunction of p and q is “p or q”,
denoted as “p ∨ q”.
• Remarks:
• p ∨ q is true when at least one of p or q is true.
• p ∨ q is false only when both p and q are false.
DISJUNCTION (∨) or INCLUSIVE
OR
• TRUTH TABLE FOR p ∨ q
p q p∨q
T T T
T F T
F T T
F F F
SUMMARY
1. What is a statement?
2. How a compound statement is formed.
3. Logical connectives (negation, conjunction, disjunction).
4. How to construct a truth table for a statement form.
Thank You
