Propositional Logic

Logic and Problem solving

MA4001
Lecture 1

Introduction and Overview of Module

Introduction to Propositional Logic
Warm Welcome to you all ….

Welcome
to Islington
College !!!
Congratulations for choosing the best IT college in
Nepal !!!
Agenda
• Module Introduction
Your Module Leader
Module Objective
Module Assessments and Syllabus Summary
Recommended booklist
• Week 1 Lecture Coverage
– Introduction to logic
– Proposition and compound Proposition
– Truth tables
Module Leader

Ashok Dhungana,
MSc. IT, TU, Nepal
Sr. Lecturer , Islington College.

ashok.dhungana@islingtoncollege.edu.np
Islington.ashok@gmail.com
01- 4412929
Your Lecturer
Mr. Ashok Dhungana Mr. Prakash Adhikari
Masters in Computer Science (Nepal) Masters in Computer Science (France)
ashok.dhungana@islingtoncollege.edu.np prakash.adhikari@islingtoncollege.edu.np
Your Tutor
Mr. Indra Dhakal
Masters in Applied Mathematics (Germany)
indra.dhakal@islingtoncollege.edu.np

•
•
•
Your Tutor
Mr. Nadil Paudel
M.A (Mathematics)
Tribhuvan University Nepal
nadil.paudel@islingtoncollege.edu.np
Introduction to the Module
• Overview of Module
- What can you expect?
• Learning Objectives
- How will you benefit?
• Learning Strategy
- How will you learn?
• Assessment Overview
- How you will be tested?
Overview of Module
• Logic and Problem solving
Aim:
This module seeks to consolidate and improve student's

mathematical knowledge, skills and concepts through practical,

analytical, problem Solving applications and through integration with other
modules. This module introduces, and in some cases reviews, the

mathematical foundations of Computer science.

Overview of Module
Syllabus :
 Propositional logic

 Sets ,Relations and Functions

 Puzzles: developing logical reasoning ,introducing systematic approach to solving puzzles, developing
appropriate strategies to solve puzzles.

 Algorithms : Understanding how problems can be solved systematically, plan their solutions and write
them in the form of algorithms.

 Permutation ,combination and Probability

 Linear Programming :Math of finance and Break-even analysis using excel as tool.
Learning Objectives

Computer
Programming
Hardware

Computer graphics
Databases
Design Logic and Problem solving
Learning Strategy
• Taught over 2 semester (30 weeks )

• Each week consists of 1 Lecture (1.5 Hours) , 1 workshop (2 hours), Q&A

session (1.5 hours) and discussion (2 hours).
• Lecture: Learn how to acquire different mathematical skills
• Workshop: Review and practice mathematical problems through in-class
assignments to acquire them.
• Discussion and Q &A ( For needy students only)
Module Assessment
Summary
Assessments:
 Two Class tests: (50% of total module marks)
Week 8(25%) and Week 22(25%)
1.15 hours closed book class test.

 Group Course Work: (50% of total module marks)

Work sheet consisting of selected exercises (Week 25)

MUST “PASS” ALL THREE ASSESSMENTS TO PASS THE

MODULE AND ACHIEVE AT LEAST 40% OF MARKS IN
AGGREGATE.
Assessment Details
Module Grading Standards in the UK

Range of Marks Grade Remarks

70 - 100 A Excellent: outstanding performance with only minor errors

60 - 69 B Very Good: above the average standard but with some errors

50 - 59 C Good: generally sound work with a number of notable errors

43 - 49 D Satisfactory: fair but with significant shortcomings

40 - 42 E Sufficient: performance meets the minimum criteria
Fail: performance does not meet the minimum criteria and
0 - 39 F
considerable further work is required
Recommended Reference
books

1. Maureen Sprankle(2008), Problem Solving and

Programming Concepts ,Prentice Hall.

2. Rod Haggarty(2006), Discrete Mathematics for

Computing, Addison Wesley .
Supplementary Reference
books

