Horus University in Egypt

(HUE)
Faculty of Artificial
Intelligence and Information
CS 104 Discrete Structure
Level 1
The Foundations: Logic and Proofs
 Text Book:
Kenneth H. Rosen, “Discrete mathematics and its
applications”, 8th_ed (2019)
Chapter1 The Foundations: Logic and Proofs
Topics
 Logic
Proposition logic
 1.1 - Propositional Logic
What is logic?
The branch of philosophy concerned with
analysing the patterns of reasoning by
which a conclusion is drawn from a set of
premises, without reference to meaning or
context
(Collins English Dictionary)
Digital Logic
 Propositional logic
• Simple types of statements, called
propositions, are treated as atomic
building blocks for more complex
statements
1) Alexandria is a port or a holiday resort.
2) Alexandria is not a port.
Therefore, Alexandria is a holiday resort
 Basic connectives and truth tables

statements (propositions): declarative sentences that are

either true or false--but not both.
Eg. Ahmed Hassan wrote Gone with the Wind.

2+3=5.

not statements:
What a beautiful morning!
Get up and do your exercises.
 Proposition
A proposition is a declarative sentence
(that is, a sentence that declares a fact) that
is either true or false, but not both.
Examples: 2 + 2 = 4 True
3 x 3 = 8 False
787009911 is a prime
Today is Tuesday.

Non- x+y>0
examples:
x2+y2=z2
They are true for some values of x and y
but are false for some other values of x and y.
 Proposition

Consider the following

sentences.

1. What time is it?

2. Read this carefully.
3. x + 1 = 2.
4. x + y = z.
 Proposition

Consider the following

sentences.

1. What time is it?

2. Read this carefully.
3. x + 1 = 2.
4. x + y =1 z.and 2 are not propositions
Sentences
because they are not declarative
sentences.
Sentences 3 and 4 are not propositions
because they are neither true nor false.
 Propositional connectives
• Propositional logic has four connectives

Name Read as Symbol

negation ‘not’ 
conjunction ‘and’ 
disjunction ‘or’ 
implication ‘if…then…’ 
 Logical Operators
• About a dozen logical operators
– Similar to algebraic operators + * - /
• We use letters to denote propositional
variables (or sentential variables)
p, q, r, s,…
• In the following examples,
p = “Today is Friday”
q = “Today is my birthday”
 Logical operators: Not

• A “not” operation switches (negates) the

truth value
• Symbol:  or ~ p p
 p = “Today is not Friday” T F
F T
 Logical operators: Not
Find the negation of the proposition
•“Michael’s PC runs Linux” p p
Solution:
T F
“Michael’s PC does not run Linux.” F T
•“Vandana’s smartphone has at least 32 GB of memory”
Solution:
“Vandana’s smartphone does not have at least 32 GB of
memory”
 Logical operators: And

• An “and” operation is true if both

operands are true p q pq

• Symbol:  T T T
T F F
p = “Today is Friday “
F T F
q = “today is my birthday“
F F F
• pq = “Today is Friday and
today is my birthday”
 Logical operators: OR

• An “or” operation is true if either operands are true

p q pq
• Symbol: 
T T T
p = “Today is Friday “
T F T
q = “today is my birthday“ F T T
• pq = “Today is Friday or F F F

today is my birthday (or possibly both)”

 Logical operators: XOR

• An “XOR” operation is true if one of p and q is true

• Symbol:
p = “Today is Friday “
q = “today is my birthday“
Logical operators: Conditional

p q pq
T T T
T F F
F T T
F F T
 Logical operators: Conditional
• A conditional means “if p then q”
• Symbol: 
• pq = “If today is
Friday, then today p q pq

is my birthday” T T T
T F F
F T T
F F T

• p→q=¬pq
 Logical operators: Bi-conditional

• A bi-conditional means “p if and only if q”

• Symbol:  p q pq
• Alternatively, it means T T T
“(if p then q) and T F F
(if q then p)” F T F
• Note that a bi-conditional F F T
has the opposite truth values
of the exclusive or XOR
 Logical operators: Bi-conditional

EXAMPLE
p = “You can take the flight,”
q = “You buy a ticket.”
Then p ↔ q is the statement

Solution
“You can take the flight if and only if you buy a ticket.”
 Boolean operators summary
not not and or xor conditional Bi-conditional

p q p q pq pq pq pq pq

