MULUNGUSHI UNIVERSITY

Pursing frontiers of Knowledge

CENTRE FOR ICT EDUCATION

ICT201 Discrete Mathematics
Lecture 2
 Contents
•Introduction to proposition Logic
•Logic connectives
•Compound propositions
•Fuzzy logic
•Logic and bit operations
 Introduction
•The rules of logic specify the meaning
of mathematical statements.
•Logic is the basis of all mathematical
reasoning, and of all automated
reasoning.
•To understand mathematics, we must
understand what makes up a correct
mathematical argument, that is, a
proof.
 Introduction
•Once we prove a mathematical statement
is true, we call it a theorem.
•The rule of mathematical reasoning (i.e
logic) are used in the design of computer
circuits, the construction of computer
programs, the verification of the
correctness of programs, and other
applications.
 Why logic?
• Logic about inference or argument

• Start from assumptions or axioms

• Make deductions according to rules of

reasoning
 Why logic?
• If I don’t buy a lottery ticket on Saturday I won’t win the
jackpot.
• If I win the lottery jackpot on Saturday then I must have
bought a ticket.
• If I don’t buy a lottery ticket on Saturday I won’t win the
jackpot. So, if I
buy a ticket I will win the jackpot.
• If it is raining then there are clouds in the sky. Today is
cloudy, so it must
be raining.
• If I don’t work on this course I won’t pass the exams. I’m
not doing a thing, I wonder what will happen?
 Why logic?
• Can formalize the rules of reasoning used
– symbolic logic
• Helps to clarify the process of reasoning
• Gives possibility of mechanizing reasoning
process
 Applications of Logic in Computer
Science
• Programming – statements like if...then
...else use Boolean expressions
• Computer Design – Logic gates used as
basis of all hardware design
• Program Specification – piece of
mathematics that describes precisely the
desired behaviour of a piece of software
 Applications of Logic in Computer
Science
• Program Verification – proving that a
program satisfies its specification
• Automated theorem proving – proving that
a mathematical theorem is the
consequence of a number of assumptions
• Data Bases – need to be able to structure
and efficiently execute queries
• Knowledge bases – need to be able to
make deductions from existing body of
facts languages in their own right
 Applications of Logic in Computer
Science
• Semantic Web searches – need to be able
to search for web content by knowing
something about the meaning of the
content, rather than just the syntax.
• Logic programming – can use particular
forms of logic as programming languages
in their own right
 Symbolic Logic
• Simplest form is concerned with
propositions
• Statements that can take value true or
false
▪ Blue is a colour
▪ 1+1=2
▪ 2 + 2 = 22
▪ All computer scientists have beards
 Symbolic Logic
•Can form compound propositions using
logical connectives (or operators)

•Today is Wednesday and it’s raining

•Either this is Chipata or I’m a Chief
•If it’s Thursday at 9 this must be ICT201

•Will introduce the full range of logical

connectives and study their properties
 Propositional Logic
•A proposition is a declarative sentence (that is,
a sentence that declares a fact) that is either
true or false, but not both
•Consider the following
[Link] is in the Copperbelt Province.
[Link] is in the Southern Province.
C.1 + 1 = 2.
D.2 + 2 = 3.
•Propositions A and C are true, whereas B and D
are false.
 Propositional Logic
•How about the following sentences.
1. What time is it?
2. Read this carefully.
3. x + 1= 2.
4. x + y= z.
•Sentences 1 and 2 are not propositions because
they are not declarative sentences.
•Sentences 3 and 4 are not propositions because
they are neither true nor false.
 Propositional Logic
•We use letters to denote propositional
variables (or statement variables), that is,
variables that represent propositions, just as
letters are used to denote numerical variables.
•The letters used for propositional variables are
p, q, r, s,. ....
•The truth value of a proposition is denoted by
T, if it is a true proposition and false, denoted by
F, if it is a false proposition.
•The area of logic that deals with propositions is
called the propositional calculus or propositional
The Logical Connectives
The Logical Connectives contd…
 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.
 Negation
• Q1. Find the negation of the proposition "Today
is Friday.“
Solution. "It is not the case that today is Friday.“ or
"Today is not Friday,“
• Q2. Find the negation of the proposition "At
least 10mm of rain fell today in Kabwe.“
Solution “Less than 10mm of rain fell today in
Kabwe”
 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
• Q3. Find the conjunction of the propositions
p and q where p is the proposition "Today is
Friday“ and q is the proposition "It is raining
today."
Solution: The conjunction of these propositions,
p ^ q , is the proposition "Today is Friday and it is
raining today."
•This proposition is true on rainy Fridays and is
false on any day that is not a Friday and on
Fridays when it does not rain.
 Truth table
•Truth table for negation of p
p ¬p
T F
F T
•Conjunction of p ^ q

p q p^q
T T T
T F F
F T F
F F F
 Disjunction
•Let p and q be propositions. The disjunction of
p and q, denoted by p v q, is the proposition "p
or q”
•The disjunction p v q is false when both p and q
are false and is true otherwise.
 Disjunction
