01 Mathematical Logic

Syllabus

1.1 Statement

1.2 Logical Connectives, Compound Statements and Truth Tables

1.3 Statement Pattern and Logical Equivalence Tautology, Contradiction

and Contingency

1.4 Quantifiers and Quantified Statements

1.5 Duality

1.6 Negation of Compound Statement

1.7 Algebra of Statements (Some Standard equivalent Statements)

1.8 Application of Logic to Switching Circuits

Introduction :-
Mathematics is an exact science. Every mathematical statement must be
precise. Hence,there has to be proper reasoning in every mathematical proof.
Proper reasoning involves logic. The study of logic helps in increasing one’s
ability of systematic and logical reasoning. It also helps to develop the skills of
understanding various statements and their validity. Logic has a wide scale
application in circuit designing, computer programming etc. Hence, the study of
logic becomes essential.roiii

Statement and its truth value:-

There are various means of communication viz.,verbal, written etc. Most of the
communication involves the use of language whereby, the ideas are conveyed
through sentences.

There are various types of sentences such as:

(i) Declarative (Assertive)

(ii) Imperative (A command or a request)
(iii) Exclamatory (Emotions, excitement)
(iv) Interrogative (Question)

Statement

A statement is a declarative sentence which is either true or false but not both
simultaneously. Statements are denoted by the letters p, q, r….

For example:

(i) 3 is an odd number.

(ii) 5 is a perfect square.
(iii) Sun rises in the east.
(iv) x + 3 = 6, when x = 3.
Truth Value

A statement is either True or False. The Truth value of a ‘true’ statement is defined
to be T (TRUE) and that of a ‘false’ statement is defined to be F (FALSE).

Note: 0 and 1 can also be used for T and F respectively.

Consider the following statements:

(i)There is no prime number between 23 and 29.

(ii) The Sun rises in the west.

(iii) The square of a real number is negative.

(iv) The sum of the angles of a plane triangle is1800.

Here, the truth value of statement i. and iv. is T and that of ii. and iii. is F.

Note:
The sentences like exclamatory, interrogative, imperative etc., are not considered
as statements as the truth value for these statements cannot be determined.
Open sentence
Open sentence:-
An open sentence is a sentence whose truth can vary according to some
conditions, which are not stated in the sentence.

Note:
Open sentence is not considered as statement in logic.

For example:

(i) x X 5 = 20
This is an open sentence as its truth depends on value of x (if x = 4, it is true and if
x ≠ 4, it is false)

(ii) Chinese food is very tasty.

This is an open sentence as its truth varies from individual to individual.
Exercise 1.1

Logical Connectives, Compound Statements and

Truth Tables
Logical Connectives:

The words or group of words such as “and, or, if ….then, if and only if, not” are
used to join or connect two or more simple sentences. These connecting words are
called logical connectives.

Compound Statements:

The new statement that is formed by combining two or more simple statements
by using logical connectives are called compound statements.

Component Statements:

The simple statements that are joined using logical connectives are called
component statements.

For example:

Consider the following simple statements,

(i) e is a vowel
(ii) b is a consonant
These two component statements can be joined by using the logical connective ‘or’
as shown below:
‘e is a vowel or b is a consonant’
The above statement is called compound statement formed by using logical
connective ‘or’.

Truth Table

A table that shows the relationship between truth values of simple statements and
the truth values of compounds statements formed by using these simple statements
is called truth table.
Note:
The truth value of a compound statement depends upon the truth values of its
component statements.

Logical Connectives

A. AND [ 𝚲 ] (Conjunction):
If p and q are any two statements connected by the word ‘and’, then the resulting
compound statement ‘p and q’ is called conjunction of p and q which is written in
the symbolic form as ‘p 𝚲 q’.

For example:

p: Today is a pleasant day.

q: I want to go for shopping.
The conjunction of above two statements is ‘p 𝚲 q’ i.e. ‘Today is a pleasant day
and I want to go for shopping’.
A conjunction is true if and only if both p and q are true.

Truth table for conjunction of p and q is as

shown below:

P q p𝚲q
T T T
T F F
F T F
F F F

