🎡

Discrete 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

Wiki

https://www.merriam-webster.com/dictionary/numerable

https://www.dictionary.com/browse/numerable?s=t

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

Resources

Foundations

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
Untitled


Requisites

Nice to have

Foundations topics

Applications

Sets

Definitions

📌
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

The following exercise is from [1]

Let A={i+(5i)iZ0i4}A=\{i+{5 \choose i} |i\in \mathbb{Z} \land 0\le i \le 4\}  and B={3ii{1,2,4,5}}B=\{3i|i\in\{1,2,4,5\}\}.

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.

p:1+2=3p:1+2=3

The Connectives of Propositional Logic. In short, Logical formulas

Definition.

Let pp and qq be propositions.

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

Grammar

Perhaps you’ve never seen before this language formalization.

<S> := P | P is P | P are P
<Proposition> := <Proposition> and <Proposition>
<Proposition> := <Proposition> or <Proposition>
<Proposition> := <Proposition> xor <Proposition> | either <Proposition> or <Proposition>
<Proposition> := not <Proposition>
<Proposition> := <Proposition> => <Proposition>
<Proposition> := (<Proposition>)
<Proposition> := <p> | True | False

<p> is whatever string (including numbers) that doesn’t be a reserved word. In this grammar order is important, it indicates precedence order when they have the same precedence level they are equals.

Note that True and False are propositions. Either-or mean XOR. In Spanish, we can use “o … o …”.

Does "either-or " mean XOR or OR? (2022, December 13). Retrieved from https://math.stackexchange.com/questions/1906242/does-either-or-means-xor-or-or

When people claim something, it means they want it to be true.

Representations

Worked examples

Suppose that Smartphone A has 256 MB RAM and 32 GB ROM, and the resolution of its camera is 8 MP; Smartphone B has 288 MB RAM and 64 GB ROM, and the resolution of its camera is 4 MP; and Smartphone C has 128 MB RAM and 32 GB ROM, and the resolution of its camera is 5 MP. Determine the truth value of each of these propositions.

smartphone(a, ram(256), rom(32), cam(8)).
smartphone(b, ram(288), rom(64), cam(4)).
smartphone(c, ram(128), rom(32), cam(5)).

a) Smartphone B has the most RAM of these three smartphones.

? smartphone(b, ram(X), _, _), smartphone(Y, ram(Z), _, _), Y \= b, X > Z.
true

b) Smartphone C has more ROM or a higher resolution camera than Smartphone B.

? smartphone(c, _, rom(RomC), cam(CamC)), smartphone(b, _, rom(RomB),cam(CamB)), (RomC > RomB; CamC > CamB).
true

c) Smartphone B has more RAM, more ROM, and a higher resolution camera than Smartphone A.

d) If Smartphone B has more RAM and more ROM than Smartphone C, then it also has a higher resolution camera.

e) Smartphone A has more RAM than Smartphone B if and only if Smartphone B has more RAM than Smart-phone A.

Fuzyy logic.

happy(fred, 0.8).
happy(jonh, 0.4).

not(happy(_, Y), Z) :- Z is 1-Y.
and(happy(_, X), happy(_, Y), Z) :- Z is min(X,Y).

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

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

Environment

A particular row or instance in the truth table is an environment, world, or model.

Natural Language into Formal Language. Natural Logic.

2

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.
💡
if ANTECEDENT then CONSEQUENT
if CAUSE then CONSEQUENCE
💡
CONSEQUENT if ANTECEDENT
  • 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.

English equivalences

if states a relation between cause and effect, makes a prediction, or speculates about what might happen. https://www.merriam-webster.com/grammar/if-vs-whether-difference-usage

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

  • Any set of Boolean operators that is sufficient to represent all Boolean expressions is said to be complete. Which of the following is NOT complete? A) {AND,NOT} B) {NOT, OR} C) {AND,OR} D) {NAND} E) {NOR}
  • Provide a method that given a set of Boolean operators, it gives you ifs

Represent the given proposition symbolically

Material Implication: If Pigs Could Fly. (2019, October 04). Retrieved from https://www.dcproof.com/IfPigsCanFly.html

Argument

Arguing or proving something is not the same as explaining it. So, if you prove something, you are not saying anything noting how the result or proof is coming up. This difference is useful when you ask since sometimes you want to learn the underlying patterns or the process.