• Q4. Find the disjunction of the propositions p
and q where p is the proposition "Today is
Friday“ and q is the proposition "It is raining
today."
Solution: The disjunction of these propositions,
p v q , is the proposition "Today is Friday or it is
raining today."
 Disjunction truth table
•Disjunction of p v q
p q pvq
T T T
T F T
F T T
F F F
 Exclusive or
•Let p and q be propositions. The exclusive or of p and
q, denoted by , is the proposition that is true
when exactly one of p and q is true and is false
otherwise.
•Truth table for exclusive or

p q p q
T T F
T F T
F T T
F F F
 Conditional Statements
•Let p and q be propositions. The conditional
statement p → q is the proposition "if p, then q.”
The conditional statement p → q is false when p
is true and q is false, and true otherwise.
•In the conditional statement p → q, p is called
the hypothesis (or antecedent or premise) and q
is called the conclusion (or consequence).
 Conditional Statements
•A useful way to understand the truth value of a
conditional statement is to think of an obligation
or a contract.
•For example, the pledge from Computer
Science student “If you allow me to register for
Bachelor of Computer Science then I will work
and pass all 2nd year courses”
 Conditional statement truth table
•Conditional statement of p → q
p q p→q
T T T
T F F
F T T
F F T

•Same as q if p; q when p; p only if q; q is

necessary for p; p is sufficient for q
 Conditional statement
• Q5. Let p be the statement “Chanda learns discrete
mathematics" and q the statement “Chanda will find
a good job.” Express the statement p → q as a
statement in English.
Solution 1. "If Chanda learns discrete mathematics. then
she will find a good job'“
Solution 2. “Chanda will find a good job when she learns
discrete mathematics.“
• Q6. What is the value of the variable x after the
statement “if 2 + 2 = 4 then x := x + 1” assume x = 0
before this statement is encountered?
 Example Conditional statement
• x > 3 implies x > 1
• where x is an integer variable. Surely this sentence is
universally true; i.e. it is true whatever integer value x
may have. Now let us give x the values 4,2,0 in turn

x x>3 x>1 p→q

4
2
0
 Converse, Contrapositive and
Inverse
•We can form some new conditional statements
starting with a conditional statement p → q.
•The proposition q → p is called the converse of p→ q.
•The contrapositive of p→ q is the proposition ¬q→¬p.
•The proposition ¬p→ ¬q is called the inverse of p→ q.
•These three conditional statements are formed from p
→ q, only the contrapositive always has the same truth
value as p → q.
 Converse, Contrapositive and
Inverse
•What are the contrapositive, the converse and the
inverse of the conditional statement "The home team
wins whenever it is raining”?
•Contrapositive of this conditional statement is "If the
home team does not win, then it is not raining.“
•The converse is "If the home team wins, then it is
raining."
•The inverse is "If it is not raining, then the home team
does not win.“
•Show that p → q ≡ ¬q → ¬p
 Biconditional
•Let p and q be propositions. The biconditional statement
p ↔ q is the proposition "p if and only if q."
•The biconditional statement p ↔ q is true when p and q
have the same truth values, and is false otherwise.

p q p↔q
T T T
T F F
F T F
F F T
 Biconditional
•Let p be the statement "You can take the flight" and let
q be the statement "You buy a ticket."
•Then p ↔ q is the statement "You can take the flight if
and only if you buy a ticket."
•This statement is true if p and q are either both true or
both false, that is, if you buy a ticket and can take the
flight or if you do not buy a ticket and you cannot take
the flight.
 Summary
Connectives Symbol
and ^
or v
not ¬
Exclusive or
if-then →
if-and-only-if ↔
 Compound propositions
•Order of precedence
Operator Precedence
¬ 1
^ 2
v 3
→ 4
↔ 5
 Compound propositions
•Construct the truth table of the compound
proposition (p v ¬q) → (p ^ q).
 Translating English statements
•Translate the following English statement into a logical
expression? "You can access the Internet from campus
only if you are a computer science student or you are
not a first year.”
•Let p, q, and r represent “You can access the Internet
from campus," "You are a computer science major,"
and "You are a first year," respectively
•Then the solution is p → (q v ¬r)
•Try this one "You cannot enter a disco (clubbing) if you
are male unless you are older than 16 years old."
 System Specifications
•Translating sentences in natural language (such as English) into
logical expressions is an essential part of specifying both
hardware and software systems.
•System and software engineers take requirements in natural
language and produce precise and unambiguous specifications
that can be used as the basis for system development.
•Express the specification "The automated reply cannot
be sent when the file system is full" using logical
connectives.
•Let p denote "The automated reply can be sent" and q
denote "The file system is full“ and ¬q "The automated
reply cannot be sent.”
•Solution is p → ¬q
 System Specifications
