WorksheetsDiscrete Structures' Long Test
Total questions: 70
Worksheet time: 35mins
Which expression is logically equivalent to ¬((p → q) ∧ (q → ¬r))?
p ∧ (¬q ∨ r)
p ∧ (q ∧ r)
¬p ∨ (q ∧ ¬r)
¬p ∨ (¬q ∨ r)
Which inference rule best justifies the derivation of r from: p → (q ∧ r), q → r
Hypothetical Syllogism then Simplification
Conjunction Introduction then Modus Ponens
Modus Ponens then Conjunction Elimination
Resolution then Simplification
What is the negation of the statement: ¬(∀x ∃y (P(x,y) → Q(y)))
∃x ∀y (P(x,y) ∧ ¬Q(y))
∀x ∀y (P(x,y) ∧ ¬Q(y))
∃x ∃y (P(x,y) ∧ ¬Q(y))
∃x ∀y (P(x,y) → ¬Q(y))
A proof technique where one assumes the opposite of a conclusion within a conditional proof structure and derives inconsistency is called:
Direct proof
Proof by contradiction
Mathematical induction
Proof by construction
5. A sequence of statements where each follows from previous steps using formally accepted rules.
Proof
Hypothesis
Assumption
Experiment
If A = {x ∈ Z | x < 4}, B = {x ∈ Z | x ≡ 1 (mod 3)}, then A ∩ B is:
{…, -5, -2, 1}
{…, -8, -5, -2}
{-2, 1, 4}
{1, 4, 7}
A function f: A → B is injective if and only if:
Distinct elements in A always map to distinct elements in B
Every element in B corresponds to exactly one element in A
No element in A maps to more than one element in B
Every element in B is an image of some element in A
What is the 10th term of the sequence defined by aₙ = 4n − (−1)ⁿ?
39
41
43
45
A set whose cardinality exceeds that of any countably infinite set is called:
Finite set
Countable set
Uncountable set
Empty set
A function whose values repeat after a constant integer interval is called:
Periodic function
Linear function
Constant function
Exponential function
What is the 2’s complement of (01101001)_2?
10010111
10010110
01101010
01101000
Convert (7A3)_16 to decimal.
1955
1953
1987
1971
The binary value corresponding to (3F)_16 is:
0011 1100
0011 1111
0010 1111
0010 1100
Which Boolean expression simplifies to A + B'C?
(A + B')(A + C)
(A + C')(A + BC)
A(BC)' + BC
(A + B)(A + C')
The base-16 number system using symbols 0–9 and A–F is called ________.
Hexadecimal
Octal
Binary
Decimal
Method of subtraction performed via adding a complement is called ________.
Complement subtraction
Direct subtraction
Binary addition
Decimal subtraction
Which law justifies: AB + A'B + AC = B + AC?
Dual Absorption
Consensus Theorem
Distributive Law
Idempotent Law
Which gate outputs TRUE only when inputs differ?
XNOR
XOR
NAND
NOR
Binary operation corresponding to logical OR.
OR
AND
XOR
NAND
Boolean law stating (AB)' = A' + B'
De Morgan’s Law
Associative Law
Distributive Law
Absorption Law
In a 4-variable K-map, a group of 8 cells eliminates how many variables from the simplified term?
1 variable
2 variables
3 variables
All variables involved
In a K-map, two cells are considered adjacent only if:
They differ in exactly one variable and share boundary wrapping
They differ in two variables but remain in the same Gray code row
They lie on diagonally opposite corners of a block
They share at least one identical minterm index
A don’t-care condition contributes to simplification when:
It forms a group only if placed on an edge of the map
It completes a larger group that would otherwise be impossible
It replaces a minterm containing a contradiction
It forces removal of redundant prime implicants
Which of the following is always TRUE about prime implicants?
They must contain at least four grouped minterms
They cannot be further expanded without including a 0-cell
They appear only in minimal SOP form
They are always essential to the final simplified expression
The final simplified expression in a K-map is obtained after selecting:
All possible prime implicants
Only implicants containing don’t-cares
All essential prime implicants plus minimum additional ones
Every group that appears more than once
The process of combining minterms into maximal power-of-two blocks to eliminate variables.
K-map grouping / looping
Boolean addition
DeMorgan's Theorem
Truth table expansion
A group of four adjacent minterms forming a simplification block.
Quad
Pair
Octet
Single
A minterm covered by exactly one prime implicant.
Singleton
Essential Prime Implicant
Redundant Minterm
Multiple Coverage
A condition where unspecified outputs may be treated as 0 or 1.
Don’t-care condition
Race condition
Hazard condition
Stable condition
The minimal SOP expression obtained after selecting essential prime implicants.
Minimal Boolean expression
Canonical SOP expression
Maximal Boolean expression
Non-essential SOP expression
Number of distinct permutations of the word “STATISTICS”. (Letters: S×3, T×3, I×2, A×1, C×1 → 10!/(3!3!2!))
25,200
50,400
168,000
504,000
A 5-digit code uses digits 0–9 but cannot begin with 0 and cannot repeat digits. How many codes?
10 × 9 × 8 × 7 × 6
9 × 9 × 8 × 7 × 6
9 × 9 × 8 × 7 × 5
9 × 8 × 7 × 6 × 5
How many functions f: A → B exist if |A| = 5 and |B| = 3?
3⁵
5³
5!
3! × 5!
A committee of 5 is formed from 12 people, but two specific people refuse to serve together. Number of possible committees:
C(12,5) – C(10,3)
C(12,5) – C(11,4)
C(10,5) – C(11,3)
C(12,5) – 2·C(10,3)
How many arrangements of 7 people are possible if three specific people must sit consecutively as a block?
6! × 3!
5! × 3!
7! / 3!
7! – 3!
A method of counting where order matters and repetition is permitted.
Permutation with repetition
Combination without repetition
Permutation without repetition
Combination with repetition
A method of selecting r objects from n when order does not matter.
Combination
Permutation
Arrangement
Selection with replacement
The rule where total outcomes of mutually exclusive events are added.
Addition rule
Multiplication rule
Subtraction rule
Division rule
The rule used when multiple independent actions are multiplied.
Multiplication rule
Addition rule
Subtraction rule
Division rule
Principle stating that if n+1 objects are placed into n boxes, one box has at least two.
Pigeonhole principle
Inclusion-Exclusion principle
Binomial theorem
Law of Large Numbers
If P(A)=0.4, P(B)=0.6, P(A∪B)=0.82, find P(A|B).
0.20
0.37
0.30
0.47
A card is drawn. Probability it is red or a face card?
7/13
9/26
11/26
10/13
Two dice are rolled. Probability the sum is composite?
19/36
23/36
25/36
29/36
If events A and B are independent, which is TRUE?
P(A|B)=P(B|A)
P(A∩B)=P(A)P(B)
P(A∪B)=P(A)+P(B)
P(A∩B)=P(A)+P(B)−1
If P(A') = 0.58, what is P(A)?
0.42
0.58
0.72
0.27
Identification: The complete set of all possible outcomes.
Sample space
Event
Probability
Random variable
Identification: Events that cannot occur together. (Write the term that matches the definition.)
Mutually exclusive
Independent events
Complementary events
Exhaustive events
Identification: Events that do not influence each other's likelihood. (Write the term that matches the definition.)
Independent events
Mutually exclusive events
Dependent events
Complementary events
Identification: Probability obtained from repeated trials.
Empirical probability
Theoretical probability
Subjective probability
Classical probability
Identification: Probability of 'not A'. (Write the term that matches the definition.)
Complement
Intersection
Union
Sample Space
A relation that is reflexive and symmetric but may fail transitivity is known as:
Preorder
Tolerance relation
Equivalence relation
Partial order
Relation R on A is antisymmetric if:
aRb always implies a=b
aRb and bRa imply a=b
In the matrix of a symmetric relation on a set of size n:
Main diagonal must be all 1s
Matrix must equal its transpose
Only upper triangular part can contain 1s
Diagonal entries alternate depending on parity
A partial order must satisfy:
Reflexive, symmetric, transitive
Reflexive, antisymmetric, transitive
Irreflexive, symmetric, transitive
Symmetric, antisymmetric, transitive
For a set A with 6 elements, number of ordered pairs in A×A is:
18
30
36
42
Identification: A relation where aRb and bRa imply a=b.
Antisymmetric
Symmetric
Transitive
Reflexive
Identification: A relation that partitions a set into equivalence classes.
Equivalence relation
Transitive relation
Symmetric relation
Reflexive relation
Identification: A table of 0s and 1s representing a relation.
Matrix representation
Graph representation
Set notation
List representation
Identification: A relation containing only (a,a) for all a in A.
Identity relation
Symmetric relation
Transitive relation
Reflexive relation
Identification: The Cartesian product of A with itself.
A × A
A + A
A ∪ A
A ∩ A
What is the probability of drawing a heart from a standard deck of cards?
1/52
1/13
1/4
1/2
Which of the following is a property of a normal distribution?
Mean, median, and mode are equal
Skewed to the right
Only positive values
Uniform distribution
In a binary tree, how many edges are there if there are n nodes?
n-1
n
2n
n+1
The principle that states the probability of the union of two events is the sum of their probabilities minus the probability of their intersection.
Addition rule
Multiplication rule
Inclusion-Exclusion principle
Conditional probability
In a 3-variable K-map, how many cells are needed to cover all possible minterms?
32
4
8
16
Which of the following represents the probability of event A occurring given that event B has occurred?
P(A|B)
P(B)
P(B|A)
P(A)
Which of the following is a valid expression for the negation of (p ∧ q)?
p ∨ q
¬p ∨ ¬q
p ∧ ¬q
¬(p ∨ q)
Identification: The probability of the occurrence of at least one of two events. (Write the term that matches the definition.)
Union
Intersection
Complement
Conditional probability
If P(A)=0.5, P(B)=0.4, and P(A ∩ B)=0.2, find P(A|B).
0.40
0.80
0.50
0.20
Which of the following is a necessary condition for two events A and B to be dependent?
P(A ∪ B) = P(A) + P(B)
P(A|B) ≠ P(A)
P(A ∩ B) = P(A)P(B)
P(A|B) = P(A)
