1

Mathematical Logic

Introduction
Logic is the basis on which all the sentences are built. The mathematical theory of logic is
called symbolic logic. This algebraic way of studying the arguments was developed by the
English Mathematician George Boole in the 19th century.

Propositions
A declarative sentence (or assertion) which is either true or false, but not both, is called a
proposition (or statement). The sentences which are interrogative, exclamatory or
imperative in nature are not propositions. Propositions are denoted by the letters p, q, r
etc. If the proposition is true we give it a truth value T (or 1) otherwise F (or 0).

Examples
For example, let us consider the following sentences:
1. p: “It is raining today”. This statement is a declared statement and so it is a
proposition. It may be true or false.
2. q: “Who is there?” This statement is an interrogative statement and not declarative
in nature as it is neither true nor false. So, it is not a proposition.
3. r: “a+b=3”. This statement is not a proposition since it is not true if a=1, b=4 and it
is not false if a=1.5, b=1.5.
4. p: “Kolkata is the capital of West Bengal”. This statement is a proposition because
it is a declared statement which is true.
5. q: “Get out from here”. This statement is not a declarative statement. So, it is not a
proposition.
6. r: “2+2=3”. This statement is a proposition which is false.

Exercise:
Identify which of the following statements are propositions:
(i) 2026 is a leap year (ii) Sun rises in the west.
(iii) P(x): x+6=7 (iv) P(5): 5+6=2
(v) Apples are oranges (vi) Grapes are black
(vii) Two and two makes 4 (viii) x>10
(ix) Open the door (x) Are you tired?

Truth value of a proposition

A proposition has two possible values True (T) or False (F). This means that if a
proposition is true, then the truth value of that proposition is true, denoted by T or 1. If
the proposition is false, the truth value is said to be false, denoted by F or 0.

Examples Let us consider the following propositions:

1. p: 3+8=12. This proposition is false. So, p takes the truth value F or 0.

 2

2. q:”distance travelled by an object is the product of its speed and time”. This
proposition is true. So, the truth value of q is T or 1.

The symbols p,q,r,...etc. are also known as propositional variables since they take two
different values T or F. The field of logic that deals with propositions is called
propositional logic or propositional calculus.
The propositions which do not contain any logical operators or connectives (to be
introduced in the next section) are called simple (primary or atomic) propositions. The
mathematical statements constructed by connecting one or more simple propositions are
called compound (molecular or complex) propositions.

Truth Table

The table which displays all the truth vales assumed by proposition is known as truth table.
For example for the proposition p the truth table is

p
T
F

In particular, truth tables can be used to show whether a propositional expression is true
for all legitimate input values, that is, logically valid.

Logical connectives

Simple propositions may be modified or combined in various ways to form new

propositions. Different connectives or operators are used to connect these propositions.
The five common Logical Connectives or Operators are:

1. Logical Conjunction (AND)

2. Logical Disjunction (Inclusive OR)
3. Logical Negation (NOT)
4. Logical Implication (Conditional)
5. Logical Biconditional (Double Implication)

Conjunction (AND).
Let p and q are two propositions, then the proposition “p and q” is called conjunction of
p and q. It is denoted by p ∧ q (read as p and q). This is a compound proposition which
is true when both p and q are true (T) and is false (F) otherwise. It is notable that
conjunction has the same properties as intersection.
 3

Examples Let p:” It is raining”, q: “It is cold” be two propositions”. Then the conjunction
of p and q is p ∧ q: “It is raining and cold”.

The truth table of the conjunction p ∧ q is

p q p∧q

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

Examples Consider the following statements:

1. Coochbehar is in India and 2 + 3 = 5
2. Sky is red and 3 + 2 = 5
3. Patna is the capital of Bihar and 10 + 2 = 12
4. Bangalore is in Delhi and 3 +7 = 5

The statements (1) and (3) are true (T) but the statements (2) and (4) are false (F)
Disjunction (OR).
Let p and q are two propositions, then the proposition “p or q” is called disjunction of p
and q. It is denoted by p˅q (read as p or q). This is a compound proposition which is true
when both p and q are false (F) and is true (T) otherwise. Disjunction has the same
property as union. It is also called ‘inclusive or’.

Examples Let p: “Shyam is tall”, q: “Shyam is intelligent” be two propositions. Then the
disjunction of p and q is p ˅ q: “Shyam is tall or he is intelligent”.

The truth table of the disjunction p˅q is

p q p˅q

T T T
T F F
F T F
F F F
 4

Examples Consider the following statements:

1. Coochbehar is in India and 2 + 3 = 5

2. Sky is red and 3 + 2 = 5
3. Patna is the capital of Bihar and 10 + 2 = 12
4. Bangalore is in Delhi and 3 +7 = 5

The statements (1), (2) and (3) are true (T) but the statement (4) is false (F)

Negation (NOT)
Given any proposition p, another proposition formed by writing “It is not the case that”
or “It is false that” before p or by inserting the word ‘not’ suitably in p is called negation
of p. It is denoted by ∼ p (or, ¬p) (read as not p). This is a compound proposition which
is true (T) when p is true and false (F) when p is false.
Examples Let p:” It is hot today” be any proposition, then∼ p is any one of the following
statements.
1. It is not the case that today is hot
2. It is false that today is hot
3. It is not hot today

The truth table for negation ∼ p is

p ∼p

T F
F T

Examples If p: “8 + 2 = 9”, then ∼ p: “8 + 2  9”

Note: ∼ (∼p)  p

Implication (Conditional)

Let p and q are two propositions, then the proposition “if p then q” is called conditional
or implication proposition of p and q. It is denoted by p → q or p ⇒ q (read as p
implies q). The statement p is called the antecedent or premise or hypothesis and the
statement q is called consequent or conclusion. This is a compound proposition which is
false when p is true (T) and q is false (F) and true (T) otherwise.
 5

Examples Let p: “Rahim works hard”, q: “Rahim comes first in Examination” be two
propositions. Then the implication of p and q is
p → q: “If Rahim works hard then he comes first in Examination”.

The truth table of p → q is

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

Examples Let p and q be two propositions, such that

p: Two triangles are congruent
q: Two triangles are similar
Then p → q can be expressed as any one of the statements
1. If two triangles are congruent, then they are similar
2. Two triangles are congruent implies that they are similar
3. Two triangles are congruent only if they are similar
4. The necessary condition for two triangles to be similar is that they are congruent

Biconditional (Double Implication)

Let p and q are two propositions, then the proposition “p if and only if q” or “ if p then q
and if q then p” is called biconditional proposition of p and q. It is denoted by p ↔ q
(read as p if and only if q). This is a compound proposition which is true when p and q
has the same truth values and is false otherwise.

It can be easily verified that p ↔ q is true when both the conditionals p→q and p→q
are true. So, the symbol ↔ is a combination of the symbols → and 
Alternatively, p↔ q is also expressed as “p iff q” and “p is necessary and sufficient for q”.
i.e., p ↔ q is (p → q) ∧ (q→ p)

Examples Let p: “ Birds fly” and q: “Sky is clear” be two propositions. Then the
biconditional of p and q is
 6

p ↔ q: “Birds fly if and only if the sky is clear” or “If the birds fly then the sky is clear
and if the sky is clear then the birds fly”.
The truth table of p ↔ q is

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

Note: The operators ∧, ˅,∼, → and ↔ are known as Connectives.

Converse, Inverse and Contrapositive
Given an if-then statement "if p then q," we can create three related statements:
1. Converse
2. Inverse
3. Contrapositive
Converse
We know that a conditional statement consists of two parts, a hypothesis in the “if” clause
and a conclusion in the “then” clause. For example, let us consider the propositions
p: It rains
q: The boys cancel school.

Here, the proposition p is hypothesis and the proposition q is the conclusion.

The conditional statement p → q is “If it rains then the boys cancel school”.
To form the converse of the conditional statement, we must interchange the hypothesis p
and the conclusion q. Thus, the converse of “If it rains then the boys cancel school” is "If
the boys cancel school, then it rains". The converse of p → q is symbolically written as q
→ p.

The truth table of q → p is

p q q→p

T T T
T F T
F T F
F F T
 7

Inverse
To form the inverse of the conditional statement, we must take the negation of both the
hypothesis p and the conclusion q.
The inverse of “If it rains then the boys cancel school” is “If it does not rain, then the
boys do not cancel school”. The inverse of p → q is symbolically written as ∼p→∼q.

The truth table of ∼p→∼q is

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

Contrapositive
To form the contrapositive of the conditional statement, we must interchange the
hypothesis p and the conclusion q of the inverse statement.
The contrapositive of "If it rains, then the boys cancel school" is "If they do not cancel
school, then it does not rain." The contrapositive of p → q is symbolically written as
∼q→∼p.

The truth table of ∼q→∼p is

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

Examples Given any conditional statement p → q, the three related statements can be
written as follows:

Statement: If x is positive, then x  0

Converse: If x  0 , then x is positive
Inverse: If x is negative, then x = 0
Contrapositive: If x = 0, then x is negative
 8

Examples Given any conditional statement p → q, the three related statements can be
written as follows:

Statement: If two angles are congruent, then they have the same measure.
Converse: If two angles have the same measure, then they are congruent.
Inverse: If two angles are not congruent, then they do not have the same measure.
Contrapositive: If two angles do not have the same measure, then they are not congruent.

Note: If a statement is true, then the contrapositive is also logically true. If the converse is
true, then the inverse is also logically true.

Exercise:

Write the converse, inverse and contrapositive of the following statements:

(a) If today is Sunday, then it is a holiday.

(b) If 5x+1=11, then x=2.
(c) If it rains today, then I will stay at home.
(d) You will win the match only if you work hard.
(e) I you are intelligent, then you will solve the problem.

Precedence of logical operators

Operator precedence is an ordering of logical operators designed to allow the dropping
of parentheses in any logical expressions. The operator ¬ has higher precedence than ∧.

Operator Precedence
¬ 1
∧ 2
˅ 3
→ 4
↔ 5

Propositional Formula or Statement Formula

A compound proposition P = f(p, q, r,...,) obtained by connecting one or more of the
variables (simple propositions) p,q,r,...by the connectives ∧, ˅,∼, → or ↔ is called a
propositional formula or statement formula.

Examples Let P = f (p, q) = ∼ (∼p ∧ q) be a propositional formula or statement formula

of the variables p and q.
 9

The truth table of a propositional statement f(p, q) = ∼(∼p ∧ q) is

p q ∼p ∼p ∧ q ∼(∼p ∧ q)

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

Examples Let f (p, q, r) = p ∧ (∼q) ˅ r → p is a propositional formula or Statement

Formula of the variables p, q, r.

The truth table of a propositional statement f (p, q, r) = p ∧ (∼q) ˅ r → p is

p Q r ∼q p ∧ (∼q) p ∧ (∼q) ˅ r p ∧ (∼q) ˅ r → p

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

