|
Logical Reasoning
| |||||||||||||
|
The validity of a statement or argument can be determined using the models and language of first order logic.
| |||||||||||||
|
1. Represent logic statements in words, with symbols, and in truth tables, including conditional, biconditional, converse, inverse, contrapositive, and quantified statements. |
||||||||||||
|
2. Represent logic operations such as and, or, not, nor, and x or (exclusive or) in words, with symbols, and in truth tables.
|
||||||||||||
|
3. Use truth tables to solve application-based logic problems and determine the truth value of simple and compound statements including negations and implications.
a. Determine whether statements are equivalent and construct equivalent statements.
Example: Show that the contrapositive of a statement is its logical equivalent.
|
||||||||||||
|
4. Determine whether a logical argument is valid or invalid, using laws of logic such as the law of syllogism and the law of detachment. a. Determine whether a logical argument is a tautology or a contradiction. |
||||||||||||
|
5. Prove a statement indirectly by proving the contrapositive of the statement. |
||||||||||||
|
Advanced Counting
| |||||||||||||
|
Complex counting problems can be solved efficiently using a variety of techniques.
| |||||||||||||
|
6. Use multiple representations and methods for counting objects and developing more efficient counting techniques.
Note: Representations and methods may include tree diagrams, lists, manipulatives, overcounting methods, recursive patterns, and explicit formulas. |
||||||||||||
|
7. Develop and use the Fundamental Counting Principle for counting independent and dependent events.
a. Use various counting models (including tree diagrams and lists) to identify the distinguishing factors of a context in which the Fundamental Counting Principle can be applied.
Example: Apply the Fundamental Counting Principle in a context that can be represented by a tree diagram in which there are the same number of branches from each node at each level of the tree.
|
||||||||||||
|
8. Using application-based problems, develop formulas for permutations, combinations, and combinations with repetition and compare student-derived formulas to standard representations of the formulas.
Example: If there are r objects chosen from n objects, then the number of permutations can be found by the product [n(n-1) ... (n-r)(n-r+1)] as compared to the standard formula n!/(n-r)!
a. Identify differences between applications of combinations and permutations.
b. Using application-based problems, calculate the number of permutations of a set with n elements. Calculate the number of permutations of r elements taken from a set of n elements.
c. Using application-based problems, calculate the number of subsets of size r that can be chosen from a set of n elements, explaining this number as the number of combinations "n choose r."
d. Using application-based problems, calculate the number of combinations with repetitions of r elements from a set of n elements as "(n + r - 1) choose r."
|
||||||||||||
|
9. Use various counting techniques to determine probabilities of events. |
||||||||||||
|
10. Use the Pigeonhole Principle to solve counting problems. |
||||||||||||
|
Recursion
| |||||||||||||
|
Recursion is a method of problem solving where a given relation or routine operation is repeatedly applied.
| |||||||||||||
|
11. Find patterns in application problems involving series and sequences, and develop recursive and explicit formulas as models to understand and describe sequential change.
Examples: fractals, population growth
|
||||||||||||
|
12. Determine characteristics of sequences, including the Fibonacci Sequence, the triangular numbers, and pentagonal numbers.
Example: Write a sequence of the first 10 triangular numbers and hypothesize a formula to find the nth triangular number.
|
||||||||||||
|
13. Use the recursive process and difference equations to create fractals, population growth models, sequences, and series. |
||||||||||||
|
14. Use mathematical induction to prove statements involving the positive integers.
Examples: Prove that 3 divides 22n - 1 for all positive integers n; prove that 1 + 2 + 3 + ... + n = n(n + 1)/2; prove that a given recursive sequence has a closed form expression.
|
||||||||||||
|
15. Develop and apply connections between Pascal's Triangle and combinations. |
||||||||||||
|
Networks
| |||||||||||||
|
Complex problems can be modeled using vertex and edge graphs and characteristics of the different structures are used to find solutions.
| |||||||||||||
|
16. Use vertex and edge graphs to model mathematical situations involving networks. a. Identify properties of simple graphs, complete graphs, bipartite graphs, complete bipartite graphs, and trees. |
||||||||||||
|
17. Solve problems involving networks through investigation and application of existence and nonexistence of Euler paths, Euler circuits, Hamilton paths, and Hamilton circuits. Note: Real-world contexts modeled by graphs may include roads or communication networks.
Example: show why a 5x5 grid has no Hamilton circuit.
a. Develop optimal solutions of application-based problems using existing and student-created algorithms.
b. Give an argument for graph properties.
Example: Explain why a graph has a Euler cycle if and only if the graph is connected and every vertex has even degree. Show that any tree with n vertices has n - 1 edges. |
||||||||||||
|
18. Apply algorithms relating to minimum weight spanning trees, networks, flows, and Steiner trees.
Example: traveling salesman problem
a. Use shortest path techniques to find optimal shipping routes.
b. Show that every connected graph has a minimal spanning tree.
c. Use Kruskal's Algorithm and Prim's Algorithm to determine the minimal spanning tree of a weighted graph.
|
||||||||||||
|
19. Use vertex-coloring, edge-coloring, and matching techniques to solve application-based problems involving conflict.
Examples: Use graph-coloring techniques to color a map of the western states of the United States so that no adjacent states are the same color, determining the minimum number of colors needed and why no fewer colors may be used; use vertex colorings to determine the minimum number of zoo enclosures needed to house ten animals given their cohabitation constraints; use vertex colorings to develop a time table for scenarios such as scheduling club meetings or for housing hazardous chemicals that cannot all be safely stored together in warehouses. |
||||||||||||
|
20. Determine the minimum time to complete a project using algorithms to schedule tasks in order, including critical path analysis, the list-processing algorithm, and student-created algorithms. |
||||||||||||
|
21. Use the adjacency matrix of a graph to determine the number of walks of length n in a graph.
|
||||||||||||
|
Fairness and Democracy
| |||||||||||||
|
Various methods for determining a winner in a voting system can result in paradoxes or other issues of fairness.
| |||||||||||||
|
22. Analyze advantages and disadvantages of different types of ballot voting systems.
a. Identify impacts of using a preferential ballot voting system and compare it to single candidate voting and other voting systems.
b. Analyze the impact of legal and cultural features of political systems on the mathematical aspects of elections. Examples: mathematical disadvantages of third parties, the cost of run-off elections |
||||||||||||
|
23. Apply a variety of methods for determining a winner using a preferential ballot voting system, including plurality, majority, run-off with majority, sequential run-off with majority, Borda count, pairwise comparison, Condorcet, and approval voting. |
||||||||||||
|
24. Identify issues of fairness for different methods of determining a winner using a preferential voting ballot and other voting systems and identify paradoxes that can result.
Example: Arrow's Theorem
|
||||||||||||
|
25. Use methods of weighted voting and identify issues of fairness related to weighted voting.
Example: determine the power of voting bodies using the Banzhaf power index a. Distinguish between weight and power in voting.
|
||||||||||||
|
Fair Division
| |||||||||||||
|
Methods used to solve non-trivial problems of division of objects often reveal issues of fairness.
| |||||||||||||
|
26. Explain and apply mathematical aspects of fair division, with respect to classic problems of apportionment, cake cutting, and estate division. Include applications in other contexts and modern situations. |
||||||||||||
|
27. Identify and apply historic methods of apportionment for voting districts including Hamilton, Jefferson, Adams, Webster, and Huntington-Hill. Identify issues of fairness and paradoxes that may result from methods.
Examples: the Alabama paradox, population paradox
|
||||||||||||
|
28. Use spreadsheets to examine apportionment methods in large problems.
Example: apportion the 435 seats in the U.S. House of Representatives using historically applied methods
|
||||||||||||
|
Information Processing
| |||||||||||||
|
Effective systems for sending and receiving information include components that impact accuracy, efficiency, and security.
| |||||||||||||
|
29. Critically analyze issues related to information processing including accuracy, efficiency, and security. |
||||||||||||
|
30. Apply ciphers (encryption and decryption algorithms) and cryptosystems for encrypting and decrypting including symmetric-key or public-key systems.
a. Use modular arithmetic to apply RSA (Rivest-Shamir-Adleman) public-key cryptosystems.
b. Use matrices and their inverses to encode and decode messages.
|
||||||||||||
|
31. Apply error-detecting codes and error-correcting codes to determine accuracy of information processing. |
||||||||||||
|
32. Apply methods of data compression.
Example: Huffman codes |
||||||||||||