CSE181

Discrete Mathematics
Lecture: 1

Md. Asiful Islam Miah

1
Lecture Outline
1.1 Propositional Logic
• Logic
• Propositional Logic
• Propositions
• Propositional Variables
• Compound Propositions
• Logical Operators
• Truth Value & Truth Table
• Truth Tables of Compound Propositions (next class)
• Conditional Statements (next class)
• Logic and Bit Operations (next class)
2
Objectives and Outcomes
• Objectives: To understand the importance of logic in mathematical reasoning, to
understand proposition and propositional logic, symbol and usage of different types
of logical operators.
• Outcomes: Students are expected to be able to apply logical operators and
analyze logical propositions via truth tables, be able to construct a truth table for a
given compound proposition.

3
4
5
6
Key Terms
• Logic: Logic is the discipline that deals with the methods of reasoning.
• Logic is the basis of all mathematical reasoning
• The rules of logic specify the meaning of mathematical statements

• Propositional Logic: The area of logic that deals with propositions is

called the propositional logic.

7
Key Terms
▪ Proposition: A proposition is a declarative statement that’s either TRUE or
FALSE, but not both.
▪ Assigned one of the two distinct values, True and False or T and F.
▪ Denoted by p, q, r.
▪ Statements that are not propositions include
• Questions
• Commands

8
Key Terms
▪ Propositional variable: A variable that represents a proposition. The
conventional letters used for propositional variables are p, q, r, s, t,..
▪ Compound proposition: A proposition constructed by combining two or
more propositions using logical operators (AKA : logical connectives)
▪ Logical Operators: Operators used to combine propositions
▪ Truth Value: The truth value of a proposition is true, denoted by T, if it is a
true statement and false, denoted by F, if it is a false statement. Truth Value
==> Either True or False
▪ Truth Table: A table displaying the truth values of propositions.

9
 10

Proposition: Examples
Propositions:
● The integer 20 is a Prime.
● Dhaka is the capital city of Bangladesh

Not Propositions:
● What is your name ?
● Solve the problem.
● Is Karim a good boy?
 11

Proposition: Examples
Proposition Not Proposition

3 + 2 = 32 Bring me coffee!

3+2=5 3+2

CSE 181 is Karim’s favorite class. CSE 181 is his favorite class.

Every cow has four legs. Do you like Cake?

 12

Logical Operators
• Logical Operators ==> unary, binary
• Unary:
• Negation
• Binary
• Conjunction
• Disjunction
• Exclusive OR
• Conditional/Implication
• Bi-conditional
Logical Operators: Symbols & Usage
Operator Symbol Usage
Negation ¬ NOT
Conjunction ∧ AND
Disjunction ∨ OR
Exclusive or ⊕ XOR
Conditional → if, then
Bi-conditional ↔ iff
13
Propositional Logic : Negation
• Let p be a proposition. The negation of p, denoted
by ¬p , is the statement “It is not the case that p.”
• The proposition ¬p is read “not p”
• The truth value of the negation of p, ¬p, is the
opposite of the truth value of p.

14
Propositional Logic : Negation
▪ Negation just turns a false proposition to true and the opposite for a
true proposition.
• Example1: p: I am going to town.
¬ p: I am not going to town. ; or,
It is not the case that I am going to town.
• Example2: p : “23 = 15 +7”
p happens to be false, so ¬ p is true.
• Example3: p: 9 is divisible by 3.
¬ p: 9 is not divisible by 3.; or,
It is not the case that 9 is divisible by 3.
15
Proposition

¬ (¬ p) is logically equivalent to p .
16
Compound Proposition
A proposition constructed by combining two or more propositions using
logical operators (AKA : logical connectives)

● Conjunction
● Disjunction
● Exclusive Disjunction

17
Conjunction
• Let p and q be propositions. The conjunction of p and q, denoted by p ∧ q,
is the proposition “p and q.”
• The conjunction p ∧ q is true when both p and q are true and is false
otherwise.
• Conjunction corresponds to English “AND”.

• Example: p : The boy prepare his lessons regularly.

q : The boy helps his parents everyday.
p ∧ q : The boy prepare his lessons regularly and helps his parents
everyday.
• Another Example: Lina is brilliant and helpful.
18
Truth Table for Conjunction

19
Conjunction: Another Example
• Example: p : ‘I am going to town’
q : ‘It is going to rain’

p ∧ q : ‘I am going to town and it is going to rain.’

• Note: Both p and q must be true to p ∧ q be true

20
Disjunction
• Let p and q be propositions.
• The disjunction of p and q, denoted by p ∨ q, is the proposition “p or q.”
• The disjunction p ∨ q is false when both p and q are false and is true
otherwise.
• Disjunction is true when at least one of the components is true.
• Disjunction corresponds to English “OR”.
• Example: p : You can take physics this semester.
q : You can take chemistry this semester.
p ∨ q : You can take physics or chemistry this semester.
• Another Example: Abdullah is brave OR intelligent.

21
Truth Table for Disjunction

22
 Examples of Conjunction & Disjunction
Let,
p:5<9
q : 9 < 7.
Construct the propositions p ∧ q and p ∨ q.
Solution:
▪ The conjunction of the propositions p and q is the proposition
p ∧ q : 5 < 9 and 9 < 7
▪ The disjunction of the propositions p and q is the proposition
p ∨ q : 5 < 9 or 9 < 7

Question: What are the truth values of p ∧ q and p ∨ q?

23
Exclusive Disjunction
• Let p and q be propositions.
• The exclusive or of p and q, denoted by p ⊕ q, and read “p or exclusive q“ is
the proposition that is true when exactly one of p and q is true and is false
otherwise.

24
Truth Table of Exclusive Disjunction

25
Exclusive Disjunction: Example
• Example: p : You can take tea.
q : You can take coffee.
p ⊕ q : You can take tea or coffee, but not both.

26
27
Thank You

28