UGC NET Computer Science Discrete Mathematics Previous Year Questions (PYQs) – Page 1 of 14
Study Stuff for MCA Examinations
For the given two machines which of the following is correct?
Solution
From the diagrams:
• Both machines are deterministic (each state has exactly one transition for each input symbol).
• The first machine has states A and B with transitions on a and b.
• The second machine has states A, B, C, but the accepted language behavior matches the first machine.
Both machines accept the same language, even though the number of states differs.
Thus they are equivalent machines.
Solution
“my friends” means $f(x)$.
“not perfect” means $\neg p(x)$.
So, the statement becomes:
$\exists x(f(x)\land \neg p(x))$
Solution
Each clause is a disjunction of literals.
Example:
$(p\vee \neg q)\wedge(r\vee s)$
Here, $(p\vee \neg q)$ and $(r\vee s)$ are clauses.
So, clauses in CNF are disjunction of literals.
A. Reflexive
B. Antisymmetric
C. Symmetric
Let $A=\{a,b,c,d,e,f,g\}$ and
$R=\{(a,a),(b,b),(c,d),(c,g),(d,g),(e,e),(f,f),(g,g)\}$
be a relation on $A$. Which of the following property/properties is/are satisfied by the relation $R$?
Solution
But $(c,c)$ and $(d,d)$ are missing.
So, relation is not reflexive.
For antisymmetric relation, if $(x,y)$ and $(y,x)$ both exist, then $x=y$.
Here, no reverse pair exists for $(c,d),(c,g),(d,g)$.
So, relation is antisymmetric.
For symmetric relation, if $(x,y)$ exists, then $(y,x)$ must also exist.
But $(c,d)$ exists and $(d,c)$ does not exist.
So, relation is not symmetric.
Therefore, relation satisfies B and not A.
Solution
Number of spanning trees:
For complete graph:
$\tau(K_n)=n^{n-2}$
A: $K_3 = 3^{1} = 3$
B: $K_4 = 4^{2} = 16$
For complete bipartite graph:
$\tau(K_{m,n}) = m^{n-1} n^{m-1}$
C: $K_{2,2} = 2^{1} \times 2^{1} = 4$
For cycle graph:
$\tau(C_n)=n$
D: $C_5 = 5$
Thus:
A = 3
C = 4
D = 5
B = 16
Increasing order:
A, C, D, B
| (A) $\forall x(P(x)\vee Q(x))$ | Premise |
| (B) $P(c)\vee Q(c)$ | Universal instantiation from (A) |
| (C) $P(c)$ | Simplification from (B) |
| (D) $\forall xP(x)$ | Universal generalization of (C) |
| (E) $Q(c)$ | Simplification from (B) |
| (F) $\forall xQ(x)$ | Universal generalization of (E) |
| (G) $(\forall xP(x))\wedge(\forall xQ(x))$ | Conjunction of (D) and (F) |
Solution
$P(c)\vee Q(c)$
So, step (B) is correct.
But from $P(c)\vee Q(c)$, we cannot conclude $P(c)$ alone.
Also, we cannot conclude $Q(c)$ alone.
So, steps (C) and (E) are not correct inferences.
Step (G) would be correct only if (D) and (F) were validly obtained.
Hence, the main error is in steps (C) and (E).
Four persons: P, Q, R and S are in police custody and one of them has committed a crime. They confess as follows:
A. Person P: Q did it.
B. Person Q: S did it.
C. Person R: I did not do it.
D. Person S: Q lied.
If exactly one of the statements is false, which of the following is the guilty person.
Solution
Check each case one by one.
Case 1: Suppose P is guilty.
P says: Q did it → False
Q says: S did it → False
R says: I did not do it → True
S says: Q lied → True
Here, two statements are false. So, P is not guilty.
Case 2: Suppose Q is guilty.
P says: Q did it → True
Q says: S did it → False
R says: I did not do it → True
S says: Q lied → True
Here, exactly one statement is false.
So, Q can be guilty.
Case 3: Suppose R is guilty.
P says: Q did it → False
Q says: S did it → False
R says: I did not do it → False
S says: Q lied → True
Here, three statements are false. So, R is not guilty.
Case 4: Suppose S is guilty.
P says: Q did it → False
Q says: S did it → True
R says: I did not do it → True
S says: Q lied → False
Here, two statements are false. So, S is not guilty.
Therefore, the guilty person is Q.
Solution
A contains numbers of the form:
$4n + 2$
So, numbers in A are:
$6, 10, 14, 18, 22, 26, 30, ...$
B contains multiples of 3:
$3, 6, 9, 12, 15, 18, 21, 24, 27, 30, ...$
Common elements are:
$6, 18, 30, 42, ...$
These can be written as:
$12n - 6$
Statement 1:
Given a graph $G=(V,E)$ in which each vertex $v \in V$ has an associated positive weight $w(v)$, we can use linear programming to find the lower bound on the weight of the minimum-weight vertex cover.
Statement 2:
The lower bound can be found by maximizing the following
$ \sum_{v \in V} w(v)x(v) $
subject to
$ x(u)+x(v) \ge 1 $ for each $(u,v) \in E$
$ x(v) \le 1 $ for each $v \in V$
$ x(v) \ge 0 $ for each $v \in V$
In the light of the above statements, choose the most appropriate answer from the options given below:
Solution
For minimum-weight vertex cover, we can write an integer linear programming formulation.
Its LP relaxation can be used to find a lower bound.
So, Statement 1 is correct.
But for minimum-weight vertex cover, the objective should be minimized, not maximized.
Correct objective should be:
$ \text{Minimize } \sum_{v \in V} w(v)x(v) $
Statement 2 says maximizing the objective, so Statement 2 is incorrect.
Solution
A: False when $r=1, p=0$ → Not tautology
B: False when $p=1, r=0$ → Not tautology
C:
$\sim p \rightarrow (p \rightarrow r)$
Always true → Tautology
D:
$(p \land r) \rightarrow (p \rightarrow r)$
Always true → Tautology
E:
$\sim(p \rightarrow r) \rightarrow p$
Always true → Tautology
Thus tautologies:
C, D, E
UGC NET Computer Science
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
UGC NET Computer Science
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
