Paper 2 CS Discrete Structures and Optimization Part 1

Modus ponens rule / Rule of detachment: According to Modus ponens rule given P and P → Q, we can infer Q

Rules of Inteference!

Rules of Inteference!

“Boolean simplification
((R ∨ Q) ∧ (P ∨ Q’))
(R∨Q)∧(P∨Q’)∧(R∨P)
(PR ∨ Q’R ∨ PQ) ∧ (R∨P)
PR ∨ RQ’ ∨ PQR ∨ PR ∨ PRQ’ ∨ PQ
(RQ’∨PQ’R)∨(PQR∨PQ)∨PR
RQ’ ∨ PQ ∨ PR
((R ∨ Q) ∧ (P ∨ Q’) ∧ (R ∨ P)) “

This question can be solved by binomial distribution

“””If X then Y unless Z”” ⇒ ¬Z → (X→Y)
⇒ Z ∨ ¬X ∨ Y
⇒ ¬X ∨ Z ∨ Y
Option B: (X ∧ ¬Z) → Y
= ¬(X ∧ ¬Z ) ∨ Y
= ¬X ∨ Z ∨ Y
Hence, option is correct. “

“→ A pumping lemma (or) pumping argument states that, for a particular language to be a member of a language class, any sufficiently long string in the language contains a section, or sections, that can be removed, or repeated any number of times, with the resulting string remaining in that language.
→ The proofs of these lemmas typically require counting arguments such as the pigeonhole principle.
→ Hence, the logic of pumping lemma is a good example of the pigeonhole principle. “

WFF means well formed formula. Just draw truth table and you will see option C is correct

Theorem : Complete graph is an undirected graph in which each vertex is connected to every vertex, other than itself. If there are ‘n’ vertices then total edges in a complete graph is n(n-1)/2.

Draw the truth table and C is the answer. Its a very simple question.

“Given data,
— Set of positive integers=8
— A pair of numbers having the same remainder when divided by=?
Step-1: This problem, we can use pigeonhole principle.
Pigeonhole Principle: If there are ‘X’ positive integers to be placed in ‘Y’ possible remainder where Y < X, then there is at least one possible remainder which receives more than one positive integer. Option-A: Total number of possible remainders, divided by 7 is 0,1,2,3,4,5,6. These numbers are less than 8 only. Option-B,C and D: Total number of possible remainders, divided by 11, 13, 15 is greater than 8 "

The set of positive integers under the operation of ordinary multiplication is a monoid but not a group.

“Reflexive: A relation R is said to be reflexive if for all elements of a set x belongs to R (x,x) exists. \n
Since in above question {(1,1), (2,2),(3,3),(4,4),(5,5),(6,6)} does not exist in given relation so it is not reflexive. \n
Symmetric: A relation R is symmetric if (x,y) belong to R then (y,x) must belong to R. Since in above question (1,2) exists but (2,1) does not exist in given relation so given relation is not symmetric. \n
Transitive: A relation is transitive if (x,y) belongs to R and (y,z) belongs to R then (x,z) must belongs to R. \n
In above question (1, 2), (2, 3) exist in given relation but (1,3) does not exist there so given relation is not transitive. \n
Hence correct option is option \n”

Theorem : Complete graph is an undirected graph in which each vertex is connected to every vertex, other than itself. If there are ‘n’ vertices then total edges in a complete graph is n(n-1)/2.

“→ Initially calculate the possible cases of a relation i.e., R={(A,B), (C,B), (A,C)} \n
→ Now check whether the relation is transitive or commutative or etc.., \n
If a relation is commutative then if (A,B) present in the relation then (B,A) also need to exists. but in the relation (B,A) is not present. so given relation is not commutative. \n”

“By default we are using inorder traversal to evaluate it.
Inorder traversal starts from left,root and right.
Inorder traversal = (¬x1∨ x2) ∧ (¬x1∨ x2) “

“Option-i: FALSE because undirected graph will be cycle also.
Option-ii: TRUE because there is at least one path between any two distinct vertices of G. otherwise we are no calling as undirected graph.
Option-iii: TRUE. If G contains no cycles and has (n-1) edges.
Option-iv: FALSE “

“To find number of edges in complete graph using standard formula is n(n-1)/2. Here, n=4
= 4(4-3)/2
= (4*3)/2
= 12/2
= 6 “

“As they are independent, answer could be Option-A, though it need to be checked with zero average too.
Note: Original key given option-C is correct answer . NET 2009”

Solve using graph theory

“The given statement says that the Relation R contains x and x1 which are identical. Which means (x,x1) are same as (x,x).
We know that “” a relation of (x,x) type is an equivalence as it satisfies Reflexive, symmetric, transitive.
The answer would be option A, it is equivalence. “

“(13 / 4 * 3) % 5 + 1
Step-1: (13 / 4 * 3) % 5 + 1
Step-2: (3.25*3)%5+1
Step-3: 9.75%5+1
Step-4: 4.75+1
Step-5: 5.75
Note: ( ) having highest precedence then *,/ and % have same precedence order. “

For connected graph : Maximum is n(n-1)/2 and minimum is n – 1

“A partially ordered set is said to be a lattice if every two elements in the set have
1. Unique least upper bound
2. Unique greatest lower bound “