The following are some notes taken during a lecture. Matrices: Overview Matrices are useful discrete structures that can be used in many ways. For example, they are used to: Describe certain types of functions known as linear transformations. Express which vertices of a graph are connected by edges. In Machine Learning, Data Mining, and Information […]
Cardinality of Sets
Cardinality Revisited Definition: The cardinality of a set A is equal to the cardinality of a set B, denoted |A| = |B|, if and only if there is a one-to-one correspondence (i.e., a bijection) from A to B. If there is a one-to-one function (i.e., an injection) from A to B, the cardinality of A […]
Sequences and Summations
The following are some notes taken during a lecture. Sequences: Definition Sequences are ordered lists of elements. 1, 2, 3, 5, 8 1, 3, 9, 27, 81, ……. Sequences arise throughout mathematics, computer science, and in many other disciplines, ranging from botany to music. We introduce the terminology to represent sequences and sums of the […]
Functions
The following are some notes taken during a lecture. Basic Definitions Definition: Let A and B be nonempty sets. A function f from A to B, denoted f: A → B is an assignment of each element of A to exactly one element of B. We write f(a) = b if b is the unique […]
Set Operations
The following are some notes taken during a lecture. Set Union Definition: Let A and B be sets. The union of the sets A and B, denoted by A ∪ B, is the set: Set Intersection Definition: The intersection of sets A and B, denoted by A ∩ B, is BELOW. Note if the intersection […]
Basic Structures: Sets, Functions, Sequences, Sums and Matrices
The following are some notes taken during a lecture. Sets Sets are one of the basic building blocks for the types of objects considered in discrete mathematics. Important for counting. Programming languages have set operations. Set theory is an important branch of mathematics. Many different systems of axioms have been used to develop set theory. […]
Recursive Definitions
The following are some notes taken during a lecture. Recursively Defined Functions Definition: A recursive or inductive definition of a function consists of two steps. BASIS STEP: Specify the value of the function at zero. RECURSIVE STEP: Give a rule for finding its value at an integer from its values at smaller integers. A function […]
Induction and Recursion
The following are some notes taken during a lecture. Mathematical Induction Suppose we have an infinite ladder: We can reach the first rung of the ladder. If we can reach a particular rung of the ladder, then we can reach the next rung. From (1), we can reach the first rung. Then by applying (2), […]
Logic and Proofs
The following are some notes taken during a lecture. Rules of Inference We have the two premises: “All men are mortal.” “Socrates is a man.” And the conclusion: “Socrates is mortal.” How do we get the conclusion from the premises? Rules of Inference: The Argument We can express the premises (above the line) and […]
Predicate Logic
The following are some notes taken during a lecture. Limitations of Propositional Logic If we have statements of the form: “All Purdue CS students are brilliant.” “Alice is a Purdue CS student.” Does it follow that “Alice is brilliant?” This is not easy to represent in propositional logic. We need a formalism (logic) that reasons […]
Propositional Logic
The following are some notes taken during a lecture. Propositions A proposition is a declarative sentence that is either true or false Examples: Neil Armstrong was a Purdue Alum. true Purdue Computer Science is in the Silicon Valley. false Purdue won the 2018 NCAA men’s basketball championship. false 1 + 0 = 1 true 0 […]