Note:
The words such as but, yet, still, inspite, though, moreover are also used to connect
the simple statements.
These words are generally used by replacing ‘and’.

B. OR [ ∨ ] (Disjunction):
If p and q are any two statements connected by the word ‘or’, then the resulting
compound statement ‘p or q’ is called disjunction of p and q which is written in the
symbolic form as ‘p ∨ q’.
The word ‘or’ is used in English language in two distinct senses, exclusive and
inclusive.

For example:

(i). Rahul will pass or fail in the exam.

(ii). Candidate must be graduate or post-graduate.
In eg. (i), ‘or’ indicates that only one of the two possibilities exists but not both
which is called exclusive sense of ‘or’.
In eg. (ii), ‘or’ indicates that first or second or both the possibilities may exist
which is called inclusive sense of ‘or’.
A disjunction is false only when both p and q are false.

Truth table for disjunction of p and q is as shown below:

p q p∨ q
T T T
T F T
F T T
F F F

C. Not [~] (Negation):

If p is any statement then negation of p i.e., ‘not p’ is denoted by ~p. Negation of

any simple statement p can also be formed by writing ‘It is not true that’ or ‘It is
false that’, before p.
For example:
p : Mango is a fruit.
~p : Mango is not a fruit.

Truth table for negation is as shown below:

p ~p
T F
F T

D. If….then (Implication, → ) (Conditional):

If p and q are any two simple statements, then the compound statement, ‘if p then
q’, meaning “statement p implies statement q or statement q is implied by
statement p”, is called a conditional statement and is denoted by p → q or p ⇒ q.
Here p is called the antecedent (hypothesis) and q is called the consequent
(conclusion).

For example:
Let
p: I travel by train.
q: My journey will be cheaper.

Here the conditional statement is

‘p → q: If I travel by train then my journey will be cheaper.’
Conditional statement is false if and only if antecedent is true
and consequent is false.

Truth table for conditional is as shown below:

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

Note:
Equivalent forms of the conditional statement p → q:
(a) p is sufficient for q.
(b) q is necessary for p.
(c) p implies q.
(d) p only if q.
(e) q follows from p.

E. Converse, Inverse and Contrapositive statements:

If p → q is given, then its

converse is q → p
inverse is ~p → ~q
contrapositive is ~q → ~p
For example:
Let
p : Smita is intelligent.
q : Smita will join Medical.
(i) q → p : If Smita joins Medical then she is intelligent.
(ii) ~p → ~q : If Smita is not intelligent then she will not join Medical.
(iii) ~q → ~p : If Smita does not join Medical then she is not intelligent.

Consider, the following truth table:

p q p →q ~p ~q q→p ~q→~p ~p →~q

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

From the above table, we conclude that

(i). a conditional statement and its contrapositive are always equivalent.

(ii). converse and inverse of the conditional statement are always equivalent.

F. If and only if (Double Implication, ⟷) (Biconditional):

If p and q are any two statements, then ‘p if and only if q’ or ‘p iff q’ is called the
biconditional statement and is denoted by p ⟷ q. Here, both p and q are called
implicants.
For example:
Let
p : price increases
q : demand falls
Here the Biconditional statement is ‘p ⟷ q : Price increases
if and only if demand falls’.
A biconditional statement is true if and only if both the implicants have same truth
value.
Truth table for biconditional is as shown below:

p q p⟷q
T T T
T F F
F T F
F F T

Statement Pattern and Logical equivalence: Statement Pattern and

Logical Equivalence
(A) Statement Pattern
Let, p, q, r,… be simple statements. A compound statement obtained from these
simple statements and by using one or more connectives ⋀ ,∨, ∼, →, ↔ is called a
statement pattern.

Following points must be noted while preparing truth tables of the statement
patterns:

(i) Parentheses must be introduced wherever necessary.

For example:
~ (p ∧ q) and ~ p ∧ q are not the same.

(ii) If a statement pattern consists of ‘n’ statements and ‘m’ connectives, then
truth table consists of 2n rows and (m + n) columns.

(B) Logical equivalence