T T F F T T F T T

T F F T F T T F F

F T T F F T T T F

F F T T F F F T T

• Learn what they mean, don’t just memorize

the table!
 Precedence of operators
• Just as in algebra, operators have
precedence
4+3*2 = 4+(3*2), not (4+3)*2
• Precedence order (from highest to lowest):
¬→↔
–The first three are the most important
• This means that p  q  ¬r → s ↔ t
yields: (p  (q  (¬r)) → s) ↔ (t)
• Not is always performed before any other
operation
Precedence of operators
 Precedence of operators
Example
s: Aya goes out for a walk.
t: The moon is out.
u: It is snowing.

( t   u)  s : If the moon is out and it is not snowing, then

Aya goes out for a walk.

If it is snowing and the moon is not out, then Aya

will not go out for a walk. (u  t )  s
 Logic and Bit Operations
A bit is a symbol with two possible
values, namely, 0 (zero) and 1 (one).
 Translating English Sentences
p = “It is below freezing”
q = “It is snowing”

pq
• It is below freezing and it is snowing p¬q
• It is below freezing but not snowing ¬p¬q
• It is not below freezing and it is not snowing pq
• It is either snowing or below freezing (or both) p→q
• ((pq)¬(pq))(p→
If it is below freezing, (then) it is also snowing
• It is either below freezing or it is snowing, ¬q)
but it is not snowing if it is below freezing
• That it is below freezing is necessary and p↔q
sufficient for it to be snowing
 Exercises
 Which of these sentences are propositions? What
are the truth values of those that are
propositions?
a) Boston is the capital of Massachusetts. Yes, T
b) Miami is the capital of Florida. Yes, F
c) 2 + 3 = 5. Yes, T
d) 5 + 7 = 10. Yes, F
e) x + 2 = 11. No
f ) Answer this question. No

01/27/25
 Exercises
 What is the negation of each of these
propositions?
a) Linda is younger than Sanjay.
Linda is not younger than Sanjay

b) Mei makes more money than Isabella.

Mei does not make more money than
Isabella

c) Moshe is taller than Monica.

Moshe is not taller than Monica

d) Abby is richer than Ricardo.

Abby is not richer than Ricardo
01/27/25
 Exercises

 Determine whether each of these

conditional statements is true or
false.
a) If 1 + 1 = 2, then 2 + 2 = 5. F
b) If 1 + 1 = 3, then 2 + 2 = 4. T
c) If 1 + 1 = 3, then 2 + 2 = 5. T
d) If monkeys can fly, then 1 + 1 = 3.
T
01/27/25
 Exercises
2 n
 How many rows appear in a truth table
for each of these compound
propositions?
a) p → .p 2
b) (p ∨ .r) ∧ (q ∨ .s) 16
c) q ∨ p ∨ .s ∨ .r ∨ .t ∨ u 64
d) (p ∧ r ∧ t) ↔ (q ∧ t) 16]

01/27/25
 Exercises
 Construct a truth table for each of these
compound propositions.
a)

b)

c)

01/27/25
 Exercises
 Construct a truth table for each of these
compound propositions.
d)

e)

01/27/25
 Exercises
 Construct a truth table for each of these
compound propositions.
f) (p → q) → (q → p)

01/27/25
 Exercises
 Construct a truth table for each of these compound

a) (p ∨ q) → (p ⊕ q) b) (p ⊕ q) → (p ∧ q)
propositions.

b) (p ∨ q) ⊕ (p ∧ q) d) (p ↔ q) ⊕ (.p ↔ q)
c ) (p ⊕ q) → (p ⊕ .q)

01/27/25
 Exercises
 Construct a truth table for each of these compound
propositions.

01/27/25
 Exercises
Construct a truth table for each of these compound
propositions. a)
b)
c) (p → q) ∨
d) (p → q) ∧
e) (p ↔ q) ∨
f) ↔ (p ↔ q)

01/27/25
 Exercises
Construct a truth table
for (p ↔ q) ↔ (r ↔ s).

01/27/25
 1.2 Applications of Propositional
Logic Logic Circuits
 A logic circuit (or digital circuit) receives input
signals p , p ,…, p , each a bit [either 0 (off) or 1
1 2 n

(on)], and produces output signals s , s ,…, s , each

1 2 n

a bit.
 Propositional logic can be applied to the design of
