Discrete (aka finite aka concrete) mathematics


What is discrete mathematics?

It is also known as Mathematics for computer science. Sometimes finite mathematics, or concrete mathematics.

Discrete mathematics is the study of numerable sets, it is distinct from others. – such as integers, graphs, and statements in logic.
Discrete \neq Discreet

Collins Dictionary




https://wikidiff.com/countable/numerable#:~:text=As adjectives the difference between,able to be counted%3B countable.

Discrete. "separate, distinct from others," late 14c., from Old French discret, discre, and directly from Latin discretus "separated;" see discreet. Related: Discretely; discreteness. https://www.etymonline.com/word/discrete



NameWhy?TopicsAuthorsLast edition
Discrete mathematicsMost topics. Several examples. Coding.Richard Johnsonbaugh
Mathematics for Computer Science - TextbookThe clearestAlbert R MeyerEric LehmanF Thomson Leighton
Discrete Mathematics and Its ApplicationsapplicationsKenneth H. Rosen
Discrete and combinatorial mathematicasRalph P. Grimaldi
Mathematics for Computer Science (6.042J) - CourseAdam ChlipalaAlbert Meyer
Concrete Mathematics (Second edition)Discrete calculusDiscrete probabilityNumber TheoryDonald E. KnuthOren PatashnikRonald L. Graham
CS103: Mathematical Foundations of Computing
1. Nilsson, N.J.: "Artificial Intelligence, a new synthesis", Ed. Morgan Kaufmann Publishers, 1998


Nice to have

Foundations topics




A collection of objects is a set.

Level 1.

Collection. A group of objects of one type that have been collected by one person or in one place. Oxford dictionary.

Object. The objects are sometimes referred to as elements or members. Elements are unique.

Level 2.

Group. A number of people or things that are located close together or are considered or classed together. Oxford dictionary.

Level 3.

Number - The content of a statement of number is an assertion about a concept. [source: The Foundations of Arithmetic, §55, Engl.transl. page 67].

How to use sets?

TAG is the set of all elements such that element checks properties\text{TAG is the set of all elements such that element checks properties}.

Finite sets. E.g. A={1,2,3,4}A=\{\text{1,2,3,4}\}

Either infinite or large finite sets. E.g. A={xx is positive, even integer}A=\{x|x\text{ is positive, even integer} \}

Number sets

Worked examples

Mathematical logic

Key ideas

Logic is the basis of all reasoning.

Classical Propositional Logical

A proposition is a communicated declarative sentence that is either true or false, but not both. Remember structure no content.
What are the four types of sentences? Declarative, exclamatory, imperative, and interrogatory. https://typesofsentences.com/

You gonna use variables to represent prepositions, thus as you use letters in algebra. e.g.


The Connectives of Propositional Logic. In short, Logical formulas


Let pp and qq be propositions.

Conjunctionpqp \land q p && qp and q
Disjunctionpqp \lor q p || qp or q. Inclusive-or
Negation!pnot p

Worked examples

6. Lógica computacional, Enrique Paniagua Arís et al., Ed. Thomson, 2003.

7. Elementos de lógica formal, Calixto Badesa et al., Ed. Ariel, 2003.

Truth tables

A truth table is a table that shows all possible truth values given a proposition.

See "truth"

Truth table generator

When you wish to provide a conclusion (or proof in mathematics), you must use chain statements throughout logical consequences (or connectives, methods, and pieces of evidence) from a base set of previous results – such as axioms, theorems, and definitions.

value judgment

Conditional propositions and logical equivalence

If pp and qq are propositions, the proposition

if p then qif\text{ p } then \text{ q}

is called a conditional proposition and is denoted p    qp\implies q.

pqp    qp\implies qComments
TTTYou must prove this by assuming the antecedent.
TFFYou don’t prove this since the conclusion is false.
FTTTrue by default or vacuously true, so you don’t prove this.
FFTTrue by default or vacuously true, so you don’t prove this.
if HYPOTHESIS then CONCLUSION This is not correct, because it is not an argument.
  • Sufficient condition. If A then B. B whenever the occurrence of A is all that is needed for the occurrence of B. A guarantees B, but B might be achieved in other ways.

If X is a cat, then X is an animal.

  • Necessary condition. A cannot occur without the occurrence of B, but B doesn’t guarantee A.

If not B then not A.

If X is not an animal, then X is not a cat.

If X is a cat, then X is an animal.

Si P, entonces Q. P: X es Y. Q: Z es W.

Si X es Y, entonces Z es W.

P es una condicion suficiente para que ocurra Q. Q ocurre porque P. P no es una condicion necesaria para que ocurra Q. Q puede ocurrir sin necesidad de que ocurra P. P garantiza Q, pero Q puede lograrse de otras maneras. Siempre que ocurra P, pasara Q. La implicacion no es un argumento, sino su sintesis. Es el fundamento para las inferencias.

Analisis de la tabla de verdad: True => True True True => False False Si sabemos que (P=>Q es falso) entonces P es verdaero y Q es Falso. True =>

