Report

Chapter 2 The Logic of Quantified Statements Section 2.1 Intro to Predicates & Quantified Statements Predicate Calculus • The symbolic analysis of predicates and quantified statements is known as predicate calculus. • Predicate calculus is used to determine the validity of statements like: All men are mortal. Socrates is a man. Therefore, Socrates is mortal. Predicate • Predicate is the part of the sentence that provides information about the subject. – Example: “Dr. Ricanek is a resident of New Hanover County” • Subject: Dr. Ricanek • Predicate: is a resident of New Hanover County Predicate • Predicate can be formed by removing the subject. – Example: “Dr. Ricanek is a resident of New Hanover County” • predicate symbol P = “is a resident of New Hanover County” • P(x) = x is a resident of New Hanover County • x is predicate variable, when it is giving a concrete value P(x) becomes a statement • x = Karl Ricanek • P(x) = “Karl Ricanek is a resident of New Hanover County” Predicate • Predicate can be formed by removing the nouns. – Example: “Dr. Ricanek is a resident of New Hanover County” • • • • • predicate symbol Q = “is a resident of” Q(x,y) = x is a resident of y x,y are predicate variables x = Charlotte, y = Pender County Q(x,y) = “Charlotte is a resident of Pender County” Predicate • Definition: – A predicate is a sentence that contains a finite number of variables and becomes a statement when specific values are substituted for the variables. – Domain of a predicate variable is the set of all values that may be substituted in place of the variable. Example • P = “is a public university in the UNC system” • P(x) = x is a public university in the UNC System. • predicate variable x, domain is any one of the 16 universities in UNC system. Example • P(x) is the predicate “x2 > x”, domain of x is all real numbers, R. • Determine which is valid: – P(2): 22 > 2 – P(1/2): ½2 > ½ – P(-1/2): -½2 > -½, ¼ > -½ Number Systems & Notations • There are universally accepted symbols and notations in mathematics, i.e. – R - set of all real numbers – Z - set of all integers – Q - set of all rational numbers, quotients of integers – + - all positive numbers – - - all negative numbers • Example: R+, Z- Number Systems & Notations – denotes a member of – x ∈A, x is a member of set A – x ∉ A, x is not a member of set A – … (ellipsis), “and so forth” – | “such that” – Example: • { x ∈ D | P(x) }, “the set of all x in D such that P(x)” Truth Set • A truth set is the set of all elements of D that make P(x) true when they are substituted for x. • Truth set is denoted: { x ∈ D | P(x) } Example • Let Q(n) be the predicate “n is a factor of 12.” Find the truth set of Q(n) if – a. the domain of n is the set of Z+ (positive integers) – solution: truth set is {1, 2, 3, 4, 6, 12} • Let Q(n) be the predicate “n is a factor of 6.” Find the truth set of Q(n) if – a. the domain of n is the set Z (all integers) – solution: truth set is {1, 2, 3, 6, -1. -2, -3, -6} Universal Quantifier • Universal quantifier symbol: ∀ • ∀denotes “for all” – Example: • “All human beings are mortal” • ∀human beings x, x is mortal, or • ∀x ∈S, x is mortal (What does S denote?) Universal Statement • A universal statement has the form, ∀x ∈ D, Q(x). • Universal statement is true, if and only if, all Q(x) is true for every x in (domain). • Counterexample occurs when a x∈D, Q(x) is false. Example • Let D = {1, 2, 3, 4, 5}, and consider the statement ∀x ∈ D, x2 ≥ x. Show that this statement is true. – 12 ≥ 1, 22 ≥ 2, 32 ≥ 3, 42 ≥ 4, 52 ≥ 5; Hence, true. – Proof by exhaustion… • Consider, ∀x ∈ R, x2 ≥ x – find one case where not true (counterexample) – x = ½ , ½ 2 ≥ ½; Hence, statement is false by counterexample. Existential Quantifier • Existential quantifier symbol: ∃ • ∃denotes “there exists”. – Example: • “There is a student in CSC 133” • ∃a person s such that s is a student in CSC 133, or • ∃s ∈ S | s is a student in CSC 133 Existential Quantifier • Existential statement has the form, ∃x ∈ D | Q(x). • Existential is defined to be true if, and only if, Q(x) is true for at least one x in D. • It is false if, and only if, Q(x) is false for all x in D. Example • Consider, ∃m ∈ Z | m*m = m – only have to find 1-case where this is true – if m = 1, then 1*1 = 1; hence, statement true. Universal Conditional Statement • ∀x, if P(x) then Q(x) • Example: – ∀x ∈ R, if x > 2 then x2 > 4 – iinformal • If a real number is greater than 2, then its square is greater than 4, or • The square of any real number that is greater than 2 is greater than 4. Example • Formal and informal examples of universal conditional statement – ∀x ∈ R, if x ∈ Z then x ∈ Q – ∀ real numbers x, if x is an integer, then x is a rational number. – “If a real number is an integer, then it is a rational number.” Equivalent Forms of ∀&∃ • There are equivalent forms of universal and existential statements. – Example: “All integers are rational.” • ∀real numbers x, if x is an interger then x is rational • ∀ integers x, x is rational – ∀x ∈U, if P(x) then Q(x) ≡∀x ∈D, Q(x) – ∃x such that P(x) and Q(x) ≡∃x ∈D such that Q(x)