Questions:
 (a) Explain Tautologies and Contradiction with help of example.
Answer:
Tautologies and contradictions
Definition: A propositional expression is a tautology if and only if for all possible assignments of truth values to its variables its truth value is T
Example: P V ¬ P
P ¬ P P V ¬ P

T F T
F T T
Definition: A propositional expression is a contradiction if and only if for all possible assignments of truth values to its variables its truth value is F
Example: P Λ ¬ P
P ¬ P P Λ ¬ P

T F F
F T F
Usage of tautologies and contradictions  in proving the validity of arguments; for rewriting expressions using only the basic connectives.
(b) Prove that the following propositions are Tautology
 p V ~p (ii) ~(p ^ q) V q (iii) p => (p V q)
Answer:
A propositional expression is a tautology if and only if for all possible assignments of truth values to its variables its truth value is T
p

q

(¬(p ∧ q) ∨ q)

F

F

T

F

T

T

T

F

T

T

T

T

p

q

(p → (p ∨ q))

F

F

T

F

T

T

T

F

T

T

T

T

 Prove that with help of Boolean algebra
 Explain all logic gates with symbol and truth table. Simplyfy the Boolean expression
A+B(A+B)+A(A’+B)
Answer:
Logic gates
Digital systems are said to be constructed by using logic gates. These gates are the AND, OR, NOT, NAND, NOR, EXOR and EXNOR gates. The basic operations are described below with the aid of truth tables.
AND gate
The AND gate is an electronic circuit that gives a high output (1) only if all its inputs are high. A dot (.) is used to show the AND operation i.e. A.B. Bear in mind that this dot is sometimes omitted i.e. AB
OR gate
The OR gate is an electronic circuit that gives a high output (1) if one or more of its inputs are high. A plus (+) is used to show the OR operation.
NOT gate
The NOT gate is an electronic circuit that produces an inverted version of the input at its output. It is also known as an inverter. If the input variable is A, the inverted output is known as NOT A. This is also shown as A´, or A with a bar over the top, as shown at the outputs. The diagrams below show two ways that the NAND logic gate can be configured to produce a NOT gate. It can also be done using NOR logic gates in the same way.
NAND gate
This is a NOTAND gate which is equal to an AND gate followed by a NOT gate. The outputs of all NAND gates are high if any of the inputs are low. The symbol is an AND gate with a small circle on the output. The small circle represents inversion.
NOR gate
This is a NOTOR gate which is equal to an OR gate followed by a NOT gate. The outputs of all NOR gates are low if any of the inputs are high.
The symbol is an OR gate with a small circle on the output. The small circle represents inversion.
EXOR gate
The ´ExclusiveOR´ gate is a circuit which will give a high output if either, but not both, of its two inputs are high. An encircled plus sign () is used to show the EOR operation.
EXNOR gate
The ´ExclusiveNOR´ gate circuit does the opposite to the EOR gate. It will give a low output if either, but not both, of its two inputs are high. The symbol is an EXOR gate with a small circle on the output. The small circle represents inversion.
A+B(A+B)+A(A’+B)
A+B(A+B)+A*B
A+BA+B+A*B
A+BA+B+A*B
A+BA+B*B
A+B*A+B
A+B
Truth table:
The Boolean expression is reduced to (A + B)
Case Detail

a => b= 1
a=> c=1
b=> d= 1
d=> c= 1
So adjacency matrix is
a b c d
a 0 1 1 0
b 1 0 0 1
c 1 0 0 1
d 0 1 1 0
 Simplify the following Boolean function F(A,B,C,D)= Σ( 0,1,2,3,4,5,7,6,8,9,11)
Karnaugh Map


AB



00

01

11

10

CD

00

1

1

1

1

01

1

1

1

1

11

0

0

0

0

10

1

1

1

0

Truth Table
A

B

C

D

F(ABCD)

0

0

0

0


0

0

0

1


0

0

1

0


0

0

1

1


0

1

0

0


0

1

0

1


0

1

1

0


0

1

1

1


1

0

0

0


1

0

0

1


1

0

1

0


1

0

1

1


1

1

0

0


1

1

0

1


1

1

1

0


1

1

1

1


So required equation is
F(ABCD) =

C

‘+

A’ D

‘+

B D

‘

Assignment C
 Complement the expression by applying DeMorgan’s theorem (A+A’B)’?
Options
 AB
 A’B´
 A’B’ **
 AB’
 Find the minimum sum of product using KMap?
F= AB+AB’C+ABC
Options
 F=A’B+AC
 F=AB+AC’
 F=AB’+AC
 F=AB+AC**
3 what is the value of Boolean expression a+a’=?
Options
 1**
 2
 a
 a’
 Consider the following
p: Anil is rich q: Kanchan is poor
What is the symbolic form of the following statement?
Anil is poor and Kanchan is rich
Options
 ~p ^ q
 p ^ q**
 ~p ^ ~q
 None of above
 Consider the following
