Predicate Logic

Module - II

S. Devi Yamini

July 30, 2020

Module - II July 30, 2020 1 / 35

Overview

1 Motivation

Module - II July 30, 2020 2 / 35

Overview

1 Motivation

2 Predicates
Quantifiers
Free and bound variables
Rules of inference

Module - II July 30, 2020 2 / 35

Motivation

Limitation of Propositional Logic

(-) The statements Peter is a man, John is a man, Raj is a man can be
represented by propositional variables P, Q, and R respectively. But it
is very difficult to identify the similarities between P, Q, and R.

Module - II July 30, 2020 3 / 35

Motivation

Limitation of Propositional Logic

(-) The statements Peter is a man, John is a man, Raj is a man can be
represented by propositional variables P, Q, and R respectively. But it
is very difficult to identify the similarities between P, Q, and R.
(-) Every CSE student must study discrete mathematics. Jack is a CSE
student. So Jack must study discrete mathematics. This cannot be
expressed with propositional logic

Module - II July 30, 2020 3 / 35

Motivation

Limitation of Propositional Logic

(-) The statements Peter is a man, John is a man, Raj is a man can be
represented by propositional variables P, Q, and R respectively. But it
is very difficult to identify the similarities between P, Q, and R.
(-) Every CSE student must study discrete mathematics. Jack is a CSE
student. So Jack must study discrete mathematics. This cannot be
expressed with propositional logic
(-) All students are good is not a proposition. Whereas these can be
handled by predicate logic

Module - II July 30, 2020 3 / 35

Motivation

Limitation of Propositional Logic

(-) The statements Peter is a man, John is a man, Raj is a man can be
represented by propositional variables P, Q, and R respectively. But it
is very difficult to identify the similarities between P, Q, and R.
(-) Every CSE student must study discrete mathematics. Jack is a CSE
student. So Jack must study discrete mathematics. This cannot be
expressed with propositional logic
(-) All students are good is not a proposition. Whereas these can be
handled by predicate logic

Predicate logic
Predicate Logic is a logical extension of propositional logic. Also known as
First order logic.

Module - II July 30, 2020 3 / 35

Predicates

Predicate/ Propositional function

is a statement that contains variables and that may be true or false
depending on the values of these variables.

Module - II July 30, 2020 4 / 35

Predicates

Predicate/ Propositional function

is a statement that contains variables and that may be true or false
depending on the values of these variables.
Example
Consider the statement Rajith reads the book
Subject is Ranjith

Module - II July 30, 2020 4 / 35

Predicates

Predicate/ Propositional function

is a statement that contains variables and that may be true or false
depending on the values of these variables.
Example
Consider the statement Rajith reads the book
Subject is Ranjith
Predicate is reads the book

Module - II July 30, 2020 4 / 35

Predicates

Predicate/ Propositional function

is a statement that contains variables and that may be true or false
depending on the values of these variables.
Example
Consider the statement Rajith reads the book
Subject is Ranjith
Predicate is reads the book

Example
Consider the statement x is greater than 3
Subject is x
Predicate is is greater than 3

Module - II July 30, 2020 4 / 35

Predicates

Example
Let P(x) denote x 2 is greater than x
where
P is the predicate is greater than and
x is the variable.

Module - II July 30, 2020 5 / 35

Predicates

Example
Let P(x) denote x 2 is greater than x
where
P is the predicate is greater than and
x is the variable.
Assigning a value to x, P(x) becomes a proposition and has truth value.

Module - II July 30, 2020 5 / 35

Predicates

Example
Let P(x) denote x 2 is greater than x
where
P is the predicate is greater than and
x is the variable.
Assigning a value to x, P(x) becomes a proposition and has truth value.
P(5) is the statement 25 is greater than 5. Hence P(5) is true.

Module - II July 30, 2020 5 / 35

More examples

1 Let Prime(x) : x is a prime number

Prime(3) - True
Prime(4) - False

Module - II July 30, 2020 6 / 35

More examples

1 Let Prime(x) : x is a prime number

Prime(3) - True
Prime(4) - False
2 Let C (x, y ) : x is the capital of y
C (India,New Delhi)
C (Tokyo, Japan)

Module - II July 30, 2020 6 / 35

More examples

1 Let Prime(x) : x is a prime number

Prime(3) - True
Prime(4) - False
2 Let C (x, y ) : x is the capital of y
C (India,New Delhi)
C (Tokyo, Japan)
3 Let E (x, y , z) :x + y = z
E (2, 3, 5)
E (4, 4, 17)

Module - II July 30, 2020 6 / 35

More examples

1 Let Prime(x) : x is a prime number

Prime(3) - True
Prime(4) - False
2 Let C (x, y ) : x is the capital of y
C (India,New Delhi)
C (Tokyo, Japan)
3 Let E (x, y , z) :x + y = z
E (2, 3, 5)
E (4, 4, 17)

Domain or Universe of discourse

UOD or Domain of a predicate variable is the collection of all possible
values that the variable may take.

Module - II July 30, 2020 6 / 35

Quantifiers

The statements like Some students are listening, The square of any real
number is non-negative,All men are mortal - need quantifiers

Module - II July 30, 2020 7 / 35

Quantifiers

The statements like Some students are listening, The square of any real
number is non-negative,All men are mortal - need quantifiers
Quantifiers
It specifies the amount or quantity from the domain.

Module - II July 30, 2020 7 / 35

Quantifiers

The statements like Some students are listening, The square of any real
number is non-negative,All men are mortal - need quantifiers
Quantifiers
It specifies the amount or quantity from the domain.
Two quantifiers:
Universal quantification - for all or given any
The symbol is : ∀

Module - II July 30, 2020 7 / 35

Quantifiers

The statements like Some students are listening, The square of any real
number is non-negative,All men are mortal - need quantifiers
Quantifiers
It specifies the amount or quantity from the domain.
Two quantifiers:
Universal quantification - for all or given any
The symbol is : ∀
Example: P(x) is true for every x in the domain D is equivalent to
writing ∀x ∈ D, P(x)

Module - II July 30, 2020 7 / 35

Quantifiers

The statements like Some students are listening, The square of any real
number is non-negative,All men are mortal - need quantifiers
Quantifiers
It specifies the amount or quantity from the domain.
Two quantifiers:
Universal quantification - for all or given any
The symbol is : ∀
Example: P(x) is true for every x in the domain D is equivalent to
writing ∀x ∈ D, P(x)
Try this! The square of any real number is non negative

Module - II July 30, 2020 7 / 35

Quantifiers

Quantifiers
Existential quantification - there exists or for some or there is at least
one
The symbol is : ∃