computer hardware
 Complicated digital circuits can be constructed from three
basic circuits, called gates,
 1.2 Applications of Propositional
Logic

Example
Determine the output for the combinatorial circuit
in Figure
 1.2 Applications of Propositional
Logic

Answer
 1.2 Applications of Propositional
Example Logic
Build a digital circuit that produces the output

when given input bits p, q, and r.

Answer
 1.2 Applications of Propositional
Logic
Find the output of each of these combinatorial
circuits
 1.2 Applications of Propositional
Logic
Find the output of each of these combinatorial
circuits
 1.2 Applications of Propositional
Logic
Construct a combinatorial circuit using inverters, OR gates,
and AND gates that produces the output
from input bits p, q, and r.
 1.3 Propositional Equivalences
A compound proposition that is always true, no
matter what the truth values of the propositional
variables that occur in it, is called a tautology.
A compound proposition that is always false is called
a contradiction.
A compound proposition that is neither a tautology
nor a contradiction is called a contingency.
 1.3 Propositional Equivalences

example of tautologies

example of contradiction
 1.3 Propositional Equivalences

Logical Equivalence
The compound propositions p and q are called
logically equivalent if p ↔ q is a tautology.
The notation p ≡ q denotes that p and q are logically
equivalent.
The symbol ⇔ is sometimes used instead of ≡ to denote
logical equivalence.
1.3 Propositional Equivalences

Logical Equivalence

p q p p  q p q
0 0 1 1 1
0 1 1 1 1
1 0 0 0 0
1 1 0 1 1

s1  s2
 1.3 Propositional Equivalences
Logical Equivalence

De Morgan laws
 1.3 Propositional Equivalences
Logical Equivalence
De Morgan laws
 1.3 Propositional Equivalences

Conditional disjunction equivalence.

p → q and

are logically equivalent

 1.3 Propositional Equivalences
distributive law
p ∨ (q ∧ r) and (p ∨ q) ∧ (p ∨ r)
are logically equivalent
1.3 Propositional Equivalences
 Tables of Logical Equivalences

• Identity laws
Like adding 0
• Domination laws
Like multiplying by 0
• Idempotent laws
Delete redundancies
• Double negation
“I don’t like you, not”
• Commutativity
Like “x+y = y+x”
• Associativity
Like “(x+y)+z = y+(x+z)”
• Distributivity
L3 Like “(x+y)z = xz+yz” 57
• De Morgan
 Tables of Logical Equivalences

• Excluded middle
• Negating creates opposite
• Definition of implication in
terms of Not and Or
1.3 Propositional Equivalences
1.3 Propositional Equivalences
 1.3 Propositional Equivalences

Show that (p ∧ q) → (p ∨ q) is a tautology.

 Fundamentals of Logic

A compound statement is called a tautology(T0) if it is true

for all truth value assignments for its component statements.

If a compound statement is false for all such assignments,

then it is called a contradiction(F0).

p  ( p  q) : tautology

p  ( p  q) : contradiction
Propositional Logic - 2 more
defn…
A tautology is a proposition that’s always TRUE.

A contradiction is a proposition that’s always FALSE.

p p p  p p  p
T F T F
F T T F
 Tautology example

Demonstrate that
[¬p (p q )]q
is a tautology in two ways:
1. Using a truth table – show that
[¬p (p q )]q is always true
2. Using a proof (will get to this later).

64
 Tautology by truth table
p q ¬p p q ¬p (p q ) [¬p (p q )]q

T T

T F

F T

F F
 Tautology by truth table
p q ¬p p q ¬p (p q ) [¬p (p q )]q

T T F

T F F

F T T

F F T
 Tautology by truth table
p q ¬p p q ¬p (p q ) [¬p (p q )]q

T T F T

T F F T

F T T T

F F T F
 Tautology by truth table
p q ¬p p q ¬p (p q ) [¬p (p q )]q

T T F T F

T F F T F

F T T T T

F F T F F
 Tautology by truth table
p q ¬p p q ¬p (p q ) [¬p (p q )]q

T T F T F T

T F F T F T

F T T T T T

F F T F F T
 Tautologies, contradictions
and programming

Tautologies and contradictions in your

code usually correspond to poor
programming design. EG:
• while(x <= 3 || x > 3)
x++;
• if(x > y)
if(x == y)
return “never got
here”;
70
 dual
