Discrete Mathematics Lecture Note

Discrete Mathematics Course Description: Fundamentals of logic (the laws of logic, rules of inferences, quantifiers, proofs of theorems), Fundamental principles of counting (permutations, combinations), set theory, relations and functions, graphs, trees and sorting, shortest path and minimal spanning trees algorithms. Monoids and Groups. Course Objectives   Provide a survey of Discrete Mathematics, the study of finite systems, needed in computer science. Further develop the mathematical concepts and technique which should serve as a preparation for more advanced quantitative courses. Prerequisites   High school algebra One introductory computer science course (recommended). Grading    Midterm 35% Final 35% Assignments: 30% Textbook   Recommended not Required - "Mathematical Structure for Computer Science", Judith L. Gersting, W. H. Freeman & Company. (Any edition). Any old or new discrete math textbook will do the job. Courseware: More course materials for this class and information about the instructor can be found at: people.bu.edu/madani. Class Policies 1) Attendance & Absences – Students are expected to attend and sit through the entire class meetings. In case of an absence, the student is responsible to arrange for notes and missed announcements. Three (3) or more absences may result in a withdrawal from the class. 2) Assignment Completion & Late Work – Late assignment submission is not allowed, unless a permission is granted by the instructor prior to the deadline. Students should submit a physical to the instructor by the due date. If the student is to be absent that day, completed assignments should be submitted via email before class begins. 3) Academic Conduct Code – Cheating and plagiarism will not be tolerated in any Metropolitan College course. They will result in no credit for the assignment or examination and may lead to disciplinary actions. Please take the time to review the Student Academic Conduct Code: NOTE: [This should not be understood as a discouragement for discussing the material or your particular approach to a problem with other students in the class. On the contrary – you should share your thoughts, questions and solutions. Naturally, if you choose to work in a group, you will be expected to come up with more than one and highly original solutions rather than the same mistakes.] Course outline TOPIC Logic Sets DESCRIPTION I.Statements and logical connectives; truth tables. II.Predicates logic and Quantifiers III.Proof techniques, the nature of mathematical theorems and proofs; direct proof, proof by contraposition, by contradiction; use of counterexamples; the principle of mathematical induction I.The notation of set theory - Subsets and the power set; binary and unary operations on a set; set operations of union, intersection, complementation, difference, and Cartesian product II. Demonstration of the denumerability of some sets and the use of Cantor diagonalization method to prove the uncountability; partition of a set Relations & Functions Combinatorics I.Binary relations as ordered pairs and verbal description; the reflexive, symmetric, transitive and antisymmetric properties of binary relations; the definition and terminology about partial orderings; graphs of partially ordered finite sets; the definition of equivalence relation and equivalence class II. Functions; definition and examples; properties of functions one-t-one, onto, bijective; function composition, inverse function I.Counting; fundamental counting principles, including the multiplication and addition principles II.Sampling and selecting III.Permutations and combinations; formulas for counting the number of permutations and combinations of k-objects from n distinct objects Midterm Examination Graphs Boolean Algebra & Computer Logic Algebraic Structures I.Graph terminology; undirected graphs, simple, complete, path, cycle, adjacency matrix, connectivity; Euler’s path and Hamiltonian circuit; graph representation, trees II.Digraphs and connectivity problems - Reachability matrix analysis; Warshall’s algorithm I.Discussion and Definition; similarities between propositional logic and set theory; mathematical structures as models or abstractions incorporating common properties found in different contexts II.Logic circuits; basic logic elements of AND gate, OR gate and inverter; representation of a Boolean expression as a combinational network and vice versa; procedure to find a canonical sum-of-product Boolean expressions using Karnaugh map or Boolean algebra properties I.Definition of binary operation and structure; discussion of the associative, commutative, identity and inverse properties; definition of semigroup, monoid, and a substructure II.Group structure; elementary group theorems, uniqueness of identity and inverse; cancellation laws; definition and properties of a subgroup; application to error correcting codes Finite State Machines I.Definition of FSM; state tables and state graphs II.FSM as transducers and recognizers III.Discussion of limitations of FSMs; introduction to formal languages Final Examination