Module - II July 30, 2020 8 / 35

Quantifiers

Quantifiers
Existential quantification - there exists or for some or there is at least
one
The symbol is : ∃
Example: P(x) is true for at least one x in D is equivalent to writing
∃x ∈ D, P(x)

Module - II July 30, 2020 8 / 35

Quantifiers

Quantifiers
Existential quantification - there exists or for some or there is at least
one
The symbol is : ∃
Example: P(x) is true for at least one x in D is equivalent to writing
∃x ∈ D, P(x)
Try this! Some birds are angry

Module - II July 30, 2020 8 / 35

Quantifiers

Quantifiers
Existential quantification - there exists or for some or there is at least
one
The symbol is : ∃
Example: P(x) is true for at least one x in D is equivalent to writing
∃x ∈ D, P(x)
Try this! Some birds are angry

Try!
1. All rabbits are faster than all tortoises

Module - II July 30, 2020 8 / 35

Quantifiers

Quantifiers
Existential quantification - there exists or for some or there is at least
one
The symbol is : ∃
Example: P(x) is true for at least one x in D is equivalent to writing
∃x ∈ D, P(x)
Try this! Some birds are angry

Try!
1. All rabbits are faster than all tortoises
Domains: R = { Rabbits }, T = { Tortoises }
Predicate: P(x, y ) : x is faster than y where x ∈ R, y ∈ T

Module - II July 30, 2020 8 / 35

Quantifiers

Quantifiers
Existential quantification - there exists or for some or there is at least
one
The symbol is : ∃
Example: P(x) is true for at least one x in D is equivalent to writing
∃x ∈ D, P(x)
Try this! Some birds are angry

Try!
1. All rabbits are faster than all tortoises
Domains: R = { Rabbits }, T = { Tortoises }
Predicate: P(x, y ) : x is faster than y where x ∈ R, y ∈ T
In symbolic notation: ∀x ∈ R, ∀y ∈ T , P(x, y )

Module - II July 30, 2020 8 / 35

Quantifiers

Quantifiers
Existential quantification - there exists or for some or there is at least
one
The symbol is : ∃
Example: P(x) is true for at least one x in D is equivalent to writing
∃x ∈ D, P(x)
Try this! Some birds are angry

Try!
1. All rabbits are faster than all tortoises
Domains: R = { Rabbits }, T = { Tortoises }
Predicate: P(x, y ) : x is faster than y where x ∈ R, y ∈ T
In symbolic notation: ∀x ∈ R, ∀y ∈ T , P(x, y )
2. Every rabbit is faster than some tortoise
3. There is a rabbit which is faster than all tortoises.
Module - II July 30, 2020 8 / 35
Quantifiers

Assume D = {x1 , x2 , . . . , xn }. Then

∀x ∈ D, P(x) ≡ P(x1 ) ∧ P(x2 ) ∧ . . . ∧ P(xn )

Module - II July 30, 2020 9 / 35

Quantifiers

Assume D = {x1 , x2 , . . . , xn }. Then

∀x ∈ D, P(x) ≡ P(x1 ) ∧ P(x2 ) ∧ . . . ∧ P(xn )
∃x ∈ D, P(x) ≡ P(x1 ) ∨ P(x2 ) ∨ . . . ∨ P(xn )

Module - II July 30, 2020 9 / 35

Quantifiers

Assume D = {x1 , x2 , . . . , xn }. Then

∀x ∈ D, P(x) ≡ P(x1 ) ∧ P(x2 ) ∧ . . . ∧ P(xn )
∃x ∈ D, P(x) ≡ P(x1 ) ∨ P(x2 ) ∨ . . . ∨ P(xn )

¬(∃x ∈ D, P(x)) ≡ ∀x ∈ D, ¬P(x)

Module - II July 30, 2020 9 / 35

Quantifiers

Assume D = {x1 , x2 , . . . , xn }. Then

∀x ∈ D, P(x) ≡ P(x1 ) ∧ P(x2 ) ∧ . . . ∧ P(xn )
∃x ∈ D, P(x) ≡ P(x1 ) ∨ P(x2 ) ∨ . . . ∨ P(xn )

¬(∃x ∈ D, P(x)) ≡ ∀x ∈ D, ¬P(x)

¬(∀x ∈ D, P(x)) ≡ ∃x ∈ D, ¬P(x)

Module - II July 30, 2020 9 / 35

Problem 1

Consider P(x) : x + 2 = 2x
UOD : {1, 2, 3}
Then
∀xP(x) is the proposition

Module - II July 30, 2020 10 / 35

Problem 1

Consider P(x) : x + 2 = 2x
UOD : {1, 2, 3}
Then
∀xP(x) is the proposition “For every x such that x + 2 = 2x”
Truth value?

Module - II July 30, 2020 10 / 35

Problem 1

Consider P(x) : x + 2 = 2x
UOD : {1, 2, 3}
Then
∀xP(x) is the proposition “For every x such that x + 2 = 2x”
Truth value? False

Module - II July 30, 2020 10 / 35

Problem 1

Consider P(x) : x + 2 = 2x
UOD : {1, 2, 3}
Then
∀xP(x) is the proposition “For every x such that x + 2 = 2x”
Truth value? False
∃xP(x) is the proposition

Module - II July 30, 2020 10 / 35

Problem 1

Consider P(x) : x + 2 = 2x
UOD : {1, 2, 3}
Then
∀xP(x) is the proposition “For every x such that x + 2 = 2x”
Truth value? False
∃xP(x) is the proposition “There exists x such that x + 2 = 2x ”
Truth value?

Module - II July 30, 2020 10 / 35

Problem 1

Consider P(x) : x + 2 = 2x
UOD : {1, 2, 3}
Then
∀xP(x) is the proposition “For every x such that x + 2 = 2x”
Truth value? False
∃xP(x) is the proposition “There exists x such that x + 2 = 2x ”
Truth value? True

Module - II July 30, 2020 10 / 35

Problem 2
Let UOD is set of integers
N(x) : x is a non-negative integer
E (x) : x is even
O(x) : x is odd
P(x) : x is prime
Express the following sentences in logical expressions:
(a) Every integer is even or odd

Module - II July 30, 2020 11 / 35

Problem 2
Let UOD is set of integers
N(x) : x is a non-negative integer
E (x) : x is even
O(x) : x is odd
P(x) : x is prime
Express the following sentences in logical expressions:
(a) Every integer is even or odd
∀x[E (x) ∨ O(x)]
(b) There exists an even integer

Module - II July 30, 2020 11 / 35