Let s be a statement. If s contains no logical connectives
other than  and  , then the dual of s, denoted sd, is the
statement obtained from s by replacing each occurrence of 
and  by  and  , respectively, and each occurrence of T
and F by F and T, respectively.
d
Eg. s : ( p   q )  ( r  T ), s : ( p   q)  (r  F )

The dual of p  q is (  p  q ) d   p  q
 The Principle of Duality

Theorem () Let s and t be statements.

If s  t , then s d  t d .

rst Substitution Rule (replace each p by another statement q)

Ex. P:  ( p  q )  (  p   q ) is a tautology. Replace

each occurrence of p by r s

P1:  [( r  s)  q ]  [  ( r  s)   q ] is also a tautology.

 Converse

The converse of a logical implication is the reversal of the implication. I.e. the converse of p q is q p.

EG: The converse of “If Donald is a duck then Donald is a bird.”

is “If Donald is a bird then Donald is a duck.”

p q and q p are not logically equivalent.

73
 Converse
p q p q q p (p q)  (q p)
 Converse
p q p q q p (p q)  (q p)
T T
T F
F T
F F
Logical Non-Equivalence of
Conditional and Converse
p q p q q p (p q)  (q p)
T T T
T F F
F T T
F F T
Logical Non-Equivalence of
Conditional and Converse
p q p q q p (p q)  (q p)
T T T T
T F F T
F T T F
F F T T
Logical Non-Equivalence of
Conditional and Converse
p q p q q p (p q)  (q p)
T T T T T
T F F T F
F T T F F
F F T T T
 Fundamentals of Logic

Compare the efficiency of two program segments.

z:=4; .
for i:=1 to 10 do .
begin Number of comparisons?
20 vs. 10+3=13 .
x:=z-1; if x>0 then
y:=z+3*i; if y>0 then
if ((x>0) and (y>0)) then …
writeln(‘The value of the sum x+y is’, x+y)
end
( p  q )  r logically equivalent p  (q  r )
Derivational Proof Techniques
When compound propositions involve more and
more atomic components, the size of the truth
table for the compound propositions
increases
Q1: How many rows are required to construct
the truth-table of:
( (q(pr ))  ((sr)t) )  (qr )
Q2: How many rows are required to construct
the truth-table of a proposition involving n
atomic components?
Derivational Proof Techniques
A1: 32 rows, each additional variable doubles
the number of rows
A2: In general, 2n rows
Therefore, as compound propositions grow in
complexity, truth tables become more and
more unwieldy. Checking for
tautologies/logical equivalences of complex
propositions can become a chore, especially
if the problem is obvious.
Derivational Proof Techniques
EG: consider the compound proposition
(p p )  ((sr)t) )  (qr )

Q: Why is this a tautology?

L3 82
Derivational Proof Techniques
A: Part of it is a tautology (p p ) and
the disjunction of True with any other
compound proposition is still True:
(p p )  ((sr)t ))  (qr )
 T  ((sr)t ))  (qr )
 T
Derivational techniques formalize the
intuition of this example.
L3 83
Propositional Logic - an
infamous 
if NOT (blue AND NOT red) OR red then…

(p  q)  q  p  q

(p  q)  (p  q) 

 DeMorgan’s
q q
 (p  q)  Double
q negation
 p  (q  Associativity
q)
 p  q Idempoten
t
 Tautology by proof
[¬p (p q )]q

L3 85
 Tautology by proof
[¬p (p q )]q
 [(¬p p)(¬p q)]q Distributive

L3 86
 Tautology by proof
[¬p (p q )]q
 [(¬p p)(¬p q)]q Distributive
 [ F  (¬p q)]q ULE

L3 87
 Tautology by proof
[¬p (p q )]q
 [(¬p p)(¬p q)]q Distributive
 [ F  (¬p q)]q ULE
 [¬p q ]q Identity

L3 88
 Tautology by proof
[¬p (p q )]q
 [(¬p p)(¬p q)]q Distributive
 [ F  (¬p q)]q ULE
 [¬p q ]q Identity
 ¬ [¬p q ]  q ULE

L3 89
 Tautology by proof
[¬p (p q )]q
 [(¬p p)(¬p q)]q Distributive
 [ F  (¬p q)]q ULE
 [¬p q ]q Identity
 ¬ [¬p q ]  q ULE
 [¬(¬p) ¬q ]  q DeMorgan