Si no Q, no P. Si no ocurre Q es una condicion suficiente para que no haya pasado P.

no P o Q.

A common mistake is no P ⇒ no Q, it is a mistake because Q can occur if P doesn’t happen.

Worked examples

Restate each proposition in the form of a conditional proposition.

  • Joey will pass the discrete mathematics exam if he studies hard.

    p: Joey will pass the discrete mathematics exam

    q: He studies hard.

    q    pq\implies p 

  • Rosa may graduate if she has 160 quarter-hours of credit.

    p: Rosa may graduate.

    q: she has 160 quarter-hours of credit.

    q    pq\implies p

  • A necessary condition for Fernando to buy a computer is that he obtain $2000.

    p: Fernando to buy a computer.

    q: He obtains $2000.

    A necessary condition for pp is qq.

    not q then not p

    p    qp \implies q

  • A sufficient condition for Katrina to take the algorithms course is that she pass discrete mathematics.

    p: Katrina to take the algorithms course.

    q: She passes discrete mathematics.

    A sufficient condition for pp is qq.

    q    pq \implies p

  • Getting that job requires knowing someone who knows the boss.

    p: Getting that job.

    q: Knowing someone who knows the boss.

    A necessary condition for getting a job is knowing someone who knows the boss.

    A necessary condition for p is q.

    p    qp \implies q

  • You can go to the Super Bowl unless you can’t afford the ticket.

    p: You can go to the Super Bowl.

    q: You can afford the ticket.

    p unless not q

    p except on the condition that not q

    A necessary condition for pp is not (not qq).

    A necessary condition for pp is q.

    p    qp\implies q

  • You may inspect the aircraft only if you have the proper security clearance.

    p: You may inspect the aircraft.

    q: You have the proper security clearance.

    A necessary condition for p is q.

    if not q, not p.

    if p, then q.

  • The audience will go to sleep if the chairperson gives the lecture.

    p: The audience will go to sleep.

    q: The chairperson gives the lecture.

    q    pq\implies p

  • The program is readable only if it is well structured.

    p: The program is readable.

    q: It is well structured.

    p    qp\implies q

  • A necessary condition for the switch to not be turned properly is that the light is not on.

    p: The switch is turned properly.

    q: The light is on.

    A necessary condition for not p is that not q.

    if q then p.

    q    pq\implies p

Represent the given proposition symbolically


Rules of Inference

Worked examples

Formulate the following arguments symbolically and determine whether each is valid.


p: I study hard.

q: I get A’s.

r: I get rich.








A predicate can be understood as a proposition whose truth depends on the value of one or more variables.

The contradictories in the square of opposition are the same as Morgan Law.

Nested Quantifiers


Mathematical systems and the Axiomatic method

What is suitable proof?

Direct proofs

Proof by contradiction

Proofs of equivalence

Problem Set


What is the proof?

Proof. A finite sequence of statements (called well-formed formulas in the case of a formal language), each of which is a previous result -axiom, an assumption, experiments, or theorems- in the sequence by a rule of inference.

Axiom. Simple postulate or assumption based on a priori knowledge and free contradictions.

Theorems. Important true statements.

Lemma. Preliminary statements.

Corollary. Statements that follow a few logical steps from the theorem.

Developing mathematical methods to verify programs and systems remains an active research area.


Good proofs


Mathematical Writing by Knuth, Larrabee, and Roberts, https://jmlr.csail.mit.edu/reviewing-papers/knuth_mathematical_writing.pdf

Guide to Proofs, Stanford https://web.stanford.edu/class/archive/cs/cs103/cs103.1156/handouts/070 Guide to Proofs.pdf

Proofwriting Checklist, Stanford https://web.stanford.edu/class/cs103/proofwriting_checklist

Some Remarks on Writing Mathematical Proofs by John M. Lee



Most ambiguous and inconsistent phrases and notations in maths
What are some examples of notations and words in maths which have been overused or abused to the point of them being almost completely ambiguous when presented in new contexts? For instance, a fun...


Direct proof

Worked examples

Proof by perfect induction o Proof by exhaustion

Proof of a Boolean theorem through perfect induction.

Simple induction

We know by Modus Ponens:

P(0)    P(1)P(0).Therefore, P(1).P(0)\implies P(1)\\ P(0).\\ \text{Therefore, }P(1).

The principle of induction says

[P(0)nP(n)    P(n+1)]    nP(n)[P(0) \wedge \forall nP(n)\implies P(n+1)]\implies \forall nP(n)
Base case: P(0)Inductive Hypothesis: Assume that P(n) is trueInductive step: \text{Base case: }P(0)\\ \text{Inductive Hypothesis: Assume that }P(n) \text{ is true}\\ \text{Inductive step: }
(nP(n)    nP(n+1)) iff nP(n+1)(\forall n P(n)\implies \forall n P(n+1)) \text{ iff } \forall nP(n+1)\\

