Logics and Proofs.pdf

Logics and Proofs Rosen 7th Edition Propositional Logic  The rules of logic give precise meaning to mathematical statements.  These rules are used to distinguish between valid and invalid mathematical arguments.  Propositions A proposition is a declarative sentence (that is, a sentence...

Logics and Proofs Rosen 7th Edition Propositional Logic  The rules of logic give precise meaning to mathematical statements.  These rules are used to distinguish between valid and invalid mathematical arguments.  Propositions A proposition is a declarative sentence (that is, a sentence that declares a fact) that is either true or false, but not both. EXAMPLE 1 All the following declarative sentences are propositions. 1. Washington, D.C., is the capital of the United States of America. 2. Toronto is the capital of Canada. 3. 1 + 1 = 2. 4. 2 + 2 = 3. Propositions 1 and 3 are true, whereas 2 and 4 are false. EXAMPLE 2 Consider the following sentences. 1. What time is it? 2. Read this carefully. 3. x + 1 = 2. 4. x + y = z.  Notation  We use letters to denote propositional variables (or statement variables), that is, variables that represent propositions, just as letters are used to denote numerical variables.  The conventional letters used for propositional variables are p, q, r, s,....  The truth value of a proposition is true, denoted by T, if it is a true proposition.  The truth value of a proposition is false, denoted by F, if it is a false proposition.  The area of logic that deals with propositions is called the propositional calculus or propositional logic.  The sentences that cannot be further split or broken down into simpler sentences. Such statements are called primary, primitive or atomic statements. Logical Connectives  It is possible to form new and rather complicated statements from the primary statements by using connecting words. These statements are called compound statements.  We have in English language „and‟ , „or‟, „not‟, but or while etc. to connect two or more statements.  However these connectives being quite flexible in their usage lead to inexact and ambiguous interpretations.  Hence we are using some of these connectives, redefine and symbolize them to suit our purpose.  Negation  Let p be a proposition. The negation of p, denoted by ￢p (also denoted by p), is the statement  “It is not the case that p.”  The proposition ￢p is read “not p.”  The truth value of the negation of p, ￢p, is the opposite of the truth value of p. Example on Negation  Find the negation of the proposition  “Vandana’s smartphone has at least 32GB of memory”  and express this in simple English.  Solution: The negation is  “It is not the case that Vandana’s smartphone has at least 32GB of memory.”  This negation can also be expressed as  “Vandana’s smartphone does not have at least 32GB of memory”  or even more simply as  “Vandana’s smartphone has less than 32GB of memory.” Conjunction(“And”)  Let p and q be propositions.  The conjunction of p and q, denoted by p ∧ q, is the proposition “p and q.”  The conjunction p ∧ q is true when both p and q are true and is false otherwise. Example on conjunction Find the conjunction of the propositions p and q where p is the proposition “Rebecca’s PC has more than 16 GB free hard disk space” and q is the proposition “The processor in Rebecca’s PC runs faster than 1 GHz.” Disjunction Let p and q be propositions. The disjunction of p and q, denoted by p∨q, is the proposition “p or q.” The disjunction p∨q is false when both p and q are false and is true otherwise. Example on disjunction Find the disjunction of the propositions p and q where p is the proposition “Rebecca’s PC has more than 16 GB free hard disk space” and q is the proposition “The processor in Rebecca’s PC runs faster than 1 GHz.”  Solution The disjunction of p and q, p ∨ q, is the proposition “Rebecca’s PC has at least 16 GB free hard disk space, or the processor in Rebecca’s PC runs faster than 1 GHz.” This proposition is true when Rebecca’s PC has at least 16 GB free hard disk space, when the PC’s processor runs faster than 1 GHz, and when both conditions are true. It is false when both of these conditions are false, that is, when Rebecca’s PC has less than 16 GB free hard disk space and the processor in her PC runs at 1 GHz or slower.  Exclusive or  Let p and q be propositions.  The exclusive or of p and q, denoted by p ⊕ q, is the proposition that is true when exactly one of p and q is true and is false otherwise.  Conditional Statements  Let p and q be propositions.  The conditional statement p → q is the proposition “if p, then q.”  The conditional statement p → q is false when p is true and q is false, and true otherwise.  In the conditional statement p → q, p is called the hypothesis (or antecedent or premise) and q is called the conclusion (or consequence).  The statement p → q is called a conditional statement because p → q asserts that q is true on the condition that p holds.  A conditional statement is also called an implication.  Note that the statement p → q is true when both p and q are true and when p is false (no matter what truth value q has).  “if p, then q” , “p implies q” , “if p, q”  “p only if q” , “p is sufficient for q”  “a sufficient condition for q is p”  “q if p” ,“q whenever p” ,“q when p” , “q is necessary for p”  “a necessary condition for p is q” “q follows from p”  “q unless ¬p”  Example on implication “If you get 100% on the final, then you will get an A.” If you manage to get a 100% on the final, then you would expect to receive an A. If you do not get 100% you may or may not receive an A depending on other factors. However, if you do get 100%, but the professor does not give you an A, you will feel cheated. Example on implication Let p be the statement “Maria learns discrete mathematics” and q the statement “Maria will find a good job.” Express the statement p → q as a statement in English. Let P and q The proposition q implies p then this called as converse p implies q. the contrapositive of p implies q is the proposition notq implies notp the inverse of p implies q is the proposition notp implies not q The home team wins whenever it is raining notp Vq is equivalent to p implies q  BICONDITIONALS Let p and q be propositions. The biconditional statement p ↔ q is the proposition “p if and only if q.” The biconditional statement p ↔ q is true when p and q have the same truth values, and is false otherwise. Biconditional statements are also called bi- implications. Ways of representation of p ↔ q: “p is necessary and sufficient for q” “if p then q, and conversely” “p iff q.” p ↔ q ≡ (p → q) ∧ (q → p)  Propositional Equivalences A compound proposition that is always true, no matter what the truth values of the propositional variables that occur in it, is called a tautology. A compound proposition that is always false is called a contradiction. A compound proposition that is neither a tautology nor a contradiction is called a contingency. Example Construct truth tables to determine whether each of the following is tautology, a contingency or a contradiction 1. p →(q → p) 2. (p ∧ q) ∧ ￢(p∨q) 3. (p ∧ q) → p 4. (p →q )↔( q ∨ ￢p) 5. (p ∧ (￢ p ∨ q)) ∧ ￢ q Logical Equivalences Compound propositions that have the same truth values in all possible cases are called logically equivalent. Show that ￢(p ∨ q) and ￢p ∧￢q are logically equivalent.  Normal Forms One of the main problems in logic is to determine whether a given statement form is tautology or a contradiction. Constructing truth tables for this purpose may not always be practical, especially where the statement form may contain a lager number of variables or has a complicated structure. Hence it is necessary to consider alternate methods, such as reducing the statement form to so called normal forms.  Disjunctive normal form(dnf) A conjunction of statement variables and (or) their negations is called as fundamental conjunction. It is also called as a min term E.g. p, ~p,~p∧q, p∧q, etc are fundamental conjunctions A statement form which consists of a disjunction of fundamental conjunctions is called a disjunctive normal form(dnf). Example Obtain the dnf of the form (p →q) ∧(~p∧q) Conjunctive normal form(cnf)  A disjunction of statement variables and (or) their negations is called a fundamental disjunction or maxterm  E.g. p, ~p,~p ∨ q, p ∨ q, etc are fundamental disjunction  A statement form which consists of a conjunction of fundamental disjunctions is called a conjunctive normal form or cnf.  Obtain the cnf of the form (~p → r) ∧ (p ↔ q) Truth table method( to find dnf) Let P be a statement form containing n variables p1,p2,……pn. We obtain its dnf from the truth table as follows. For each row in which P assumes value T, form the conjunction p1 ∧p2 ∧p3…. ∧pn. Find the dnf of the form (~p → r) ∧ (p↔q) Predicates and Quantifiers  Predicates An assertion that contains one or more variables is called a predicate; its truth value is predicted after assigning truth values to its variables. Example “x is tall and handsome” “x+3=5” “x+y >=10”  Example on predicate Let P(x) denote the statement “x > 3.” What are the truth values of P(4) and P(2)? Let A(x) denote the statement “Computer x is under attack by an intruder.” Suppose that of the computers on campus, only CS2 and MATH1 are currently under attack by intruders. What are truth values of A(CS1), A(CS2), and A(MATH1)? Let Q(x, y) denote the statement “x = y + 3.” What are the truth values of the propositions Q(1, 2) and Q(3, 0)? n-place predicate A statement of the form P(x1, x2,... , xn) is the value of the propositional function P at the n- tuple (x1, x2,... , xn), and P is also called an n- place predicate or a n-ary predicate.  Quantifiers When the variables in a propositional function are assigned values, the resulting statement becomes a proposition with a certain truth value.  However, there is another important way, called quantification, to create a proposition from a propositional function. Quantification expresses the extent to which a predicate is true over a range of elements. There are two types of quantifiers: Universal Quantifier Existential Quantifier  THE UNIVERSAL QUANTIFIER Many mathematical statements assert that a property is true for all values of a variable in a particular domain, called the domain of discourse (or the universe of discourse), often just referred to as the domain. The universal quantification of P(x) is the statement “P(x) for all values of x in the domain.” The notation ∀xP(x) denotes the universal quantification of P(x). Here ∀ is called the universal quantifier.We read ∀xP(x) as “for all xP(x)” or “for every xP(x).” An element for which P(x) is false is called a counterexample of ∀xP(x). Example on Universal Quantifier 1. Let P(x) be the statement “x + 1 > x.” What is the truth value of the quantification ∀xP(x), where the domain consists of all real numbers? 2. Let Q(x) be the statement “x < 2.” What is the truth value of the quantification ∀xQ(x), where the domain consists of all real numbers? Solution for Q(x) is not true for every real 2 number x, because, for instance, Q(3) is false. That is, x = 3 is a counterexample for the statement ∀xQ(x). Thus ∀xQ(x) is false. Represent UNIVERSAL QUANTIFIER using logical connectives When all the elements in the domain can be listed—say, x1, x2,..., xn—it follows that the universal quantification ∀xP(x) is the same as the conjunction P(x1) ∧ P(x2) ∧ · · · ∧ P(xn), Because this conjunction is true if and only if P(x1), P(x2),... , P (xn) are all true.  Example What is the truth value of ∀xP(x), where P(x) is the statement “x2 < 10” and the domain consists of the positive integers not exceeding 4? Solution: The statement ∀xP(x) is the same as the conjunction P(1) ∧ P(2) ∧ P(3) ∧ P(4) Because the domain consists of the integers 1, 2, 3, and 4. Because P(4), which is the statement “42 < 10,” is false, it follows that ∀xP(x) is false. THE EXISTENTIAL QUANTIFIER The existential quantification of P(x) is the proposition “There exists an element x in the domain such that P(x).” We use the notation ∃xP(x) for the existential quantification of P(x). Here ∃ is called the existential quantifier. A domain must always be specified when a statement ∃xP(x) is used. Different ways of representation of Exist EXISTENTIAL QUANTIFIER “There is an x such that P(x),” “There is at least one x such that P(x),” “For some xP(x Example on Quantification Let Q(x) denote the statement “x = x+1. ”What is the truth value of the quantification ∃ xQ(x), where the domain consists of all real number When all elements in the domain can be listed— say, x1,x2,...,xn— the existential quantification ∃xP(x) is the same as the disjunction P(x1)∨P(x2)∨···∨P(xn), because this disjunction is true if and only if at least one of P(x1),P(x2),...,P(xn) is true. Example on EXISTENTIAL QUANTIFIER  What is the truth value of∃xP(x), where P(x)is the statement “x2 > 10” and the universe of discourse consists of the positive integers not exceeding 4? Solution: Because the domain is{1,2,3,4}, the proposition ∃xP(x) is the same as the disjunction P(1)∨P(2)∨P(3)∨P(4). Because P(4), which is the statement “42 > 10,” is true, it follows that ∃xP(x) is true Example on Predicate  Let P(x) be the statement “the word x contains the letter a.” What are these truth values? a) P(orange)  b) P(lemon) c) P(true)  d) P(false) Logical Equivalences Involving Quantifiers Statements involving predicates and quantifiers are logically equivalent if and only if they have the same truth value no matter which predicates are substituted into these statements and which domain of discourse is used for the variables in these propositional functions. We use the notation S ≡ T to indicate that two statements S and T involving predicates and quantifiers are logically equivalent.  Show that ∀x(P(x)∧Q(x)) and ∀xP(x)∧∀xQ(x) are logically equivalent (where the same domain is used throughout).  Negating Quantified Expressions Consider the negation of the statement “Every student in your class has taken a course in calculus.” This statement is a universal quantification, is represented as ∀x P(x)  The negation of this statement is “It is not the case that every student in your class has taken a course in calculus.” This is equivalent to “There is a student in your class who has not taken a course in calculus.” And this is simply the existential quantification of the negation of the original propositional function, namely, ∃x¬P(x). ¬∀xP(x) ≡ ∃ x ¬P(x). To show that ¬∀x P(x) and ∃x P(x) are logically equivalent no matter what the propositional function P(x)is and what the domain is, first note that¬∀xP(x) is true if and only if∀xP(x) is false. Next, note that ∀xP(x) is false if and only if there is an element x in the domain for which P(x)is false. This holds if and only if there is an element x in the domain for which ¬P(x) is true. Finally, note that there is an element x in the domain for which ¬P(x)is true if and only if ∃x¬P(x)is true. Putting these steps together, we can conclude that ¬∀xP(x) is true if and only if ∃x¬P(x) is true.  It follows that¬∀xP(x) and ∃x ¬P(x) are logically equivalent.  What are the negations of the statements “There is an honest politician” and “All Americans eat cheeseburgers”?  When the domain has n elements x1, x2,...,xn, it follows that ¬∀xP(x) is the same as ¬(P(x1)∧P(x2)∧···∧P(xn)), Which is equivalent to ¬P(x1)∨¬P(x2)∨ ···∨¬P(xn) by De Morgan‟s laws, and this is the same as ∃x¬P(x). Similarly, ¬∃xP(x) is the same as ¬(P(x1)∨P(x2)∨···∨P(xn)), Which by De Morgan‟s laws is equivalent to ¬P(x1)∧¬P(x2)∧···∧¬P(xn), and this is the same as ∀x¬P(x) Example on negating quantifiers  What are the negations of the statements ∀x(x2 > x) and ∃x(x2 = 2)? Solution The negation of ∀x(x2 > x)is the statement ¬∀x(x2 > x), which is equivalent to ∃x¬(x2 > x). This can be rewritten as ∃x(x2 ≤ x). The negation of ∃x(x2 = 2) is the statement ¬∃x(x2 = 2), which is equivalent to ∀x¬(x2 = 2). This can be rewritten as ∀x(x2 ≠ 2). The truth values of these statements depend on the domain. Home work example Show that ¬∀x(P(x)→ Q(x)) and ∃x(P(x)∧¬Q(x)) are logically equivalent. Translating from English into Logical Expressions  Express the statement “Every student in this class has studied calculus” using predicates and quantifiers.  Solution: First, we rewrite the statements that we can clearly identify the appropriate quantifiers to use. Doing so, we obtain:  “For every student in this class, that student has studied calculus.”  Next, we introduce a variable x so that our statement becomes  “For every student x in this class, x has studied calculus.”  Continuing, we introduce C(x), which is the statement “x has studied calculus.” Consequently, if the domain for x consists of the students in the class, we can translate our statement as ∀xC(x). Home work example  Let P(x)be the statement “x spends more than five hours every weekday in class,” where the domain for x consists of all students. Express each of these quantifications in English. a) ∃xP(x) b) ∀xP(x) c) ∃x¬P(x) d) ∀x¬P(x) Let Q(x) be the statement “x +1 > 2x.” If the domain consists of all integers, what are these truth values?  a) Q(0)  b) Q(−1) c) Q(1) d) ∃xQ(x)  e) ∀xQ(x)  f) ∃x¬Q(x)  g) ∀x¬Q(x)  Suppose that the domain of the propositional function P(x)consists of the integers 0, 1, 2, 3, and 4. Write each of these propositions using disjunctions, conjunctions, and negations. a) ∃xP(x)  b) ∀xP(x)  c) ∃x¬P(x) d) ∀x¬P(x)  e) ¬∃xP(x)  f) ¬∀xP(x