BSc: Logic and Discrete Mathematics

Logic and Discrete Mathematics (Philosophy 1)

• Course name: Logic and Discrete Mathematics (Philosophy 1)
• Code discipline: CSE113
• Subject area: Math, Computer Science

Short Description

This course consists of two distinct but overlapping parts: i. Logic; and ii. Discrete Mathematics. The first part of the course is an introduction to formal symbolic logic. Philosopher John Locke once wrote that ``logic is the anatomy of thought. This part of the course will teach students to analyse and evaluate arguments using the formal techniques of modern symbolic logic. The second part of the is designed for students to teach them basic notions of graph theory, discrete optimization and dynamic programming. This part will give practical experience with basic algorithms in discrete mathematics.

Course Topics

Course Sections and Topics

Section	Topics within the section
Basic of Logic	Logical Operators Truth Tables for Propositions Propositional calculus Quantifiers Predicate Logic Basic Proof Techniques in Math Fundamental proofs Use of propositional calculus to do proofs
Set Theory & Finite combinatorics	Fundamentals of the set theory From sets to relations Functions and numbers Algebra of binary relations Principles of finite combinatorics Recursion and Discrete Optimization Linear recurrence relations
Basic of Graphs	From set and relations to graphs Euler tours and graphs Hamilton paths and graphs Planar graphs and Euler formula Trees and Kőnig's infinity lemma

Intended Learning Outcomes (ILOs)

What is the main purpose of this course?

This calculus course will provide an opportunity for participants to:

• understand key principles involved in differentiation and integration of functions
• solve problems that connect small-scale (differential) quantities to large-scale (integrated) quantities
• become familiar with the fundamental theorems of Calculus
• get hands-on experience with the integral and derivative applications and of the inverse relationship between integration and differentiation.

ILOs defined at three levels

We specify the intended learning outcomes at three levels: conceptual knowledge, practical skills, and comprehensive skills.

Level 1: What concepts should a student know/remember/explain?

By the end of the course, the students should be able to ...

• know the categorical logic
• know the propositional logic
• know the predicate logic
• explain the difference between deduction and induction
• know the trees and spanning trees
• remember the Euler and Hamilton graphs
• know what is planar graphs
• explain the Dijkstra’s algorithm

Level 2: What basic practical skills should a student be able to perform?

By the end of the course, the students should be able to ...

• use Venn diagrams
• calculate truth values
• analyse formal structures of some arguments
• differ the deduction and induction
• build spanning trees
• find Euler tour and Hamilton path
• use Dijkstra’s algorithm
• solve maximum flow problem

Level 3: What complex comprehensive skills should a student be able to apply in real-life scenarios?

By the end of the course, the students should be able to ... ...

Grading

Course grading range

Grade	Range	Description of performance
A. Excellent	90-100	-
B. Good	75-89	-
C. Satisfactory	60-74	-
D. Fail	0-59	-

Course activities and grading breakdown

Activity Type	Percentage of the overall course grade
Midterm	40
Final exam	40
In-class participation	20

Recommendations for students on how to succeed in the course

• Participation is important. Attending lectures is the key to success in this course.
• Review lecture materials before classes to do well.
• Reading the recommended literature is obligatory, and will give you a deeper understanding of the material.

Resources, literature and reference materials

Open access resources

• K.H. Rosen, Discrete Mathematics and Its Applications (7th Edition). McGraw Hill, 2012.
• Lehman, E., Leighton, F. T., Meyer, A. R. (2017). Mathematics for Computer Science. Massachusetts Institute of Technology Press.

Activities and Teaching Methods

Teaching and Learning Methods within each section

Teaching Techniques	Section 1	Section 2	Section 3
Problem-based learning (students learn by solving open-ended problems without a strictly-defined solution)	1	1	1
Project-based learning (students work on a project)	0	0	0
Modular learning (facilitated self-study)	0	0	0
Differentiated learning (provide tasks and activities at several levels of difficulty to fit students needs and level)	1	1	1
Contextual learning (activities and tasks are connected to the real world to make it easier for students to relate to them)	0	0	0
Business game (learn by playing a game that incorporates the principles of the material covered within the course)	0	0	0
Inquiry-based learning	0	0	0
Just-in-time teaching	0	0	0
Process oriented guided inquiry learning (POGIL)	0	0	0
Studio-based learning	0	0	0
Universal design for learning	0	0	0
Task-based learning	0	0	0

Activities within each section

Learning Activities	Section 1	Section 2	Section 3
Lectures	1	1	1
Interactive Lectures	1	1	1
Lab exercises	1	1	1
Experiments	0	0	0
Modeling	0	0	0
Cases studies	0	0	0
Development of individual parts of software product code	0	0	0
Individual Projects	0	0	0
Group projects	0	0	0
Flipped classroom	0	0	0
Quizzes (written or computer based)	1	1	1
Peer Review	0	0	0
Discussions	1	1	1
Presentations by students	0	0	0
Written reports	0	0	0
Simulations and role-plays	0	0	0
Essays	0	0	0
Oral Reports	0	0	0

Formative Assessment and Course Activities

Ongoing performance assessment

Section 1

1. Solve Truth Tables
2. Use Truth Tables to analyse arguments
3. Use Quantifiers to assess inferences
4. What is Propositional Logic used for?
5. What is Predicate Logic used for?

Section 3

1. What is the characteristic property of trees?
2. How to find an Euler tour?
3. What is a Hamilton path?
4. Why are K3 and K5,5 not planar?
5. What is the difference between undirected and directed graphs?
6. Why do we consider weighted graphs?
7. What practical problems are solved using Dijkstra's algorithm?
8. What is the maximum flow problem?

Final assessment

Section 1

1. What is the difference between Categorical and Propositional Logic?
2. How does Predicate Logic differ from Categorical and Propositional Logic?
3. Why is Predicate Logic so important?
4. What are Truth-Functions and why do we use them?
5. Compute True Tables for Propositions
6. Compute True Tables for Arguments

Section 3

1. Explain handshaking lemma.
2. Give necessary and sufficient conditions for the existence of an Euler tour.
3. Give sufficient conditions for the existence of a Hamilton path (theorems of Dirac and Ore).
4. Explain Kuratowski’s theorem.
5. Explain the difference between undirected and directed graphs.
6. Give the definition of weighted graphs?
7. Explain Dijkstra's algorithm?
8. What is the solution of the maximum flow problem (the Ford-Fulkerson algorithm)?

The retake exam

Retakes will be run as a comprehensive exam, where the student will be assessed the acquired knowledge coming from the textbooks, the lectures, the labs, and the additional required reading material, as supplied by the instructor. During such comprehensive oral/written the student could be asked to solve exercises and to explain theoretical and practical aspects of the course.