Index Index
acyclic graph, Item
Addition Rule, Theorem
adjacent
edges, Item
vertices, Item
Algorithm
breadth-first search, Algorithm
depth-first search, Algorithm
topological sorting, Algorithm
alphabet, Item
alphabetic order, Example
and (logical connective), Item
notation for, Item
truth table for, Figure
antisymmetric relation, Item
argument, Item
valid, Item
Test, Test
articulation vertex, Item
associativity
of logical connectives, Item
of set operations, Item
axiom, Item
axiomatic system, Item
base
case (in mathematical induction), Item
clause (inductive definition), Item
biconditional, Item
notation for, Item
truth table for, Figure
bijection, Item
binary
relation, Paragraph
search, Item
string (see binary word)
word, Item
binomial, Item
coefficient, Item
Binomial Theorem, Theorem
Boolean
polynomial, Item
breadth-first
search, Algorithm
spanning tree, Item
bridge, Item
candidate-condition notation, Subsection
Cantor’s
diagonal argument, Lemma
Theorem, Theorem
cardinality, Item
Cartesian product, Item
choose function, Item
class (for an equivalence relation), Item
representative, Item
complete set, Item
codomain (of a function), Item
coefficient
binomial, Item
multinomial, Item
combination, Item
commutativity
of logical connectives, Item
of set operations, Item
comparable, Item
complement
double, Item
of a relation, Item
of a simple graph, Item
set, Item
relative, Item
composition (of functions), Item
compound
statement, Item
conclusion (in an argument), Item
conditional, Item
construction from negation and disjunction, Item
contrapositive, Item
converse, Item
inverse, Item
notation for, Item
truth table for, Figure
conjuction, Item
notation for, Item
truth table for, Figure
conjunctive normal form, Paragraphs
connected
component of a graph, formal definition, Item
component of a graph, working definition, Item
graph, Item
vertices (in a graph), Item
connective(s), Item Definition
truth tables for, Figure
contradiction, Item
propositional calculus rules, Item
Contradiction, Law of, Item
contrapositive, Item
converse, Item
countable, Item
countably infinite, Item
counterexample, Item
cycle, Item
proper, Item
defined term, Item
definition, Item
degree (of a vertex), Item
DeMorgan’s Laws
for logical connectives, Item
for set operations, Item
depth-first
search, Algorithm
spanning tree, Item
diagonal embedding, Exercise
dictionary order, Example
direct proof, Procedure
directed graph
formal definition, Item
working definition, Item
disjoint
sets, Item
union, Item
disjunction, Item
notation for, Item
truth table for, Figure
disjunctive normal form, Item
distributivity
of logical connectives, Item
of set operations, Item
Division Rule, Theorem
domain
of a variable in a predicate statement, Item
domain (of a function), Item
double
complement, Item
negation, Item
dual order, Example
duality
of truth/falsity, Item
of universal/empty sets, Item
edge, Item
adjacent, Item
bridge, Item
connectivity, Item
incident vertex, Item
loop, Item
parallel, Item
element, Item
image under a function, Item
maximal, Item
Test, Test
maximum, Item
minimal, Item
Test, Test
minimum, Item
embedding, Item
empty
function, Item
graph, Item
relation, Item
word, Item
equality
of functions, Item
of sets, Item
test, Test
equivalence
class, Item
representative, Item
set of representatives, Item
modulo, Item
relation, Item
quotient, Item
equivalent
logical statements, Item
Test, Test
polynomials, Item
Euler circuit, Activity
Excluded Middle, Law of the, Item
exclusive or, Item
existential
quantifier, Item
extension (of a function), Item
by zero, Item
factorial, Item
finite
sequence, Item
set, Item
forest, Item
form-parameter notation, Subsection
function
bijective, Item
choose, Item
codomain, Item
composition, Item
definition
formal, Item
working, Item
domain, Item
embedding, Item
equality, Item
extension, Item
by zero, Item
graph, Item
identity, Item
image, Item
on a subset, Item
inclusion, Item
injective, Item
Test, Test
input-output rule, Item
inverse, Item
onto, Item
permutation, Item
projection, Item
restricting the codomain, Item
restriction (of the domain), Item
surjective, Item
Test, Test
undefined on domain element, Example
well-defined, Example
graph
acyclic, Item
binary search tree, Item
breadth-first
search, Algorithm
spanning tree, Item
complement, Item
connected, Item
component (formal definition), Item
component (working definition), Item
vertices, Item
cycle, Item
proper, Item
depth-first
search, Algorithm
spanning tree, Item
directed
formal definition, Item
working definition, Item
edge, Item
adjacent, Item
bridge, Item
connectivity, Item
incident vertex, Item
loop, Item
parallel, Item
empty, Item
Euler circuit, Activity
forest, Item
formal definition, Item
incident edge/vertex, Item
node, Item
of a function, Item
path, Item
trivial, Item
simple, Item
sub-, Item
trail, Item
tree, Item
vertex, Item
adjacent, Item
articulation, Item
degree, Item
incident edge, Item
isolated, Item
walk, Item
closed, Item
open, Item
weighted
formal definition, Item
working definition, Item
working definition, Item
greatest lower bound, Item
Gödel’s First Incompleteness Theorem, Theorem
idempotence
of logical connectives, Item
of set operations, Item
identity function, Item
if and only if (logical connective), Item
notation for, Item
truth table for, Figure
if … then … (logical connective), Item
notation for, Item
truth table for, Figure
image
inverse
of a set, Item
of an element, Item
of a domain element, Item
of a function, Item
of a function on a subset, Item
incident edge/vertex, Item
inclusion function, Item
inclusive or, Item
Incompleteness Theorem, Gödel’s First, Theorem
induction
hypothesis, Item
step, Item
Induction, Mathematical, Axiom
strong form, Axiom
inductive
clause, Item
definition, Item
base clause, Item
inductive clause, Item
limiting clause, Item
infinite
sequence, Item
infinite set, Item
initial node (in a binary search tree), Item
injection, Item
input-output rule (of a function), Item
integers, set of, Item
intersection
of relations, Item
of sets, Item
inverse
conditional, Item
function, Item
image
of a set, Item
of an element, Item
relation, Item
irrational number(s)
set of, Item
isolated
vertex, Item
Law
DeMorgan’s
for logical connectives, Item
for set operations, Item
of Contradiction, Item
of Syllogism, Item
of the Excluded Middle, Item
least upper bound, Item
length, of a word, Item
letters, Item
limiting clause (inductive definition), Item
logical
analysis, Item
biconditional, Item
notation for, Item
conditional, Item
notation for, Item
conjuction, Item
notation for, Item
connectives, Definition
disjunction, Item
notation for, Item
negation, Item
notation for, Item
statement(s), Item
Test, Test
substatement, Item
logically
false (see contradiction)
implies, Item
true (see tautology)
loop, Item
lower bound, Item
greatest, Item
Mathematical Induction, Axiom
strong form, Axiom
maximal element, Item
Test, Test
maximum element, Item
membership (in a set), Item
minimal element, Item
Test, Test
minimum element, Item
model (for an axiomatic system), Item
modulo, Item
modus ponens, Item
modus tollens, Theorem
standard argument, Item
multinomial
coefficient, Item
Multinomial Theorem, Theorem
Multiplication Rule, Theorem
naive set theory, Item
natural
numbers, set of, Item
projection, Item
negation, Item
double, Item
notation for, Item
truth table for, Figure
node, Item
initial (in a binary search tree), Item
terminal (in a binary search tree), Item
nonconnected graph. See connected graph
not (logical connective), Item
notation for, Item
truth table for, Figure
numbers
integers, Item
natural, Item
rational, Item
real, Item
object (informal definition), Item
onto, Item
or (logical connective), Item
notation for, Item
truth table for, Figure
order
alphabetic, Example
dictionary, Example
partial, Item
total, Item
compatible, Item
parallel edges, Item
partial order, Item
dual, Example
strict relationship, Item
total, Item
compatible, Item
partially ordered set, Item
comparable elements, Item
incomparable elements, Item
lower bound, Item
greatest, Item
maximal element, Item
Test, Test
maximum element, Item
minimal element, Item
Test, Test
minimum element, Item
topological sorting, Algorithm
upper bound, Item
least, Item
partition, Item
cell, Item
path
trivial, Item
path (in a graph), Item
permutation, Item
of size \(k\), Item
Pigeonhole Principle, Corollary
formal version, Theorem
strong form (formal version), Theorem
strong form (informal version), Corollary
power set, Item
predicate, Item
premise (in an argument), Item
prime number, Example
primitive term, Item
Principle
of Mathematical Induction, Axiom
strong form, Axiom
Pigeonhole, Corollary
formal version, Theorem
strong form (formal version), Theorem
strong form (informal version), Corollary
Procedure
direct proof, Procedure
proof by contradiction, Procedure
proof by induction, Procedure
proof by proving the contrapositive, Procedure
proof by strong induction, Procedure
proof of conditional involving disjunction, Procedure
proving a biconditional, Procedure
proving uniqueness, Procedure
reduction to cases, Procedure
procedure
disjunctive normal form, Procedure
projection
function, Item
natural (onto a quotient), Item
proof
by contradiction, Procedure
by induction, Procedure
by proving the contrapositive, Procedure
by reduction to cases, Procedure
by strong induction, Procedure
direct, Procedure
of a biconditional, Procedure
of conditional involving disjunction, Procedure
of uniqueness, Procedure
proper
cycle, Item
subset, Item
Test, Test
propositional calculus
rules of, Proposition
quantifier, Item
distribution of, Proposition
existential, Item
negation of, Proposition
universal, Item
quotient, Item
rational numbers, set of, Item
real numbers, set of, Item
recurrence relation, Item
recursively-defined sequence, Item
reduction to cases, Procedure
reflexive relation, Item
relation
partial order, Item
dual, Example
strict relationship, Item
total, Item
relation(s)
antisymmetric, Item
Test, Test
binary, Paragraph
complement of, Item
empty, Item
equivalence, Item
quotient, Item
formal definition, Item
intersection of, Item
inverse, Item
reflexive, Item
Test, Test
symmetric, Item
Test, Test
ternary, Item
transitive, Item
Test, Test
union of, Item
universal, Item
working definition, Item
relative complement, Item
restriction
of the codomain of a function, Item
of the domain of a function, Item
Rule(s)
Addition, Theorem
Division, Theorem
for Operations on Sets, Proposition
Multiplication, Theorem
of Predicate Calculus
distribution of quantifiers, Proposition
negation of quantifiers, Proposition
of Propositional Calculus, Proposition
Substitution
for equivalent statements, Theorem
into a tautology or contradiction, Theorem
into an argument, Theorem
Subtraction, Theorem
Russell’s Paradox, Example
same size (for sets), Item
sequence, Section
finite, Item
infinite, Item
recursively-defined, Item
set operations
rules for, Proposition
set(s)
alphabet, Item
cardinality, Item
Cartesian product, Item
combination, Item
countable, Item
countably infinite, Item
defining, Section
by listing, Subsection
candidate-condition notation, Subsection
form-parameter notation, Subsection
disjoint, Item
union, Item
element, Item
equality, Item
test, Test
finite, Item
infinite, Item
informal definition, Item
intersection, Item
larger, Item
Test, Test
letters, Item
membership, Item
of irrational numbers, Item
of words, Item
partially ordered, Item
comparable elements, Item
greatest lower bound, Item
incomparable elements, Item
least upper bound, Item
lower bound, Item
maximal element, Item
maximal element, Test for, Test
maximum element, Item
minimal element, Item
minimal element, Test for, Test
minimum element, Item
topological sorting, Algorithm
upper bound, Item
partition, Item
cell, Item
permutation, Item
power, Item
same size, Item
smaller, Item
Test, Test
sub-, Item
proper, Item
Test, Test
totally ordered, Item
uncountable, Item
union, Item
simple
graph, Item
statement, Item
spanning
subgraph, Item
tree, Item
square
free, Exercises
number, Exercises
statement (in logic)
compound, Item
connective, Item
truth tables for, Figure
simple, Item
sub-, Item
statement(s) (in logic), Item
equivalent, Item
Test, Test
Test, Test
strict partial order relationship, Item
subgraph, Item
spanning, Item
subset, Item
image under a function, Item
proper, Item
Test, Test
Test, Test
substatement, Item
Substitution Rule
for equivalent statements, Theorem
into a tautology or contradiction, Theorem
into an argument, Theorem
Subtraction Rule, Theorem
surjection, Item
Syllogism, Law of, Item
symmetric relation, Item
tautology, Item
propositional calculus rules, Item
term
defined, Item
primitive, Item
terminal node (in a binary search tree), Item
ternary relation, Item
Test
argument validity, Test
for equivalence of logical statements}, Test
injective function, Test
larger/smaller set, Test
maximal/minimal elements, Test
relation
antisymmetric, Test
reflexive, Test
symmetric, Test
transitive, Test
set equality, Test
statement, Test
subset, Test
proper, Test
surjective function, Test
Theorem
Binomial, Theorem
Cantor-Bernstein, Theorem
Cantor’s, Theorem
Gödel’s First Incompleteness, Theorem
Multinomial, Theorem
Trinomial, Theorem
topological sorting, Item
total order, Item
compatible, Item
totally ordered set, Item
trail (in a graph), Item
transitive relation, Item
tree, Item
binary search, Item
spanning, Item
Trinomial Theorem, Theorem
truth
table, Item
for each of the connectives, Figure
value, Item
uncountable, Item
union
of relations, Item
of sets, Item
disjoint, Item
universal
quantifier, Item
relation, Item
upper bound, Item
least, Item
