Discrete Structures and Mathematical Logic

The course presents introduction to basic concepts in discrete mathematics, abstract algebra, mathematical logics (especially to logical knowledge representation and inference) and combinatorics; abilities to apply these concepts in information structures analysis are being formed; students learn basics of formal logical descriptions, literacy in logical symbolisation, will get acquainted with principles of logical induction and logical deduction. Form of study: lectures and problem solving practical.

Provide knowledge of the basic concepts of discrete structures and mathematical logic and develop practical skills in application of these concepts to solve real world problems.

-

1. Knowledge representation. Models of knowledge representation, knowledge bases, extensional and intensional knowledge, examples. 2 Discrete nature of knowledge. Semantic elements of knowledge, judgments, reasoning, their semantical structure, ambiguity of natural language. 3. Fundamentals of intuitive set theory. The concept of a set, its properties, symbols for sets, sets of numbers, operations over sets, Venn diagrams, laws of set algebra, paradoxes. 4. Relations and functions. Cartesian product, relations, properties of relations, functions, properties of functions (surjection, injection, bijection), examples. 5. Algebraic structures. Structures with one operation, structures with two operations, Boolean algebra. 6. Combinatorics. Formulation of problems in combinatorics, combinatorics problems with regular structure, combinatorics problems with irregular structure, combinatorial trees, generating functions in combinatorics, combinatorial algorithms. 7. Functions in logic. Features as functions, operators (functions of objects), propositional functions. 8. Propositional logic. (syntax): Complex propositions, truth tables, main tautologies, tautologies in reasoning, proof in mathematics; (semantics): analysis of logical possibilities, logical relations among complex propositions, formalization of complex propositions, normal forms. 9. Knowledge representation in propositional logic. Methods of deductive reasoning, transformation of knowledge base to CNF, examples. 10. Inference in propositional logic. Resolution rule, proof by contradiction, algorithms of inference, examples. 11. First-order logic. Concept of predicate, quantifiers, laws of first-order logic, categorical propositions, reasoning in first-order logic, syllogisms, relations in reasoning, using properties of relations in reasoning. 12. Knowledge representation in first-order logic. Knowledge base of the first-order logic, syntax of formulas, interpretation, Skolemization, transformation of knowledge base to canonical form, examples. 13. Inference in the first-order logic. Herbrand‘s universe, Herbrand‘s base, unification, algorithms of inference, examples.

1. Three practical works are evaluated: 1. Algebraic structures and combinatorics ten point system. 2. Fundamentals of set theory, relationships and functions (10 point system). 3. Logic of statements, derivation in the logic of statements; predicate logic (10 point system). The final practical grade is the average of three practical assignments. 2. The midterm exam is written in the form of a written test or open-ended questions. The student must know the basic concepts, laws and be able to explain those concepts. Evaluated on a 10-point scale 3. Final assessment exam in writing. The student's ability to concisely answer open test questions, the ability to choose the correct answer from several answer options, logical thinking are assessed. Evaluated on a ten-point scale.