Rules of Inference

Worked examples

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

Let

p: I study hard.

q: I get A’s.

r: I get rich.

Notes

https://en.wikipedia.org/wiki/List_of_rules_of_inference

https://calcworkshop.com/logic/rules-inference/

http://logic.stanford.edu/intrologic/glossary/rule_of_inference.html

http://intrologic.stanford.edu/chapters/chapter_04.html

https://www.cs.sfu.ca/~ggbaker/zju/math/inference.html

Predicates

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

xD,P(x)x\in D, P(x): let x is in D, we claim P(x)P(x)

Example: P(x)P(x)

Quantifiers

xD,P(x)\forall x \in D, P(x) , for all x in D we claim P(x)P(x)

x\exists x

Negation. The negation of x,P(x)\forall x ,P(x) is that there exists at least one value for which the statement is not true.

Nested Quantifiers

Exercises

Formulate the leap year definition as a predicate. If you achieve this, you don’t need to nest “if” clauses in your program.

on every year that is evenly divisible by 4
  except every year that is evenly divisible by 100
    unless the year is also evenly divisible by 400

Predicate

xYears,LeapYear(x):x(mod 400)==0 or (x(mod 4)==0 and x(mod 100)!=0)x\in Years, LeapYear(x) : x(\text{mod } 400)==0 \text{ or } (x(\text{mod } 4)==0 \text{ and } x(\text{mod } 100)!=0)

The last rule has more priority, so if x(mod 400)==0x(\text{mod } 400)==0 is true, xx is a leap year.

Proofs

Mathematical systems and the Axiomatic method

What is suitable proof?

Uninformative and informative proofs

Direct proofs

Proof by contradiction

Proofs of equivalence

Prove the Morgan Law with .

Problem Set

Proofs

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.

https://mathoverflow.net/questions/18352/theorem-versus-proposition

Writing code and mathematics

Notes

https://math.mit.edu/~poonen/papers/writing.pdf

Logical Verification 2019–2020. (2022, December 13). Retrieved from https://lean-forward.github.io/logical-verification/2019

Theorem Proving in Lean — Theorem Proving in Lean 3.23.0 documentation. (2021, October 02). Retrieved from https://leanprover.github.io/theorem_proving_in_lean

Natural number game. (2021, May 27). Retrieved from https://www.ma.imperial.ac.uk/~buzzard/xena/natural_number_game

Logic and Proof — Logic and Proof 3.18.4 documentation. (2021, December 04). Retrieved from https://avigad.github.io/logic_and_proof/index.html

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

https://www.youtube.com/watch?v=B0acu5nhG0w&ab_channel=StanfordOnline

https://math.stackexchange.com/questions/424854/1-0-by-integration-by-parts-of-tanx/424855#424855

Translating from English into Predicate Logic with Identity (Unit 10.1). (2015, February 17). Retrieved from https://dornsife.usc.edu/assets/sites/548/scripts/LogicWebExercises/bwr-exercises/unit10.1.html

Tammet, T. (2021, September 04). Logictools. Retrieved from https://logictools.org/index.html

Tree Proof Generator. (2022, December 13). Retrieved from https://www.umsu.de/trees

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...
https://math.stackexchange.com/questions/1024280/most-ambiguous-and-inconsistent-phrases-and-notations-in-maths

Methods

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

https://www.youtube.com/watch?v=9w20J4j5-0Y&ab_channel=AtticPhilosophy

Worked example.

https://web.stanford.edu/~dntse/classes/cs70_fall09/cs70-2_notes3.pdf

https://math.stackexchange.com/questions/2926239/when-we-can-use-mathematical-induction-and-when-we-cant

https://www.purplemath.com/modules/inductn2.htm

Boolean Algebra

California State University

Proof of a Boolean theorem through perfect induction

https://www.youtube.com/watch?v=z7QCT8cgsR4&ab_channel=FrankStajanoExplains

Zermelo-Fraenkel Axioms

Our Axioms

Mathematical data types

Symbols

== vs ::=::=

FAQ

Is a definition a proposition?

Please Explain Kuratowski Definition of Ordered Pairs. (2022, December 22). Retrieved from https://math.stackexchange.com/questions/1767604/please-explain-kuratowski-definition-of-ordered-pairs

