Discrete Math - Definitions Flashcards
contrapositive
of a conditional proposition p -> q is (~q) -> (~p)
Every polynomial that is not continuous has at most one zero.
converse
Switching the hypothesis and conclusion of a conditional statement. If Q then P
Every continuous polynomial as at least two zeroes.
inverse
p → q is the proposition ∼ p →∼ q
negation
There exists some polynomial with at least two zeroes that is not continuous.
constructive proof
An existential proof is constructive if it explicitly produces the desired ob- ject (or gives an algorithm to produce it).
floor
The floor of real number x is the largest integer n with n ≤ x.
odd
A number x is odd if there is an integer n with x=2n+1.
irreducible
A number is irreducible if it cannot be factored into two nonunits.
cardinal number
A cardinal number measures the size of some set.
ordinal number
An ordinal number measures sequential position, as compared to ‘first’.
binary relation
A binary relation on A,B is a subset of A×B.
union
The union of two sets is the set containing all the elements in either or both sets.
injective
A function is injective if every pair of distinct elements in the domain get mapped to distinct elements of the codomain.
Modus Tollens
A rule of deduction that concludes ∼ p from hypotheses p → q and ∼ q
Syntax
A set of artificial rules about arrangements of otherwise meaningless symbols
Semantics
The interpretation of symbols to derive meaning about other things
tautology
A compound proposition that is true for every possible combination of truth values of its components
symmetric difference
the set of elements which are in either of the sets and not in their intersection
A∆B for sets A, B is (A−B)∪(B−A) or (A∪B)−(A∩B)
power set
set S is the set consisting of all the subsets of S (including the empty subset)
union
A ∪ B for sets A, B is the set {x : x ∈ A or x ∈ B}
valid
An argument/proof is valid if the conclusion must be true if all the premises are true
vacuous proof
It proves the implication p->q by proving that ~p holds
proof by contradiction
Takes as additional hypothesis the negation of the desired conclusion, and derives a contradiction
proposition
A statement that must be true or false but not both or neither
predicate
A collection of propositions indexed by one or more variables. A predicate is not a proposition, because it may be trie for certain values of its variable(s) and false for others
GCD
Greatest Common Divisor - of integers a,b, not both zero, is the largest integer that divides each of them
Union
With regards to two sets A,B it is the set that consists of those elements in A,B, or both.
Maximal
A poset element “a” is if only there isn’t some different poset element “b” with a
codomain
It is the set of a function in which it takes its values. Alternatively, it is the second set of the direct product, from which the function relation is drawn
bijection
Only if a function is both one-to-one and onto.
counterexample
An example which disproves a proposition
subset
a set of which all the elements are contained in another set.
power set
The set of all the subsets of a set
Equivalence relation
the relation that holds between two elements if and only if they are members of the same cell within a set that has been partitioned into cells such that every element of the set is a member of one and only one cell of the partition
partial order
a set if it has: 1. Reflexivity 2. Antisymmetry 3. Transitivity: and implies
floor
the largest integer not greater than x
ceiling
the smallest integer not less than x
least upper bound
Let S be a nonempty set of real numbers that has an upper bound. Then a number c is called the least upper bound (or the supremum, denoted supS) for S iff it satisfies the following properties:
- c>=x for all x in S.
- For all real numbers k, if k is an upper bound for S, then k>=c.
event
any subset of a sample space
graph
a diagram showing the relation between variable quantities, typically of two variables, each measured along one of a pair of axes at right angles.
tree
an undirected graph if each pair of distinct vertices has exactly one path between them
modus ponens
If each of F and F=>G is either an axiom or a theorem formally deduced from axioms by application of inference rules, then G is also a formal theorem
absolute complement
When all sets under consideration are considered to be subsets of a given set U, the absolute complement of A is the set of all elements in U but not in A
Ac ={x∈U|x̸∈A}.
Total Order
a set plus a relation on the set (called a total order) that satisfies the conditions for a partial order plus an additional condition known as the comparability condition
If every pair of elements of A are comparable
function
a relation between a set of inputs and a set of permissible outputs with the property that each input is related to exactly one output.
pigeonhole principle
if n pigeons fly into k holes with n > k then some of the pigeonholes contain at least two pigeons
Eulerian path
A path that contains all edges of a graph G
starts and ends at different vertices
Euler circuit
A path that is also a circuit which contains all edges of a graph G
starts and ends at the same vertex
Hamiltonian path
if it visits every vertex of the graph exactly once
Hamiltonian circuit
A circuit that visits every vertex exactly once except for the last vertex which duplicates the first one
countable
(of a set) having a finite number of elements.
(of a set) having elements that form a one-to-one correspondence with the natural numbers; denumerable; enumerable.
