Shared Flashcard Set

Details

CSc 245 (McCann) - Final Exam Definitions
CSc 245 - Introduction to Discrete Structures - McCann
119
Computer Science
Undergraduate 2
05/06/2010
Click here to study/print these flashcards.

Create your own flash cards! Sign up here.

Additional Computer Science Flashcards

 

 

Cards

Term
Discrete Mathematics
 Definition
____ encompasses the representation and study of collections of distinct objects.
Term
Philosophical Logic
 Definition
____ is the classical notion of ‘logic:’ The study of thought and reasoning.
Term
Mathematical Logic
 Definition
____ is the use of formal languages and grammars to represent the syntax and semantics
of computation.
Term
Well-Formed Formula (wff)
 Definition
A ____ is a correctly structured expression of a language.
Term
Proposition (a.k.a. Statement )
 Definition
A ____ is a claim that is either true or false with respect to an associated
context.
Term
Simple Proposition
 Definition
A ____ is a proposition that contains no logical operators.
Term
Compound Proposition
 Definition
A claim that is a combination of multiple propositions is a ____.
Term
(Logically) Equivalent
 Definition
Two propositions p and q are ____ (p ≡ q) when both evaluate to the same result when
presented with the same input.

Alternate Definition:
p and q are ____, written p ≡ q, if p ↔ q is a tautology.
Term
Tautology
 Definition
A ____ is a proposition that always evaluates to true.
Term
Contradiction
 Definition
A ____ is a proposition that always evaluates to false.
Term
Contingency
 Definition
A ____ is a proposition that is neither a tautology nor a contradiction.
Term
Inverse
 Definition
The ____ of p → q is !p → !q.
Term
Converse
 Definition
The ____ of p → q is q → p.
Term
Contraposition
 Definition
The ____ of p → q is !q → !p.
Term
Predicate (a.k.a. Propositional Function)
 Definition
A statement that includes one or more variables and will evaluate to either true or false when the variables
are assigned values is a ____.
Term
Domain of Discourse (a.k.a. Universe of Discourse)
 Definition
The collection of values from which a variable’s value is drawn is known as the ____.
Term
Bound
 Definition
A quantified variable in a predicate is a ____ variable.
Term
Free (a.k.a. Unbound)
 Definition
Unquantified variables are ____ variables.
Term
Argument
 Definition
“An ____ is a connected series of statements to establish a definite proposition.” [Thanks to Monty
Python!]
Term
Inductive Argument
 Definition
An argument that moves from specific observations to a general conclusion is an ____.
Term
Deductive Argument
 Definition
An argument that uses accepted general principles to explain a specific situation is a ____.
Term
Valid [Argument]
 Definition
Any deductive argument of the form (p1 ∧ p2 ∧ . . . ∧ pn) → q is ____ if the conclusion must follow from
the hypotheses.
Term
Sound [Argument]
 Definition
A valid argument that also has true premises is a ____ argument.
Term
Specious Reasoning
 Definition
Any unsupported or improperly constructed argument demonstrates ____.
Term
Fallacy
 Definition
A ____ is an argument constructed with an improper inference.
Term
Conjecture
 Definition
A ____ is a statement with an unknown truth value.
Term
Theorem
 Definition
A ____ is a conjecture that has been shown to be true.
Term
Proof
 Definition
A sound argument that establishes the truth of a theorem is a____.
Term
Lemma
 Definition
A ____ is a simple theorem whose truth is used to construct more complex theorems.
Term
Corollary
 Definition
A ____ is a theorem whose truth follows directly from another theorem.
Term
Horn Clause
 Definition
A ____ is a disjunction of predicates in which at most one of the predicates is not negated.
Term
Set
 Definition
A ____ is an unordered collection of unique objects.
Term
Subset
 Definition
Set A is a ____ of set B (written A ⊆ B) if every member of A can be found in B.
Term
Proper Subset
 Definition
A is a ____ of B (written A ⊂ B) if A ⊆ B and A != B.
Term
Power Set
 Definition
The ____ of a set A (written P(A)) is the set of all of A’s subsets, including the empty set.
Term
Disjoint
 Definition
Two sets are ____ if their intersection is ∅.
Term
Partition
 Definition
A ____ of a set separates its members into disjoint subsets.
Term
Ordered Pair
 Definition
An ____ is a group of two items (a, b) such that (a, b) != (b, a) unless a = b.
Term
Cartesian Product
 Definition
The ____ (symbol: ×) of two sets A and B is the set of all ordered pairs (a, b) such that
a ∈ A and b ∈ B.
Term
Matrix
 Definition
