-
web.groovymark@gmail.com
- November 12, 2024
Question 01
Which of the following is true for an anti-reflexive relation?
a) Every element in the set is related to itself
b) No element in the set is related to itself
c) Every element in the set is related to some other element
d) Only some elements in the set are related to themselves
Correct Answer: b) No element in the set is related to itself
Explanation: In an anti-reflexive relation, no element in the set can be related to itself.
Question 02
Which of the following describes De Morgan’s Law for ¬(p∧q)?
a) ¬p∨¬q
b) ¬p∧¬q
c) p∨q
d) ¬p∨q
Correct Answer: a) ¬p∨¬q
Explanation: According to De Morgan's Law, ¬(p∧q) is equivalent to ¬p∨¬q.
Question 03
In Boolean algebra, what does the expression A.A simplify to?
a) A
b) 0
c) 1
d) ¬A
Correct Answer: a) A
Explanation: In Boolean algebra, A.A simplifies to A according to the Idempotent Law.
Question 04
Which of the following is an example of a tautology in propositional logic?
a) p∧¬p
b) p∨¬p
c) ¬(p∨q)\
d) p∧q
Correct Answer: b) p∨¬p
Explanation: p∨¬p is a tautology because it is always true, regardless of the truth value of p.
Question 05
What does the complement of A∨B simplify to in Boolean algebra?
a) ¬A∧¬B
b) A∧¬B
c) ¬A∨B
d) ¬A∨¬B
Correct Answer: a) ¬A∧¬B
Explanation: According to De Morgan's Law, ¬(A∨B) simplifies to ¬A∧¬B.
Question 06
What is the negation of the biconditional statement p↔q?
a) p∨¬q
b) ¬(p↔q)
c) (p∧¬q)∨(¬p∧q)
d) p∧q
Correct Answer: c) (p∧¬q)∨(¬p∧q)
Explanation: The negation of a biconditional statement is true when p and q have opposite truth values, which is represented by (p∧¬q)∨(¬p∧q).
Question 07
What is the result of applying the distributive law to p∧(q∨r)?
a) (p∧q)∨(p∧r)
b) (p∨q)∧(p∨r)
c) p∨(q∧r)
d) (p∨q)∧r
Correct Answer: a) (p∧q)∨(p∧r)
Explanation: The distributive law states that p∧(q∨r) is equivalent to (p∧q)∨(p∧r).
Question 08
Which of the following is an example of a valid argument form?
a) p∧¬p→q
b) p→q,¬q→¬p
c) p→q,p→r,q∧r→p
d) p∨q→¬p∧q
Correct Answer: b) p→q,¬q→¬p
Explanation: This is an example of Modus Tollens, a valid argument form that concludes ¬p from p→q and ¬q.
Question 09
Which of the following is true for a simple graph?
a) It contains no parallel edges and no loops
b) It contains only parallel edges
c) It contains only loops
d) It contains parallel edges and loops
Correct Answer: a) It contains no parallel edges and no loops
Explanation: A simple graph is a graph that has no parallel edges or loops.
Question 10
Which of the following best describes a complete graph?
a) Every vertex is connected to every other vertex
b) There is exactly one path between any two vertices
c) Every vertex has a self-loop
d) Every edge connects to the same vertex
Correct Answer: a) Every vertex is connected to every other vertex
Explanation: In a complete graph, each vertex is directly connected to every other vertex.
Question 11
What is the degree sequence of a graph?
a) A list of vertices in order of increasing degree
b) A list of edges in order of their lengths
c) A list of vertices in order of decreasing degree
d) A list of edges in order of their weights
Correct Answer: c) A list of vertices in order of decreasing degree
Explanation: The degree sequence is a list of the degrees of all vertices in non-increasing order.
Question 12
What is a bipartite graph?
a) A graph where vertices can be divided into two sets such that no edges exist within the same set
b) A graph where every vertex is connected to every other vertex
c) A graph that contains loops
d) A graph that contains parallel edges
Correct Answer: a) A graph where vertices can be divided into two sets such that no edges exist within the same set
Explanation: A bipartite graph divides vertices into two sets such that edges only exist between vertices from different sets.
Question 13
Which of the following is an example of a reflexive relation on set A?
a) (a,b)∈A, but (b,a)∉A
b) (a,a)∈A for all a∈A
c) (a,b)∈A for all a,b∈A
d) (a,b)∉A for all a,b∈A
Correct Answer: b) (a,a)∈A for all a∈A
Explanation: A relation is reflexive if every element is related to itself, meaning (a,a) is in the relation for all a.
Question 14
Which of the following is an example of a transitive relation?
a) If a is related to b and b is related to c, then a is related to c
b) If a is related to b, then b must be related to a
c) If a is related to b, then a is greater than b
d) If a is related to b, then a must be equal to b
Correct Answer: a) If a is related to b and b is related to c, then a is related to c
Explanation: A relation is transitive if whenever one element is related to a second, and the second is related to a third, the first is related to the third.
Question 15
What is the Hasse diagram used for?
a) To represent a partially ordered set
b) To represent a connected graph
c) To represent a matrix
d) To represent a cyclic graph
Correct Answer: a) To represent a partially ordered set
Explanation: A Hasse diagram is used to represent the structure of a partially ordered set, showing the relationships between elements.
Question 16
Which of the following is an example of a strict order?
a) a<b, but a≥b
b) a≤b, but a=b
c) a<b, and there are no self-loops
d) a≥b, and there are self-loops
Correct Answer: c) a<b, and there are no self-loops
Explanation: A strict order is a transitive, anti-reflexive relation where no element is related to itself.
Question 17
Which of the following describes an equivalence relation?
a) Reflexive, symmetric, and transitive
b) Antisymmetric and transitive
c) Reflexive and antisymmetric
d) Symmetric and transitive
Correct Answer: a) Reflexive, symmetric, and transitive
Explanation: An equivalence relation is one that is reflexive, symmetric, and transitive.
Question 18
Which of the following describes a strict partial order?
a) It is a relation that is antisymmetric and transitive
b) It is a relation that is reflexive and symmetric
c) It is a relation that is reflexive and antisymmetric
d) It is a relation that is symmetric and transitive
Correct Answer: a) It is a relation that is antisymmetric and transitive
Explanation: A strict partial order is a relation that is both antisymmetric and transitive, meaning no element is related to itself and the relation is preserved through transitivity.
Question 19
Which of the following is a characteristic of a directed acyclic graph (DAG)?
a) It contains no cycles
b) It contains exactly one cycle
c) It contains multiple cycles
d) It contains parallel edges
Correct Answer: a) It contains no cycles
Explanation: A directed acyclic graph (DAG) has no cycles, meaning it is impossible to return to a vertex by following edges in the graph.
Question 20
Which of the following is a property of a spanning tree?
a) It is a subgraph that contains all vertices and has no cycles
b) It is a subgraph that contains all vertices and has cycles
c) It is a subgraph that contains only some vertices and has no cycles
d) It is a subgraph that contains only some vertices and has cycles
Correct Answer: a) It is a subgraph that contains all vertices and has no cycles
Explanation: A spanning tree is a subgraph that includes all the vertices of the original graph and is acyclic.
