Mathematical
Skills
Time: Wednesdays 10:40 - 12:10 (on Dean's Day, 8 November, there will be no lecture)
Place: T5 (T149, Troja OP - 1.patro/1st floor. V Holešovičkách 747/2, 180 00 Praha 8)
Classes for the course Mathematical Skills in the winter semester of
2017 give an introduction to propositional logic and predicate
first-order logic, proof techniques such as mathematical induction and
proof by contradiction, and a variety of example problems that
illustrate different aspects of mathematical proof. Classes also enable
students to consolidate their learning and mathematical background to
help follow the Mathematical Analysis I, Discrete Mathematics I and
Linear Algebra I
courses.
Mathematical Skills is an optional course, although credits are awarded
for regular participation in classes and performance on the two tests
that will be set near the middle and at the end of the semester.
Resources
K.R. Rosen, Discrete Mathematics and Its Applications, 7th ed., 2012.
For those of a logic bent, see e.g. A.G. Hamilton, Logic for Mathematicians, revised ed. 1988
J. D'Angelo and D. West, Mathematical Thinking: Problem-solving and Proofs, 2nd edition, 2000.
Material covered
4 October
Axiom,
definition. Statements (either true or false): theorem, proposition,
observation; lemma; corollary. Claim, conjecture. Counterexample.
Truth functions. Negation. Conjunction (and). Disjunction (or) -
exclusive or, inclusive or. Implication (if ... then...). Equivalence
(if and only if). Proof as valid arguments transmitting truth of a set
of statements known to be true to another. Tautology, e.g., "a
falsehood implies anything"; modus ponens: if ((P implies Q) and P)
then Q.
11 October
DeMorgan's laws. Disjunctive normal form (DNF), conjunctive normal
form (CNF). Atomic propositions (variables taking truth values).
Compound propositions (well-formed formualas - wffs). Logical
equivalence.
18 October
Logical
equivalences used in proof strategies: contrapositive, proof by
contradiction, proof by cases. Examples of each type of proof. "By
symmetry", "without loss of generality".
25 October
Examples of proofs by contradiction (irrationality of square root of
prime number, infinitude of primes, of primes congruent to 3 modulo 4).
Pigeon-hole Principle (proof by contradiction). Ramsey theorem for
monochrome triangles in K_6.
1 November
Pigeohole-principle
to prove Erdos-Szekeres Theorem. Always find two vertices of the same
degree in a graph. Counterexamples (a 2-coloured K_5 with no
monochromatic triangles, a sequence of n^2 terms with no monotone
subsequence of more than n terms, n^2+n+41 prime until n=40, Fermat
primes).
Homework: prove (by contrapositive) that if 2^m + 1 is prime then m is
a power of 2.
8 November - no class
15 November
Natural numbers and mathematical induction,
recurrences, examples of proofs by induction,
22 November
Mathematical induction ctd., recursively defined functions/operations.
29 November
TEST
5 December
Well-ordering (WO) of natural
numbers, minimal counterexamples. Examples of proof by WO.
13 December
Further examples of proof by WO.
Combinatorial proofs: partitioning, counting in two ways ("double counting"). Examples.
20 December
Sperner's Lemma (ctd.). Further examples of proofs by counting in two ways, and by partitioning.
3 January
Inclusion-exclusion Principle. Examples.
10 January
TEST
