Data Loading...
DISCRETE MATHEMATIC Flipbook PDF
P4 AINURFARISHAH (265003), NURHIDAYAH (265050)
118 Views
66 Downloads
FLIP PDF 14.83MB
JUST DO IT Discrete Mathematics
Graph Theory
Number Theory
Logic and Proof
Boolean Algebra
BY: AINUR FARISHAH BINTI AHMAD ZULKIFLY (265003) NUR HIDAYAH BINTI MOHD RUSLI (265050)
There are many questions that play on the mind for the students to choose their subject. This always happened during the add drop period. Some universities already provided the timetable to the student for the whole semester but there are some universities require the student to make the scheduled by themselves.
“What courses that easy to score” or "what interesting subject to take” are the few question that the students always asked to their friends before the making the scheduled. This problem usually happened to students who are taking minor subject due to lack of the knowledge for the subject. This is because they do not very familiar with the subject. For the major courses, they can ask their senior or friends about the subject but for the minor courses, to do so quite difficult.
In this magazine discuss in detail about Discrete Math. One of the subjects for the student who are taking Mathematics as the minor course. Discrete Math or SQQM1034 is the code for this subject. To take this subject, there are none prerequisite, so students does not have to worry about either to take it first or last. In this subject, there are 5 chapters to be learned. In this magazine showed the summary for each chapter. With this, students can take a look at each of the chapter to know better about this subject before taking it.
TTEE E E R R IISSCC D D TT IISS H A A H TTH?? A W A WH M M
WHAT IS GRAPH THEORY? A graph is a set of points identified as vertices and a number of lines. Moving a few points, called the edges. When G is a graph, we can write G(V) and G(E) respectively for the vertices and the edges. Simple graph is referred to as a graph without multiple edges or lines. In the setting of simple graphs, several natural problems make sense only. If the edge connects two vertices it's called adjacent.
Graphs are shown as G= (V,E) sets, in which V is the vertices set and E the edge set.
DIRECTED GRAPH
UNDIRECTED GRAPH
If at most one edge is present from one vertex to another, a directed graph is simple. A graph directed from a vertex u to another vertex v is referred to as a directing multigraph.
Every edge is a two-element subset of V in an undirected graph. Undirected graph does not contain multiple edges or lines (the edge from the graph). A multigraph is considered a graph that has more than one edge between the two vertices. We mean typically a simple undirected graph when we say graph.
The degree of a vertex v, written in d(v), is the number of edges that connect to the vertex.
HANDSHAKING THEOREM IN GRAPH THEORY Handshaking Theorem is also known as Handshaking Lemma or Sum of Degree Theorem.
TYPES OF GRAPHS Null Graph
Connected graph
Disconnected graph
Since the vertex is the number of edges that appear with this vertex, the number of times that a vertex appears is counted.
In a graph, the total number of vertices is even.
Since each edge has two vertices, every edge is counted twice at every edge. The degree numbers are twice as high as possible.
Bipartite graph
Weighted graph
Isomorphism of Graphs Two graphs are defined as isomorphic when a bijective function occurs from the vertices set in the first graph to the vertices set in the second graph, so that the adjacency connection is preserved (if two vertices are adjacent and their images are adjacent)
A TREE A tree is a connected undirected graph with
No simple circuits
No multiple edges No loops
When one to one (a bijection) functions f are located between vertices G and H in order to have a border between vertices u and v in G only when there is one border between vertices f(u)and f(v) in H. Two graphs G and H are isomorphic
Adjacency Matrix
Any tree must then be a simple graph. An undirected graph is a tree only if there is a single, simple path between two vertices.
SPANNING TREE The spanning tree is a graph with a minimal number of edges on all vertices.
The adjacency matrix, also known as a connection matrix, is a matrix comprising rows, columns and a simple mark-up graph, 0 or 1 in position (Vi, Vj) based on whether or not Vi and Vj are adjacent.
A minimum spanning tree that has the smallest possible sum weight of its edges is a minimal twist of a connected weighted graph. + Prim Algorithms + Kruskal's Algorithms
GRAPH COLORING The four colors theorem states that no more than four colors will color a maps which is a division of the plane into any number of areas in such a way that no two adjacent regions share the same color.
NUMBER THEORY
ERASTOTHENES (276-194 B.C.)
In this topic of number theory discuss about the integers and their properties. There are many subtopic that will be dicussed further such as; Divisibility and Modular Artihematic
EUCLID (325– 265 B.C.E.)
Prime and Greatest Common Divisors Cryptography From this subtopic, cryptography is the common one to be used in the real life as the application.
PAUL ERDŐS (1913-1996)
CRYPTOGRAPHY Cryptography is used as one way to secure information and communications by the use of passwords(codes), so that it can be only read and interpreted by the person secretly. The term "cryptography" is derived from the Greek kryptos giving the meaning of hidden. The first use of a modern cypher was by Julius Caesar who dealing with his governors and officers and he did not trust his messengers. For this purpose, he developed a scheme in which a character three positions ahead of it in the Roman alphabet was substituted for each character in his messages.
ÉTIENNE BÉZOUT (1730-1783
LOGIC AND PROOFS The logic of proposition involves statements to which the "true" and "false" values can be related. The logic of proposal These statements must be evaluated separately or in a composite way.
LOGICAL EQUIVALENT If, and only if, two statement types is logically called equivalent on any possible replacement of theirs, they have the same true values variables statement.
AUGUSTUS DE MORGAN (1806 - 1871)
Here are few examples of propositions: "Ahmad is a man", it returns truth value “TRUE”
"15 + 5 = 8 - 1", it returns truth value “FALSE”
Some examples of non-Propositions are given below: "A is less than 2". It is because unless we give a specific value of A, we cannot say whether the statement is true or false.
If a statement is true it is false and if the statement is false it is true. This can be seen as a table called a 'truth table.'
Only when all simple statements are true is a conjunction true.
A disjunction is false only when both component statements are false.
TAUTOLOGY
ARISTOTLE (384 B.C.E. - 322 B.C.E.) The converse of the conditional statement is "If Q then P"
GEORGE BOOLE (1815 - 1864)
The contrapositive of the conditional statement is "If not Q then not P"
The inverse is the "If not P then not Q" statement. JOHN WILDER TUKEY (1915 - 2000)
A tautology is a form of statement often valid regardless of the values of the truth of the different statements that have replaced its variables.
PREDICT AND QUANTIFIER Predicate logic is a proposition logic extension. It contributes the concept of predicates and quantifiers to better understand the meaning of statements that cannot be expressed adequately by proposing logic.
RULES OF INFERENCE For logical proof, mathematical logic is also used. Proof is objective argument that defines mathematical statements' truth values. A set of statements is an argument. The final declaration is the conclusion and all its previous statements are called premises (or hypothesis). Until end, the symbol " "(read therefore).
∴
Quantifiers quantify the predicate variable. In predicate logic there are two different types of quantifiers which are Universal and Existential Quantifier.
All values in a particular element are declared true by Universal Quantifier. It is denoted by the symbol .
∀
The Existential Quantifier states that only certain values in the specific variable are valid for the statements within its scope. It is denoted by the symbol .
∃
PROOFS A proof is a valid argument that supports the validity of a mathematical assertion. Proof can use axioms presumed to be valid and pre-proven theorems, as the hypotheses of theorem, if any. The final step in the proof is to determine the validity of the statement using these ingredients and rules of inference.
Direct Proofs Suppose that p is true and then show q (using axioms, definitions).
Proof by Contraposition A proof that p implies q is true to prove that p must be false if q is false.
Some Terminology The less important theorems are propositions The statement that is true is called axioms A less relevant theorem to explain a theorem is known as a lemma A theorem explicitly demonstrable from a proved theorem is known as a corollary.
BOOLEAN ALGEBRA
Identities of Boolean Functions
Boolean algebra approaches variables with two values, 0 and 1 [false] (True). George Boole is the person who discovered the method of controlling symbolic logic and to be known as Boolean Algebra till now.
Boolean Functions There are three operations used: Complementation Boolean sum( + / OR) Boolean product ( × / AND)
Logic Gates In the real life, Boolean Algebra is used as the model of the circuit for the electronic device. In the logic gates, the input and ouput can be represent as (0,1). AND GATE
OR GATE
NOT GATE
REFERENCES