Math 151

Basic concepts of elementary logic: statements and statement forms, connectives, logical equivalence, truth tables; converse, inverse and contrapositive of a conditional statement. Tautologies and contradictions. Universal and existential statements. Methods of proof: direct proof, proof by cases, proof by contrapositive, proof by contradiction, first and second principles of mathematical induction. -Relations: general definitions, digraph and matrix of a relation; reflexive, symmetric, antisymmetric and transitive relations. Equivalence relations and partitions. Order relations and Hasse diagrams. Boolean algebras: general definitions, Boolean functions, complete sum of products form, complete product of sums form. Karnaugh maps, minimal sum of products form and minimal product of sums form. Gates and design of logic circuits. Graph theory: basic definitions and examples, paths, cycles, connected graphs, subgraphs. Regular, complete and bipartite graphs. Isomorphism of simple graphs. Trees, spanning trees, breadth-first search and depth-first search.