Maths for Computer Science PDF

Maths for Computer Science Micro-Credit Program in Computer Science Dr.Srinivasan Krishnaswamy Daksh Gurukul - IIT Guwahati Cohort-2406 Session-N Logic and Proofs Daksh Gurukul - IIT Guwahati List of Topics Propositions and Logical Operators...

Maths for Computer Science Micro-Credit Program in Computer Science Dr.Srinivasan Krishnaswamy Daksh Gurukul - IIT Guwahati Cohort-2406 Session-N Logic and Proofs Daksh Gurukul - IIT Guwahati List of Topics Propositions and Logical Operators Conditional Statements Predicates and Quantifiers Proofs Daksh Gurukul - IIT Guwahati Proposition Proposition Statement that is either True or false Examples 1 New Delhi is the capital of India. 2 Mumbai is the capital of Sri Lanka 3 1+1=2 4 2+2=3 Daksh Gurukul - IIT Guwahati Proposition What is not a proposition Questions or Instructins. x +1=2 Daksh Gurukul - IIT Guwahati Logical Operators Logical Operators Helps create new propositions from propositions. ¬p - negation p ∨ q - disjunction p ∧ q - conjunction p ⊕ q - EX-OR Daksh Gurukul - IIT Guwahati Logical OPerators ∨ p q p∨q T T T T F T F T T F F F Daksh Gurukul - IIT Guwahati Logical OPerators ∧ p q p∧q T T T T F F F T F F F F Daksh Gurukul - IIT Guwahati Logical OPerators ⊕ p q p⊕q T T F T F T F T T F F F Daksh Gurukul - IIT Guwahati Conditional Statements If — then — p → q. p is the hypothesis/anticedent/premise. q is the conclusion/consequence. Daksh Gurukul - IIT Guwahati Conditional Statements → p q p→q T T T T F F F T T F F T Daksh Gurukul - IIT Guwahati Conditional Statements p→q Converse: q → p Contrapositive: ¬q → ¬p Inverse: ¬p → ¬q Biconditional:p ↔ q Daksh Gurukul - IIT Guwahati Conditional Statements ↔ p q p↔q T T T T F F F T F F F T Daksh Gurukul - IIT Guwahati Logical Equivalence Tautology: A statement that is always true. Contradiction: A statement that is always false A statement that is neither a tautology or a Contradiction is called a contingency. Two propositions p and q are said to be logically Equivalent if p ↔ q is a tautology. Daksh Gurukul - IIT Guwahati Logical Equivalences De Morgans laws ¬(p ∧ q) ≡ ¬p ∨ ¬q ¬(p ∨ q) ≡ ¬p ∧ ¬q Daksh Gurukul - IIT Guwahati Logical Equivalences Other logical equivalences p → q ≡ ¬plorq (Disjunction Equivalence) p ∨ (q ∧ r ) ↔ (p ∨ q) ∧ (p ∨ r ) (Distributivity) (p ∨ q) ∨ r ≡ p ∨ (q ∨ r (p ∧ q) ∧ r ≡ p ∧ (q ∧ r (Associativity). p ∨ (p ∧ q) ≡ p p ∧ (p ∨ q) ≡ p (Absorption) Daksh Gurukul - IIT Guwahati Satisfiability A proposition is satisfiable if it is true for some set of assignment of truth values. It is generally a difficult problem to check satisfiability. Daksh Gurukul - IIT Guwahati Predicates and Quantifiers Predicates x >3 x is the subject. > 3 is the predicate. When a value is given to a subject, the statement becomes a proposition. If p(x) denotes x > 3, P(4) is T and P(2) is F Daksh Gurukul - IIT Guwahati Predicates and Quantifiers Universal Quantifiers Universal Quantifier: Forall (∀) Universal Quantifier of the statement P(x), ∀xP(x), is the following statement, ”P(x) for all values of x in the domain” Can be used with restrictions. For example ∀x > 0P(x). A false value of P(x) is called a counterexample of the universal quantifier. Daksh Gurukul - IIT Guwahati Predicates and Quantifiers Existential Quantifiers There exists ∃, ∃xP(x): There exists some x such that P(x) is true. ∃x∀y ∀z(F (x, y ) ∧ F (x, z) ∧ (y ̸= z) → ¬F (y , z) ?? F (a, b) is the statement a and b are friends. Daksh Gurukul - IIT Guwahati Predicates and Quantifiers Existential Quantifiers There exists ∃, ∃xP(x): There exists some x such that P(x) is true. ∃x∀y ∀z(F (x, y ) ∧ F (x, z) ∧ (y ̸= z) → ¬F (y , z) ?? F (a, b) is the statement a and b are friends. There is someone whose no two friends are friends. Daksh Gurukul - IIT Guwahati Predicates and Quantifiers Logical Equivalence with Quantifiers ¬∀xP(x) ≡ ∃x¬P(x) ¬∃xP(x) ≡ ∀x¬P(x) These are De Morgan’s laws for Quantifiers Daksh Gurukul - IIT Guwahati Proofs What is a proof A sequence of arguments that establish that a statement is true Uses logical equivalences and Rules of Inference Three types Direct, Contraposition and Contradiction. Daksh Gurukul - IIT Guwahati Proofs Rules of Inference Rule of Inference Tautology Name p p ∧ (p → q) → q Modus Ponens p→q ∴q ¬q ¬q ∧ (p → q) → ¬p Modus Tollens p→q ∴ ¬p p→q (p → q) ∧ (q → r ) → (p → r ) Hypothetical Syllogism q→r ∴p→r Daksh Gurukul - IIT Guwahati Proofs Rules of Inference Rule of Inference Tautology Name p∨q (p ∨ q) ∧ ¬p → q Disjunctive syllogism ¬p ∴q p p → (p ∨ q) Addition ∴p∨q p∧q (p ∧ q) → p Simplification ∴p Daksh Gurukul - IIT Guwahati Proofs Rules of Inference Rule of Inference Tautology Name p ((p) ∧ (q)) → p ∧ q Conjunction q ∴p∧q p∨q (p ∨ q) ∧ (¬p ∨ r ) → (q ∨ r ) Resolution ¬p ∨ r ∴q∨r Daksh Gurukul - IIT Guwahati Proofs Types of Proofs Direct Proof: To prove p → q assume that p is true and show that q is always true. Contraposition Proof: To prove p → q assume ¬q and show that ¬p is always true. Contradiction Proof: To prove p, we show that p → (r ∧ ¬r ) for some statement r. Daksh Gurukul - IIT Guwahati