Chapter 1

1.1 Propositional Logic:

• Propositional Logic (Calculus): It deals with propositions.
• Proposition: A statement that is either true or false (but not both).
• Examples of propositions:
- Today is Thursday. (True) since, today is Thursday.
- W: Today it is raining. (False) since, today is not raining.
- P: 1 + 1 = 4. (False), since 1 + 1 = 2
- Water boils at 50C. (False) → Scientific Fact
- Q: Ali has a cat. (True) as example for a story.
- Ali has a dog. (false) as example for a story.

• Examples of non-propositions:
- 1 + x = 4. Since x is a variable
- Close the door. (order)
- What is your name? (question)
- Wow!!!!! (Exclamation)

• Propositions can be denoted by Letters. A…Z

• P and Q are commonly used.
• True value can be denoted by T.
• False value can be denoted by F.
• Example:
- P: Ali has a cat. : T
- Q: 1 + 1 = 4. :F

• Propositions are classified into:

1. Atomic: consists of single proposition.
2. Compound: consists of one or more propositions connected by logical operators.
NOT, AND, OR, XOR, IMPLIES, IFF

• Example:
- P: Ali has a cat. : T Atomic
- Q: 1 + 1 = 4. :F Atomic
- R: P AND Q :F Compound

Truth Table

• A Truth Table is a complete list of the possible truth values of a logical statement.
• Truth table can be used to show the effect of each logical operator, and it can be also used to show the result
of a logical statement.

1
 • Logical Operators:

Assume that P, Q, and R are propositions

1- Negation: for P, Negation of P is denoted by ~P, and it is read as "NOT P"

Negation reverses the truth value of P.
- P: Today is sunny. : T Atomic
- Q: 1 + 1 = 4. :F Atomic
- ~P: Today is not sunny. : F compound
- ~Q: 1 + 1 ≠ 4. :T compound
- R: Ali is tall : T Atomic
- ~R: Ali is not tall : F Compound
- S: 3 + 3 > 6 : F Atomic
- ~S: 3 + 3 <= 6 : T Compound

• Truth Tables of a single proposition P or its Negation P:

P P P
T T F
F F T

2- Conjunction: is denoted by P  Q, and it is read as "P AND Q"

Conjunction is True if both P and Q are true.
Let:
P: Ali has a cat.
Q: Ali has a dog
P  Q : Ali has a cat and a dog. It is True when Ali has 2 pets both are a cat and a dog

P Q P Q
T T T
T F F
F T F
F F F

2
 3- Disjunction:
a. inclusive OR is denoted by P  Q, and it is read as "P OR Q"
It is True, if any of P and Q is true.
Let:
P: Ali has a cat.
Q: Ali has a dog
P  Q : Ali has a cat or a dog. It is True when Ali has a cat or a dog or both.

P Q P Q
T T T
T F T
F T T
F F F

b. exclusive OR is denoted by P  Q, and it is read as "P XOR Q"

It is True, if any of P and Q is true, but not both. i.e. if they are different.
Let:
P: Ali has a cat.
Q: Ali has a dog
P  Q : Ali has one pet, Ali has a cat or a dog.
It is True when Ali has a cat or a dog but not both.

Let:
R : Ahmad is tall.
S : Ahmad is short.
W: Ahmad is fat.
R  S : Ahmad is tall or short.
R  W : Ahmad is tall or fat.

P Q PQ
T T F
T F T
F T T
F F F

3
4- Implication: is denoted by P→ Q, and it is read as "P implies Q"
It is false, only if P is T and Q is F
P : Hypothesis
Q: Conclusion
P → Q has many forms in English Language:
" If P, then Q" "If P, Q" "P only if Q"
"P implies Q" "Q if P" "Q unless P"
“When P, then Q” “Whenever P, Q” " P is sufficient for Q"
"Q is necessary for P"

P Q P→Q
T T T
T F F
F T T
F F T

P Q Q→P
T T T
T F T
F T F
F F T

USING:
- P: it rains.
- Q: I wear my coat.
- P → Q : has many forms:
1- If it rains, then I will wear my coat.
P → Q
2- If it rains, I will wear my coat.

3- It rains only if I wear my coat.