Note: The number of rows in a truth table of a propositional statement is 2n where n is the
number of variables in the propositional statement. For example in the above truth table
of the propositional formula P = f (p, q)= ∼(∼p ∧ q), the number rows is 22 = 4, since, the
formula contains two variables p and [Link] the truth table of the propositional statement p
∧ (∼q) ˅ r → p there are 23 = 8 rows, since, the formula contains three variables p, q and
r.

Logical Equivalence
Two compound propositions P = f1 (p, q, r,...) and Q = f2 (p, q, r,...) are said to be logically
equivalent or simply equivalent, if they have identical truth values, viz. if the truth value of
P is equal to the truth value of Q for every one of the 2n possible sets of truth values
assigned for p, q, r,...This equivalence is denoted by
P  Q (read as P is equivalent to Q).
 10

Examples Let us consider the propositional statements p → q and ∼p ∨ q.

The truth tables of the statements p → q and ∼ p ∨ q are

p q p→q p q ∼p ∼p ∨ q
and
T T T T T F T
T F F T F F F
F T T F T T T
F F T F F T T

We find that the final columns in the truth tables of the statements p → q and
∼ p ∨ q are identical.
Hence, p → q  ∼p ∨ q.
Note: The symbol  is not a connective.

Principal of Duality

The dual of a compound proposition that contains only the logical operators ˅, ˄ and ∼
is the proposition obtained by replacing each ˅ by ˄, each ˄ by ˅, each T by F and each
F by T, where F and T are special variables representing compound propositions that are
tautologies and contradictions respectively. The dual of the proposition P is denoted by
P*.
If P (p, q, r,...)  Q( p, q, r,...), where P and Q are compound propositions, then P* (p,
q, r,...)  Q*( p, q, r,...).

Algebra of Propositions
For any propositions p, q, r the logical connectives ˄, ˅, ∼ obey the laws of Algebra as
shown in the following table

Laws of Algebra of Propositions

Sl Name of law Primal form Dual form
No
1. Idempotent law p˅ p  p p ˄ p p

2. Identity law p˅ F  p p ˄ T p
 11

3. Dominant law p˅ T  T p ˄ F F

4. Complement law p ˅ ∼p  T p ˄ ∼p  F

5. Commutative law p˅q  q˅p p˄q  q˄p

6. Associative law (p ˅ q) ˅ r  p ˅ (q ˅ r) (p ˄ q) ˄ r  p ˄ (q ˄ r)
7. Distributive law
p ˅ (q ˄ r)  (p ˅ q ) ˄ (p˅ r) p ˄ (q ˅ r)  (p ˄ q ) ˅ (p ˄ r)
8. Absorption law
p ˅ (p ˄ q)  p p ˄ (p ˅ q)  p
9. De Morgan’s law
∼ (p ˅ q)  ∼ p ˄ ∼ q ∼ (p ˄ q)  ∼ p ˅ ∼ q

For any propositions p, q, r the equivalences involving conditional ‘→’ are shown in the
following table
Equivalences involving Conditionals
Sl No. Equivalences

1. p→q  ∼p ˅ q

2 p→q  ∼q →∼p

3 p ˅q  ∼p →q

4 p ˄ q  ∼ (p → ∼ q)

5 ∼ (p → q)  p ˄ ∼ q

6 (p → q) ˄ ( p → r)  p → (q ˄ r)

7 (p → r) ˄ (q→ r)  (p ˅ q) → r
8 (p → q) ˅ ( p → r)  p → (q ˅ r)

9 (p → r) ˅ (q→ r)  (p ˄ q) → r
 12

For any propositions p, q, r the equivalences involving Biconditional ‘↔’ are shown in
the following table

Equivalences involving Biconditional

Sl No. Equivalences

1. p ↔ q  (p → q) ˄ ( q → p)
2
p↔ q  ∼p↔∼q
3
p ↔ q  (p ˄ q) ˅ ( ∼ p ˄ ∼ q)
4
∼ (p ↔ q)  p ↔ ∼ q

Truth tables for Equivalences

In this Section we shall verify some laws of Algebra, equivalences involving Conditional
and Biconditional using truth tables
Examples Using truth table we shall verify the distributive law

p ˄ (q ˅ r)  (p ˄ q ) ˅ (p ˄ r)

p ˄ (q ˅ r)

p q r q˅r p ˄ (q ˅ r)

T T T T T
T T F T T
T F T T T
T F F F F
F T T T F
F T F T F
F F T T F
F F F F F
 13

(p ˄ q) ˅ (p ˄ r)

p q r p˄q p˄r (p ˄ q ) ˅ (p ˄ r)

T T T T T T
T T F T F T
T F T F T T
T F F F F F
F T T F F F
F T F F F F
F F T F F F
F F F F F
From the above tables we see that the two propositional statements p ˄ (q ˅ r) and (p ˄ q
) ˅ (p ˄ r) have the same truth tables. Hence,
p ˄ (q ˅ r)  (p ˄ q ) ˅ (p ˄ r)

Examples Using truth table we shall verify the De Morgan’s law

∼ (p ˅ q)  ∼ p ˄ ∼ q

Truth table for ∼ (p ˄ q) is

∼ (p ˅ q)
p q p˅q ∼ (p ˅q)

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

∼p˄∼q
p q ∼p ∼q ∼p˄∼q
 14

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

From the above tables we see that the two propositional statements ∼ (p ˄ q) and ∼ p ˄
∼ q have the same truth tables. Hence,
∼ (p ˅ q)  ∼ p ˄ ∼ q

Examples Using truth table we shall verify

p→q  ∼p ˅ q

p→q

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

∼p˅q

p q ∼p ∼p ˅ q

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

From the above tables we see that the two propositional statements p → q and ∼ p ˅ q
have the same truth tables. Hence,

∼ (p ˅ q)  ∼ p ˄ ∼ q

Example Using truth table we shall verify

 15

p ↔ q  (p → q) ˄ ( q → p)

p↔q
P q p↔q

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

(p → q) ˄ ( q → p)
p q p→ q→p (p → q) ˄ ( q → p)
q
T T T T T
T F F T F
F T T F F
F F T T T

From the above tables we see that the two propositional statements p ↔ q and (p → q) ˄
( q → p) have the same truth tables. Hence,

p ↔ q  (p → q) ˄ ( q → p)

Solved Problems

Problem 1: Let p:’Today is Sunday’ and q: ‘It is hot’ be two propositions. Write the
sentences which describe the compound propositions

(i)q ˄∼ p

(ii)∼ (p ˅ q)
 16

(iii)p ˅ q

Solution. (i) It is hot and today it is not Sunday

(ii) It is not true that Today is Sunday or it is hot

(iii) Today is Sunday or it is hot

Problem 2: Let p:’He is intelligent’ and q: ‘He is fat’ be two propositions. Write each of
the following statements in logical form using the simple propositions p and q.

(i) He is fat but not intelligent

(ii) He is neither fat nor intelligent
(iii) He is intelligent or he is fat
(iv) It is not true that he is intelligent or he is fat
(v) It is not true that he is neither fat nor intelligent
(vi) If he is intelligent then he is fat

Solution. (i) q ˄ ∼ p

(ii) ∼q ˄ ∼ p

(iii) p ˅ q

(iv). ∼ (p ˅ q)

(v). ∼ (∼q ˅∼ p)

(vi) p → q

Problem 3: Let p:’I get a Bachelors degree in Science’, q: ‘I get a job’ and r:’I go to USA’
be three propositions. Write each of the following statements in logical form using the
simple propositions p, q and r. Write the statements corresponding to the following
compound propositions

(i). ∼q →(r ˄ p)

(ii) (p ˅ q) ↔r
(iii)(p˄ ∼ q) →∼r
 17

Solution. (i) If I do not get a job then I go to USA and get a bachelors degree in Science

(ii) I get a Bachelors degree in Science or I get a job if and only if I go to USA

(iii) If I get a Bachelors degree in Science and I do not get a job then I do not go to USA

Problem 4: Write down the negation of the statements

(i) Today is Wednesday

(ii) No one wants to buy my bag
(iii) Every even integer greater than 2 is not prime
(iv) Some people have no ideas

Solution. (i). Today is not Wednesday

(ii) Someone wants to buy my bag
(iii) Some even integer greater than 2 is not prime.
(iv) All people have ideas

Problem 5: Construct the truth table for each of the following compound propositions:

(i) (p ˅ q) → (p ˄ q)
(ii) (p → q) → (q → p)
(iii) (q → ∼ p) ↔ (p ↔ q)
(iv) (p → q) ↔ (∼q → ∼p)

Solution. In the compound proposition (p ˅ q) → (p ˄ q) two simple propositions p and

q are involved. So, there must be 22 = 4 rows in the truth table.

(i) Truth table for (p ˅ q) → (p ˄ q) is

p q p˅q p˄q (p ˅ q) → (p ˄ q)

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

(ii)Truth table for (p → q) → (q → p) is

p q p→ q→ (p → q) → (q → p)
q p
 18

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

(iii)Truth table for (q → ∼ p) ↔ (p ↔ q) is

p q ∼p q→∼p p↔q (q → ∼ p) ↔ (p ↔ q)

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

(iv)Truth table for (p → q) ↔ (∼q → ∼p) is

p q ∼p ∼q p→q ∼q → ∼ p (p → q) ↔ (∼q → ∼p)

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

Problem 6:Determine the dual of the following statements

(i) p ˄ (q ˄ r)

(ii) ∼p ˅ ∼q

(iii)(p ˄ ∼ q) ˅ (∼p ˄ q)

(iv) ((∼p ˅ q) ˄ (q ˄ ∼r)) ˅ (p ˅ F), where F is false

Solution (i) The dual of p ˄ (q ˄ r) is p ˅ (q ˅ r)

(ii) The dual of ∼p ˅ ∼q is ∼p ˄ ∼q

(iii) The dual of (p ˄ ∼ q) ˅ (∼p ˄ q) is (p ˅∼ q) ˄ (∼p ˅ q)

 19

(iv) The dual of ((∼p ˅ q) ˄ (q ˄ ∼r)) ˅ (p ˅ F) is

((∼p ˄ q) ˅ (q ˅ ∼r)) ˄ (p ˄T),

Problem 7: Construct the truth table for each of the following compound propositions:

(i) (p→( q → r)) → ((p → q) →( p → r))

(ii) ∼(p˅ ( q ˄ r)) ↔ ((p ˅ q) ˄ ( p → r))
(iii) ((p˄ q) ˅ ∼(r)) ↔ p
(iv) ((p → q) → r) →s

Solution. (i) In the compound proposition (p→ ( q → r)) → ((p → q) →( p → r)) three
simple propositions p, q and r are involved. So, there must be 23 = 8 rows in the truth
table.

Truth table for (p→ ( q → r)) → ((p → q) →( p → r)) is

p q r p→q p→r q→r p→ ( q → r) (p → q) →( p → r) a→b

a b
T T T T T T T T T
T T F T F F F F T
T F T F T T T T T
T F F F F T T T T
F T T T T T T T T
F T F T T F T T T
F F T T T T T T T
F F F T T T T T T

