CONTENTS

KEY- CONCEPTS
SUGGESTED EXERCISE
ANSWER - KEY
 KEY CONCEPTS
Mathematical logic is the science of reasoning. It is a process by which we arrive at a conclusion from
known statements or assertions with the use of valid assumption which is known as
Laws of Logic.

1. Basic Concepts: A statement is a sentence which is either true of false but not both simultaneously.

2. Truth value of statement : If a statement is true, we say that its truth value is TRUE or T and if it is false
we say that its truth value is FALSE or F.

3. Compound statements: A statement is said to be simple, if it cannot be broken down into two or more
sentences. New statements that can be formed by combining two or more simple statements are called
sub-statements or component statements of the compound statements.

4. The compound statement S consisting of sub statements p, q, r, ..... is denoted by S (p,q, r,..).
A fundamental property of a compound statements is that its truth value is completely determined by the
truth value of each of its sub statements together with the way in which they are connected to form the
compound statement.

5. Basic logical connectives: The words which combine simple statements to form compound statements
are called connectives. To define a set of connectives with definite meanings in the language of logic is
called object language. Three basic connectives (logical) are

Object language English word Symbol

(i) Conjuction and 

(ii) Disconjuction or 
(iii) negation not ~

6. Conditional and Bi-conditional stetements :

" If p then q " , such statements are called conditional statements and are denoted by p  q read as 'p
implies q'.

" p if and only if q " such statements are called bi-conditional statements and are denoted by pq.

Table (to be remembered)

S.No. Connective Nature of the compound Symbol Symbolic Negation

statement formed by the form
Connective.
1. and Conjuction  p q (~ p)  (~ q)
2. or Disjunction  p q (~ p)  (~ q)
3. not negation ~ ~p ~(~ p) = p
4. If then implication or  pq p  (~ q)
conditional
5. If then equivalence or  p  q [ p(~q) ] [ q  (~ p)]
only if biconditional
Truth table :
Let S(p, q, r) be a compound statement consisting of sub statements p, q, r, .... etc. A simple concise
way to show the relationship between the truth table of S and the truth values of its substatements
p, q, r, ... etc. is by means of a table called the truth table for the statement S.

Example:
(1) Construct the truth table for [ p  (~ p ) ]
p ~ p [ p  (~ p ) ]
T F F
F T F

(2) Construct truth table for (i) p  q and (ii) p  q

(i) p q p q (ii) p q p q
T T T T T T
T F F T F T
F T F F T T
F F F F F F

Tautologies and contradiction:

A statement is said to be tautology if it is true for all logical possibilities. Analogously a statement is said
to be a contradiction if it is false for all logical possibilities.
A straight forward method to determine whether a given statement is tautology (or contradiction) is to
construct its truth table. We denote tautology by 't' and contradiction by 'C'.

Logical equivalence:
Two statements S1 (p, q, r, ...) and S2 (p, q, r, ....) are said to be logically equivalent, or simply equivalent
if they have the same truth values for all logical possibilities and denoted by
S1 (p, q, r, ...)  S2 (p, q, r, ....)

Note:
(1) p  q  ( ~ p)  q (Conditional statement)
(2) ~ ( p  q)  p  (~ q) (Negation of Conditional statement)
(3) p  q  ( ~ q)  (~ p) (Contrapositive of Conditional statement)
(4) p  q  (p  q)  (q  p) (Bicond statement)
(5) ~ ( p  q)  ( p  ~ q)  (~ p  q) (Negation of Biconditional statement)

Duality:
Two compound statements S1 and S2 are said to be duals of each other if one can be obained from other
by replacing  by  and  by  . The connections  and  are called duals of each other..

Algebra of statements:
1. Idempotent laws : If p is any statement then (a) p  p  p (b) p  p  p
2. Associative laws : If p, q and r are any three statements, then
(a) p  (q  r) = (p  q)  r (b) p  (q  r) = (p  q)  r
3. Commutative laws: If p and q are two statements, then
(a) p  q  q  p (b) p  q  q  p
4. Distributive Laws: If p, q and r are three statements then,
(a) p  (q  r)  (p  q)  (p  r)
(b) p  (q  r)  ( p  q)  (p  r)
5. Identity laws: If p is any statement, t is tautology and c is contradiction, then
(a) p  t = t (b) p  t = p (c) p  c = p (d) p  c = c
6. Complement laws: If t is tautology , c is a contradiction and p is any statement, then
(a) p  (~ p)  t (b) p  (~ p)  c
(c) ~ t  c (d) ~ c  t
7. Involution law: If p and q be any two statements then ~ (~ p)  p