Problem 2
Let UOD is set of integers
N(x) : x is a non-negative integer
E (x) : x is even
O(x) : x is odd
P(x) : x is prime
Express the following sentences in logical expressions:
(a) Every integer is even or odd
∀x[E (x) ∨ O(x)]
(b) There exists an even integer
∃xE (x)

Module - II July 30, 2020 11 / 35

Problem 2
Let UOD is set of integers
N(x) : x is a non-negative integer
E (x) : x is even
O(x) : x is odd
P(x) : x is prime
Express the following sentences in logical expressions:
(a) Every integer is even or odd
∀x[E (x) ∨ O(x)]
(b) There exists an even integer
∃xE (x)
(c) Not all integers are odd

Module - II July 30, 2020 11 / 35

Problem 2
Let UOD is set of integers
N(x) : x is a non-negative integer
E (x) : x is even
O(x) : x is odd
P(x) : x is prime
Express the following sentences in logical expressions:
(a) Every integer is even or odd
∀x[E (x) ∨ O(x)]
(b) There exists an even integer
∃xE (x)
(c) Not all integers are odd
¬∀xO(x) or ∃x¬O(x)

Module - II July 30, 2020 11 / 35

Problem 2
Let UOD is set of integers
N(x) : x is a non-negative integer
E (x) : x is even
O(x) : x is odd
P(x) : x is prime
Express the following sentences in logical expressions:
(a) Every integer is even or odd
∀x[E (x) ∨ O(x)]
(b) There exists an even integer
∃xE (x)
(c) Not all integers are odd
¬∀xO(x) or ∃x¬O(x)
(d) All prime integers are non negative

Module - II July 30, 2020 11 / 35

Problem 2
Let UOD is set of integers
N(x) : x is a non-negative integer
E (x) : x is even
O(x) : x is odd
P(x) : x is prime
Express the following sentences in logical expressions:
(a) Every integer is even or odd
∀x[E (x) ∨ O(x)]
(b) There exists an even integer
∃xE (x)
(c) Not all integers are odd
¬∀xO(x) or ∃x¬O(x)
(d) All prime integers are non negative
∀x[P(x) → N(x)]

Module - II July 30, 2020 11 / 35

Problem 2
Let UOD is set of integers
N(x) : x is a non-negative integer
E (x) : x is even
O(x) : x is odd
P(x) : x is prime
Express the following sentences in logical expressions:
(a) Every integer is even or odd
∀x[E (x) ∨ O(x)]
(b) There exists an even integer
∃xE (x)
(c) Not all integers are odd
¬∀xO(x) or ∃x¬O(x)
(d) All prime integers are non negative
∀x[P(x) → N(x)]
(e) The only even prime is two

Module - II July 30, 2020 11 / 35

Problem 2
Let UOD is set of integers
N(x) : x is a non-negative integer
E (x) : x is even
O(x) : x is odd
P(x) : x is prime
Express the following sentences in logical expressions:
(a) Every integer is even or odd
∀x[E (x) ∨ O(x)]
(b) There exists an even integer
∃xE (x)
(c) Not all integers are odd
¬∀xO(x) or ∃x¬O(x)
(d) All prime integers are non negative
∀x[P(x) → N(x)]
(e) The only even prime is two
∀x[(E (x) ∧ P(x)) → (x = 2)]
Module - II July 30, 2020 11 / 35
Problem 3
Translate each of the following sentences into logical expression:
Not all cars have carburetors

Module - II July 30, 2020 12 / 35

Problem 3
Translate each of the following sentences into logical expression:
Not all cars have carburetors
Let car (x) : x is a car , carburetors(x) : x has carburetor
¬∀x[car (x) → carburetors(x)]

Module - II July 30, 2020 12 / 35

Problem 3
Translate each of the following sentences into logical expression:
Not all cars have carburetors
Let car (x) : x is a car , carburetors(x) : x has carburetor
¬∀x[car (x) → carburetors(x)]
Some people are religious or pious

Module - II July 30, 2020 12 / 35

Problem 3
Translate each of the following sentences into logical expression:
Not all cars have carburetors
Let car (x) : x is a car , carburetors(x) : x has carburetor
¬∀x[car (x) → carburetors(x)]
Some people are religious or pious
Let R(x) : x is religious, P(x) : x is pious
∃x(R(x) ∨ P(x))

Module - II July 30, 2020 12 / 35

Problem 3
Translate each of the following sentences into logical expression:
Not all cars have carburetors
Let car (x) : x is a car , carburetors(x) : x has carburetor
¬∀x[car (x) → carburetors(x)]
Some people are religious or pious
Let R(x) : x is religious, P(x) : x is pious
∃x(R(x) ∨ P(x))
No dogs are intelligent

Module - II July 30, 2020 12 / 35

Problem 3
Translate each of the following sentences into logical expression:
Not all cars have carburetors
Let car (x) : x is a car , carburetors(x) : x has carburetor
¬∀x[car (x) → carburetors(x)]
Some people are religious or pious
Let R(x) : x is religious, P(x) : x is pious
∃x(R(x) ∨ P(x))
No dogs are intelligent
∀x(dog (x) → ¬intelligent(x))

Module - II July 30, 2020 12 / 35

Problem 3
Translate each of the following sentences into logical expression:
Not all cars have carburetors
Let car (x) : x is a car , carburetors(x) : x has carburetor
¬∀x[car (x) → carburetors(x)]
Some people are religious or pious
Let R(x) : x is religious, P(x) : x is pious
∃x(R(x) ∨ P(x))
No dogs are intelligent
∀x(dog (x) → ¬intelligent(x))
All that glitters is not gold

Module - II July 30, 2020 12 / 35

Problem 3
Translate each of the following sentences into logical expression:
Not all cars have carburetors
Let car (x) : x is a car , carburetors(x) : x has carburetor
¬∀x[car (x) → carburetors(x)]
Some people are religious or pious
Let R(x) : x is religious, P(x) : x is pious
∃x(R(x) ∨ P(x))
No dogs are intelligent
∀x(dog (x) → ¬intelligent(x))
All that glitters is not gold
∀x(glitter (x) → ¬gold(x))

Module - II July 30, 2020 12 / 35

Problem 3
Translate each of the following sentences into logical expression:
Not all cars have carburetors
Let car (x) : x is a car , carburetors(x) : x has carburetor
¬∀x[car (x) → carburetors(x)]
Some people are religious or pious
Let R(x) : x is religious, P(x) : x is pious
∃x(R(x) ∨ P(x))
No dogs are intelligent
∀x(dog (x) → ¬intelligent(x))
All that glitters is not gold
∀x(glitter (x) → ¬gold(x))
Not all that glitters is gold

Module - II July 30, 2020 12 / 35

