### General

### Discrete Mathematics

### Fall 2017-2018

*Discrete mathematics is no more about mathematics than astronomy is about telescopes. *

- General
### General

### Discrete Mathematics

### Fall 2017-2018

*Discrete mathematics is no more about mathematics than astronomy is about telescopes.* - Sets and Relations
### Sets and Relations

Sets: equality of sets, the empty set, subsets, the power set. Operations on sets: complement of a set, union, intersection, set difference and symmetric difference of the sets, proof by Venn diagram, Cartesian product of sets.

Relations: binary relation, properties of binary relations, higher-order relations, equivalence relations, equivalence classes, partition of a set, partial orders, posets, minimum, maximum, minimal and maximal elements, Hasse diagram.

- Functions
### Functions

Functions: domain and range of a function, the identity function, one-to-one, onto and one-to-one correspondence functions, some discrete and real variable examples, inverse function, composition of functions.

- Propositional Calculus and Boolean Algebra
### Propositional Calculus and Boolean Algebra

Propositional Calculus: atomic and compound propositions, well-formed propositions, theorem and contradiction, proof by truth table.

Boolean Algebra: basic boolean functions, digital logic gates, equivalence between logic circuits, minterm and maxterm expansions, simplified notation for the gates (accepter and rejecter), basic theorems of boolean algebra, simplifying boolean functions with Karnaugh maps.

- Induction and Recursion
### Induction and Recursion

Induction: the principle of mathematical induction (weak and strong forms).

Recursion: some special sequences (arithmetic and geometric sequences), 1st and 2nd order recurrence relations, solving homogeneous recurrence relations, the characteristic polynomial.

- Principles of Counting
### Principles of Counting

Principles of Counting: the principle of inclusion-exclusion, the addition and multiplication rules, the pigeonhole principle (weak and strong forms).

- Permutations and Combinations
### Permutations and Combinations

Permutations and Combinations: permutations and r-permutations, r-combinations, binomial coefficients, repetitions, derangements, the binomial theorem, Pascal's triangle.

- Graphs
### Graphs

Graphs: terminology and basic properties, degree of a vertex, subgraphs, pseudographs, connected graphs, bipartite graphs, complete and complete bipartite graphs, Euler's proposition on sum of the degrees, isomorphism, Eulerian pseudographs, the theorems on Eulerian circuits and Eulerian trails, Hamiltonian cycles, adjacency matrix.

- Trees
### Trees

Trees: trees and their properties, spanning trees, minimum spanning trees, Kruskal's algorithm, Prim's algorithm.

Skip NavigationSkip License## License

This work is licensed under a Creative Commons Attribution-NonCommercial 3.0 Unported License.