Two logical statements are said to be equivalent if and only if the truth values in
their respective columns in the joint truth table are identical.

If S1 and S2 are logically equivalent statement patterns, we write S1 ≡ S2.

For example:

To prove: p ∧ q ≡ ~ (p → ~q) [Mar 08]

p q p∧q ~q (p → ~q) ~(p → ~q)

T T T F F T
T F F T T F
F T F F T F
F F F T T F
In the above truth table, all the entries in the columns of p ∧ q and ~ (p → ~q) are
identical.
∴ p ∧ q ≡ ~(p → ~q).

Tautology, Contradiction and Contingency

Tautology:

A statement pattern having truth value always T, irrespective of the truth values of
its component statement is called Tautology.

For example,
consider (p ↔ q) ↔ (q ↔ p)

p q p ↔q q ↔p (p ↔ q) ↔ (q ↔ p)
T T T T T
T F F F T
F T F F T
F F T T T

In the above truth table, all the entries in the last column are T.
∴ The given statement pattern is a tautology.

Contradiction:

A statement pattern having truth value always F, irrespective of the truth values of
its component statement is called a Contradiction.

F or ex ample,
consider p ∧ ~ p

p ~p p∧~p
T F F
F T F

In the above truth table, all the entries in the last column are F.
∴ The given statement pattern is a contradiction.
Contingency:

A statement pattern which is neither a tautology nor a contradiction is called

Contingency.

For example,
consider (p ↔ q) ∧ ~(p → ~ q)

p q p↔q ~q p →~q ~(p → ~q) (p ↔ q) ∧~(p → ~q)

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

In the above truth table, the entries in the last column are a combination of T and F.
∴ The given statement pattern is neither a tautology nor a contradiction, it is a
contingency.

Quantifiers:

Quantifiers are the symbols used to denote a group of words or a phrase.

Generally, two types of quantifiers are used. They are as follows:

(i) Universal Quantifier:

The symbol ‘∀’ stands for “all values of” and is known as universal
quantifier.

For example,

Consider A = {1, 2, 3}
Let p: ∀ x ∈ A, x < 4
Here, the statement p uses the quantifier ‘for all’(∀).
This statement is true if and only if each and every element of set A
satisfies the condition ‘x < 4’ and is false otherwise.
Here, the given statement is true for all the elements of set A, as 1, 2, 3
satisfy the condition, ‘x ∈ A, x < 4’.

(ii) Existential Quantifier:

The symbol ‘∃’ stands for ‘there exists’ and is known as existential
quantifier.

For example,
Consider A = {4, 14, 66, 70}.
Let p: ∃ x ∈ A such that x is an odd number. Here, the statement p uses
the quantifier ‘there exists’ (∃).
This statement is true if atleast one element of set A satisfies the
condition ‘x is an odd number’ and is false otherwise.
Here, the given statement is false as none of the elements of set A satisfy
the condition, ‘x ∈ A such that x is an odd number’.

Quantified statement:

The statement containing quantifiers is known as quantified statement.

Generally, an open sentence with a quantifier becomes a statement and
is called quantified statement.

For example:

Use quantifiers to convert open sentence x + 2 < 4 into a statement.

Solution:
∃ x ∈ N such that x + 2 < 4, is a true
statement, since x = 1 ∈ N satisfies x + 2 < 4.
Duality:u
ality
Two compound statements S1 and S2 are said to be duals of each other,
if one can be obtained from the other by interchanging ‘∧’ and ‘∨’ and
vice-versa. The connectives ‘∧’ and ‘∨’ are duals of each other. Also, a
dual is obtained by replacing t by c and c by t, where ‘t’ denotes
tautology and ‘c’ denotes contradiction.
Remarks:
(i) The symbol ‘~’ is not changed while finding the dual.
(ii) Dual of a dual is the statement itself.
(iii) The special statements ‘t’ (tautology) and ‘c’ (contradiction) are
duals of each other.
(iv) T is changed to F and vice-versa.

Principle of Duality:
If a compound statement S1 contains only ~, ∧ and ∨ and statement S2
arises from S1 by replacing ∧ by ∨ and ∨ by ∧, then S1 is a tautology if
and only if S2 is a contradiction.