Problem 3
Translate each of the following sentences into logical expression:
Not all cars have carburetors
Let car (x) : x is a car , carburetors(x) : x has carburetor
¬∀x[car (x) → carburetors(x)]
Some people are religious or pious
Let R(x) : x is religious, P(x) : x is pious
∃x(R(x) ∨ P(x))
No dogs are intelligent
∀x(dog (x) → ¬intelligent(x))
All that glitters is not gold
∀x(glitter (x) → ¬gold(x))
Not all that glitters is gold
¬∀x(glitter (x) → gold(x))

Module - II July 30, 2020 12 / 35

Problem 3
Translate each of the following sentences into logical expression:
Not all cars have carburetors
Let car (x) : x is a car , carburetors(x) : x has carburetor
¬∀x[car (x) → carburetors(x)]
Some people are religious or pious
Let R(x) : x is religious, P(x) : x is pious
∃x(R(x) ∨ P(x))
No dogs are intelligent
∀x(dog (x) → ¬intelligent(x))
All that glitters is not gold
∀x(glitter (x) → ¬gold(x))
Not all that glitters is gold
¬∀x(glitter (x) → gold(x))
Someone has visited every country in the world except Libya

Module - II July 30, 2020 12 / 35

Problem 3
Translate each of the following sentences into logical expression:
Not all cars have carburetors
Let car (x) : x is a car , carburetors(x) : x has carburetor
¬∀x[car (x) → carburetors(x)]
Some people are religious or pious
Let R(x) : x is religious, P(x) : x is pious
∃x(R(x) ∨ P(x))
No dogs are intelligent
∀x(dog (x) → ¬intelligent(x))
All that glitters is not gold
∀x(glitter (x) → ¬gold(x))
Not all that glitters is gold
¬∀x(glitter (x) → gold(x))
Someone has visited every country in the world except Libya
∃x[Person(x) ∧ ∀y (Country (y ) ∧ y 6= Libya → visited(x, y ))]
Module - II July 30, 2020 12 / 35
Problem 4

Let P(x) and Q(x) be predicates involving an integer valued variable x.

Prove or disprove ∀x(P(x) → Q(x)) is logically equivalent to
∀xP(x) → ∀xQ(x)

Module - II July 30, 2020 13 / 35

Problem 4

Let P(x) and Q(x) be predicates involving an integer valued variable x.

Prove or disprove ∀x(P(x) → Q(x)) is logically equivalent to
∀xP(x) → ∀xQ(x)

Solution
FALSE
Let P(x) : x is even, Q(x) : x + 1 is even.

Module - II July 30, 2020 13 / 35

Problem 4

Let P(x) and Q(x) be predicates involving an integer valued variable x.

Prove or disprove ∀x(P(x) → Q(x)) is logically equivalent to
∀xP(x) → ∀xQ(x)

Solution
FALSE
Let P(x) : x is even, Q(x) : x + 1 is even.
P(2) → Q(2) is false
Hence ∀x(P(x) → Q(x)) is false.

Module - II July 30, 2020 13 / 35

Problem 4

Let P(x) and Q(x) be predicates involving an integer valued variable x.

Prove or disprove ∀x(P(x) → Q(x)) is logically equivalent to
∀xP(x) → ∀xQ(x)

Solution
FALSE
Let P(x) : x is even, Q(x) : x + 1 is even.
P(2) → Q(2) is false
Hence ∀x(P(x) → Q(x)) is false.
On the other hand, ∀xP(x) is false (since all integers are not even)

Module - II July 30, 2020 13 / 35

Problem 4

Let P(x) and Q(x) be predicates involving an integer valued variable x.

Prove or disprove ∀x(P(x) → Q(x)) is logically equivalent to
∀xP(x) → ∀xQ(x)

Solution
FALSE
Let P(x) : x is even, Q(x) : x + 1 is even.
P(2) → Q(2) is false
Hence ∀x(P(x) → Q(x)) is false.
On the other hand, ∀xP(x) is false (since all integers are not even)
Hence ∀xP(x) → ∀xQ(x) is true

Module - II July 30, 2020 13 / 35

Multiple Quantifiers

Consider P(x, y ) : xy = 1
UOD for x is the set of positive integers
UOD for y is the set of real numbers
Then
∀x∀yP(x, y ) :

Module - II July 30, 2020 14 / 35

Multiple Quantifiers

Consider P(x, y ) : xy = 1
UOD for x is the set of positive integers
UOD for y is the set of real numbers
Then
∀x∀yP(x, y ) : For every positive integer x and for every real number
y , xy = 1.

Module - II July 30, 2020 14 / 35

Multiple Quantifiers

Consider P(x, y ) : xy = 1
UOD for x is the set of positive integers
UOD for y is the set of real numbers
Then
∀x∀yP(x, y ) : For every positive integer x and for every real number
y , xy = 1.
What is the truth value of this?

Module - II July 30, 2020 14 / 35

Multiple Quantifiers

Consider P(x, y ) : xy = 1
UOD for x is the set of positive integers
UOD for y is the set of real numbers
Then
∀x∀yP(x, y ) : For every positive integer x and for every real number
y , xy = 1.
What is the truth value of this? false

Module - II July 30, 2020 14 / 35

Multiple Quantifiers

Consider P(x, y ) : xy = 1
UOD for x is the set of positive integers
UOD for y is the set of real numbers
Then
∀x∀yP(x, y ) : For every positive integer x and for every real number
y , xy = 1.
What is the truth value of this? false
∀x∃yP(x, y ):

Module - II July 30, 2020 14 / 35

Multiple Quantifiers

Consider P(x, y ) : xy = 1
UOD for x is the set of positive integers
UOD for y is the set of real numbers
Then
∀x∀yP(x, y ) : For every positive integer x and for every real number
y , xy = 1.
What is the truth value of this? false
∀x∃yP(x, y ): For every positive integer x, there is a real number y
such that xy = 1.

Module - II July 30, 2020 14 / 35

Multiple Quantifiers

Consider P(x, y ) : xy = 1
UOD for x is the set of positive integers
UOD for y is the set of real numbers
Then
∀x∀yP(x, y ) : For every positive integer x and for every real number
y , xy = 1.
What is the truth value of this? false
∀x∃yP(x, y ): For every positive integer x, there is a real number y
such that xy = 1.
What is the truth value of this?

Module - II July 30, 2020 14 / 35

Multiple Quantifiers

Consider P(x, y ) : xy = 1
UOD for x is the set of positive integers
UOD for y is the set of real numbers
Then
∀x∀yP(x, y ) : For every positive integer x and for every real number
y , xy = 1.
What is the truth value of this? false
∀x∃yP(x, y ): For every positive integer x, there is a real number y
such that xy = 1.
What is the truth value of this? true

