BSc:Logic and Discrete Mathematics
Logic and Discrete Mathematics (Philosophy 1)
- Course name: Logic and Discrete Mathematics (Philosophy 1)
- Course number: CSE113
- Subject area: n/a
Course characteristics
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.
Key concepts of the class
- Deductive Reasoning
- Inductive Reasoning
- Categorical Logic
- Propositional Logic
- Predicate Logic
- Basic elements of Graph Theory
- Planar Graphs
- Algorithms on Graphs
What is the purpose of this course?
The first part of the course (on Logic) sets students upon a path of finely honed logical skills essential for life in the modern world. This part of the course is thus specifically designed to improve writing, thinking and oral presentation skills that are applicable to all areas of academic study and relevant to working life.
The Discrete Math part of the course introduces students to the basic concepts of structuring algorithms through graph theory. This gives students the skills of deep algorithmic thinking. Thus, the successful completion of the course by students will give them the skills for further deep mastering of computer science courses.
Course Objectives Based on Bloom’s Taxonomy
What should a student remember at the end of the course?
- how to use Venn diagrams
- how to calculate truth values
- the formal structures of some arguments
- the difference between deduction and induction
- how to build spanning trees
- how to find Euler tour and Hamilton path
- how to use Dijkstra’s algorithm
- how to solve maximum flow problem
What should a student be able to understand at the end of the course?
By the end of the course, the students should be able to understand:
- what is categorical logic
- what is propositional logic
- what is predicate logic
- what is the difference between deduction and induction
- what is trees and spanning trees
- what is Euler and Hamilton graphs
- what is planar graphs
- Dijkstra’s algorithm
What should a student be able to apply at the end of the course?
By the end of the course, the students should be able to apply the content of this course in all areas of their academic study but also in their working life, with special reference to the following disciplines:
- computer science
- engineering
- robotics
Course evaluation
| Proposed points | ||
|---|---|---|
| Final Exam (Written, Math) | 40 | 40 |
| Mid Term (Written, Logic) | 40 | 40 |
| Participation/Attendance | 20 | 20 |
If necessary, please indicate freely your course’s features in terms of students’ performance assessment.
Final Exam (Written, Math):
The final exam will consist of theoretical and practical questions. The exam will be 90 minutes long.
Mid Term (Written, Logic):
The midterm exam will consist of quizzes and various exercises (such as open theoretical questions, multiple choices, and true/false questions). The Mid-Term will be held in class on week 8. The exam will last 75 minutes.
Participation/Attendance:
Weekly exercises (hereby reports) must be uploaded on moodle the day after the lab sessions are over. Although reports are not marked, they directly count towards participation. Failure to submit reports will incur in a penalty of the course mark, which will be proportional to the number of reports missing.
Overall score: 100 points (100%).
Grades range
| Proposed range | ||
|---|---|---|
| A. Excellent | 85-100 | 85-100 |
| B. Good | 75-84 | 75-84 |
| C. Satisfactory | 60-75 | 60-75 |
| D. Poor | 0-59 | 0-59 |
If necessary, please indicate freely your course’s grading features: The semester starts with the default range as proposed, but it may change slightly (usually reduced) depending on how the semester progresses.
Resources and reference material
Textbook:
- Hurley, P. J. (2014). A Concise Introduction to Logic. Wadsworth Pub Co.
- Priest, G. (2017). Logic: A very short introduction. Oxford, UK: Oxford University Press.
- Lehman, E., Leighton, F. T., Meyer, A. R. (2017). Mathematics for Computer Science. Massachusetts Institute of Technology Press.
Electronic copies of these books will be available on Moodle for download. All the materials for the course will be uploaded by the Professors on Moodle in due time. Please note: The lectures will be highly interactive and the students may be interrogated during the lectures, sometimes via kahoots (this approach is known as flipped learning).
Course Sections
The main sections of the course and approximate hour distribution between them is as follows:
| Section | Section Title | Lecture Hours | Seminars (labs) | Self-study | Knowledge evaluation |
|---|---|---|---|---|---|
| 1 | Basic Concepts | 2 | 2 | 8 | 2 |
| 2 | Fundamentals of Logic | 5 | 5 | 12 | 1 |
| 3 | Undirected graphs | 5 | 5 | 12 | 2 |
| 4 | Directed graphs | 2 | 2 | 8 | 1 |
Section 1
Section title:
Basic Concepts
Topics covered in this section:
- Introduction to Propositional Logic
- Logical Operators
- Truth Tables for Propositions
- Truth Tables for Arguments
- Introduction to Predicate Logic
- Quantifiers
- Translation
What forms of evaluation were used to test students’ performance in this section?
| Form | Yes/No |
|---|---|
| Development of individual parts of software product code | 0 |
| Homework and group projects | 1 |
| Midterm evaluation | 1 |
| Testing (written or computer based) | 0 |
| Reports | 0 |
| Essays | 0 |
| Oral polls | 1 |
| Discussions | 1 |
Typical questions for ongoing performance evaluation within this section
- Solve Truth Tables
- Use Truth Tables to analyse arguments
- Use Quantifiers to assess inferences
- What is Propositional Logic used for?
- What is Predicate Logic used for?
Typical questions for seminar classes (labs) within this section
- Exercises to understand the potential implications of Propositional Logic for Computer Science
- Exercises to get a glimpse of the importance of Predicate Logic in Science (e.g. Mathematics)
- Exercises to understand the relation between connectors and truth tables.
Test questions for final assessment in this section
- Solve exercises on Categorical Logic.
- Understand the importance of Categorical Logic in thinking and reasoning
- Evaluate categorical propositions
Section 2
Section title:
Fundamentals of Logic
Topics covered in this section:
- Compilation pipeline & compilation data structures
- Lexical analysis and deterministic state automata
- Bottom-up and top-down parsing
- Principles of semantic analysis
What forms of evaluation were used to test students’ performance in this section?
| Form | Yes/No |
|---|---|
| Development of individual parts of software product code | 1 |
| Homework and group projects | 1 |
| Midterm evaluation | 0 |
| Testing (written or computer based) | 0 |
| Reports | 1 |
| Essays | 0 |
| Oral polls | 0 |
| Discussions | 1 |
Typical questions for ongoing performance evaluation within this section
- Abstract syntax tree & symbol tables: what is it for and how create and manage them?
- How to organize communication between compilation phases?
- What are basic differences between bottom-up and top-down parsing?
Typical questions for seminar classes (labs) within this section
- How to implement a hash function for a symbol table?
- How to write a grammar for an expression using YACC/Bison tool?
Test questions for final assessment in this section
- What is the difference between Categorical and Propositional Logic?
- How does Predicate Logic differ from Categorical and Propositional Logic?
- Why is Predicate Logic so important?
- What are Truth-Functions and why do we use them?
- Compute True Tables for Propositions
- Compute True Tables for Arguments
Section 3
Section title:
Undirected graphs
Topics covered in this section:
- Basics elements of Graph Theory
- Trees
- Euler tours
- Hamilton paths
- Planar graphs
What forms of evaluation were used to test students’ performance in this section?
| Form | Yes/No |
|---|---|
| Development of individual parts of software product code | 1 |
| Homework and group projects | 1 |
| Midterm evaluation | 0 |
| Testing (written or computer based) | 0 |
| Reports | 0 |
| Essays | 0 |
| Oral polls | 0 |
| Discussions | 1 |
Typical questions for ongoing performance evaluation within this section
- What is the characteristic property of trees?
- How to find an Euler tour?
- What is a Hamilton path?
- Why are K3 and K5,5 not planar?
Typical questions for seminar classes (labs) within this section
- Exercises to build spanning trees.
- Exercises to find an Euler tour/cycle and a Hamilton path/cycle or determine that one of them or both do not exist.
- Exercises to determine if a graph is planar.
Test questions for final assessment in this section
- Explain handshaking lemma.
- Give necessary and sufficient conditions for the existence of an Euler tour.
- Give sufficient conditions for the existence of a Hamilton path (theorems of Dirac and Ore).
- Explain Kuratowski’s theorem.
Section 4
Section title:
Directed graphs
Topics covered in this section:
- Introduction to Directed Graphs
- Introduction to Weighted Graphs
- Dijkstra’s algorithm
- Maximum flow problem
What forms of evaluation were used to test students’ performance in this section?
| Form | Yes/No |
|---|---|
| Development of individual parts of software product code | 0 |
| Homework and group projects | 1 |
| Midterm evaluation | 0 |
| Testing (written or computer based) | 1 |
| Reports | 0 |
| Essays | 0 |
| Oral polls | 1 |
| Discussions | 1 |
Typical questions for ongoing performance evaluation within this section
- What is the difference between undirected and directed graphs?
- Why do we consider weighted graphs?
- What practical problems are solved using Dijkstra's algorithm?
- What is the maximum flow problem?
Typical questions for seminar classes (labs) within this section
- Introduction to Directed Graphs
- Introduction to Weighted Graphs
- Dijkstra’s algorithm
- Maximum flow problem
Test questions for final assessment in this section
- Explain the difference between undirected and directed graphs.
- Give the definition of weighted graphs?
- Explain Dijkstra's algorithm?
- What is the solution of the maximum flow problem (the Ford-Fulkerson algorithm)?