A ____ is an n-dimensional collection of values.
Term
Square [Matrices]
 Definition
Matrices in which the # of rows equal the # of columns are called ____ matrices.
Term
Equal [Matrices]
 Definition
Two matrices A and B are ____ if they share the same dimensions and each pair of corresponding elements is equal.
Term
Transposition
 Definition
The ____ of an m× n matrix A is an n ×m matrix denoted AT in which the rows and columns have been exchanged.
Term
Symmetric
 Definition

The transposition of a matrix is denoted AT.

A matrix A is ____ if A = AT
Term
Matrix Product
 Definition
The ____ of an m×n matrix A and an n×o matrix B is an m×o matrix C = A·B in which cij is equal to the sum of (aik · bkj) from k = 1 to n
Term
Identity Matrix
 Definition
The ____, denoted In, is an n×n matrix populated with ones down the main diagonal (upperleft
to lower-right) and zeros elsewhere.
Term
n-th Power [Matrices]
 Definition
The ____ of a square matrix A, denoted An, is the result of n − 1 successive matrix products of A.
Term
r-th Boolean Power [Matrices]
 Definition
The ____ of an n × n 0-1 matrix A, denoted A[r], is the n × n matrix resulting from A ⊙ A ⊙ . . . ⊙ A, consisting of r A’s and r − 1 boolean products. A[0] = In.
Term
(Binary) Relation
 Definition
A ____ from set X to set Y is a subset of the Cartesian Product of the domain X and the
codomain Y .
Term
Reflexive
 Definition
A relation R on set A is ____ if (a, a) ∈ R, ∀a ∈ A.
Term
Symmetric
 Definition
A relation R on set A is ____ if (a, b) ∈ R whenever (b, a) ∈ R for a, b ∈ A.
Term
Antisymmetric
 Definition
A relation R on set A is ____ if (x, y) ∈ R and x != y, then (y, x) !∈ R, ∀x, y ∈ A.
Term
Transitive
 Definition
