# Study Material

**Teerthankar Mahaveer University, Moradabad**

**Subject**: CBNST
**Unit: - 1**

*Q1. *What is Proposition? Explain with the help of suitable example.

Q2. State wheather which of the following are propositions or not with reason:

a.)there are seven days in a week.

b.)2+2=5

c.)The earth in flat

d.)The equation x2+x+1=0 has no real root.

e.)43>=21

f.)4€ {1,3,5}

g.)It will rain tomorrow

h.)X+3.=5

i.)Bring that book!

j.)This statement is false

Q3. Explain the basic & derived logical operations?

Q4. Using the following statements:

P: Ram is tall, q: Ram is beautiful

Write the following statements in symbol form:

- Ram is tall and beautiful
- Ram is tall but not beautiful
- It is false that Ram is short or beautiful
- Ram is tall or Ram is short and beautiful

Q5. Write English sentences corresponding to the following statement:

- ((┐p) ^q)→ r
- r →(pνq)
- (┐p)→ ((┐q) vp)
- (qv(┐p))↔r

Q6. What is converse , inverse and contra position proposition contract the truth table at each.

Q7. What is truth table? Construct the truth table at each logical operation.

Q8. Construct the truth table at following:-

(i) (┐pvq) → q

(ii) ┐(pvq) v(p↔q)

(iii) (┐p→r) ^ (p↔q)

Q9. What is tautology, contradiction and contingency. Explain with the help of examples?

Q10. Construct truth tables to find whether each of the following is a tautology a

contingency or a contradiction.

(i) p→ (q→p)

(ii) p^q)^ ┐(pvq)

(iii) (p^r) ↔ q

Q11. What is logical Equivalence? Prove that the following are the logically equivalent:-

(i) p→q ≡ ┐pvq

(ii) p→(q→r) ≡(p^q)→r

Q12. What is logical implication? Explain this with help of example.

Q13. Write the rules of algebra of propositions.

Q14. What is quantifier? Explain the different types of quantity.

Q15. Write the negation of a quantified statement and also write in symbol: for all x ,

x<5 or x>=5

Q16. Write the rules of informers.

Q17. What is principles of mathematical induction?

Q18. Prove by induction:

1+2+3+---------------+ n = (n(n+1))/2

Q19. Show that x3 +2n is divisible by 3 for all n>=1.

Q20 .Prove that 2n <= n! for n>=4.

**Unit: - 2**

- What is Boolean algebra? How it different from conventional algebra?
- Write the axioms of Boolean algebra?
- Explain all types of logic gates with the help of diagram.
- What is Boolean expression? Write the Boolean expression of all the logic gates.
- Describe the SOP and POS representations for logic expressions.
- How will you convert the SOP into standard SOP form.
- How will you convert the SOP into standard POS form.
- What is K-Map and how will you simplify of Boolean expression using K-map.
- Using K-map, simplify the following expressions:-
- x= A`B`C` + A`B`C` + ABC`
- x= a`bc`d` + abc`d`+ a`bcd` +abcd`

- F (A,B,C,D) = ∑ (0,1,2,3,4,5,7,8,9,11) using K-Map.
- Simplify F (x,y,z) = ∏ (0,1,5,3,2)
- Convert the expression y = AB+AC+BC into standard SOP form
- Convert the expression y= (A+B) (A+C)(B+C`) into standard pos form.
- Represent the standard POS expression y=(A+B+C) (A+B`+C)(Ā+B+C) on k map.
- Plot the y=A’B’C’D’+A’B’CD+A’BCD’+ABC’D’ on k-map.
- Represent basic gates using NAND gate.
- Represent basic gates using NOR gate.
- Construct the logic circuit of S=PQ’R+PQ’R’+P’Q’R
- Make the logic circuit of each logic gate.
- What are universal gates? Why they called universal.

**Unit: - 3**

Q1. What is set? Explain the various ways to describe a set.

Q2. Describe the set terminology.

Q3. Explian the properties of set.

Q4. Explain the identities of set.

Q5. What is Cartesian product? Describe it with example.

Q6. What is Venn diagram? Show all operations of set through Venn diagram.

Q7. What is Relation? Also explain domain & range.

Q8. How will you represent a relation? Explain.

Q9. Explian the pictorial representation of relation.

Q10. Explian the various types of relation.

Q11. Explain the composition of relation with the help of example.

Q12. Explain the Equivalence relation & class.

Q13. Draw the pictorial representation of relation “less than” on {1,2,3,4}

Q14. Define function. Also describe domain &range of it.

Q15. Explain the various types of function.

Q16. Explian the composition of function.

Q17. how will you classify the function?

Q18. Let function f(x) = 2x-3 and g(x) = x^{2 }+3x+5. find

(i) Gof

(ii) Fog

Q19. Let A={1,2,3,4} and let R={(1,1),(1,2)(2,1)(2,2)(3,3)(3,4)(4,3)(4,4)} find

wheather the relation is reflexive irreflexive symmetric ,anti symmetric or transitive

Q20. let A=(1,2,3,4,5,6,7) let R={(x,y):(x-y) is divisible by3 find whether R is an

equivalence relations or not. also draw the diagraph of R.

**Unit: - 4**

Q1.What is permutation? Proof that P(n,r)=n(n-1)(n-2)--------(n-r+1)

Q2.How many 4 digit decimal number can be formed so that no digit repeat.

Q3.In how many ways can 3 exams be scheduled within a 5 day period so that no two exams be scheduled on the same day.

Q4.Find the no. different permutations of the letter in the word COMPUTER.

Q5. How many words are there for 5 distinct letters the word COMPUTER.

Q6.What is Combination? Proof the formula.

Q7.What is recurrence reltation? Define linear recurrence relation with Constant coefficients.

Q8.What is homogeneous solution? Find the different roots equation.

Q9.Find the solution of a(r+2)-a(r+1)-6a(r)=0.

Q10.Find the solution of a(r+2)+2a(r+1)-3a(r)=0. That satisfy a(0)=1,a(1)=2.

Q11.Find the solution of 12a(r-2)+6a(r-1)+a(r)+8a(r-3)=0.

Q12 What is generating function? Explain the types.

Q13 Find g.f if a(r)=s^{r} and (1,3,9,---------)

Q14.If a(r)=7.3^{r }find g.f.

Q15.If a(r)=3^{r+2} find g.f

Q16.If a(r)=3^{r}+4^{r+1} find g.f

Q17.Find g.f if a(r)=0 r odd =2^{r+1 }r even

Q18.Find a(r)=if g.f A(z)=1/1+z

Q19.Find a(r)=if g.f A(z)=(3-5z)/(1-2z-3z^{2}).

Q20.Find a(r)=if g.f A(z)=1/(5-6z+z^{2}).

**Unit: - 5**

- What is graph? Give the graphical representation of graph.
- Describe the graph terminology.
- Explain the applications of graph.
- Describe finite & infinite graphs.
- Describe various types of graph.
- Describe tree & its properties.
- Define rooted & binary tree.
- Explain the traversal of tree.
- Draw the complete bipartite graph K2,3 & K4,6.
- Is k3 bipartite graph?
- Is there a Hamiltonian ckt. In K4,5 & K4,6 ?
- Define Euler Path & circuits.
- Define Hamiltonian Paths & circuits.
- Describe the representation of graphs.
- Define rooted tree & siblings.
- Express (((a+b*c)*d-e)/(f+g)) in the form of Binary tree.
- Explain the properties of tree.
- Express c*d*e in the form of Binary tree.
- Define planer graphs with the help of diagram.
- How many edges must a planer graph have if has 7 regions & 5 edges. Draw it.