P → Q

4- only if It rains, I wear my coat.

4
 5- Raining implies that I will wear my coat.

6- I will wear my coat, if it rains.

7- I will wear my coat unless it is not raining.

Q if ~ ~p

P → Q
8- Unless it is not raining, I will wear my coat.
IF ~ ~P Q
P → Q

Note: P→ Q IS NOT THE SAME Q→P

If it rains, then I will wear my coat.

P → Q

If I wear my coat., it will rain

Q → P

5
5- Biconditional: is denoted by PQ, and it is read as "P if and only if Q"
It is true, if P and Q both have the same truth value.
P  Q has many forms in English Language:
"P if and only if Q"
"If P, then Q, and conversely"
"P is sufficient and necessary for Q"
USING:
- P: it rains.
- Q: I wear my coat.
- P  Q : has many forms:
1- If and only if it rains, I will wear my coat.
2- If it rains, I will wear my coat, and conversely.
3- If it rains, I will wear my coat and if I wear my coat, it will rain.
(P → Q)  (Q → P)

P Q PQ
T T T
T F F
F T F
F F T

P  Q is the same as:

( p → Q)  (Q → P)
T →T T→ T =T
T  T

T →F F→ T =F
F  T

F →T T→ F =F
T  F

F →F F→ F =T
T  T

Example:
If n is an even integer then it is divisible by 2, and if n is divisible by 2, then it is even.
(R → S )  ( S → R )

RS

6
Summary of logical operations:
1- NOT: it reverses the truth value.
2- AND: it is always FALSE, except if they are both TRUE.
3- OR: it is always TRUE, except if they are both FALSE.
4- XOR: it is TRUE if they are different.
5- IMPLIES: it is always TRUE, except TRUE → FALSE
6- IFF: it is TRUE if they are the same.

Examples:
USING:
- P: Samer has a car.
- Q: Samer has a bicycle.
- R: Today is sunny.
- S: It rains.
- W: I wear my umbrella.

WE CAN BUILD:
- ~R: Today is not sunny.
- P  Q: Samer has a car and a bicycle.
- P  Q: Samer has a car or a bicycle.
- P  Q: Samer has a divining machine; it is either a car or a bicycle.
- S → W: If it rains, I will wear my umbrella.
- S  W: If it rains, I will wear my umbrella, and conversely.

7
• The following truth table can be used to represent the compound proposition:

(P  Q)  (~P)

P Q PQ ~P (P  Q)  (~P)
T T T F T
T F F F F
F T F T T
F F F T T

Note: If a compound proposition has n distinct simple components, then it will have 2n rows in its
truth table, as this is the number of possible combinations of n components, each with 2 possible truth
values T or F.

(P  Q)  (~R) ---------> 3 VARIABLES → 8 ROWS

P Q R PQ ~R (P  Q)  (~R)
T T T T F T
T T F T T T
T F T F F F
T F F F T T
F T T F F F
F T F F T T
F F T F F F
F F F F T T

8
• P → Q has 3 components: Converse, contrapositive, Inverse

Assume: (P→Q) if it is raining, then it is cloudy.

P Q
1. Converse: Q→P If it is cloudy, then it is raining.
IT IS NOT THE SAME AS
P→Q
2. Inverse: P→Q if it is not raining, then it is not cloudy.
IT IS NOT THE SAME AS
P→Q
3. Contrapositive: Q → P If it is not cloudy, then it is not raining.
IT IS THE SAME AS
P→Q

• Logical operator Precedence

Ex: Assume P: T Q: F R: F
Operator Precedence
Find the value of:
 1
PQR P
 2 TFF T
 3 TFT T
 4 TF T
→ 5 TT
 6 T

If the operators are the same, priority goes from left to right.

9
 1.2 Applications of Propositional Logic:
Translation FROM English Sentences TO logic expressions:

1. if you are a computer science major or you are not a freshman, you can access the internet in the lab.
P Q R

(P   Q) → R

2. If you watch television frequently, your mind will decay, and conversely.
P Q
P  Q

3. You got an A in this class, but you did not do every exercise in the book.
P Q

P  Q

