Page 1
Semester 1: Discrete Mathematics
Relations - Binary relations, Operations on relations, Properties of binary relations, Equivalence relations, Representation by matrix and digraph
Relations
Binary Relations
A binary relation R from a set A to a set B is defined as a subset of the Cartesian product A x B. If (a, b) is in R, a is related to b. Binary relations can be represented in various ways, including by a set of ordered pairs or a relation matrix.
Operations on Relations
Common operations on binary relations include union, intersection, and composition. The union of two relations R1 and R2, denoted R1 ∪ R2, includes all pairs that are in either relation. The intersection R1 ∩ R2 includes pairs that are in both. The composition of two relations R1 and R2, denoted R1 ∘ R2, is the set of pairs (a, c) such that there exists a b in set B with (a, b) in R1 and (b, c) in R2.
Properties of Binary Relations
Binary relations can have various properties such as reflexivity, symmetry, and transitivity. A relation is reflexive if every element is related to itself. It is symmetric if for every pair (a, b), if (a, b) is in R then (b, a) is also in R. It is transitive if whenever (a, b) and (b, c) are in R, then (a, c) must also be in R.
Equivalence Relations
An equivalence relation is a type of binary relation that is reflexive, symmetric, and transitive. If a relation R is an equivalence relation, it partitions the set into disjoint subsets known as equivalence classes, where every member of a class is related to each other.
Representation by Matrix
A binary relation from a set A with n elements can be represented by an n x n matrix. The matrix entry at position (i, j) is 1 if the element corresponding to row i is related to the element corresponding to column j; otherwise, it is 0.
Representation by Digraph
A directed graph (digraph) can also represent binary relations, where each element in the set represents a vertex, and directed edges represent the relationships between the pairs. If (a, b) is in relation R, a directed edge from vertex a to vertex b is drawn.
Functions - Definition, Classification, Composition, Inverse
Functions
Definition
A function is a relation that uniquely associates each element of a set with exactly one element of another set. In mathematical terms, a function f from a set A to a set B is denoted as f: A → B.
Classification
Functions can be classified into various types. One major classification is based on the nature of their relationship. Types include: one-to-one functions, onto functions, and many-to-one functions. Another classification is based on the nature of the output, producing real-valued functions, or integer-valued functions.
Composition
The composition of two functions f and g is defined as the function h such that h(x) = f(g(x)). The composition is often denoted as (f ∘ g) and provides a way to combine the effects of two functions.
Inverse
An inverse function reverses the effect of the original function. If f: A → B is a function, then an inverse function f^{-1}: B → A exists if for every b in B, f(f^{-1}(b)) = b. Not all functions have inverses; only one-to-one functions do.
Mathematical Logic - Logical connectives, Well-formed formulas, Truth tables, Quine's method, Normal forms, Rules of inference, Quantifiers
Mathematical Logic
Logical Connectives
Logical connectives are symbols or words used to connect two or more propositions. Common connectives include AND, OR, NOT, IMPLIES, and BICONDITIONAL. These connectives form the foundation of forming compound statements.
Well-formed Formulas
Well-formed formulas (WFFs) are expressions that are constructed according to the rules of syntax in propositional logic. A WFF is made up of propositions and logical connectives that are arranged in a valid manner.
Truth Tables
Truth tables are used to determine the truth value of a compound statement for all possible truth values of its components. Each row of the table represents a possible combination of truth values, and the final column shows the resultant truth value.
Quine's Method
Quine's method involves translating a logical expression into a normal form, which facilitates the evaluation and simplification of logical expressions. It's a systematic approach to handle logical expressions.
Normal Forms
Normal forms, such as conjunctive normal form (CNF) and disjunctive normal form (DNF), are standard ways of structuring logical expressions. CNF consists of conjunctions of disjunctions, and DNF consists of disjunctions of conjunctions.
Rules of Inference
Rules of inference are logical rules that outline the valid reasoning process to derive conclusions from premises. Common rules include Modus Ponens, Modus Tollens, and Disjunctive Syllogism.
Quantifiers
Quantifiers specify the quantity of specimens in the domain of discourse that satisfy a certain property. The two most common quantifiers are the existential quantifier (there exists) and the universal quantifier (for all).
Recurrence Relations - Formulation, Iteration, Linear homogeneous and non-homogeneous relations, Permutations and combinations
Recurrence Relations
Formulation
Recurrence relations are equations that define sequences recursively by relating terms to previous terms. They can often be expressed in terms of initial conditions and a defined relation that can compute any term based on its predecessors.
Iteration
Iteration involves repeating a process to approximate a solution. For recurrence relations, this means computing terms in the sequence step by step starting from the initial conditions until reaching the desired term or general form.
Linear Homogeneous Relations
Linear homogeneous recurrence relations are expressed as a linear combination of previous terms. They take the form a_n = c_1*a_{n-1} + c_2*a_{n-2} + ... + c_k*a_{n-k}, where c_i are constants and k is the order of the relation.
Non-Homogeneous Relations
Non-homogeneous recurrence relations include an additional term that does not depend on a_n or its predecessors. They can be expressed as a_n = c_1*a_{n-1} + ... + c_k*a_{n-k} + f(n), where f(n) is a function of n.
Permutations
Permutations are arrangements of a set of objects. In the context of recurrence relations, one can relate the number of arrangements of elements to various previously computed terms. The factorial relation often arises in the counting of permutations.
Combinations
Combinations refer to the selection of items from a larger set where the order does not matter. This is represented by binomial coefficients and can be modeled using recurrence relations, for instance, C(n, k) = C(n-1, k-1) + C(n-1, k).
Matrices - Types, Determinants, Inverse, Rank, Solving linear equations, Characteristic equations, Cayley-Hamilton Theorem
Matrices
Types of Matrices
1. Row Matrix: A matrix with only one row. 2. Column Matrix: A matrix with only one column. 3. Square Matrix: A matrix with the same number of rows and columns. 4. Zero Matrix: A matrix in which all elements are zero. 5. Identity Matrix: A square matrix with 1s on the diagonal and 0s elsewhere.
Determinants
1. Definition: A scalar value that can be computed from the elements of a square matrix. 2. Properties: Determinants can help to determine the invertibility of a matrix. 3. Methods: Calculating using row reduction, cofactor expansion, or properties of determinants.
Inverse of a Matrix
1. Definition: The matrix that, when multiplied with the original matrix, yields the identity matrix. 2. Conditions: A matrix must be square and have a non-zero determinant to have an inverse. 3. Methods: Finding the inverse using the formula, using row operations, or using the adjugate method.
Rank of a Matrix
1. Definition: The maximum number of linearly independent row or column vectors in the matrix. 2. Calculation: Determined using row reduction or the number of non-zero rows in the row echelon form.
Solving Linear Equations
1. Representation: Linear equations can be represented in matrix form as AX = B. 2. Methods: Solutions can be found using row reduction, matrix inversion, or Cramer's rule.
Characteristic Equations
1. Definition: An equation that is derived from the determinant of (A - λI) = 0, where A is the matrix, λ is the eigenvalue, and I is the identity matrix. 2. Applications: Used to find eigenvalues and eigenvectors.
Cayley-Hamilton Theorem
1. Statement: Every square matrix satisfies its own characteristic equation. 2. Implications: This theorem is powerful for calculating powers of matrices and solving linear differential equations.
Graphs - Connected graphs, Euler graphs and lines, Hamiltonian circuits and paths, Planar graphs, Complete, Bipartite, Hypercube graphs, Matrix representation
Graphs
Connected Graphs
A connected graph is a type of graph in which there is a path between every pair of vertices. In other words, all vertices are reachable from any other vertex in the graph. A graph that is not connected is called a disconnected graph. Connected graphs can be further categorized into connected components, which are maximal connected subgraphs. Determining connectivity in a graph is a fundamental aspect of graph theory.
Euler Graphs
An Euler graph is a graph in which there exists a closed trail that visits every edge exactly once. Such a trail is termed an Eulerian circuit. For a graph to be an Euler graph, all vertices must have an even degree, and the graph must be connected. If a connected graph has exactly two vertices of odd degree, it contains an Eulerian path, which visits every edge exactly once but does not return to the starting vertex.
Hamiltonian Circuits and Paths
A Hamiltonian circuit is a cycle in a graph that visits every vertex exactly once and returns to its starting vertex. A Hamiltonian path visits every vertex exactly once but does not necessarily return to the starting vertex. Determining whether a Hamiltonian circuit or path exists in a graph is known as the Hamiltonian path problem, which is NP-complete. Various heuristic methods exist to find such paths in specific classes of graphs.
Planar Graphs
A planar graph is a graph that can be drawn on a plane without any edges crossing. Not every graph is planar; for example, the complete graph K5 and the complete bipartite graph K3,3 are examples of non-planar graphs, as established by Kuratowski's theorem. Planarity can be tested using algorithms, and planar graphs can often be represented in the form of a face structure.
Complete Graphs
A complete graph is a type of graph wherein every pair of distinct vertices is connected by a unique edge. A complete graph with n vertices is symbolized by Kn, and it contains n(n-1)/2 edges. Complete graphs are an essential theoretical tool in graph theory and can be used to demonstrate various concepts, including graph coloring.
Bipartite Graphs
A bipartite graph is a graph whose vertices can be divided into two disjoint sets, such that no two vertices within the same set are adjacent. Bipartite graphs can be used to model relationships between two different classes of objects. A complete bipartite graph is denoted as K(m,n), where m and n are the sizes of the two sets.
Hypercube Graphs
A hypercube graph, denoted as Qn, represents the connectivity pattern of a n-dimensional hypercube. The vertices correspond to the binary representations of the numbers from 0 to 2^n-1, and vertices are connected if their binary representations differ by exactly one bit. Hypercube graphs are important in computer science for parallel computing and network design.
Matrix Representation of Graphs
Graphs can be represented using several types of matrices, the most common being the adjacency matrix and the incidence matrix. An adjacency matrix is a square matrix used to represent a finite graph, with rows and columns indexed by the graph's vertices, where the cell entry indicates whether pairs of vertices are adjacent. An incidence matrix represents the relationship between vertices and edges; it is particularly useful for bipartite graphs and in algorithm implementations.
