Discrete Mathematics flashcards

These flashcards cover key terms and definitions from the discrete mathematics lecture notes to help students review and prepare for exams.

What is Discrete Mathematics?

Discrete Mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous.

Algorithm

An algorithm is a finite set of precise instructions for performing a computation or solving a problem.

Logic

Logic is the branch of mathematics that deals with formal reasoning, involving statements and their validity.

Proposition

A proposition is a declarative sentence that is either true or false, but not both.

Universal Statement

A universal statement asserts that a property holds for all elements in a set.

Conditional Statement

A conditional statement expresses a logical relationship where one statement implies another.

Existential Statement

An existential statement asserts that there exists at least one element in a set for which a property holds.

Proof

A proof is a logical argument that establishes the truth of a mathematical statement.

Proof by Induction

A proof technique that establishes the truth of a statement for all natural numbers by showing it holds for a base case and an inductive step.

Pigeonhole Principle

If more items are put into fewer containers than there are items, at least one container must contain more than one item.

Time Complexity

Time complexity is a computational complexity that describes the amount of computational time that an algorithm takes to complete as a function of the length of the input.

Space Complexity

Space complexity is the amount of memory that an algorithm requires in relation to the size of the input.

Recursion

Recursion is the process of defining a function in terms of itself, often used in programming and mathematics.

Graph

A graph is a collection of nodes (or vertices) connected by edges.

Tree

A tree is a special type of graph that is connected and acyclic.

Set

A set is a well-defined collection of distinct objects, considered as an object in its own right.

Function

A function is a relation that uniquely associates elements of one set with elements of another set.

Factorial

The factorial of a non-negative integer n, denoted n!, is the product of all positive integers up to n.

List

A list is an ordered sequence of elements that may contain duplicates.

Subsequence

A subsequence is a derived sequence that can be obtained by deleting some elements of the original sequence without changing the order of the remaining elements.

Summation

Summation is the operation of adding a sequence of numbers.

Mathematical Induction

A technique used to prove propositions for all natural numbers through a base case and the inductive step. Steps include:

1. Base Case: Show P(1) is true.
2. Inductive Hypothesis: Assume P(k) is true for some positive integer k.
3. Inductive Step: Prove P(k+1) is true, assuming P(k).

Example: Proving the sum of the first n integers (1 + 2 + \dots + n = n(n+1)/2) by showing it holds for n=1 (base case) and then assuming it holds for k to prove it for k+1.

Big-O Notation

Big-O notation is used to describe the upper bound of the time complexity of an algorithm.

O(n)

Indicates linear time complexity, meaning the time grows linearly with the input size.

O(1)

Indicates constant time complexity, meaning the time remains constant regardless of input size.

O(n^2)

Indicates quadratic time complexity, meaning the time grows proportionally to the square of the input size.

Rules of Inference

Rules of inference are established patterns of reasoning that allow us to derive new true propositions from existing true propositions. They are fundamental in constructing valid mathematical proofs.