Discrete Structure PDF

Combinatorial Analysis – An important DISCRETE STRUCTURE problem – solving skill is the ability to count PRELIMS or enumerate objects; it includes the...

Combinatorial Analysis – An important DISCRETE STRUCTURE problem – solving skill is the ability to count PRELIMS or enumerate objects; it includes the discussion of basic techniques of counting.. FORMAL LOGIC Discrete Structures – a course in discrete mathematics should teach students how to INTRODUCTION TO LOGIC work with discrete structures, which are the abstract mathematical structures used to Mathematics can be broadly classified into represent discrete objects and relationships two categories − between these objects. These discrete structure include set, permutations, relations,  Continuous Mathematics - based graphs, trees, and finite – state machines. upon continuous number line or the real numbers. It is characterized by the fact Algorithmic Thinking – certain classes of that between any two numbers, there problems are solved by the specification of an are almost always an infinite set of algorithm, Aftermath, an algorithm has been numbers. For example, a function in described a computer program can be continuous mathematics can be plotted constructed implementing it. in a smooth curve without breaks. Application and Modeling – Discrete  Discrete Mathematics - on the other mathematics has applications to almost hand, involves distinct values; i.e. every conceivable area of study. There are between any two points, there are a many applications to computer science and countable number of points. For data networking. example, if we have a finite set of objects, the function can be defined as a list of WHAT IS A LOGIC? ordered pairs having these objects, and can be presented as a complete list of Logic is technically defined as “the science or those pairs. study of how to evaluate arguments and reasoning.” Discrete Mathematics - is a branch of mathematics involving discrete elements that Logical reasoning it is used in mathematics uses algebra and arithmetic. It is increasingly to prove theorems. being applied in the practical fields of mathematics and computer science. It is a Mathematical Logic ( symbolic logic ) it is very good tool for improving reasoning and a branch of mathematics with close problem-solving capabilities. connections to computer science. Four (4) Divisions GOALS OF DISCRETE MATHEMATICS 1. Set Theory 2. Model Theory Mathematical Reasoning – Students must 3. Recursion Theory understand mathematical reasoning in order 4. Proof Theory to read, comprehend and construct mathematical arguments. It includes the discussion of mathematical logic which serves as a foundation for the subsequent discussion of method of proof. MATHEMATICAL LOGIC Six (6) main logical connectives Definition: Methods of reasoning, provides rules and techniques to determine whether 1. CONJUNCTION an argument is valid The conjunction of p and q, written p ^ q , is the statement formed by joining statements p Theorem: a statement that can be shown to and q using the word “and” be true (under certain conditions) A statement, or a proposition, is a declarative sentence that is either true or false, but not both Uppercase letters denote propositions 2. DISJUNCTION Let p and q be statements. The disjunction of p and q, written p v q , is the statement formed by joining statements p and q using Truth value the word “or” The statement p v q is true if One of the values “truth” (T) or “falsity” (F) at least one of the statements p and q is true; assigned to a statement otherwise p v q is false The symbol v is read “or” LOGICAL CONNECTIVES Proportional Variable it is a variable which used to represent a statement. Logical connectives are used to combine simple statement which are referred as compound statement. Compound statement it is a statement 3. NEGATION composed of two or more simple statements The negation of the statement p is denoted connected by logical connectives. (and, or, if by ~ p where ~ is the symbol for not. then, not, if and only if, exclusive – or) If p is true, the symbol ~ is read as not. , ~ is Simple (atomic) statement a statement false. which is not compound. 4. CONDITIONAL / IMPLICATION Let p and q be statements. The statement “if 6. EXCLUSIVE -OR p then q” is called an implication or The exclusive – or of the statement p and q is condition. the compound statement p exclusive – or q. The conditional statement p -> q is false only Symbolic, p xor q, where xor is the symbol for when p is true and q is false. exclusive or. The implication “if p then q” is written p -> q If p and q are true or both false, then p xor q is false; if p and q have opposite truth values, p is called the hypothesis, q is called the then p xor q is true. conclusion Precedence of logical connectives is: ~ highest ^ second highest 5. BI-CONDITIONAL / BI-IMPLICATION v third highest Let p and q be statements. The statement “p → fourth highest if and only if q” is called the bi-implication ↔ fifth highest or bi-conditional of p and q Three (3) important classes of compound If p and q are true or both false, then p statement: q is true; if p and q have opposite truth values, then p q is false. 1. Tautology is a compound statement that is true for all possible combinations of the The bi-conditional “p if and only if q” is truth values of the propositional variables written p q “p if and only if q” also called logical true. 2. Contradiction is a compound statement The converse of this implication is written that is false for all possible combinations of q → p. the truth values of its propositional variables If I wash the car, then today is Sunday also called logically false or absurdity. The inverse of this implication is written 3. Contingency is a compound statement ~p→ ~q. that can be either true or false depending on If today is not Sunday, then I will not wash the truth values of the propositional variables the car are neither a tautology nor a contradiction. The contrapositive of this implication is written ~q →~p. Logical Equivalence If I do not wash the car, then today is not Sunday Logically Implies A statement formula p is said to logically imply a statement formula q if the statement SETS formula p → q is a tautology. If p logically is an unordered collection of object or a implies q, then symbolically we write p → q. collection of elements. A statement formula p is said to be logically SET THEORY equivalent to a statement formula q if the created by a German Mathematician born statement formula p ↔ q is a tautology. If p is in Russia named Georg Ferdinand Ludwig logically equivalent to q, then symbolically Philip Cantor we write p q. -objects in a set are also called the elements or members of the set. a set is said to contain its elements Describing a set: {x, y, z} P = {c, c++, java} E = {2, 4, 6, 8, 10, 12, 14} {1, a, Ted, Beth, Philippines} {1, 2, 3,...150} Two sets are equal if and only if they have the same elements {a, b, c} = {c, a, b} {1, 2, 3, 3, 4, 5, 5, 6} = {1, 2, 3, 4, 5, 6} Variation of Conditional Statement Set Builder Notation O = { x | x is an odd positive integer less than Implication 15} Let p: Today is Sunday and q: I will wash the R = { x | x is a real number} car. V = { x | x is a vowel } Conditional : p → q : If today is Sunday, then I will wash the car VENN DIAGRAM The cardinality of a set is a measure of the number of elements of the set.  developed by John Venn The cardinality of S is denoted by |S |.|∅ |  method of using diagrams to illustrate set theory A set is said to be infinite if it is not finite. Infinite sets may be countable or uncountable.  the Universal Set U contains all objects under consideration. UNION U  represented using a rectangle.  inside rectangle, circles or other geometric figures are used to represent sets.  sometimes points are used to represent the particular elements of the set.  often used to indicate the relationships between sets.  Another notation to describe INTERSECTION membership in sets by writing a ∉ (element of) and ∉ (not an element of)  Set with no elements is called the empty set or null set, denoted by ∅ or {} singleton set; {∅ }  The set A is a subset of B if and only if every element of A is also an element of B. COMPLEMENT OF C DIFFERENCE LAW ON SETS SYMMETRIC DIFFERENCE ⊕ PROPERTIES AND RELATIONSHIPS OF SET THEORY There are three ways to describe a set: 1. We can use Words. N is the set of natural numbers or counting numbers. 2. We can make a List. N = {1, 2, 3,...} PROBLEMS ON SET 3. We can use Set-Builder Notation. N = {x | x ∉ N} Roster notation B = {6, 7, 8, …..}  A finite set has a limited number of PERFORMING OPERATIONS OF SETS AND members. SUBSETS Example: The set of students in our Math class. DIFFERENCE OF TWO SETS How to find the difference of two sets?  An infinite set has an unlimited number If A and B are two sets, then their difference of members. is given by A - B or B - A. Example: The set of integers. If A = {2, 3, 4} and B = {4, 5, 6} A - B means elements of A which are not the  A well-defined set has a universe of elements of B. objects which are allowed into ie., in the above example consideration and any object in the A - B = {2, 3} universe is either an element of the set B - A = {5, 6} or it is not. Let A = {a, b, c, d, e, f} and B = {b, d, f, g}.  In set theory, the universe of discourse is (i) A - B = {a, c, e} called the universal set, typically Therefore, the elements a, c, e belong to A designated with the letter U. but not to B (ii) B - A = {g) Therefore, the element g belongs to B but not COMPLEMENTS OF A SET A. Given three sets P, Q and R such that: P = {x : x is a natural number between 10 and 16}, Q = {y : y is a even number between 8 and 20} and R = {7, 9, 11, 14, 18, 20} P - Q = {11, 13, 15} Q – R = {10, 12, 16} SUBSETS OF A SET R - P = {7, 9, 18, 20} Q – P = {10, 16, 18} CARDINALITY Definition: Let S be a set. If there are exactly n distinct elements in S, where n is a nonnegative integer, we say S is a finite set and that n is the cardinality of S. The cardinality of S is denoted by | S |. Examples: V={1 2 3 4 5} | V | = 5 A={1,2,3,4,..., 20} |A| =20 |Ø|=0  NUMBER THEORY TYPES OF NUMBERS COUNTING NUMBERS are positive whose numbers excluding zero. Ex. 1, 2, 3, 4, 5, 6, …… WHOLE NUMBERS are positive integers including zero. Ex. 0, 1, 2, 3, 4, 5, 6,…… Let A={1,2,3,4} and INTEGERS Let B={3,4,5,6}. are numbers formed by the natural Find: A∩B, A∪B, A−B, and AC numbers including zero together with the negatives of the non – zero natural numbers. Then: Ex. … -4, -3, -2, -1, 0, 1, 2, 3, 4, … A∩B={3,4} A∪B={1,2,3,4,5,6} RATIONAL NUMBERS A−B={1,2} are numbers that can be written as fraction AC={all real numbers except 1,2,3 and 4} and whose numerators and denominators are integers provided that the denominator is not equal to 0. Let A={y,z} and Ex. 1/2, 1/5, 3/4 Let B={x,y,z}. Find: A∩B, A∪B, A−B, and AC IRRATIONAL NUMBERS are numbers that can be written as non Then: terminating and non repeating decimal. A∩B={y,z} Ex. pi(π=3⋅ 14159265…), A∪B={x,y,z} √2, √3, √5, A−B=∅ Euler's number (e = 2⋅ 718281…..) AC={everything except y and z} REAL NUMBER Always perform any operations inside are numbers comprised of all rational and parenthesis first! irrational numbers. Given: Ex. Ex. 1/2, 1/5, 3/4 U = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10} pi(π=3⋅ 14159265…), A = { 1, 3, 7, 9 } √2, √3, √5, B = { 3, 7, 8, 10 } Euler's number (e = 2⋅ 718281…..) Find: IMAGINARY NUMBERS (A U B)’ is the square root of negative one. Any real A’ ∩ B’ number times i is an imaginary number. Ex. COMPLEX NUMBERS are the combination of real numbers and imaginary numbers. Ex. ODD NUMBER DIVISION ALGORITHM is a number when divided by 2 contains a remainder of 1. Division Algorithm Ex. 1, 3, 5, 7, 9, 11, 13,.… Is an effective method for producing such quotient and remainder. EVEN NUMBERS is a number divisible by 2. There are numbers of algorithm such as decimal notation of integers, long division Ex. 2, 4, 6, 8, 10, 12, 14, … which provides an efficient division algorithm. PRIME NUMBERS The integer division algorithm is an is a natural numbers greater than 1 that important procedure for other algorithm, has no positive divisors other than1 and itself. such as Euclidian algorithm for determining Ex. the greatest common divisor of any pair of integers. EUCLIDEAN ALGORITHM : a = qb +r ; a = bq + r Determine the greatest common divisor of 372 and 132. COMPOSITE NUMBERS is a positive integer which has a positive divisor other than 1 or itself. In other words a composite number is any positive integer greater than 1 that is not a prime number. Ex. PERFECT NUMBERS is a positive integer that is equal to the sum of its proper positive divisors, that is, the sum Solve for the GCD of 108 and 87. of its positive divisors excluding the number itself. Ex. Find the least common multiple of the following: a. (12, 18) b. (90, 108) c. (24, 36, 108) ♥RYRY 2024♥