I601 Logic and Discrete Math Revision Questions
Propositions, logical operations and compound propositional statements
A proposition is a declarative sentence that is either true or false, but not both. A proposition can also be considered a result of logical operators (logical connectives, AND, OR, XOR, NAND). New compositions, called compound propositions are formed from existing propositions using logical operators.
Classification of compound propositions
Tautology
Contradiction
Contingency
Logical equivalence
Contrapositive
Converse
Algebra of propositions
Conjunctive and Disjunctive Normal Form of propositional statements
Predicates and quantifiers
Bound and free variables
Logical equivalences for quantifiers
Propositional calculus (PC)
Derivation in classical logic
Semantics of predicate calculus
Validity and satisfiability of predicate statements
Sequent predicate calculus LK
A way of deducing if a logic statement is true or not.
Please see yourself to the interactive tutorial of the Sequent Calculus (LK).
Proof techniques. Constructive and non-constructive proofs
Proofs by contraposition and contradiction
Mathematical induction (ordinary and strong)
Recursively defined functions
Elementary set theory, basic definitions and set operations
Power set and Cartesian product
Cardinality. Countable sets
Countability of rational numbers
Uncountable sets
Cardinality of power set
Continuum hypothesis
Binary relations
Equivalence relation
Partial order relation
Composition of relations, powers of relations
Closures of relations
Functions
Injective, surjective and bijective functions
Basic counting techniques
Product rule
Sum rule
Inclusion-exclusion principle
Pigeon-hole principle
Combinations and permutations
Binomial coefficients
Pascal's triangle
Permutations of multisets
Distributing n identical objects among k groups. Combinations with repetitions
Recurrence equations
Classification
Arithmetic and geometric progressions
Fibonacci sequence
Method of characteristic roots for solving of recurrence equations
Graphs, vertices, edges, paths, cycles and connectedness
Eulerian and Hamiltonian graphs, travelling-salesman problem
The shortest path problem
Dijkstra’s algorithm
Basic definitions and properties of trees
Minimum spanning tree problem
Kruskal’s algorithm
Isomorphism of labelled graphs
Prüfer’s code
Number of labelled trees
Counting of unlabelled trees
Planar graphs. Euler’s formula
Homeomorphic graphs
Characterization of planar graphs
Platonic solids and planar graphs
Colouring of graphs
Brooks’ theorem
Welch-Powell’s colouring algorithm
Colouring of planar graphs with 6 and 5 colours
Colouring of maps and four-colour problem