L3 90
 Tautology by proof
[¬p (p q )]q
 [(¬p p)(¬p q)]q Distributive
 [ F  (¬p q)]q ULE
 [¬p q ]q Identity
 ¬ [¬p q ]  q ULE
 [¬(¬p) ¬q ]  q DeMorgan
 [p  ¬q ]  q Double Negation

L3 91
 Tautology by proof
[¬p (p q )]q
 [(¬p p)(¬p q)]q Distributive
 [ F  (¬p q)]q ULE
 [¬p q ]q Identity
 ¬ [¬p q ]  q ULE
 [¬(¬p) ¬q ]  q DeMorgan
 [p  ¬q ]  q Double Negation
 p  [¬q q ] Associative

L3 92
 Tautology by proof
[¬p (p q )]q
 [(¬p p)(¬p q)]q Distributive
 [ F  (¬p q)]q ULE
 [¬p q ]q Identity
 ¬ [¬p q ]  q ULE
 [¬(¬p) ¬q ]  q DeMorgan
 [p  ¬q ]  q Double Negation
 p  [¬q q ] Associative
 p  [q ¬q ] Commutative

L3 93
 Tautology by proof
[¬p (p q )]q
 [(¬p p)(¬p q)]q Distributive
 [ F  (¬p q)]q ULE
 [¬p q ]q Identity
 ¬ [¬p q ]  q ULE
 [¬(¬p) ¬q ]  q DeMorgan
 [p  ¬q ]  q Double Negation
 p  [¬q q ] Associative
 p  [q ¬q ] Commutative
pT ULE

L3 94
 Tautology by proof
[¬p (p q )]q
 [(¬p p)(¬p q)]q Distributive
 [ F  (¬p q)]q ULE
 [¬p q ]q Identity
 ¬ [¬p q ]  q ULE
 [¬(¬p) ¬q ]  q DeMorgan
 [p  ¬q ]  q Double Negation
 p  [¬q q ] Associative
 p  [q ¬q ] Commutative
pT ULE
T Domination

L3 95
 Writing Logical Formula for a Truth Table

Digital logic:

en a digital circuit, we can construct the truth table.

Now, suppose we are given only the truth table (i.e. the
specification,
e.g. the specification of the majority function), how can
we construct a digital circuit (i.e. formula) using only
simple gates (such as AND, OR, NOT)
that has the same function?
 Examples
1. “I don’t study well and fail” is logically
equivalent to “If I study well, then I
don’t fail”
2. Write a C program that represents the
compound proposition (pq)r
Decide whether the following statements are
tautologies or contradictions or neither

1. (p  q)  (q  p).
2. (p  q)  (q  ¬p).
3. p  ¬p.
4. (p  ¬q)  (q  ¬p).
 Use truth table to find
• ¬P  Q  P  R
• P  -Q  R  P  R  - Q
• A  B  -C  D  E  F
• (P ↔ Q)  (P˅ Q)
• [P ˄ (P  Q)]  Q
Which of the following equivalent
to ¬ (P˄Q)
• (¬p) ˄ (¬Q)
• P˅Q
• (¬P) ˄ Q
• (¬P) ˅ (¬Q)
 Exercises
Use truth tables to verify these equivalences.
a) p ∧ T ≡ p
b) p ∨ F ≡ p
c) p ∧ F ≡F
d) p ∨ T ≡ T
e) p ∨ p ≡ p
f ) p ∧ p ≡ p.

01/27/25
 Exercises
Use truth tables to verify the commutative laws
a)p ∨ q ≡ q ∨ p.

b) p ∧ q ≡ q ∧ p.

01/27/25
 Exercises
Use a truth table to verify the distributive law
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r).

01/27/25
 Exercises
Show that each of these conditional statements is a
tautology
by using truth tables.
a) (p ∧ q) → p

b) p → (p ∨ q)

01/27/25
 Exercises
Show that each of these conditional statements is a
tautology
by using truth tables.
c) ¬ p → (p → q)

d) (p ∧ q) → (p → q)

01/27/25
 Exercises
Show that each of these conditional statements is a
tautology
by using truth tables.
e) ¬(p → q) → p

f ) ¬(p → q) → ¬ q

01/27/25
 Exercises
Show that (p ∨ q) ∧ (¬p ∨ r) → (q ∨ r) is a
tautology.

01/27/25
 Thank
You
01/27/25