Discrete Structures Flashcards
All elements of the universal set, minus the elements of the set under consideration
Absolute Compliment
Aᶜ
The set of all possible ordered pairs between two sets
Cartesian Product
A x B
The number of elements in a set
Cardinality
| A + B |
A function from A to B that is also a function from B to A (must be both One-to-One and Onto for this to be true)
Invertible (Bijection)
A series of functions linked together where the codomain of one function is the domain of the next function
Composite Function (Composition)
Sets that have no common elements
Disjoint
An item in a set
Element
∈
A set of ordered pairs depicting all relations between the domain and codomain of a function
Graph
The output element of a function for a given input
Image
A relation between two sets in which every element of the domain is related to one element of the codomain
Function
ƒ()
The set of all possible subsets for a single set
Power Set
2ᴬ; 2ᴮ; 2ᶜ etc…
The set of elements that two or more sets have in common
Intersection
∩
A function that maps each element of the domain to only one element in the codomain
One-to-one (Injection)
A relation in which each element is related to itself
Reflexive
The set of all image values of a function
Range
A function in which every element of the codomain is mapped from an element of the domain
Onto (Surjection)
If every element of one set is also an element of a second set
Subset
⊆
A list of items that have something in common
Set
A set of ordered pairs a directed graph can illustrate
Relation
A set operation that results in a set containing the elements that remain when the second set is subtracted from the first set
Relative Complement
\
The elements that belong to set A or set B but not both
Symmetric Difference
⊕
A relation in which the first element related to the second element and the second element related to the third element implies the first element is also related to the third element
Transitive
A graphical representation of sets as enclosed areas of a plane that shows all possible relationships
Venn Diagram
The set operation that combines the elements of two or more sets
Union
∪
A relation in which the first element is related to the second and the second element is related back to the first
Symmetric
Every element of a set is in a second set but there is at least one element in the second set not in the first set.
Proper Subset
⊂
The set with no elements
Empty Set or Null Set
∅ or {}
A device that shows the truth value of a compound proposition for all combinations of input values
Truth Table
A declarative statement that is either true or false but not both
Proposition
The logical operator that results in a true output if one or the other or both propositions are true
OR
The related form that negates the hypothesis and conclusion of a conditional statement and is not logically equivalent to the original conditional statement
Inverse
The related form that reverses the order of the conditional statement and is not logically equivalent to the original conditional statement
Converse
Each proposition that makes up an argument in a proof
Premise
The logical operation that results from stating “if this then that”
Conditional
The logical operation that results in a true output if one or the other but not both propositions are true
Exclusive OR
The principle that describes a function with a finite domain graphed to a smaller finite codomain
Pigeonhole Principle
The counting rule applied to non-intersecting sets of outputs
Sum Rule
Sub propositions joined by logical connectives
Compound Proposition
The counting rule applied to intersecting sets of outputs
Product rule
The logical operation that results from stating “it is false that…”
NOT
Validation of a conclusion from an argument based on the truth of the hypothesis
Proof
A proposition that results in true for all inputs
Tautology
The related form that reverses the order of and negates the hypothesis and conclusion of the conditional statement and is logically equivalent to the original conditional statement
Contrapositive
The logical operator that results in a true output only if both propositions are true
AND
The logical operation that results from stating “this if and only if that”
Biconditional
A proposition that results in false for all inputs
Contradiction
The condition where two propositions result in identical truth tables
Logically equivalent