4. if it is hot outside, buy an ice cream, and if you buy an ice cream, it is hot outside.
P Q Q P
(P →Q)  (Q→P)  P Q

5. You got an A in this class, only if you do every exercise in the book.
P Q

P →Q

6. only if You got an A in this class, you do every exercise in the book.
P Q

P →Q

7. Yo got an A in this class, if you do every exercise in the book.

P Q
Q→P

if you do every exercise in the book, Yo got an A in this class

8. if Yo got an A in this class, you do every exercise in the book.

P Q
P→Q

9. You will not get an A in this class, unless you do every exercise in the book.
~ P if ~ Q
 Q → P  P → Q

10. unless You did not get an A in this class, you will do every exercise in the book.
if ~ ~P Q

P→Q
10
• Logic And Bit Operations

- Binary system uses bits.

- Bit has two values: 0, 1
- True (1), False (0)
- Boolean Variable: a variable that is either true or false.
- Bit operation corresponds to logical connectives:

Logical Bit operator

Operator
 NOT
 AND
 OR
 XOR

- Bit string: it is a sequence of zero or more bits.

- String Length: number of bits in the Bit string.
- Byte: 8-bits
Ex1: 101010011 is a bit string with length = 9
Ex2:

01 1011 0110 OR 01 1011 0110 AND 01 1011 0110 XOR

11 0001 1101 11 0001 1101 11 0001 1101

11 1011 1111 01 0001 0100 10 1010 1011

NOT (01 1011 0110) = 10 0100 1001

11
1.2 Applications of Propositional Logic
The required topics:
1- Translating from English to Logic
2- Bit-wise operations

Other applications are Self-Study.

12
1.3 Logical Equivalence

Def: 1. Tautology: compound proposition that is always true (Ex: P  P)

P P P  P
T F T
F T T

2. Contradiction: compound proposition that is always false (Ex: P  P)

P P P  P
T F F
F T F

3. Contingency: compound proposition that is either true or false (Ex: P → Q)

• Logical Equivalence (P  Q, P  Q)
Def: the two compound propositions P, Q are logically equivalent iff P  Q is a tautology.

Proving Techniques:

A. Using truth table

Ex1: show that P→ Q   P  Q

P Q P P→ Q PQ P→ Q   P  Q
T T F T T T
T F F F F T
F T T T T T
F F T T T T

It is a Tautology
 They are equivalent

Ex2: show that  (P  Q)  ( P  Q) using truth table

Note: Truth tables are not advised for proposition with large number of simple propositions.

13
B. Using Logical Equivalence Rules

Table 1: Equivalence rules:    Table 2: Implications Logical Rules

Equivalence rule Name 1. P →Q   P  Q
PT P Identity 2. P →Q  Q → P
PF P 3. P  Q  P → Q
P TT Domination 4. P  Q  (P → Q)
P FF 5. (P → Q)  P   Q
P PP Idempotent 6. (P→Q)  (P→ R)  P→( Q R)
P PP 7. (Q→R)  (P→ R)  (Q P) → R
8. (P→Q)  (P→ R)  P→( Q  R)
P P T Negation
9. (Q→R)  (P→ R)  (Q P) → R
P P F
( P)  P Double
Negation
PQQP Commutative Table 3: Bicondintional Rules
PQQP 1. P  Q  (P →Q)  (Q→ P)
(P  Q)  R  P  (Q  R) Associative 2. P  Q  P  Q
(P  Q)  R  P  (Q R) 3. P  Q  (P  Q)  (P Q)
P  (Q  R)  (P  Q)  (P  R) Distributive 4. (P  Q)  P  Q
P  (Q  R)  (P  Q)  (P R)
 (P  Q)  P  Q De Morgan’s
 (P  Q)  P  Q
P  (P  Q)  P Absorption
P  (P  Q)  P

Ex1: show that (P  Q) → (P  Q) is a tautology

1.  (P  Q)  (P  Q) Implication rule
2. (P  Q)  (P  Q) De Morgan’s Law
3. (P  P)  (Q  Q) Associative and commutative
4. T  T Negation law
5. T

Ex2: show that  (P  (P  Q)) and (P Q) are logically equivalent.
show that  (P  (P  Q))  (P Q)

