Mathematical Foundations of Computing

Unit 1

FORMAL LOGIC

Propositional Logic
A proposition: is a declarative sentence that is either true or false,
but not both.

Declarative sentence: is a sentence that declares a fact

EXAMPLE : All of the following declarative sentences are

propositions.

1) Washington is the capital of USA

2) Dubai is the capital of Germany
3) 1+1=2
4) 2+2=3

Propositions 1 & 3 are T, while propositions 2 & 4 are F

EXAMPLE
Which of the following sentences are propositions?
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

Note that each of sentences 3 and 4 can be turned into a

proposition if we assign values to the variables

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 conventional letters used for propositional variables are

p, q , r, s, . . . .

The truth value of a proposition are:

True (denoted by T) , if it is a true proposition
False (denoted by F), if it is a false proposition.
Compound propositions:
propositions, formed from existing propositions using logical
operators (connectives).

The 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.

• The above table represents the truth table for the

negation of a proposition p.
• This table has a row for each of the two possible
truth values of a proposition p. Each row shows the
truth value of ¬ p corresponding to the truth value of
p for this row.
EXAMPLE:
Find the negation of the proposition "Today is
Friday“ and express this in simple English.

Solution:
The negation is
"It is not the case that today is Friday."
This negation can be more simply expressed by
"Today is not Friday,"
Or, "It is not Friday today."

EXAMPLE:
Find the negation of the proposition
"At least 20 mm of rain fell today in Madinah.“
and express this in simple English.

Solution:
The negation is "It is not the case that at least
20 mm of rain fell today in Madinah."

This negation can be more simply expressed by

"Less than 20 mm of rain fell today in Madinah.”
The 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 if and only if

both p and q are true and is false otherwise.

• The above table displays the truth table of p /\ q .

• This table has a row for each of the four possible
combinations of truth values of p and q .
• The four rows correspond to the pairs of truth values
TT, TF, FT, and FF, where the first truth value in the
pair is the truth value of p and the second truth
value is the truth value of q .
 EXAMPLE:
If p is the proposition "Today is Friday“ and q is the
proposition "It is raining today.“

Find the conjunction of the propositions p and q

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

THE 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.
EXAMPLE : What is 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 p and q, p v q, is the

proposition
"Today is Friday or it is raining today."
This proposition is true on any day that is either a Friday
or a rainy day (including rainy Fridays).
It is only false on days that are not Fridays when it also
does not rain.
 The Connective or in English
 In English “or” has two distinct meanings.
 “Inclusive OR” - In the sentence “Students who have taken
CS202 or Math120 may take this class,” we assume that
students need to have taken one of the prerequisites, but
may have taken both. This is the meaning of disjunction.
 For p ∨q to be true, either one (or both) of p and q must be true.

 “Exclusive OR (XOR) - When reading the sentence “ Coffee

or tea comes with dinner” we do not expect to be able to
get both coffee and tea.
 This is the meaning of the XOR (p ⊕ q)
 In (p ⊕ q) one of p and q must be true, (but not both)

THE EXCLUSIVE OR (XOR)

Let p and q be propositions.

The exclusive or of p and q (denoted by p q)
is the proposition that is true when exactly only one
of p and q is true and is false otherwise.
Example:
For the following sentence, determine whether an Inclusive
OR or an Exclusive OR is intended. Explain your answer.

"Students who have taken calculus or physics, but not both, can
enroll in this class.“

That is, students that can take the class are those:
1) who have taken only calculus,
2) who have taken only physics

This is XOR

Conditional Statements

Let p and q be propositions

The conditional statement p → q

is the proposition "if p, then q .“

p is called the hypothesis (or antecedent or premise)

q is called the conclusion (or consequence).

A conditional statement is also called an implication.

The conditional statement p → q

is false when p is true and q is false, and true otherwise.
The truth table for the conditional statement p → q is shown in the table
below.

Note that the statement p → q is true when both p and q are true
and when p is false (no matter what truth value q has).

Ways to express the conditional statement:

