What is the truth value of the logical implication pq when p is true and q is false?
Correct answer:
B) False
Explanation: A logical implication pq is false only when p is true and q is false.
What is the truth value of the logical implication pq when p is true and q is false?
Correct answer:
B) False
Explanation: A logical implication pq is false only when p is true and q is false.
In which of the following situations is a biconditional statement pq true?
Correct answer:
B) When p and q are both true or both false
Explanation: A biconditional statement pq is true only when p and q have the same truth values.
Which of the following is always true in a tautology?
Correct answer:
A) The statement is true under all possible interpretations
Explanation: A tautology is a statement that is always true, regardless of the truth values of its components.
Which of the following describes a contradiction in logic?
Correct answer:
B) A statement that is always false
Explanation: A contradiction is a statement that is always false, regardless of the truth values of its components.
What is the empty set?
Correct answer:
B) A set containing no elements
Explanation: The empty set is defined as the set with no elements.
What is the power set of a set A containing 3 elements?
Correct answer:
D) A set containing 8 elements
Explanation: The power set of a set with n elements contains 2n subsets. For a set with 3 elements, the power set contains 23=8 subsets.
What is the Cartesian product of two sets A and B?
Correct answer:
B) The set of all ordered pairs (a,b) where aA and bB
Explanation: The Cartesian product AB is the set of all ordered pairs formed by taking elements from A and B.
Which of the following is a property of a reflexive relation?
Correct answer:
B) Every element in the set relates to itself
Explanation: A reflexive relation requires that every element in the set is related to itself.
Which of the following best describes an antisymmetric relation?
Correct answer:
B) If a is related to b and b is related to a, then a=b
Explanation: In an antisymmetric relation, if two elements relate to each other in both directions, they must be equal.
Which of the following defines a symmetric relation?
Correct answer:
A) If a is related to b, then b is also related to a
Explanation: A symmetric relation ensures that if one element is related to another, the second element is also related to the first.
Which of the following is an example of a transitive relation?
Correct answer:
A) If a is related to b and b is related to c, then a is related to c
Explanation: A transitive relation ensures that if an element relates to a second element, and the second element relates to a third, then the first element relates to the third.
Which of the following is a characteristic of an equivalence relation?
Correct answer:
A) Reflexive, symmetric, and transitive
Explanation: An equivalence relation must be reflexive, symmetric, and transitive.
Which of the following is an example of a directed graph?
Correct answer:
B) A graph with edges that have a direction
Explanation: In a directed graph, edges are associated with a direction from one vertex to another.
What is a complete graph?
Correct answer:
A) A graph where each vertex is connected to every other vertex
Explanation: A complete graph is one where every vertex is directly connected to every other vertex.
What is the degree of a vertex in a graph?
Correct answer:
A) The number of edges coming from it
Explanation: The degree of a vertex is the number of edges that are connected to it.
Which of the following represents a bipartite graph?
Correct answer:
A) A graph that can be divided into two groups, where no vertices in the same group are connected
Explanation: In a bipartite graph, the vertices can be split into two groups such that edges only connect vertices from different groups.
What is the significance of Euler's circuit in graph theory?
Correct answer:
A) It is a circuit that visits every edge exactly once
Explanation: An Euler circuit is a closed path in a graph that travels along each edge exactly once.
What is the Pigeonhole Principle?
Correct answer:
A) If n items are put into m containers and n>m, then at least one container must contain more than one item
Explanation: The Pigeonhole Principle states that when there are more items than containers, at least one container must hold more than one item.
Which of the following is true for a Boolean complement?
Correct answer:
B) The complement of 1 is 0
Explanation: In Boolean algebra, the complement of 1 is 0, and the complement of 0 is 1.
Which Boolean operation corresponds to the logical AND operation?
Correct answer:
B) Boolean multiplication
Explanation: Boolean multiplication corresponds to the logical AND operation, where the result is true only if both operands are true.
What is the Boolean exclusive OR (XOR) operation?
Correct answer:
B) False when both inputs are true
Explanation: The XOR operation is true when the inputs differ and false when the inputs are the same.
Which of the following best describes a conjunctive normal form (CNF)?
Correct answer:
A) The product of sums of literals
Explanation: In conjunctive normal form, a Boolean expression is represented as the product of sums of literals.
Which of the following is true for a tautology in Boolean algebra?
Correct answer:
A) The expression is always true
Explanation: A tautology in Boolean algebra is an expression that is always true, regardless of the values of the variables.
Which of the following is a method used to simplify Boolean expressions?
Correct answer:
B) De Morgan's Law
Explanation: De Morgan's Law is used to simplify Boolean expressions by transforming the negation of conjunctions and disjunctions.
Which of the following statements is true for Kruskal's algorithm?
Correct answer:
A) It finds a minimum spanning tree by adding increasing cost arcs
Explanation: Kruskal's algorithm is a greedy algorithm that finds the minimum spanning tree of a graph by adding edges in increasing order of cost.
What is the result of adding two Boolean variables using Boolean addition?
Correct answer:
C) The logical OR of the variables
Explanation: Boolean addition corresponds to the logical OR operation, where the result is true if at least one of the variables is true.
What is the purpose of an adjacency matrix in graph theory?
Correct answer:
B) To represent the edges between vertices in a graph
Explanation: An adjacency matrix is used to represent a graph by showing which pairs of vertices are connected by edges.
Which of the following describes a matrix product in terms of dot product?
Correct answer:
A) The dot product of row i from matrix A with column j from matrix B
Explanation: The matrix product is computed by taking the dot product of rows from one matrix and columns from another.
Which of the following is a characteristic of an injective function?
Correct answer:
C) Each element in the domain maps to a unique element in the codomain
Explanation: An injective function ensures that no two distinct elements in the domain map to the same element in the codomain.
Which of the following is a bijective function?
Correct answer:
B) A function that is injective and surjective
Explanation: A bijective function is both injective (one-to-one) and surjective (onto), meaning every element in the domain maps to a unique element in the codomain, and every element in the codomain is mapped.
Which of the following is true for a surjective function?
Correct answer:
B) Every element in the codomain has at least one preimage
Explanation: A surjective function ensures that every element in the codomain is the image of at least one element from the domain.
What is the range of a function?
Correct answer:
C) The set of all images of the elements in the domain
Explanation: The range of a function is the set of all images (outputs) of the elements in the domain.
Which of the following describes the Principle of Mathematical Induction?
Correct answer:
A) If a statement is true for a base case and holds for n+1 when it holds for n, then it is true for all n
Explanation: The Principle of Mathematical Induction is used to prove statements for all natural numbers by showing that the base case holds and that the statement holds for n+1 when it holds for nnn.
Which of the following best describes the principle of strong mathematical induction?
Correct answer:
B) The statement must be true for the base case and hold for all k before proving it for k+1
Explanation: Strong mathematical induction requires proving the statement for the base case and showing that if it holds for all values up to k, it also holds for k+1.
Which of the following is true for an r-permutation of a set?
Correct answer:
B) It is an ordered arrangement of r elements from the set
Explanation: An r-permutation is an ordered arrangement of r elements chosen from a set.
What is the difference between a permutation and a combination?
Correct answer:
A) A permutation involves order, while a combination does not
Explanation: A permutation considers the order of elements, while a combination does not.
What does the inclusion-exclusion principle calculate?
Correct answer:
A) The number of elements in the union of two or more sets
Explanation: The inclusion-exclusion principle is used to calculate the size of the union of two or more sets, accounting for any overlap.
Which of the following statements is true for a binary relation on set A?
Correct answer:
D) It relates elements of set A to elements of set A
Explanation: A binary relation on set A is a subset of AA, meaning it relates elements of set A to other elements in the same set.
Which of the following describes a reflexive relation?
Correct answer:
B) Every element in the set is related to itself
Explanation: A reflexive relation means that each element in the set is related to itself.
Which of the following describes a symmetric relation?
Correct answer:
A) If a is related to b, then b must also be related to a
Explanation: A symmetric relation ensures that if an element is related to another, the second element must also be related to the first.
Which of the following is true for a transitive relation?
Correct answer:
A) If a is related to b and b is related to c, then a must be related to c
Explanation: A transitive relation means that if one element is related to a second element, and the second element is related to a third, then the first element is also related to the third.
What is a strict order?
Correct answer:
A) A relation that is transitive and anti-reflexive
Explanation: A strict order is a relation that is both transitive and anti-reflexive, meaning no element is related to itself.
What is a directed acyclic graph (DAG)?
Correct answer:
A) A directed graph with no positive length cycles
Explanation: A directed acyclic graph (DAG) is a directed graph that contains no cycles of positive length.
What is the truth value of the conjunction p AND q when p is true and q is false?
Correct answer:
B) False
Explanation: A conjunction is true only when both statements are true. Since q is false, p AND q is false.
A conditional statement p -> q is false only when:
Correct answer:
A) p is true and q is false
Explanation: An implication is false only when the hypothesis is true and the conclusion is false. In every other case it is true.
What is the negation of the statement "All students passed the exam"?
Correct answer:
C) At least one student did not pass the exam
Explanation: The negation of "for all x, P(x)" is "there exists an x such that not P(x)", so at least one student did not pass.
By De Morgan's law, NOT (p OR q) is equivalent to:
Correct answer:
D) NOT p AND NOT q
Explanation: De Morgan's laws: NOT (p OR q) = NOT p AND NOT q, and NOT (p AND q) = NOT p OR NOT q.
A compound statement that is always true, regardless of the truth values of its components, is called a:
Correct answer:
B) Tautology
Explanation: A tautology, such as p OR NOT p, is true in every row of its truth table. A contradiction is always false.
The converse of the conditional "If p, then q" is:
Correct answer:
A) If q, then p
Explanation: The converse swaps hypothesis and conclusion. Unlike the contrapositive, it is not logically equivalent to the original.
How many rows does a truth table need for a statement with three variables?
Correct answer:
C) 8
Explanation: Each variable can be true or false, so n variables need 2^n rows. With three variables, 2^3 = 8.
If this exam is giving you a hard time, let us be your helping hand. Contact us, and we'll provide the assistance you need to pass and move forward.