Logic & Reasoning PDF - 1st Year Preparatory Classes, HEC, Algeria, September 2023

MINISTRY OF HIGHER EDUCATION AND SCIENTIFIC RESEARCH 1s t year preparatory classes Algebra 1 - Semester 1 Chapter 01 Logic & Reasoning Dr. K.AGGOUN...

MINISTRY OF HIGHER EDUCATION AND SCIENTIFIC RESEARCH 1s t year preparatory classes Algebra 1 - Semester 1 Chapter 01 Logic & Reasoning Dr. K.AGGOUN September 2023  Contents 1 Preliminaries 3 2 Logical operations 4 2.1 Negation.................................................. 4 2.2 The conjunction............................................. 4 2.3 The disjunction............................................. 4 2.4 Implication................................................ 4 2.5 Equivalence (biimplication or biconditional)........................ 5 3 Quantifiers 6 3.1 The Universal Quantifier....................................... 6 3.2 The Existential Quantifier...................................... 6 3.3 Mixed quantifiers............................................ 7 4 Proofs 7 4.1 Direct proofs............................................... 7 4.1.1 A direct proof......................................... 7 4.1.2 A counter-example...................................... 7 4.2 Indirect proofs.............................................. 8 4.2.1 Proof by Contraposition.................................. 8 4.2.2 Proof by Contradiction................................... 8 4.2.3 Proof by induction...................................... 9 2 1 Preliminaries There is certainly widespread agreement that mathematics is logical. Indeed, properly con- ceived, this may be one of the most important defining properties of mathematics. Logical thought and logical arguments are not easy to come by, nor is it always clear whether a given argument is logical (that is, logically correct). Logic itself deserves study; the right tools and concepts can make logical argument easier to discover and to discern. Mathematics typically involves combining true (or hypothetically true) statements in various ways to produce (or prove) new true statements. We begin by clarifying some of these fundamental ideas. Definition 1. A proposition is a statement that is true or false. Examples : “In 1492 Columbus sailed the ocean blue.” is a True proposition. “Grass is green and roses are blue.” is a False proposition. “13 is not a big number” is a proposition whose truth value depends on the exact definition of big numbers which may vary from a context to another. Non-examples : “What time is it?” Question “Don’t look back!” Order More generally, Definition 2. By a formula we mean a proposition, possibly involving some variables.
Example : If P x , y is the proposition “x |y ” which is read ”x divides y ”, then P (3, 27) is 5 True while P (3, 5) is False. We could have said : 3 × = 5 so P (3, 5) is True! but, in 3 normal usage, the appearance of the formula “x |y ” implies that x , y and the ratio are integers. Whether a sentence is true or false usually depends on what we are talking about, hence we define Definition 3. The universe of discourse for a particular branch of mathematics is a set that contains everything of interest for that subject. Example: D f , the domain of definition of a given function f , is the universe of x. Complicated sentences and formulas are put together from simpler ones, using a small number of logical operations. We want to study (mathematical) logic without being dis- tracted by the concrete contents of propositions, so we use letters and symbols as follows : Propositional variables : P,Q , R... Connectives : ¬, ∧, ∨, ⇒, ⇔. In the first example above, the three first propositions are, respectively, of the form: (P ) , (P ∧ Q ) and (¬P ). 3 2 Logical operations Just a handful of these operations will let us say everything we need to say in mathematics. 2.1 Negation If P is a formula, then ”not P ” is another formula, which we write symbolically as ¬P or P. Of course, ¬P is false if P is true and vice versa. P ¬P Truth table for ¬ is : 0 1 ; 0 = false and 1 = true. 1 0 Example: “6 is not a prime number” or ¬(6 is prime) Remark. ¬ is the only unary operator (uses 1 operand). Suppose that P and Q are formulas, then we define 2.2 The conjunction “P and Q ” is a formula written symbolically as P ∧ Q , called the conjunction of P and Q which is true if both P and Q are true, false otherwise. We first list all possible combinations of assignments to P and Q. P Q P ∧Q 0 0 0 Truth table for ∧ is : 0 1 0. 1 0 0 1 1 1 2.3 The disjunction “P or Q ” is written symbolically as P ∨Q , called the disjunction of P and Q. The only way P ∨ Q can be false is if both P and Q are false. P Q P ∨Q 0 0 0 Truth table for ∨ is : 0 1 1. 1 0 1 1 1 1 It is important to note that this is the “inclusive or”. Exercise. Construct the truth table of the exclusive or while giving an example. 2.4 Implication “if P then Q ” or “P implies Q ” is written P =⇒ Q. An implication P =⇒ Q is true if : whenever P is true, then also Q is true; false otherwise. P Q P =⇒ Q 0 0 1 Truth table for =⇒ is : 0 1 1. 1 0 0 1 1 1 4 Attention! “False =⇒ True“ is true logically, for example the statement : “If x is less than 2 then x is less than 4” which can be written “x < 2 =⇒ x < 4” is true regardless of the value of x. For instance, If x = 1, it evaluates to True =⇒ True, if x = 3, it becomes False =⇒ True, and if x = 5, it becomes False =⇒ False. So it appears that P =⇒ Q is true unless P is true and Q is false. This is the rule that we adopt. 2.5 Equivalence (biimplication or biconditional) Finally, the equivalence, written ⇔ , corresponds to the phrase “if and only if” or “iff” for short. So P ⇔ Q is true when both P and Q have the same truth value, otherwise it is false. P Q P ⇔Q 0 0 1 Truth table for ⇔ is : 0 1 0. 1 0 0 1 1 1 Two propositions having the same truth values (on each row) in the truth table are equivalent. De Morgan’s Laws ¨ ¬ (P ∨ Q ) ⇐⇒ (¬P ∧ ¬Q ) ¬ (P ∧ Q ) ⇐⇒ (¬P ∨ ¬Q ) Naming. A proposition is a tautology if its column in a truth table exclusively consists of 1s. A proposition is a contradiction (fallacy) if its column in a truth table exclusively consists of 0s. A proposition is a contingency if it is not a tautology, nor a contradiction. Theorem. The following propositions are valid (tautologies) : a) P ⇔ ¬¬P b) P ∨ Q ⇔ Q ∨ P c) P ∧ Q ⇔ Q ∧ P d) (P ∧ Q ) ∧ R ⇔ P ∧ (Q ∧ R ) e) (P ∨ Q ) ∨ R ⇔ P ∨ (Q ∨ R ) f) P ∧ (Q ∨ R ) ⇔ (P ∧ Q ) ∨ (P ∧ R ) g) P ∨ (Q ∧ R ) ⇔ (P ∨ Q ) ∧ (P ∨ R ) h) (P =⇒ Q ) ⇔ (¬P ∨ Q ) 5 i) P =⇒ (P ∨ Q ) j) P ∧ Q =⇒ Q k) (P ⇔ Q ) ⇔ ((P =⇒ Q ) ∧ (Q =⇒ P )) l) (P =⇒ Q ) ⇔ (¬Q =⇒ ¬P ) The proofs are left as exercises. 3 Quantifiers Recall that a formula is a statement whose truth value may depend on the values of some variables. For example,"x ≤ 5 ∧ x > 3" is true for x = 4 and false for x = 6. Compare this with the statement "For every x , x ≤ 5 ∧ x > 3," which is definitely false and the statement "There exists an x such that x ≤ 5 ∧ x > 3," which is definitely true. The phrase "for every x " (sometimes "for all x ") is called a universal quantifier and is de- noted by ∀x. The phrase "there exists an x such that” is called an existential quantifier and is denoted by ∃x. 3.1 The Universal Quantifier A sentence ∀x : P (x ) is true if and only if P (x ) is true no matter what value (from the uni- verse of discourse) is substituted for x. Example The square of any number is not negative: ∀x : x 2 ≥ 0. Two numbers having the same square are equal:
∀x , ∀y : x 2 = y 2 =⇒ x = y. Note that the truth value of these statements depends on the universe of discourse. 3.2 The Existential Quantifier A sentence ∃x : P (x ) is true if and only if there is at least one value of x that makes P (x ) true. Example ∃x : x ≥ x 2 is true since x = 0 is a solution. There are many others. ∃x :(x is a prime number ∧ x is even), i.e., “some prime number is even.” and x = 2 is the unique one. Remark: We write ∃! instead of ∃ to express existence and uniqueness. There are versions of De Morgan’s laws for quantifiers: ¨ ¬ (∀x : P (x )) ⇐⇒ ∃x : ¬P (x ). ¬ (∃x : P (x )) ⇐⇒ ∀x : ¬P (x ) 6 3.3 Mixed quantifiers In many of the most interesting mathematical formulas some variables are universally quantified and others are existentially quantified, the order of the quantifiers is extremely important. Example:

Compare these two statements: ∀x ∈ R, ∃y ∈ R : x < y and ∃y ∈ R, ∀x ∈ R : x < y. The first one states that “given any number there is a strictly larger number” i.e. “there is no largest number” which is true. The second one says that : “there is a single number that is strictly larger than all real numbers” and this is false. 4 Proofs The idea of proof is central to all branches of mathematics; by using rigorous, logically correct reasoning, we aim to prove mathematical theorems, that is, to demonstrate that something is true beyond all doubt. 4.1 Direct proofs 4.1.1 A direct proof is a sequence of statements which are either givens or deductions from previous state- ments, and whose last statement is the conclusion to be proved. This is generally to prove a statement of the form ∀x : P (x ) ⇒ Q (x ). The language typically employed is "Suppose x satisfies P (x ),” "Assume P (x ),” or "Let P (x ).” Example: Whenever the sum of two integers is even, the sum of their squares is also even. This can be written : ∀a ∈ Z, ∀b ∈ Z : (a + b is even =⇒ a 2 + b 2 is even ). Proof: Let a and b be two integers such that (a + b ) is even. We have : a 2 + b 2 = (a + b )2 − 2a b , which is even as the sum of two even numbers.„ 4.1.2 A counter-example is any exception to a generalization, it is used to disprove a universally quantified formula. Example: n 2 + n + 41 is prime for any natural number. This can be written : ∀n ∈ N : n 2 + n + 41 is prime. Disproof: For n = 41, we have 412 + 41 + 41 = 41 × 43 is composite.„ 7 4.2 Indirect proofs Frequently you will find that it is difficult (or impossible) to prove something directly, but easier (at least possible) to prove it indirectly. 4.2.1 Proof by Contraposition You must have seen the last formula in the above theorem : (P =⇒ Q ) ⇔ (¬Q =⇒ ¬P ) , instead of proving the implication (P =⇒ Q ) directly, we prove its Contrapositive : (¬Q =⇒ ¬P ) which is logically equivalent. Example: Let a , b ∈ N. We have a × b is even =⇒ (a is even ) ∨ (b is even ). Proof: The contrapositive of the above formula is : ¬ ( (a is even ) ∨ (b is even ) ) =⇒ ¬ ( a × b is even ), and by applying the De Morgan’s rule it becomes : (a is odd ) ∧ (b is odd ) =⇒ a × b is odd, which is much easier to prove. Indeed, Assume both a and b are odd, that is : a = 2x + 1 and b = 2y + 1 for some natural ! numbers x and y. Consequently, a × b = 2 2x y + x + y + 1 which is obviously odd.„ | {z } z 4.2.2 Proof by Contradiction To prove a sentence P by contradiction we assume ¬P and derive a statement that is known to be false; this means P must be true. Example: p ∀x ∈ R : sin x + cos x ≤ 2. Proof: p Assume that : ∃x ∈ R : sin x + cos x > 2. Then squaring both sides leads to : + cos2 x} + | sin2 x {z | x cos x} > 2 =⇒ sin 2x > 1, 2 sin {z 1 sin 2x this is a contradiction since we knowpthat the sine of any angle is ≤ 1. Conclusion : ∀x ∈ R : sin x + cos x ≤ 2.„ In the case that the sentence we are trying to prove is of the form P =⇒ Q , we assume that P is true and Q is false (see proposition (h) in the theorem above), and try to derive a statement known to be false. 8 4.2.3 Proof by induction Mathematical induction is a method for proving that a statement P (n ) is true for every nat- ural number n (the initial value is usually 0 or 1), i.e. the infinitely many cases P (0) , P (1) , P (2) ,... all hold. It consists of two steps: The first, the base step, proves the statement for n = 0. The second step, the induction step, proves that if the statement holds for any given n , then it must also hold for the next case n +1. In other words, prove the implication P (n) =⇒ P (n + 1). Example: Let n ∈ N∗ , we have : 1 + 3 + 5 +... + (2n − 1) = n 2. Proof: Let L H S denotes the left-hand side : 1 + 3 +... + (2n − 1) and R H S the right-hand side : n 2. Step 1: for n = 1, L H S = 2 × 1 − 1 = 1 and R H S = 12 = 1. Since L H S = R H S , the base case is satisfied. Step 2: Assume that, for a given n , we have : 1 + 3 +... + (2n − 1) = n 2 called the induction assumption or hypothesis and prove that : 1 + 3 +... + (2n + 1) = (n + 1)2. Starting from the inductive assumption and adding (2n + 1) to both sides we obtain : 1 + 3 + 5 +... + (2n − 1) + (2n + 1) = n 2 + (2n + 1). The left-hand side compresses into : 1 + 3 +... + (2n + 1) while the right-hand side is a re- markable identity, therefor : 1 + 3 +... + (2n + 1) = (n + 1)2 which was to be demonstrated.„ 9