(ii)Truth table for ∼ (p˅ ( q ˄ r)) ↔ ((p ˅ q) ˄ ( p → r))

p q r q ˄ r p˅ ( q ˄ r ) ∼a p˅q p→r (p ˅ q) ˄ ( p → r) ∼a ↔b
a b
T T T T T F T T T F
T T F F T F T F F T
T F T F T F T T T F
T F F F T F T F F T
F T T T T F T T T F
F T F F F T T T T T
F F T F F T F T F F
F F F F F T F T F F
 20

(iii) Truth table for ((p˄ q) ˅ ∼(r)) ↔ p

p q r ∼r p ˄ q (p ˄ q) ˅ ∼r p˄ q) ˅ ∼(r)) ↔ p
T T T F T T T
T T F T T T T
T F T F F F F
T F F T F T T
F T T F F F T
F T F T F T F
F F T F F F T
F F F T F T F

(iv)In the compound proposition ((p → q) → r) →s four simple propositions p, q, r and

s are involved. So, there must be 24 = 16 rows in the truth table.

p q r s p→q (p → q) → r (p → q) → r) →s
T T T T T T T
T T T F T T F
T T F T T F T
T T F F T F T
T F T T F T T
T F T F F T F
T F F T F T T
T F F F F T F
F T T T T T T
F T T F T T F
F T F T T F T
F T F F T F T
F F T T T T T
F F T F T T F
F F F T T F T
F F F F T F T

Note: Every combination of the truth values of every component is chosen according to
some rules. In the first column of the truth table corresponding to the first component,
1 1
we have taken  2 n entries each equal to T, followed by  2 n entries each equal to F.
2 2
1
In the second column corresponding to the second component  2n entries each equal
4
 21

1 n 1
to T have been taken, followed by  2 F’s and again followed by  2n T’s and again
4 4
1 n 1
 2 F’s. In the third column corresponding to the third component  2n T’s and again
4 8
1 n
 2 F’s will be alternatively written starting with T’s and so on.
8

Problem 8: Write the converse, inverse and contrapositive of the following statements

(i) If it is raining, then I feel cold

(ii) If it is raining, then I will take coffee
(iii) If today is independence day, then tomorrow is Thursday

Solution (i). Let us consider the statements

p: It is raining
q: I feel cold

The Converse of the statement is ‘q → p’: If I feel cold, then it is raining

The Inverse of the statement is ‘∼p →∼q’: If it is not raining, then I do not feel cold.
The Contrapositive of the statement is ‘∼q →∼p’: If I do not feel cold, then it is not
raining

(ii) Let us consider the statements

p: It is raining
q: I will take cofee

The Converse of the statement is ‘q → p’: If I take coffee, then it is raining

The Inverse of the statement is ’∼p →∼q’: If it is not raining, then I will not take
coffee”
The Contrapositive of the statement ‘∼q →∼p’: If I do not take coffee, then it is not
raining”

(iii) Let us consider the statements

p: Today is Impendence day
q: Tomorrow is Thursday

The Converse of the statement is ‘q → p’: If tomorrow is Thursday, then today is

Independence day”
The Inverse of the statement is ‘∼p →∼q’: If today is not Independence day, then
tomorrow is not Thursday”
 22

The Contrapositive of the statement is ‘∼q →∼p’: If tomorrow is not Thursday, then
today is not Independence day”

Problem 9: Using truth table prove the equivalences

(i) p → (q ˅ r)  (p → q) ˅ (p → r)
(ii) p ˄( (∼q ˅ r) ˄(∼r ˅ q))  p˄ (q↔ r)

Solution (i) Truth table for p → (q ˅ r) is

p q r q˅r p → (q ˅ r)
T T T T T
T T F T T
T F T T T
T F F F F
F T T T T
F T F T T
F F T T T
F F F F T

Truth table for (p → q) ˅ (p → r) is

p q r p→q p→ r (p → q) ˅ (p → r)

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

Since the truth tables of p→(q ˅ r) and (p → q) ˅ (p → r) are identical so

p→ (q ˅ r)  (p → q) ˅ (p → r)

(iii) Truth table for p ˄ ((∼q ˅ r) ˄ (∼r ˅ q)) is

 23

p q R ∼q ∼r ∼q ˅ r ∼r ˅ q (∼q ˅ r) ˄ (∼r ˅ q) p ˄ (∼q ˅ r) ˄(∼r ˅ q)

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

(ii). Truth table for p ˄ (q↔ r) is

p q r q↔r p ˄ (q↔ r)

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

Since the truth tables of p ˄ ((∼q ˅ r) ˄ (∼r ˅ q)) and p ˄ (q ↔ r) are identical so
p ˄( (∼q ˅ r) ˄(∼r ˅ q))  p˄ (q↔ r)

Problem 10: Without using truth tables, prove the following

(i) (∼p˅ q) ˄ (p ˄ (p ˄ q))  p˄ q

(ii) p →( q→ p)  ∼p → ( p→ q)
(iii) ∼(p ↔ q)  (p ˅ q) ˄∼ (p ˄ q)  (p ˄∼ q) ˅ (∼p ˄ q)
(iv) p → (q ˅ r)  (p → q) ˅ (p → r)

Solution (i).L.H.S =(∼p˅ q) ˄(p˄ (p ˄ q))

 (∼p ˅ q) ˄ (p ˄ p) ˄ q, by associative law

 24

 (∼p ˅ q) ˄ (p ˄ q), by idempotent law

 (p ˄ q) ˄ (∼p ˅ q), by commutative law

 ((p ˄ q) ˄∼p) ˅ ((p ˄ q) ˄ q), by distributive law

 ((∼p ˄ (p ˄ q)) ˅ ((p ˄ q) ˄ q)), by commutative law

 ((∼p ˄ p) ˄ q) ˅ (p ˄ (q ˄ q)), by associative law

 (F ˅ q) ˅ (p ˄ q), by complement and idempotent law

 F ˅ (p ˄ q), by dominant law

 p ˄ q, by dominant law

Also R.H.S= p ˄ q

Hence, (∼p ˅ q) ˄ (p ˄ (p ˄ q))  p ˄ q

(ii) L.H.S = p → (q → p)

 ∼p ˅ (q → p) [as p → q  ∼p ˅ q]

 ∼p ˅ (∼ q ˅ p) [as p → q  ∼p ˅ q)]

 (∼p ˅∼ q) ˅ p, by associative law

 (∼q ˅∼ p) ˅ p, by commutative law

 ∼q ˅ (∼p ˅ p), by associative law

 ∼q ˅ (p ˅∼ p), by commutative law

 ∼q ˅ T, by complement law

 T, by dominant law

Also, R.H.S = ∼p → ( p → q)

 ∼p ˅ (p → q) [as p → q  ∼p ˅ q]
 ∼p ˅ (∼p ˅ q) [as p → q  ∼p ˅ q]

 (∼p ˅ ∼ p) ˅ q , by associative law

 T ˅ q, by complement law
 25

 T, by dominant law

Since, L.H.S = R.H.S so

p → ( q → p)  ∼p → ( p → q)

(iii) L.H.S = ∼ (p ↔ q)

 ∼ ((p → q) ˄ (q → p)) [as p ↔ q  ∼((p →q) ˄ (q → p))]

 ∼ (∼p ˅ q) ˄ (∼ q ˅ p) [as p → q  ∼p ˅ q)]

 ∼ [((∼p ˅ q) ˄ ∼q)) ˅ ((∼p ˅ q) ˄ p)], by distributive law

 ∼ [((∼p ˄ ∼q) ˅ (q ˄ ∼q)) ˅ ((∼p ˄ p) ˅ (q ˄ p))],

by distributive law

 ∼ [((∼p ˄ ∼q) ˅ F)) ˅ ((F ˅ (q ˄ p))], by complement law

 ∼ ((∼p ˄ ∼q) ˅ (q ˄ p)), by identity law

 ∼ (∼ (p ˅ q)) ˅ (q ˄ p)), by De Morgan’s law

 (p ˅ q) ˄ ∼ (q ˄ p), by De Morgan’s law (1)

 (p ˅ q) ˄ (∼ q ˅ ∼ p), by De Morgan’s law

 ((p ˅ q) ˄ ∼ q) ˅ ((p ˅ q) ˄ ∼ p), by distributive law

 ((p ˄ ∼q) ˅ (q ˄∼ q)) ˅ ((p ˄ ∼p) ˅ (q ˄∼ p)),

by distributive law

 ((p ˄ ∼q) ˅ F)) ˅ ((F ˅ (q ˄∼ p)), by complement law

 (p ˄ ∼q) ˅ (q ˄∼ p)), by identity law

 (p ˄ ∼q) ˅ (∼p ˄ q)), by commutative law (2)

From (1) and (2), it follows that

∼ (p ↔ q)  (p˅ q) ˄∼ (p ˄ q)  (p ˄∼ q) ˅ (∼p ˄ q)
 26

(iv) R.H.S = (p → q) ˅ (p → r)

 (p → q) ˅ (p → r)

 (∼p ˅ q) ˅ (∼ p ˅ r) [as p → q  ∼p ˅ q)]

 (q ˅∼p) ˅ (∼ p ˅ r), by commutative law

 q ˅ (∼p ˅ (∼ p ˅ r)), by associative law

 q ˅ ((∼p ˅ ∼ p) ˅ r)), by associative law

 q ˅ (∼p ˅ r)), by idempotent law

 q ˅ ( r ˅ ∼p)), by commutative law

 (q ˅ r )˅ ∼p, by associative law

 ∼p ˅ (q ˅ r), by commutative law

 p → (q ˅ r) [as p → q  ∼p ˅ q]

L.H.S = p → (q ˅ r)

Since, L.H.S = R.H.S so

p → (q ˅ r)  (p → q) ˅ (p → r)

Problem 11: Without using truth tables, prove the following

(i) (p ˄ q) → (p ˅ q) is a tautology
(ii) ∼ (p ˅ q) ˅ (∼p ˄ q) ˅ p is a tautology
(iii) ∼((p ˅ (∼p ˄ q)) ˅ (∼q ˄ p)) ˄ q is a contradiction

Solution (i) (p ˄ q) → (p ˅ q)  ∼ (p ˄ q) ˅ (p ˅ q) [as p → q  ∼p ˅ q) ]

 (∼ p ˅∼q) ˅ (p ˅ q), by De Morgan’s law

 (∼ p ˅ ∼q) ˅ p) ˅ q, by associative law

 (∼ p ˅ (∼q ˅ p)) ˅ q, by associative law

 (∼ p ˅ (p ˅∼ q)) ˅ q, by commutative law

 27

 ((∼ p ˅ p) ˅∼ q) ˅ q, by associative law

 ((T) ˅∼ q) ˅ q, by complement law

 (T ˅ (∼ q ˅ q)), by associative law

 T ˅ T, by complement law

T

Hence, (p ˄ q) → (p ˅ q) is a tautology

