Discrete Mathematics

Other Virginia Mathematics sets

• Kindergarten
• Grade 1
• Grade 2
• Grade 3
• Grade 4
• Grade 5
• Grade 6
• Grade 7
• Grade 8
• Algebra 1
• Algebra 2
• Algebra, Functions, and Data Analysis
• Computer Mathematics
• Data Science
• Data Science
• Geometry
• Mathematical Analysis
• Probability and Statistics
• Trigonometry

Use Venn diagrams to codify and solve logic problems.DM.LR.1.a

Express logical statements in symbolic form. DM.LR.1.b

Represent a conditional statement as its converse, inverse, and contrapositive.DM.LR.1.c

Describe how symbolic logic can be used to map the processes of computer applications.DM.LR.1.d

Construct a truth table to display all possible input combinations and their outputs.DM.LR.1.e

Identify the rules of inference and model basic logical statements including De Morgan’s Law.DM.LR.1.f

Apply logical reasoning to model contextual situations and make decisions.DM.LR.1.g

Apply informal logical reasoning to contextual problems (e.g., predicting the behavior of software, solving puzzles).DM.LR.2.a

Outline the basic structure of a proof technique (e.g., direct proof, proof by contradiction, induction).DM.LR.2.b

Deduce the best type of proof for a given problem.DM.LR.2.c

Use the rules of inference to construct direct proofs and proofs by contradiction. DM.LR.2.d

 Construct induction proofs involving summations and inequalities.DM.LR.2.e

Use a truth table to prove the logical equivalence of statements.DM.LR.2.f

Explain basic properties of Boolean algebra: duality, complements, and standard forms. DM.LR.3.a

Represent verbal statements as Boolean expressions. DM.LR.3.b

Apply Boolean algebra to prove identities and simplify expressions.DM.LR.3.c

Generate truth tables that encode the truth and falsity of two or more statements.DM.LR.3.d

Explain the operation of discrete logic gates.DM.LR.3.e

Describe the relationship between Boolean algebra and electronic circuits.DM.LR.3.f

Analyze a combinational network using Boolean expressions. DM.LR.3.g

Design simple combinational networks that use NAND (AND followed by NOT), NOR (OR followed by NOT), and XOR (exclusive-OR) gates.DM.LR.3.h

Compare and contrast inductive and deductive reasoning.DM.LR.4.a

Explain the relationship between weak and strong induction.DM.LR.4.b

Construct induction proofs involving a divisibility argument.DM.LR.4.c

Prove the Binomial Theorem through mathematical induction.DM.LR.4.d

The student will identify and use the properties of sets and set operations. DM.SNT.1

The student will apply the formulas of combinatorics.DM.SNT.2

The student will use Pascal’s Triangle to analyze numerical patterns and relationships.DM.SNT.3

Compare and contrast sets, relations, and functions.DM.SNT.1.a

Express relationships between sets using Venn diagrams.DM.SNT.1.b

Describe a set using set-builder notation.DM.SNT.1.c

Construct new sets using the set operations intersection, union, difference, and complement.DM.SNT.1.d

Identify the laws of set theory (e.g., associative, commutative, distributive, De Morgan’s Law).DM.SNT.1.e

Use the principle of inclusion and exclusion to determine the size of a set.DM.SNT.1.f

Use the properties of set operations to prove set equality.DM.SNT.1.g

Create a tree diagram to represent relationships between independent events.DM.SNT.2.a

Use the Fundamental (Basic) Counting Principle to determine the number of possible outcomes of an event. DM.SNT.2.b

Determine the number of combinations possible when subsets of r elements are selected from a set of n elements without regard to order. DM.SNT.2.c

Determine the number of permutations possible when r objects selected from n objects are ordered. DM.SNT.2.d

Use the pigeonhole principle to solve packing problems to facilitate proofs.DM.SNT.2.e

Construct a proof by induction using principles of combinatorics.DM.SNT.2.f

Construct Pascal’s Triangle. DM.SNT.3.a

Expand binomials having positive integral exponents, using the Binomial Theorem and Pascal’s Triangle. DM.SNT.3.b

Compare the binomial coefficient to the calculation of combinations.DM.SNT.3.c

Identify the Fibonacci numbers within Pascal’s Triangle. DM.SNT.3.d

The student will represent problems using vertex-edge graphs. The concepts of degree, connectedness, paths, planarity, and directed graphs will be analyzed.DM.GT.1

The student will solve problems through analysis and application of circuits, cycles, Euler paths, Euler circuits, Hamilton paths, and Hamilton circuits. Optimal solutions will be determined using existing algorithms and student-created algorithms.DM.GT.2