Algebra of statements:

Some standard equivalent statements:

(a) Idempotent Law:

(i) p ∨ p ≡ p
(ii) p ∧ p ≡ p

(b) Commutative Law:

(i) p ∨ q ≡ q ∨ p
(ii) p ∧ q ≡ q ∧ p
(c) Associative Law:

(i) (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) ≡ p ∨ q ∨ r
(ii) (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) ≡ p ∧ q ∧ r

(d) Distributive Law:

(i) p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
(ii) p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
(e) Identity Law:

(i) p ∨ F ≡ p
(ii) p ∧ F ≡ F
(iii) p ∨ T ≡ T
(iv) p ∧ T ≡ p

(f) Complement Law:

(i) p ∨ ~p ≡ T
(ii) p ∧ ~p ≡ F

(g) Involution Law:

(i) ~T ≡ F
(ii) ~F ≡ T
(iii) ~(~p) ≡ p

(h) DeMorgan’s Law:

(i) ~(p ∨ q) ≡ ~p ∧ ~q
(ii) ~(p ∧ q) ≡ ~p ∨ ~q
(i) Absorption Law:

(i) p ∨ (p ∧ q) ≡ p
(ii) p ∧ (p ∨ q) ≡ p

(j) Conditional Law:

(i) p → q ≡ ~p ∨ q
(ii) p ↔ q ≡ (~p ∨ q) ∧ (~q ∨ p)

Application of Logic to Switching Circuit:

The working of an electric switch is similar to a logical statement which

has exactly two outcomes, namely, T or F. A switch also has two
outcomes or results (current flows and current does not flow) depending
upon the status of the switch i.e. (ON or OFF). This analogy is very
useful in solving problems of circuit design with the help of logic.

Switch:

An electric switch is a two state device used for turning a current ‘on’ or
‘off’.
Consider a simple circuit having a switch ‘S’, a battery and a lamp
‘L’. When the switch ‘S’ is closed (i.e., ON, current is flowing through
the circuit), the lamp glows (is on). Similarly, when the switch is open
(i.e., OFF, current is not flowing through the circuit), the lamp does not
glow (is off).

Thus, if p is a statement ‘the switch is closed’ and if l is a statement

‘the lamp glows’ then p is equivalent to l i.e p ≡ l.
Note:

(i) ~p means ‘the switch is open’. In this case, the lamp will not glow
and thus ~ p ≡ ~ l.

(ii) If a switch is ‘ON’ then its truth value is T or 1 and if the switch is
‘OFF’, its truth value is F or 0. If there are two switches, then they can
be connected in the following ways:

(i) Switches S1 and S2 connected in series:

Let
p: the switch S1 is closed
q: the switch S2 is closed
l : the lamp glows

In this case, the lamp glows, if and only if both the switches are closed.
Thus we have, p ∧ q ≡ l.

Input – Output (switching) table:

p q p∧q
T (1) T (1) T (1)
T (1) F (0) F (0)
F (0) T (1) F (0)
F (0) F (0) F (0)

ii. Switches S1 and S2 are in parallel

Let
p : the switch S1 is closed
q : the switch S2 is closed
l : the lamp glows
In this case, the lamp glows, if at least one of the switches is closed.
Thus, we have p ∨ q ≡ l,
Input – output (switching) table:

p q p∨q
T (1) T (1) T (1)
T (1) F (0) T (1)
F (0) T (1) T (1)
F (0) F (0) F (0)

Note:

( i) If two or more switches in a circuit are open or closed

simultaneously, then they are denoted by same letter and are called
‘equivalent switches.’

(ii) Any two switches in a circuit having opposite states are called
complementary switches.
For example, if S1 and S2 are the two switches such that when S1 is
closed, S2 is open and vice-versa, then the switches S1 and S2 are called
complementary switches and S2 is denoted as S1. In such a situation,
one of them is considered as p and the other as ~p or p

(iii) Two circuits are called equivalent if output of the two circuits is
always same.

(iv) A circuit is called simpler if it contains lesser number of switches.