Mathematical
Skills
Classes for the course Mathematical Skills in the winter semester of
2018 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 set during the semester.
Resources
K.P Rosen, Discrete Mathematics and Its Applications, 7th ed., 2012
For more advanced material:
A.G. Hamilton, Logic for Mathematicians, revised ed. 1988
J. D'Angelo and D. West, Mathematical Thinking: Problem-solving and
Proofs, 2nd edition, 2000.
Classes are held at 15:40 on Mondays (excepting holidays) in
Room S10 in the MFF building at Malostranské nám. 25, 1st floor.
Material covered
1 October
Propositions (declarative statements). True, false, but not both. Propositional logic. Connectives. Truth tables for unary
functions (negation) and
binary (and, inclusive or, exclusive or, implication, equivalence).
Ways of formulating an implication in English ('if p then q', 'q is
a necessary condition for p' etc. ).
8 October
Truth tables. Logical equivalence. Implication and contrapositive. DeMorgan's laws. Disjunctive Normal Form (DNF).
15 OctoberRecap of
logical equivalence. Conjunctive Normal Form. Logical implication.
Valid arguments. First-order logic: domain, variables, values,
propositional functions and quantifiers.
22 October
Universal and existential quantification. Examples and counterexamples.
Expressing restricted domain for existentially and universally
quantifed formula. Uniqueness quantifier (expressed in terms of
universal and existential). Nested quantifiers. Translating
mathematical statements into quantified formulas (e.g. injective
function, axioms for reals, Archimedean Property), the need to define
terms and specify domains precisely e.g. "every cubic has a real root".
DeMorgan's laws for universal quantifiers (pushing negation inside
quantifiers).
29 October
Valid arguments. Rules of inference: argument forms (modus ponens,
proof by contradiction, etc.) and instantiation/generalization for
quantifiers. Examples, counterexamples. Infinitely many primes: proof
by contradiction. Direct proofs (e.g. square of an odd number is odd,
product of two reals greater than 1 is also greater than 1).
Axiom, Lemma, Proposition/Theorem, Corollary.
5 November
Direct proofs (expand definitions, manipulate information given, adding
use of known results and techniques/calculation). "P iff Q" by proving
"P implies Q" and "Q implies P". Indirect proofs: contrapositive and
proof by contradiction. Square root of 2 irrational. Pigeon-hole
principle.
12 November
Mid-semester test on topics covered in class, as listed in summary form
above, from 1 October to 5 November (excluding Pigeonhole Principle at
the end). Definitions (e.g. logical implication, and techniques
(e.g. how to form DNF from truth table, how to negate a quantifed
statement, taking contrapositive of a conditional statement to give an
indirect proof).
Test will be written, 1 hour.
19 November
The Pigeonhole Principle and applications. Ramsey theorem for complete
graph on 6 vertices (colour edges red and green and there's always a
red triangle or green triangle).
Pigeonhole Principle at
Cut-the-Knot (has many exercises).
26 November
Mathematical
induction. Basic examples: 2^n smaller than n! for n greater than
3; 1+2+ .... + n = n(n+1)/2; sum of geometric series. Alternative
proofs e.g. for geometric series, writing 1+ r + .... + r^{n-1}= S_n,
we have rS_n - S_n = r^n - 1, from which S_n = (r^n -1)/(r-1);
combinatorial proof of binomial theorem (choosing x or y from n factors
(x + y) ).
3 December
Pascal's recurrence (combinatorial proof) and the binomial theorem by
induction. Recurrence for number of derangments of [n] (permutations
with no fixed point). Strong mathematical induction (inductive
hypothesis all previous values rather than just immediately preceding).
Examples: every natural number greater than 1 has a prime factor;
closed formula for recursively defined sequences involving two or more
previous terms (e.g. Fibonacci); triangulation of an n-gon into n - 2
triangles.
17 December
Well-Ordering of natural numbers. Minimum counterexamples. Examples of
proofs: every natural number greater than 1 has a prime factor (cf. by
strong induction); Division Algorithm in integers (integer a = qd + r
for unique integer q and non-negative r <d); a graph with an odd
cycle as a subgraph has an induced odd cycle. Equivalence of
Well-Ordering and (Strong) Mathematical Induction.
7 January
End-of-semester test.
Revision for this test can be based on the following sections from K. Rosen's Discrete Mathematics and its Applications:
5.1 and 5.2 (Induction), 6.2 (Pigeon-hole Principle), 6.3 (Binomial coefficients)
