Discrete Mathematics

Course Information

College	Akashi College	Year	2021
Course Title	Discrete Mathematics
Course Code	0028	Course Category	Specialized / Elective
Class Format	Lecture	Credits	School Credit: 2
Department	Electrical and Computer Engineering Electrical Engineering Course	Student Grade	4th
Term	Year-round	Classes per Week	2
Textbook and/or Teaching Materials
Instructor	HAMADA Yukihiro

Course Objectives

[1] Can explain what counting is.
[2] Develop self-directed and continuous learning skills by mastering the arguments used in a mathematical proof.
[3] Can think in a recursive manner.
[4] Can explain the generalized concept of being equal and being larger (smaller).
[5] Can explain the basics of graph theory.
[6] Can explain the basics of formal language theory.

Rubric

	Ideal Level	Standard Level	Unacceptable Level
Achievement 1	Can explain sets and functions in a classified way, and determine whether the cardinalities of two sets are equal	Can explain sets and a functions, and determines whether the cardinalities of two sets are equal	Cannot explain a set and a function, and cannot determines whether the cardinalities of two sets are equal
Achievement 2	Can explain the propositions and predicates, and correctly write a mathematical proof using proof by contraposition and contradiction, and the mathematical induction methods accurately.	Can explain the propositions and predicates, and write a mathematical proof using proof by contraposition and contradiction, and the mathematical induction methods.	Cannot explain the propositions and predicates, and write a mathematical proof using proof by contraposition and contradiction, and the mathematical induction methods.
Achievement 3	Can define sets and functions recursively and correctly.	Can define sets and functions recursively.	Cannot define sets and functions recursively.
Achievement 4	Can explain the equivalence relation, partial orders, and total orders accurately.	Can explain the equivalence relation, partial orders, and total orders.	Cannot explain the equivalence relation, partial orders, and total orders.
Achievement 5	Can explain the path, connectivity, and tree of graph theory accurately.	Can explain the path, connectivity, and tree of graph theory.	Cannot explain the path, connectivity, and tree of graph theory.
Achievement 6	Can use Backus form, context-free grammar, finite automaton, and regular grammar correctly.	Can use Backus form, context-free grammar, finite automaton, and regular grammar.	Cannot use Backus form, context-free grammar, finite automaton, and regular grammar.

Assigned Department Objectives

学習・教育到達度目標 (D) （基礎学力と自主的・継続的学習能力）

学習・教育到達度目標 (F) （柔軟かつ創造的な設計能力）

Teaching Method

Outline:

Discrete mathematics is a field of mathematics that deals with finite or discrete subjects, and one of the foundations of computer science. In this course, you will learn about sets and functions, mathematical induction and recursive definitions, Backus form and context-free grammar, relationships between sets, graphs and trees, finite automaton and regular grammar.

Style:

Classes will be held in a lecture style.

Notice:

Make sure you understand the exact definition of the term and get an intuitive image from the formal description. Try to solve the examples or exercise problems yourself and score it against the answer.
Students who miss 1/3 or more of classes will not be eligible for a passing grade.

Characteristics of Class / Division in Learning

Aided by ICT

Applicable to Remote Class

Course Plan

			Theme	Goals
1st Semester
	1st Quarter
		1st	Basic form	Can use form to represent sets or conditions.
		2nd	The relationship between the sets	Can perform various set operations and can use basic formulas.
		3rd	Function 1/2	Can explain the basics function.
		4th	Function 2/2	Can explain the associative law, inverse function and substitution for injection, surjection, bijection, composition of function, and composition.
		5th	Infinite sets and cardinality 1/2	Can explain the cardinality of a set and can determine if the cardinalities of the two sets are equal.
		6th	Infinite sets and cardinality 2/2	Can explain the counting and cardinality of the continuum.
		7th	Propositions and proof by contradiction	Can explain the propositions and the converse, inverse, and contraposition. Can write mathematical proof using contraposition and proof by contradiction.
		8th	Midterm exam
	2nd Quarter
		9th	Predicate	Can explain a predicate (a function that takes only true or false as a value).
		10th	Propositional logic and its limitation in descriptive ability	Can explain the logical expression of a propositional logic and can represent a statement in a logical expression. Can explain the logical expression of predicate logic.
		11th	Language	Can explain the basics of formal languages.
		12th	Mathematical induction 1 of 2	Can mathematical proof by induction
		13th	Mathematical induction 2 of 2	Can write mathematical proof using the complete induction. Can explain the dual induction.
		14th	Recursive definition	Can define sets, functions, etc. recursively.
		15th	Backus form and context-free grammar	Can handle Backus form and context-free grammar.
		16th	Final exam
2nd Semester
	3rd Quarter
		1st	Binary relation 1 of 2	Can explain the basics of binary relation.
		2nd	Binary relation 2 of 2	Can calculate composition and exponentiation of binary relation.
		3rd	Equivalence relation 1/2	Can explain the equivalence relation, which is a generalization of the concept of equal.
		4th	Equivalence relation 2/2	Can handle equivalence class, quotient set, and subdivisions of equivalence relation.
		5th	Order 1 of 2	Can explain the partially ordered set and total order of the inequality (=) generalization.
		6th	Order 2 of 2	Can handle the upper extremum, lower extremum, maximum, and minimum values of a partially ordered set, and can explain the above (below) boundary.
		7th	Illustration of binary relation	Can illustrate the binary relation as a directed graph.
		8th	Midterm exam
	4th Quarter
		9th	Hasse diagram, topological sort, and transitive closure	Can draw a Hasse diagram of partially ordered set, and can explain the closure of topological sort and transitive.
		10th	Graph basics 1 of 2	Can explain the basics of graphs.
		11th	Graph basics 2 of 2	Can explain n-partite graph and several kinds of paths in a graph. Also, can represent a graph by adjacency matrix, adjacency list and incidence matrix.
		12th	The connectivity of a graph	Can explain the diameter, radius, connected component, cut vertex, bridge, connectivity and edge connectivity. Also, can explain n-connected and n-edge connected.
		13th	Tree	Can explain the fundamental concepts and theorems about trees. Also, can explain ordered tree, positional tree, binary tree and n-ary tree.
		14th	Finite automaton and nondeterministic finite automaton	Can define FA and NFA formally and draw their state transition diagrams. Also, can determine the language that they accept.
		15th	Regular grammar and regular expression	Can define right linear grammar and left linear grammar formally, and determine the language that they generate. Can represent a given language by regular expression.
		16th	Final exam

Evaluation Method and Weight (%)

	Examination	Presentation	Mutual Evaluations between students	Behavior	Portfolio	Other	Total
Subtotal	100	0	0	0	0	0	100
Basic Proficiency	0	0	0	0	0	0	0
Specialized Proficiency	100	0	0	0	0	0	100
Cross Area Proficiency	0	0	0	0	0	0	0