Subject description - A4M33AU

Summary of Study | Summary of Branches | All Subject Groups | All Subjects | List of Roles | Explanatory Notes               Instructions
A4M33AU Automatic Reasoning
Roles:PO, V Extent of teaching:2P+2C
Department:13136 Language of teaching:CS
Guarantors:  Completion:Z,ZK
Lecturers:  Credits:6
Tutors:  Semester:L


Theorem proving is no more restricted to mathematics, but it is ever more often used in situations, when one needs to make sure that the suggested procedure meets the initial requirements it is used in deductive databases as well as for verification of SW or HW components. The process of proof construction has to be automated for that purpose. The course reviews current systems of 1st order theorem proving and their practical applications. There are explained underlying theoretical principles (model checking, resolution, tableaux) together with their practical and theoretical constraints. Special attention is devoted to gaining experience in choosing the best tool to solve a specific problem, in identification of mistakes in input or in strengthening the obtained results.

Course outlines:

1. History of automated reasoning in the context of artificial intelligence, review of its historical and up-to-date applications.
2. Problems in Boolean domains: from their specification and representation, to the formal solution. Properties of logical theorem proving - correctness and completness.
3. DPLL method, its existing implementations and their practical applications.
4. Model checking as a tool for verification, applications for finite automata.
5. Model checking - existing systems and how they are used in practice.
6. Automated theorem proving in general domains, language of 1st order logic.
7. Resolution and theorem provers based on this paradigma.
8. Workflow in resolution theorem provers and its basic steps: transformation to clausal form, ANL loop.
9. Non-resolution theorem provers: "tableaux", equality, transformation to DPLL.
10. Methods and systems for model construction in general domains.
11. Practical and theoretical boundaries for existing methods and systems.
12. Review of current automated theorem provers, their efficiency and practical utilization.
13. Algorithmic complexity of automated theorem provers and choice of the language for knowledge representation.
14. Spare slot.

Exercises outline:

1. Examples of typical problems for automated reasoning from various domains..
2. Specification of some simple problems in the formal language.
3. Transformation of the specification into the form requested by the theorem prover.
4. The tools for automated theorem proving - hands-on exercise.
5. Specification of more complex problems in the formal language and their automated solution I.
6. Specification of more complex problems in the formal language and their automated solution II.
7. Choice of the tool to be used in a specific problem.
8. Assignment of an individual project its goal is to implement a simple theorem prover applying specific clearly defined strategy or constraint on the used language in order to check impact of this.
9. Transformations of input and output for various theorem provers, interpretation of conclusions.
10. How to find an error in the problem statement.
11. Autonomous work on the assigned project the second part.
12. Simplification and strengthening of the obtained results.
13. Autonomous work on the assigned project the third part.
14. Credits, spare slot.


Bundy, A.: The Computational Modelling of Mathematical Reasoning, Academic Press 1983 (Bundy). Clarke, E.M. Jr., Grumberg, O. and Peled, D. A.: Model Checking, The MIT Press, 1999, Fourth Printing 2002. McCune, W.: Otter 3.3 Reference Manual ( Newborn, M.: Automated Theorem Proving: Theory and Practice Robinson, J.A., Voronkov, A. (Eds.): Handbook of Automated Reasoning (in 2 volumes). Elsevier and MIT Press 2001 Weidenbach, Ch.: SPASS: Combining Superposition, Sorts and Splitting (1999) Wos, L. and Pieper, G.W.: A Fascinating Country in the World of Computing: Your Guide to Automated Reasoning


Rozpoznávání a strojové učení, Pokročilé metody reprezentace znalosti


Subject is included into these academic programs:

Program Branch Role Recommended semester
MPIB Common courses V
MPKME1 Wireless Communication V 4
MPKME5 Systems of Communication V 4
MPKME4 Networks of Electronic Communication V 4
MPKME3 Electronics V 4
MPKME2 Multimedia Technology V 4
MPOI1 Artificial Intelligence PO 4
MPEEM1 Technological Systems V 4
MPEEM5 Economy and Management of Electrical Engineering V 4
MPEEM4 Economy and Management of Power Engineering V 4
MPEEM3 Electrical Power Engineering V 4
MPEEM2 Electrical Machines, Apparatus and Drives V 4
MPKYR4 Aerospace Systems V 4
MPKYR1 Robotics V 4
MPKYR3 Systems and Control V 4
MPKYR2 Sensors and Instrumentation V 4

Page updated 6.8.2020 14:51:49, semester: Z,L/2020-1, L/2019-20, Send comments about the content to the Administrators of the Academic Programs Proposal and Realization: I. Halaška (K336), J. Novák (K336)