CSC165H1, Winter 2022 CSC165H1: Worksheet 3—Working with Predicates (Partial Solutions)
Learning Objectives
By the end of this worksheet, you will:
• Translate sentences between natural English and predicate logic.
Copyright By PowCoder代写 加微信 powcoder
• Use definitions of predicates to simplify or expand statements in predicate logic. • Apply negation equivalence rules to simplify statements in predicate logic.
1. Translation with predicates. Suppose we have a set P of computer programs that are each meant to solve the same task. Some of the programs are written in the Python programming language, and some are written in a different language. Some of the programs correctly solve the task, and others do not.
Let’s define the following predicates:
Python(x) : “x is a Python program”,
Correct(x) : “x solves the task correctly”, Express each English statement below as a sentence in predicate logic.
(a) Program my prog is correct and is written in Python.
(b) An incorrect program is written in Python.
(c) No Python program is correct.
(d) Every incorrect program is written in Python.
Translate each predicate logic statement below into natural English. (a) ∃x ∈ P, Python(x) ∧ Correct(x)
where x ∈ P where x ∈ P
Correct(my prog) ∧ Python(my prog)
∃x ∈ P, ¬Correct(x) ∧ Python(x)
¬(∃x∈P, Python(x)∧Correct(x)) or
∀x ∈ P, Python(x) ⇒ ¬Correct(x)
∀x ∈ P, ¬Correct(x) ⇒ Python(x) or the contrapositive,
∀x ∈ P, ¬Python(x) ⇒ Correct(x)
At least one Python program is correct.
(b) ∀x ∈ P, ¬Python(x) ∧ Correct(x)
CSC165H1, Winter 2022 CSC165H1: Worksheet 3—Working with Predicates (Partial Solutions)
Every program is written in a language other than Python and is correct.
(c) ¬∀x ∈ P, Correct(x) ⇒ Python(x)
(d) ∀x ∈ P, ¬Python(x) ⇔ Correct(x)
Not every correct program is written in Python.
Alternate: A correct program is written in a language other than Python.
For every program x, x is not written in Python if and only if x is correct. But it’s a bit more natural to first rewrite the ⇔ and then translate:
• ∀x ∈ P, ¬Python(x) ⇒ Correct(x) ∧ Correct(x)) ⇒ ¬Python(x), which translates to “Every program not written in Python is correct, and every correct program is not written in Python.”
• ∀x ∈ P, ¬Python(x)∧Correct(x)∨Python(x)∧¬Correct(x), which translates to “Every program is either not written in Python and correct, or written in Python and not correct.”
2. Quantifiers in subformulas. So far, we have seen quantifiers only as the leftmost components of our formulas. However, because all predicate statements have truth values (i.e., are either True or False), they too can be combined using the standard propositional operators. Let’s see some examples of this (refer to the same predicates as Question 1).
(a) Translate the following statement into English.
∀x ∈ P, Python(x) ⇒ Correct(x) ∨ ∀y ∈ P, Python(y) ⇒ ¬Correct(y)
(b) Translate the following statement into predicate logic. “If at least one Python program is correct, then all Python programs are correct.”
All Python programs are correct, or all Python programs are incorrect.
∃x ∈ P, Python(x) ∧ Correct(x) ⇒ ∀y ∈ P, Python(y) ⇒ Correct(y)
(c) Finally, consider the following two statements:
∃x1 ∈N, x1 |165∧∃x2 ∈N, 7|x2
∃x∈N, x|165∧7|x What is the difference between these two statements? Are they True or False?
(Statement1) (Statement2)
In the first statement, there are two different numbers, and each one satisfies one predicate (dividing 165 or being divisible by 7). In the second statement, we only have one number, that must satisfy both predicates.
The first statement is True (why?) and the second statement is False (why?).
3. Expanding definitions. Consider the following statement:
CSC165H1, Winter 2022 CSC165H1: Worksheet 3—Working with Predicates (Partial Solutions)
If m and n are odd integers, then mn is an odd integer.
If we want to express this statement using predicate logic, we need to start with a definition of the term “odd”. Let
n∈Z. Wesaythatnisoddwhen2|(n+1),i.e.,when∃k∈Z,n+1=2k.
(a) Write the definition of a predicate over the integers named Odd that is True when its argument is odd.
(b) Using the predicate Odd and the notation of predicate logic, express the statement: For every pair of odd integers m and n, mn is an odd integer.
(c) Repeat part (b) but fully expand the definitions of the predicates Odd and |.
(d) Repeat parts (b) and (c) using the following statement (which states the converse of the original implication). For every pair of integers m and n, if mn is odd, then m and n are odd.
4. Simplifying negated formulas. Recall the rules governing how to simplify negations of predicate formulas:
• ¬(¬p) becomes p.
• ¬(p ∨ q) becomes ¬p ∧ ¬q.
• ¬(p ∧ q) becomes ¬p ∨ ¬q.
• ¬(p⇒q) becomes p∧¬q.
• ¬(p⇔q) becomes (p∧¬q)∨(¬p∧q).
• ¬(∃x ∈ S, P(x)) becomes ∀x ∈ S, ¬P(x). • ¬(∀x ∈ S, P(x)) becomes ∃x ∈ S, ¬P(x).
Using these rules, simplify each of the following formulas so that the negations are applied directly to predi- cates/propositional variables. Note: this is a pretty mechanical exercise, but an extremely valuable one: once we get to the next chapter, we will be assuming you can take negations of statements very quickly as a first step in some proofs.
(a) ¬(a∧b)⇔c
Odd(x): ∃k∈Z,x+1=2k, wherex∈Z. Odd(x): 2|(x+1), wherex∈Z.
∀m,n∈Z,Odd(m)∧Odd(n)⇒Odd(mn)
∀m,n∈Z, ∃k1∈Z, m=2k1 +1∧∃k2∈Z, n=2k2 +1⇒∃k3∈Z, mn=2k3 +1
CSC165H1, Winter 2022 CSC165H1: Worksheet 3—Working with Predicates (Partial Solutions)
¬(a∧b)⇔c (a∧b)∧(¬c)∨(¬(a∧b)∧c) a∧b∧¬c∨(¬a∨¬b)∧c
(b) ¬∀x,y∈S, ∃z∈S, P(x,y)∧Q(x,z)
¬∀x,y∈S, ∃z∈S, P(x,y)∧Q(x,z)
∃x,y∈S, ∀z∈S, ¬P(x,y)∧Q(x,z) ∃x,y∈S, ∀z∈S, ¬P(x,y)∨¬Q(x,z)
(c) ¬∃x ∈ S, P(x) ⇒ ∃y ∈ S, Q(y)
5. Choosing a universe and predicates. Consider the statement
∃x∈U, P(x)∧∃y∈U, Q(y)⇒∃z∈U, P(z)∧Q(z).
Define a non-empty domain U and predicates P and Q for which this statement is False.
Hint: The statement says: “If some x ∈ U makes P(x) True and some y ∈ U makes Q(y) True, then some z ∈ U makes both P(z) and Q(z) True.” Think about how this statement could be False, and use this to construct a U, P and Q.
¬∃x ∈ S, P(x) ⇒ ∃y ∈ S, Q(y)
∃x∈S, P(x)∧¬∃y∈S,Q(y) ∃x∈S, P(x)∧∀y∈S,¬Q(y)
Since we want to show that an implication is False, we want to construct an example where the hypothesis is True and the conclusion False.
Let U = Z. Define the following predicates over Z: P (x) : “x is even”, and Q(x) : “x is odd”.
Then (∃x ∈ U, P(x)) is True, as the integer 2 provides an example. And (∃y ∈ U, Q(y)) is also True, as the
integer 3 provides an example. The hypothesis in the statement is therefore True.
However, there is no integer that is both even and odd at the same time, and so [∃ z ∈ U, P(z)∧Q(z)] is False. (Put another way, the intersection of the even and odd numbers is empty.) So the conclusion in the statement is False.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com