Create a 20 question college level discrete maths exam.
- User
Create a 20 question college level discrete maths exam.
Assistant
Here’s a 20-question college-level discrete mathematics exam covering a variety of topics, including logic, set theory, combinatorics, graph theory, and number theory. The questions range from basic to more challenging problems.
Discrete Mathematics Exam
Time: 90 minutes Total Points: 100
Section 1: Logic and Proofs (20 points)
- (5 pts) Let ( P ) and ( Q ) be propositions. Prove that ( (P \rightarrow Q) \equiv (\neg Q \rightarrow \neg P) ) using a truth table.
- (5 pts) Prove by contradiction: "If ( n^2 ) is odd, then ( n ) is odd."
- (5 pts) Use mathematical induction to prove that ( 1 + 3 + 5 + \dots + (2n-1) = n^2 ) for all positive integers ( n ).
- (5 pts) Determine whether the following statement is a tautology, contradiction, or contingency: [ (P \lor Q) \land (\neg P \lor \neg Q) ]
Section 2: Set Theory and Functions (20 points)
- (5 pts) Let ( A = {1, 2, 3} ) and ( B = {2, 4, 6} ). Compute ( A \times B ) and ( B \times A ).
- (5 pts) Prove or disprove: If ( A \subseteq B ) and ( B \subseteq C ), then ( A \subseteq C ).
- (5 pts) Let ( f: \mathbb{R} \rightarrow \mathbb{R} ) be defined by ( f(x) = x^2 + 1 ). Determine whether ( f ) is injective, surjective, or both.
- (5 pts) Let ( A = {1, 2, 3, 4} ). How many relations are there on ( A )?
Section 3: Combinatorics (20 points)
- (5 pts) How many ways can you arrange the letters in "DISCRETE"?
- (5 pts) A committee of 5 people is to be chosen from 8 men and 6 women. How many ways can this be done if the committee must have at least 3 women?
- (5 pts) Prove the identity using combinatorial reasoning: [ \binom{n}{k} = \binom{n}{n-k} ]
- (5 pts) Solve the recurrence relation: [ a_n = 2a_{n-1} + 3a_{n-2} ] with initial conditions ( a_0 = 1 ) and ( a_1 = 2 ).
Section 4: Graph Theory (20 points)
- (5 pts) Draw a graph with 5 vertices where each vertex has degree 2.
- (5 pts) Prove that in any graph, the sum of the degrees of all vertices is twice the number of edges.
- (5 pts) Determine whether the following graph is bipartite:
- Vertices: ( {A, B, C, D} )
- Edges: ( {AB, AC, AD, BC, BD} )
- (5 pts) Find the chromatic number of a complete graph ( K_4 ).
Section 5: Number Theory and Algorithms (20 points)
- (5 pts) Find the greatest common divisor (GCD) of 123 and 456 using the Euclidean algorithm.
- (5 pts) Prove that ( \sqrt{2} ) is irrational.
- (5 pts) Find the number of positive divisors of 1080.
- (5 pts) Use the Chinese Remainder Theorem to solve: [ x \equiv 2 \pmod{3} ] [ x \equiv 1 \pmod{5} ]
Grading Scheme:
- Each question is worth 5 points.
- Partial credit may be given for correct reasoning even if the final answer is incorrect.
- Show all work for full credit.
This exam tests a broad range of discrete mathematics concepts while ensuring a mix of computational and proof-based questions.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.