Logic and Discrete Mathematics (Spring 2021)

See the course description at study.ruc.dk for a brief and formal description of the course. Practical information can be found at the Moodle page of the course (requires login). All day-to-day information will be sent via Moodle to your RUC email account, so please read your RUC email regularly.

 

This page describes the content and structure of the course. In the following, the main subjects of the course are described; a detailed description of the structure of the course can be found further down the page.

      Logic The first subject of the course is logic, that is, propositional- and predicate logic as well as rules of inference and logic in mathematical proofs. This part of the course comprises the first six course days and covers the first chapter of the textbook.

      Sets and functions Two course days cover sections 2.1 - 2.3 in the book, which concern sets, set operations (union, intersection, powerset, Cartesian product, ...) and functions between sets (injections, surjections, inverse functions, ...). This is mainly high school material, formulated more rigeously.

      Algorithms and complexity Three course days covers sections 3.1 - 3.3 as well as Appendix A-3, which concern algorithms, pseudocode, and the computational complexity of algorithms.

      Induction and recursion Two course days cover sections 4.1 - 4.4 in the book, which concern mathematical induction, structural induction, recursive definitions, and recursive algorithms. The principle of mathematical induction can be used to prove a tremendous variety of mathematical results. Understanding how to read and construct proofs by mathematical induction is a key goal of this part of the course.

      Modeling computation Two course days covers sections 12.1 and 12.5 in the book. Section 12.1 concerns formal languages and different types of grammars, providing models for both natural languages, such as English, and for programming languages, such as Java. Section 12.5 concerns Turing machines, which are general mathematical models of computers, invented by the British mathematician Alan Turing.

During the course three mini projects are carried out, based on a handed out problem formulation. One of the mini-projects may optionally involve use of the programming language Prolog (Programming in logic), which will be briefly introduced at the course.

 

All references below are to the textbook, which can be bought at Amazon:

Kenneth H. Rosen, Discrete Mathematics and Its Applications, International Version, 6th edition, Mc-Graw Hill.

ISBN-13: 978-0071244749, ISBN-10: 0071244743

 

Course structure (NOTE: THE PLAN IS TENTATIVE!)

 

#

Day

Curriculum

Pages

Assignments

Hand-in

1

Tuesday 9/3

1.1 and slides propositional logic

1-16

1.1.1, 1.1.3, 1.1.5, 1.1.7, 1.1.13, 1.1.25, 1.1.27, 1.1.44, 1.1.49

 

2

Thursday 11/3

1.2

21-27

1.1.51, 1.2.5, 1.2.7, 1.2.9, 1.2.11, 1.2.15, 1.2.61

 

 

Sunday 14/3

 

 

 

1.1.50, 1.2.6, 1.2.14, 1.2.42

3

Tuesday 16/3

Priestís chapter

Assignments sent by email

4

Thursday 18/3

Introduction to Mini-project 1

Assignments sent by email.

Mini-projekt 1 start

5

Tuesday 23/3

1.3 and slides predicate logic

30-46

1.3.1, 1.3.5, 1.3.7, 1.3.17, 1.3.25, 1.3.51, 1.3.59

6

Thursday 25/3

1.4

50-58

not ex. 8, 16

1.3.55, 1.4.1, 1.4.9, 1.4.19ac, 1.4.27ac, 1.4.29ac, 1.4.33abc

Friday 26/3

1.3.12abcd, 1.3.18abc, 1.3.50, 1.3.56

7

Tuesday 30/3

1.5, 1.6, 1.7

63-72,

75-85,

86-94

1.5.1, 1.5.3cd, 1.5.5, 1.5.13ab, 1.6.1, 1.6.15, 1.6.39

Wednesday 31/3

Mini-projekt 1 to be handed in 12 (noon).

Mini-projekt 2 start

 

No teaching 1/4 (Easter)

 

 

 

8

Tuesday 6/4

(compressed)

Introduction to Mini-project 2. 2.1, 2.2, 2.3

111-128, 133-142

2.1.7, 2.1.15, 2.1.17, 2.1.21, 2.1.29, 2.1.33a, 2.2.3, 2.2.13, 2.2.45, 2.3.4a, 2.3.19ab, 2.3.25, 2.3.28, 2.3.29, 2.3.35, 2.3.38a, 2.3.76

Wednesday 7/4

1.5.24, 1.6.16, 2.1.4, 2.1.34a, 2.2.16a

9

Thurday 8/4

3.1, A-3

167-172

A10-A15

A-3.1, A-3.3, 3.1.1, 3.1.3, 3.1.9, 3.1.13

10

Tuesday 13/4

3.2 (A-2 if needed) and Prolog intro

180-190

3.2.1abcd, 3.2.3, 3.2.17, 3.2.19ab

2.3.18ab (cf. page 138), A-3.2, 3.1.6, 3.1.24 (cf. page 136)

11

Thursday 15/4

3.3

193-199

not ex. 5, 6

3.3.13, 3.3.23, 3.3.27

Mini-projekt 2 to be handed in

12

Tuesday 20/4

4.1, 4.2 and Prolog intro

263-270

278-279

283-288

4.1.3, 4.1.9 (use ex. 1), 4.1.47, 4.2.42

3.2.2abd, 3.2.18, 3.2.20b, 3.3.4, 3.3.12ab.

Mini-projekt 3 start

13

Thursday 22/4

4.3, 4.4 and Prolog intro

294-308

311-317

4.3.1ab, 4.3.7ac, 4.3.25a, 4.3.26ac, 4.4.7, 4.4.18, 4.4.21

14

Tuesday 27/4

12.1

785-793

12.1.7, 12.1.8, 12.1.13, 12.1.20, 12.1.21ab

4.1.56, 4.3.24a, 4.4.2, 4.4.10 (compare to algorithm page 169)

15

Thursday 29/4

12.5

827-837

not ex. 2

12.5.1, 12.5.3, 12.5.7, 12.5.11, 12.5.15

Mini-projekt 3 to be handed in