Module - II July 30, 2020 14 / 35

Multiple Quantifiers

Consider P(x, y ) : xy = 1
UOD for x is the set of positive integers
UOD for y is the set of real numbers
Then
∀x∀yP(x, y ) : For every positive integer x and for every real number
y , xy = 1.
What is the truth value of this? false
∀x∃yP(x, y ): For every positive integer x, there is a real number y
such that xy = 1.
What is the truth value of this? true
∃y ∀xP(x, y ):

Module - II July 30, 2020 14 / 35

Multiple Quantifiers

Consider P(x, y ) : xy = 1
UOD for x is the set of positive integers
UOD for y is the set of real numbers
Then
∀x∀yP(x, y ) : For every positive integer x and for every real number
y , xy = 1.
What is the truth value of this? false
∀x∃yP(x, y ): For every positive integer x, there is a real number y
such that xy = 1.
What is the truth value of this? true
∃y ∀xP(x, y ): There exists a real number y such that, for every
positive integer x, xy = 1.

Module - II July 30, 2020 14 / 35

Multiple Quantifiers

Consider P(x, y ) : xy = 1
UOD for x is the set of positive integers
UOD for y is the set of real numbers
Then
∀x∀yP(x, y ) : For every positive integer x and for every real number
y , xy = 1.
What is the truth value of this? false
∀x∃yP(x, y ): For every positive integer x, there is a real number y
such that xy = 1.
What is the truth value of this? true
∃y ∀xP(x, y ): There exists a real number y such that, for every
positive integer x, xy = 1.
What is the truth value of this?

Module - II July 30, 2020 14 / 35

Multiple Quantifiers

Consider P(x, y ) : xy = 1
UOD for x is the set of positive integers
UOD for y is the set of real numbers
Then
∀x∀yP(x, y ) : For every positive integer x and for every real number
y , xy = 1.
What is the truth value of this? false
∀x∃yP(x, y ): For every positive integer x, there is a real number y
such that xy = 1.
What is the truth value of this? true
∃y ∀xP(x, y ): There exists a real number y such that, for every
positive integer x, xy = 1.
What is the truth value of this? false

Module - II July 30, 2020 14 / 35

Example

If R(x, y ) : x relies upon y , express the following in unambiguous English:

∀x∃yR(x, y )

Module - II July 30, 2020 15 / 35

Example

If R(x, y ) : x relies upon y , express the following in unambiguous English:

∀x∃yR(x, y )
Everyone has someone to rely on

Module - II July 30, 2020 15 / 35

Example

If R(x, y ) : x relies upon y , express the following in unambiguous English:

∀x∃yR(x, y )
Everyone has someone to rely on

∃y ∀xR(x, y )

Module - II July 30, 2020 15 / 35

Example

If R(x, y ) : x relies upon y , express the following in unambiguous English:

∀x∃yR(x, y )
Everyone has someone to rely on

∃y ∀xR(x, y )
There exists a person whom everyone relies upon

Module - II July 30, 2020 15 / 35

Example

If R(x, y ) : x relies upon y , express the following in unambiguous English:

∀x∃yR(x, y )
Everyone has someone to rely on

∃y ∀xR(x, y )
There exists a person whom everyone relies upon

∃x∀yR(x, y )

Module - II July 30, 2020 15 / 35

Example

If R(x, y ) : x relies upon y , express the following in unambiguous English:

∀x∃yR(x, y )
Everyone has someone to rely on

∃y ∀xR(x, y )
There exists a person whom everyone relies upon

∃x∀yR(x, y )
There exists a person who relies upon everyone

Module - II July 30, 2020 15 / 35

Example

If R(x, y ) : x relies upon y , express the following in unambiguous English:

∀x∃yR(x, y )
Everyone has someone to rely on

∃y ∀xR(x, y )
There exists a person whom everyone relies upon

∃x∀yR(x, y )
There exists a person who relies upon everyone

∀y ∃xR(x, y )

Module - II July 30, 2020 15 / 35

Example

If R(x, y ) : x relies upon y , express the following in unambiguous English:

∀x∃yR(x, y )
Everyone has someone to rely on

∃y ∀xR(x, y )
There exists a person whom everyone relies upon

∃x∀yR(x, y )
There exists a person who relies upon everyone

∀y ∃xR(x, y )
Everyone has someone who relies upon them

Module - II July 30, 2020 15 / 35

Ordering Quantifiers

1 ∀x∀yP(x, y ) ≡ ∀y ∀xP(x, y )

Module - II July 30, 2020 16 / 35

Ordering Quantifiers

1 ∀x∀yP(x, y ) ≡ ∀y ∀xP(x, y )

2 ∃x∃yP(x, y ) ≡ ∃y ∃xP(x, y )

Module - II July 30, 2020 16 / 35

Ordering Quantifiers

1 ∀x∀yP(x, y ) ≡ ∀y ∀xP(x, y )

2 ∃x∃yP(x, y ) ≡ ∃y ∃xP(x, y )

3 ∀x∃yP(x, y ) 6= ∃y ∀xP(x, y )

Module - II July 30, 2020 16 / 35

An illustration

Let us consider UOD: set of all humans

P(x, y ) : x runs faster than y

Module - II July 30, 2020 17 / 35

An illustration

Let us consider UOD: set of all humans

P(x, y ) : x runs faster than y
∀x∃yP(x, y ) -

Module - II July 30, 2020 17 / 35

An illustration

Let us consider UOD: set of all humans

P(x, y ) : x runs faster than y
∀x∃yP(x, y ) - Every one runs faster than some one.
∃y ∀xP(x, y ) -

Module - II July 30, 2020 17 / 35

An illustration

Let us consider UOD: set of all humans

P(x, y ) : x runs faster than y
∀x∃yP(x, y ) - Every one runs faster than some one.
∃y ∀xP(x, y ) - There is a person who runs slower than every other
person.

Module - II July 30, 2020 17 / 35

Free and bound variable

In a formula with ∀xP(x) or ∃xP(x), the variable x is said to be bounded.

Any occurrence of a variable which is not bounded is said to be a free
variable.

Module - II July 30, 2020 18 / 35

Free and bound variable

In a formula with ∀xP(x) or ∃xP(x), the variable x is said to be bounded.

Any occurrence of a variable which is not bounded is said to be a free
variable.

Example
∀x P(x, y ) - x is bound whereas y is a free variable

Module - II July 30, 2020 18 / 35

Free and bound variable

In a formula with ∀xP(x) or ∃xP(x), the variable x is said to be bounded.

Any occurrence of a variable which is not bounded is said to be a free
variable.