(ii)∼ (p ˅ q) ˅ (∼p ˄ q) ˅ p  ((∼ p ˄∼q) ˅ (∼ p ˄ q)) ˅p, by De Morgan’s law

 (∼ p ˄ (∼q ˅ q)) ˅p, by distributive law

 (∼ p ˄ T) ˅ p , by complement law

 ∼ p ˅ p, by identity law

 T, by complement law

Hence, ∼ (p ˅ q) ˅ (∼p ˄ q) ˅ p is a tautology

(iii)∼ ((p ˅ (∼p ˅ q)) ˅ (∼q ˄ p)) ˄ q  ∼ ((p ˅ ∼p) ˅ q)) ˅ (∼q ˄ p)) ˄ q,

by associative law

 ∼ ((T ˅ q)) ˅ (∼q ˄ p)) ˄q,

by complement law

 ∼ (T) ˅ (∼q ˄ p)) ˄q,

by identity law

 ∼( T) ˄ (p˅q)) ˄q ,

by idempotent and complement laws

 ∼(T˄(p˅q)) ˄ q , by dominant law

 ∼(p˅q)) ˄ q , by identity law

 ( ∼p˄∼q) ˄ q , by D’morgan’s law

 ∼p˄F , by complement law

 28

 F , by dominant law

Hence, ∼((p ˅ ((∼p˄q)) ˅ (∼q ˄ p)) ˄q is a contradiction

Problem 12: Construct the truth table of (∼p˄q) ˅P.

p q ∼p ∼p˄q (∼p˄q) ˅p
T T F F T
T F F F T
F T T T T
F F T F F

Problem 13: Construct the truth table of ∼p˅q.

p q ∼p ∼p˅q
T T F T
T F F F
F T T T
F F T T

Exercises
1. Consider the following propositions:
p: Rita is rich
q: Hema is poor

Write the following statements in symbolic forms:

(i) Rita and Hema are both rich

(ii) Rita is poor and Hema is rich
(iii) Rita is not rich and Hema is poor
(iv) Neither Rita nor Hema is poor
(v) It is not true that Rita and Hema are both rich
(vi) Either Rita is poor or Hema is poor
(vii) Either Rita or Hema is poor

2. Consider the following propositions:

p: He is intelligent
 29

q: He is brave

Write the following statements in symbolic forms:

(i) He is intelligent and brave

(ii) He is brave or he is not brave and intelligent
(iii) He is intelligent or not brave

3. Consider the following propositions:

(i) p: The bag is good
(ii) q: He bag is cheap

Write the following statements in symbolic forms:

(i) The bag is good and cheap

(ii) The bag is not good but cheap
(iii) This bag is costly but good
(iv) This bag is neither good nor cheap
(v) This bag is good or cheap

4. Consider the following propositions:

p: It is Sunday
q: It is cold

Write the statement against the following symbolic expressions:

(i) p˅q
(ii) ∼ (p˅q)
(iii) ∼ p˄∼q
(iv) ∼ (p˅∼q)

5. Consider the following propositions:

p: Today is Monday
q: It is raining
r: It is cold

Write the statement against the following symbolic expressions:

(i) p→q
(ii) ∼p→(q˅r)
 30

(iii) p↔q

6. Consider the following propositions:

p: Today is Saturday
q: It is raining
r: It is cold

Write the statement against the following symbolic expressions:

(i) p˅q
(ii) ∼p→q
(iii) p↔r

7. Consider the following propositions:

p: x is odd number
q: x is divisible by 5

Write the statement against the following symbolic expressions:

(i) ∼p˄∼q
(ii) p→q
(iii) p↔q

8. Write the negation of the following statements

(i) If he studies, he will pass in the Examination
(ii) All Negros are tall
(iii) Someone has visited every part of India except New Delhi
(iv) Today is Sunday
(v) No one wants to buy my friend’s car
(vi) Every even integer greater than two is not prime

9. Write the converse , inverse and contrapositive of the following statements

(i) If today is Monday, then I go to the office

2 2 2
(ii) If ABC is a right angled triangle, then AB + BC = AC
(iii) If n is prime, then n is 2 or n is odd.
(iv) If a triangle is not equilateral, then it is not isosceles
(v) If it is hot, then people will sweat
(vi) If I study hard, then I will pass the Examination
 31

10. Construct the truth table for each of the following compound propositions:
(i) (p ˄ q) → (p ˅q)
(ii) (p → q) ↔ (∼q →∼p)
(iii) (p → q) ˅ (∼p → q)
(iv) (p → q) ˄ (∼p → q)
(v) (p ↔ q) ˅ (∼p ↔ q)
(vi) (∼p˄ (∼q ˄ r)) ˅(q ˄ r) ˅(p ˄ r)
(vii) (p → q) ˄ (q → r) → (p → r)
(viii) (p ↔ q) ˅ (∼q ↔ r)
11. Prove the following equivalences:

(i) ∼ (p → q)  p ˄ ∼q
(ii) ( p ˄ q) ˅ (p ˄∼q)  p
(iii) ( p ˅ q) ˄ (p ˅∼q)  p
(iv) ∼ (p ↔ q)  (p ˄ ∼q) ˅(∼p ˄ q)
(v) (p → q) ˄ (p → r)  p → (q ˄ r)
(vi) p ˄ ((∼q ˅ r) ˄ (∼r ˅ q))  p ˄ ( q ↔ r)

Answers
1 (i) p ˄ ∼q

(i) ∼p ˄ ∼q
(ii) ∼p ˄ q

(iv) p ˄ ∼q

(v)∼ (p ˄ ∼q)

(vi)(∼p) ˅q

(vii)∼p ˅ q

2. (i) p ˄ q

(ii) q ˅(∼q ˄ p)

(iii)p˅∼q

3.(i) p ˄ q
 32

(ii) ∼p ˄ q

(iii) ∼q ˄ p

(iv) ∼p ˄∼q

(v) p ˅ q

4.(i)It is Sunday or it is cold

(ii)It is not true that it is Sunday or it is cold

(iii)It is neither Sunday nor it is cold

(iv) I t is false that it is not Sunday or it is not cold

5.(i) If today is Monday, then it is raining

(ii) If today is not Monday, then it is raining or it is cold

(iii) Today is Monday if and only if it is raining

6 (i) Today is Saturday or it is raining

(ii)If today is not Saturday, then it is raining

(iii)Today is Saturday if and only if it is cold

7(i) x is not odd number and x is not divisible by 5

(ii)If x is odd number, then x is divisible by 5

(i) x is odd number if and only if x is divisible by 5

8(i) He studies and he will not pass the Examination

(ii)Some Nigros are short

(iii)Everyone has either visited New Delhi or has not visited any part of India

other than New Delhi

 33

(iv)Today is not Sunday

(v)Someone wants to buy my friend’s car

(vi) Some even integer greater than two is prime

9. (i) Converse: If I go to office, then today is Monday

Inverse: If today is not Monday, then I do not go to office

Contrapositive: If I do not go to office, then today is not Monday

2 2 2
AB + BC = AC
(ii) Converse: If , then the triangle ABC is a right angled

triangle.
2 2 2
Inverse: If ABC is not a right angled triangle, then AB + BC  AC
2 2 2
Contrapositive: If AB + BC  AC , the triangle ABC is not a right angled
triangle.

(iii) Converse: If n is odd or n is 2, then n is prime

Inverse: If n is not prime, then n is not odd or n is not 2

Contrapositive: If n is not odd and n is not 2, then n is not prime

(iv) Converse: If a triangle is not isosceles, then it is not equilateral

Inverse: If a triangle is equilateral, then it is isosceles

contrapositive: If a triangle is isosceles, then it is equilateral

(v) Converse: If people will sweat, then it is hot

Inverse: If it is not hot, then people will not sweat

Contrapositive: If people will not sweat, then it is not hot

(vi)Converse: If I pass in the Examination, then I will study hard

Inverse:If I do not study hard, then I will not pass in the Examination

Contrapositive: If I do not pass in the Examination, then I will not study hard
 34

Formal Logic and Predicate Calculus

Predicate Calculus or Predicate Logic

In mathematics and computer programs, we encounter statements involving variables
such as “x > 6”, ”x = y + z” and “ x + y = z”. These statements are neither true nor false,
when the values of the variables are not specified.

The statement “x is greater than 6” has two parts. The first part, the variable x, is the
subject of the statement. The second part “ is greater than 6”, which refers to the property
which a subject can have, is called the predicate. Thus, in a sentence, the word (or set of
words) which describe the nature or properties of a subject is the predicate.

The statement “x is greater than 6” can be denoted by the notation P(x), where P
denotes the predicate “is greater than” and x is the variable. P(x) is called the propositional
function at x. Once a value has been assigned to the variable x, the statement P(x) becomes
a proposition and assumes truth values.

For example, the truth value of P (10) (  10 > 6) and P(3) (  3 > 6) are True (T) and
False (F) respectively.

The statements “x = y + 2” and “x + y = z” will be denoted by P(x, y) and P(x, y, z)

respectively.
The logic based on the analysis of predicates in any statement is called predicate logic or
predicate calculus.

Domain (Universe of discourse) of a proposition function

 35

The set of all possible values that may be substituted in place of the variables of a
proposition function is called domain (Universe of discourse) of the proposition function.

Example For P(x): “x > 6” we assume that x takes values from

A ={1, 3, 10, 12}.

Here, A is the universe of discourse. Here, P(1) and P(3) are false (F) while P(10) and
P(12) are true (T).

Example Let us consider the proposition “Nilanjan is a doctor”. Then, the propositional
function P(x) is “x is a doctor”. Here, P is the proposition “Nilanjan” and the predicate is
“is a doctor”. The domain or Universe of discourse is “the set of all human beings”.

Example Let us consider the proposition function P(x, y) which states “x2+y2 = 5”. The
proposition function is defined for two variables x, y. P(1, 2) is true (T) but P(1, 3) is false
(F). The Universe of discourse of P(x, y) is R  R, where R is the set of all real numbers.

Quantifiers
We have seen that a proposition can be created from a propositional function P(x) by
assigning particular value to the variable x. Quantification is the process of creating a
proposition from a proposition function. There are two types of quantifications, namely,
Universal quantification and Existential quantification.

• Universal Quantification

The universal quantification of the proposition function P(x) is the proposition “P(x) is
true for all values of x in the domain”. This quantification is denoted by  x, P(x).The
symbol  is called the Universal quantifier.

Example Let P(x) be the propositional function “x + 3 < 14”. Let the domain be A = {1,
3, 5, 7, 9, 11, 13, 15}. Then, the Universal quantification is “x + 3 < 14”  x  {1, 3, 5, 7,
9, 11, 13, 15}. The proposition  x, P(x) is false (F), since the values 11, 13, 14 do not
satisfy the relation “x + 3 < 14”.

But, if the domain is taken A = {1, 3, 5, 6, 7, 9}, then  x, P(x) will be true.

Example Let P(x) be the propositional function “x >3”. Let the domain be A: “set of all
real numbers”. Then, the Universal quantification  x, P (x) is “x >3 is true for all values
of x”. Obviously the proposition  x, P(x) is false (F), since x >3 is not true for x = 2.
 36

Example Let P(x) be the propositional function “x is mortal”. Let the domain be A: “set
of all human beings”. Then the Universal quantification is ”All human beings are mortal”.
Obviously the proposition  x, P(x) is true (T).

Example Let P(x) be the propositional function “x is a good batsman” where the domain
A is “set of all students in a class”. Then the Universal quantification  x, P(x) is the
statement “Every student in the class is a good batsman”.

• Existential quantification

The Existential quantification of the propositional function P(x) is the proposition “There
exists a value of x in the domain for which P(x) is true”. This quantification is denoted by
 x, P(x). The symbol  is called the Existential quantifier.

Example Let P(x) be the propositional function “x + 3 < 14”. Let the domain be A = {1,
3, 5, 7, 9, 11, 13, 15}. Then, the Existential quantification  x, P(x) is “there exists a value
of x for which x + 3 < 14 is true”. Obviously the proposition  x, P(x) is true (T).

But, if the domain is taken A = {11, 13, 15}, then  x, P(x) will be false (F), since there is
no value of x for which “x + 3 < 14” is true.

Example Let P(x) be the propositional function “x >3”. Let the domain be A: “set of all
real numbers”. Then, the Existential quantification  x, P(x) is “there exists a value of x
for which x >3 is true”. Obviously the proposition  x, P(x) is true (T), since x >3 is true
for x = 4.

Example Let P(x) be the propositional function “x is a good batsman” where the domain
A is “ set of all students in a class”. Then the existential quantification  x, P(x) is the
statement “there exists a student in the class who is a good batsman”.

Example Let P(x) be the propositional function “x + 5 = x”. Let the domain be A: “set of
all real numbers”. Then, the Existential quantification  x, P(x) is “there exists a value of
x for which x + 5 = 5 is true”. Obviously the proposition  x, P(x) is false (F), since there
is no real value which satisfies the relation x +5 = x.

Negation of a Quantified Expression

If P(x) is the proposition statement “x has studied mathematical logic”, then  x, P(x)
means that “every student (in the class) has studied mathematical logic”. The negation of
this statement is “It is not the case that every student in the class has studied mathematical
 37

logic” or equivalently “there is a student in the class who has not studied mathematical
logic” which is denoted by  x, ∼P(x). Thus, we can write

∼ (  x P(x))   x (∼P(x)), for x  A, A is the Universe of discourse

Similarly,  x, P(x) means that “there is a student in the class who has studied mathematical
logic”. The negation of this statement is “Every student in the class has not studied
mathematical logic” which is denoted by  x, ∼P(x). Thus we can write

∼(  x P(x))   x( ∼P(x)), for x  A, A is the Universe of discourse

Example Negate the following propositions:

1. All men can run faster than all women

2. Some women are more intelligent than all men
3. Some animals do not live in forest
4. All students pass in the semester examination

Solution: (i) Some men can run faster than some women
(ii) All women are more intelligent than some men
(iii) All animals live in forest
(iv) Some students do not pass in the semester examination

Example Negate the following propositions:

(i)  x P(x) ˄  y Q(y)

(ii)  x P(x) ˅  y Q(y)
(iii)  x P(x) ˄  y Q(y)
(iv)  x P(x) ˅  y Q(y)
(v) (  x  A) (x+6=25)
(vi) (  x  A) (x < 25)

Solution (i): (∼  x P(x) ˄  y Q(y))

 ∼  x P(x) ˅∼  y Q(y), by D’morgan’s law

  x ∼P(x) ˅  y ∼Q(y)
 38

(ii) ∼(  x P(x) ˅  y Q(y))

 ∼  x P(x) ˄∼  y Q(y), by D’morgan’s law

  x ∼P(x) ˄  y ∼Q(y)

(iii) ∼(  x P(x) ˄  y Q(y))

 ∼  x P(x) ˅∼  y Q(y) , by D’morgan’s law

  x ∼P(x) ˅  y ∼Q(y))

