Mathematical
Skills
Classes for the course Mathematical Skills in the winter semester of
2019 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 10:40 on Mondays (excepting holidays) in
Room S11 in the MFF building at Malostranské nám. 25, 1st floor.
Material covered
7 October
``Every quadratic has two roots" to illustrate the need to define the domain of variables and terms used, and to resolve ambiguities (exactly two? at most two? at least two?).
In logic: propositions as declarative statements that are true or false, but not both.
Mathematical texts: axioms, definition, lemma, proposition (proved to be true), theorem (major proposition), corollary, conjecture.
Axioms must be consistent (i.e. not lead to a contradiction) in order to avoid deriving a statement that is simultaneously true and false.
14 October
Propositional logic. Propositional variables. Truth tables for truth functions. Connectives. Propositional variables. Truth tables for unary
functions (negation) and
binary (and, inclusive or, exclusive or, material implication, equivalence).
Ways of formulating an implication in English ('if p then q', 'q is
a necessary condition for p' etc. ).
Constant truth functions T and F.
Logical equivalence (same truth table).
21 October
Disjunctive normal form (DNF), conjunctive normal form (CNF). Examples of logical equivalence (De Morgan's laws etc.).
4 November
Logical connectives as set operations (universal set = all tuples of truth values assigned to propositional variables).
Logical implication. Valid arguments. Modus ponens, modus tollens (contrapositive), proof by contradiction.
11 November
Proof by cases, proof of equivalence (implication one way and its converse), circle of implications (``the following are equivalent"). Proof by contradiction: logical form and examples.
Pigeonhole Principle proof. Contrapositive proof framed as a proof by contradiction.
18 November
In-class written TEST on material covered so far.
25 November
First-order logic: domain, propositional functions; quantifiers, negation of quantifiers (cf. De Morgan Laws). Axioms for a group using quantifiers, and other mathematical statements put into the language of First Order Logic.
``There is a unique x." For domain the natural numbers: ``There are infinitely many n", ``There are finitely many n", ``For sufficiently large n".
2 December
Natural numbers and induction. Examples of summing series. Fermat numbers (and their coprimality). Number of subsets.
9 December
Binomial coefficients and Pascal's recurrence. Other combinatorial recurrences obtained by partitioning the objects of size n to be counted into two parts (Stirling numbers of the second kind, Fibonacci numbers). Strong induction principle and examples of proofs using it.
16 December
Well-ordering of natural numbers. Equivalence with principle of mathematical induction. Examples of proofs using well-ordering.
6 January
In-class written TEST on material since the last test. Definitions, examples, basic proofs.
The test will take up to 80 minutes; it will be marked in a few days, and you will be informed if the mark you have does not reach the threshold described on SIS (under ``Podmínky zakončení předmětu" in English ``angličtina") to give you a course credit.