Example
∀x P(x, y ) - x is bound whereas y is a free variable
∀x(P(x) → (∃y )R(x, y )) - x, y are bound variables

Module - II July 30, 2020 18 / 35

Free and bound variable

In a formula with ∀xP(x) or ∃xP(x), the variable x is said to be bounded.

Any occurrence of a variable which is not bounded is said to be a free
variable.

Example
∀x P(x, y ) - x is bound whereas y is a free variable
∀x(P(x) → (∃y )R(x, y )) - x, y are bound variables
∃x(P(x) ∧ Q(x)) - x is a bound variable

Module - II July 30, 2020 18 / 35

Free and bound variable

In a formula with ∀xP(x) or ∃xP(x), the variable x is said to be bounded.

Any occurrence of a variable which is not bounded is said to be a free
variable.

Example
∀x P(x, y ) - x is bound whereas y is a free variable
∀x(P(x) → (∃y )R(x, y )) - x, y are bound variables
∃x(P(x) ∧ Q(x)) - x is a bound variable
(∃x)P(x) ∧ Q(x) - The x occuring in P(x) is bound. But the x
occuring in Q(x) is free.

Module - II July 30, 2020 18 / 35

Problem 5
What is the negation of ∀x ∃y [(p(x, y ) ∧ q(x, y )) → r (x, y )]
Solution
¬[∀x ∃y [(p(x, y ) ∧ q(x, y )) → r (x, y )]]

Module - II July 30, 2020 19 / 35

Problem 5
What is the negation of ∀x ∃y [(p(x, y ) ∧ q(x, y )) → r (x, y )]
Solution
¬[∀x ∃y [(p(x, y ) ∧ q(x, y )) → r (x, y )]]

⇔ ∃x[¬∃y [(p(x, y ) ∧ q(x, y )) → r (x, y )]]

Module - II July 30, 2020 19 / 35

Problem 5
What is the negation of ∀x ∃y [(p(x, y ) ∧ q(x, y )) → r (x, y )]
Solution
¬[∀x ∃y [(p(x, y ) ∧ q(x, y )) → r (x, y )]]

⇔ ∃x[¬∃y [(p(x, y ) ∧ q(x, y )) → r (x, y )]]

⇔ ∃x∀y ¬[(p(x, y ) ∧ q(x, y )) → r (x, y )]

Module - II July 30, 2020 19 / 35

Problem 5
What is the negation of ∀x ∃y [(p(x, y ) ∧ q(x, y )) → r (x, y )]
Solution
¬[∀x ∃y [(p(x, y ) ∧ q(x, y )) → r (x, y )]]

⇔ ∃x[¬∃y [(p(x, y ) ∧ q(x, y )) → r (x, y )]]

⇔ ∃x∀y ¬[(p(x, y ) ∧ q(x, y )) → r (x, y )]

⇔ ∃x∀y ¬[¬[p(x, y ) ∧ q(x, y )] ∨ r (x, y )]

Module - II July 30, 2020 19 / 35

Problem 5
What is the negation of ∀x ∃y [(p(x, y ) ∧ q(x, y )) → r (x, y )]
Solution
¬[∀x ∃y [(p(x, y ) ∧ q(x, y )) → r (x, y )]]

⇔ ∃x[¬∃y [(p(x, y ) ∧ q(x, y )) → r (x, y )]]

⇔ ∃x∀y ¬[(p(x, y ) ∧ q(x, y )) → r (x, y )]

⇔ ∃x∀y ¬[¬[p(x, y ) ∧ q(x, y )] ∨ r (x, y )]

⇔ ∃x∀y [¬¬[p(x, y ) ∧ q(x, y )] ∧ ¬r (x, y )]

Module - II July 30, 2020 19 / 35

Problem 5
What is the negation of ∀x ∃y [(p(x, y ) ∧ q(x, y )) → r (x, y )]
Solution
¬[∀x ∃y [(p(x, y ) ∧ q(x, y )) → r (x, y )]]

⇔ ∃x[¬∃y [(p(x, y ) ∧ q(x, y )) → r (x, y )]]

⇔ ∃x∀y ¬[(p(x, y ) ∧ q(x, y )) → r (x, y )]

⇔ ∃x∀y ¬[¬[p(x, y ) ∧ q(x, y )] ∨ r (x, y )]

⇔ ∃x∀y [¬¬[p(x, y ) ∧ q(x, y )] ∧ ¬r (x, y )]

⇔ ∃x∀y [(p(x, y ) ∧ q(x, y )) ∧ ¬r (x, y )]

Module - II July 30, 2020 19 / 35
Rules of inference

Name Rule
Universal Specification or ∀xP(x)
Instantiation
∴ P(c)
Universal Generalization P(c) for arbitrary member c of the universe

∴ ∀xP(x)
Existential Generalization P(c) for some member c of the universe

∴ ∃xP(x)
Existential Specification or ∃xP(x)
Instantiation
∴ P(c)
Table 1: Rules of Inference

Module - II July 30, 2020 20 / 35

Illustration

Example
Everyone who takes some fruit daily is healthy. Ramya is not healthy.
Therefore, Ramya does not take fruit daily.

Module - II July 30, 2020 21 / 35

Illustration

Example
Everyone who takes some fruit daily is healthy. Ramya is not healthy.
Therefore, Ramya does not take fruit daily.
To check the validity of the above argument, let
P(x) : x takes fruit daily
Q(x) : x is healthy

Module - II July 30, 2020 21 / 35

Illustration

Example
Everyone who takes some fruit daily is healthy. Ramya is not healthy.
Therefore, Ramya does not take fruit daily.
To check the validity of the above argument, let
P(x) : x takes fruit daily
Q(x) : x is healthy
Premises of the given argument are
∀x(P(x) → Q(x))
¬Q(Ramya)
Conclusion is
¬P(Ramya)

Module - II July 30, 2020 21 / 35

Illustration contd.

Example
Steps Logical Statement Reason
1 ¬Q(Ramya) Rule P
2 ∀x(P(x) → Q(x)) Rule P
3 P(Ramya) → Q(Ramya) Rule T, Universal specification of (2)
4 ¬P(Ramya) Rule T, Modus Tollens of (1) and (3)

Module - II July 30, 2020 22 / 35

Another example

Example
Every living thing is a plant or an animal. Rama’s dog is alive and it is not
a plant. All animals have hearts. Therefore, Rama’s dog has a heart.

Module - II July 30, 2020 23 / 35

Another example

Example
Every living thing is a plant or an animal. Rama’s dog is alive and it is not
a plant. All animals have hearts. Therefore, Rama’s dog has a heart.
To check the validity of the above argument, let
L(x) : x is alive
P(x) : x is a plant
A(x) : x is an animal
H(x) : x has a heart