(iv) ∼(  x P(x) ˄  y Q(y))

 ∼  x P(x) ˅∼  y Q(y) , by D’morgan’s law

  x ∼P(x) ˅  y ∼Q(y) ,

(v) ∼ (  x  A) (x+6=25)

  x A∼(x + 6) = 25

 (  x A)(x + 6)  25

(vi) ∼ (  x  A) (x < 25)

  x A∼( x < 25)

 (  x A) (x  25)

Solved Problems
Problem 1: State which rule of inference is used in the argument
(i) It is below freezing now. Therefore, it is either below freezing or raining now.
(ii) If today is Sunday then we will not go to office. If we do not go to office
today, then we will go to a long drive. Therefore, if today is Sunday then we
will go for a long drive.
(iii) Either Heera is a good boy or Sanjay is a good boy. Heera is not a good boy,
therefore, Sanjay is good boy.
 39

(iv) If a polygon is a square then it has four sides. If a polygon has four sides,
then it has three angles. Therefore, if a polygon is a square, then it has three
angles.
(v) Bula is an excellent swimmer. If Bula is an excellent swimmer, then she can
work as a lifeguard. Therefore, Bula can work as a lifeguard.
(vi) If I run fast, then I will be champion in the race. I do not become champion
in the race. Therefore, I do not run fast.

Solution: (i) Let us consider the following simple propositions

p: It is below freezing now

q: It is raining now.

Therefore, p→ p ˅q

This follows from the rule “Addition”.

(ii) Let us consider the following simple propositions

p: today is Sunday

q: we will not go to office

r: we will go to a long drive

In symbolic form

p→q
q→r
p → r
Hence, (p → q) ˄ ( q → r) → p → r is a tautology. This follows from the rule
“Hypothetical Syllogism”.

(iii) Let us consider the following simple propositions

p: Heera is a good

q: Sanjay is a good

In symbolic form

p ˅q
∼p
q
 40

Hence, (p ˅ q) ˄ ∼p → q is a tautology. This follows from the rule “Disjunctive

Syllogism”.

(iv) Let us consider the following simple propositions

p: polygon is a square

q: polygon has four sides

r: polygon has three angles

In symbolic form

p→q
q→r
p → r

Hence, (p → q) ˄ ( q → r) → p → r is a tautology. This follows from the rule

“Hypothetical Syllogism”.

(v) Let us consider the following simple propositions

p: Bula is an excellent swimmer

q: Bula can work as a lifeguard

In symbolic form

p
p →q

q

Hence, p ˄ (p → q) → q is a tautology. This follows from the rule “Modus ponens”.

(vi) Let us consider the following simple propositions

p: I run fast

q: I will be champion in the race

In symbolic form
p →q
∼q
 41

∼p
Hence, (p→q) ˄ ∼q → ∼p is a tautology. This follows from the rule “Modus
tollens”.

Problem 2: Prove the validity of the following argument using truth tables

“If it rains, then it will be cold. If it is cold, then I shall stay at home. Sine, it rains
therefore, I shall stay at home”.

Solution: Let us consider the following simple propositions

p: It rains

q: It will be cold

r: I shall stay at home

The first premise is P1:p → q

The second premise is P2: q → r
The third premise is P3: p
The conclusion is Q: r
Therefore, the argument is symbolically written as P1, P2, P3 − Q
Therefore, the argument is symbolically written as P1, P2, P3 − Q that is p → q , q → r, p
−r
This argument will be valid if (P1˄ P2˄ P3) → Q that is
((p → q) ˄ (q → r) ˄ p)) →r is a tautology

The truth table for ((p → q) ˄ (q → r) ˄ p)) →r is

p q r p→q q → r (p → q) ˄ (q → r) (( p → q) ˄ (q → r) ˄ p)) a→r

a
T T T T T T T T
T T F T F F F T
T F T F F F F T
T F F F T F F T
F T T T T F F T
F T F T F F F T
F F T T T T F T
F F F T T T F T
 42

We see all the truth values of (( p → q) ˄ (q → r) ˄ p)) → r are “T”. So, this is a valid
argument

Problem 3: Prove the validity of the following argument using truth tables

“If 6 is even and 2 does not divide 7. Either 5 is not prime or 2 divides 7. But 5 is prime,
therefore, 6 is odd.

Solution: Let us consider the following premises

p: 6 is even

q: 2 divides 7

r: 5 it prime

The first statement is P1: p → ∼q

The second statement is P2: ∼r ˅ q
The third statement is P3: r
The conclusion is Q: ∼p
Therefore, the argument is symbolically written as P1, P2, P3 − Q
Therefore, the argument is symbolically written as P1, P2, P3 − Q that is
(P1˄ P2˄ P3) → Q
This argument will be valid if (P1˄ P2˄ P3) → Q that is
((p→∼q) ˄ (∼r ˅ q) ˄ r)) → ∼p is a tautology

The truth table for ((p→ ∼q) ˄ (∼r ˅ q) ˄ r)) → ∼p is

p q r ∼p ∼q ∼r p→∼q ∼r ˅ q (p→∼q) ˄ (∼r ˅ q) a˄r a→

a b r
T T T F F F F T F F T
T T F F F T F T F F T
T F T F T F T F F F T
T F F F T T T T T F T
F T T T F F T T T T T
F T F T F T T T T F T
F F T T T F T F F F T
F F F T T T T T T F T
 43

We see all the truth values of ((p→∼q) ˄ (∼r ˅ q) ˄ r)) →∼p are “T”. So, this is a valid
argument

Problem 4: Prove the validity of the following argument using truth tables

“If I drive to work then I will arrive in time. I do not drive to work. Therefore, I will not
arrive in time”.

Solution: Let us consider the following simple propositions

p: I drive to work

q: I will arrive in time

The first premise is P1: p → q

The second premise is P2: ∼p
The conclusion is Q: ∼q
Therefore, the argument is symbolically written as P1, P2 − Q
Therefore, the argument is symbolically written as P1, P2 − Q that is
p → q , ∼p − Q
This argument will be valid if (P1 ˄ P2) → Q that is (p → q) ˄ ∼p →∼q is a tautology

The truth table for (p → q) ˄ ∼p → ∼q is

p q ∼p ∼q p→q (p → q) ˄ ∼p (p → q) ˄ ∼p →∼q

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

We see all the truth values of (p → q) ˄ ∼p → ∼q are not “T”. So, this is an invalid
argument.

Problem 5: Prove that the argument

p → (q ˅ r), (s ˄ t) → q, (q ˅ r) → (s ˄ t) − , p → q is valid without using truth tables:

Solution: The three premises are: p → (q ˅ r), (s ˄ t) → q and (q ˅ r) → (s ˄ t)

 44

The conclusion is: p → q

Now, the following sequence of elementary arguments is used to prove the validity of the
given argument:

(i) p → (q ˅ r) (given, first premise)

(ii) (s ˄ t) → q (given, second premise)

(iii) (q ˅ r)→(s ˄ t) (given, third premise)

(iv) p → (s ˄ t) (Hypothetical syllogism using (i) and (iii))

