CSC165H1, Winter 2022 CSC165H1: Worksheet 2—Predicate Logic (Partial Solutions)
Learning Objectives
By the end of this worksheet, you will:
• Translate statements between natural English and predicate logic. • Determine the truth value of sentences on small domains.
Copyright By PowCoder代写 加微信 powcoder
• Define a property of a mathematical function using predicate logic. • Express conditions on domains in predicate logic.
1. Alternating quantifiers. Consider the following table that shows the employees of a (very small) company:1
Employee Aizah
E be the set of the six employees listed above. We’ll define two predicates on this set:
Rich(x) : “x earns more than 35,000,” where x ∈ E
SameDept (x, y) : “x and y are in the same department,” where x, y ∈ E
Salary Department 60,000 Sales
15,000 Sales
30,000 Sales 50,000 Design 20,000 Design
(a) Consider the statement
Give one example to show that this statement is True. Is there more than one possible answer? Note: just as in
∃x,y∈E, Rich(x)∧SameDept(x,y).
programming and math, the two variables x and y can have the same value (i.e., refer to the same employee).
x = Aizah and y = Aizah is one possibility. A good exercise is to try to find all possbilities.
(b) Here’s the same statement, but with a universal quantifier instead: ∀x,y∈E, Rich(x)∧SameDept(x,y).
Give one counter-example to show that this statement is False. Is there more than one possible answer?
(c) Now let’s look at alternating quantifiers.
∀y∈E, ∃x∈E, Rich(x)∧SameDept(x,y).
Is this True or False? How do you know?
Lots of possibilities here! We can pick an employee who isn’t rich, e.g. x = Betty and y = Aizah. Or, we could pick two employees who aren’t in the same department, e.g. x = Aizah and y = Carlos.
This is True. The translation is “for every employee y, there is an employee x who has a salary greater than 35,000 and in the same department as y.” Each department has an employee with a salary greater than 35,000, so for each employee y, we can always pick an employee x in the same department who is “rich”.
For example, when y = Betty, we can pick x = Aizah (can you list all possibilities?). Note that the HR department only has one employee! So if y = Carlos, we would also pick x = Carlos to make this
1This example is adapted from an old set of CSC165 course notes.
CSC165H1, Winter 2022 CSC165H1: Worksheet 2—Predicate Logic (Partial Solutions)
statement True.
(d) With the quantifiers switched:
∃x∈E, ∀y∈E, Rich(x)∧SameDept(x,y). Explain why this statement is False.
2. A property of functions. Let f : R → R be a function. Recall that the codomain of f is the set after the → symbol (in this case, R), which contains the possible output values of f. However, in general the codomain of a function might contain values that cannot possibly be output (e.g., if f : R → R is defined as f(x) = x2). We say that f : R → R is onto when its codomain R only contains values that could possibly be output by f (and no “impossible” values). For example, f(x) = x + 1 is onto, but f(x) = x2 is not onto.
(a) Let f : R → R. Express the statement “f outputs 10 (for at least one input)” in symbolic form. You may use an expression like f(x) = 10 in your statement.
(b) Now express the definition of onto as a predicate in symbolic form by filling in the following blank.
Onto(f): , wheref:R→R.
(c) Let f(x) = x2. Using your definition, give a counter-example to show that f is not onto.
This statement says that there is an employee x who has a salary greater than 35,000 and where every employee is in the same department as x. This is False, since there are employees in different departments. For example, if x = Aizah, while Rich(x) is True, it’s not true that SameDept(x,y) for all employees y.
∃x∈R, f(x)=10.
∀y∈R, ∃x∈R, f(x)=y.
Because x2 is always greater than or equal to 0, if we pick y = −1, the statement ∃x ∈ R, x2 = −1 is False!
CSC165H1, Winter 2022 CSC165H1: Worksheet 2—Predicate Logic (Partial Solutions)
3. Expressing conditions. Often when we want to express statements using predicate logic, the common domains like N and R do not quite fit. For example, consider the statement:
Every natural number greater than 3 is greater than 1.
The use of “every” suggests a universal quantification, but using the domain of N in the following way does not capture the meaning of the statement:
In this question, you’ll explore two equivalent ways of modifying the above formula to capture the condition “greater
(a) One simple way is to change the domain over which we’re quantifying. Write down the definition of a set S such that the following formula is equivalent to the original statement:
(b) We’ve hinted at another way to express this statement by using the word “condition” to describe the role of “greater than 3”. The original statement only talks about natural numbers greater than 3, and ignores all others—the same is true of the implication operator. This suggests that we can keep the original domain, but use an implication to narrow the scope of what we’re talking about.
Define a predicate P (n) such that the following formula is equivalent to the original statement: ∀n∈N, P(n)⇒n>1
(c) Using what you’ve learned, express each of the following statements in two different ways: Every integer that is greater than 10 or less than -40 is not equal to 0.
S = {n | n ∈ N and n > 3}.
P(n): n>3,wheren∈N.
Using the domain S = {x | x ∈ Z and x > 10 or x < −40}, ∀x∈S, x̸=0
Using the predicate P (x) : “x > 10 ∨ x < −40” where x ∈ Z, ∀x∈Z, P(x)⇒x̸=0
∀x∈Z, x>10∨x<−40⇒x̸=0
Every employee who is in the same department as Doug is rich. (See pg. 1.)
Using the domain S = {x | x ∈ E and SameDept(x,Doug)}, ∀x ∈ S, Rich(x)
CSC165H1, Winter 2022 CSC165H1: Worksheet 2—Predicate Logic (Partial Solutions)
Using the predicate P(x): “SameDept(x,Doug)” where x ∈ E, ∀x∈E, P(x)⇒Rich(x)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com