Part one: Logic and proof. A review of Logic of Propositions: Alphabet, syntax and semantics. A review of Logic of Predicates: Alphabet, syntax and semantics. Fundamental methods of roofs: Direct proof, Proof by contraposition, Existence Proof (constructive and non- constructive), Indirect proof, Proof by mathematical induction (weak and strong induction). Formal deductive systems: Hilbert-style systems, Semantic tableaux. Recursion and induction. Validation of programs by using Hoare Logic: Partial correctness of code, Total correctness of code. Relations-Relational databases (elementary presentation of Prolog).
Part two: Formal languages and automata. Alphabets and languages. Regular expressions and regular languages. Deterministic and non-deterministic finite automata. The pumping lemma for regular expressions. Context-free grammars and languages. Regular grammars. Grammar simplification. The pumping lemma for context-free languages. Pushdown automata. Turing machines. Computation using a Turing machine. Context sensitive grammars. Computability. Undecidable languages. Recursively enumerable languages. Ta limits of computability. Rice’s Theorem.