Discrete Maths PDF

Demystifying Discrete Maths Discrete Maths Distinct & countable objects Dealing with things you can count,not things which smoothly flow So, think of discrete math as the superhero of counting and arranging things Why is it necessary? Discrete Math is the language of logic Forms the...

Demystifying Discrete Maths Discrete Maths Distinct & countable objects Dealing with things you can count,not things which smoothly flow So, think of discrete math as the superhero of counting and arranging things Why is it necessary? Discrete Math is the language of logic Forms the groundwork for algorithms The Superhero’s sidekick Mathematical Proof Proof is the verification of Propositions by a chain of Logical deductions from a set of Axioms Proof Start with a claim Hey! I think this is true,Let me show you why You start saying things everyone agrees Finally, you conclude by saying Based on all that we Take small Logical steps and end up proving an idea know,my idea is true Example Start with a claim Claim: Sum of 2 even numbers Hey! I think this is true,Let me show you why is always even - Sum of 4 and 6 is even You start Assumption: even number can saying things be written as 2×some integer everyone agrees Finally, you conclude by saying Based on all that we Take small Logical steps and end up proving an idea know,my idea is true Logic: The sum of our even numbers (4 + 6) can be expressed as 2×(2+3) 2×(2+3), is clearly a multiple of 2. Proposition Logic is a system based on propositions. A proposition is a (declarative) statement that is either true or false (not both). We say that the truth value of a proposition is either true (T) or false (F). Corresponds to 1 and 0 in digital circuits Understanding Propositions “Elephants are bigger than mice” Is this a Statement? Yes Is this a Proposition? Yes Truth value of the Proposition? True Understanding Propositions “ 500 < 154 ” Yes Is this a Statement? Is this a Proposition? Yes Truth value of the Proposition? False Understanding Propositions “Please don't fall asleep ” Is this a Statement? No, Request Is this a Proposition? No,Only statements can be proposition “x < y if and only if y > x.” Is this a Statement? Yes Is this a Proposition? Yes,truth value depends on X and Y Combining Propositions 1 or more propositions can be combined using Logical conjectures Combining Propositions 1 or more propositions can be combined using Logical conjectures Implication Implication is like a promise. If someone says, "If I finish my homework, then I can play video games," it means that if they finish their homework (P is true), they will play video games (Q is true). However, if they don't finish their homework (P is false), we can't be sure whether they will play video games or not. So, implication (P → Q) means that if P is true, then Q must also be true. But if P is false, we don't know anything about Q. Biconditional The biconditional is like a mutual agreement. Imagine two friends saying, "We'll meet at the park if and only if it's sunny." This means they will meet at the park only if it's sunny, and they will meet nowhere else. Also, if they do meet, it's because it's sunny. So, the biconditional (P ↔ Q) means that if P is true, then Q must also be true, and if Q is true, then P must also be true. Both conditions are linked together. Converse, Inverse and Contrapositive Not fundamental connectives, but derived from Implication Let’s consider the conditional, “If you live in LA, then you live in California” If P then Q - Implication connective Converse will be doing a flip flop of the cause and effect relationship If Q, then P Inverse “If you live in California, then you live in LA” Negation of the conditional statement - If ~P then ~Q “If you dont live in LA, then you dont live in CA” Contrapositive - Reverse negation of conditional statement - If ~Q then ~P If you dont live in CA,then you dont live in LA Converse, Inverse and Contrapositive Conditional “If I'm Hungry,then I will eat Dosa” Converse:- “If I eat Dosa, then I’m Hungry” Inverse:- “If I’m not hungry,then I will not eat Dosa” Contrapositive:- “If I dont eat Dosa, then I’m not hungry” Axioms A mathematical statement which we assume to be true without a proof is called an axiom. These are truths that form the basis for all other derivations and have been derived from the basis of everyday experiences. There is no evidence opposing them. Tautology, Contradiction, Contingency and Satisfiability Tautology:- Contradiction A compound proposition which is A compound Proposition which is always True always False P ~P PV~P P ~P P^~P T F T T F F F T T F T F Examples - Axioms Tautology, Contradiction, Contingency and Satisfiability Contigency Satisfiability A compound proposition which is A compound Proposition is sometimes T and sometimes F satisfiable if there is atleast one true result in the truth table P Q P^Q Tautology - always satisfiable T F F T T T Contradiction always unsatisfiable F T F Compound proposition is valid if its a tautology, invalid if its a contradiction/contingency F F F Predicate Logic/ FOPL Predicate Logic is an extension of Propositional Logic Includes concepts of Predicate,Quantifiers Predicate - Relation between 2 objects “X is an animal” - X= Subject is an animal = Predicate Short hand Notation :- animal(x) X is greater than 3 = G(x), G(5) - True  Quantifiers Quantifiers are used to define scope/range of the objects Universal Quantifier : “For all” Objects symbol: ∀ Existential Quantifier : “There exists,” symbol: ∃ Person A likes Mangoes( Obj 1 - Person A ; Obj2 - Mango; Relationship : likes ∀x likes(x,Mango) = All X likes Mango ~∃x ~likes(x,Mango) = There does not exist at least 1 x who does not like Mango Methods to ascertain Truth Direct Proof Contradiction Induction/ Strong Induction Methods to ascertain Truth Direct Proof We use it to prove statements of the form ”if p then q” or ”p implies q” which we can write as p ⇒ q. Directly prove that if m and n are odd integers then mn is also an odd integer. Assume that m and n are odd integers. Then by definition m = 2k + 1 for some integer k and n = 2l + 1 for some integer l. mn = (2k + 1)(2l + 1) m and n = 4kl + 2k + 2l + 1 Hence we have shown that mn has the form of an odd integer since 2kl + k + l is an integer Methods to ascertain Truth Contradictive Proof We use direct arguments to prove the truth of the statement. Sometimes, we use indirect arguments to prove the statement using “Proof by Contradiction” A contradiction occurs when we get a statement p, such that p is true and its negation ~p is also true Let a+b = c+d, and ad using the proof by contradiction method. Methods to ascertain Truth Mathematical Induction Mathematical induction, is a technique for proving results or establishing statements for natural numbers. The technique involves two steps to prove a statement, as stated below − Step 1(Base step) − It proves that a statement is true for the initial value. Step 2(Inductive step) − It proves that if the statement is true for the nth iteration (or number n), then it is also true for (n+1)th iteration ( or number n+1). Mathematical Induction Mathematical Induction Step 1: The first Domino falls Step 2: The next Domino falls all Domino falls Step 1:Show it is true for n=1 Step 2: Assume it is true for n=k Prove that 3k+1−1 is a multiple of 2 3k+1 is also 3×3k And then split 3× into 2× and 1× is 3n−1 a multiple of 2? 3k+1−1 =(2x3k) + (1x 3k ) -1 =(2x3k) + (3k -1) (3k -1) - assumed as a multiple of 2 in the inductive step (2x3k) - multiple of 2 since we are multiplying it by 2 Therefore the entire expression 3k+1−1 is a multiple of 2 This completes the proof for the inductive step, showing that if the statement holds for n=k, it also holds for n=k+1. Strong Induction Induction Strong Induction Imagine you have a set of dominoes, and each Now, imagine instead of just saying the domino represents a statement. next domino will fall, you say, If you can show that the first domino falls "If any domino falls, not only will the next (base case) and that if any domino falls, the one fall, but every other domino after it next one will also fall (inductive step), then you will fall too." can be sure all the dominoes will fall. strong induction lets you assume that the statement holds for all the dominoes up to a certain point, not just the one right before the next one. Strong Induction Normally, when using induction, we assume that P(k) is true to prove P(k+1). In strong induction, we assume that all of P(1),P(2),...,P(k) are true to prove P(k+1). is 3n−1 a multiple of 2? Induction Strong Induction Assume it is true for n=k: Assume it is true for all positive integers Assume that 3k−1 is a multiple of 2. up to n=k: Prove it for n=k+1: Show that Assume that for every n from 1 to k, the 3k+1−1 is a multiple of 2. expression 3n−1 is a multiple of 2. Prove it for n=k+1 Show that 3k+1−1 is a multiple of 2. Disproof Techniques Disproof Techniques Thank You