Discrete Mathematics (Virginia SOL)

Logical Reasoning (LR)

• DM.LR.1 Use reasoning to build and apply logical arguments.
• Use Venn diagrams to organize and solve logic problems.
• Write logical statements in symbolic form.
• Write the converse, inverse and contrapositive of a conditional.
• Explain how symbolic logic models what computers do.
• Build a truth table showing all inputs and outputs.
• Identify rules of inference and model basic statements, including De Morgan's laws.
• Use logic to model real situations and support decisions.
• DM.LR.2 Apply logic and methods of proof to build valid arguments.
• Use informal reasoning on everyday problems such as software behavior or puzzles.
• Outline how direct proof, proof by contradiction and proof by induction are structured.
• Choose the most suitable kind of proof for a problem.
• Use rules of inference to write direct proofs and proofs by contradiction.
• Write induction proofs about sums and inequalities.
• Use truth tables to show that statements are logically equivalent.
• DM.LR.3 Use Boolean algebra to represent and analyze logic gates and circuits.
• Explain Boolean properties such as duality, complements and standard forms.
• Turn verbal statements into Boolean expressions.
• Use Boolean algebra to prove identities and simplify expressions.
• Build truth tables for two or more statements.
• Explain how discrete logic gates work.
• Describe how Boolean algebra connects to electronic circuits.
• Analyze combinational networks with Boolean expressions.
• Design simple networks with NAND, NOR and XOR gates.
• DM.LR.4 Use mathematical induction to prove formulas and statements.
• Compare inductive and deductive reasoning.
• Explain how weak and strong induction relate.
• Write induction proofs about divisibility.
• Prove the Binomial Theorem by induction.

Set and Number Theory (SNT)

• DM.SNT.1 Identify and use properties of sets and set operations.
• Compare sets, relations and functions.
• Show how sets relate with Venn diagrams.
• Describe sets in set-builder notation.
• Form new sets by intersection, union, difference and complement.
• Identify set laws such as associative, commutative, distributive and De Morgan's laws.
• Use inclusion-exclusion to find the size of a set.
• Prove two sets are equal using properties of set operations.
• DM.SNT.2 Apply counting (combinatorics) formulas.
• Draw tree diagrams for independent events.
• Use the Fundamental Counting Principle to count outcomes.
• Count combinations of r items from n when order does not matter.
• Count permutations of r items from n when order matters.
• Use the pigeonhole principle for packing problems and in proofs.
• Write induction proofs that use counting principles.
• DM.SNT.3 Use Pascal's triangle to analyze number patterns.
• Build Pascal's triangle.
• Expand binomials with positive whole-number exponents.
• Compare binomial coefficients with combinations.
• Find Fibonacci numbers in Pascal's triangle.

Graph Theory (GT)

• DM.GT.1 Model problems with vertex-edge graphs and analyze their properties.
• Explain basic graph terms such as vertex, edge and degree.
• Model situations with vertices as objects and edges as relationships.
• Identify and describe degree and connectedness.
• Decide whether a graph is planar.
• Relate faces, edges and vertices with Euler's formula.
• Use directed graphs to show one-way restrictions.
• Decide whether a graph is a tree.
• DM.GT.2 Solve problems with circuits, cycles and Euler and Hamilton paths and circuits.
• Decide whether an Euler path or circuit exists and find it.
• Decide whether a Hamilton path or circuit exists and find it.
• Count Hamilton circuits in a complete graph with n vertices.
• Use an Euler circuit algorithm to solve optimization problems.
• DM.GT.3 Use graphs to solve conflict problems.
• Model a project with several subtasks as a graph.
• Use graphs to resolve scheduling conflicts.
• Use graph coloring to find the chromatic number.
• DM.GT.4 Recognize and use algorithms for networks, conflict resolution and sorting.
• Recognize nearest-neighbor, brute-force and cheapest-link algorithms on graphs.
• Use Kruskal's algorithm to find a minimum spanning tree.
• Use Prim's algorithm to find a minimum spanning tree.
• Use Dijkstra's algorithm to find shortest routes.
• DM.GT.5 Use algorithms to schedule tasks and keep project time to a minimum.
• Show the order of tasks in a directed graph.
• Find the critical path and the earliest finish time.
• Use a list-processing algorithm to find an optimal schedule.
• Create and test scheduling algorithms.

Computational Methods (CM)

• DM.CM.1 Apply sorting and searching algorithms used to process information.
• Choose and apply a sorting algorithm such as bubble, merge or network sort.
• Compare the pros and cons of sorting algorithms.
• Analyze knapsack and bin-packing problems.
• Choose and apply search algorithms to analyze problems.
• Find average, best-case and worst-case performance of searches.
• DM.CM.2 Use recursive processes.
• Compare iterative and recursive processes.
• Use recursion to model growth and decay.
• Use recursion to make fractals.
• Use recursion to generate the Fibonacci sequence.
• Decide whether a recursive solution is more efficient than an iterative one.
• DM.CM.3 Identify and apply methods of cryptography.
• Compare ciphers and codes.
• Describe how cipher systems have developed.
• Identify the Fundamental Theorem of Arithmetic.
• Explain how hard prime factorization is and why that matters for cryptography.
• Describe modular arithmetic in contexts such as clocks and calendars.
• Analyze how divisibility and modulus relate.
• Decide whether numbers are congruent in modular arithmetic.
• Carry out operations in modular arithmetic.
• Apply modular arithmetic to cryptography and to check digits such as ISBN and IBAN.
• DM.CM.4 Analyze the limits of algorithms and computing.
• Describe the worst-case complexity of an algorithm with Big O notation.
• Describe Turing machines and how they test the limits of computing.
• Describe the halting problem and its link to undecidability.
• Explain the P versus NP problem and argue a position on it.
• Analyze how P versus NP could affect society.