•System specifications should be consistent, that is, they
should not contain conflicting requirements that could be
used to derive a contradiction. Try this specification.
•"The diagnostic message is stored in the buffer or it is
retransmitted."
•"The diagnostic message is not stored in the buffer."
•"If the diagnostic message is stored in the buffer then it is
retransmitted.“
•Let p = diagnostic message is stored in the buffer or it is
retransmitted. And q = diagnostic message is retransmitted."
•Using the truth table you can see that this is possible when p
is false and q is true
 Boolean Searches
•Logical connectives are used extensively in searches of
large collections of information, such as indexes of Web
pages.
•Because these searches employ techniques from
propositional logic, they are called Boolean searches.
•The connective AND is used to match records that
contain both of two search terms,
•The connective OR is used to match one or both of
two search terms. and the
•The connective NOT (sometimes written as AND NOT)
is used to exclude a particular search term.
 Logic puzzles
•Smullyan posed many puzzles about an island that has
two kinds of inhabitants, knights, who always tell the
truth, and their opposites, knaves, who always lie.
•You encounter two people A and B. What are A and B
if A says "B is a knight" and B says "The two of us are
opposite types"?
•Let p and q be the statements that A is a knight and B
is a knight respectively, so that ¬p and ¬q are the
statements that A is a knave and B is a knave,
respectively.
•Solution is that both A and B are knaves
 Truth table
•Knights always tell the truth and knaves always
lie.
•You encounter two people A and B. What are A
and B if A says "B is a knight" and B says "The
two of us are opposite types“?
p (A) q (B) Opp. Conc. A Conc. B
T T F T F
T F T F F
F T T F T
F F F T T
 Logic and Bit Operations
•Computers represent information using bits. A
bit is a symbol with two possible values, namely,
0 (zero) and 1 (one).
•They are equivalent to true or false.
•Computer bit operations correspond to the
logical connectives.
 Logic and Bit Operations
•A bit string is a sequence of zero or more bits.
The length of this string is the number of bits in
the string. Eg 101010011 is a bit string of length
nine
•We can extend bit operations to bit strings.
•We define the bitwise OR, bitwise AND, and
bitwise XOR of two strings of the same length to
be the strings that have as their bits the OR,
AND, and XOR of the corresponding bits in the
two strings, respectively.
 Logic and Bit Operations
•Find the bitwise OR, bitwise AND and bitwise
XOR of the bit strings 01 1011 0110 and 11 0001
1101
•Solution
01 1011 0110
11 0001 1101
bitwise OR 11 1011 1111
bitwise AND 01 0001 0100
bitwise XOR 10 1010 1011
 Exercises
Q1. Which of these are propositions? What are
the truth values of those that are propositions?
a) Do not pass go.
b) What time is it?
c) There are no black flies in Kabwe.
d) 4+x=5.
e) The moon is made of green cheese.
f) 2n ≥ 100.
 Exercises
Q2. Let p and q be the propositions, p= You drive over 100 km per
hour, and q = You get a speeding ticket. Write these propositions
using p and q and logical connectives.
a) You do not drive over 100 km per hour.
b) You drive over 100 km per hour, but you do not get a speeding
ticket.
c) You will get a speeding ticket if you drive over 100km per hour.
d) If you do not drive over 100km per hour, then you will not get a
speeding ticket.
e) Driving over 100km per hour is sufficient for gelling a speeding
ticket.
f) You get a speeding ticket, but you do not drive over 100km per
hour.
g) Whenever you get a speeding ticket, you are driving over 100km
per hour.
 Exercises
Q3. Write each of these statement in the form "if p,
then q“ in English.
a) It snows whenever the wind blows from the
northeast.
b) The apple trees will bloom if it stays warm for a
week.
c) That the Zanaco win the championship implies that
they beat the Buffaloes.
d) It is necessary to walk 3 km to get to the Great North
Road from Administration Building.
e) If you drive more than 400 km you will need to buy
fuel
f) Moses will go swimming unless the water is too cold.
 Exercises
Q4. Construct a truth table for each of these
compound propositions.
a) p ^ ¬ p
b) p v ¬p
c) (p v ¬ q) →q
Q5. Find the bitwise OR, bitwise AND. and
bitwise XOR of each of these pairs of bit strings.
a) 101 1110 ; 010 0001
b) 1111 0000 ; 1010 1010
 Exercises
Q5. Each inhabitant of a remote village always tells the truth or always
lies. A villager will only give a "Yes" or "No“ response to a question a
tourist asks. Suppose you are a tourist visiting this area and come to a
junction where the road splits into two. One branch leads to the ruins
you want to visit; the other branch leads deep into the Jungle. A
villager is standing at the junction in the road. What one question can
you ask the villager to determine which branch to take?
Q6. A detective has interviewed four witnesses to a crime. From the
stories of the witnesses the detective has concluded that if the butler
is telling the truth then so is the cook: the cook and the gardener
cannot both be telling the truth; the gardener and the handyman are
not both lying; and if the handyman is telling the truth then the cook is
lying. For each of the four witnesses, can the detective determine
whether that person is telling the truth or lying? Explain your
reasoning.