Logic and computation

Home / Undergraduate Studies / Courses / G semester / Logic and computation

EDG803 Logic and computation

Course website

Logic addresses the production of basic building blocks called propositions and their synthesis. A proposition is a declarative sentence that is either true or false, but not both. Logic is the basis of all mathematical reasoning and of all automated reasoning. The area of logic that deals with propositions is called propositional calculus or propositional logic and was first developed systematically by Aristotle approximately 2500 years ago.

Computation is any type of calculation which includes both arithmetical and non-arithmetical steps and follows a well-defined model like, for example, an algorithm. Computations entail finding an answer to a problem via math or logic. The study of computation is central in computer science.

In the context of this course we study basic logical operations, elements of propositional calculus as well as proof methods. We also address the classification of problems into easy and hard based on their computational hardness/complexity and present typical hard problems which appear very often in practice (like for example scheduling, set cover, coloring) together with methods used for obtaining practically efficient approximations to their solutions.

The course contributes to the development of “computational thinking” and offers the necessary background for the exploitation and use of methods, techniques and tools from the area of ​​computer science and technology in the study of issues in the field of modern history-archaeology.

Course outline

Companions

  1. ALGORITHMS TO LIVE BY. THE COMPUTER SCIENCE OF HUMAN DECISIONS, B. Christian, T. Griffiths (Eudoxus code: 86193640)
  2. DISCRETE MATHEMATICS AND ITS APPLICATIONS, K. Rosen (Eudoxus code: 77106820)