Definition :
A non empty set B together with two operations generally denoted by '+' and '.' is said to be a Boolean
Algebra if the following axioms hold:

(I) For all x, y  B

(a) x+y B (Closure property for +)
(b) x, y  B (Closure property for .)
(II) For all x, y  B
(a) x+y=y+x (Commutative law of +)
(b) x.y =y.x (Commutative law of .)
(III) For all x, y and z in B
(a) (x + y) + z = x + (y + z) (Associative law of +)
(b) (x . y) . z = x. (y . z) (Associative law of .)
(IV) (a) x + (y. z) = (x + y) . (x + z) (Distributive law of + over .)
(b) x . (y + z) = (x . y) + (x . z) (Distributive law of . over +)
(V) There exists elements denoted by 0 and 1 in B. Such that for all x  B.
(a) x+0=x (0 is identity for +)
(b) x.1=x (1 is identity for .)
(VI) For each x  B, there exists an element denoted by x, called the component or negation of x, in B such
that
(a) x + x = 1 (b) x . x = 0 (Complement law)
* Here '+' and '.' are not ordinary addition and multiplication. These are simply operations.

Important points:
1. Boolean algebra is designated as (B , '+' , '.' , ' ' ' , 0, 1 ) in order to emphasise it six parts, namely set B,
the two binary operations '+' and '.' , the complement operation ' ' ' and the two special elements 0 and
1. The symbols 0 and 1 not necessarily represent the numbers zero and one but elements are called zero
elements and unit elements.
2. For the set S of all logical statements, the operations  and  play the roles of '+' and '.' respectively..
The tautology t and the contradiction C play the roles of 1 and 0, and the operation '~' plays the role
' ' '.
3. For P(A), the set of all subsets of a set A, the operations  and  play the roles of '+' and '.' , A and
 play the roles of 1 and 0, and complementation plays the role of ' ' ' .
Principal of duality:
The dual of any statement in a boolean algebra B is the statement obtained by interchanging the elements
0 and 1 in the original statement.
Concept of duality as defined in mathematical logic is same here, the only difference between the two is
of notations as '+' is used for  , '.' is used for  , 0 is used for contradiction c and 1 used for the
tautology t.
Principle of Duality: Dual of any theorem in Boolean algebra is also a theorem.

Theorem 1:In a Boolean algebra 0 and the unit element 1 are unique.
Theorem 2: Let B be a Boolean algebra. Then for any x and y in b we have,
(a) x + x = x (a) x . x = x
(b) x + 1 = 1 (b) x . 0 = 0
(c) x + (x.y) = x (c) x. (x + y) = x
(d) 0 = 1 (d) 1 = 0
(e) (x) = x
(f) (x + y) = x . y (f ) (x.y) = x + y
Note that a' , b' , c' , d' and f ' are duals of a, b , c, d and f.

Arguments and their validity:

An argument is the assertion that statement S, follows from other statements , S 1 , S2 , S3 , ...Sn We
denote the argument by (S1 , S2 , S3 , .... ,Sn ; S). The statement S is called the comclusion and the
statements S1 , S2 , ...., Sn are called hypothesis.
An argument consisting of the hypothesis S1 , S2 , ... , Sn and conclusion S is said to be valid if S is true
whenever all S1 , S2 , .... , Sn are true.

Application of Boolean algebra to switching circuits :

Switches p and q are in series. Switches p and q are in parallel.

Switches Lamp Switches Lamp

p q State p q State
closed closed on closed closed on
closed open off closed open on
open closed off open closed on
open open off open open off

If we replace the words 'closed' and 'on' by the word 'True (or T)' and words 'open' and 'off' by the
word 'False (or F)' then the tables becomes truth table for logical experiment p  q and p  q respectively..
In the language of logic we use symbols 1 and 0 to represent T and F.
 Switches Lamp Switches Lamp
p q State p q State
1 1 1 1 1 1
1 0 0 1 0 1
0 1 0 1 1 1
1 1 1 1 1 1

Switches p and q are in series, i.e. p  q Switches p and q are in parallel, i.e. p  q .

These type of tables are called input/output tables with input as all possible values in bits of the switches
p, q etc. and output as the corresponding values in bits of their outcome.
We define the logical operations '+' and '.' on the set of bits {0, 1} by

Operation OR (+) Operation AND (.)

1+1=1 T  T=T 1.1=1 T  T=T
1+0=1 T  F=T 1.0=0 T  F=F
0+1=1 F  T=T 0.1=0 F  T=F
0+0=0 F F=F 0.0=0 F F=F

The NOT operation ',' on the set {0, 1} is defined by 0= 1 as ~ F = T and 1 = 0 as ~T = F.

Definition 2:
Let {B, + , . , ' , 0 , 1, } be a Boolean algebra and x 1 , x2 , ....., xn are in B. Then Boolean expressions
in x1, x2 , ....,xn are defined recursivley as follows:
(I) 0, 1, x1 , x2 , ... , xn are all Boolean expression.
(II) If x and y are Boolean expressions , then
(a) x
(b) x + y (or x  y)
(c) x . y (or x  y)
are also Boolean expressions.
Note: We denote a Boolean expression X in x1 , x2 , ...., xn by X( x1 , x2 , .... , xn)
Definition 3:
Let X(x1 , x2 , ...., xn) be a boolean expression in x 1 , x2 , ...,xn . Then a function f of the form
f (x1 , x2 , ...,xn) = X (x1 , x2 , ..., xn) is called a Boolean function.
Three basic gates :
Gates are circuits constructed using solid state devices, which are capable of switching voltage levels (
bits 0 and 1).
The input / output tables for these gates are similar to the truth tables of conjuction, discunjuction and
negation respectively with T = 1 and F = 0.

Definition: An AND gate is a Boolean function defined by f (x 1, x2) = x1.x2 x1 , x2  {0, 1}

Input Output
x1 x2 x1 . x2
1 1 1
1 0 0
0 1 0
0 0 0
Definition: An OR gate is a Boolean function defined by f (x1, x2) = x1 + x2 x1 , x2  {0, 1}
Input Output
x1 x2 x1 + x2
1 1 1
1 0 1
0 1 1
0 0 0

Definition: An NOT gate is a Boolean function defined by f (x) = x x1 , x2  {0, 1}

Input Output
x x'
0 1
1 0

(1) (2)

In the circuit (1) :

In a circuit if the output S is uniquely defined for each combination of inputs x1, x2and x3 . Such a circuit
is said to be combinatorial circuit or combinatorial circuit.

In the circuit (2) :

We observe that if x1 = 1 and x2 = 0 then the inputs to the AND gate are 1 and 0 and so the output of
the AND gate is 0 . Which is the input to the NOT gate which yields output 1 i.e.
S = 1. But the diagram states that x2 = S i.e. 0 = 1 a contradiction. Therefore we conclude that output S
is not uniquely defined. Such a circuit is not a combinational circuit.

Definition:
Two combinatorial circuits are equivalent if their input/output tables are identical.

Input Output Input Output

x1 x2 S1 x1 x2 S2
1 1 0 1 1 0
1 0 0 1 0 0
0 1 0 0 1 0
0 0 1 0 0 1
 SUGGESTED EXERCISE

Q1. Let B = { {1} , {2} , {1, 2 } ,  }. Show that (B ,  ,  , ' ,  , {1, 2 } ) is a Boolean Algebra.

Q2. Let L be set of all logical statements. Define operations '+' , '.' and ' ' ' by
p+q=p  q ; p.q=p  q ; p'=~p
for all p, q  L where  ,  , ~ has usual meaning in mathematical logic.
Show that (L , + , . , ' , C , t ) is a Boolean Algebra.

Q3. Let B be a Boolean algebra. Then, for any x and y in B, prove

(i) (x + y) . (x + 1) = x + x . y + y
(ii) x = 0 if and only if y = x.y' + x'.y + x'.y for all y
(iii) x + x. (y + 1) = x

Q4. Construct truth tables for the following

(i) [ p  (~ p)  q) ]  q
(ii) p  (q  r)
(iii) [ p  (~ r)  (q  r)

Q5. Which of the following are equivalent ?

(i) p  q ; (~ p)  (~ q)
(ii) p  q ; ( p  q)  (~ p  (~ q) )

Q6. Examine the validity of the folloiwng arguments:

(i) S1 : p  q ; S 2 : q  p ; S : p  q
(ii) S1 : [ p  (~ q) ]  r ; S2 : p  q ; S3 : q  p ; S : r

Q7. Construct an input output table for each of the following Boolean Algebra functions:
(i) f (x1 , x2 , x3) = ( (x1 . x2') + x3) . x1'
(ii) f (x1 , x2) = (x1 . x2') + x2
Q8. Write the Boolean expression for the following input/output table. Show that it is a Boolean function and
also draw its arrow diagram.

Input Output
x1 x2 x3 S
1 1 1 1
1 1 0 0
1 0 1 0
1 0 0 1
0 1 1 0
0 1 0 0
0 0 1 1
0 0 0 0

Q9. Find the combinatorial circuit corresponding to the following Boolean expressions:
(i) x1 + (x1' . x2)
(ii) {x1 + (x2' . x3) } + x3
(iii) {x1' + (x2' . x3)} + x2
Q10. Prove Demorgans Laws for any elements a, b in a Boolean algebra. i.e. prove
(i) (a + b)' = a' b' (ii) (a b) ' = a' + b'

Q11. Simplify
(i) { [ (a '  b') '  c]  (a  c) } ' a, b  B
(ii) ( x  y)  [ (x  y ' )  y] ' x, y  B
where B is a Boolean algebra

Q12. Draw the circuit which realizes the function a  [ (b  d')  (c'  (a  d  c')]  b

Q13. Write the Boolean expression corresponding to the following switching circuit. Use laws of Boolean
algebra to simplify the circuit. Construct the network for the simplified circuit.

Q14. If A, B, C represent three switches in an on position and A', B' and C' represent the switches in an off
position, then construct a network for the polynomial ABC + AB'C + A'B'C. Using the laws of the
Booean algebra, show that above polynomial is equivalent to C(A+ B') and construct an equivalent
switching circuit.

Q15. Simplify the combinational circuit :

Q16. For each x in a Boolean Algebra B, prove that

x  y  1
  y  x
x.y  0 
 ANSWER KEY

p q ~p ~pq p(~p q) p (~p q) q

T T F F T T
T F F F T F
Q4. (i)
F T T T T T
F F T F F T

p q r qr p q r)

T T T T T
T T F F F
T F T T T
T F F T T
(ii) F T T T F
F T F F F
F F T T F
F F F T F

p q r ~r p ~ r) qr (p ~r)  (q r)

T T T F F T T
T T F T T T T
T F T F F T T
(iii) T F F T T F F
F T T F F T T
F T F T F T T
F F T F F T T
F F F T F F T

Q5. No , Yes Q6. (i) invalid ; (ii) invalid

x1 x2 x3 x'2 x1.x'2 (x1.x'2 ) + x3 x'1 ( (x1.x'2 ) + x3 ). x'1

0 0 0 1 0 0 1 0
0 0 1 1 0 1 1 1
0 1 0 0 0 0 1 0
0 1 1 0 0 1 1 1
Q7. (i) 1 0 0 1 1 1 0 0
1 0 1 1 1 1 0 0
1 1 0 0 0 0 0 0
1 1 1 0 0 1 0 0

x1 x2 x1.x2 (x1.x2 )' (x1.x2 )' + x2

1 1 1 0 1
1 0 0 1 1
(ii)
0 1 0 1 1
0 0 0 1 1
Q8. f (x) = x1 · x2 · x3 + x1 · x2' · x3' + x1' · x2' · x3

Arrow Diagram

Q9. (i)

(ii)

(iii)

Q11. (i) (a'  c') ; (ii) 1

Q12.

Q13. pq + r (r ' + q) (p' + r q ')

Simplified form: pq + qr

Q14. ]

Q15.