Simply put, if you split all the digits of a number into two groups – every other digit (one group will have all the digits in odd positions, the other – in even positions), sum up all the digits in each group and subtract one sum from the other, then the remainder when dividing the result by 11 will be the same as for the original number.
Theory of Divisibility
basics
trivial divisor
A divisor of n is called a trivial divisor of n if it is either 1 or n itself.
nontrivial divisor
A divisor of n is called a nontrivial divisor if it is a divisor of n, but is neither 1, nor n.
A modular inverse of a number is such a natural number that, when multiplied modulo a given number, results in one. The modular inverse modulo m can be computed using the so-called Extended Euclidean Algorithm.
4. Выбираем число e: простое, меньше k, оно должно быть взаимно простое с k. Выберем e = 43 (открытая экспонента)
Взаимно простые числа — целые числа, не имеющие никаких общих делителей, кроме ±1. Равносильное определение: целые числа взаимно просты, если их наибольший общий делитель равен 1
5. Вычислить d, обратно по модулю k:
(d * e) % k = 1
(d * 43) % 60 = 1
d = 7 или 67
public key
Algorithms
DSA
Digital Signature Algorithm
The Digital Signature Algorithm (DSA) is a widely used asymmetric cryptographic algorithm for creating and verifying digital signatures. It was proposed by the National Institute of Standards and Technology (NIST) as a standard for digital signatures.
DSA algorithm
Key Generation:
Generate a large prime number p, typically 1024 or 2048 bits long, and a smaller prime number q, such that q divides p-1. These primes are public parameters shared by the participants.
Select an integer g, where g is a generator of the multiplicative group of integers modulo p. This group is denoted as Zp*.
Choose a private key x, a randomly selected integer from the range [1, q-1].
Compute the corresponding public key y, where y = g^x mod p.
Signing Process:
Hash the message to be signed using a secure hash function, such as SHA-256, to obtain a fixed-size message digest.
Generate a random number k from the range [1, q-1].
Compute r, where r = (g^k mod p) mod q.
Compute s, where s = ((hash + x*r) * k^(-1) mod q), and hash represents the message digest.
The signature for the message is the pair (r, s).
Signature Verification:
Obtain the public key (y) of the signer from a trusted source.
Hash the received message to obtain the message digest.
Compute w, where w = s^(-1) mod q.
Compute u1, where u1 = (hash * w) mod q.
Compute u2, where u2 = (r * w) mod q.
Compute v, where v = ((g^u1 * y^u2) mod p) mod q.
The signature is valid if and only if v is equal to r.
The DSA algorithm relies on the computational difficulty of computing discrete logarithms to provide security. The private key x must be kept secret, while the public key y can be freely distributed.
DSA is widely used in various cryptographic applications, such as secure communication, digital certificates, and authentication. However, it has been largely replaced by the more efficient and secure Elliptic Curve Digital Signature Algorithm (ECDSA) in many modern systems and protocols.
ECDSA
Elliptic Curve Digital Signature Algorithm
The Elliptic Curve Digital Signature Algorithm (ECDSA) is an asymmetric cryptographic algorithm used for creating and verifying digital signatures. It is based on the mathematical properties of elliptic curves over finite fields. ECDSA provides a high level of security with shorter key lengths compared to other algorithms like RSA.
ECDSA algorithm
Key Generation:
Select an elliptic curve defined over a finite field. The curve parameters, including the equation and base point, must be agreed upon by the communicating parties.
Choose a private key d, a random integer from a specific range defined by the curve's order.
Compute the corresponding public key Q, where Q = d * G, and G is the base point on the elliptic curve.
Signing Process:
Hash the message to be signed using a secure hash function, such as SHA-256, to obtain a fixed-size message digest.
Generate a random number k within the specified range.
Compute the point R = k * G on the elliptic curve, where G is the base point.
Derive the x-coordinate of R as r, where r = R.x mod n, and n is the order of the base point.
Compute the value s, where s = (k^(-1) * (hash + r * d)) mod n.
The signature for the message is the pair (r, s).
Signature Verification:
Obtain the public key Q of the signer from a trusted source.
Hash the received message to obtain the message digest.
Compute the value w, where w = s^(-1) mod n.
Compute the value u1, where u1 = (hash * w) mod n.
Compute the value u2, where u2 = (r * w) mod n.
Compute the point R' = u1 * G + u2 * Q on the elliptic curve.
The signature is valid if and only if the x-coordinate of R' is equal to r.
ECDSA offers strong security and performance advantages over traditional digital signature algorithms. It requires shorter key lengths, making it more efficient in terms of computation and storage. The use of elliptic curves enhances the security of the algorithm.
ECDSA is widely used in various cryptographic applications, such as secure communication protocols, digital certificates, and blockchain technologies. It provides a reliable method for verifying the authenticity and integrity of digital data.
RSA
Rivest-Shamir-Adleman
Rivest-Shamir-Adleman (RSA) is an asymmetric cryptographic algorithm widely used for secure communication, digital signatures, and encryption. It was introduced in 1977 by Ron Rivest, Adi Shamir, and Leonard Adleman. RSA relies on the computational difficulty of factoring large integers into their prime factors.
RSA algorithm
Key Generation:
Select two large prime numbers, p and q.
Compute the modulus N as N = p * q.
Compute Euler's totient function ϕ(N) as ϕ(N) = (p-1) * (q-1).
Choose a public exponent e, which is typically a small prime number, coprime to ϕ(N) (i.e., gcd(e, ϕ(N)) = 1).
Compute the private exponent d as the modular multiplicative inverse of e modulo ϕ(N) (i.e., d ≡ e^(-1) (mod ϕ(N))).
The public key is (N, e), while the private key is (N, d).
Encryption:
Convert the plaintext message into a numerical representation (e.g., using ASCII or Unicode encoding).
Split the message into blocks if necessary.
For each block m, compute the ciphertext c as c ≡ m^e (mod N).
The resulting ciphertext represents the encrypted message.
Decryption:
Obtain the private key (N, d).
For each ciphertext block c, compute the plaintext block m as m ≡ c^d (mod N).
If necessary, combine the decrypted blocks to obtain the original plaintext message.
Digital Signatures:
To create a digital signature for a message, the signer uses their private key (N, d).
The signer computes the hash of the message using a secure hash function.
The hash is then encrypted using the private key: s ≡ hash^d (mod N).
The resulting value s represents the digital signature.
Signature Verification:
To verify the signature, the recipient uses the public key (N, e) and the received signature s.
The recipient decrypts the signature using the public key: hash ≡ s^e (mod N).
The recipient computes the hash of the original message using the same secure hash function.
If the computed hash matches the decrypted hash, the signature is valid.
RSA is widely used in various applications due to its security, efficiency, and versatility. However, the security of RSA relies on the difficulty of factoring large integers, and as computing power advances, longer key lengths are required to maintain security against attacks.
Standarts
DES
Data Encryption Standard
The Data Encryption Standard (DES) is a symmetric-key block cipher algorithm that was widely used for encryption and decryption of electronic data. It was developed in the 1970s by IBM and later standardized by the National Institute of Standards and Technology (NIST) in the United States.
DES algorithm
Key Generation
The DES algorithm uses a 56-bit key, which is generated by the user or system.
The key undergoes a process called key schedule, involving permutations and transformations, to generate 16 subkeys of 48 bits each.
Encryption Process
The data to be encrypted is divided into blocks of 64 bits.
Each block goes through an initial permutation (IP) stage.
The permutation rearranges the bits according to a fixed table.
The permuted block is then divided into two halves, left and right, each consisting of 32 bits.
Rounds
The DES encryption process consists of 16 rounds of similar operations.
In each round, the right half of the data block is expanded from 32 bits to 48 bits using an expansion permutation.
The expanded right half is then XORed (bitwise exclusive OR) with a subkey generated during the key schedule.
The XOR result is passed through a series of S-boxes (substitution boxes).
The S-boxes perform a non-linear substitution, replacing each 6-bit input with a 4-bit output.
The outputs of the S-boxes are combined and passed through a permutation called a P-box.
The result of the P-box permutation is XORed with the left half of the data block.
The updated left half becomes the new right half, and the previous right half becomes the new left half.
This process is repeated for 16 rounds, with the subkeys used in a predetermined order.
Final Permutation and Output
After 16 rounds, the left and right halves of the data block are swapped.
The combined block goes through a final permutation (IP inverse).
The output of the final permutation is the encrypted data block.
Decryption
Decryption in DES is essentially the reverse of the encryption process.
The subkeys are used in the reverse order during decryption.
The same operations of expansion, XOR, S-boxes, and permutation are applied, but in the reverse order.
After 16 rounds, the final permutation is applied to obtain the decrypted data block.
DES was widely used for many years as a standard encryption algorithm, but its key size of 56 bits is now considered too short for secure encryption. Consequently, the Advanced Encryption Standard (AES) has largely replaced DES in modern cryptographic applications due to its stronger security and larger key sizes.
AES
Advanced Encryption Standard
The Advanced Encryption Standard (AES) is a symmetric-key encryption algorithm that was selected by the National Institute of Standards and Technology (NIST) in 2001 as a replacement for the Data Encryption Standard (DES). AES has become the most widely used encryption algorithm worldwide due to its strong security and efficiency.
AES algorithm
Key Generation:
AES supports key sizes of 128, 192, or 256 bits.
The key is generated by the user or system and must match the chosen key size.
Encryption Process:
The data to be encrypted is divided into blocks of 128 bits.
AES operates on a fixed number of rounds depending on the key size: 10 rounds for AES-128, 12 rounds for AES-192, and 14 rounds for AES-256.
Each round consists of several transformation stages, including SubBytes, ShiftRows, MixColumns, and AddRoundKey.
SubBytes: Each byte of the data block is substituted using a predefined substitution box (S-box), which provides non-linearity and confusion.
ShiftRows: The bytes in each row of the data block are shifted cyclically to the left.
MixColumns: The columns of the data block are mixed using a matrix multiplication operation to achieve diffusion.
AddRoundKey: The data block is XORed with a round key derived from the main encryption key.
Key Expansion:
The original encryption key is expanded to generate a set of round keys for each round of encryption.
The key expansion algorithm involves a series of transformations, including SubBytes, RotWord, and XOR with a round constant.
The round keys are derived from the main encryption key and used in the AddRoundKey operation during each round.
Decryption:
Decryption in AES is essentially the reverse of the encryption process.
The round keys are used in reverse order during decryption.
The inverse of each transformation stage (InvSubBytes, InvShiftRows, InvMixColumns) is applied in the reverse order.
After the final round, the data block is XORed with the last round key to obtain the decrypted data.
AES provides a high level of security, even against sophisticated attacks, and is widely adopted in various applications, including secure communication, data storage, and digital systems. Its flexibility in supporting different key sizes allows for a balance between security and performance, making it a versatile encryption algorithm.
DSS
Digital Signature Standard
The Digital Signature Standard (DSS) is a standard for digital signatures that was established by the National Institute of Standards and Technology (NIST) in the United States. It specifies the algorithms and protocols to be used for generating and verifying digital signatures.
Components
Digital Signature Algorithm (DSA):
DSA is the core algorithm used for generating and verifying digital signatures in the DSS.
It is based on the mathematical properties of modular exponentiation and the difficulty of solving the discrete logarithm problem in finite fields.
DSA utilizes a specific elliptic curve (FIPS 186-4) or a set of predefined parameters for prime fields (FIPS 186-3).
The algorithm provides a high level of security with relatively short key sizes.
Key Generation:
DSS specifies the key generation process for DSA.
A large prime number p and a smaller prime number q are generated according to specific criteria.
The private key is randomly generated as an integer within a certain range.
The corresponding public key is computed based on the private key and the generated primes.
Signature Generation and Verification:
DSS defines the procedures for generating and verifying digital signatures using DSA.
To generate a signature, the private key holder computes specific mathematical operations based on the message and private key.
The resulting signature consists of two values: r and s.
To verify the signature, the public key holder performs calculations using the received signature, message, and public key.
The verification process ensures that the signature is valid and has not been tampered with.
Key Management and Certification:
DSS provides guidelines for key management and certification, including the storage, backup, and revocation of keys.
It outlines practices for generating, storing, and protecting keys to maintain the security and integrity of digital signatures.
The standard also addresses the use of certificates to establish trust and verify the authenticity of public keys.
The Digital Signature Standard (DSS) is widely adopted and used in various applications where digital signatures are required for authentication, integrity, and non-repudiation of digital data. It ensures the security and interoperability of digital signature systems and plays a crucial role in secure communication, electronic transactions, and data integrity verification.
methods
CFRAC
Continued FRACtion method (for factoring)
Choose a number to factorize: Let's say we have a composite number N that we want to factorize.
Choose a quadratic function: The method uses a quadratic function, typically f(x) = (x^2) mod N, to generate a sequence of numbers.
Generate a sequence: We generate a sequence of numbers using the quadratic function and a chosen starting value.
Create fractions: Each number in the sequence is used to create a fraction. The fraction is then converted into a continued fraction.
Find convergents: The convergents (best rational approximations) of the continued fraction are computed.
Check for factorization: For each convergent, we check if the denominator divides N. If it does, we've found a non-trivial factor of N.
Repeat: If no factor is found, the process is repeated with a different quadratic function or a different starting value.
ECM
Elliptic Curve Method (for factoring)
Choose a number to factorize: Let's say we have a composite number N that we want to factorize.
Choose an elliptic curve and a point: We randomly choose an elliptic curve E over the field of integers modulo N, and a point P on E.
Perform point multiplication: We compute kP where k is a product of small primes, and P is the point chosen on the elliptic curve.
Check for factorization: If during the computation of kP, we find a non-trivial divisor of N, then we've found a factor of N.
Repeat: If no factor is found, the process is repeated with a different elliptic curve or a different point.
NFS
Number Field Sieve (for factoring)
Choose a number to factorize: Let's say we have a composite number N that we want to factorize.
Polynomial selection: We choose two polynomials f(x) and g(x) such that f(x) is irreducible over the integers and g(x) is a simpler polynomial, typically linear. The root of f(x) modulo N should be a root of g(x) modulo N.
Sieving: We search for values of x such that both f(x) and g(x) are B-smooth, meaning all their factors are less than some bound B. These values of x are used to form a matrix over the field with two elements.
Matrix reduction: We use linear algebra techniques to find a nontrivial kernel of this matrix. This gives us a set of x values such that the product of f(x) is a square modulo N and the product of g(x) is a square in the integers.
Square root computation: We compute these square roots and use them to find a factor of N.
Select a smoothness bound B.
Choose a quadratic polynomial f(x) = (ax + b)^2 - N.
Sieve using a set of primes p1, p2, ..., pk, such that their squares are smaller than or equal to B:
Compute f(x) modulo pi for x = 0 to B.
If f(x) is divisible by pi, divide f(x) by pi until it is not divisible anymore.
Record the exponent of pi.
difference
QS
In the QS algorithm, a single quadratic polynomial is selected, and sieving is performed using this polynomial. The goal is to find x values for which the polynomial evaluates to a perfect square modulo N.
MPQS
On the other hand, MPQS extends the QS algorithm by using multiple quadratic polynomials. A set of quadratic polynomials is chosen, and sieving is performed using each of these polynomials. The aim is still to find x values for which each polynomial evaluates to a perfect square modulo N.
In summary, the key difference between QS and MPQS is that QS uses a single quadratic polynomial for sieving, while MPQS employs multiple quadratic polynomials to increase the probability of finding suitable x values for factorization.
Construct a matrix "relations" to store the relationships between smooth values.
For each smooth value (x, exponent):
For each prime pi:
Compute pi^exponent modulo N and store it in the "relations" matrix.
Use Gaussian elimination or other linear algebra techniques to find equations summing up to zero modulo 2.
Solve the system of equations to find a set of x values.
Compute the product of the corresponding f(x) values.
If the product is a perfect square modulo N, you have found non-trivial factors of N.
If no factors are found, repeat with different quadratic polynomials until successful or a limit is reached.
Multiple Polynomial Quadratic Sieve (MPQS)
ECPP
Elliptic Curve Primality Proving
Select a random elliptic curve E defined over a finite field of size N.
Choose a random point P on the elliptic curve E.
Generate a random prime q such that q is small enough for efficient computation and q does not divide N.
Compute the point Q = [q]P, where [q] denotes the scalar multiplication of the point P by the integer q.
If the point Q is the identity element on the elliptic curve (i.e., Q = O, where O denotes the point at infinity), return to step 2 and choose a different random point P.
Compute the order r of the point Q. The order r is the smallest positive integer such that [r]Q = O.
If r does not divide N, return to step 2 and choose a different random point P.
Verify the primality of N using the primality test for r. This step involves checking if r is a prime number using a separate primality-testing algorithm.
If the primality test for r determines that r is composite, return to step 2 and choose a different random point P.
Repeat steps 2 to 9 until a prime r is found.
Perform a set of consistency checks to ensure that the computed values are correct and that N is a prime number.
If all the checks pass, conclude that N is a prime number. Otherwise, repeat the process with a different elliptic curve or different random point P.
Number systems
Conversion from Decimal
Whole Part
Sequentially divide by the base, record the remainder as the new digit of the number, and then divide the result again by the base. Write the digits in reverse order (the first remainder is the last digit of the number).
Fraction
Sequentially multiply by the base, record the whole part as a digit, and multiply the fractional part again by the base. Write the digits in the order obtained.
0.515625 = 0.41 (8)
0.515625 * 8 = 4.125
> 4
0.125 * 8 = 1
> 1
Binary
Fractions
0.1 = 0.5
1/2
0.01 = 0.25
1/4
0.001 = 0.125
1/8
0.0001 = 0.0625
1/16
To Decimal
0.75 = 0 + 7 * (1/8) + 5 * (1/64)
Octal
Conversion from Binary using 3 bits
10 101.101110 = 25.56
Fractions
0.1 = 0.125
1/8
0.01 = 1/64
Hexadecimal
Conversion from Binary using 4 bits
1.01 = 1.4
10 0111 0010 = 272
Fractions
0.1 = 0.0625
1/16
Multiplication
FAF9 * 6FFD = 16AF6
Numbers
Numbers
1
01
1
1
2
10
2
2
3
11
3
3
4
100
4
4
5
101
5
5
6
110
6
6
7
111
7
7
8
1000
10
8
9
1001
11
9
10
1010
12
A
11
1011
13
B
12
1100
14
C
13
1101
15
D
14
1110
16
E
15
1111
17
F
16
10 000
20
10
Sequences and Series
Series
It is the sum of the terms of a sequence.
Arithmetic progression
The sum of all terms of an arithmetic progression is equal to half the product of the sum of its extreme terms and the number of all its terms.
sum of all positive odd numbers
Geometric progression
Examples
The sum of n terms of a geometric progression with denominator q != 1 is equal to the quotient of dividing the difference between the product of the last term by the denominator of the progression and the first term by the difference between the denominator of the progression and one.
Sum of squares
Sum of cubes
Examples
Triangular numbers
decomposition
sum decomposition
moving multiplier
don't do this for n
compound percent
FV is the future value of the annuity.
P is the monthly deposit (annuity payment).
r is the monthly interest rate (as a decimal).
n is the total number of payments (or months, in this case).
limit
sequences limit
convergents
geometric series
The limit of geometric series
harmonic series
Cauchy Criterion
English
Root test
Ratio test
additional
convergence of a sequence between two others
conditions
Binomial Theorem
limits
Sequences
Arithmetic progression
Geometric progression
module (random)
Popular
Bernoulli
Bernoulli numbers are a sequence of rational numbers which are deeply connected to number theory. They appear in the series expansions of trigonometric functions, in formulas for the sum of powers of the first n positive integers, in the Euler-Maclaurin formula, and many other areas in mathematics.
Fermat
Mersenne primes
Sets
General
Set theory branch of mathematics that deals with the properties of well-defined collections of objects
Definition
A set is defined as a collection of distinct elements.
{a, b, c}
{x | x is a natural number, x < 10}
A set is an unordered collection of unique objects
Cardinality of a set (Card)
Number of elements in a set.
Element of a set
Subset
A set where all elements are also in another set.
Proper subset
A proper subset is a subset that contains some but not all elements of the larger set, and it can't be identical to the larger set.
Not Proper subset
Special Sets
Natural numbers
Integers
Rational numbers
Irrational numbers
Irrational numbers are real numbers that cannot be expressed as a simple fraction – that is, they cannot be written as a ratio of two integers. When written in decimal form, irrational numbers are infinite and non-repeating. This means that the numbers go on forever without repeating a pattern.
characteristics
Non-repeating
The decimal expansion never repeats or terminates. Unlike a rational number, where you can eventually find a repeating pattern or the digits end entirely, irrational numbers have no such repeating pattern.
Non-terminating
They go on forever without coming to an end.
examples
3.14159...
1.41421...
The square root of any non-perfect square
Euler's number (e):
2.71828...
The golden ratio (φ)
1.61803...
Real numbers
Representing Sets
Listing Method
List all elements within curly brackets.
Examples
Set-Builder Notation (Rule of Inclusion)
Describe elements using a rule within curly brackets.
Examples
Even Integers
Odd Integers
Rational Numbers
Power Sets
The power set P(S) of a set S contains all possible subsets of S
Elements & Subsets
Elements of a set can also be sets themselves.
A set can be both a subset of one set and an element of another.
Examples
Cardinality
Advanced Cardinality
Set Operations
Union of Sets
the set containing all the elements that are in either A or B.
Intersection of Sets
the set containing all the elements that are in both A and B.
Set Difference
The set difference A−B contains all the elements that are in A but not in B.
Symmetric Difference
contains all the elements that are in either A or B, but not in both.
Membership Tables
1 means the element belongs to the set.
0 means the element does not belong to the set.
Cartesian product
A Cartesian product of two sets A and B is the set containing ordered pairs from A and B
Venn Diagrams and Set Theory
Universal Set
Denoted by U, it contains all possible elements.
Complement of a Set
meaning it contains all elements in U that are not in A.
Venn Diagrams for Sets
Used to visualize relationships among sets.
The entire area represents the Universal Set U
Operations
Commutativity
Associativity
Distributivity
De Morgan's Laws
Special Cases
Absorption Laws
Set Difference
Disjoint Sets
Inclusion-Exclusion Principle (IEP) for two sets
Laws
De Morgan's Laws
First Law
The complement of the union of two sets is equal to the intersection of their complements:
Second Law
The complement of the intersection of two sets is equal to the union of their complements:
Functions and plots
Plots
Coordinates
Addition
Q(1,2)
P(-1, 3)
Q+P(0, 5)
Q-P(2,-1)
Plane
Cartesian Coordinates
System of two perpendicular axes, x,y to map and label points on the plane
origin
(0, 0)
Formulas
distance between points
midpoint
description
Tangent to curve
The gradient of a curve at any point is equal to the gradient of the tangent at that point
Asymptote
an asymptote (/ˈæsɪmptoʊt/) of a curve is a line such that the distance between the curve and the line approaches zero as one or both of the x or y coordinates tends to infinity.
intersections with axes
x = 0
y = 0
symmetry
types
Straight line
Any straight line has an equation of the form y = mx + c where m and c are constants
m
In the equation y = mx + c the value m is known as the gradient and is a measure of the steepness of the line
or slope
m
if the point (a, b) lies on the line y = mx + c then equation is satisfied by letting x = a and y = b
parallel
perpendicular
two-point form
base changing
a - vertical dilation
b - horizontal dilation
c - horizontal translation
d - vertical translation
Quadratic function
y = 0
Cubic function
fractional
higher order polynomials
circle
center: (h, k)
Function
Definitions
Intervals
closed
An interval that includes its end-points is called a closed interval
[1, 3]
open
Any interval that does not include its end-points is called an open interval
strictly greater
strictly less
(1, 3)
semi-open/semi-closed
[1, 3)
types
Surjective function
to each y of set Y is associated at least one element x of set X
onto
vertical line test
every possible output must be obtainable from some input.
Injective function
to each x of set X is associated only one distinct y of set Y
one-to-one
horizontal line test
different inputs must result in different outputs.
Image and Pre-Image
y is the image of x
x is the pre-image of y.
Components of a Function
Domain of a function
elements of set X on which f is defined
The set of all inputs for the function
Every element x in the domain of a function has one output f(x).
Codomain of a function
elements of Y linked by f to X
The set containing all possible outputs
Range
The set of all actual outputs from the function
variants
A non-injective surjective
An injective surjective
An injective non-surjective
A non-injective non-surjective
domain
co-domain
inverse function
graph
Function composition
Definition
The composition of two functions
equal to
Stages of Computation
Input X to the function G and get G(x) as output.
Use the output of G(x) as an input to the function F and get F(G(x)).
Example with Functions F and G
Function F
Function G
Calculating
Get the output of G(x)
Use the output of G(x) as an input to F
Visualization of Function Composition
Sets
Commutative Property
Function composition is not commutative
Example
As we can see, F(G(1)) is not equal to G(F(1)). Therefore, the function composition is not commutative.
Floor and Ceiling Functions
Floor Function
The floor function is denoted as ⌊x⌋.
The floor function, ⌊x⌋, takes a real number
x and returns the largest integer less than or equal to x.
For example
Properties of the Floor Function
The ceiling of an integer is equal to itself.
The ceiling of any number x between n and n+1 (inclusive) is n + 1
The domain of the ceiling function is all real numbers.
Property Proof: Floor Function
Graph
Ceiling Function
The ceiling function, ⌈x⌉, takes a real number x and returns the smallest integer greater than or equal to x
Example
Properties of the Ceiling Function
The ceiling of an integer is equal to itself.
The ceiling of any number x between n and n+1 (inclusive) is n+1.
The domain of the ceiling function is all real numbers.
Graph
Hamming distance
the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different.
it measures the minimum number of substitutions required to change one string into the other, or the minimum number of errors that could have transformed one string into the other.
Kinematics
variables
u - initial velocity
v - final velocity
S - distance
formulas
graphs
Useful
Exponential
for all a, y intercept of 1, that is the graph passes through (0,1)
a > 1, the function is increasing
a < 1, the function id decreasing
for all a, the function is positive
the x-axis is an asymptote
e
2.71828
natural exponential function
Logarithms
Types
Natural logarithm
the inverse of the natural exponential function
Logarithm function with base a
the domain
the range
Logarithm with base 10
Properties
Product Rule
Quotient Rule
Reciprocal Rule
Power Rule
Inverse properties
Base a
Base e
Common
Change of base
Every logarithmic function is a constant multiple of the natural logarithm
Graphs
for all a, x intercept of 1, that is the graph passes through (1,0)
for all a, the graph passes through (a, 1)
a > 1, the function is increasing
a < 1, the function id decreasing
for all a, the function is positive
the y-axis is an asymptote
the function defined for a > 0 and x > 0
for a > 1 the bigger a is more slowly the function increases
for a < 1 the smaller a is the more slowly the function decreases
Limits and differentiation
Limit of sequence
If limit exists finite, the sequence is convergent
If limit doesn't exists the sequence is said to be divergent
Laws
Sum Law
The limit of a sum is the sum of the limits
Difference Law
The limit of the difference is the difference of the limits
Constant Multiple Law
The limit if a constant times a function is the constant times the limit of the function
Product Law
The limit if a product is the product of the limits
Quotient Law
The limit of a quotient is the quotient of the limits (provided that the limit of the denominator is not 0)
Limit and continuity of a function
Discontinious
Derivative of a function
The derivative of a function is the limit of the ratio of the change in the function to the change in its argument, provided that the change in the argument approaches zero.
Slope
Slope shows the change in y or the change on the vertical axis versus the change in x or the change on the horizontal axis.
Gradient
Rules
Trigonometric
L'Hôpital's rule
Derivate and study of a function
Max and Min
Second test
Concavity test
Introduction
Symbols
The Greek alphabet
Latex
Sets
\mathbb{letter}
Real number
Vocabulary
Prime numbers
It is a positive integer, larger than 1, which cannot be expressed as the product of two smaller positive integers
2, 3, 5, 7, 11, 13, 13, 17, 19, 23
factor
3 * 4 = 12
3 and 4 are factors of 12
when a number is written as a product of prime numbers we say the number has been factorised
Highest common factor
h.c.f
greatest common divisor
g.c.d
Lowest common factor
fraction
fraction = numerator/denominator = p /q
proper fraction
p < q
improper fraction
p > q
inverted
q / p
reciprocal
reciprocal = inverted fraction
The reciprocal of a number is found by inverting it, so, for example, the reciprocal of 4/5 is 5/4
equivalent fractions
simplest form
when there are no factors common to both numerator and denominator
common denominator
q / a and p / a. a - common denominator
mixed fraction
whole number and fraction part
least common multiply
l.c.m
In Mathematics, the LCM of any two is the value that is evenly divisible by the two given numbers. The full form of LCM is Least Common Multiple. It is also called the Least Common Divisor
l.c.d
decimal
decimal point
first decimal place
number of significant figures
number of decimal places
rounded
rounded up
rounded down
percentage
percentage change
ratio
Ratios are simply an alternative way of expressing fratcions
Divide 170 in the ratio 3 : 2
3/5 of 170
102
2/5 of 170
68
Divide 250 cm in the ratio 1 : 3 : 4
1/8
BODMAS
Brackets
()
Of
x
Division
/
numerator
denumerator
quotient
Multiplication
*
Addition
+
Substruction
-
Algebra
superscript
power
index
y
indices
plural
laws of indices
the first law
base
x
negative powers
fractional powers
scientific notation
quadratic expressions
a and b - coefficients
constant term
subscript
root
substitution
Substitution means replacing letters by actual numerical values
formula
A formula is used to relate two or more quantities
subject
transpose
If we asked to transpose formula for r, then we must rearrange the formula so that r becomes the subject
like terms
Like terms are multiples of the same quantity
Like terms can be collected together and added or subtracted in order to simplify them
fraction
partial fractions
it is a part of the original fraction
linear factor
ax + b
repeated linear factor
quadratic factor
equations
unknown quantity
solve
solution
root of the equation
satisfy the equation
linear equations
ax + b = 0
b - constant term
simultaneous equations
eliminating
quadratic equations
discriminant
> 0
distinct real roots
= 0
repeated root
equal roots
verbs
evaluate
simplify
express
factorise
determine
obtain
inequalities
x > y
y < 5
sequence
term
finite sequence
infinite sequence
limit
converge
When a sequence possesses a limit it is said converge
diverge
arithmetic progressions
common difference
geometric progressions
common ratio
series
sigma notation
arithmetic series
geometric series
set
A set is a collection of clearly defined objects, things or states
{...}
finite set
infinite set
equal sets
subset
union
Venn diagrams
number sets
Number bases
decimal system
binary system
octal system
hexadecimal system
elementary logic
symbolic logic
negation
The negation of a proposition is the proposition that is true whenever the original proposition is false and false when the original is true
not
conjunction
Given any two propositions we can form their conjunction
and
disjunction
or
implication
if then
compound proposition
Trigonometry
angle
measure
degree
360
minutes
60
seconds
60
radian
types
right
90
flat
180
complete
360
triangles
properties
types
similar triangles
Isosceles
two sides and two angles are equal
equilateral
all sides and angles are equal
right triangles
sides
h - hypotenuse
opposite
adjacent
properties
scalene
all three sides are different
General
cosine
sine
tangent
cotangent
trigonometrical ratios
formulas
the cosine rule
the sine rules
secant
cosecant
cotangent
more
Cofunction identities
Double angles
Even/odd
Half angles
Reciprocal functions
Power reducing formulas
Product to sum
Pythagorean identities
Sum and difference of angles
Sum to product
Circle view
projections
Functions
The sine finction
The cosine function
the tangent function
Vectors and Matrices
Common
Vector space
A vector space or a linear space is a group of objects called vectors, added collectively and multiplied (“scaled”) by numbers, called scalars.
Properties
Associatibity
Commutativity
Identity
Inverse
Compatibility
Distributivity
Examples
Euclidean vector
line
plane
Operations
scalar product of vectors
The scalar product of two vectors is defined as the product of the magnitudes of the two vectors and the cosine of the angles between them
The Dot Product
Cross Product
The scalar product is the product of vectors which gives a scalar quantity whereas the vector product is the product of vectors which gives a vector quantity as the product.
parallelogram area
length
unit vector
A unit vector is a vector whose length is 1
Linear independence
In the theory of vector spaces, a set of vectors is said to be linearly independent if there exists no nontrivial linear combination of the vectors that equals the zero vector. If such a linear combination exists, then the vectors are said to be linearly dependent. These concepts are central to the definition of dimension.
Basis
A basis for a vector space is a sequence of vectors that form a set that is linearly independent and that spans the space.
Linear Transformations and Matrices
Vector Rotations
Clockwise rotation
Linear
Matrix
Multiplication
To perform multiplication of two matrices, we should make sure that the number of columns in the 1st matrix is equal to the rows in the 2nd matrix. Therefore, the resulting matrix product will have a number of rows of the 1st matrix and a number of columns of the 2nd matrix.
sum i row A * j column B
Determinant of a matrix
The determinant of a matrix is the scalar value or number calculated using a square matrix.
Inverse Transformation
Inverse matrix is obtained by dividing the adjugate of the given matrix by the determinant of the given matrix.
Systems of equations and matrices
Example
A system of equations can be represented by an augmented matrix.
In an augmented matrix, each row represents one equation in the system and each column represents a variable or the constant terms.
In this way, we can see that augmented matrices are a shorthand way of writing systems of equations.
Gauss Jordan elimination
Gauss-Jordan Elimination is an algorithm that can be used to solve systems of linear equations and to find the inverse of any invertible matrix.
Probability
Probability
Total outcomes
x
variants
n
times
or
and
Independent events
The outcome of one event does not affect the other
Dependent events
The outcome of one event affects the other
conditional probability
probability that, given the occurrence of B, A occurs as well
example
A = clubs
B = king
A and B = king of clubs
Combinatorics
Permutations
Types and formulas
Formula
+
Selecting r elements from n options, with repetition
Distribute r distinguishable balls into n distinguishable boxes
Permutations with repetition
+
Permutations without repetition
Arranging n elements in a sequence, no repetition
+
-
Permutations without using all elements
Arranging r elements from n options, no repetition
+
-
Combinations without repetition
Selecting r elements from n options, no repetition, order does not matter
Distribute n balls into r boxes, no repeated balls
-
-
Permutations of a multiset
Arranging elements of a multiset (where n is the total number of items, and m_1, m_2, ..., m_k are the counts of each distinct item)
+
Implicit (due to the nature of multisets)
Combinations with Repetitions
Number of ways to select k objects from n categories with repetition permitted is given by the combination formula.
Distribute n balls into k boxes, repeated balls
-
+
Counting
The Rule of Sum (Addition Principle)
If you have two tasks, and there are a ways to do the first task and b ways to do the second task, and these tasks can't be done at the same time (they are mutually exclusive), then there are a+b ways to do one of the tasks.
The Rule of Product (Multiplication Principle)
If there are a ways to do something, and
b ways to do another thing after the first thing has been done, then there are a×b ways to perform both actions.
the permutation of r elements
in a set of total n elements
if we don't want to count more than once the groups (couples) that are different only for by the order we must divide by r!
Binomial distribution
Combinations
Combinations are about selecting objects without regard to the order in which they are selected. If you have n objects and want to select r of them, the number of ways to do this is given by the combinations formula.
If you're arranging r objects out of n available objects, the formula changes a bit.
Permutations of multisets
Distinguishable Objects and Boxes
Distinguishable Balls into Distinguishable Boxes
With Exclusion
Representation as unordered selection of k boxes from n.
Without Exclusion
Representation as an ordered selection of k boxes from n with repetition.
Indistinguishable Balls into Distinguishable Boxes
With Exclusion
Without Exclusion
k - balls
n - boxes
Binomial coefficients
Here, n! denotes the factorial of n, which is the product of all positive integers up to n.
Properties
Symmetry
Binomial coefficients have a symmetric property.
Summation
They also follow a rule when adding two adjacent coefficients.
Pascal's Triangle
Each number in Pascal's triangle is the sum of the two numbers directly above it, and these numbers represent binomial coefficients.
Examples of application
Binomial Coefficients
look at the fifth row (counting from zero) of Pascal’s Triangle and the second element in this row (counting from zero)
Combinatorial Tasks
Suppose you want to find the number of paths from the top-left corner to the bottom-right corner of a grid, moving only down and to the right. For a 2x2 grid, the number of paths is equal to the element in the third row and third element of Pascal's Triangle, which is 6.
Permutations with repetition (Paths through a grid)
Finding the number of distinct paths through an
r×s grid, using only steps down and to the right
Expansion of Binomial Powers
use the fourth row of Pascal’s Triangle (1, 4, 6, 4, 1)
Probability Theory
Number of outcomes for tossing a coin 3 times. If you toss a coin 3 times, the number of possible outcomes for each quantity of "heads" corresponds to the third row of Pascal’s Triangle: 1 (no heads), 3 (one head), 3 (two heads), 1 (three heads).
Geometry
Binomial Theorem
The binomial coefficients play a key role in the binomial theorem, which gives the expansion of powers of binomials.
Example
Let's calculate the binomial coefficient for n = 5 and r = 3
So, there are 10 ways to choose 3 elements out of a set of 5.
Application
Combinatorics
They are used to solve problems involving combinations where order does not matter.
Probability
Binomial coefficients can calculate the probabilities in binomial distributions, where there are two possible outcomes (like success and failure).
Algebra
In expanding binomials, they determine the coefficients in the expanded form.
Applications
Designing algorithms
Cryptographic systems
Network optimization
Game theory
Pigeonhole Principle
Basic
Definition
If K+1 objects are placed into K boxes, then at least one box contains two or more objects.
Contrapositive
If no box has more than one object, then the total number of objects would be at most K, which contradicts having K+1 objects.
One-to-One Functions
If the domain of a function F has K+1 elements mapped to K elements, then F is not one-to-one.
Create a box for each element in the co-domain of F.
As there are K+1 elements in the domain and only K boxes, there must be at least one box with more than one element.
Therefore, F is not one-to-one.
Generalized
If N objects are placed into K boxes, then there exists a box with at least ceiling(N/K) objects.
Proof
Assume no box exceeds ceiling(N/K - 1) objects, which contradicts the total being N.
Application
Cards from a Deck
To guarantee at least 4 cards of the same suit, a minimum of 13 cards from a standard deck of 52 cards must be selected.
Statistics
frequency
mean
The mean is the average of all the numbers in a dataset.
You sum up all the numbers and then divide by the total count.
value
amount of value
median
The median is the middle value when you arrange the numbers in ascending order. If there's an even number of values, you take the mean of the two middle numbers.
Median=Middle value in sorted list
variance
Variance measures how spread out the numbers are from the mean.
standard deviation
The standard deviation is the square root of the variance. It's useful because it's in the same units as the data.
mode
Mode=Most frequently occurring value(s)
The mode is the number that appears most frequently in a dataset. A dataset can have zero or more modes. If no number repeats, it's called "no mode." If there are multiple numbers that appear most frequently, it's "multimodal."
Normal distribution (Gaussian distribution)
Key Points
Symmetry
It's symmetrical around the mean, which means the left and right sides are mirror images of each other.
Mean, Median, Mode
In a perfect normal distribution, the mean, median, and mode are all the same and located at the center of the curve.
Standard Deviation
The "width" of the bell curve is determined by the standard deviation (σ). A larger σ means a wider curve, and a smaller σ means a narrower curve.
68-95-99.7 Rule
About 68% of the data falls within one standard deviation of the mean.
About 95% falls within two standard deviations.
About 99.7% falls within three standard deviations.
Mathematical Expression
μ is the mean
σ is the standard deviation
Chebyshev's Theorem
Chebyshev's Theorem states that no matter what the shape of the distribution, at least a certain percentage of the data must lie within k standard deviations (σ) of the mean (μ).
Key Points
Applicability
Unlike the 68-95-99.7 rule for normal distributions, Chebyshev's Theorem applies to any distribution shape.
k Value
k must be greater than 1. The larger the k, the higher the percentage of data within that range.
Discrete
Predicate Logic
Predicate Logic vs Propositional Logic
Propositional Logic Limitations
Inadequate for expressing complex mathematical statements.
Example
"All men are mortal."
"Socrates is a man."
Conclusion: "Socrates is mortal."
Only deals with propositions (statements with known truth values).
Example
Statement: "X squared is equal to 4."
This is not a proposition as its truth value depends on the value of 'x'.
Propositional logic cannot express this, but predicate logic can.
Propositional logic cannot express complex statements in mathematics precisely
Propositional logic only studies propositions with known truth values
Propositional logic is helpful for studying propositions but has limitations
Predicate Logic Advantages
Overcomes limitations of propositional logic.
Allows for building more complex reasoning.
Introduction
Objective: Understanding the role of predicate logic in addressing the limitations of propositional logic.
Focus: Examining examples that propositional logic can't describe and introducing predicate logic as a solution.
Defining Predicate Logic
Predicate: A generalization of propositions; functions returning true/false based on variables.
Transformation into Proposition: Predicates become propositions when variables are assigned specific values.
Example Analysis
Predicates
Predicates are functions that return a true or false value depending on their variables.
Predicates are generalizations of propositions.
Predicates become propositions when their variables are given actual values.
Examples
with a single parameter
with multiple parameters
Logical Operations
Logical operations from propositional logic can be carried over to predicate logic.
Quantification
Quantifiers
Universal
for all values of x in the universe of discourse
for all x P(x)
If universe of discourse is finite, universal quantifier is conjunction of propositions over all elements
conjunction
Existential
there exists a value x in the universe of discourse
there exists x P(x)
If universe of discourse is finite, existential quantifier is disjunction of propositions over all elements
disjunction
Uniqueness
there exists a unique value of x in the universe of discourse
there exists a unique x P(x)
Nested quantifiers
examples
Variables
Bound
A variable is bound if it is within the scope of a quantifier
Free
A variable is free if it is not bound by a quantifier or particular value
x is bound
y is free
De Morgan's laws for quantifiers
Negation of for all x, P of x is equivalent to there exists x for which not P of x
Negation of there exists x for which P of x is equivalent to for all x not P of x
Application of De Morgan's laws successively from left to right
Rules of Inference
Rules
Modus Ponens
Premises
Conclusion
Modus Tollens
Premises
Conclusion
Conjunction
Premises
Conclusion
Simplification
Premises
Conclusion
Addition
Premises
Conclusion
Hypothetical Syllogism
Premises
Conclusion
Disjunctive Syllogism
Premises
Conclusion
Resolution
Premises
Conclusion
Rules of Inference with Quantifiers
Universal Instantiation
From
Infer
for a specific element c
Example
Premise
Application
Consider a specific number, say 5
Conclusion
Existential Instantiation
From
Infer
for some element c
Example
Premise
Application
Consider a specific bird, say a sparrow.
Conclusion
Sparrow can fly.
Universal Generalization
From
Infer
Example
Premise
Every single apple in a basket is red.
Application
This apple is red, that apple is red, and so on for every apple.
Conclusion
Existential Generalization
From
Infer
Example
Premise
A particular bird, say a robin, can sing.
Application
This robin can sing.
Conclusion
Universal Modus Ponens
From
Infer
Example
Premise
Application
Conclusion
Universal Modus Tollens
From
Infer
Example
Premise
Application
Conclusion
In these rules, P(x) represents a predicate involving the variable x, and c represents a specific constant or element. These rules help in moving between statements about specific elements and general statements about all elements (or the existence of elements) within a domain.
Expressing Complex Statements Using Quantifiers
Determine the universe of discourse of variables
Reformulate the statement by making "for all" and "there exists" explicit
Reformulate the statement by introducing variables and defining predicates
Reformulate the statement by introducing quantifiers and logical operations
Info
Premises
These are statements or propositions that are assumed to be true. They serve as the starting point for logical reasoning.
Conclusion
This is the statement or proposition that logically follows from the premises. It's what you deduce or infer based on the given premises.
Tautology
A tautology is a statement or formula that is true in every possible interpretation. No matter what values you assign to its components, a tautological statement will always be true.
It's like saying "it will either rain or not rain today." This statement is always true because there are no other possibilities besides raining and not raining.
In the context of the Rules of Inference, tautologies can be used to justify certain steps in a logical argument or proof. For instance, some rules might inherently involve tautological statements to ensure the validity of the conclusions drawn from the premises.
How to Use the Rules of Inference:
Identify the Form of the Argument: First, look at the logical structure of the argument you have. Which rule of inference does it resemble? For instance, if you have two premises: "If it rains, the ground will be wet" and "It is raining," this matches the structure of Modus Ponens.
Apply the Rule: Once you've identified the rule, apply it to derive the conclusion. In our example, using Modus Ponens, we conclude: "The ground will be wet."
Propositional Logic
Key Concepts
Propositions
In propositional logic, propositions are statements that can be either true or false but not both. They are the basic building blocks of logical reasoning. For example, "The sky is blue" and "2 + 2 = 5" are propositions.
Definition of a Proposition: In the realm of mathematics and logic, a proposition is a declarative sentence that can have only one of two truth values: true or false. It serves as the fundamental building block for logical reasoning.
Logical Connectives
And (∧): Represents logical conjunction. It is true only when both propositions are true.
Or (∨): Represents logical disjunction. It is true when at least one of the propositions is true.
Not (¬): Represents negation. It reverses the truth value of a proposition.
Implies (→): Represents implication. It indicates that if the first proposition is true, the second must also be true.
If and Only If (↔): Represents biconditional. It is true when both propositions have the same truth value.
Non-declarative questions, e.g., "What time is it?"
Imperative statements, e.g., "Read this carefully."
Statements with vague or relative meanings, e.g., "This coffee is strong."
Propositional Variables
To streamline notations and avoid repetition, propositional variables (usually denoted as p, q, r, etc.) are employed. These variables represent propositions.
Truth Tables and Truth Sets
Truth Tables
When dealing with complex propositions, we need a systematic method to determine their truth values. Truth tables serve as a tool to represent all possible combinations of truth values for propositional variables.
Definition
A truth table is a tabular representation that exhaustively lists all possible combinations of truth values for its constituent propositional variables.
Constructing a Truth Table
Number of Rows
For n propositional variables, create a table with 2^n rows and n columns.
Filling Values
Fill the n columns with all possible combinations of truth values, usually starting with false values.
Example
Consider three propositional variables, p, q, and r. The truth table will have eight rows, with columns for p, q, and r. Values will alternate to represent all possible combinations
Truth tables help manage and analyze the truth values of complex propositions by systematically listing all possible combinations of truth values for propositional variables.
Truth Set
Truth Set of a Proposition
Let p be a proposition defined on a set S. The truth set of p, denoted as capital P, is the set of elements in S for which p is true.
Example
Scenario
et S be the set of integers from 1 to 10. Define two propositions concerning an integer n in S:
Proposition p: "n is even."
Proposition q: "n is odd."
Truth Sets
The truth set of p, denoted as capital P, includes integers 2, 4, 6, 8, and 10.
The truth set of q, denoted as capital Q, includes integers 1, 3, 5, 7, and 9.
A truth set, denoted as capital P for a proposition p, is the set of elements in a given set for which p is true.
Compound Propositions
Negation (Not Operator)
Negation of a Proposition (not p)
If p is a proposition, then the negation of p, denoted as not p, is the statement "It is not the case that p." The truth value of not p is the opposite of the truth value of p.
Example
For proposition p, "John's program is written in Python," the negation not p is the proposition "John's program is not written in Python."
Conjunction (And Operator)
Conjunction of Propositions (p and q)
Given propositions p and q, the conjunction p and q is true only when both p and q are true; otherwise, it is false.
Example
If p is "John's program is written in Python" and q is "John's program has less than 20 lines of code," then p and q is "John's program is written in Python and has less than 20 lines of code."
Disjunction (Or Operator)
Disjunction of Propositions (p or q)
Given propositions p and q, the disjunction p or q is false only when both p and q are false; otherwise, it is true.
Example
If p is "John's program is written in Python" and q is "John's program has less than 20 lines of code," then p or q is "John's program is written in Python or has less than 20 lines of code."
Exclusive-Or (XOR Operator)
Exclusive-Or of Propositions (p xor q)
Given propositions p and q, the exclusive-or p xor q is true only when either p is true and q is false or p is false and q is true, but not both.
Example
If p is "John's program is written in Python" and q is "John's program has less than 20 lines of code," then p xor q is "John's program is written in Python or has less than 20 lines of code, but not both."
Order of Precedence
Parentheses for Clarity
When combining propositions, use parentheses to clarify the order of operations. The meaning of propositions can vary based on the arrangement of parentheses.
Order of Precedence
To reduce the number of parentheses, you can use an order of precedence, which determines the sequence of logical operations.
Logical Implication
Conditional Statements
Conditional statements are propositions of the form "if p then q," where p is the hypothesis, and q is the conclusion or consequence.
Example
Consider propositions p and q: p is "John did well in discrete mathematics," and q is "John will do well in the programming course." The conditional statement is "If John did well in discrete mathematics, then John will do well in the programming course."
Truth Table
Logical Reasoning
Conditional statements represent reasoning from p to q. If the reasoning is correct (true implication), when the hypothesis is true, the conclusion is also true. In the case of incorrect reasoning (false implication), when the hypothesis is true, the conclusion is false. If the hypothesis is false, any conclusion can be implied, whether false or true.
Variations
If p then q
If p, q
p implies q
p only if q
q follows from p
p is sufficient for q
q unless not p
q is necessary for p
Related Statements
converse
The converse of p implies q is q implies p.
contrapositive
The contrapositive of p implies q is not q implies not p.
inverse
The inverse of p implies q is not p implies not q.
Example
Logical Equivalence
Equivalence Operator
Let p and q be propositions. The biconditional or equivalent statement, "p equivalent to q," is the proposition p implies q and q implies p. It is also represented as "p if and only if q." The statement "p equivalent to q" is true when p and q have the same truth values and false otherwise.
Equivalence of Propositions
Logical Equivalence
Two propositions, p and q, are considered logically equivalent if they always have the same truth value, denoted as "p equivalent to q." This concept is different from equivalent statements.
Determining Equivalence
Equivalence can be determined by using truth tables to check whether two propositions have the same truth values for all possible combinations.
Translation
Logic Laws
Propositional
Idempotent Laws
p or p is equivalent to p.
p and p is equivalent to p.
Commutative Laws
p or q is equivalent to q or p.
p and q is equivalent to q and p.
Associative Laws
The conjunction and disjunction operators can be distributed over one another.
Distributive Laws
The order in which operators are performed doesn't matter as long as their sequence remains the same
Identity Laws
p or false is equivalent to p.
p and true is equivalent to p.
Domination Laws
p or true is always equivalent to true.
p and false is always equivalent to false.
DeMorgan's Laws
Formalize negation of conjunction and disjunction.
Negation of disjunction (p or q) is equivalent to (not p and not q).
Negation of conjunction (p and q) is equivalent to (not p or not q).
Absorption Laws
p or (p and q) is equivalent to p.
p and (p or q) is equivalent to p.
Negation Laws
p or not p is always true (tautology).
p and not p is always false.
Double Negation Law:
not not p is equivalent to p.
Tables
Boolean Algebra
History
Aristotle established the foundations of logic between 384 and 322 BC
George Boole developed a system of logical algebra in 1854
Huntington defined the six rules of Boolean algebra in 1904
Claude Shannon investigated Boolean algebra for analyzing relay switching circuits in 1938
Boolean algebra is the foundation of computer circuits analysis
Basic Operations
AND
Logical product representing logical conjunction
2
OR
Logical sum
3
NOT
Logic complement
1
Postulates
Huntington's
Closure: The value of any Boolean operation is either zero or one.
Identity: The value of x + 0 and x.1 is always equal to the value of x.
Commutativity: Plus and dot are both commutative. That is, x + y equals y + x and x.y equals y.x.
Complements: The logical sum of x and its corresponding complement is always equal to one, while the logical product of x and its corresponding complement is always equal to zero.
Distance Elements: Any Boolean algebra has to have two distinct values.
Basic Theorems
Idempotent laws: For any logical variable x, x + x equals x and x.x equals x.
Tautology and contradiction: For any logical variable x, x + 1 is a tautology as its value is always equal to one, whereas x.0 is a contradiction as its value is always equal to zero.
Involution: For any logical variable x, the value of applying the complement twice on x is always equal to x.
Associative laws: Given any three logical variables x, y, and z, we have x + (y + z) = (x + y) + z and x.y.z = (x.y).z.
Absorption laws: Given any two logical variables x and y, we have x + (x.y) = x and x.(x + y) = x.
Uniqueness of complements: Given any two logical variables x and y, if y + x = 1 and y.x = 0, then x = complements of y.
Inversion law: The complement of zero is equal to one and the complement of one is equal to zero.
De Morgan's Theorems
The complement of a product of variables is equal to the sum of the complements of the variables: complements of x.y = complements of x + complements of y.
The complement of a sum of variables is equal to the product of the complements of the variables: complements of (x + y) = complements of x . complements of y.
Distributivity of plus over dot
Principle of Duality
Every theorem in Boolean algebra remains valid if we interchange all ANDs and ORs and interchange all zeros and ones.
Equivalence Proving Methods
Perfect induction: Showing that two expressions have identical truth tables.
Axiomatic proof: Applying Huntington's postulates or other rules and theorems.
Duality principle: Interchanging ANDs and ORs and zeros and ones.
Contradiction: Assuming the hypothesis is false and showing it leads to a false conclusion.
Proof of Absorption Rule
By writing the truth table or using the rules, we can prove that x + (x.y) = x and x.(x + y) = x.
By applying the duality principle, we can also deduce that x.(x + y) = x.
Boolean functions
Definition
Boolean function: mapping from Boolean input value(s) to a Boolean output value
n Boolean input values result in 2^n possible combinations
Algebraic Form
f(x) = x + x'y
f(x) = x + y
Standardized Forms
Sum of products form: values built using the AND operator, summed using the OR operator
Product of sums form: values built using the OR operator, multiplied using the AND operator
Useful Boolean Functions
Exclusive OR Function (XOR)
xor(x, y) = x'y + xy' (true if either x or y is true, but not both)
Implies Function
implies(x, y) = x' + y (true if x implies y)
Logic Gates
Introduction
Definition: electronic circuit with single or multiple inputs and single or multiple outputs
Outputs are logical functions of inputs
Basic logic gates: OR, AND, NOT
Variants
Basic Logic Gates
OR
High output if at least one input is high
Truth table: f = x + y
AND
High output if all inputs are high
Truth table: f = x * y
NOT
Output is opposite of input
Truth table: f = not x
Additional
XOR
High output if inputs are different
NAND
AND gate followed by an inverter
NOR
OR gate followed by an inverter
XNOR
XOR gate followed by an inverter
Multiple Input Gates
AND, OR, XOR, and XNOR operations can be extended to more than two inputs
NAND and NOR operations are commutative but not associative
De Morgan's Laws
The complement of the product of variables is equal to the sum of the compliments of the variables
The complement of the sum of variables is equal to the product of the compliments of the variables
Combinational Circuits
Introduction
Combination circuits are logic networks designed to model Boolean functions
They implement a Boolean function, where the output values depend on the current input configuration
We want to minimize the number of gates to reduce the circuit's cost
Building a Logic Network
Label the gates' outputs that depend on input variables
Express the Boolean functions for each gate in the first level
Repeat this process for subsequent levels until all outputs are written as Boolean expressions
Designing Systems for Specific Problems
Label inputs and outputs using variables
labelling
Model the problem as a Boolean expression
modelling
Replace each operation with its equivalent logic gates
replacing
Half Adder
Used to add two 1-digit binary bits
Sum is the output of XOR gate
Carry can be represented by AND gate
Full Adder
Overcomes limitations of half adder for multi-bit additions
Has 3 inputs: x, y, and carry in
Express sum as x XOR y XOR carry in
Express carry out as xy + carry in
the key functions of a full adder circuit
Binary Addition: It adds two binary digits plus a carry-in from a less significant bit position.
Sum Output: It produces a sum output, which is the result of the addition of the two input bits and the carry-in.
Carry Output: It generates a carry-out, which is used as a carry-in for the addition of the next pair of higher significant bits.
table
Simplification
Purpose
reducing global cost, computation time, and increasing circuit density
Algebraic simplification
Use of Boolean algebra paradigms to simplify Boolean functions
Theorems/rules for simplification: De Morgan's laws, distributive laws, commutative, idempotent, complement laws, and absorption law
Karnaugh maps
K-maps
Example
0
1
Tables
Proofs
Definitions and Terminology
Proof
A valid argument used to prove the truth of a statement.
Theorem
A formal statement that can be shown to be true.
Axiom
A statement assumed to be true to serve as a premise for further arguments.
Lemma
A proven statement used as a step to a larger result.
Corollary
A theorem that can be established by a short proof from another theorem.
Types
Direct Proof
Direct proof is based on showing that a conditional statement, p implies q, is true. It starts by assuming that p is true and then uses axioms, definitions, theorems, and rules of inference to show that q must also be true.
Example
For example, let's consider the theorem stating that there exists a real number between any two not equal real numbers. This can be proven using a direct proof by assuming that x and y are arbitrary elements in R, and let z be the real number (x + y) / 2. It can be shown that z satisfies x < z < y. Therefore, the statement holds for all x and y in R.
Proof by Contraposition
Proof by contraposition is based on the fact that proving the conditional statement p implies q is equivalent to proving its contrapositive, not q implies not p. It starts by assuming that not q is true and then uses axioms, definitions, theorems, and rules of inference to show that not p must also be true.
Example
For example, the theorem stating "If n squared is even, then n is even" can be proven using the contrapositive. By assuming that n is odd, it can be shown that n squared is also odd. Therefore, the contrapositive holds and the original statement is true.
Proof by Contradiction
Proof by contradiction is based on assuming that the statement to be proved is false and then showing that this assumption leads to a false proposition. It starts by assuming that not p is true and then uses axioms, definitions, theorems, and rules of inference to show that not p is false. From this, it can be concluded that the initial assumption was wrong, so p must be true.
Example
For example, the theorem stating "There are infinitely many prime numbers" can be proven using a proof by contradiction. By assuming that there are only finitely many prime numbers and listing them as p_1, p_2, p_3, etc., it can be shown that there exists a number c that is a product of all the prime numbers plus 1. From this, it can be derived that c has at least one prime divisor, which contradicts the assumption that there are only finitely many prime numbers.
Mathematical Induction
Definition
Mathematical induction is a method used to prove that a propositional function, P(n), is true for all positive integers, n.
Induction can be formalized using the following rule of inference: P(1) is true, and for all k, P(k) implies P(k+1).
Intuition
Induction is based on the idea that if P is true for a base case (e.g., P(1)), and if P being true for one case implies P being true for the next case (e.g., P(k) implies P(k+1)), then P is true for all cases.
Structure of Induction
Basic step: Show that P(1) is true.
Inductive step: Show that for all k in n, if P(k) is true (inductive hypothesis), then P(k+1) is also true.
Applications
Formulas
Inequalities
Divisibility
Properties of subsets and their cardinality
Proof by Induction
Introduction
Induction can be used to prove formulas, inequalities, and divisibility
Two steps for proving a propositional function P of n:
Basis step: show P of 1 is true
Inductive step: show if P of k is true, then P of k plus 1 is true for all k in n
Examples
Proving a Formula
Proving the formula: the sum from 1 to n is equal to n times (n plus 1) divided by 2
Basis step: P of 1 is true
Inductive step: Assuming P of k is true, show P of k plus 1 is true
Proving an Inequality
Proving the inequality: 3 to the power of n is less than n factorial for n >= 7
Basis step: P of 7 is true
Inductive step: Assuming P of k is true, show P of k plus 1 is true
Proving Divisibility
Proving the divisibility: 6 to the power of n plus 4 is divisible by 5
Basis step: P of 0 is true
Inductive step: Assuming P of k is true, show P of k plus 1 is true
Incorrect Induction
Statement: the sum from i equals 0 to n minus 1 of 2 to the power of i is equal to 2 to the power of n for all n in n
Incorrectly assumed that the statement holds true for all n
Base case and inductive step were verified, but the statement is false
To avoid false conclusions, both the base case and the inductive step must be verified
Strong Induction
Principle
In ordinary induction, you prove a base case, say P(1), and then show that if P(k) is true, P(k+1) is also true.
In strong induction, you assume that the statement is true for all values less than or equal to a certain number k (i.e., P(1), P(2), ..., P(k)) and use this to show that P(k+1) is true.
Why Use Strong Induction?
It's used when the proof of P(k+1) depends not just on P(k) but on several or all of the previous cases.
Steps in a Strong Induction Proof
Base Case
rove the statement for the initial value(s), just like in ordinary induction. This could be for one or more initial values (e.g., P(1), P(2)).
Inductive Step
Assume P(i) is true for all i ≤ k, where k is some positive integer. Then prove that P(k+1) is true under this assumption.
Example
Proving properties in sequences or series where each term depends on multiple previous terms.
Establishing correctness of algorithms, especially recursive ones.
Why It's "Strong"
It's not stronger in the sense of proving more statements true. Rather, it's a more flexible tool in your mathematical toolkit, allowing you to tackle problems that ordinary induction can't handle as easily.
Tips for Writing Strong Induction Proofs
Clearly state the property P(n) you want to prove.
Don't forget to prove the base case(s) thoroughly.
In the inductive step, clearly state your inductive hypothesis (that P(i) is true for all i ≤ k).
Show how this hypothesis helps you prove P(k+1).
Recursive
Definitions
Introduction
Recursion allows for defining objects in terms of themselves
Recursive definitions are used for functions, sets, and algorithms
Recursively Defined Functions
A function is recursively defined by a basis step and a recursive step
Basis step: specifies the initial value of the function
Recursive step: provides a rule for finding the value of the function at an integer from its values at smaller integers
Recursively Defined Sets
Sets can also be defined recursively
Basis step: specifies some initial elements
Recursive step: provides a rule for constructing new elements from those already defined
Example: Set S contains all positive integers that are multiples of four
Recursive Algorithms
An algorithm is a finite sequence of precise instructions for solving a problem
Recursive algorithms solve a problem by reducing it to a smaller instance of the same problem
Example: Recursive algorithm for computing n factorial
Basis step: 0 factorial equals 1
Recursive step: n factorial equals n multiplied by (n-1) factorial
Recurrence Relations
First-order Recurrence
Example: Modeling country's population growth
Linear recurrence equation: an+1 = 1.01an + 50,000
This describes a sequence where each term is a linear combination of only the previous term plus a constant.
Second-order Recurrence
Example: Fibonacci sequence
Linear recurrence equation: an = an-1 + an-2
Each term is a linear combination of the previous two terms.
Arithmetic Sequences
Definition and properties
Definition: A sequence where each term differs from the next by a constant amount (common difference).
Properties: Easy to compute, used for simple uniform series.
Example: Common difference
Geometric Sequences
Definition and properties
A sequence where each term is obtained by multiplying the previous term by a constant (common ratio).
Used in exponential growth/decay models, compound interest calculations.
Example: Common ratio
Divide and Conquer Algorithms
Three steps: divide, solve, combine
Divide: Break the problem into smaller subproblems.
Solve: Solve each subproblem (often recursively).
Combine: Combine solutions of subproblems to form the solution to the original problem.
Example: Finding minimum of a sequence
Solving Recurrence Relations
Linear Recurrence
General form
Characteristic equation
If r is a solution with multiplicity p, the combination satisfies the recurrence
Fibonacci Recurrence
General form
Characteristic equation
Distinct roots
Solution
Use initial conditions to find
Using Strong Induction
Graphs
Definition
Graph G represented as VE
V - set of nodes or vertices
E - set of edges, lines, or connections
Vertices
Basic elements of a graph
Usually represented as nodes or dots
Set of vertices denoted as V(G) or just V
Edges
Links between two vertices
Usually represented as lines
Set of edges denoted as E(G) or just E
Adjacency
Vertices are adjacent if they are endpoints of the same edge
Edges are adjacent if they share the same vertex
If vertex v is an endpoint of edge e, then e and v are incident
Loops and Parallel Edges
Loops: edge that connects a vertex to itself
Parallel edges: multiple edges between the same pair of vertices
Directed Graphs
Edges have a direction, indicated by arrows
digraph
A graph is a discrete structure consisting of vertices or nodes and edges connecting them
Applications
Computer science uses graph theory to create abstractions of real-world problems that can be represented, understood, and manipulated by computers
Graphs can model associations or connections between items in various domains, such as course scheduling, computer networks, roadmaps, and organization structures
The first problem in graph theory was the Seven Bridges of Königsberg problem, solved by Leonhard Euler in 1735
Real-World Applications
Modeling computer networks
Modeling roadmaps
Solving shortest path problems
Assigning jobs in an organization
Distinguishing chemical compound structures
Walks and Paths
Walk
A sequence of vertices and edges where vertices and edges can be repeated.
Trail
A walk in which no edge is repeated. Vertices can be repeated.
Circuit
A closed trail where vertices can be repeated.
Path
A trail in which neither vertices nor edges are repeated.
Cycle
A closed path consisting of edges and vertices, where the last vertex is reachable from the first.
Named Paths
Euler Path
A path that uses each edge of the graph precisely once, making the graph traversable.
Euler Circle
If a graph has an Euler circuit, then every vertex of the graph has a positive even integer
Hamiltonian Path
A path that visits each vertex of a graph exactly once.
Hamiltonian Cycle
A cycle that visits each vertex exactly once, except for the starting vertex which is visited once at the start and once again at the end.
Graph Connectivity
Connected Graph
A graph in which any two vertices are connected by a path.
Strongly Connected Digraph
A strongly connected digraph is a directed graph in which it is possible to reach any node starting from any other node by traversing edges in the direction(s) in which they point.
Transitive Closure
The digraph G* where there is a directed edge from U to V if there is a directed path from U to V.
Degree Sequence
Vertex Degree
The degree of a vertex in a graph is the number of edges incident to the vertex.
An isolated vertex has a degree: 0
In directed graphs, it is distinguished between in-degree (number of edges for which the vertex is the terminal vertex) and out-degree (number of edges for which the vertex is the initial vertex).
A loop contributes twice to the degree.
Degree Sequence
For an undirected graph G, the degree sequence is a sequence of the degrees of each vertex in G written in descending order, separated by commas.
Properties
The sum of the degree sequence is always even.
The sum of the degree sequence is twice the number of edges in the graph.
Example
Consider a graph with vertex degrees 4, 3, 3, 2, 1, 1. The sum of the degree sequence is 14. This indicates the graph has 7 edges.
directed graph
The degree sequence of a directed graph is the list of its indegree and outdegree pairs
Special graphs
Simple Graphs
A simple graph contains no loops and no parallel edges.
The degree of each vertex of a simple graph with n vertices is at most n-1.
Example
Regular Graphs
An r-regular graph has all vertices with the same number of neighbors and degree.
Properties
Degree sequence of an r-regular graph is r, r, r repeated n times
Number of edges = r*n/2
r*n should be even
Examples
Complete Graphs
A complete graph has every pair of vertices adjacent.
Properties of complete graphs with n vertices
Every vertex has a degree of n-1
Sum of degree sequence = n*(n-1)
Number of edges = n*(n-1)/2
Examples
Isomorphic Graphs
Definition
Two graphs, G1 and G2, are isomorphic if there is a bijection, an invertible function F, mapping all vertices of G1 to vertices of G2, preserving adjacency and non-adjacency.
If vertices U and V in G1 with edge uv, then F(u), F(v) is an edge in G2, preserving adjacency.
Properties
Degree Sequences
Graphs with different degree sequences are not isomorphic.
Graphs with the same degree sequences are not necessarily isomorphic.
Bipartite graphs
Definition
A graph G is bipartite if the set of vertices V can be divided into two sets V₁ and V₂, and each edge is between V₁ and V₂.
Vertices can be divided into two sets - V1 and V2
Each edge connects a vertex in V1 with a vertex in V2
Matching
Matching: A set of pairwise non-adjacent edges.
Maximum Matching: A matching of maximum size.
Vertex is matched if it is an endpoint of a matching edge.
Hopcroft-Karp Algorithm
Augmenting path: Increases the cardinality of the current matching.
An augmenting path is a path in a bipartite graph that begins and ends with unmatched vertices (vertices not included in the current matching) and alternates between edges that are not in the matching and those that are. This means the path starts with an edge not in the current matching, the next edge is in the matching, the following is not, and so on.
Breadth-first search (BFS)
Traverses the graph level by level
Depth-first search (DFS)
Traverses a graph all the way to a leaf before starting another path
Used to find the maximum matching in a bipartite graph
Follows a pseudocode involving breadth-first and depth-first search
Explanation
Adjacency Matrix
Adjacency List
The adjacency list of a graph is a list of vertices and their corresponding adjacent vertices
Adjacency Matrix
A graph can also be represented by its corresponding adjacency matrix.
digraph
Properties
The adjacency matrix of an undirected graph is symmetric.
The number of edges in an undirected graph is half the sum of all the elements of its adjacency matrix.
For example, the sum of the adjacency matrix's elements is equal to the sum of the degree sequence of the undirected graph and a half of of the degree sequence of the directed graph.
Matrix powers
If A is the adjacency matrix of the directed or undirected graph G, then the matrix A^n (i.e., the matrix product of n copies of A) has an interesting interpretation: the element (i, j) gives the number of (directed or undirected) walks of length n from vertex i to vertex j.
If n is the smallest nonnegative integer, such that for some i, j, the element (i, j) of A^n is positive, then n is the distance between vertex i and vertex j.
Dijkstra's Algorithm
Definition
Dijkstra's algorithm is used to compute the shortest path between two vertices in a weighted graph.
It works in two steps:
Initialization: Initialize distances from A to all vertices and the unvisited list.
Pic
Set distance from start vertex A to itself as 0.
Set distance from start vertex A to all other vertices as infinity.
Previous vertex is initialized to undefined.
Update unvisited list with all nodes of the graph.
Update Step: Iteratively visit unvisited vertices, calculate distances, and update the table until completion.
Pic
For each visited vertex, examine its unvisited neighbors and calculate their distances from A.
Update the shortest distances for the neighbors if the calculated distances are less.
Update the previous vertex column for visited neighbors.
Remove the visited vertex from the unvisited list.
Application
It can be used in various scenarios such as modeling the distance between cities, response time in a communication network, or cost of a transaction.
Trees
Application
Finding the shortest path in a graph.
Constructing efficient algorithms to locate items in a list.
Modeling procedures carried out using a sequence of decisions.
Binary tree as a fundamental data structure in high-level programming.
Definition
Acyclic Graph
An acyclic graph has no cycles, loops, or parallel edges.
Tree
A tree is an undirected graph that is connected and acyclic.
Properties
1. A tree is a connected graph with a unique simple path between any pair of vertices.
2. A tree with n vertices has exactly n-1 edges.
Forest
In graph theory, a cycle-free disconnected graph is called a forest.
Spanning Trees
Definition
A spanning tree of a connected graph is a subgraph that is a tree containing all the vertices of the original graph.
Properties
A graph with n vertices has n-1 edges in its spanning tree.
A spanning tree does not contain any cycles.
Removal of any edge from a spanning tree results in a disconnected graph.
Algorithms for Finding
Depth-First Search (DFS): Traverses the graph depth-wise, ensuring a spanning tree is formed.
Breadth-First Search (BFS): Explores the neighbors of the vertices horizontally to construct a spanning tree.
Minimum Spanning Tree
A minimum spanning tree of a weighted graph is the spanning tree with the minimum total edge weight.
Prim's and Kruskal's algorithms are commonly used to find the minimum spanning tree of a graph.
Kruskal's Algorithm
Start with: Cheapest edge, add cheapest edges to keep it connected without cycles
Prim's Algorithm
Starting node: Choose any node and iteratively add the least-weight edge to connect nodes
Weight of Spanning Tree
Sum of edge weights in the tree
A minimum cost spanning tree connects all vertices in a graph with the lowest overall edge weight.
Isomorphic
Two spanning trees are isomorphic if there exists a bijection preserving adjacency between them.
Non-Isomorphic
Rooted Trees
Definition
A rooted tree has a designated root vertex, and every edge is directed away from the root.
A directed tree with one vertex as the root.
Property
Each vertex has a directed path from the root.
Depth
Number of edges from root to a node. (Path length)
Height
Longest path from node to leaf.
Terms
Parent
Children
Ancestor
Siblings
Internal
External Nodes
Special Trees
Binary Tree
Max two children per vertex.
Ternary Tree
Max three children per vertex.
m-ary Tree
Max m children per vertex.
Regular m-ary Tree
Each internal node has m children.
Properties
Isomorphic Trees
Definition
Two trees are isomorphic if there's a bijective map preserving adjacency.
Isomorphism
Rooted trees are isomorphic if there's a bijection mapping roots.
Binary Search
Definition
A binary search tree (BST) is a binary tree data structure where each node has at most two children, referred to as the left child and right child, with the left child's key being less than the parent's key and the right child's key being greater.
Uses
BSTs are commonly used for searching, inserting, and deleting elements in logarithmic time complexity, making them efficient data structures for many operations.
Building a Binary Search Tree
Start with an empty tree
Insert nodes one by one following the key comparison rules
Nodes on the left have keys less than the parent node, and nodes on the right have keys greater
Storing Records
For each side, add the minimum to the maximum, divide it by two and take the floor of the result.
External nodes (green rectangles) can store additional records.
Height
The height of a binary search tree depends on the order of insertion of records.
In the best-case scenario with balanced input, the height is logarithmic, while in the worst-case scenario of skewed input, the height can be linear.
Example
if N = 15, height is 4 using both methods.
Algorithm
Compare search element to middle term of the list.
Split list into two sub-lists based on comparison.
Continue search in appropriate sub-list.
Relations
Intro
Overview
Relations connect two entities, whether living or non-living.
Common relationships include familial ties (e.g., mother-daughter, brother-sister), employment relations, and associations in computer science.
Mathematical
Study relationships like divisibility of positive integers, relations between real numbers, and function evaluations.
Define relationships between elements of sets and within the same set.
Properties
Further exploration of the characteristics and behaviors of mathematical relations.
Understanding the various properties inherent to different types of relations.
Motivation
Recognizing the importance of relations in mathematical analysis and problem-solving.
Building a foundation for understanding complex mathematical concepts through relation theory.
Definition
A relation is a set of ordered pairs where the first element in each pair is related to the second element.
Relation vs. Function
A relation R is a set of ordered pairs (x, y) where x is related to y.
A function is a special type of relation where each element in the domain is related to exactly one element in the co-domain.
Examples
Cartesian Product
The Cartesian product of sets A and B is a set of pairs
Formal Definition
Binary Relation
A binary relation from set A to B is a subset of A x B. It consists of ordered pairs (x, y) where x is from A and y is from B, indicating that x is related to y.
Matrix and Graph
Intersection
Intersection Notation
Definition
Combining Relations
Union Calculation
using matrix join operation.
Intersection Calculation
using matrix meet operation.
Graphical Representation of a Relation
A relation on set A can be represented by a digraph with vertices as elements of A
Relation Defined by Division
Consider
Relation using Matrix
Matrix Representation of Specific Relations
Relation: Strictly Less Than
Relation: Less Than or Equal To
Properties
Reflexive Relations
A relation R on set S is reflexive if for all x ∈ S, xRx holds.
Example of Reflexive Relation
Let R be on Z such that a ≤ b. This is a reflexive relation as a ≤ a for all a ∈ Z.
Example of Non-Reflexive Relation
For all x elements of Z, we have x !< x hence x !R x
Digraph
Digraph has a loop on each element of S
Example
S={1,2,3,4}, R={(a,b) | a,b ∈ S, a ≤ b}
Matrix
Adjacency matrix M_r of a reflexive relation has all diagonal elements as 1
Reflexivity
Every element is related to itself.
Symmetric Relations
A relation R on set S is symmetric if for all a,b in S, aRb implies bRa
Example
R={(a,b) | a,b ∈ Z, a mod 2 = b mod 2} is symmetric
Digraph
Digraph contains symmetric pairs of arcs
Matrix
Matrix M_r is symmetric if R is symmetric
Symmetry
Relations are bidirectional between related elements.
Anti-symmetric Relations
A relation R on set S is anti-symmetric if for all x, y ∈ S, if xRy and yRx, then x = y.
Example
If R relates a to b and b to a, then a = b for R to be anti-symmetric.
R={(a,b) | a,b ∈ Z, a ≤ b} is anti-symmetric
Digraph
No parallel edges between different vertices in the digraph
Matrix
Element M_ij ≠ 0 implies M_ji = 0 for anti-symmetry
Anti-symmetry
If two elements relate to each other, they must be the same.
Transitivity
Digraph
Transitive relations can be visually represented by digraphs where nodes represent elements of the set S, and edges display the relation between elements.
Transitive Closure
The transitive closure of a relation R on a set S is the smallest transitive relation that contains R.
To find the transitive closure of a relation, iteratively add edges to make it transitive until no more edges need to be added.
Importance
Transitivity is crucial in various areas such as graph theory, database management, and equivalence relations.
It helps in determining the reachability and connectivity between elements in networks and systems.
A relation R on a set S is transitive if for all a, b, c in S, if a is related to b and b is related to c, then a is related to c.
Equivalence
Definition
A relation R on a set S is an equivalence relation if and only if R is reflexive, symmetric, and transitive.
Example
Non-Equivalence Relation
A relation on Z where a, b are related if a ≤ b is not an equivalence relation as it fails to be symmetric.
Let R be a relation on elements in Z where a, b are related if a mod 2 = b mod 2 for all a, b in Z. R is reflexive, symmetric, and transitive, thus an equivalence relation.
Equivalence Classes
Equivalence class of a is set {x ∈ S | xRa}.
Equivalence relation on Z where a mod 2 = b mod 2 has two equivalence classes: {1, 3} and {2, 4}.
Partitioning
Equivalence classes form a partition of the set S.
Representatives
Each equivalence class has a representative element.
Uniqueness
Each element in S belongs to exactly one equivalence class.
Properties
Reflexivity
For all a ∈ S, aRa.
Symmetry
For all a, b ∈ S, if aRb then bRa.
Transitivity
For all a, b, c ∈ S, if aRb and bRc, then aRc.
Partition
all the elements of the set are in the partition.
each element of the set appear in one parition only
Order
Partial Order
A relation R on set S is a partial order if it is reflexive, anti-symmetric, and transitive.
Example
Relation on integers Z where a is less than or equal to b.
Relation on positive integers Z-plus where a divides b.
Total Order
A relation R on set S is a total order if it is a partial order and every pair of elements in S are comparable.
Example
Relation on integers Z where a is less than or equal to b.
Interval Orders
An interval order is a partial order that arises from a collection of intervals on the real line.
Example
Consider a set of intervals in R defined by their endpoints. The relation "less than or overlaps" between intervals forms an interval order
Linear Extensions
In the context of a partial order, a linear extension is a total order that preserves the partial order relation.
Example
Given a partial order on a set of elements, determining a linear extension involves defining a linear order that respects the given partial order constraints.