Module - II July 30, 2020 23 / 35

Another example

Example
Every living thing is a plant or an animal. Rama’s dog is alive and it is not
a plant. All animals have hearts. Therefore, Rama’s dog has a heart.
To check the validity of the above argument, let
L(x) : x is alive
P(x) : x is a plant
A(x) : x is an animal
H(x) : x has a heart
Premises are:
∀x[L(x) → (P(x) ∨ A(x))]
L(Rd) ∧ ¬P( Rd)
∀x[A(x) → H(x)]
Conclusion is:
H( Rd ) where Rd denotes Rama’s dog

Module - II July 30, 2020 23 / 35

contd.

Example
Logical Statement Reason
1. L( Rd ) ∧ ¬P( Rd ) Rule P
2. L( Rd ) Rule T, Simplification of (1)
3. ¬P( Rd ) Rule T, Simplification of (1)
4. ∀x[L(x) → (P(x) ∨ A(x))] Rule P
5. L( Rd) → (P( Rd ) ∨ A( Rd )) Rule T, US of (4)
6. (P( Rd ) ∨ A( Rd )) Rule T, Modus Ponens of (2) and (5)
7. A( Rd) Rule T, Disjuctive syllogism of (3) and
8. ∀x[A(x) → H(x)] Rule P
9. A( Rd) → H( Rd ) Rule T, US of (8)
10. H( Rd ) Rule T, Modus Ponens of (7) and (9)

Module - II July 30, 2020 24 / 35

Problem 6

Prove or disprove: All doctors are college graduates. Some doctors are not
golfers. Hence, some golfers are not college graduates.

Module - II July 30, 2020 25 / 35

Problem 6

Prove or disprove: All doctors are college graduates. Some doctors are not
golfers. Hence, some golfers are not college graduates.
Solution
The premises are : ∀x(Doctor (x) → Grad(x))
∃x(Doctor (x) ∧ ¬Golf (x))
Conclusion:
∃x(Golf (x) ∧ ¬Grad(x))
This conclusion is false. (Proof by Venn diagram)

Module - II July 30, 2020 25 / 35

Problem 7

Prove that ∃x(P(x) ∧ Q(x)) =⇒ [(∃xP(x)) ∧ (∃xQ(x))]

Module - II July 30, 2020 26 / 35

Problem 7

Prove that ∃x(P(x) ∧ Q(x)) =⇒ [(∃xP(x)) ∧ (∃xQ(x))]

Solution
Logical Statement Reason
1. ∃x(P(x) ∧ Q(x)) Rule P
2. P(c) ∧ Q(c) for some c Rule T, ES of (1)
3. P(c) for some c Rule T, Simplification of (2)
4. Q(c) for some c Rule T, Simplification of (2)
5. ∃xP(x) Rule T, EG of (3)
6. ∃xQ(x) Rule T, EG of (4)
7. (∃xP(x)) ∧ (∃xQ(x)) Rule T, Conjunction of (5) and (6)

Module - II July 30, 2020 26 / 35

Problem 8
Prove that [∀x(P(x) ∨ Q(x))] =⇒ [∀xP(x) ∨ ∃xQ(x)]
Solution
We prove this result by contradiction. So, the additional premise is
¬[∀xP(x) ∨ ∃xQ(x)] ≡ ∃x¬P(x) ∧ ∀x¬Q(x)

Logical Statement Reason

1. ∃x¬P(x) ∧ ∀x¬Q(x) Rule P
2. ∃x¬P(x) Rule T, Simplification of (1)
3. ¬P(c) for some c Rule T, ES of (2)
4. ∀x¬Q(x) Rule T, Simplification of (1)
5. ¬Q(c) Rule T, US of (4)
6. ∀x(P(x) ∨ Q(x)) Rule P
7. P(c) ∨ Q(c) Rule T, US of (6)
8. Q(c) Rule T, Disjunctive syllogism of (3) and (7)
9. Q(c) ∧ ¬Q(c) Rule T, Conjunction of (5) and (8)
10. False Contradiction.
Module - II July 30, 2020 27 / 35
Problem 9

Show that ∃xM(x) follows logically from the premises ∀x[H(x) → M(x)]
and ∃xH(x)

Solution
Logical Statement Reason
1. ∃xH(x) Rule P
2. H(c) for some c Rule T, ES of (1)
3. ∀x[H(x) → M(x)] Rule P
4. H(c) → M(c) Rule T, US of (3)
5. M(c) for some c Rule T, Modus Ponens of (2) and (4)
6. ∃xM(x) Rule T, EG of (5)

Module - II July 30, 2020 28 / 35

Problem 10

Show that from (a) ∃x(F (x) ∧ S(x)) → [∀y (M(y ) → W (y ))] and (b)
∃y (M(y ) ∧ ¬W (y )), the conclusion ∀x(F (x) → ¬S(x)) follows.

Module - II July 30, 2020 29 / 35

Problem 10

Show that from (a) ∃x(F (x) ∧ S(x)) → [∀y (M(y ) → W (y ))] and (b)
∃y (M(y ) ∧ ¬W (y )), the conclusion ∀x(F (x) → ¬S(x)) follows.

Solution
Logical Statement Reason
1. ∃y (M(y ) ∧ ¬W (y )) Rule P
2. ∃y ¬(¬M(y ) ∨ W (y )) Rule T, logical equivalence of (1)
3. ¬∀y (M(y ) → W (y )) Rule T, logical equivalence of (2)
4. ∃x(F (x) ∧ S(x)) → Rule P
[∀y (M(y ) → W (y ))]
5. ¬∃x(F (x) ∧ S(x)) Rule T, Modus Tollens of (3) and (4)
6. ∀x(¬F (x) ∨ ¬S(x)) Rule T, Logical equivalence of (5)
7. ∀x(F (x) → ¬S(x)) Rule T, Conditional law of (6)

Module - II July 30, 2020 29 / 35

Problem 11

Show the following by constructing derivations:

(a) ∀x[P(x) → (Q(y ) ∧ R(x))] and (b) ∃xP(x).
The conclusion is Q(y ) ∧ ∃x[P(x) ∧ R(x)]

Module - II July 30, 2020 30 / 35

Problem 11

Show the following by constructing derivations:

(a) ∀x[P(x) → (Q(y ) ∧ R(x))] and (b) ∃xP(x).
The conclusion is Q(y ) ∧ ∃x[P(x) ∧ R(x)]

