# CSC165H1: Problem Set 1 solved

\$35.00

Category:

## Description

1. [6 marks] Propositional formulas. For each of the following propositional formulas, find the following
two items:
(i) The truth table for the formula. (You don’t need to show your work for calculating the rows of the
table.)
(ii) A logically equivalent formula that only uses the ¬, ∧, and ∨ operators; no ⇒ or ⇔. (You should
show your work in arriving at your final result. Make sure you’re reviewed the “extra instructions”
for this problem set carefully.)
(a) [3 marks] (p ⇒ q) ⇒ ¬q.
(b) [3 marks] (p ⇒ ¬r) ∧ (¬p ⇒ q).
Page 2/5
CSC165H1, Problem Set 1
2. [8 marks] Fixed Points.
Let f be a function from N to N. A fixed point of f is an element x ∈ N such that f(x) = x. A least
fixed point of f is the smallest number x ∈ N such that f(x) = x. A greatest fixed point of f is the largest
number x ∈ N such that f(x) = x.
(a) [1 mark] Express using the language of predicate logic the English statement:
“f has a fixed point.”
You may use an expression like “f(x) = [something]” in your solution.
(b) [2 marks] Express using the language of predicate logic the English statement:
“f has a least fixed point.”
You may use the predefined function f as well as the predefined predicates = and <. You may not use any other predefined predicates. (c) [2 marks] Express using the language of predicate logic the English statement: “f has a greatest fixed point.” You may use the predefined function f as well as the predefined predicates = and <. You may not use any other predefined predicates. (d) [3 marks] Consider the function f from N to N defined as f(x) = x mod 7.1 Answer the following questions by filling in the blanks. The fixed points of f are: The least fixed point of f is: The greatest fixed point of f is: 1 Here we are using the modulus operator. Given a natural number a and a positive integer b, a mod b is the natural number less than b that is the remainder when a is divided by b. In Python, the expression a % b may be used to compute the value of a mod b. Page 3/5 CSC165H1, Problem Set 1 3. [6 marks] Partial Orders. A binary predicate R on a set D is called a partial order if the following three properties hold: (1) (reflexive) ∀d ∈ D, R(d, d) (2) (transitive) ∀d, d0 , d00 ∈ D, (R(d, d0 ) ∧ R(d 0 , d00)) ⇒ R(d, d00) (3) (anti-symmetric) ∀d, d0 ∈ D, (R(d, d0 ) ∧ R(d 0 , d)) ⇒ d = d 0 A binary predicate R on a set D is called a total order if it is a partial order and in addition the following property holds: ∀d, d0 ∈ D, R(d, d0 ) ∨ R(d 0 , d). For example, here is a binary predicate R on the set {a, b, c, d} that is a total order: R(a, b) = R(a, c) = R(a, d) = R(b, c) = R(b, d) = R(c, d) = R(a, a) = R(b, b) = R(c, c) = R(d, d) = True and all other values are False. (a) [2 marks] Give an example of a binary predicate R on the set N that is a partial order but that is not a total order. (b) [2 marks] Let R be a partial order predicate on a set D. R specifies an ordering between elements in D. Whenever R(d, d0 ) is True, we will say that d is less than or equal to d 0 , or that d 0 is greater than or equal to d. The following formula in predicate logic expresses that there exists a greatest element in D; that is, an element in D that is greater than or equal to every other element in D: ∃d ∈ D, ∀d 0 ∈ D, R(d 0 , d) An element in D is said to be maximal if no other element in D is larger than this element. The following formula in predicate logic expresses that there exists a maximal element in D: ∃d ∈ D, ∀d 0 ∈ D, d = d 0 ∨ ¬R(d, d0 ) Give an example of a partial order order R over {a, b, c, d} such that every element is maximal. (c) [2 marks] Give an example of a partial order R over {a, b, c, d} such that a ∈ D is maximal but a is not a greatest element. Justify your answer briefly. Page 4/5 CSC165H1, Problem Set 1 4. [13 marks] One-to-one functions. So far, most of our predicates have had sets of numbers as their domains. But this is not always the case: we can define properties of any kind of object we want to study, including functions themselves! Let S and T be sets. We say that a function f : S → T is one-to-one if no two distinct inputs are mapped to the same output by f. For example, if S = T = Z, the function f1(x) = x + 1 is one-to-one, since every input x gets mapped to a distinct output. However, the function f2(x) = x 2 is not one-to-one, since f2(1) = f2(−1) = 1. Formally we express “f : S → T is one-to-one” as: ∀x1 ∈ S, ∀x2 ∈ S, f(x1) = f(x2) ⇒ x1 = x2. We say that f : S → T is onto if every element in T gets mapped to by at least one element in S. The above function f(x) = x + 1 is onto over Z but is not onto over N. Formally we express “f : S → T is onto” as: ∀y ∈ T, ∃x ∈ S, f(x) = y Let t ∈ T. We say that f outputs t if there exists s ∈ S such that f(s) = t. (a) [1 mark] How many functions are there from {1, 2, 3} to {a, b, c, d}? (b) [1 mark] How many one-to-one functions are there from {1, 2, 3} to {a, b, c, d}? (c) [1 mark] How many onto functions are there from {1, 2, 3, 4} to {a, b, c}? (d) [2 marks] Now let R be a binary predicate with domain N×N. We say that R represents a function if, for every x ∈ N, there exists a unique y ∈ N, such that R(x, y) (is True). In this case, we write expressions like y = f(x). Define a predicate F unction(R), where R is a binary predicate with domain N × N, that expresses the English statement: “R represents a function.” You may use the predicates <, ≤, =, R, but may not use any other predicate or function symbols. In parts (e)-(h) below, you may use the predicate F unction(R) (in addition to the predicates <, ≤ , =, R) in your solution, but may not use any other predicate or function symbols. (e) [2 marks] Define a predicate that expresses the following English statement. “R represents an onto function.” (f) [2 marks] Define a predicate that expresses the following English statement. “R represents a one-to-one function.” (g) [2 marks] Define a predicate that expresses the following English statement. “R represents a function that outputs infinitely many elements of N.” (h) [2 marks] Now define a predicate that expresses the following English statement. “R represents a function that outputs all but finitely many elements of N.” Page 5/5