Logic and Discrete Mathematics Exam Help: Difference between revisions

Revision as of 14:13, 16 January 2016

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

@@ Line 1: / Line 1: @@
-Logic and Discrete Math Revision Questions
+I601 Logic and Discrete Math Revision Questions
-I601: Logic and Discrete Mathematics
@@ Line 7: / Line 5: @@
 ==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==