View source for Logic and Discrete Mathematics Exam Help

Logic and Discrete Math Revision Questions

I601: Logic and Discrete Mathematics


__TOC__

==Propositions, logical operations and compound propositional statements==

==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 [http://logitext.mit.edu/tutorial 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===