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