The student will apply graphs to conflict-resolution problems, such as graph coloring, scheduling, matching, and optimization. DM.GT.3

The student will recognize and apply algorithms to solve configuration, conflict-resolution, and sorting problems.DM.GT.4

The student will use algorithms to schedule tasks to determine a minimum project time.DM.GT.5

Illustrate the basic terminology of graph theory (e.g., vertex, edge, graph, degree of a vertex).DM.GT.1.a

Use graphs to map situations in which the vertices represent objects, and edges represent a particular relationship between objects.DM.GT.1.b

Identify and describe degree and connectedness.DM.GT.1.c

Determine whether a graph is planar or nonplanar.DM.GT.1.d

Analyze the relationship between faces, edges, and vertices using Euler’s formula (F = E – V + 2).DM.GT.1.e

Use directed graphs (digraphs) to represent situations with restrictions in traversal possibilities.DM.GT.1.f

Determine when graphs are trees.DM.GT.1.g

Determine whether a graph has an Euler circuit or path, and determine the circuit or path, if it exists.DM.GT.2.a

Determine whether a graph has a Hamilton circuit or path, and determine the circuit or path, if it exists.DM.GT.2.b

Count the number of Hamilton circuits for a complete graph with n vertices.DM.GT.2.c

Use an Euler circuit algorithm to solve optimization problems.DM.GT.2.d

Model projects consisting of several subtasks, using a graph.DM.GT.3.a

Use graphs to resolve conflicts that arise in scheduling.DM.GT.3.b

Use graph coloring to determine the chromatic number of a graph. DM.GT.3.c

Recognize algorithms such as nearest neighbor, brute force, and cheapest link as they apply to graphs.DM.GT.4.a

Use Kruskal’s algorithm to determine the shortest spanning tree of a connected graph.DM.GT.4.b

Use Prim’s algorithm to determine the shortest spanning tree of a connected graph. DM.GT.4.c

Use Dijkstra’s algorithm to determine the shortest spanning tree of a connected graph.DM.GT.4.d

Specify in a digraph the order in which tests are to be performed.DM.GT.5.a

Identify the critical path to determine the earliest completion time (minimum project time).DM.GT.5.b

Use the list-processing algorithm to determine an optimal schedule.DM.GT.5.c

Create and test scheduling algorithms.DM.GT.5.d

The student will describe and apply sorting and searching algorithms used in processing and communicating information. DM.CM.1

The student will use recursive processes.DM.CM.2

The student will identify and apply cryptographic methods.DM.CM.3

The student will analyze the limitations of algorithms and their contextual relationships in computing. DM.CM.4

Select and apply a sorting algorithm, such as a bubble sort, merge sort, or network sort.DM.CM.1.a

Describe the advantages and disadvantages of various sorting algorithms.DM.CM.1.b

Analyze the knapsack and bin-packing problems.DM.CM.1.c

Select and apply search algorithms to analyze problems.DM.CM.1.d

Determine the average, best-case, and worst-case reasoning for different searches.DM.CM.1.e

Compare and contrast iterative and recursive processes.DM.CM.2.a

Use recursive processes to model growth and decay.DM.CM.2.b

Use recursive processes to create fractals.DM.CM.2.c

Use recursive processes to generate the Fibonacci sequence. DM.CM.2.d

Determine if a recursive solution is more efficient than an iterative solution.DM.CM.2.e

Compare and contrast ciphers and codes.DM.CM.3.a

Describe the evolution of cipher systems. DM.CM.3.b

Identify the Fundamental Theorem of Arithmetic.DM.CM.3.c

Describe how the complexity of prime factorization is used in cryptography.DM.CM.3.d

Describe modular arithmetic in context (e.g., clocks, days of the week, measures of time).DM.CM.3.e

Analyze the relationship between divisibility and modulus.DM.CM.3.f

Determine congruence within modular arithmetic.DM.CM.3.g

Perform operations within modular arithmetic.DM.CM.3.h

Apply modular arithmetic to problems in context (e.g., cryptography, International Standard Book Number (ISBN), International Bank Account Number (IBAN)).DM.CM.3.i

Describe maximum complexity of an algorithm using Big O notation.DM.CM.4.a

Describe Turing machines and how they are used to test the limits of computation. DM.CM.4.b

Describe the halting problem and explain how it characterizes the fundamental limitations of computation and undecidability.DM.CM.4.c

Explain the P versus NP problem and defend a justification for equality, inequality, or undecidability. DM.CM.4.d

Analyze how the equivalence of P- and NP-class problems might impact society. DM.CM.4.e