### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Week 2 Terms and Concepts: Quantified Statements CS 225

OSU

GPA 3.8

### View Full Document

## About this Document

## 3

## 0

## Popular in Discrete Structures in Computer Science

## Popular in Computer science

This 7 page Class Notes was uploaded by Tiffani Friesendorf on Thursday October 6, 2016. The Class Notes belongs to CS 225 at Oregon State University taught by Samina Ehsan in Fall 2016. Since its upload, it has received 3 views. For similar materials see Discrete Structures in Computer Science in Computer science at Oregon State University.

## Reviews for Week 2 Terms and Concepts: Quantified Statements

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/06/16

Discrete Mathematics CS225 Terms and concepts: Week 2 Reading 3.1, 3.2, with notes from the lecture and optional reading added in accordingly. The Logic of Quantified Statements Predicate Calculus: The symbolic analysis of predicates and quantified statements. Statement/Proposition Calculus: Symbolic analysis of ordinary compound statements. 3.1 Predicates and Quantified Statements • Predicate (as used in logic): ◦ Asentence that contains a finite number of variables and becomes a statement when specific values are substituted for variables. ◦ Can be obtained by removing some or all of the nouns from a statement. ▪ Ex: “James is a student at Bedford College.” • Both of these can be predicates: ◦ P: is a student at Bedford College. ◦ Q: is a student at ▪ P and Q in these instances are predicate symbols. • Apredicate symbol together with suitable predicate variables: ◦ P(x): x is a student at Bedford College. ◦ Q(x, y): x is a student at y. ▪ x and y are predicate variables. ◦ Can have multiple predicate variables. ▪ P(x , 1 ,2. . ., n ) • Is the value of the propositional function P at the n-tuple. • P = n-place predicate or n-ary predicate. ◦ In other treatments of logic, such objects are referred to as: ▪ Propositional functions. ▪ Open sentences. • Domain: The domain of a predicate variable is the set of all values that may be substituted in place of the variable. Finding the Truth Values of a Predicate • Truth Set: If P(x) is a predicate and x has domain D, the truth set is the set of all elements of D that make P(x) true when substituted for x. ◦ Truth set of P(x) is denoted: ▪ {x∈D∨P(x)} • Ex: Let Q(n) = n is a factor of 8. ◦ Domain of n is set Z for all positive integers. ▪ Truth set is: {1, 2, 4, 8} (all positive integers that divide into 8 evenly) ◦ Domain of n is set Z for all integers. ▪ Truth set is: {1, 2, 4, 8, -1, -2, -4, -8} (all integers that divide into 8 evenly) Preconditions and Post-Conditions • Predicates can be used to establish the correctness of a computer program. ◦ Show that the computer programs always produce the desired output when given valid input. ◦ Unless the correctness of a computer program is established, no amount of testing can show it produces the desired output for all input values, unless all values are tested. • Preconditions: Statements that describe valid input. • Postconditions: Conditions that the output should satisfy when the program has run. • Ex: Program designed to interchange the values of variables x and y: ◦ temp := x x := y y := temp ▪ For precondition, must express that x and y have particular values before running the program. • Precondition: P(x, y) where x = a, and y = b. ▪ After running the program, the expected postcondition needs to be true. • Postcondition P(x, y) where x = b, and y = a. Quantifiers • Quantification: Expresses the extent to which a predicate is true over a range of elements. • Propositional logic can only express specific information: ◦ “Alex is an infant.” ◦ “Alex has no child.” ◦ Apredicate makes it possible to make more generalized statements. ▪ Takes argument as a predicate and returns True or False. • “Alex is an infant therefore he has no child.” • Alex Infant→¬Alex HasChild ▪ Want to get to if any patient is an infant, then that patient has no children, not justAlex. • Quantifiers allow for this. ◦ Instead of justAlex, a quantity, such as: ◦ All people ◦ All infants ◦ Some patients ◦ etc. ▪ Predicate allows for arguments to express this generalization. • Ex Predicates: ◦ Infant(x): is true if and only if x is an infant. ◦ HasChild(x): is true if and only if x has a child. The Universal Quantifier: ∀ • Away to obtain statements from predicates is to add quantifiers. • Quantifiers: Words that refer to quantities and tell how many elements a given predicate is true. • ∀ Universal Quantifier: Denotes “for all” ◦ Ex: “All human beings are mortal” ▪ ∀ human beings are x, x is mortal. • In this case, x is an individual, but generic, object. ◦ x has all the properties shared by every human being, but no other properties. ◦ When describing the property satisfied by x, refer to it as singular (“is” instead of “are”) ▪ ∀∈H , x is mortal. • H is the set of all human beings. • Read: “For all x in the set of all human beings, x is mortal.” ◦ Ex: If any patient is an infant, then the patient has no children. ▪ ∀ xInfant(x)→¬HasChild(x) • The domain of the predicate variable: ◦ is generally indicated between the∀ symbol and the variable name: ▪ Ex: ∀ human beings x. ▪ Ex: ∀ xInfant(x)→¬HasChild(x) • The domain in this case (x) is all patients. • Formal version: For all x, where x is a patient, if x is an infant, then x does not have a child. ◦ or immediately following the variable name: ▪ ∀ x∈H ◦ In a sentence such as “∀ real numbers x and y, x + y = y + x” ▪ ∀ symbol is understood to refer to both x and y. • Expressions that can be used as universal quantifiers: ◦ for all ◦ for every ◦ for arbitrary ◦ for each ◦ given any ◦ all of ◦ for any ▪ Best to avoid using “for any x” • It is often arbitrary. Could mean every or some. • Any is unambiguous when used in negatives. ◦ Ex: “There is not any reason to avoid studying.” • Universal statement:Astatement in the form ofx∈D , Q(x) ◦ It is defined to be true if, and only if, Q(x) is true for every x in D. ◦ It is defined to be false if, and only if, Q(x) is false for at least one x in D. • Counterexample:Avalue for which Q(x) is false. • Method of exhaustion: Consists of showing the truth of the predicate separately for each individual element of the domain. ◦ In theory, can be used whenever the domain of the predicate variable is finite. The Existential Quantifier∃ • ∃ Existential Quantifier: “there exists.” • Ex: There is a student in Math 140 ◦ ∃ a person p such that p is a student in Math 140. ◦ more formally: ∃p∈Psuchthat pisastudent∈Math140. ▪ Where P is a set of all People • Ex: There exists a patient that is an infant and has the flu. ◦ ∃x Infant(x)∧HasFlu(x) ▪ The domain in this case (x) is all patients. ▪ More Formal: There exists an x, where x is a patient, such that x is an infant and has the flu. • Expressions that can be used as existential quantifiers: ◦ there exists ◦ there is a ◦ we can find a ◦ there is at least one ◦ for some ◦ for at least one • In a sentence such as “∃ integers m and n such that m + n = n + m” ◦ ∃ is understood to refer to moth m and n • Existential statement:Astatement in the form ∃x∈D , Q(x) ◦ It is defined to be true if, and only if, Q(x) is true for at least one x in D. ◦ It is defined to be false if, and only if, Q(x) is false for all x in D. Statement When True: When False: ∀ x P(x) P(x) is true for every x. There is an x for which P(x) is false. ∃x P(x) There is an x for which P(x) is truP(x) is false for every x. Formal Versus Informal Language Translating from Formal to Informal Language • Ex: Rewrite these formal statements in a variety of equivalent but more informal ways. Do not use the symbol 2∀ or ∃ . ◦ ∀ x∈R ,x ≥0 ▪ All real numbers have nonnegative squares. ▪ Every real number has a nonnegative square. ▪ Any real number has a nonnegative square. ▪ The square of each real number is nonnegative. ◦ ∀ x∈R ,x ≠−1 ▪ All real numbers have squares that are not equal to -1. ▪ No real numbers have squares equal to -1. ◦ ∃m∈Z +¿ such that m =m ▪ There is a positive integer whose square is equal to itself. ▪ We can find at least one positive integer equal to its own square. ▪ Some positive integer equals its own square. ▪ Some positive integers equal their own squares. • Another way to restate the universal and existential statements informally is to place the quantification at the end of the sentence. ◦ Ex: Instead of: For any real number x, x is nonnegative. 2 ▪ x is nonnegative for any real number x. • The quantifier is said to trail the rest of the sentence. Translating from Informal to Formal Language • Ex: Rewrite each of the following statements formally. Use quantifiers and variables. ◦ All triangles have 3 sides. ▪ ∀ triangles t t has three sides. ▪ ∀d∈T t has three sides (where T is the set of all triangles). ◦ No dogs have wings. ▪ ∀ dogs d, d does not have wings. ▪ ∀d∈D , d does not have wings (where D is the set of all dogs). ◦ Some programs are structured. ▪ ∃ a program p such that p is structured. ▪ ∃p∈P such that p is structured (where P is the set of all programs). Universal Conditional Statements • ∀ x if P(x) then Q(x). Writing Universal Conditional Statements Informally • Ex: ∀ x∈R , if x > 2 then x > 4. ◦ If a real number is greater than 2 then its square is greater than 4. ◦ Whenever a real number is greater than 2, its square is greater than 4. ◦ The square of any real number greater than 2 is greater than 4. ◦ The squares of all real numbers greater than 2 are greater than 4. Writing Universal Conditional Statements Formally • Ex: Rewrite each of the following statements in the form: V ____, if _____ then _____. ◦ If a real number is an integer, then it is a rational number. ▪ real numbers x, if x is an integer, then x is a rational number. ∀ ▪ ∀ x∈R ,if x∈Z thenx∈Q. ◦ All bytes have eight bits. ▪ ∀ x , if x is a byte, then x has eight bits. ◦ No fire trucks are green. ▪ ∀ x , if x is a fire truck, then x is not green. • It is common to omit explicit identification of the domain of predicate variables in universal conditional statements. • The definition of a valid argument is a universal conditional statement: ◦ ∀ combinations of truth values for the component statements, if the premises are all true then the conclusion is also true. Equivalent Forms of Universal and Existential Statements • These statements mean the same thing: ◦ ∀ real numbers x, if x is an integer then x is rational. ◦ ∀ integers x, x is rational. ▪ Both have informal translations:All integers are rational. • ∀x∈U ,if P(x)thenQ(x) ◦ can be rewritten∀ x∈D,Q(x) ▪ By narrowing U to e the domain D consisting of all values of the variable x that make P(x) true. • Conversely,∀ x∈D,Q(x) ◦ can be written: ∀x,if xis∈DthenQ(x) • Ex:All squares are rectangle. ◦ ∀ x. if x is square then x is a rectangle. ◦ ∀ squares x, x is a rectangle. • Ex: ∃x such that p(x) and Q(x). ◦ ∃x∈D such that Q(x) (where D is set of all x for which P(x) is true.) • Ex: There is an integer that is both prime and even. ◦ Even(n) is n is even ◦ Prime(n) is n is prime. ▪ ∃n such that Prime(n) ∧ Even(n). ▪ ∃ a prime number n such that Even(n). ▪ ∃ an even number n such that Prime(n). Implicit Quantification • Can occur with the words: ◦ a ◦ an ▪ Ex: If a number is an integer, then it is a rational number. • ∀ x , if x then y. (x is integer, y is rational number) ▪ The number 24 can be written as a sum of two even integers. • ∃ even integers m and n such that 24 = m + n. • Can occur in cases where the general context of a sentence supplies meaning. ◦ Ex: In an algebra course in which the letter x is always used to indicate a real number, the 2 predicate: If x > 2 then x > 4 can 2e interpreted: ▪ ∀ real numbers x, x > 2 then x > 4 . • ⇒ Double arrow: Indicates implicit quantification symbolically. ◦ x>2⇒x >4 ◦ Let P(x) and Q(x) be predicates and suppose the common domain of x is D. ▪ The notation P(x)⇒Q(x) means that every element in the truth set of P(x) is in the truth set of Q(x), or, equivalently . ▪ The notation P(x)⇔Q(x) means that P(x) and Q(x) have identical truth sets, or, equivalently ∀ x ,P(x)↔Q(x) . • Ex: Math text may contain: ◦ a. (x + 1 ) = x + 2x + 1 ◦ b. Solve 3x – 4 = 5 ▪ Although neither a nor b contains specific quantification, it is understood that: • a. is universally quantified. • b. is existentially quantified. ▪ Made explicit: • a. ∀ real numbers x, (x + 1 ) = x + 2x + 1. • b. Show, by finding a value, tha∃ a real number x such that 3x – 4 = 5. • The quantification statement—whether universal or existential—crucially determines both how the statement can be applied and what method must be used to establish its truth. ◦ Important to be alert to the presence of hidden quantifiers in order to interpret statements in a logical way. 3.2 Negations of Quantified Statements • Negating Quantifiers ◦ Similar to DeMorgan’s law. Logically: ▪ ¬∀P(x)≡∃x¬P(x) ▪ ¬∃xP(x)≡∀¬P(x) ◦ Ex: Not all patients are infants. x is all patients. ▪ Symbolically: ¬(∀xInfant(x)) ▪ Logically equivalent: There exists a patient that is not an infant. • Symbolically: ∃x¬Infant(x) ◦ Ex: There does not exist a patient that is an infant. ▪ Symbolically: ¬(∃xInfant(x)) ▪ Logically Equivalent: For all patients, none of them are infants. • Symbolically: ∀x¬Infant(x) ◦ Sometimes the logically equivalent version is easier to understand. • Negation of a universal statement: ◦ The negation of a statement of the form: in D, Q(x) ▪ Is logically equivalent to: in D such that¬Q(x) ▪ Symbolically: ¬(∀x∃D,Q(x))≡∃x∈D suchthat¬Q(x) ◦ The negation of a universal statement (“all are”) is logically equivalent to an existential statement (“some are not” or “there is at least one that is not”). • Negation of an existential statement: ◦ The negation of a statement of the form: in D such that Q(x) ▪ Is logically equivalent to: in D, ¬❑Q(x) ▪ Symbolically: ¬(∃x∈DsuchthatQ(x))≡forallx∈D,negQ(x) ◦ The negation of an existential statement (“some are”) is logically equivalent to a universal statement (“none are” or “all are not”). • It is easy to make mistakes when writing negations of informal statements. ◦ Away to avoid this error, rewrite the statement formally, and take the negation using the formal rule. Negations of the Universal Conditional Statements • By definition of the negation of a “for all” statement: ◦ ¬(∀ x ,P(x)→Q(x))≡∃xsuchthat ¬(P(x)→Q(x)) • but, the negation of an if-then statement is logically equivalent to an and statement: ◦ ¬(p(X)→Q(x))≡P(x)∧¬Q(x) • substitution gives: ◦ ¬(∀ x ,P(x)→Q(x))≡∃xsuchthat(P(x)∧¬Q(x)) ▪ which is the negation of a universal conditional statement. • Negation of a Universal conditional statement (written less symbolically): ◦ ¬(∀x,if P(x)thenQ(x))≡∃xsuchthat P(x)∧¬Q(x)

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the material...plus I made $280 on my first study guide!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.