Course Catalog

Description

The course is designed to introduce students to the fundamental concepts of discrete mathematics. The discrete part is related to the validation of computer programs and major applications in computer science. It starts with the motivation of discrete mathematics and introduces the student to propositional logic and discusses the logical value of an expression. Using propositional logic a formal proof method is constructed. These can be used to determine the validity of an statement given in English or to proof that an algorithm in computer science is correct. The next step is to introduce formal symbols and predict their logic value. Predicate logic is used to determine the truth table of several mathematical expressions as well as expressions of our used language. Predicate logic is also used to check the correctness of programs that use assignment and conditional statements. A major point in this proof technique part is to discuss the different types of proofs like direct, contraposition, contradiction and induction proofs. After completing the proof’s section sets and set operations are introduced. The previous proof techniques are used to show that certain set identities are correct and useful in computer science applications. The reflexive, symmetric, transitive, and antisymmetric properties of binary relations are discussed and consequences are derived from the proofs for mappings and functions and their graphs. The terminology of graphs, direct graphs and trees is introduced to describe simple, connected planar graphs by Euler’s formula and prove elementary properties of them. Different algorithms like Dijkstra’s and Prim’s are applied to to simple connected graphs.