nP(n+1)\forall n P(n+1) use nP(n)\forall n P(n) when nP(n)    nP(n+1)\forall n P(n)\implies \forall n P(n+1) but the same to simple P(n+1)P(n+1)if always is true then P(n)P(n)  is always true.

Strong induction


Worked example.




Boolean Algebra

California State University

Proof of a Boolean theorem through perfect induction


Zermelo-Fraenkel Axioms

Our Axioms

Mathematical data types


Sums and Asymptotics

Cardinality Rules

The Bijection Rule

Bijection := one-to-one correspondence

Each element of one set is paired with exactly one element of the other set, and each element of the other set is paired with exactly one element of the first set.

What does it mean to write |A| = n?

It means that there is a bijection f : A → {1, . . . , n}

MIT OpenCourseWare. 2016. 3.3.3 Counting with Bijections: Video. YouTube. Retrieved May 25, 2021 from https://www.youtube.com/watch?v=n0lce1dMAh8‌

The Bijection Rule or Equinumerosity

Let S and T be two finite sets. If there exists one-to-one correspondence (or bijection) between them, from S to T, if and only if S=T|S|=|T| i.e. S and T have the same number of elements. This is taken as the definition.


Counting Sequences

Multiplication Principle or Product Rule

P1×P2×...×Pn={(p1,p2,...pn)p1P1,p2P2,...,pnPn}=all sequencesP_1\times P_2\times ... \times P_n=\{(p_1,p_2,...p_n)|p_1\in P_1,p_2 \in P_2,...,p_n\in P_n\}=\text{all sequences} called Cartesian product.

Thus, if P1,P2,,PnP_1,P_2,\cdots ,P_n are finite sets, then

P1×P2××Pn=P1P2Pn|P_1\times P_2 \times \cdots \times P_n|=|P_1|\cdot|P_2|\cdots|P_n|

For example, if A={x,y,z}A=\{x,y,z\} and B={1,2,3}B=\{1,2,3\}

A×B={(x,1),(x,2),(x,3),(y,1),(y,2),(y,3),(z,1),(z,2),(z,3)}A\times B=\{(x,1),(x,2),(x,3),(y,1),(y,2),(y,3),(z,1),(z,2),(z,3)\}

A×B=AB=33=9|A\times B|=|A|\cdot|B|=3 \cdot 3=9

Key ideas

Product Rule Worked examples

Exercises 10–12 ask about strings of length 5 formed using the letters ABCDEFG without repetitions.

Two chess players, A and B, are going to play 7 games. Each game has three possible outcomes: a win for A (which is a loss for B), a draw (tie), and a loss for A (which is a win for B). A win is worth 1 point, a draw is worth 0.5 points, and a loss is worth 0 points.

Addition Principle or Sum Rule

If A1,A2,...,AnA_1,A_2,...,A_n are disjoint sets, then:

A1A1...An=A1+A2+...+An|A_1\cup A_1\cup ...\cup A_n|=|A_1|+|A_2|+...+|A_n|

Inclusion–exclusion principle

If XX and YY are finite sets, then

XY=X+YXY|X\cup Y|=|X|+|Y|-|X\cap Y|

The k-to-1 rule or division rule

If B is a finite set and f : A → B maps precisely k items of A to every item of B, then A has k times as many items as B.


The division rule is a common way to ignore “unimportant” differences when you are counting things. You can count distinct objects, and then use the division rule to “merge” the ones that are not significantly different.


A permutation of n things taken r at a time, written P(n,r), is an arrangement in a row of r things, taken from a set of n distinct things. Order matters.

In your problem, (a0,a1,a2)(a1,a2,a0)?(a_0,a_1,a_2)\ne(a_1,a_2,a_0)?

Example: How many permutations of the letters ABCDEF contain the letters DEF together in anyorder?

Counting Subsets or combinations

A combination of n things taken r at a time, written C(n,r) or n r (“n choose r”) is any subset of r things from n things. Order makes no difference.

In your problem, (a0,a1,a2)=(a1,a2,a0)?(a_0,a_1,a_2)=(a_1,a_2,a_0)?

The key points to remember in this section are that a permutation takes order into account and a combination does not take order into account. Thus, a key to solving counting problems is to determine whether we are counting ordered or unordered items.

Counting subsets=CoutingGroup by repetitions\text{Counting subsets}=\frac{Couting}{\text{Group by repetitions}}

Combinatorial Proofs

n(n1k1)=k(nk)n{n-1 \choose k-1}=k{n \choose k}

Vandermonde's identity

(m+nk)=j=0k(mj)(nkj){m+n \choose k} = \sum^k_{j=0} {m \choose j}{n\choose k-j}

The Binomial Theorem

Pascal’s Triangle Identity

Worked examples

The Pigeonhole Principle

TIP. Bash. Brace expansion.

echo {1..3}{1..2}{5..10} | wc -w # 36
echo {1..3}{1..2} # 11 12 21 22 31 32


Generating Functions

Diophantine equations


Finite calculus

Discrete logarithm problems


Recurrences relations, sequences, and subsequences, or difference equations

Worked examples