DIS_GT IMP QUESTIONS 1-6

Download as pdf or txt
Download as pdf or txt
You are on page 1of 8

Unit I

1. Show that R ∨ S follows logically from the premises C ∨ D, (C ∨ D) → ¬H, ¬H→(A ∧ ¬B) and
(A ∧ ¬B) → (R ∨ S)
2. Show that the premises “It is not sunny this afternoon and it is colder than yesterday,” “We will
go swimming only if it is sunny,” “If we do not go swimming, then we will take a canoe trip,”
and “If we take a canoe trip, then we will be home by sunset” lead to the conclusion “We will be
home by sunset.”
3. Given the truth values of P & Q as T, & those of R & S as F. Find the truth value of the
following.
(¬ (P ∧ Q) ∨¬R) ∨ ((Q ↔¬P) → ( R ∨¬S)
4. Show that ((Q ∧ A) →C ) ∧ (A→(P ∨ C)) (A ∧ (P→Q)) →C by using logical
equivalence.

5. Translate these statement into English where C(x) is “x is a comedian” and F(x) is “x is funny”
and the domain consist of all people.

a) ∀x (C(x) →F(x))
b) ∀x (C(x) ∧ F(x))
c) ∃x (C(x) →F(x))
d) ∃x (C(x) ∧ F(x))
6. Show that (¬P∧ (¬ Q ∧ R )) ∨ (Q ∧ R) ∨ (P ∧ R) R by using logical equivalence.
7. Show the following equivalence
i. A → (B ∨ C) (A ∧ ¬B) →C
ii. (P ∨ Q) → C (P→C) ∧ (Q→C)
8. Demonstrate R is a valid inference from the premises P → Q, Q → R and P
9. Let P(x) be the statement “x speaks more than five hours every weekday in class”, where the
domain for x consist of all students. Express each of these quantification I English.

Unit II
1. Explain the following terms with suitable examples.
i. Set ii. Venn Diagram
iii. Countable set iv. Power set
v. Cardinality

2. Draw the venn diagram for following representation


i. (A⊆B) ∩ (B⊆C)
ii. (A⊂B) ∩ (B⊂C)
iii. A–B
iv. (A⊂B) ∩ (A⊂C)
3. Let given R={(1,1),(1,3), (3,2),(3,4),(4,2)}, S={(2,1),(3,3),(3,4),(4,1)}. Evaluate following terms
R∘S, S∘R, R∘R, S∘S, (R∘S)∘R, R∘(S∘R), R3
4. Use set builder notation and logical equivalences to establish the first De Morgan law

5. What is the function and Composition of function? Explain its basic types with examples.
6. Prove that A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪C) by using logical equivalence and membership table.
7. What is relation and its basic properties with example.
8. Find formulae for sequences with following first five terms
a. 1, 1/2,1/4, 1/8, 1/16
b. 1,3,5,7,9
c. 1,-1,1,-1,1
9. What are the Cartesian product
i. AXBXC ii. AXB
iii. BXC iv. A2
Where A={0,1}, B = {1,2} and C={0,1,2}
10. Let A = {a,b,c}, B = {x ,y} and C ={0,1} Find
i. AxBxC ii. CxBxA
iii. CxAxB iv. BxBxB
11. Illustrate in brief following function with example
i. One to one function
ii. Onto function
iii. Bijection function
12. What is the value of following summations.
i. ∑1<= x<=5 x2
ii. ∑4<= x<=5 (-1)x
iii. ∑1<= j<=5 j2 + 3

Unit III
1. Show that every element in a group is its inverse then group must be Abelian.
2. Consider a set B = {0,1} and the operation + and X on B as given below
+ 0 1 X 0 1
0 0 1 0 0 0
1 1 0 1 0 1

Determine whether the given system is semigroup or not.


3. Write down composition <Z6, +6>, <Z6*, X6> where Z6*= Z6 –{[0]}.
4. Find the left coset of {[0],[4]} in group <Z7, +7>.
5. Design composition table for <Z7, +7>, <Z7, X7>
6. What are the properties of Abelian group. Explain with example.
7. Show that <P(S), U> & <P(S), ∩> are monoid, where S = non empty set and P(S) = power set of S
set and also draw composition table for U & ∩.
8. In a group <G,*>, if (a*b)2 = a2 * b2 a,b ∈ G then show that G is abelian.
9. Show that the set N is a monoid with respect to multiplication
10. Let <G,*> is group where G= <α, β, γ, δ> and * on G is given in composition table.
* α β γ δ
α α β γ δ
β β α δ γ
γ γ δ β α
δ δ γ α β

Find out identity element & inverse of each element of group.

Unit IV
1. Obtain product of sum expansion
a. (x1⊕x2)’ *x3
b. x1⊕x2
c. x1* x2
2. Give the K-map representation for given Boolean function
f(a, b, c) = a(b + c)
3. Let S = {a b, c}, Draw the diagram of <P(s), ⊆ >.
4. Obtain simplified Boolean expression which are equivalent to this expression
a. m0 + m7
b. m0 + m1 + m2+ m3
5. Find the K-map for
i. xy + x’y
ii. xy’ + xy
iii. xy’+x’y+x’y’
6. Draw the Hasse Diagram <Sn , D>. n be an integer & Sn contains all divisions of n, for n =6, 30.
7. Obtain Boolean expression in an equivalent sum of product canonical form in three variable x1, x 2,
x3.
a. x1* x2
b. x1⊕x2
8. Find the complement of every element of lattice <Sn , D> for n=30 & 45. Draw lattice.
9. Use K-map to find sum of product expression using each of function
a. f(a,b,c) = ∑(0,1,4,6)
b. f(a,b,c,d) = ∑ (0,5,7,8,12,14)
10. Define complemented lattice & find complement of every element of lattice <P(L), ⊆ >, L = {α, β,
γ}

Unit V
1. Show that in a complete binary tree total no. of edges is given by 2(nt -1) where nt is the no. of
terminal nodes.
2. ((x+y)↑2)+((x-4)/3) ? what is the ordered rooted tree that represents the expression. Express
preorder & postorder.
3. Use prim’s & Krushkal’s algorithm to find minimum spanning tree in the weighted graph shown
in figure.
4. Construct binary tree for given mathematical expression
i. a+b*c
ii. (a+b)*(c+d)/e
iii. (A+B)/(C-D)
5. Evaluate the expression
i. 723*- 4↑93/+
ii. + - *235/↑234
6. Use Depth-First search to find a spanning tree for the graph G

7. Express given trees in inorder expression


8. Convert the given tree into binary tree.

Unit VI
1. Determine whether the graph G and H are isomorphic.

2. What is graph? Explain different types of graph with example.


3. Which of the G1, G2 & G3 have an Euler circuit? of these that do not, which have an Euler
path?

4. Construct Adjacency matrix


5. Represent the graph shown in fig. with incidence matrix

6. Define the following term with example


i. Simple graph
ii. Path
iii. Strongly connected graph
iv. Weakly connected graph
v. Bipartite graph
7. With the given graph i, ii, iii, iv determine whether the graph is bipartite or not.
8. How many paths of length four are there from a to d in the simple graph G in fig

9. Show that digraph is isomorphic

10. Draw the digraphs with the given matrix as a adjacency matrix

You might also like