Why would definition not be proposition? (2022, December 22). Retrieved from https://philosophy.stackexchange.com/questions/1074/why-would-definition-not-be-proposition

What is the difference between proofs and arguments?

What's the difference between an argument and proof? (2022, December 22). Retrieved from https://www.quora.com/Whats-the-difference-between-an-argument-and-proof

How do I know if my mathematical proof is actually a proof or just a convincing argument? (2022, December 22). Retrieved from https://www.quora.com/How-do-I-know-if-my-mathematical-proof-is-actually-a-proof-or-just-a-convincing-argument

Counting

Counting is finding the finite set’s cardinality.

Foundations rules

The sum rule.

If two sets are disjoint, AB=A+B|A\cup B|=|A|+|B|

The product rule.

X×Y=XY|X\times Y|=|X||Y|

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.

https://www.cs.colostate.edu/~cs220/summer19/slides/16_bijection_rule.pdf

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|

But, if we have three finite sets, then

XYZ=X+Y+ZXYXZYZ+XYZ|X\cup Y \cup Z|=|X|+|Y|+|Z|-|X\cap Y|-|X\cap Z|-|Y\cap Z|+|X \cap Y\cap Z|

And for nn finite sets

A1A2...A3=S{1,2,...,n}(1)S+1iSAi|A_1\cup A_2\cup ... A_3|=\\ \sum\limits_{\emptyset \neq S \subset \{1,2,...,n\}} (-1)^{|S|+1}| \bigcap_{i\in S} A_i|

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.

https://dspace.mit.edu/bitstream/handle/1721.1/70477/6-042j-fall-2002/contents/readings/ln9.pdf

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.

Permutations

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

Consider the function f.

int f(int x)
{
	int n = 1;	
	if (x%2 == 0) n *= 2;
	if (x%3 == 0) n *= 3;
	if (x%5 == 0) n *= 5;
	if (x%7 == 0) n *= 7;
	if (x%11 == 0) n *= 11;
	if (x%13 == 0) n *= 13;
	if (x%17 == 0) n *= 17;
	if (x%19 == 0) n *= 19;
	return n;
}

The Pigeonhole Principle

How many digits does 125¹⁰⁰ have?

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

https://wiki.bash-hackers.org/syntax/expansion/brace

Generating Functions

Diophantine equations

https://www.hackmath.net/en/calculator/integer-diophantine-equations-solver

Finite calculus

Discrete logarithm problems

https://www.youtube.com/watch?v=cI5lkif-V1c&ab_channel=ALEXonScience

Recurrences relations, sequences, and subsequences, or difference equations

Worked examples

Let a recurrences relation $s1=3s_1=\sqrt {3}$ and sn=3+sn1s_n=\sqrt{3+\sqrt{s_{n-1}}}. Find its closed form.

Note

https://web.math.utk.edu/~cplaut/docs/analysis.pdf

https://wp.kntu.ac.ir/hrahmanei/Adv-Control-Books/Difference-Equations-Axler.pdf

http://mitran-lab.amath.unc.edu/courses/MATH564/biblio/text/02.pdf

https://oeis.org/

http://math.colga

https://people.math.aau.dk/~matarne/11-imat/notes2011a.pdfte.edu/math312/Spring1999/iterate.html

An Introduction to Difference Equations (Undergraduate Texts in Mathematics)

Introduction to Difference Equations 978-0486650845

https://www.cimt.org.uk/projects/mepres/alevel/discrete_ch14.pdf

https://www.rand.org/content/dam/rand/pubs/reports/2006/R374.pdf

https://people.math.umass.edu/~lr7q/ps_files/teaching/math456/Chapter3.pdf

Summations and products

You find sums everywhere, so we need tools to make them easier.

How do you denote the sum of nn integers? You can write it as 1+2+3+...+(n1)+n1+2+3+...+(n-1)+n where  tell you a pattern, but a more explicit and compact notation is k=1nak\sum_{k=1}^n a_k that means “sum over k k, from 1 to nn”. When you want to sum have predicates (conditions) you write a general form P(k)ak\sum \limits_{P(k)} a_k or kSf(s)\sum \limits_{k \in S} f(s) , they allow you change boundaries easily.

We introduce you to some properties below where cc is a constant and the sum is finite.

P(k)cak=cP(k)ak\sum_{P(k)} ca_k = c \sum_{P(k)} a_k