A relation R on set A is ____ if whenever (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R, for a, b, c ∈ A.
Term
Inverse
 Definition
The ____ of a relation R, denoted R−1, contains all of the ordered pairs of R with their components
exchanged. (That is, R−1 = {(b, a) | (a, b) ∈ R}.)
Term
Composite
 Definition
Let G be a relation from set A to set B, and let F be a relation from B to set C. The ____ of F and G, denoted F ◦ G, is the relation of ordered pairs (a, c), a ∈ A, c ∈ C, such that b ∈ B, (a, b) ∈ G,
and (b, c) ∈ F.
Term
(Reflexive/Weak) Partial Order
 Definition
A relation R on set A is a ____ if it is reflexive, antisymmetric, and transitive.
Term
Irreflexive
 Definition

A relation R on set A is ____ if for all members of A,

(a, a) !∈ R.
Term
Irreflexive (or Strict) Partial Order
 Definition
A relation R on set A is an ____ if it is irreflexive, antisymmetric, and
transitive.
Term
Equivalence Relation
 Definition
A relation R on set A is an ____ if it is reflexive, symmetric, and transitive.
Term
Equivalence Class
 Definition
The ____, denoted [b], of an element b ∈ B and an equivalence relation R on B is {c ∈ B | (b, c) ∈ R}. That is, the ____ is the set of all elements of the base relation equivalent to a given element as defined by the relation.
Term
Comparable
 Definition
Let R be a partial order on set A. a and b are said to be ____ if a, b ∈ A and either a  b or b  a
(that is, (a, b) ∈ R or (b, a) ∈ R).
Term
Total Order
 Definition
A partially-ordered relation R on set A is a ____ if every pair of elements a, b ∈ A are comparable.
Term
Function
 Definition
A ____ from set X to set Y , denoted f : X → Y , is a relation from X to Y . If (x, y) ∈ f, then y is
the only value returned from f(x). Further, f(x) is defined ∀x ∈ X.
Term
Domain
 Definition
For each of the following, let f : X → Y be a function, and assume f(n) = p.
– X is the ____ of f.
Term
Codomain
 Definition
For each of the following, let f : X → Y be a function, and assume f(n) = p.
– Y is the ____ of f.
Term
Maps
 Definition
For each of the following, let f : X → Y be a function, and assume f(n) = p.
– f ____ X to Y.
Term
Image
 Definition
For each of the following, let f : X → Y be a function, and assume f(n) = p.
– p is the ____ of n.
Term
Pre-Image
 Definition
For each of the following, let f : X → Y be a function, and assume f(n) = p.
– n is the ____ of p.
Term
Range
 Definition
For each of the following, let f : X → Y be a function, and assume f(n) = p. – The ____ of f is the set of all images of elements of X.
Term
Injective (a.k.a. one-to-one)
 Definition
A function f : X → Y is ____ if, for each y ∈ Y , f(x) = y for at most one
member of X.
Term
Surjective (a.k.a. onto)
 Definition
A function f : X → Y is ____ if f’s range is Y (the range = the codomain).
Term
Bijective Function (a.k.a. a one-to-one correspondence)
 Definition
A ____ is both injective and surjective.
Term
Inverse
 Definition
The ____ of a bijective function f, denoted f−1, is the relation {(y, x) | (x, y) ∈ f}.
Term
Composition
 Definition
Let f : Y → Z and g : X → Y . The ____ of f and g, denoted f ◦ g, is the function h = f(g(x)),
where h : X → Z.
Term
Binary
 Definition
A function f : X × Y → Z (or f(x, y) = z) is a ____ function.
Term
Factor
 Definition
Let i and j be positive integers. j is a ____ of i when i%j = 0.
Term
Prime
 Definition
A positive integer p is ____ if p ≥ 2 and the only factors of p are 1 and p.
Term
Composite
 Definition
A positive integer p is ____ if p ≥ 2 and p is not prime.
Term
Greatest Common Divisor (GCD)
 Definition
Let x and y be integers such that x != 0 and y != 0. The ____ of x and y is the largest integer i such that i | x and i | y.
Term
Relatively Prime
 Definition
If the GCD of a and b is 1, then a and b are ____.
Term
Pairwise Relatively Prime
 Definition
When the members of a set of integers are all relatively prime to one another, they are ____.
Term
Least Common Multiple (LCM)
 Definition
Let x and y be positive integers. The ____ of x and y is the smallest integer s such that x | s and y | s.
Term
Congruent Modulo
 Definition
If a, b ∈ Z and m ∈ Z+, then a and b are ____ m (written a ≡ b (mod m)) iff a%m = b%m
(or, iff m| (a − b)). (This is just a different phrasing of the definition given in Topic 1. Either is
acceptable.)
Term
Congruence Class
 Definition
If a, b ∈ Z and m ∈ Z+, then a and b are congruent modulo m (written a ≡ b (mod m)) iff a%m = b%m
(or, iff m| (a − b)). (This is just a different phrasing of the definition given in Topic 1. Either is
acceptable.)
– a and b are said to be members of the same ____.
Term
Sequence
 Definition
A ____ is the ordered range of a function from a set of integers to a set S.
Term
Arithmetic Sequence (a.k.a. arithmetic progression)
 Definition
In an ____ a, an+1−an is constant. This constant is called
the common difference of the sequence.
Term
Common Difference
 Definition
In an arithmetic sequence (a.k.a. arithmetic progression) a, an+1−an is constant. This constant is called
the ____ of the sequence.
Term
Geometric Sequence (a.k.a. geometric progression)
 Definition
In a ____ g, (gn+1)/(gn) is constant. This constant is called the common ratio of the sequence.
Term
Common Ratio
 Definition
In a geometric sequence (a.k.a. geometric progression) g, (gn+1)/(gn) is constant. This constant is called the ____ of the sequence.
Term
Increasing (a.k.a. non-decreasing)
 Definition
An ____ sequence i is ordered such that in ≤ in+1.
Term
Strictly Increasing
 Definition
A ____ sequence i is ordered such that in < in+1.
Term
Non-Increasing (a.k.a. decreasing)
 Definition
A ____ sequence i is ordered such that in ≥ in+1.
Term
Strictly Decreasing
 Definition
A ____ sequence sequence i is ordered such that in > in+1.
Term
Subsequence
 Definition
Sequence x is a ____ of sequence y when the elements of x are found within y in the same relative
order.
Term
String
 Definition
A ____ is a contiguous finite sequence of zero or more elements drawn from a set called the alphabet.
Term
Finite
 Definition
A set is ____ if there exists a bijective mapping between it and a set of cardinality n, n ∈ Z.
Term
Countably Infinite (a.k.a. denumerably infinite)
 Definition
A set is ____ if the bijective mapping is to either of the sets
Z or Z+.
Term
Countable
 Definition
A set is ____ if it is either finite or countably infinite.
Term
Uncountable
 Definition
A set is countable if it is either finite or countably infinite. If neither, the set is ____.
Term
First Principle of Mathematical Induction
 Definition
The ____: if (i) P(a) is true for the starting point a ∈ Z+, and (ii)
if P(k) is true for any k∈Z+, then P(k+1) is true, then P(n) is true for all n ∈ Z+, n ≥ a.
Term
Second Principle of Mathematical Induction
 Definition
The ____: if (i) P(a) is true for the starting point a ∈ Z+, and
(ii) (for any k ∈ Z+) if P(j) is true for any j ∈ Z+ such that a ≤ j ≤ k, then P(k+1) is true, then P(n)
is true for all n ∈ Z+, n ≥ a.
Term
(Generalized) Pigeonhole Principle
 Definition
I provided two definitions of the ____; learn either one:
(a) if n items are placed in k boxes, then at least one box contains at least ⌈n
k ⌉ items.
(b) Let f : X → Y , where |X| = n and |Y | = k, and let m = ⌈n
k ⌉. There are at least m values
(a1, a2, . . . , am) such that f(a1) = f(a2) = . . . = f(am).
Term
Multiplication Principle (a.k.a. the Product Rule)
 Definition
The ____: If there are s steps in an activity, with n1 ways
of accomplishing the first step, n2 of accomplishing the second, etc., and ns ways of accomplishing the
last step, then there are n1 · n2 · . . . · ns ways to complete all s steps.
Term
Addition Principle (a.k.a. the Sum Rule)
 Definition
The ____: If there are t tasks, with n1 ways of accomplishing the first, n2 ways of accomplishing the second, etc., and nt ways of accomplishing the last, then there are n1 + n2 + . . . + nt ways to complete one of these tasks, assuming that no two tasks interfere with one another.
Term
Principle of Inclusion-Exclusion for Two Sets
 Definition
The ____ says that the cardinality of the union of sets M and
N is the sum of their individual cardinalities excluding the cardinality of their intersection. That is:
|M ∪ N| = |M| + |N| − |M ∩ N|
Term
Principle of Inclusion-Exclusion for Three Sets
 Definition
The ____ says that the cardinality of the union of sets M, N, and O is the sum of their individual cardinalities excluding the sum of the cardinalities of their pairwise intersections and including the cardinality of their intersection. That is: |M ∪ N ∪ O| = |M| + |N| + |O| − (|M ∩ N| + |M ∩ O| + |N ∩ O|) + |M ∩ N ∩ O|
Term
Permutation
 Definition
An ordering of n distinct elements is called a ____.
Term
r-Permutation
 Definition
An ordering of an r-element subset of n distinct elements is called an ____.
Term
r-Combination
 Definition
An ____ of an n-element set X is an r-element subset of X. The quantity of r-element subsets
is denoted C(n, r) or
Term
Algorithm
 Definition
An ____ is a set of instructions for performing a task.
Term
Recursive Definition
 Definition
A ___ has two (sometimes three) parts: 1. The basis clause determines how trivial cases are to be handled. 2. The inductive clause explains how complex problems are answered in terms of simpler versions of the same problem. 3. The extremal clause says that only cases covered by the basis and inductive clauses are covered by the recursive definition. That is, the extremal clause provides boundaries for the definition.
Term
Recursive Algorithm
 Definition
A ____ expresses the solution to a task in terms of a simpler case of the same problem.
Term
Factorial
 Definition
The ____ of a non-negative integer n, denoted n!, is the product of all integer values from 1 through
n, inclusive. By definition, 0! = 1.
Term
Fibonacci Sequence
 Definition
The nth term of the ____ is the sum of terms n−1 and n−2, where F(0) = 0 and F(1) = 1.
Term
Recurrence Relation
 Definition
A ____ for the sequence a0, a1, . . . is an equation that expresses term ak in terms of one or
more of its preceding sequence members, one of more of which are explicitly stated initial conditions of
the sequence.
Term
Linear Homogeneous Recurrence Relation with Constant Coefficients
 Definition

A ____ of degree (or order) k

(abbreviated: LHRRWCC of degree k) has the form

R(n) = c1R(n − 1)+ c2R(n − 2)+ . . .+ ckR(n − k),

where ci ∈ R and ck != 0.
Term
Probability
 Definition
The ____ that a specific event will occur is the ratio of the number of occurrences of interest to
the number of possible occurrences.
Term
Conditional Probability
 Definition
Let X and Y be events. The ____ of X given Y , denoted p(X|Y), is p(X\Y ) p(X [INTERSECT] Y)/p(Y).
Term
Independent
 Definition
If p(A|B) = p(A), then the events A and B are____.
Supporting users have an ad free experience!