Discrete Math
a modulo n (a mod n) - ANS -If n is a positive integer and a is any integer, then the remainder
we get when using the division algorithm to divide a by n is calld a modulo n. and is denoted a
mod n
\Absorption Laws - ANS -P ᴧ ( p v q) ≡ p
p v (p ᴧ q) ≡ p
\Argument - ANS -An argument is a series of statements, called PREMISES, followed by
another statement, called a CONCLUSION. An argument is called VALID if the conclusion is
true whenever all the premises are true.
\Associative Laws - ANS -p ᴧ (q ᴧ r) ≡ (p ᴧ q) ᴧ r
p v (q v r) ≡ (p v q) v r
\Cardinality - ANS -If A and B are 2 sets, then we say A and B have THE SAME cardinality if
there exists a map
f : A → B that is a bijection.
\Cardinality - ANS -If A is the finite set, then the cardinality of A is the number of distinct
elements in A, and is denoted by |A|.
\Cartesian Product - ANS -The Cartesian Product of two sets A and B is the set of all ordered
pairs (a,b), where a Є A and
b Є B. Is denoted by A x B. Therefore,
A x B = { (a,b) | a Є A and b Є B}.
\Ceiling Function - ANS -The ceiling function from R to Z maps x to the smallest integer that is
greater than or equal to x. It is denoted by ┌x┐
\Chinese Remainder Theorem - ANS -Suppose n1,n2,....,nk are integers which are pairwise
relatively prime. Then for any integers a1, a2,...,ak, there is a solution x to the system of
equations
x ≡ a1 (mod n1)
x≡ a2(mod n2).......
x≡ ak(mod nk)
x = a1• N1•x1 + a2•N1•xd mod N
where,
N = n1•n2
N1= N/n1
N2=N/n2
x1= inverse of N1 mod n1
x2 = inverse of N2 mod n2
\Codomain - ANS -Let f : A → B be a function from A to B. The set B is called the codomain of f.
\Commutative Laws - ANS -p ᴧ q ≡ q ᴧ p
pvq≡qvp
\Complement - ANS -The complement of a set A is the set U - A whose elements are the
elements of the universal set U that are not elements of A. It is denoted by Ā. Therefore,
, Ā = { x | x Ɇ A }.
\Composition - ANS -Let g: A → B be a function from the set A to the set B, and let f : B → C be
a function for the set B to the set C. Then the composition of f and g is the function f ᵒ g from A
to C defined by
( f ᵒ g ) (a) = f ( g (a) )
\Conditional - ANS -A statement of the form "if p, then q" where p and q are statements, is called
a conditional and is denoted by p -> q.
\Congruence Modulo n. - ANS -Let n be a positive integer, and a and b any integers. Then a ≡ b
(mod n) if and only if the leave the same remainder when divided by n using the division
algorithm, that is if and only if
a mod n = b mod n.
\Congruent modulo n - ANS -Let n be a positive integer. Two integers a and b are said to be
congruent modulo n if n | (b - a). We write a ≡ b (mod n) to denote a is congruent to b modulo n,
and write a ≠ b (mod n) to indicate that this is not the case.
\Conjunction - ANS -The conjunction of two statements p and q is the statement "p and q," and
is denoted by p ᴧ q. The conjunction p ᴧ q is true if both p and q are true and is false otherwise.
\Contingency - ANS -A statement that is sometimes false and sometimes true is called a
contingency
\Contradiction - ANS -To prove a statement p, start by assuming the statement is false. In other
words assume ⌐p. Then show that assuming ⌐p leads to a contradiction.
\Corollary 3.1 - ANS -If a, b and c are integers, and a | b and a | c, then for any integers m and
n, a | ( mb + nc),
\Countable - ANS -A set A is called countable(countably infinite) if there exists a bijection f : {
1,2,3,....} → A
(i.e. - we can make an infinite lists of all elements of A.)
\De Morgan's Law - ANS -For statements p and q,
⌐(p ᴧ q) ≡ ⌐p v ⌐q
⌐(p v q) ≡ ⌐p ᴧ ⌐q
\Difference - ANS -Let A and B be sets. The diffence of A and B is the set whose elements are
elements of A but not elements of B. It is denoted by A - B. Therefore,
A - B = { x |x Є A and x Є B }.
\Disjunction - ANS -The disjunction of two statements p and q is the statement "p or q," and is
denoted by p v q. The disjunction p v q is true if either of p and q are true or if both are true.
\Disjunctive Syllogism - ANS -p v q
⌐p
----------
Therefore q
\Distributive Laws - ANS -p ᴧ (q v r) ≡ (p ᴧ q) v (p ᴧ r)
p v (q ᴧ r) ≡ (p v q) ᴧ (p v r)
\Divides - ANS -If a and b are integers and there is an integer c such that b = a • c, then we say
a divides b or b is divisible by a, and write a|b. In this case, we say that a is a factor or divisor of
b and that b is a multiple of a. If a does not divide b, we write a ł b.
\Domain - ANS -Let f : A → B be a function from A to B. We call A the domain of f
\Double Negation Law - ANS -⌐(⌐p) ≡ p
a modulo n (a mod n) - ANS -If n is a positive integer and a is any integer, then the remainder
we get when using the division algorithm to divide a by n is calld a modulo n. and is denoted a
mod n
\Absorption Laws - ANS -P ᴧ ( p v q) ≡ p
p v (p ᴧ q) ≡ p
\Argument - ANS -An argument is a series of statements, called PREMISES, followed by
another statement, called a CONCLUSION. An argument is called VALID if the conclusion is
true whenever all the premises are true.
\Associative Laws - ANS -p ᴧ (q ᴧ r) ≡ (p ᴧ q) ᴧ r
p v (q v r) ≡ (p v q) v r
\Cardinality - ANS -If A and B are 2 sets, then we say A and B have THE SAME cardinality if
there exists a map
f : A → B that is a bijection.
\Cardinality - ANS -If A is the finite set, then the cardinality of A is the number of distinct
elements in A, and is denoted by |A|.
\Cartesian Product - ANS -The Cartesian Product of two sets A and B is the set of all ordered
pairs (a,b), where a Є A and
b Є B. Is denoted by A x B. Therefore,
A x B = { (a,b) | a Є A and b Є B}.
\Ceiling Function - ANS -The ceiling function from R to Z maps x to the smallest integer that is
greater than or equal to x. It is denoted by ┌x┐
\Chinese Remainder Theorem - ANS -Suppose n1,n2,....,nk are integers which are pairwise
relatively prime. Then for any integers a1, a2,...,ak, there is a solution x to the system of
equations
x ≡ a1 (mod n1)
x≡ a2(mod n2).......
x≡ ak(mod nk)
x = a1• N1•x1 + a2•N1•xd mod N
where,
N = n1•n2
N1= N/n1
N2=N/n2
x1= inverse of N1 mod n1
x2 = inverse of N2 mod n2
\Codomain - ANS -Let f : A → B be a function from A to B. The set B is called the codomain of f.
\Commutative Laws - ANS -p ᴧ q ≡ q ᴧ p
pvq≡qvp
\Complement - ANS -The complement of a set A is the set U - A whose elements are the
elements of the universal set U that are not elements of A. It is denoted by Ā. Therefore,
, Ā = { x | x Ɇ A }.
\Composition - ANS -Let g: A → B be a function from the set A to the set B, and let f : B → C be
a function for the set B to the set C. Then the composition of f and g is the function f ᵒ g from A
to C defined by
( f ᵒ g ) (a) = f ( g (a) )
\Conditional - ANS -A statement of the form "if p, then q" where p and q are statements, is called
a conditional and is denoted by p -> q.
\Congruence Modulo n. - ANS -Let n be a positive integer, and a and b any integers. Then a ≡ b
(mod n) if and only if the leave the same remainder when divided by n using the division
algorithm, that is if and only if
a mod n = b mod n.
\Congruent modulo n - ANS -Let n be a positive integer. Two integers a and b are said to be
congruent modulo n if n | (b - a). We write a ≡ b (mod n) to denote a is congruent to b modulo n,
and write a ≠ b (mod n) to indicate that this is not the case.
\Conjunction - ANS -The conjunction of two statements p and q is the statement "p and q," and
is denoted by p ᴧ q. The conjunction p ᴧ q is true if both p and q are true and is false otherwise.
\Contingency - ANS -A statement that is sometimes false and sometimes true is called a
contingency
\Contradiction - ANS -To prove a statement p, start by assuming the statement is false. In other
words assume ⌐p. Then show that assuming ⌐p leads to a contradiction.
\Corollary 3.1 - ANS -If a, b and c are integers, and a | b and a | c, then for any integers m and
n, a | ( mb + nc),
\Countable - ANS -A set A is called countable(countably infinite) if there exists a bijection f : {
1,2,3,....} → A
(i.e. - we can make an infinite lists of all elements of A.)
\De Morgan's Law - ANS -For statements p and q,
⌐(p ᴧ q) ≡ ⌐p v ⌐q
⌐(p v q) ≡ ⌐p ᴧ ⌐q
\Difference - ANS -Let A and B be sets. The diffence of A and B is the set whose elements are
elements of A but not elements of B. It is denoted by A - B. Therefore,
A - B = { x |x Є A and x Є B }.
\Disjunction - ANS -The disjunction of two statements p and q is the statement "p or q," and is
denoted by p v q. The disjunction p v q is true if either of p and q are true or if both are true.
\Disjunctive Syllogism - ANS -p v q
⌐p
----------
Therefore q
\Distributive Laws - ANS -p ᴧ (q v r) ≡ (p ᴧ q) v (p ᴧ r)
p v (q ᴧ r) ≡ (p v q) ᴧ (p v r)
\Divides - ANS -If a and b are integers and there is an integer c such that b = a • c, then we say
a divides b or b is divisible by a, and write a|b. In this case, we say that a is a factor or divisor of
b and that b is a multiple of a. If a does not divide b, we write a ł b.
\Domain - ANS -Let f : A → B be a function from A to B. We call A the domain of f
\Double Negation Law - ANS -⌐(⌐p) ≡ p