P(k)(ak+bk)=P(k)ak+P(k)bk\sum_{P(k)} (a_k+b_k) = \sum_{P(k)} a_k+\sum_{P(k)} b_k

Worked examples

Geometric series.

k=0n(2)j=(2)n+113\sum_{k=0}^n(-2)^j= \dfrac{(-2)^{n+1}-1}{-3}

If S={1,3,5,7}S=\{1,3,5,7\}, then

jSj=i=1S(2i1)\sum_{j\in S}j= \sum_{i=1}^{|S|} (2i-1)

jSj2=i=1S(2i1)2\sum_{j\in S}j^2= \sum_{i=1}^{|S|} (2i-1)^2

jS1/j=i=1S1/(2i1)\sum_{j\in S}1/j= \sum_{i=1}^{|S|} 1/(2i-1)

jS1=i=1S1\sum_{j\in S} 1= \sum_{i=1}^{|S|} 1

Worked example.

Asymptotics

Big Oh of something is a quantity, It’s part of the name of a relation. It is the relation between mathematical functions, it doesn’t tell anything about algorithm performance itself.

f ~ g iff limn=f(n)g(n)=1lim_{n\to\infty}=\dfrac{f(n)}{g(n)}=1 roughly f = g, f is asymptotically equal g

f = o(g(n)) iff limn=f(n)g(n)=0lim_{n\to\infty}=\dfrac{f(n)}{g(n)}=0 roughly f < g, f is asymptotically smaller than g.

g = O(g(n)) iff limsupn=f(n)g(n)<limsup_{n\to\infty}=\dfrac{f(n)}{g(n)}<\infty roughly f ≤ g, f is asymptotically order of growth g.

If you want to say something as f is at least O(n2)O(n^2) —a blunder, instead you must say n2=O(f)n^2=O(f), f=Ω(n2)f=\Omega(n^2), or n2=o(f)n^2=o(f).

Explanation.

Lemma.

If f=o(g) or f ~ g, then f=O(g)

If I'm lim=0 or lim=1 implies lim<lim < \infty ,

But why limsuplimsup? Some f(n)/g(n)f(n)/g(n) has no limit, but we can get a greater value.

Useful lemmas are ln(x)=o(xϵ)ln(x)=o(x^{\epsilon}), ϵ>0\epsilon>0 and xc=o(ax)x^c=o(a^x) for a>1a>1 and cRc\in R.

Worked example

Sort all the functions below in increasing order of asymptotic (big-O) growth. If some have the same asymptotic growth, then be sure to indicate that. As usual, lg means base 2.

  1. 5n5n
  1. 4lgn4 \lg n
  1. 4lglgn4 \lg \lg n
  1. n4n^4
  1. n1/2(lgn)4n^{1/2} (\lg n)^4
  1. (lgn)5lgn(\lg n)^{5 \lg n}
  1. nlgnn^{\lg n}
  1. 5n5^n
  1. 4n44^{n^4}
  1. 55n5^{5^n}
  1. 55n5^{5n}
  1. nn1/5n^{n^{1/5}}
  1. nn/4n^{n/4}
  1. (n/4)n/4(n/4)^{n/4}

Graph theory

https://arxiv.org/pdf/2312.11543.pdf

💡
A graph G is a par if sets (V,E) where V is called vertices (or nodes) and a set E of edges (or arcs) such that each edge eEe\in E is associated with a pair of vertices.

Definiciones

Grafo o red -Graph-

G=(V,E)G = (V, E), donde V son los vértices y E las aristas.

Loop

Una arista conectada a un vértice a sí misma.

Directed

Walk

Cycle

Circuit

Open walk

Closed walk

Definiciones

