Mathematical Foundations of Computer Science Mid - I, September - 2011

1.Which statement is false under all circumstances
  • Universally valid statement
  • Absurdity
  • Contingency
  • None of the above
Answer: B
2.The dual of the proposition (pvTo) Λ (�qvFo) is
  • (pΛFo) V (¬qΛTo)
  • (p Λ Fo)Λ(¬q Λ To )
  • (p V To) V (¬q V Fo)
  • (p V To) Λ (¬q V Fo)
Answer: A
3.For any propositions p and q, {[pΛ (p→q)] →q}
  • Contradiction
  • Tautology
  • Contingency
  • None of the above
Answer: B
4.Negation of ∀x (P(x) →Q(x)) is
  • ∀x (¬P(x) V Q(x))
  • ∃x (¬P(x) V Q(x))
  • ∃x (P(x) Λ ¬Q(x))
  • ∀x (P(x) Λ ¬Q(x))
Answer: C
5.Rewriting the argument “All birds can fly” using quantifiers, variables and predicate symbols gives
  • ∃x (B(x) → F(x))
  • ∀x B(x) Λ ∃∀x F(x)
  • ∃x B(x) V ∃x F(x)
  • ∀x (B(x) → F(x))
Answer: D
6.The relation ‘divides’ on set of positive integers is
  • Symmetric
  • Transitive
  • Asymmetric
  • Reflexive
Answer: D
7.A relation R on a set S is said to be partial ordering if it is
  • Reflexive, antisymmetric,
  • Reflexive, asymmetric, transitive
  • Reflexive, symmetric, transitive
  • None of these
Answer: A
8.The binary operation * defined on (R, *) where x*y = xy is
  • Associative
  • Not associative
  • Can’t be determined
  • Commutative
Answer: B
9.An isomorphism of a semi group onto itself is called a semi-group
  • Automorphism
  • Endomorphism
  • Isomorphism
  • None
Answer: A
10.The operation o on the set Q-{1} of all rational numbers except 1, defined by a o b = a b – ab satisfies
  • Associative
  • Closure
  • Commutative
  • All the above
Answer: D
11.Negation of ��x (P(x) ��Q(x)) is ___________________________________________
Answer: ∃ x, (P(x) Λ Q (x))
12.Express P↑Q in terms of ↓ only ______________
Answer: [(P↓P) ↓ (Q↓Q)] ↓ [(P↓P) ↓ (Q↓Q)]
13.What is universal modus pones rule ______________________________________
Answer: [x, (P(x) → Q(x))] Λ P(a) ⇒ Q(a).
14.� (p ↔ q) _________________
Answer: (PVQ) Λ ¬ (PΛQ) or (PΛ¬ Q) V (¬ PΛQ)
15.Write the relation determined by the graph shown below 23

Image not found.
______________________________________
Answer: R = {(1,2), (2,1), (2,3), (3,4), (5,4), (5,1)}
16.(P→Q) Λ (R→�Q) Λ R ⇒ _________
Answer: ¬ P
17.In a group (G,*) is said to be an abelian group if_____________
Answer: a * b = b*a, ∀ a, b∈ G
18.If o (A) = n, then o (P (A)) = ---------------------------
Answer: 2^n
19.Let f be defined by f(x) = 3x-7. Find a formula for the inverse function f-1: R→R, _______.
Answer: f-1 (x) = (x+7)/3.
20.Image not found.

Write the Least upper bounds of {3,5} for the above poset ({3,5,9,15,24,45}, |) ____________
Answer: 15