"if p, then q"
"if p, q "
"p is sufficient for q"
"q if p"
"q when p"
"a necessary condition for p is q"
"q unless ¬ p"
"p implies q"
"p only if q"
"a sufficient condition for q is p"
"q whenever p"
"q is necessary for p"
"q follows from p”
Example:
Let p be the statement “Ahmad learns discrete structures"
and q the statement " Ahmad will find a good job."

Express the statement p → q as a statement in English.

Solution:
p → q represents the statement
"If Ahmad learns discrete structures, then he will find a
good job."

EXAMPLE:
In which cases the following statement will be T and
when will it be F?
"If it is sunny today, then we will go to the beach.“
Solution:
The statement is true unless it is indeed sunny
today, but we do not go to the beach.
EXAMPLE:
In which cases the following statement will be T
and when it will be F
"If today is Friday, then 2 + 3 = 5 . “
Solution:
is always true from the definition of a conditional
statement, because its conclusion is true

EXAMPLE:
In which cases the following statement will be T
and when it will be F
"If today is Friday, then 2 + 3 = 6 . “
Solution:
is true every day except Friday, even though
2 + 3 = 6 is false.
 CONVERSE, CONTRAPOSITIVE, AND INVERSE

New conditional statements could be formed starting with a conditional statement

p→q.
In particular, there are three related conditional statements

If we have the conditional statement p → q

The proposition q → p is called the converse of p → q

The proposition ¬ q → ¬ p is called contrapositive of p → q

The proposition ¬ p → ¬ q is called the inverse of p → q.

EXAMPLE :
What are the contrapositive, the converse, and
the inverse of the conditional statement
"The home team wins whenever it is raining.

Solution:
Because "q whenever p" is one of the ways to
express the conditional statement p → q , the
original statement can be rewritten as

"If it is raining, then the home team wins."

Consequently,
REMEMBER THAT:

q → p is called the converse of p → q

¬ q → ¬ p is called contrapositive of p → q
¬ p → ¬ q is called the inverse of p → q.

The statement is: "If it is raining, then the home team wins."

SOLUTION

The converse is
"If the home team wins, then it is raining."

the contrapositive
"If the home team does not win, then it is not raining."

The inverse is
"If it is not raining, then the home team does not win."

NOTE THAT Only the contrapositive is equivalent to the original statement.

BICONDITIONALS:
another way to combine propositions that expresses that two propositions have
the same truth value.

DEFINITION :
Let p and q be propositions.

The biconditional statement p ↔ q is the proposition "p if and only if q .“

Biconditional statements are also called bi-implications.

The biconditional statement p ↔ q is

TRUE when p and q have the same truth values (Both TRUE or both FALSE ),
and is FALSE otherwise.
That is why we use the words "if and only if " to express this
logical connective and why it is symbolically written by
combining the symbols → and ←

• There are some other common ways to express p ↔ q :

"p is necessary and sufficient for q "
"if p then q , and conversely"
"p iff q"

• The last way of expressing the biconditional statement

p ↔ q uses the abbreviation "iff" for "if and only if.

EXAMPLE :
Let p be the statement "You can take the flight"
and let q be the statement "You buy a ticket.“
Find p ↔ q

SOLUTION
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.

It is false when p and q have opposite truth values.

Summary of Boolean operators

Precedence of Logical Operators

 Truth tables of the compound proposition
We can use the connectives (conjunctions, disjunctions, conditional statements, and biconditional
statements-as well as negations) to build up complicated compound propositions involving any
number of propositional variables. We can use truth tables to determine the truth values of these
compound propositions
EXAMPLE :
Construct the truth table of the logical expression [compound proposition]
(p v ¬ q) → (p /\ q).

Example
How many rows are there in a truth table with
3 propositional variables?

Solution:
2n where n is the number of propositions.
So the number of rows is 23 = 8 rows
 Bits and Boolean Variables
 Computers represent information using bits
 A bit may have one of two values: 0, 1
 There are two possible truth values: T, F. Therefore, a bit
can be used to represent a truth value as shown in this
table:
 A variable is called a Boolean variable if its value can only