ConceptoDef.EjemploRepresentaciónObservaciones
Graph, NetworkG = (V, E), donde V son los vertices y E las aristas.
LoopUna arista conectada a un vertice a si mismo.
DirectedCada arista tiene una direccion.
WalkUna sequencia v0v1v2...v_0v_1v_2...
Cycle
Circuit
Open walkWalk donde el primer y el ultimo vertice son distintos.
Closed walkWalk donde el primer y el ultimo vertice son iguales.
TrailUn walk abierto con distintas aristas.
PathUn walk abierto con distintos vertices y aristas.
Todos los path son trials.
Euler TrailUn trial que incluye todas las aristas del grafo, esto es, en el trial cada arista aparece exactamente una sola vez.
ConnectedUn grafo donde existe un path entre cualquier par de de vertices.
TourClosed Walk que incluye todos las aristas al menos una vez.
Euler Tour o Eulerian CircuitTour donde cada arista es incluida una unica vez. Asi, es un Euler Trial cerrado.
Otra def:
Un tour de Euler de un grafo dirigido fuertemente conectado G = (V, E) es un ciclo que atraviesa cada arista de G exactamente una vez, aunque podría visitar los vértices en más de una ocasión.
EulerianEulerian es un grafo que tiene un Euler Tour
ComponentUn maximo conectado subgrafo.
TreeUn conectado subgrafo.
Free treeUn arbol con ninguna raiz.
DAGGrafo aciclico dirigido.
Eulerian -Tour de Euler, ciclo euleriano, camino de Euler- Un tour de Euler de un grafo dirigido fuertemente conectado G = (V, E) es un ciclo que atraviesa cada arista de G exactamente una vez, aunque podría visitar los vértices en más de una ocasión.
HamiltonianGrafo con un ciclo visitando cada vertice una vez.
Cut -corte-Conjunto de vertices donde cada remoción incrementa el numero de componentes.
Cut-setEl minimo corte.
Cut-edgeEl tamano de un corte.
k-ConnectedUn grafo conectado con la remoción de k-1 vertices.
k-ToughSV,S\forall S\subseteq V,S\neq\emptyset we have kc(GS)Skc(G-S)\le|S|
k-RegularUn grafo donde todos los vertices tienen grado k.
k-FactorUn k-regular esparza un subgrafo.
MatchingUn conjunto de aristas, no pares que no tienen adjuntos.
CliqueUn conjunto de vertices que son todos adjuntos.
Ind. setUn conjunto de vertices donde ninguno es adjunto.
Vertex coverUn conjunto de vertices el cual cubre todos las aristas.
Planar graphUn grafo el cual esta embebido en un plano.
Plane graphEl embemiento de un planar graph.
OrderNumero de vertices en el grafo.
SizeNumero de aristas en el grafo.

Notación

EspañolRep. matemáticaEjemplo
Grafo o redGG
Nodo o vértice -vertex-v,uv,u
Conjunto de aristas, arcos o enlace -edge-E(G)E(G), G.EG.E
Conjunto de vérticesV(G)V(G), G.VG.V
Cantidad de componentesc(G)c(G)
Subgrafo inducidoG[S]G[S]
Grado de un vérticedeg(v)deg(v)
Máximo grado del grafoΔ(G)\Delta(G)
Menor grado del grafoδ(G)\delta(G)
Número cromático

X(G)X(G)
Número cromático de aristas

XE(G)X_E(G)
Complemento del grafoGCG^C
Grafo completoKnK_n
Grafo completo bipartitoKn,n2K_{n,n_2}
Número de Ramseyr(k,l)r(k,l)
Grado de entradaindegree(v)in-degree(v)
Grado de salidaoutdegree(v)out-degree(v)

References

https://arxiv.org/pdf/2312.11543.pdf

http://www.uop.edu.pk/ocontents/Euler Tours.pdf

https://d3gt.com/unit.html

If you want to represent a graph use Graphviz and its dot language.

Para representar grafos usa Graphviz y su dot languaje, una version online esta disponible o https://edotor.net/

Frank Harary. Graph Theory. Addison-Wesley, 1969.

Gross, J. L., & Yellen, J. (2003). Handbook of graph theory. CRC press.

Operator precedence

(),¬,,,    ,    (),\lnot, \land, \lor, \implies,\iff

Operator precedence is about associations, no evaluations. You can evaluate how you want, but following operator precedence. When operators have the same precedence, you must associate left to right. Instead, in some languages such as SQL the expression evaluation is unpredictable.

Example:

What do you think about the below sentence? Will be either i=1 or i=0?

let i  = 0;
i == 0 || ((i = Math.sqrt(i+1)) == 1 && ++i == 1);
// What will be i's value, i = 0 or i = 1?

Even though &&, (), Math.sqrt() have higher precedence, ii will be 0 since JavaScript evaluates the left-hand side first and because T || x = T, it doesn’t evaluate the right-hand side.

$$ fafa $$