1.  (P  (P  Q)   P   (P  Q) De Morgan’s

2.   P  ((P)  Q) De Morgan’s
3.   P  ( P  Q ) Double negation
4.  ( P  P)  ( P  Q) Distributive
5.  F  ( P  Q) Negation
6.  ( P  Q) Identity

14
4. PREDICATES AND QUANTIFIERS

PREDICATES
• X>3
• X = Y +3
Both above statements are not propositions, they are called predicates

Ex1:
P(x): x > 3 , x it is not specified. True or False ???
P(2): 2 >3 : F it is a proposition
p(4): 4>3 : T it is a proposition
… according to the domain.

It is called: Propositional function

Ex2: Q(x, y): x= y+3 predicate Q(3,0): 3 = 0 + 3 : T proposition

Ex3: R(X,Y,Z): X + Y = Z . predicate R(2,3,4) : 2+3 = 4 :F proposition

R (1, 3, Z) ???
It is not a proposition. It is a predicate because Z is still a variable.

QUANTIFIERS:

Quantifiers Universal quantifier (  ), for all

Existential Quantifier (  ), for some

1. Universal Quantifier
* P(x) is true for all values of x in the universe of discourse (domain). ➔ x p(x)
* x p(x) is read as: “for all x p(x) “ , “ for every x p(x)”

x p(x)  p(e1)  p(e2)  p(e3)  …..  p(en) , where {e1,e2,…,en} are all elements of the domain
x p(x) : T , if p(x) is true for all elements

Ex1: p(x) : “x+1 > x” , what is the truth value of x p(x), where the domain is all real numbers?

Sol : x p(x) is true for all values of x

Ex2: What is the truth value x p(x), where p(x) is (x*x < 10). The domain is all positive integers not
exceeding 4?

Sol : x p(x) = P(1)  p(2)  p(3)  p(4)

T T  T  F = F

15
Ex3: what is the truth value of x (x*x  x) , if the domain is all integer numbers

Sol: T

Ex4: Translate the following statement into English language:

x Q(x), where Q(x) is “x has two parents” and the domain is all people.

Sol: every person has two parents

2. Existential quantifier
• There exists an element x in the domain such that p(x) is true ➔ x p(x)
• x p(x) is read as: “there is a x such that p(x) “,“ there is at least one x such that p(x)”

x p(x)  p(e1)  p(e2) p(e3) …..  p(en) , where {e1,e2,…,en} are all elements of the domain
x p(x) : T , if p(x) is true for at least one element

Ex1: what is the truth value of x p(x), where p(x) is “x*x > 10” and the domain is all positive integers
not exceeding 4?

x p(x) = P(1)  p(2)  p(3)  p(4) = True, since p(4) is True

Ex2: p(x): x > 1 what is the truth value of x p(x), where the domain is all real numbers?

Ans: True

Ex3: p(x): x = 0.1 what is the truth value of x p(x), where the domain is all integer numbers?

Ans: False

16
Binding Variable
A variable in a predicate might be:
1- Free:
Ex1: p(x): x has a cat. Domain: people x is a free variable.
Ex2: like(x, y): x likes y. Domain: people x and y are free variables.
Ex3: R(x,y,z): x+y = z. Domain: integers x, y, z are free variables.

2- Bound:
a. To a value
Ex1: p(Ali): Ali has a cat. x is a bound variable to value Ali.

Ex2: like(Ali, Ahmad): Ali likes Ahmad. x and y are bound variables to values.
like(Ali, y): Ali likes y. x is a bound variable to a value, y is free. → it is still a predicate.

b. To a quantifier
Ex: xy like(x, y) x is bound to , y is bound to 
Ex: x Q(x, y) x is bound, y is free
Ex: x ( p(x)  Q(x))  x (R(x))
- x is bound to x, - x is bound to x
- Scope of x is ( p(x)  Q(x)) - Scope of x is R(x)

This statement can be written as :

x ( p(x)  Q(x))  y R(y)
But if it becomes: x ( p(x)  Q(x))  R(y)
since y is free, so this is a predicate (not a proposition)
because a proposition must be a predicate with no free variables.

( ) following the quantifier specified the scope of it. if there is no ( ), the scope of the
quantifier will be the first predicate after it. Like:
x P(x)  Q(z)  y R(y)  x (p(x))  Q(z)  y (R(y) )
Because Q is out of  scope. This makes z is a free variable → it is a predicate.

Negation
1.  x P(x)   ( p(e1)  p(e2)  p(e3)  …..  p(en) ) 
( p(e1)  p(e2)  p(e3)  …..  p(en) )  x  p(x)
ex: Every student in the class has taken calculus. x P(x)
There is a student in the class who has not taken Calculus.  x P(x) x  p(x)

2.  x P(x)   (p(e1)  p(e2) p(e3) ….. p(en) )  x  p(x)

ex: There is a student in the class who has taken Calculus. x p(x)
Every student in the class has not taken calculus.  x P(x)  x  P(x)

17
Ex: what are the negations of the following statements, domain: Integers?
A. x (x*x >x)  F
Sol: x (x*x >x) → x  (x*x > x) → x (x*x  x)  T since 0,1 make it True

B. x (x *x = 2)  F
Sol : x (x *x = 2) → x  (x *x = 2) → x (x *x  2)

5 NESTED QUANTIFIERS
Ex1:
1. x(y ( x + y = y + x )) is true, for every values x and y x + y = y + x Domain: Real Numbers.
x(y ( x + y = y + x )) is the same as xy x + y = y + x (parentheses are optional)
2. xy ( x - y = y - x ) is false, for every values x and y x - y = y - x Domain: Real Numbers.
Because (3,4) make it false

Ex2: xy ( x + y = 0 ) is false for every values x and y x + y = 0 Domain: Real Numbers.
Because (1,1) makes it false

NEGATING NESTED QUANTIFIER

Ex1: xy (x.y = 1) → x y (x.y = 1) → xy (x.y  1)
Ex2: xy z (P(x,y) Q(y,z) ) → xy z (P(x,y) Q(y,z))
→ x y z (P(x,y) Q(y,z)) → x y z (P(x,y) Q(y,z))
→ x y z (P(x,y) ˅Q(y,z))

ORDER OF QUANTIFIER
Statement When true When false
xy P(x, y) P(x, y) is true for every pair There is a pair x, y for
yx P(x, y) x, y. which P(x, y) is false
xy P(x, y) For every x, there is a y for There is x, such that P(x, y)
which P(x, y) is true is false
xy P(x, y) There is a common x for For every x there is a y for
which P(x, y) is true for which P(x, y) is false
every y.
xy P(x, y) There is a pair x, y for P(x, y) is false for every
yx P(x, y) which P(x, y) is true pair x, y.

18
Using Domain: All integers:{…, -3,-2,-1,0,1,2,3,4,…}
Ex1: Let Q(x, y) denote “ x + y = 0” what are the truth values of the quantifications
xy Q(x, y), and xy Q(x, y)?

Sol: xy Q (x, y) false xy Q(x, y) true

Ex2: Let Q(x, y) denote “ x + y = x” what are the truth values of the quantifications
yx Q(x, y), and xy Q(x, y)?

Sol: yx Q (x, y) true xy Q(x, y) true

Ex3: Let Q(x, y) denote “ x + y = y + x” what are the truth values of the quantifications
yx Q(x, y), and xy Q(x, y)?

Sol: yx Q (x, y) true xy Q(x, y) true

Ex4: Let Q(x, y) denote “ x + y = 5” what are the truth values of the quantifications
yx Q(x, y), and xy Q(x, y)?

Sol: yx Q (x, y) true xy Q(x, y) false

Ex5: Let Q(x, y) denote “ x + y = 0.5” what are the truth values of the quantifications
yx Q(x, y), and xy Q(x, y)?

Sol: yx Q (x, y) false xy Q(x, y) false

19
 Translation From English Into Logical Expressions
Examples:

1. Express the statement:

“Everyone in this class has taken calculus”
“For every person x, if person x is a student in this class then x has studied Calculus”.
Domain: All people S(x) C(x)
x ( S(x) → C(x) )
T → T : if x is a student in this class, then he must study calculus
F → T : if x is not a student in this class, then he may study calculus
F → F : if x is not a student in this class, then he may not study calculus
T → F : if x is a student in this class, then he does not study calculus (it is not allowed)

2. Express the statement:

“Every student in this class x, x has studied Calculus”.
x C(x)
Domain: All students in this class.
x C(x)

3. Express the statement:

“Every student x if x is in this class, x has studied Calculus”.
S(x) C(x)
Domain: All students
x ( S(x) → C(x) )

4. “No one is perfect”

x  P(x)

5. “All your friends are perfect.”

F(x): your friend P(x): perfect
x ( F(x) → P(x))

6. Let P(x) be the statement “x can speak French” and Q(x) be the statement “x knows C++”. The domain
is all students in the school. Express the following statement using quantifiers and logical operator:

A. “No student at your school can speak French or knows C++.”

x  (P(x)  Q(x))

B. There is a student at your school who can speak French but does not know C++.
x (P(x)  Q(x))

7. Express the statement “if a person is a female and is a parent, then this person is someone’s mother”

F(x): person is a female

P(x): person is a parent

20
M(x, y): x is the mother of y

Sol: x ( (F(x)  P(x)) → y M(x, y) )

8. Express the statement: “Everyone has one best friend”

Sol:
B(x, y) : x is the best friend of y
x y B(x, y)

9. C(x) is “x has a computer”

F(x, y) is “x and y are friends

Translate the statement:

x (C(x)  y (C(y)  F(x, y) ) )

Sol: For every student x in your school x has a computer or there is a student y such that y has a computer and
x and y are friends.

Or

Every student in your school has a computer or has a friend who has a computer

21
Chapter 1 Exercise on Translation

➢ Exercise 1:
Domain: people
Teacher(x): x is a teacher.
Student(x): x is a student.
Visit(x, y): x visited y.
Translate the following into Logic:
A. Ali visited Sami.
B. Ali visited everyone.
C. Ali visited someone.
D. Ali visited some teachers.
E. Ali visited all teachers.
F. Someone visited someone.
G. Everyone visited someone.
H. Someone visited everyone.
I. Everyone visited everyone.
J. Everyone has been visited by someone.
K. Ali did not visit anyone  Ali visited nobody.
L. Ali did not visit everyone.
M. All students visited Ali and some teacher too.
N. All students visited Ali and some teacher did.
O. Ali visited everyone but nobody visited him.

➢ Exercise 2:
Let:
Domain: Animals

Translate the following into Logic:

Domain: Animals
A. All animals have skin.
B. All dogs have legs.
C. Some cats are black.
D. Some cats are black or white.
E. No cat can speak English.

22
➢ Exercise 3:
Let:
Domain1: people
Domain2: fruits.
L(x, y): x likes y.
Friend (x, y): x is a friend of y.
Student(x): x is a student.
Teacher(x): x is a teacher.
Teach(x, y): x teaches y.

Translate the following into Logic:

A. Everybody likes apples.

B. Somebody likes apples but not oranges.
C. Everybody likes apples or oranges.
D. Everybody likes some fruits.
E. Everybody likes somebody.
F. Everyone likes Ali.
G. Ahmad likes Ali.
H. Someone likes everyone.
I. No one likes everyone.
J. Everyone likes himself/herself.
K. There is someone whom everybody likes.
L. Some students like some teachers.
M. Ali and Ahmad are friends.
N. Some students are friends.
O. Every teacher has taught Ali.
P. Some teachers have taught Ali and all his friends.
Q. Ali has a friend who has been taught by all teachers.
R. Some teachers have taught all students.
S. Some students and some teachers are friends.
T. If someone is a teacher, then Ali likes him.
U. If a person is a teacher, then he taught some students.

23
6 Rules of Inference
Example:
P : T (hypothesis, or premise)
P→ Q : T (hypothesis, or premise)
--------------
Q : T (Conclusion)

(Therefore)

Rules of inference Tautology Name

P P→ (P  Q)
------ Addition
P  Q
PQ
------ (P  Q) → P
Simplification
P (P  Q) → Q
Q
P
Q Conjunction
((p)  (Q)) → (P  Q)
------
 PQ
P
Modus ponens
P→Q
[P  (P→Q)]→ Q Forward Reasoning
------
Q
Q
Modus Tollens
P→Q
[  Q  (P→Q)]→  P Backward Reasoning
------
 P
P→Q
Q→R
[(P→Q)  (Q→R)]→(P→R) Hypothetical Syllogism (H. S.)
--------
 P→R
P Q
P
[(P  Q)   P]→ Q Disjunctive syllogism (D. S.)
--------
Q
PQ
P R
[(P  Q)  (  P  R)]→ Q  R Resolution
----------
Q  R

24
Ex1: state the rule of inference for:
“It is below freezing now, therefore it is either below freezing or raining now”
P P Q

Sol:
It is below freezing: P P
It is raining: Q -----------
P  Q
It is called: Addition Inference Rule.

Ex2: State the rule of inference used in the argument

“If it rains today, then we will not barbecue today”.
“If we don’t barbecue today then we will have a barbecue tomorrow”.
Therefore, “if it rains today, then we will have a barbecue tomorrow”.

Sol:
it is raining today: P we barbecue today: Q
We have barbecue tomorrow: R

1. P→  Q
2.  Q→R
------------------
 P→R using H. S. of step 1 and step 2

Valid Argument

• An Argument form is called valid if whenever the entire hypothesizes are true, the conclusion is also
true.
• Consequently Q logically follows from the hypothesis P1, P2, P3, ….., Pn:
( P1  P2  P3……  Pn) → Q will be a tautology.

25
EX: Show that the hypotheses:
“It is not sunny this afternoon and it is colder than yesterday.”
“We will go swimming only if it is sunny,”
“If we do not go swimming, then we will take a canoe trip,” and
“If we take a canoe trip, then we will be home by sunset”
lead to the conclusion “we will be home by sunset”

P: It is sunny this afternoon

Q: it is colder than yesterday
R: we will go swimming
S: we will take a canoe trip
H: we will be home by sunset

Hypothesis
1.  P  Q
2. R→P
3.  R→S
4. S→H

Solution:

Step Reason
1.  P  Q Hypothesis #1
2.  P Simplification using step 1
3. R→P Hypothesis #2
4.  R Modus tollens step 2 + 3
5.  R→S Hypothesis #3
6. S Modus ponens using step 4 and 5
7. S→H Hypothesis #4
--------------------------------------
 H Conclusion (modus ponens using step 6 and 7

Fallacies sum of (Fallacy)

There are two types of fallacies:

A. Fallacy of affirming the conclusion [(P→Q)  Q] → P
Because P can be either true or false.

B. Fallacy of Denying the Hypothesis [(P→Q)   P] →  Q

26
Rules Of Inference For Quantified Statements
Rules Of Inference Name
xP(x) Universal Instantiation
---------
 P(c) for all elements c
P(c) for every element c Universal Generalization
---------
 xP(x)

xP(x) Existential Instantiation

---------
 P( c) for some element c
P(c) for some element c Existential Generalization
----------
 xP(x)

EX1: show that the premises “Everyone in this class has taken a course in computer science” and “Marla is a
student in this class” imply the conclusion “Marla has taken a course in computer science”. Domain: Students

D(x) : x in this class

C(x) : x has taken a course in computer science.
Premises:
1. x( D( x) → C( x)) Premise #1
2. D(Marla) Premise #2

Sol:
1. x( D( x) → C( x)) Premise #1
2. D(Marla) → C(Marla) Universal instantiation from step #1
3. D(Marla) Premise #2
---------------------------------------------------
 C(Marla) Modus Ponens from steps 2 and 3

27
EX2: show that the premises “Everyone in this class has taken a course in computer science” and “Someone is
a student in this class” imply the conclusion “Someone has taken a course in computer science”.

D(x) : x in this class

C(x) : x has taken a course in computer science.

Premises:
1. x( D( x) → C( x)) Premise #1
3. x D(x) Premise #2

Sol:
1. x( D( x) → C( x)) Premise #1
2. D(a) → C(a) for all possible values of value a. using Universal instantiation from 1
3. x D(x) Premise #2
4. D(a) for some possible values of value a. Existential instantiation from 3
5. C(a) for some possible values of value a. Modus Ponens from 2 and 4
---------------------------------------------------
 x C(x) Existential generalization from 5

EX3: show that the premises “Everyone in this class has taken a course in computer science” and “Everyone is
a student in this class” imply the conclusion “Everyone has taken a course in computer science”.

D(x) : x in this class

C(x) : x has taken a course in computer science.

Premises:
1. x( D( x) → C( x)) Premise #1
3. x D(x) Premise #2

Sol:
1. x( D( x) → C( x)) Premise #1
2. D(a) → C(a) for all possible values of value a. using Universal instantiation from 1
3. x D(x) Premise #2
4. D(a) for all possible values of value a. Universal instantiation from 3
5. C(a) for all possible values of value a. Modus Ponens from 2 and 4
---------------------------------------------------
 x C(x) Universal generalization from 5

28
7. Introduction to Proofs

Methods Of proofs
1. Direct Proof
• The implication P→Q can be proved by showing that if P is true then Q must also be true.
• Integer n is even if there exists an integer K such that n=2K
• Integer n is Odd if there exists an integer K such that n=2K+1 or n =2K-1

Ex: Give a direct proof of the theorem “if n is an odd integer, then n2 is an odd integer”
p→Q
Sol:
1. Assume n is odd. n = 2K+1
2. It follows that n = (2K+1)2 = 4K2+4K + 1 = 2(2K2+2K) + 1= 2W+1, where W= 2K2+2K is an integer
2

n2 =2W+1 is also odd

5. therefore, n2 is odd

2. Indirect Proof
• The implication P→ Q is equivalent to it’s contrapositive  Q→  P
• To prove that P→ Q is true we should prove that  Q→  P is true

Ex: Give indirect proof of the theorem “if 3n+ 2 is odd, then n is odd”
First, you need to change the theorem to become: “if n is even, then 3n+2 is even”
1. Assume that n is even so n =2K
2. 3n+ 2 = 3(2K) + 2 = 6K + 2 = 2(3K + 1) so it is even
3. If n is even then 3n + 2 is even,
So, if 3n+2 is odd then n is odd

3. Vacuous proof. The hypothesis is always False → the theorem is always True
Ex.: Show that the proposition P(0) is true, where P(n) is “If n > 1, then n2 > n” and the domain
consists of all integers.
Solution: Note that P(0) is “If 0 > 1, then 02 >0.” We can show P(0) using a vacuous
proof. Indeed, the hypothesis 0 > 1 is false. This tells us that P(0) is automatically true.

4. Trivial proof. The conclusion is always True → the theorem is always True
Ex.: Let P(n) be “If a and b are positive integers with a ≥ b, then an ≥ bn,” where the domain consists
of all nonnegative integers. Show that P (0) is true.
Solution: The proposition P (0) is “If a ≥ b, then a0 ≥ b0.” Because a0 = b0 = 1, the conclusion
of the conditional statement “If a ≥ b, then a0 ≥ b0” is true. Hence, this conditional statement,
which is P (0), is true. This is an example of a trivial proof. Note that the hypothesis, which is
the statement “a ≥ b,” was not needed in this proof

29
5. Prove by Contradiction
Ex: proof by contradiction that “if n is an odd integer, then n2 is an odd integer”
1. assume n is even but n2 is an odd integer ~p→q
2. n = 2K ~p
3. n2 = 4K2 = 2(2 K2) it is even ~q
4. n2 cannot be odd and even at the same time.
So, by contradiction if n is even then n2 is even.
So, if n is odd then n2 is odd.

6. Proof by cases
P1  P2  P3 ….. Pn → Q  P1 → Q  P2 →Q ….. Pn → Q
Each one of these is called a case. We need to prove them all

Ex1: Use proof by cases to show that: |xy|=|x||y|

Case P1: x>=0  y >=0
Case P2: x>=0  y <0
Case P3: x<0  y >=0
Case P4: x<0  y <0
Case Q: |x||y|
We need to show that
P1→Q  P2→Q  P3→Q  P4→Q
T  T  T  T =T

Ex2: Use proof by cases to show that: if n is even or odd integer then 2n+3 is odd.
Ex3: Prove that if n is an integer and it is not divisible by 3, then n2 is not divisible by 3.

30