Mathematical Induction
the statement ∀n P(n) is true if P(1) is true and ∀k[P(k) → P(k + 1)] is true. Cannot be used to find new theorems, or explain why a particular theorem is true.
Basis Step
the proof of P(1) in a proof by mathematical inductionof ∀nP (n)
Inductive Step
the proof of P(k) → P(k + 1) for all positiveintegers k in a proof by mathematical induction of∀nP (n)
Inductive Hypothesis
the assumption that P(k) is true
Well-ordering property
Appendix 1
Proposition
A declarative sentence (that is, a sentence that declares a fact) that is either true or false, but not both. e.g. Washington, DC is the capital of the United States of America; or 1+1=2; but NOT x + 1 = 2.
Propositional variables
aka statement variables; a variable that represents a proposition
Truth value
If it is a true proposition, denoted by T and the truth value of a proposition is false, denoted by F, if it is a false proposition
Propositional logic
The area of logic that deals with propositions
Compound propositions
New propositions that are formed from existing propositions using logical operators.
Truth table
A table with a row for each of the possible truth values of a proposition p. Each row shows the truth value of ¬p corresponding to the truth value of p for this row.
Implication
(aka material implication) A conditional statement, consisting of a hypothesis , followed by a conclusion. Often expressed as p->q. Statement only false if the hypothesis is true and the conclusion is false. If the conclusion is true, the truth of the hypothesis doesn't matter. Helpful to think of as a contractual obligation that you expect to be fulfilled. Example: If I am elected, then I will lower taxes.
Truth Value
(of a proposition) This value is true, denoted by T, if it is a true proposition, or value is false, denoted by F, if it is a false proposition.
Propositional calculus
(aka propositional logic) The area of logic that deals with propositions
Compound Propositions
New propositions that are formed from existing propositions using logical operators
Propositional Variables
(aka statement variables) variables that represent propositions, just as letters are used to denote numerical variables. By convention p,q,r,s... are used.
Inclusive or
(aka Inclusive Disjunction) True when at LEAST one of the two propositions is true.
Exclusive or
(aka Exclusive Disjunction) True when at MOST one of thetwo propositions is true.
Hypothesis
(aka antecedent or premise )The first portion of an implication
Conclusion
(aka consequence) The second portion of an implication.
Converse
the conditional statement q → p. Does NOT have the same truth value as p->q for all possible truth values of p and q. e.g. Converse of "If it is raining, then the home team wins" is "If the home team wins, then it is raining
Contrapositive
the conditional statement ¬q →¬p. Always has the same truth value as p -> q. e.g. Contrapositive of "If it is raining, then the home team wins" is "If the home team doesn't win, then it isn't raining
Inverse
the conditional statement ¬p →¬q. Does NOT have the same truth value as p->q for all possible truth values of p and q. e.g. Inverse of "If it is raining, then the home team wins" is "If it isn't raining, then the home team doesn't win
Equivalent propositions
When two compound propositions always have the same truth value, e.g. a conditional statement and its contrapositive, or it's converse and inverse.
Biconditional
The proposition "p if and only if q". Denoted p <-> q. Can also be expressed "p is necessary and sufficient for q" or "p iff q". Example: If and only if I am elected, I will lower taxes.
Tautology
A compound proposition that is always true, no matter what the truth values of the propositionalvariables that occur in it
Contradiction
A compound proposition that is alwaysfalse
Logical Order of Operations
Parens, Neg, Conj, Disj, Cond, Bicond
Product rule
...
Sum rule
...
Boolean variable
A variable that is either true or false. Can be represented using a bit.
Bit
A symbol with two possible values, namely 0 and 1. Can be used to represent a truth value, customarily 1= T and 0 = F.
Bit operations
An operation on a bit or bits. Correspond to logical connectives, i.e. OR=∨, AND=∧, and XOR=⊕
Negation
The proposition with truth value opposite to the truth value of p. Read "not p". In English, "It is not the case that p
Logical operators
operators used to combine propositions
Disjunction
the proposition "p or q," which is false when both p and q are false and is true otherwise
Conjunction
the proposition "p and q," which is true if and only if both p and q are true, and is false otherwise.
Exclusive Or
the proposition "p XOR q," which is true when exactly one of p and q is true, but not both. E.g. this entree comes with a choice of soup or salad. Denoted by p ⊕ q
Bit string
a list of bits
Bitwise operations
operations on bit strings that operate on each bit in one string and the corresponding bit in the other string
Logic gate
a logic element that performs a logical operationon one or more bits to produce an output bit
Logic circuit
a switching circuit made up of logic gates thatproduces one or more output bits
Contingency
a compound proposition that is sometimes trueand sometimes false
Consistent Compound Propositions
compound propositions for which there is an assignment of truth values to the variables that makes all these propositions true
satisfiable compound proposition
a compound proposition for which there is an assignment of truth values to its variables that makes it true
logically equivalent compound propositions
compound propositions that always have the same truth values
predicate
part of a sentence that attributes a property to thesubject
propositional function
a statement containing one or more variables that becomes a proposition when each of its variablesis assigned a value or is bound by a quantifier
domain of discourse
the values a variable in a propositional function may take
existential quantification
the proposition ∃x P(x) that is true if and only if there exists an x in the domain such that P(x) is true
universal quantification
the proposition ∀xP(x) that is true if and only if P(x) is true for every x in the domain
logically equivalent expressions
expressions that have the same truth value no matter which propositional functions and domains are used
free variable
a variable not bound in a propositional function
bound variable
a variable that is quantified
scope of a quantifier
portion of a statement where the quantifier binds its variable
argument
a sequence of statements
argument form
a sequence of compound propositions involvingpropositional variables
premise
a statement, in an argument, or argument form, otherthan the final one
conclusion
the final statement in an argument or argumentform
valid argument form
a sequence of compound propositionsinvolving propositional variables where the truth of all thepremises implies the truth of the conclusion
valid argument
an argument with a valid argument form
rule of inference
a valid argument form that can be used inthe demonstration that arguments are valid
fallacy
an invalid argument form often used incorrectly as arule of inference (or sometimes, more generally, an incorrect argument)
circular reasoning
(aka begging the question) reasoning where one or more steps are based on the truth of the statementbeing proved
theorem
a mathematical assertion that can be shown to betrue
conjecture
a mathematical assertion proposed to be true, butthat has not been proved
proof
a demonstration that a theorem is true
axiom
a statement that is assumed to be true and that can beused as a basis for proving theorems
lemma
a theorem used to prove other theorems
corollary
a proposition that can be proved as a consequenceof a theorem that has just been proved
vacuous proof
a proof that p → q is true based on the factthat p is false
trivial proof
a proof that p → q is true based on the fact thatq is true
direct proof
a proof that p → q is true that proceeds by showingthat q must be true when p is true
proof by contraposition
a proof that p → q is true that proceedsby showing that p must be false when q is false
proof by contradiction
a proof that p is true based on thetruth of the conditional statement ¬p → q, where q is acontradiction
exhaustive proof
a proof that establishes a result by checkinga list of all possible cases
proof by cases
a proof broken into separate cases, where thesecases cover all possibilities
without loss of generality
an assumption in a proof thatmakesit possible to prove a theorem by reducing the number ofcases to consider in the proof
counterexample
an element x such that P(x) is false
constructive existence proof
a proof that an element with a specified property exists that explicitly finds such an element
nonconstructive existence proof
a proof that an element with a specified property exists that does not explicitly find such an element
rational number
a number that can be expressed as the ratio of two integers p and q such that q = 0
uniqueness proof
a proof that there is exactly one element satisfying a specified property
Alphabet
A finite, nonempty set of objects called symbols
Argument (of a function)
An input to a function
Binary Relation
A relation whose domain is a set of pairs
Boolean operation
An operation on Boolean values
Boolean value
The values TRUE or FALSE, often represented by 1 or 0
Cartesian product
An operation on sets forming a set of all tuples of elements from respective sets
Complement
An operation on a set, forming the set of all elements not present
Concatenation
An operation that joins strings together
Connected graph
Boolean AND operation
Cycle
A path that starts and ends in the same node
Directed graph
A collection of points and arrows connecting some pairs of points
Domain
The set of possible inputs to a function
Edge
A line in a graph
Element
An object in a set
Empty set
The set with no members
Empty string
The string of length zero
Equivalence relation
A binary relation that is reflexive, symmetric, and transitive
Function
An operation that translates inputs into outputs
Graph
A collection of points and lines connecting some pairs of points
Intersection
An operation on sets forming the set of common elements
k-tuple
A list of k objects
Language
A set of strings
Member
An object in a set
Node
A point in a graph
Ordered pair
A list of two elements
Path
A sequence of nodes in a graph connected by edges
Property
A predicate
Range
The set from which outputs of a function are drawn
Relation
A predicate, most typically when the domain is a set of k-tuples
Sequence
A list of objects
Set
A group of objects
Simple path
A path without repetition
Singleton set
A set with one member
String
A finite list of symbols from an alphabet
Symbol
A member of an alphabet
Tree
A connected graph without simple cycles
Union
An operation on sets combining all elements into a single set
Unordered pair
A set with two members
Vertex
A point in a graph
cardinality
two sets A and B have the same cardinality ifthere is a one-to-one correspondence from A to B
countable set
a set that either is finite or can be placed inone-to-one correspondence with the set of positive integers
uncountable set
a set that is not countable
ℵ0 (aleph null)
the cardinality of a countable set
c
the cardinality of the set of real numbers
Cantor diagonalization argument
a proof technique used toshow that the set of real numbers is uncountable
computable function
a function for which there is a computerprogram in some programming language that finds itsvalues
uncomputable function
a function for which no computerprogram in a programming language exists that finds itsvalues
continuum hypothesis
the statement there no set A existssuch that ℵ0 < |A| < c
matrix
a rectangular array of numbers
matrix addition
see page 178
matrix multiplication
see page 179
In (identity matrix of order n)
the n × n matrix that hasentries equal to 1 on its diagonal and 0s elsewhere
At (transpose of A)
the matrix obtained fromAby interchangingthe rows and columns
symmetric matrix
a matrix is symmetric if it equals its transpose
zero-one matrix
matrix with each entry equal to either 0 or1
set
a collection of distinct objects
paradox
a logical inconsistency
element, member of a set
an object in a set
roster method
a method that describes a set by listing itselements
set builder sotation
the notation that describes a set by statinga property an element must have to be a member
∅ (empty set, null set)
the set with no members
universal set
the set containing all objects under consideration
Venn diagram
a graphical representation of a set or sets
S = T (set equality)
S and T have the same elements
S ⊆ T (S is a subset of T)
every element of S is also anelement of T
S ⊂ T (S is a proper subset of T)
S is a subset of T andS = T
finite set
a set with n elements, where n is a nonnegativeinteger
infinite set
a set that is not finite
|S| (the cardinality of S)
the number of elements in S
P(S) (the power set of S)
the set of all subsets of S
A ∪ B (the union of A and B)
the set containing those elements that are in at least one of A and B
A ∩ B (the intersection of A and B)
the set containing those elements that are in both A and B
A − B (the difference of A and B)
the set containing those elements that are in A but not in B
A' (the complement of A)
the set of elements in the universal set that are not in A
A ⊕ B (the symmetric difference of A and B)
the set containing those elements in exactly one of A and B
membership table
a table displaying the membership of elementsin sets
function from A to B
an assignment of exactly one elementof B to each element of A
domain of f
the set A, where f is a function from A to B
codomain of f
the set B, where f is a function from A to B
b is the image of a under f
b = f(a)
a is a pre-image of b under f
f(a) = b
range of f
the set of images of f
onto function, surjection
a function from A to B such that every element of B is the image of some element in A
one-to-one function, injection
a function such that the images of elements in its domain are distinct
one-to-one correspondence, bijection
a function that is both one-to-one and onto
inverse of f
the function that reverses the correspondencegiven by f (when f is a bijection)
f ◦ g (composition of f and g)
the function that assignsf (g(x)) to x
x (floor function)
the largest integer not exceeding x
x (ceiling function)
the smallest integer greater than or equal to x
partial function
an assignment to each element in a subset ofthe domain a unique element in the codomain
sequence
a function with domain that is a subset of the set ofintegers
geometric progression
a sequence of the form a, ar, ar2, . . . ,where a and r are real numbers
arithmetic progression
a sequence of the form a, a + d,a + 2d, . . . , where a and d are real numbers
string
a finite sequence
empty string
a string of length zero
recurrence relation
a equation that expresses the nth term an of a sequence in terms of one or more of the previous terms of the sequence for all integers n greater than a particularinteger
\sum_{i=1}^{n} a_{i}
the sum a_1 + a_2 + ... a_n
algorithm
a finite sequence of precise instructions for performinga computation or solving a problem
searching algorithm
the problem of locating an element in alist
linear search algorithm
a procedure for searching a list elementby element
binary search algorithm
a procedure for searching an orderedlist by successively splitting the list in half
sorting
the reordering of the elements of a list into prescribedorder
f(x) is O(g(x))
the fact that |f (x)| ≤ C|g(x)| for all x > kfor some constants C and k
witness to the relationship f (x) is O(g(x))
a pair C and ksuch that |f (x)| ≤ C|g(x)| whenever x > k
f (x) is \omega{(g(x))}
the fact that |f (x)| ≥ C|g(x)| for all x > kfor some positive constants C and k
f (x) is \theta{(g(x))}
the fact that f (x) is bothO(g(x)) and(g(x))
time complexity
the amount of time required for an algorithmto solve a problem
space complexity
the amount of space in computer memory required for an algorithm to solve a problem
worst-case time complexity
the greatest amount of time required for an algorithm to solve a problem of a given size
average-case time complexity
the average amount of time required for an algorithm to solve a problem of a given size
algorithmic paradigm
a general approach for constructingalgorithms based on a particular concept
brute force
the algorithmic paradigm based on constructingalgorithms for solving problems in a naive manner from the statement of the problem and definitions
greedy algorithm
an algorithm that makes the best choice ateach step according to some specified condition
tractable problem
a problem for which there is a worst-casepolynomial-time algorithm that solves it
intractable problem
a problem for which no worst-casepolynomial-time algorithm exists for solving it
solvable problem
a problem that can be solved by an algorithm
unsolvable problem
a problem that cannot be solved by an algorithm
linear and binary search algorithms
(given in Section 3.1). Linear = O(n) worst case, Binary = O(n log n) worst case
bubble sort
a sorting that uses passes where successive itemsare interchanged if they in the wrong order
insertion sort
a sorting that at the j th step inserts the j th elementinto the correct position in in the list, when the firstj − 1 elements of the list are already sorted
a | b (a divides b)
there is an integer c such that b = ac
a and b are congruent modulo m
m divides a − b
modular arithmetic
arithmetic done modulo an integerm ≥ 2
prime
an integer greater than 1 with exactly two positiveinteger divisors
composite
an integer greater than 1 that is not prime
Mersenne prime
a prime of the form 2p − 1, wherep is prime
gcd(a, b) (greatest common divisor of a and b)
the largest integer that divides both a and b
relatively prime integers
integers a and b such that gcd(a, b) = 1
pairwise relatively prime integers
a set of integers with the property that every pair of these integers is relatively prime
lcm(a,b)
the smallestpositive integer that is divisible by both a and b
a mod b
the remainder when the integer a is divided by thepositive integer b
a ≡ b (mod m) (a is congruent to b modulo m)
a − b is divisible by m
n = (akak−1 . . . a1a0)b
the base b representation of n
binary representation
the base 2 representation of an integer
octal representation
the base 8 representation of an integer
hexadecimal representation
the base 16 representation of an integer
linear combination of a and b with integer coefficients
an expression of the form sa + tb, where s and t are integers
Bézout coefficients of a and b
integers s and t such that the Bézout identity holds
Bézout identity
sa + tb = gcd(a, b)
inverse of a modulo m
an integer a such that aa ≡ 1 (mod m)
linear congruence
a congruence of the form ax ≡ b (mod m), where x is an integer variable
pseudoprime to the base b
a composite integer n such that bn−1 ≡ 1 (mod n)
Carmichael number
composite integer n such that n is a pseudoprime to the base b for all positive integers b with gcd(b, n) = 1
primitive root of a prime p
an integer r in Zp such that every integer not divisible by p is congruent modulo p to a power of r
discrete logarithm of a to the base r modulo p
the integer e with 0 ≤ e ≤ p − 1 such that re ≡ a (mod p)
encryption
the process of making a message secret
decryption
the process of returning a secret message to itsoriginal form
encryption key
a value that determines which of a family ofencryption functions is to be used
shift cipher
a cipher that encrypts the plaintext letter p as(p + k) mod m for an integer k
affine cipher
a cipher that encrypts the plaintext letter p as(ap + b) mod m for integers a and b with gcd(a, 26) = 1
character cipher
a cipher that encrypts characters one by one
block cipher
a cipher that encrypts blocks of characters of afixed size
cryptanalysis
the process of recovering the plaintext from ciphertextwithout knowledge of the encryption method, orwith knowledge of the encryption method, but not the key
cryptosystem
a five-tuple (P, C,K, E,D) where P is the setof plaintext messages, C is the set of ciphertext messages,K is the set of keys, E is the set of encryption functions,and D is the set of decryption functions
private key encryption
encryption where both encryption keys and decryption keys must be kept secret
public key encryption
encryption where encryption keys are public knowledge, but decryption keys are kept secret
RSA cryptosystem
the cryptosystem where P and C are both Z26, K is the set of pairs k = (n, e) where n = pq where p and q are large primes and e is a positive integer, Ek(p) = pe mod n, and Dk(c) = cd mod n where d is the inverse of e modulo (p − 1)(q − 1)
key exchange protocol
a protocol used for two parties to generate a shared key
digital signature
a method that a recipient can use to determine that the purported sender of a message actually sent the message
division algorithm
Let a and d be integers with d positive. Then there are unique integers q and r with 0 ≤ r < d such that a = dq + r.
Euclidean algorithm
for finding greatest common divisors by successively using the division algorithm (see Algorithm 1 in Section 4.3)
Bézout's theorem
If a and b are positive integers, then gcd(a, b) is a linear combination of a and b.
sieve of Eratosthenes
A procedure for finding all primes not exceeding a specified number n, described in Section 4.3
fundamental theorem of arithmetic
Every positive integer can be written uniquely as the product of primes, where the prime factors are written in order of increasing size.
Chinese remainder theorem
A system of linear congruences modulo pairwise relatively prime integers has a unique solution modulo the product of these moduli.
Fermat's little theorem
If p is prime and p | a, then ap−1 ≡ 1 (mod p).
Markov chains
...
computational model
idealized computer
finite state machine
aka finite automaton
state diagram
...
states
...
start state
...
accept state
aka final states
transitions
...
accept
...
reject
...
transition function
...
language of machine M
...
M recognizes A
aka M accepts A
regular language
...
deterministic
...
nondeterministic
...
unary alphabet
...
nondeterministic finite automaton
aka NFA
equivalence of machines
...
regular expressions
...
circular definition
...
inductive definition
...
token
...
lexical analyzer
...
generalized nondeterministic finite automaton
...
pumping lemma
...
pumping length
...
pigeonhole principle
...
negation operator
constructs a new proposition from a single existing proposition
connectives
logical operators used to form new propositions from two or more existing propositions
bitwise OR
The bitwise OR of two strings is the string obtains by taking the OR of the corresponding bits from both strings
bitwise AND
The bitwise AND of two strings is the string obtains by taking the AND of the corresponding bits from both strings
bitwise XOR
The bitwise XOR of two strings is the string obtains by taking the XOR of the corresponding bits from both strings
logic circuit
aka digital circuit; receives input signals p1, p2, . . . , pn, each a bit [either 0 (off) or 1 (on)], and produces output signals s1, s2, . . . , sn, each a bit
gates
basic logic circuits, AND, OR, and NOT
Satisfiable
A compound proposition where there's at least one assignment of truth values to its variables that makes it true
Solution
An assignment of truth values that makes a compound proposition true
Unsatisfiable
When a compound proposition is false for ALL possible assignments of truth values to its variables
Predicate logic
...
Propositional function
The statement P(X)
Uniqueness quantifier
There exists exactly one unique X such that P(x) is true
Predicate
Refers to a property that the subject of the statement can have. Also a function whose range is {TRUE, FALSE}.
Argument
A sequence of statements that end with a conclusion.
Argument
A sequence of statements that end with a conclusion
Valid
The conclusion must follow from the truth of the preceding statements
Premises
...
Validity (of an argument)
The conclusion must follow from the truth of the premises. An argument is valid if and only if it is impossible for all the premises to be true andthe conclusion to be false.
Premises (of an argument)
In the context of an argument, the statements leading to a conclusion.
Conclusion (of an argument)
The final statement of an argument
Fallacies
Common forms of incorrect reasoning, which lead to invalid arguments
Modus ponens
(p ∧ (p → q)) → q
Modus tollens
(¬q ∧ (p → q))→¬p
Hypothetical syllogism
((p → q) ∧ (q → r)) → (p → r)
Disjunctive syllogism
((p ∨ q)∧¬p) → q
Addition (rule of inference)
p → (p ∨ q)
Simplification (rule of inference)
(p ∧ q) → p
Conjunction (rule of inference)
((p) ∧ (q)) → (p ∧ q)
Resolution (rule of inference)
((p ∨ q) ∧ (¬p ∨ r)) → (q ∨ r)
De Morgan's Laws
¬(p ∧ q) ≡ ¬p ∨¬q, and ¬(p ∨ q) ≡ ¬p ∧¬q
Identity laws
p ∧ T ≡ p; p ∨ F ≡ p
Domination laws
p ∨ T ≡ T; p ∧ F ≡ F
Idempotent laws
p ∨ p ≡ p; p ∧ p ≡ p
Double negation law
¬(¬p) ≡ p
Commutative laws
p ∨ q ≡ q ∨ p; p ∧ q ≡ q ∧ p
Associative laws
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r); (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
Distributive laws
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r); p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Absorption laws
p ∨ (p ∧ q) ≡ p; p ∧ (p ∨ q) ≡ p
Negation laws
p ∨¬p ≡ T; p ∧¬p ≡ F
Affirming the consequent
a formal fallacy of inferring the converse from the original statement; In other words, treating an argument with premises p → q and q and conclusion p as a validargument form, which it is not. "If it is snowing, then it is below 32F" "It is below 32F", therefore "it is snowing
Denying the antecedent
a formal fallacy of inferring the inverse from the original statement; In other words, treating an argument with the premises p → q and ¬p and conclusion ¬q as a valid argument form, which it is not. "If it is snowing, then is it below 32F" "It is not snowing", therefore "it is not below 32F
Universal instantiation
the rule of inference used to conclude that P(c) is true, where c is a particular member of the domain, given the premise ∀xP(x). Universal instantiation is usedwhen we conclude from the statement "All women are wise" that "Lisa is wise," where Lisa is a member of the domain of all women.
Universal generalization
the rule of inference that states that ∀xP(x) is true, given the premise that P(c) is true for all elements c in the domain. Universal generalization is used whenwe show that ∀xP(x) is true by taking an arbitrary element c from the domain and showing that P(c) is true. "Any particular dog loves to wag its tail. Therefore, all dogs love to wag their tails.
Existential instantiation
the rule of inference that allows us to conclude that there is an element c in the domain for which P(c) is true if we know that ∃xP(x) is true. We cannot select an arbitraryvalue of c here, but rather it must be a c for which P(c) is true. Usually we have no knowledge of what c is, only that it exists. Because it exists, we may give it a name (c) and continue our argument. "Something loves to wag its tail. c loves to wag his tail
Existential generalization
The rule of inference that is used to conclude that ∃xP(x) istrue when a particular element c with P(c) true is known. That is, if we know one element c in the domain for which P(c) is true, then we know that ∃xP(x) is true. "Rover loves to wag his tail. Therefore, something loves to wag its tail.
Universal modus ponens
Combines universal instantiation with modus ponens∀x(P(x) → Q(x))P(a), where a is a particular element in the domain∴ Q(a)Example: Every truck that is a firetruck is red. I see a firetruck. Therefore, it must be red.
Universal modus tollens
Combines universal instantiation with modus tollens∀x(P(x) → Q(x))¬Q(a), where a is a particular element in the domain∴ ¬P(a)Example: Every truck that is a firetruck is red. I see a blue truck. Therefore, it cannot be a firetruck.
Proof
A valid argument that establishes the truth of a mathematical statement. Used to demonstrate that theorems are true.
Theorem
(aka facts or results) A statement that can be shown to be true.
Axiom
(aka postulates) Statements we assume to be true, the premises, if any, of the theorem, and previously proven theorems.
Lemma
A less important theorem that is helpful in the proof of other results. Example: the pumping lemma
Corollary
A theorem that can be established directly from a theorem that has been proved
Conjecture
a statement that is being proposed to be a true statement, usually on the basis of some partial evidence, a heuristic argument, or the intuition of an expert
Direct proof
A conditional statement p->q constructed when the first step is the assumption that p is true; subsequent steps are constructed using rules of inference, with thefinal step showing that q must also be true. Lead from the premises to the conclusion.
Parity
The even-ness or odd-ness of a number; All even numbers share the same parity, as do all odd numbers
Indirect proof
Proofs of theorems that are not direct proofs; i.e. they do not start with the premises and end with the conclusion
Proof by contraposition
Take !q as a premise, and using axioms, definitions, and previously proven theorems, together with rules of inference, we show that !p must follow.
Vacuous proof
A proof which uses the fact that the hypothesis is false
Trivial proof
A proof which uses the fact that the conclusion is true
Rational number
A real number where there exist integers p and q with q != 0 such that r=p/q.
Irrational number
A real number that is not rational.
Matrix
A rectangular array of numbers. Plural is matrices. By convention, represented as A, B, C, etc.. with 1..j..m columns and 1..i..n rows. A particular cell in a matrix is denoted by a_{ij}, b_{kn}, c_{lo}, etc
Square Matrix
A matrix with the same number of rows and columns
Equality (matrices)
When two matrices have the same number of rows and columns and the corresponding entries in every position are equal.
Identity Matrix
The identity matrix of order n is the n × n matrix In = [δ_ij ], where δ_ij = 1 if i = j and δ_ij = 0 if i != j . Multiplying a matrix by an appropriately sized identity matrix does not change this matrix.
Element (matrices)
The value in the a_{ij} cell
Summation (matrices)
Let A = [a_ij] and B = [b_ij] be m × n matrices. Given the matrices being summed have equal size (rows and columns), the sum of A and B, denoted B, is the m x n matrix that has a_{ij} + b_{ij} as its (i, j)th element. Alternatively, A+B = [a_{ij} + b_{ij}]
Product (matrices)
Let A be an m x k matrix and B be a k x n matrix. The product of A and B, denoted by AB, is the m x n matrix with its (i, j)th entry equal to the sum of the products of the corresponding elements from the ith row of A and jth column of B. In other words, if AB = [c_ij], then:c_ij = a_{i1}b_{1j} + a_{i2}b_{2j} + ... + a_{ik}b_{kj}. Important note: The product of two matrices is not defined when the number of columns in the first matrix and the number of rows in the second matrix are not the same. Another important note: matrix multiplication is not commutative (AB != BA)
Join (matrix)
Given zero-one matrices A and B, the zero-one matrix with (i, j )th entry aij ∨ bij. Denoted by A ∨ B. Basically you OR every bit.
Meet (matrix)
Given zero-one matrices A and B, the zero-one matrix with (i, j )th entry aij ∧ bij . Denoted by A ∧ B.
Boolean product (matrix)
Let A = [aij ] be an m × k zero-one matrix and B = [bij ] be a k × n zero-one matrix. Then A and B, denoted by AB, is the m × n matrix with (i, j)th entry c_ij where: c_ij = (a_i1 ∧ b_1j ) ∨ (a_i2 ∧ b_2j ) ∨ · · · ∨ (a_ik ∧ b_kj).
Transposition (matrices)
Denoted by A^t, is the n × m matrixobtained by interchanging the rows and columns of A. In other words, if A^t = [b_ij], then b_ij = a_ji for i = 1, 2, . . . , n and j = 1, 2, . . . , m. Basically, every row i becomes a column j, and every column j becomes a row i.
Symmetric matrix
A square matrix where A = A^t. Thus A = [aij ] is symmetric if aij = aji for all i and j with 1 ≤ i ≤ n and 1 ≤ j ≤ n. In other words, transposing the matrix doesn't change the matrix.
Zero-one matrix
A matrix all of whose entries are either 0 or 1.
Rank (matrices)
The A, denoted by rank A, is the dimension of the column space of A.
Vector (matrices)
A matrix with only one column is called a column vector, or simply a vector
Zero vector
The vector whose entries are all zero is called the zero vector and is denoted by 0.(The number of entries in 0 will be clear from the context.)
Scalar (matrices)
Given a vector u and a real number c, the scalar multiple of u by c is the vector cu obtained by multiplying each entry in u by c.The number c in cu is called a scalar; it is written in lightface type to distinguish it fromthe boldface vector u.
Subspace (matrices)
A subspace of Rn is any set H in Rn that has three properties:a. The zero vector is in H.b. For each u and v in H, the sum u C v is in H.c. For each u in H and each scalar c, the vector cu is in H. g
Basis (matrices)
A basis for a subspace H of Rn is a linearly independent set in H that spans H.
Dimension (matrices)
Given a nonzero subspace H, denoted by dimH, is the number of vectors in any basis for H. The dimension of the zero subspace f0g is defined to be zero.2
Linear independence
An indexed set of vectors fv1; : : : ; vpg in Rn is said to be linearly independentif the vector equationx1v1 C x2v2 C C xpvp D 0has only the trivial solution.