(v) p → q (Hypothetical syllogism using (ii) and (iv))

Hence, the given argument is valid

Problem 6: Prove that the argument

(p ˄ q) → r, r → q, (r ˄ q) → (q ˄ r) − (p ˄ q) → (q ˄ r) is valid without using truth

tables:

Solution: The three premises are: (p ˄ q) → r, r → q and (r ˄ q) → (q ˄ r)

The conclusion is: (p ˄ q) → (q ˄ r)

Now, the following sequence of elementary arguments is used to prove the validity of the
given argument:

(i) (p ˄ q)→r (given, first premise)

(ii) r → q (given, second premise)

(iii) (r ˄ q) → (q ˄ r) (given, third premise)

(iv) r → (r ˄ q) (rule of absorption using (ii))

(v) (p ˄ q) → (r ˄ q) (Hypothetical syllogism using (i) and (iv)

(vi) (p ˄ q) → (q ˄ r) (Hypothetical syllogism using (v) and (iii)

Hence, the given argument is valid

 45

Problem 7: Prove the validity of the following arguments without using truth tables:

(i) p ˅ q, ∼p − q
(ii) p, p → q, q → r − r
(iii) p, q, (p ˄ q) →r − r
(iv) p, (p ˄∼q) →∼ p − p → q

Solution (i): The two premises are: p ˅ q and ∼p

The conclusion is: q

Now, the following sequence of elementary arguments is used to prove the validity of the
given argument:

(i) p ˅ q (given, first premise)

(ii) ∼p (given, second premise)

(iii) q (disjunctive syllogism)

Hence, the given argument is valid

Solution (ii): p, p → q, q → r − r

The three premises are: p, p → q and q → r

The conclusion is: r

Now, the following sequence of elementary arguments is used to prove the validity of the
given argument:

(i) p (given, first premise)

(ii) p → q (given, second premise)

(iii) q → r (given, third premise)

(iv) p → r (Hypothetical syllogism using (ii) and (iii))

(v) r (Modus ponens using (iv) and (i))

Hence, the given argument is valid

Solution (iii): p, q, (p ˄ q) → r − r
 46

The three premises are: p, q and (p ˄ q) → r

The conclusion is: r

Now, the following sequence of elementary arguments is used to prove the validity of the
given argument:

(i) p (given, first premise)

(ii) q (given, second premise)

(iii) (p ˄ q) → r (given, third premise)

(iv) p ˄ q (Rule of conjunction using (i) and (ii)

(v) r (Modus ponens using (iii)and (iv))

Hence, the given argument is valid

Solution (iv): p, (p˄∼q) →∼ p − p→q

The three premises are: p and (p˄∼q) →∼ p

The conclusion is: p→q

Now, the following sequence of elementary arguments is used to prove the validity of the
given argument:

(i) p (given, first premise)

(ii) (p ˄∼q) →∼ p (given, second premise)

(iii) ∼ (p ˄∼q) (Modus tollens using (ii) and (i))

(i): ∼ ∼(p→q) (as ∼ (p→q)  (p˄∼q))

(i) (p → q) (Complement property of (iv))

Hence, the given argument is valid

Problem 8: Prove the validity of the following argument without using truth tables

“If it does not rain or if there is no traffic dislocation, then the sports day will be held and
the cultural programme will go on. If the sports day is held, the trophy will be awarded.
The trophy was not awarded. Therefore it rained”
 47

Solution: Let us consider the following simple propositions

p: It rains

q: There is traffic dislocation

r: The sports day will be held

s: cultural programme will go on

t: The trophy will be awarded

The first premise is P1: ∼p ˅∼q → r ˄ s

The second premise is P2: r →t
The third premise is P3: ∼t
The conclusion is Q: p
Therefore, the argument is symbolically written as P1, P2, P3 − Q
Therefore, the argument is symbolically written as P1, P2. P3 − Q that is
∼p˅∼q → r ˄ s, r → t, ∼t − p

This argument will be valid if (P1˄ P2˄ P3) → Q that is

(∼p˅∼q → r ˄ s) ˄ (r → t) ˄ (∼t) → p is a tautology

Now, the following sequence of elementary arguments is used to prove the validity of the
given argument:

(i) ∼p ˅∼q → r ˄ s (given, first premise)

(ii) r → t (given, second premise)

(iii) ∼ t (given, third premise)

(iv) (∼p→( r˄s) ˄( ∼q → (r˄s)) (equivalence rule (a˅b) →c  (a→c) ˄(b→c))

(v) ∼ (r˄s) →p (contrapositive of (iv))

(vi)∼ t→∼r (contrapositive of (ii))

(vii) ∼ r (Modus pones using (iii) and (vi))

(viii) ∼ r ˅ ∼s (addition of (vii))

(ix) ∼(r ˄ s) (Demorgans’s law on (viii))

(x) p (Modus pones using (v) and (ix))

 48

Hence, the given argument is valid

Problem 9: Prove the validity of the following argument without using truth tables

“Either I will pass the examination, or, will not graduate. If I do not graduate, I will go to
USA. I failed; therefore I will go to USA”.

Solution: Let us consider the following simple propositions

p: I will pass the examination

q: I will graduate

r: I will go to USA

The first premise is P1: p˅∼q

The second premise is P2: ∼q → r
The third premise is P3: ∼p
The conclusion is Q: r
Therefore, the argument is symbolically written as P1, P2, P3 − Q
Therefore, the argument is symbolically written as P1, P2. P3 − Q that is
p˅∼q, ∼q → r, ∼p − r

This argument will be valid if (P1˄ P2˄ P3) → Q that is

(p˅∼q) ˄ (∼q → r) ˄ ∼p → r is a tautology

Now, the following sequence of elementary arguments is used to prove the validity of the
given argument:

(i) p ˅∼q (given, first premise)

(ii) ∼q → r (given, second premise)

(iii) ∼ p (given, third premise)

(iv) ∼q (Disjunctive syllogism using (i) and (iii))

(v): r (modus ponen using (ii) and (iv))

Hence, the given argument is valid

Problem 10: Prove the validity of the following argument without using truth tables
 49

“If I study, then I will pass examination. If I do not go to picnic, then I will study. But I
failed examination. Therefore, I went to picnic.”

Solution: Let us consider the following simple propositions

p: I will study

q: I will pass examination

r: I go to picnic

The first premise is P1: p → q

The second premise is P2: ∼r → p
The third premise is P3: ∼p
The conclusion is Q: r
Therefore, the argument is symbolically written as P1, P2, P3 − Q
Therefore, the argument is symbolically written as P1, P2. P3 − Q that is
p → q, ∼r → p, ∼p − r

This argument will be valid if (P1˄ P2 ˄ P3) → Q that is

(p → q) ˄ (∼r → p) ˄ (∼p) → r is a tautology

Now, the following sequence of elementary arguments is used to prove the validity of the
given argument:

(i) p → q (given, first premise)

(ii) ∼r → p (given, second premise)

(iii) ∼ p (given, third premise)

(iv) ∼ ∼r (Modus tollens using (ii) and (iii))

(v): r (complement property using (iv))

Hence, the given argument is valid

Problem 11: Prove the validity of the following “Famous Socrates argument” which is
given by:

“All men are mortal. Socrates is a man. Therefore, Socrates is mortal”

Solution: Let us consider the following notations

 50

x: Socrates

P(x): x is a man

H(x): x is mortal

With these symbolic notations, the mathematical statement is

 x (P(x) → Q(x)) ˄P(x) → Q(x)

Now, the following sequence of elementary arguments is used to prove the validity of the
given argument:

(i)  x (P(x) → Q(x)) (given)

(ii) P(x) → Q(x) (given)

(iii) P(x) (given)

(iv) Q(x) (Modus ponens using (ii) and (iii))

Hence, the given argument is valid.

Aliter: Let us consider the simple propositions

p: Socrates

q: Man

r: Mortal

In symbolic form

p → q: Socrates is a man (first premise)

q → r: All men are mortal (second premise)

p → r: Socrates is mortal (conclusion)

Hence, the argument (p → q) ˄ ( q → r) → (p → r) is valid argument by the rule

“Hypothetical syllogism”.

Problem 12: Prove the validity of the implication

 x (P(x) →Q(x),  x (R(x) →∼Q(x) ⇒  x (R(x) →∼P(x))
 51

Solution: (i)  x (P(x) →Q(x) (given premise)

(ii) P(a) →Q(a) (  value x = a in (i))

(iii)  x (R(x) →Q(x) (given premise)
(iv) R(a) →∼Q(a) (  value x = a in (iii))
(v) Q(a) →∼R(a) (Equivalence of (iv))
(vi) P(a) →∼R(a) (Hypothetical Syllogism of (ii), (v))
(vii) R(a) →∼P(a) (Equivalence of (vi))
(viii)  x (R(x) →∼P(x)) (  value x in (vii))

Hence, the result follows.

Problem 13: Show that the conclusion  x(P(x) →∼Q(x)) follows from the premises

 x (P(x) ˄Q(x)) →  y (R(y) →S(y)) and  y (R(y) ˄∼S(y))

Solution: (i)  y (R(y) ˄∼S(y)) (given premise)

(ii) R(a) ˄∼S(a) (  value x = a in (i))

(iii)∼R(a) ˅ S(a) (De Morgan’s law of (ii))

(iv)∼(R(a) → S(a)) (Equivalence of (iii))

(v)  y(∼R(y) → S(y) (  value y = a in (iii))

(vi)∼  y(R(y) → S(y) (Negation equivalence of (v))

(vii)  x ((P(x) ˄Q(x)) →  y ((R(y) →S(y)) (given premise)

(v iii)∼  x (P(x) ˄Q(x)) (Modus tollens from (vi) and (vii))

(ix)  x ∼ ((P(x) ˄Q(x)) (Negative equivalence of (viii))

(x)∼ (P(a) ˄ Q(a)) (  value x = a in (ix))

(xi)∼ P(a) ˅∼Q(a) (De Morgan’s law)

(xii) P(a) →∼Q(a) (equivalence of (xi))

(xiii)  x (P(x) →∼Q(x)) (  value x = a in (xi))

Hence, the result follows.

 52

Problem 14: Prove that

 x (P(x) → (Q(y) ˄ R(x)))→S(y),  x (P(x) ⇒ Q(y) ˄  x (P(x) ˄R(x))

Solution: (i)  x (P(x) → (Q(y) ˄ R(x))) (given premise)

(ii) P(a) → (Q(y) ˄ R(a)) (  value x = a in (i))

(iii)  x P(x) (given premise)

(iv)P(a) (  value x = a in (iii))

(v) Q(y) ˄ R(a) (Modus pones (ii) and (iv))

(vi) Q(y) (Simplification (v))

(vii)R(a) (Simplification (v))

(viii)P(a) ˄ R (a) (Conjunction of (iv) and (vii))

(ix)  x( P(x) ˄ R (x)) (  value x = a in (viii)))

(ix) Q(y) ˄  x (P(x) ˄R(x)) (Conjunction of (vi) and (ix))

Hence, the result follows.

Problem 15: Find the truth value of  x, P(x) where P(x) is the statement “x2<50” and the
domain is the set {1, 2, 3, 4, 5}

Solution: We have, 12=1<50, 22=4<50, 32=9<50, 42=16<50 and 52=25<50

So, x2<50 hold for all values of x in the set {1, 2, 3, 4, 5}. Hence, the Universal quantifier
 x, P(x) is true.

Problem 16: Find the truth value of  x, P(x) where P(x) is the statement “2x+1<10” and
the domain is the set {0, 2, 3, 5}

Solution: We have for x =0, 2(0)+1=1<10,

x=2, 2(2)+1=5<10,

x=3, 2(3)+1=7<10,

x=5, 2(5)+1=11>10

So, we cannot say 2x+1<10 for all values of x in {0, 2, 3, 5}

 53

Hence, the Universal quantifier  x, P(x) is true.

Problem 17: Find the truth value of the existential quantification of  x, P(x), where P(x)
is the statement “x2>30” and the domain is the set {0, 1, 2,3,4,5, 6,7,8}

Solution: We have that x=0, 1, 2,3,4,5 satisfy the relation x2>30. Hence, there exists a
value of x in the domain for which x2>30 hold.

Thus, the existential quantification of P(x) that is  x, P(x) is true.

Problem 18: Find the truth value of the Universal quantifier of the propositional function
P(x, y) stating “x2+y2>10” and the domain is the set {1, 2,3}

Solution: The statement P(x, y): “x2+y2<20” contains two variables x, y. When the variables
take values from the domain {1, 2, 3}, we have

12+12=2< 20, 12+22=5< 20, 12+32=10< 20, 22+22=8< 20, 32+32=18< 20

So, P(x, y): “x2+y2<20” hold for all values of x in the set {1, 2, 3}.

Hence, the Universal quantifier  x, P(x) is true.

Problem 19: Le P(x, y) states that “x2>y+2” where the domain is the set S= {1, 2, 3}. Find
the truth value of the quantifier  x,  y P(x, y).

Solution: For y = 1, 2, 3, y+2= 3, 4, 5

Now, only for x= 3 in the domain S= {1, 2, 3}, the relation “x2>y+2” hold, which is x2=32

=9> 3, 4, 5.

Hence, there exists one value of x (x =3) for which x2>y+2 hold  y

So,  x, such that  y P(x, y) is true

Hence,  x,  y P(x, y) is true

Problem 20: Le P(x, y) states that “x2+y2 < 15” where the domain is the set S= {1, 2, 3}.
Find the truth value of the quantifier  x,  y P(x, y).

Solution: For x=1, 12+y2 < 15 or, y2 < 14

For x=2, 22+y2 < 15 or, y2 < 11

For x=3, 32+y2 < 15 or, y2 < 6

We see that for y=1, 12 < 14, 12 < 11, 12 < 6

 54

Thus, there exists a value of y for which x2+y2 < 15 hold for all values of x.

Hence,  x,  y P(x, y) is true

Problem 21: Determine the truth value of the quantifier  x, P(x), where P(x) is the
statement “x2-2x+7=0” and set of real numbers is the Universe of discourse.

Solution: For the statement P(x) is the statement

x2-2x+7=0

2  4 − 4 1 7
or, x=
2

2  − 24
or, x=
2

or, x =1 i 6

The two values of x = 1 + i 6 and x = 1 − i 6 are complex numbers.

Thus, there is no real value of x which satisfies the equation x2-2x+7=0

Hence, the existential quantifier  x, P(x) is false.

Problem 22: If P(x, y) symbolizes the statement “x likes y”, where the Universe of
discourse for both x and y consists of all people in the world. Translate the following
English sentences into logical expressions:

(i) Everybody likes z

(ii) Everybody likes somebody
(iii) There is somebody whom everybody likes
(iv) Nobody likes everybody
(v) There is somebody whom no one likes

Solution (i): P(x, y) for all x. Hence,  x P(x, z)

(ii)P(x, y) is true for all x and some y. Hence,  x,  y P(x, y).

(iii)Even if, (iii) is the same as (ii), the stress is on the existence of somebody “y” whom
all “x” like. Hence,  y,  x P(x, y).
 55

(iv)Nobody likes everybody that is there is not one who likes everybody. Hence, ∼ 
x,  y P(x, y)

  x ∼  y P(x, y)

  x  y ∼P(x, y)

(v)The sentence means that there is somebody whom everyone does not like.

Hence, ∼  x  y P(x, y)

  x ∼  y P(x, y)

  x  y ∼P(x, y)

Problem 23: Express each of the following statements using mathematical and logical
operations, predicates and quantifiers, where the universe of discourse consists of all
students of computer science / mathematics honours course.

(i) Every computer science student needs a course in mathematics

(ii) There is a student in the class who owns a personal computer
(iii) Every student in the class has taken at least one mathematics course
(iv) There is a student in the class who has taken at least one mathematics course

Solution (i): Let P(x) be the statement “x needs a course in mathematics”, where the
Universe of discourse consists of all computer science honours students. Then the
mathematical statement is  x P(x)

(ii)Let P(x) be the statement “x owns a personal computer”, where the Universe of
discourse consists of all students in the class. Then the mathematical statement is  x P(x)

(iii)Let P(x, y) be the statement “x has taken y”, where the Universe of x consists of all
students in the class and that of y consists of all mathematics courses. Then the
mathematical statement is  x  y P(x, y)

(iv)Let P(x, y) be the statement “x has taken y”, where the Universe of x consists of all
students in the class and that of y consists of all mathematical courses. Then the
mathematical statement is  x  y P(x, y)

Problem 24: Express the negations of the following statements using quantifiers and in
English:
 56

(i) If the teacher is absent, then some students do not keep quiet
(ii) All the students keep quiet and the teacher is present
(iii) Some of the students do not keep quiet or the teacher is absent
(iv) No one has done every problem in the exercise.

Solution (i): Let P represents the teacher in the class and Q(x) represents “x keeps
quiet”. Then the given statement is

∼P→  x Q (x)  ∼P→∼  x Q (x)

 P˅∼  x Q (x)

Hence, Negation of the given statement is

∼ (P˅∼  x Q (x))

 ∼ P˄  x Q (x)

That is the teacher is absent and all the students keep quiet.

(ii) Let P represent the teacher in the class and Q(x) represents “x keeps quiet”. Then
the given statement is

 x Q (x) ˄P

Hence, Negation of the given statement is

∼ (  x Q (x) ˄P)

 ∼  x Q (x) ˅∼P

  x ∼Q (x) ˅∼P

That is some students do not keep quiet or the teacher is absent

(iii) Let P represent the teacher in the class and Q(x) represents “x keeps quiet”. Then
the given statement is

 x∼ Q (x) ˅∼P

 ∼  x Q (x) ˅∼P

Hence, Negation of the given statement is

∼ (∼  x Q (x) ˅∼P)
 57

  x Q (x) ˄P

That is all the students keep quiet and the teacher is present

(iv)Let D(x, y) represent “x has done problem y”.

Then the given statement is

( ∼  x) (  D (x, y))

Hence, Negation of the given statement is

(∼∼  (x)) (  y D (x, y))

  (x)  y D (x, y)

That is someone has done every problem in the exercise.

Problem 25: Determine the negation of the following statements

(i)  x  y  z, P(x, y ,z)

(ii)  x  y, P(x, y)
(iii)  y  x  z, P(x, y ,z)

Solution (i): ∼ (  x  y  z, P(x, y ,z))

  x  y  z ∼P(x, y ,z)

(ii) ∼(  x  y, P(x, y))

  x  y, ∼P(x, y)

(iii) ∼(  y  x  z, P(x, y ,z))

  y  x  z, ∼P(x, y, z)

Problem 26: Determine the negation of the following statements

(i)  x  y, (P(x) ˅ Q(y))

(ii)  x  y, (P(x, y) →Q(x, y))
(iii)  x  y, (P(x) ˄Q(y))
 58

Solution (i): ∼ (  x  y, (P(x) ˅Q(y))

  x  y, ∼(P(x) ˅ Q(y))

  x  y, (∼P(x) ˄∼Q(y))

(ii) ∼ (  x  y, (P(x, y) →Q(x, y))

  x  y, ∼( P(x, y) →Q(x, y))

(iii) ∼(  x  y, (P(x) ˄ Q(y))

  x  y, ∼( P(x) ˄ Q(y))

  x  y, (∼ P(x) ˅∼Q(y))

Problem 27: Give a direct proof of the statement “The Square of an even integer is an
even integer”.

Solution: Let p and q be two simple propositions. Let x be an even integers, then

x = 2n, n Z (set of integers)

p: the square of even integer x

q: x is even integer

Squaring both sides,

x2=(2n)2

= 4n2

= 2(2n2)

= 2t, where t = 2n2 Z

This is even. Thus, the square of an even integer is an even integer.

Therefore, p is true and p → q is true, we conclude that q is true by the rule of “Modus
ponens”.

Problem 28: Give an indirect proof of the statement “If 3n + 2 is odd, then n is odd”.

Solution: Let p and q be two simple propositions.

 59

p: 3n + 2 is odd

q: n is odd

We have to prove p → q. We shall prove the statement by using its equivalent

contrapositive statement: ∼q → ∼p.

Now, ∼q: n is even

⇒ n =2t, t Z

Consider

3n + 2 = 3(2t) + 2

= 6t +2

= 2(3t +1)

This is even

⇒ 3n + 2 is even

⇒∼p holds.

Therefore, by the rule of contrapositive the result holds.

Aliter: This statement may be proved by the method of contradiction.

Let p and q be two simple propositions.

p: 3n + 2 is odd

q: n is odd

Let ∼q is true that is n is even,

Then n = 2t, t Z (set of integers)

It follows that 3n + 2 = 3(2t) + 2

= 6t + 2

= 2(3t + 1)

⇒3n + 2 is even (since it can be expressed as a multiple of 2)

 60

We arrive at a contradiction that p: 3n + 2 is even but the hypothesis is that p is even.

This contradiction proves that q is true and the implication p → q is true.

Problem 29: Prove the validity of the following argument using indirect method

 x (P (x)˅ Q (x)) ⇒(  x (P (x))˅ (  x Q (x))

Solution: This statement may be proved by the method of contradiction

We shall prove that ∼ (  x (P (x)) ˅ (  x Q (x)) is false.

Now, the following sequence of elementary arguments is used to give the result:

(i) ∼ (  x (P (x))˅ (  x Q (x)) (given, assumed)

(ii) ∼ (  x (P (x)) ˄ ∼ ( (  x Q (x)) (De Morgan’s law)

(iii) ∼ (  x (P (x)) (Simplfication)

(iv) ∼ (  x Q (x)) (Simplfication)

(v):  x ∼ (P (x) (negation of (iii))

(vi)  x ∼Q (x) (negation of (iv))

(vii) ∼ P (a) (  one value x=a in (v))

(viii) ∼Q (a) (  value x = a in (vi))

(ix) ∼ P (a) ˄∼Q (a) (Conjunction of (vii)and (viii))

(x) ∼ (P (a) ˅Q (a)) (De Morgan’s law)

(xi)  x (P (x)˅ Q (x)) (given premise)

(xii) P (a)˅ Q (a) (  value x = a in (xi))

(xiii) (P (a)˅ Q (a)) ˄∼ (P (a) ˅Q (a)) (conjunction of (x) and (xii))

(xiv) F (Complement law)

This shows that our assumption that ∼ (  x (P (x))˅ (  x Q (x)) is true is actually false.
This contradiction proves that
 x (P (x)˅ Q (x)) ⇒(  x (P (x))˅ (  x Q (x))
 61

Problem 30: Prove the validity of the following argument using indirect method

 x (P (x) → Q (x)) ˄  yP (y) ⇒  zQ (z)

Solution: This statement may be proved by the method of contradiction

We shall prove that ∼(  zQ (z)) is false

Now, the following sequence of elementary arguments is used to give the result:

(i) ∼(  zQ (z)) (given, assumed)

(ii)  z (∼Q (z)) (Negation of (i))

(iii)(∼Q (a)) (  value x = a in (ii))

(iv)  yP (y) (given premise)

(v) P(a) (  one value x=a in (iv))

(vi) P(a) ˄ ∼Q (a) (conjunction of (iii) and (v))

(vii) ∼(∼P(a) ˅ Q (a)) (De Morgan’s law)

(viii) ∼(P(a) → Q (a)) (Equivalence of (vii))

(ix)  x (P (x) → Q (x)) (given premise)

(x) P (a) → Q (a) (  value x = a in (ix))

(xi) (P (a) → Q (a)) ˄∼(P(a) → Q (a)) (conjunction of (viii) and (x))

(xii) F (Complement law)

This shows that our assumption that ∼(  zQ (z)) is true is actually false. This contradiction
proves that
 x (P (x) → Q (x)) ˄  yP (y) ⇒  zQ (z)

Exercises
1. State which rule of inference is used in the argument
 62

(vii) Kangaroos live in Australia and are marsupials. Therefore, Kangaroos are
marsupials.
(viii) Covid 19 is a Pandamic and originated from china. Therefore, Covid 19 is
originated from China
(ix) Hema is a very good dancer. If Hema is a very good dancer, then she can
work as a dance trainer. Therefore, Hema can work as a dance trainer.
(x) Aloke will work at a computer company this winter. Therefore, this winter
Aloke will work at a computer company or he will be a beach bum.
(xi) If I work all night on my lessons, then I can answer all the questions. If I
answer all the questions, I will have better knowledge. Therefore, if I work
all night on my lessons, then I will have better knowledge
(xii) Either today I will go to cinema or I will go to shopping mall. I will not go to
cinema today, therefore I will go to shopping mall.

1. Prove the validity of the following argument using truth tables

(i) If today is Sunday, then yesterday was Saturday. Yesterday was Saturday, Therefore,
today is Sunday”.

(ii) If a man is married then he is unhappy. If a man is unhappy then he dies young.
Therefore, married man dies young.

(iii) Every living thing is a plant or an animal. My cat is alive and it is not a plant. All
animals have hearts. Therefore my cat has a heart.

(iv) All integers are rational numbers. Some integers are powers of 2. Therefore,
some rational numbers are powers of 2.
(v) If I like Propositional logic, then I will study. Either I study or I get less marks.
Therefore, if I get less marks, I do not like Propositional logic
(vi) If the wages increase, then there will be inflation. The cost of living will decrease
if there is no inflation. Therefore, if wages will increase then the cost of living
will not decrease.

2. Prove the validity of the following arguments without using truth tables
(i) p, q, − (p˅r) ˄q
(ii) p→q, p˄r − q
(iii) (p→q) ˄(r→s), (p˅r) ˄(q˅r) − q˅s
(iv) (p˄q) ˅( r→s), t→r, ∼ (p˄q) − t→s
 63

(v) p→(q˅r),(s˄t)→q, (q˅r) →(s˄t) − p→q

(vi) p˅(q→p), ∼ p˄r − ∼q

3. Prove the validity of the following argument without using truth tables

(i) Either I will get good marks or I will not graduate. If I did not graduate, I
will go to Europe. I got good marks. Therefore, I will not go to Europe.
(ii) If the market is free, then there is no inflation. If there is no inflation, then
there are price controls. Since, there are price controls; therefore, the market
is free.
(iii) One student in Computer class knows how to write programs in C++.
Everyone who knows how to write programs in C++ can get a high-paid job.
Therefore, someone in this class can get a high- paid job
(iv) Everyone who eats some vegetables daily are healthy. Jaya is not healthy.
Therefore, Jaya does not eat vegetables daily.
(v) A student in this class has not read the book. Everyone in this class passed
the first examination. Therefore someone who passed the first examination
has not read the book.
(vi) No man is an island. Manhattan is an island. Therefore, Manhattan is not a
man.

4. Express each of the following statements using mathematical and logical operations,
predicates and quantifiers, where the universe of discourse consists of all students
of a school.
(i) There is a student in the school who can speak English and who knows
Bengali
(ii) No student in the school can speak English or knows Bengali
(iii) There is a student in the school who can speak English but who does not
know Bengali.
(iv) All the students in the school can speak English as well as know Bengali

5. Let P(x) be the statement “x can speak English”, Q(x) be the statement “x knows
Bengali”, where the universe of discourse consists of all students of a school.
Translate the following English sentences into logical expressions:

(i)  x (P(x) ˅Q(x))

 64

(ii)  x ∼( P(x) ˄Q(x))

(iii)  x ∼( P(x) ˄Q(x))

(iv)  x ( P(x) ˄∼Q(x))

6. Let P(x) be the statement “x is a shark”, Q(x) be the statement “x is a fish” and R(x)
be “ x lives in water”, where the universe of discourse consists of all animals.
Translate the following English sentences into logical expressions:

(i)  x (∼ R(x))
(ii)  x ( Q(x) ˄∼P(x))
(iii)  x ( P(x) ˄R(x)) →Q(x)
(iv)  x ( P(x) ˄Q(x)) →R(x)

7. Prove the following implications

(i)  x (P(x) →Q(x)) ˄  x (Q(x) →R(x)) ⇒  x (P(x) →R(x))

(ii)  x P(x),  x (P(x) →Q(x)) ⇒  x Q(x)

(iii)  x(P(x) ˄ Q(x)) ⇒  x(P(x) ˄  x Q(x))

(iv)  x P(x) →  x Q(x) ⇒  x (P(x) → Q(x))

(v)  x (P(x) → Q(x)) ⇒  x (P(x) →  x Q(x))

(vi)  x (C(x) → A(x)) ⇒  x (  y(C(y) ˄ B(x, y)) →  y (A(y) ˄ B(x, y)))

8. Determine the truth value of each of the following statements where A = {1, 2, 3,
4, 5, 6} is the Universe of discourse.
(i)  x (x + 3 = 12)
(ii)  x (x + 3 < 12)
(iii)  x (x + 3 < 6)
(iv)  x (x + 3  8)
(v)  x (x2 - 9 = 0)

9. Determine the truth value of each of the following statements where A = {1, 2, 3} is
the Universe of discourse.
 65

(i)  x,  y, x2 < y + 1
(ii)  x,  y, x2 + y2< 12

10. Determine the truth value of each of the following statements where A = {1, 2,3, ...,
9, 10} is the Universe of discourse.

(i)  x,  y, (x + y < 14)

(ii)  x,  y, (x + y < 14)

11. Determine the truth value of each of the following statements where the set of all
numbers is the Universe of discourse
(i)  x P(x) where P(x) is “x2 = xn”
(ii)  x P(x) where P(x) is “2x = xn”
(iii)  x P(x) where P(x) is “x2 -4= 0”

12. Express the negation of the statement using quantifiers and in English:

“Every student in this class is intelligent” in two different ways

13. Determine the negation of the following statements

(i) x is real number, if x > 3 then x2 > 9
(ii) x is real number, if x(x + 1) > 0 then x > 0 or x < -1

14. Determine the negation of the following statements

(i) ∼  x  y P(x, y)
(i) ∼ (  x  y ∼R(x, y) ˄  x  y P(x, y))

15. Give a direct proof of the following statements

(i) Sum of two odd integers is even
(ii) Sum of two rational numbers is rational
(iii) Square od an even number is an even number
(iv) 5 is rational
(v) If n is an integer and n2+5 is odd, then n i even
(vi) Product of two rational numbers is rational
 66

16. Give an indirect proof of the following statements

(i) If x, y  Z (set of integers) such that xy is odd then both x and y are odd.
(ii) If x and y are two integers such that x is even and y is odd then xy is even
(iii) If x2 + 4x = 0,x R (set of Reals) then x = 0
(iv) For all real numbers x and y, if x + y  2 then either x  1 or y  1
(v) If n is a positive integer, then n is odd if and only if 5n + 6 is odd
(vi) For x, y  Z (set of integers), x2 = y2 if and only if x = y or x = -y

Answers

1. (i)The rule of Inference is “Simplification”

(ii) The rule of Inference is “Simplification”

(iii)The rule of Inference is “Modus ponens”

(iv)The rule of Inference is “ Addition”

(v)The rule of Inference is “ Hypothetical Syllogism”

(vi) The rule of Inference is “Disjunctive Syllogism”

1 (i) not valid

(ii) valid

(iii)valid

(iv)valid

(v)not valid

(vi) not valid

2 (i) valid

(ii) valid

(iii)valid

(iv)valid
 67

(v) valid

(vi) valid

3 (i) valid

(ii) valid

(iii)valid

(iv)valid

4. (i)  x (P(x) ˄Q(x))

(ii)  x ∼( P(x) ˅Q(x))

(iii)  x (P(x) ˅∼Q(x))

(iv)  x(P(x) ˄Q(x))

3. (i) Every student of the school either can speak English or know Bengali

(ii) There is a student who cannot speak English and also do not know Bengali.

(iii)No student in the school can speak English and knows Bengali

(iv)All the students in the school can speak English but do not know Bengali

4. (i) There exists an animal which does not live in water

(ii)There exists a fish that is not a shark

(iii)Every shark that lives in water is a fish

(iv) Every shark which is a fish lives in water

5. (i) False
(ii)True

(iii)True

(iv)False
 68

(v)True

8. (i) True

(ii) True

9. (i) True

(ii) False

10.(i) False

(ii) True

(iii)True

∼(  x  y,

11. (i) Not every student in this class is intelligent

(ii) Some student in this class is not intelligent

12.(i)  a real number x such that x > 3 and x2  9

(ii)  a real number x such that x (x + 1) > 0 then and x  0 and x  −1

13.(i)  x  y, P(x, y)

(ii) (  x  y R(x, y) ˅(  x  y, ∼P(x, y))