be either true or false.
 A Boolean variable can be represented using a bit.

Bit Operations
 Bit Operations correspond to Logical Connectives
 After replacing true by 1 and false by 0 in the truth tables,
we can use the bit operators OR, AND, and XOR as follow:
 Bit Strings and Bitwise 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.
 101010011 is a bit string of length nine.
 We can extend bit operations to bit strings.
 bitwise OR, bitwise AND, and bitwise XOR
 Bitwise OR of two strings of the same length is the string that have
the OR of the corresponding bits in the two strings
 Similarly for bitwise AND and bitwise XOR
 We use the symbols , , and  to represent the bitwise
OR, bitwise AND, and bitwise XOR operations, respectively

Example
Find the bitwise OR, bitwise AND, and bitwise XOR of the bit
strings: 01 1011 0110 and
11 0001 110 1

Solution
The bitwise OR, bitwise AND, and bitwise XOR of these
strings are obtained by taking the OR, AND, and XOR of the
corresponding bits, respectively
 Example
Evaluate the following expression.
11001  (11011  10010)

Solution

Translating English Sentences

Example 1
EXAMPLE 2
How can this English sentence be translated into a logical
expression?

"You can access the internet from campus only if you are a
computer science major or you are not a freshman.”

• a= access the internet,

• C = computer science student and,
• F =freshman
• "p only if q"

Example 3
 Propositional Equivalences
An important type of step used in a mathematical argument is the
replacement of a statement with another statement with the same
truth value.

We begin our discussion with a classification of compound

propositions according to their possible truth values.

DEFINITION :

Tautology: is a compound proposition that is always true, no

matter what the truth values of the propositions that occur in
it.

Contradiction: is a compound proposition that is always false,

no matter what the truth values of the propositions that occur
in it.

Contingency: is a compound proposition that is neither a

tautology nor a contradiction.

EXAMPLE:

We can construct examples of tautologies and

contradictions using just one propositional
variable.
 Logical Equivalences

Compound propositions that have the same

truth values in all possible cases are called
logically equivalent.

The notation p ≡ q denotes that p and q are

logically equivalent.
Example:
Using the truth table, prove that ONLY the
contrapositive is equivalent to the original
conditional statement (p → q )

Example:

1) Prove that

2) Prove that
 De Morgan’s Laws

Example: Use De Morgan's laws to express the negations of:

1) “Ahmad has a cellphone and he has a laptop computer"
2) “Ali will go to the university or Mohammad will go to the
university“
Solution of part 1:
Let p: " Ahmad has a cellphone"
q: " Ahmad has a laptop computer."

Then " Ahmad has a cellphone and he has a laptop computer"

can be represented by p  q.
By the first of De Morgan's laws,

¬(p  q) is equivalent to ¬p  ¬q.

The negation of our original statement will be

“Ahmad does not have a cell phone or he does not have a

laptop computer."
Solution of part 2:
Let r: “ Ali will go to the university"
s: " Mohammad will go to the university."

Then " Ali will go to the university or Mohammad will go to the

university " can be represented by r  s

By the second of De Morgan's laws,

¬(r  s) is equivalent to ¬r  ¬ s

The negation of our original statement will be

“Ali will not go to the university and Mohammad will not go

to the university."

Proof using Logical Equivalences

EXAMPLE:
Using logical equivalences, show that the following compound
propositions are logically equivalent

(p  r)  (q  r)  (p  q)  r

 ( p  r)  ( q  r) Definition of implication
prqr Associative
pqrr Commutative
 ( p   q)  (r  r) Associative
  (p  q)  r De Morgan, Idempotent
 (p  q)  r Definition of implication
 Example 2
Using logical equivalences, show that the following
proposition is a tautology
(p  q)  (p  q)

  (p  q)  (p  q) Implication
 ( p   q)  (p  q) De Morgan

 ( p  p)  ( q  q) Commutative, Associative

TT Negation

T Identity

Example 3
Using logical equivalences, show that the following compound
propositions are logically equivalent