Introduction

Lecture: Mr Morgan

Course Code: Comp1210

Course Title: Mathematics

for Computing

Credits: three

1
 Topics To Be Covered

✔ Propositions
✔ Connectives
✔ Truth Tables
✔ Logical Equivalence
✔ Tautology
✔ Contradiction
✔ Quantifiers
✔ Propositional Logic

2
 Logic
Logic = the study of correct reasoning
Use of logic
■ In mathematics:
to prove theorems
■ In computer science:
to prove that programs do what they are
supposed to do

3
 Propositions

Definition: A proposition is a statement or

sentence that is either true or false.
Examples:
■ “John is a programmer" is a proposition
■ “I wish I were wise” is not a proposition

4
 Propositions
Notations
■ Propositions will be denoted by lowercase
letters such as p, q and r
■ Truth values True will be denoted by T and
False by F
■ p: John is a student
will be used to define the proposition p to be
“John is a student”

5
 Connectives
If p and q are propositions, new compound
propositions can be formed by using
connectives
Most common connectives:
■ Conjunction AND. Symbol ^
■ Inclusive disjunction OR Symbol v
■ Exclusive disjunction ORSymbol v
■ Negation Symbol ~
■ Implication Symbol →
■ Double implication Symbol ↔
6
 Truth Tables
Definition: The truth table of a compound
proposition, p, made up of individual
propositions p1, p2,….,pn, lists all the
possible combinations of truth values for
p1,p2,….,pn, T denoting true and F
denoting false and for each such
combination lists the truth value of p.

7
Truth Table of Conjunction

Truth table of conjunction

p q p^q
T T T
T F F
F T F
F F F

p ^ q is true only when both p and q are true.

8
 Truth Table of Disjunction
❑ The truth table of (inclusive) disjunction
is
p q pvq
T T T
T F T
F T T
F F F

❑ p ∨ q is false only when both p and q

are false 9
 Exclusive disjunction
“Either p or q” (but not both), in symbols p ∨
q
p q pvq
T T F
T F T
F T T
F F F

❑ p ∨ q is true only when p is true and q is

false, or p is false and q is true.
10
 Negation
Negation of p: in symbols ~p

p ~p
T F

F T

~p is false when p is true, ~p is true when p is

false

11
Operator Precedence
In expressions involving some or all of the
operators ~, ^ and ∨ in the absence of
parentheses we first evaluate ~, then ^
then ∨

12
 Conditional propositions

Definition: If p and q are propositions, the

compound proposition
“If p then q”
is called a conditional proposition. p is called the
antecedent or hypothesis q is called the
consequent or conclusion

NOTATION: p→q
Example:
■ p: John is a programmer and q: Mary is a lawyer
■ p → q: If John is a programmer then Mary is a lawyer

13
 Truth table of p → q

p q p→q
T T T
T F F

F T T
F F T

❑ p → q is true when both p and q are true

or when p is false.
14
 Precedence again
In expressions involving the logical
operators ~, ^, ∨ and →, the conditional
operator is evaluated last.

15
 Double implication
The double implication “p if and only if q” is
defined in symbols as p ↔ q

p q p↔q
T T T
T F F
F T F
F F T

16
More compound statements

Let p, q, r be simple statements

We can form other compound statements,
such as
■ (p∨q)^r
■ p∨(q^r)
■ (~p)∨(~q)
■ (p∨q)^(~r)
■ and many others…

17
Example: truth table of (p∨q)^r
p q r (p ∨ q) ^ r
T T T T
T T F F
T F T T
T F F F
F T T T
F T F F
F F T F
F F F F

18
 Logical equivalence
❑ Definition:Two propositions are said to be
logically equivalent if their truth tables are
identical.
p q p→q ~p ∨ q

T T T T
T F F F
F T T T
F F T T

❑ Example: ~p ∨ q is logically equivalent to p → q

19
 Converse
The converse of p → q is q → p

p q p→q q→p
T T T T
T F F T
F T T F
F F T T

These two propositions

are not logically equivalent
20
 Contrapositive
Definition: The contrapositive is an alternative, logically
equivalent form of the conditional proposition
Example:
The contrapositive of p → q is ~q → ~p.

p q p→q ~q → ~p
T T T T
T F F F
F T T T
F F T T
They are logically equivalent.
21
 Double implication
The double implication “p if and only if q” is
defined in symbols as p ↔ q

p q p↔q (p → q) ^ (q → p)
T T T T
T F F F
F T F F
F F T T
p ↔ q is logically equivalent to (p → q)^(q → p)

22
 Tautology
Definition: A proposition is a tautology if its truth
table contains only true values for every case
Example: p → p v q

p q p→pvq
T T T
T F T
F T T
F F T 23
 Contradiction
Definition: A proposition is a Contradiction if its
truth table contains only false values for every
case
Example: p ^ ~p

p p ^ (~p)
T F
F F

24
De Morgan’s laws for logic

The following pairs of propositions are

logically equivalent:

■ ~ (p ∨ q) and (~p)^(~q)
■ ~ (p ^ q) and (~p) ∨ (~q)

25
 Quantifiers

A propositional function P(x) is a statement

involving a variable x
For example:
■ P(x): 2x is an even integer
x is an element of a set D
■ For example, x is an element of the set of integers
D is called the domain of P(x)

26
 Domain of a propositional
function
In the propositional function
P(x): “2x is an even integer”,
the domain D of P(x) must be defined, for
instance D = {integers}.
D is the set where the x's come from.

27
For every and for some
Most statements in mathematics and
computer science use terms such as for
every and for some.
For example:
■ For every triangle T, the sum of the angles of T
is 180 degrees.
■ For every integer n, n is less than p, for some
prime number p.

28
 Universal quantifier

One can write P(x) for every x in a domain D

■ In symbols: ∀x P(x)
∀ is called the universal quantifier

29
Truth of as propositional function
The statement ∀x P(x) is
■ True if P(x) is true for every x ∈ D
■ False if P(x) is not true for some x ∈ D
Example: Let P(n) be the propositional
function n2 + 2n is an odd integer
∀n ∈ D = {all integers}
P(n) is true only when n is an odd integer,
false if n is an even integer.

30
 Existential quantifier

For some x ∈ D, P(x) is true if there exists

an element x in the domain D for which P(x) is
true. In symbols: ∃x, P(x)

The symbol ∃ is called the existential

quantifier.

31
 Counterexample
The universal statement ∀x P(x) is false if
∃x ∈ D such that P(x) is false.

The value x that makes P(x) false is called a

counterexample to the statement ∀x P(x).
■ Example: P(x) = "every x is a prime number", for
every integer x.
■ But if x = 4 (an integer) this x is not a prime
number. Then 4 is a counterexample to P(x)
being true.

32
 Generalized De Morgan’s
laws for Logic
If P(x) is a propositional function, then each
pair of propositions in a) and b) below have
the same truth values:
a) ~(∀x P(x)) and ∃x: ~P(x)
"It is not true that for every x, P(x) holds" is equivalent
to "There exists an x for which P(x) is not true"
b) ~(∃x P(x)) and ∀x: ~P(x)
"It is not true that there exists an x for which P(x) is
true" is equivalent to "For all x, P(x) is not true"

33
Summary of propositional logic

In order to prove the In order to prove the

universally quantified universally quantified
statement ∀x P(x) is statement ∀x P(x) is
true false
■ It is not enough to ■ It is enough to exhibit
show P(x) true for some x ∈ D for which
some x ∈ D P(x) is false
■ You must show P(x) is ■ This x is called the
true for every x ∈ D counterexample to
the statement ∀x P(x)
is true
34
? 35