P: This computer is good q: This computer is cheap
What is the symbolic form of the following statement?
This computer is neither good nor cheap
Options
 ~p ^ q
 p ^ ~q
 (~p) ^ (~q)**
 None of above
 In which of the following gates the output is 1, if and only if at least one input is 1 ?
Options
 NOR
 AND
 OR**
 NAND
 In which of the following gates the output is 0, if and only if at least one input is 1 ?
Options
 NOT
 AND
 NOR**
 NAND
 What is the minimum number of two input NAND gates used to perform the function of two inputs OR gate?
Options
 Three**
 Two
 One
 Four
 Which of the following gates are added to the inputs of the OR gate to convert it to the NAND gate?
Options
 NOT**
 AND
 AND
 XOR
 What logic function is produced by adding an inverter to the output of an AND gate?
Options
 NAND**
 NOR
 XOR
 OR
 Which of the following Boolean algebra expressions is incorrect?
Options
 A+ A’+= A+B
 A+AB =B **
 (A+B)(A+B) = A+BC
 (A+B’)(A+B)=A
 The simplified form of the Boolean expression (X+Y+XY)(X+Z) is ?
Options
 X+Y+Z
 XY+YZ
 X+YZ**
 XZ+Y
 The simplified form of the Boolean expression (X+Y’+Z)(Z+Y’+Z’) (X+Y+Z) is ?
Options
 X’Y+Z’
 X+Y’Z**
 X
 XY+Z’
 A full binary tree with n leaves contains
Options
 n nodes
 log2n nodes
 (2n1) nodes **
 2n nodes
 A full binary tree with non leaf nodes contains
Options
 (2n+1) nodes **
 log2n nodes
 (n+1) nodes
 2n nodes
 A complete graph with five vertices is
Options
 Non planar
 planar
 a non regular graph
 a tree **
 Which of the following statement is true?
Options
 (A+ B)(A+C)=AC+BC
 (A+ B)(A+C)=AB+C
 (A+ B)(A+C)=A+BC **
 (A+ B)(A+C)=AC+B
 A non empty connected graph G is Eulerian if and only if its vertices are all of
Options
 Odd degre
 Even degree**
 Both (a) and (b)
 None
 A  is a closed path of none zero length that does not contain repeated edge.
Options
 Path
 Simple path
 Circuit**
 None
 A  is a path that does not contain a repeated vertex.
Options
 Path
 Simple path**
 Circuit
 None
 The maximum number of edges in any simple graph with n vertices is
Options
 n
 n+1
 n(n1)/2**
 None
 A simple graph is said to be  if every vertex in graph is connected with every other vertex
Options
 null
 regular
 complete **
 None
 A graph in which all vertices are equal degree is called a  graph
Options
 null
 regular**
 complete
 None
 What is the value of Boolean expression a + (a.b) =?
Options
 b
 a**
 ab
 a’
 What is the value of Boolean expression a + 1 =?
Options
 0
 a
 1**
 none
 Consider the following
P: Today is Tuesday q: It is raining r: it is cold
Write in simple sentence for q => (r ^ p)
This computer is neither good nor cheap
Options
 If today is Tuesday, then it is raining
 If today is not Tuesday, then it is raining or it is cold
 If it is not raining, then it is cold and today is Tuesday
 None of these
 If there exists at least one path between every pair of vertices in a graph, the graph is known as
Options
 Complete graph
 Disconnected graph
 Connected graph**
 Euler graph
 The length of Hamiltonian path (if exists) in a connected graph of n vertices is
Options
 n1**
 n
 n+1
 n/1
 If each node in a tree has value greater than every value in its left subtree and has value less than every value in its right subtree , the tree is known as
Options
 Complete tree
 Full binary tree
 Binary search tree**
 Threaded tree
 Which of the following statement is false ?
Options
 A tree contains a cycle**
 A tree with n nodes contains n1 edges
 A tree is a connected graph
 None
 Graph can be implemented using
Options
 arrays
 linked list**
 queue
 all of these
32. Traversing a binary tree first root and then left and right subtrees calledtraversal
Options
 postorder
 preorder**
 inorder
 all of these
33. A circuit is a connected graph which includes every vertex of the graph is known as
Options
 Euler
 Unicursal
 Hamiltorium**
 Clique
 The number of vertices of odd degree in a graph is
Options
 Always even**
 Always odd
 Either even or odd
 Always zero
 If a binary tree traversal in inorder, then numbers of the node are printed in order
Options
 Ascending
 Descending**
 randomly
 none of these
 Which gate is known as universal gate
Options
 NOT gate
 AND gate
 NAND gate**
 XOR gate
 is the value of Boolean expression (a .b)’ =?a
Options
 a+b
 a’+b’**
 b
 None of above
 Find the complement of Boolean expression xy’ +x’y
Options
 x+y
 (x’+y).(x+z’)**
 x+y’
 None
 A Karnaugh map in four variables is a square divided into 
Options
 8
 12
 14
 16**
 A tree with n nodes has  edges
Options
 n/2
 n1**
 n
 n+1
Solve by www.solvezone.in contact for more detail  8882309876