1. P. Grossman, Discrete Mathematics for Computing (2nd

edition), Macmillan, 2002.

2. A. Simpson, Discrete Mathematics by Examples, McGraw Hill,

2002.
Learning Strategy

Attendance for all classes is

important!
• Mathematics cannot be learnt by memorizing. It is learnt
through constant practice.
• We want to provide you the environment to practice and
improve quickly.
Google Classroom Code…

The Google classroom code for Logic and Problem-solving

module is

l336nkz
Please feel free to visit IT Department if you have any problems
with Google classroom.
Any Questions?
Let’s get started with Lecture 1

An Introduction to Propositional logic

 But First… Lets see some
examples of why Mathematics is
Important!

What can we learn from these 2

videos?
Why Mathematics is Important ?
When not knowing math can cost you $ 15000
Agenda
Week 1 lecture coverage
• Logic and proposition
• Logical Connectives
• Truth tables
Logic
- Study of principles of reasoning.
- Example:
Jack is a human.
All humans have brain.
Therefore, Jack has a brain.
Hence, logical reasoning concludes based on certain statements.
The fundamental objects in logic are Propositions
Proposition
Proposition is a statement that is either true or false.
It is a building block of logic.
For example ->
1. Kathmandu is a city. (True)
2. Java is a programming language. (True)
3. Paper is made of glass. (False)

A proposition is either true or false but not both

True(T) or False(F) is called the truth value of the proposition
Proposition (Continued)
Sentences that are “Questions”, “Commands” and “Opinions”
are not valid propositions because they will/may not have a true or
false value.
Examples ->
1. How old are you?
2. Go to School.
3. He is tall.
Proposition (Continued)

Some examples of valid propositions

1. Kathmandu is the capital of Nepal.
2. There are 7 days in a week.
3. Isaac Newton was born in 1642.
4. 6 is greater than 8.
Proposition Notation:
Proposition is represented by lower case letters for example: p, q, r, ……,
to denote propositional variables.

Example ->
p = Java is an object-oriented language.
Meaning,
p represents the proposition “Java is an object-oriented language”
Primitive and Compound
Propositions:
p: Kathmandu is in either Nepal or UK.
This proposition is made up of two simpler propositions.

q: Kathmandu is in Nepal.
r: Kathmandu is in UK.

Joined together by the word “or ”

Primitive and Compound Propositions:

Propositions q and r cannot themselves be broken down into simpler ones.
Such propositions are called primitive.


In the above example “p” is combination of two propositions called
compound proposition.

In the above example, compound proposition is connected by “or” which
is called connective.
Compound Propositions:
A compound proposition is an expression
P(p, q, r, ...), which consists of propositional variables p, q, r, ... joined
together by the logical connectives ∧, V and ¬.

The propositional variables p, q, ... are sometimes called the arguments of

P.
Any Questions?
Operations on Propositions:
Main operations on propositions
are:
1) Conjunction/ AND
2) Disjunction/ OR and
3) Negation/ NOT/ Complement
4) Conditional
5) Bi-conditional
Conjunction:(AND)
Conjunction of two propositions:
Let p and q be given propositions.

The proposition “p and q” is called the conjunction of the given propositions.

It is written p ∧ q and read as “p and q”.
p ∧ q is true if both propositions p and q are true, otherwise p ∧ q is
false.
Conjunction (Contd.):
Example ->

p: Kathmandu is the capital of Nepal.

q: Delhi is the capital of India.
(p and q) : Kathmandu is the capital of Nepal and Delhi is the capital of
India.
p ∧ q is called the conjunction of two propositions.
The word “and” which links the two propositions is called a logical
connective.
The above compound proposition is true .
Disjunction: (OR)
Disjunction of two Propositions
Let p and q be given propositions.
The proposition “p or q” is called the disjunction of the given propositions.
It is written p ∨ q and read “p or q”.

p ∨ q is true if either p is true or q is true or both p and q are true,

otherwise p ∨ q is false.
Disjunction (Continued):
Example ->
p: Kathmandu is the capital of Nepal.
q: Delhi is the capital of China.