Solution
Logical Statement Reason
1. ∃xP(x) Rule P
2. P(c) for some c Rule T, ES of (1)
3. ∀x[P(x) → (Q(y ) ∧ R(x))] Rule P
4. P(c) → (Q(y ) ∧ R(c)) Rule T, US of (3)
5. Q(y ) ∧ R(c) for some c Rule T, Modus Ponens of (2) and (4
6. (Q(y ) ∧ R(c)) ∧ P(c) for some c Rule T, Addition of (2) and (5)
7. Q(y ) ∧ (R(c) ∧ P(c)) for some c Rule T, Associative law in (6)
8. Q(y ) ∧ ∃x(R(x) ∧ P(x)) Rule T, EG of (7)

Module - II July 30, 2020 30 / 35

Problem 12
Show that ∃xP(x) → ∀x((P(x) ∨ Q(x) → R(x)), ∃xP(x), ∃xQ(x) ⇒
∃x∃y (R(x) ∧ R(y ))

Module - II July 30, 2020 31 / 35

Problem 12
Show that ∃xP(x) → ∀x((P(x) ∨ Q(x) → R(x)), ∃xP(x), ∃xQ(x) ⇒
∃x∃y (R(x) ∧ R(y ))
Solution
Logical Statement Reason
1. ∃xP(x) → Rule P
∀x((P(x) ∨ Q(x)) → R(x))
2. ∃xP(x) Rule P
3. ∀x((P(x) ∨ Q(x)) → R(x)) Rule T, Modus Ponens of (1) an
4. ∀x((P(x) → R(x)) ∧ (Q(x) → R(x))) Rule T, Logical Equivalence of (
5. ∀x(P(x) → R(x)) Rule T, Simplification of (4)
6. ∀x(Q(x) → R(x)) Rule T, Simplification of (4)
7. P(a) for some a Rule T, ES of (2)
8. ∃xQ(x) Rule P
9. Q(b) for some b Rule T, ES of (5)
10. P(a) → R(a) Rule T,US of (5)

Module - II July 30, 2020 31 / 35

contd.

Solution
Logical Statement Reason
11. Q(b) → R(b) Rule T,US of (6)
12. R(a) Rule T, Modus Ponens of (7) and (10)
13. R(b) Rule T, Modus Ponens of (9) and (11)
14. R(a) ∧ R(b) Rule T, Conjunction of (12) and (13)
15. ∃x∃y (R(x) ∧ R(y )) Rule T, EG of (14)

Module - II July 30, 2020 32 / 35

Problem 13
Show that
∀x(H(x) → A(x)) ⇒ ∀x(∃y (H(y ) ∧ N(x, y )) → ∃y (A(y ) ∧ N(x, y )))

Module - II July 30, 2020 33 / 35

Problem 13
Show that
∀x(H(x) → A(x)) ⇒ ∀x(∃y (H(y ) ∧ N(x, y )) → ∃y (A(y ) ∧ N(x, y )))
Solution
Let us prove this by contradiction.

Logical Statement Reason

1. ¬∀x(∃y (H(y ) ∧ N(x, y )) → ∃y (A(y ) ∧ N(x, y ))) Premise
2. ∃x(¬(¬∃y (H(y ) ∧ N(x, y )) ∨ ∃y (A(y ) ∧ N(x, y )))) Log. Equi of (1)
3. ∃x(∃y (H(y ) ∧ N(x, y )) ∧ ∀y (¬A(y ) ∨ ¬N(x, y ))) Log. Equi of (2)
4. ∃x∃y (H(y ) ∧ N(x, y )) ∧ ∃x∀y (¬A(y ) ∨ ¬N(x, y )) Log. Equi of (3)
5. ∃x∃y (H(y ) ∧ N(x, y )) Simplification of (4
6. H(b) ∧ N(a, b) ES of (5)
7. ∃x∀y (¬A(y ) ∨ ¬N(x, y )) Simplification of (4
8. ¬A(b) ∨ ¬N(a, b) Rule T, ES and US

Module - II July 30, 2020 33 / 35

contd.

Solution
Logical Statement Reason
9. N(a, b) Rule T, Simplification of (6)
10. ¬A(b) Rule T, Disjunctive syllogism of (8) and (9)
11. ∀x(H(x) → A(x)) Rule P
12. H(b) → A(b) Rule T, US of (11)
13. ¬H(b) Rule T, Modus Tollens of (10) and (12)
14. H(b) Rule T, Simplification of (6)
15. H(b) ∧ ¬H(b) Rule T, Conjunction of (13) and (14)
16. False Contradiction

Module - II July 30, 2020 34 / 35

Try these problems

Check the validity of the following arguments:

1 All integers are rational numbers. Some integers are powers of 2.
Therefore, some rational numbers are powers of 2.

Module - II July 30, 2020 35 / 35

Try these problems

Check the validity of the following arguments:

1 All integers are rational numbers. Some integers are powers of 2.
Therefore, some rational numbers are powers of 2.
2 All men are mortal. Socrates is a man. Therefore, Socrates is mortal.

Module - II July 30, 2020 35 / 35

Try these problems

Check the validity of the following arguments:

1 All integers are rational numbers. Some integers are powers of 2.
Therefore, some rational numbers are powers of 2.
2 All men are mortal. Socrates is a man. Therefore, Socrates is mortal.
3 No junior or senior is enrolled in a physical education class. Sai has
enrolled in a physical education class. Therefore Sai is not a senior.

Module - II July 30, 2020 35 / 35

Try these problems

Check the validity of the following arguments:

1 All integers are rational numbers. Some integers are powers of 2.
Therefore, some rational numbers are powers of 2.
2 All men are mortal. Socrates is a man. Therefore, Socrates is mortal.
3 No junior or senior is enrolled in a physical education class. Sai has
enrolled in a physical education class. Therefore Sai is not a senior.
4 All squares have four sides. Quadrilateral ABCD has four sides.
Therefore quadrilateral ABCD is a square.

Module - II July 30, 2020 35 / 35

Try these problems

Check the validity of the following arguments:

1 All integers are rational numbers. Some integers are powers of 2.
Therefore, some rational numbers are powers of 2.
2 All men are mortal. Socrates is a man. Therefore, Socrates is mortal.
3 No junior or senior is enrolled in a physical education class. Sai has
enrolled in a physical education class. Therefore Sai is not a senior.
4 All squares have four sides. Quadrilateral ABCD has four sides.
Therefore quadrilateral ABCD is a square.
5 Every computer science student takes discrete mathematics. Geethu
is taking discrete mathematics. Therefore, Geethu is a computer
science student.
6 A student in this class has not read the book. Everyone in this class
passed the first exam. Therefore, someone who passed the first exam
has not read the book.

Module - II July 30, 2020 35 / 35