p or q: Kathmandu is the capital of Nepal or Delhi is the capital of China.

p ∨ q is called the disjunction of the two propositions p and q.
The above compound proposition is true .
Negation: (NOT)
Let p be any proposition.
The proposition “not p” or “it is not true that p” is called the negation
of p.
It is written ¬ p and read as “not p”.

Example ->
p: Kathmandu is the capital of Nepal.
¬ p: Kathmandu is not the capital of Nepal.
Here p is true but ¬ p is false
Examples: Its your turn..
Consider the propositions : p, q ,r and s
p is F, q is T, r is T and s is F. Using the definitions of ∧, ∨ and ¬. Find the truth
value for the following:
1. p ∧ ¬q is ?
2. q V ¬r is ?
3. ¬s V q is ?
Answers:
1.F
2.T
3.T
Use of Brackets:
When there are more than one logical connectives, their operation can
be determined by using braces.
For example:
(p ∨ q) ∧ r means first evaluate w = (p ∨ q) and then evaluate w ∧
r.
Use of Brackets Example:

Let ,
p: Kathmandu is the capital of Nepal. T
q: Delhi is the capital of China. F
r: Tokyo is the capital of Pakistan. F

Then (p ∨ q) ∧ r is false but p ∨ (q ∧ r) is true .

Use of Brackets Rules:
To minimize the number of brackets in expressions we will adopt the
following order of precedence in which connectives are applied.
1. Apply connectives within brackets first.
2. The ¬ connective next.
3. “and” and “or”.
Using this convention ¬ p ∧ q will mean (¬ p) ∧ q rather than ¬ (p ∧
q)
Any Questions?
Truth Tables:

Truth Tables represents the truth or falsity of logical statements.
Example:

p ¬p
T F
F T
The above is the truth table for negation.
Truth Tables (Continued):
Similarly,
-conjunction:(p
Truth table for ∧ q)
p q p∧q
T T T
T F F
F T F
F F F
Truth Tables (Contd.):
Similarly,
-disjunction:
Truth table for
(p  q)
p q pq
T T T
T F T
F T T
F F F
Truth Tables (Contd.):
Note:
1. Truth table provides an equivalent definition for the propositions ¬p, p ∧ q,
and p ∨ q.
2. The truth table for a proposition with n atomic propositions will have 2n
rows.
Example ->
If we have two propositions, p and q, then there are 22 = 4 number of rows.
Truth Tables (Contd.):Try it…
Example: Draw the truth table for p ∧ (q ∨ r)
p q r q∨r p ∧ (q ∨ r)
T T T T T
T T F T T
T F T T T
T F F F F
F T T T F
F T F T F
F F T T F
F F F F F
Any Questions?
Exercises: Its your Turn….

1. Which of the following are propositions?

a. How tall are you?
b. 2+8=11
c. x+3=4
d. Come here.
e. Mercury is the closest planet to earth.
f. x2 – 16 = 0 has two solutions.
Exercises: Its your turn…
2. Assume that p represents the statement “ Hari is happy” and q
represents the statement “Ram is in pain”. Write natural
language statements (English sentences) for each of the
following propositions:
a. ¬ p b. p ∧ q c. p ∨ ¬ q

d. p ∨ q e. q ∨ ¬ p
Exercises: Its Your Turn…
3. Write down the truth table for
a. p ∧ (¬q)
b. (¬p) ∧ (¬q)
c. ¬ (p ∧ q)
d. p ∧ (q ∨ r)
e. (p ∧ q) ∨ r
f. ¬ p ∧ q
g. p ∧ (false ∧ q)
Any Questions?
Summary: Week 1 Lecture

• Logic and proposition

• Logical Connectives
• Truth tables
What to Expect: Week 1 Workshop

•Review and practice Logic problems through in-class

assignments to actually acquire them.
• Practice problems to know how Propositional logic can be useful
in solving various mathematical problems.
Thank you