Logic and Discrete Mathematics

Logic and Discrete Mathematics
1. [10 pts.] Consider the weak partial order
P = (ff1g; f2g; f4g; f1; 2g; f1; 4g; f2; 4g; f3; 4g; f1; 3; 4g; f2; 3; 4gg; ?):
a. Find the maximal elements in P.
b. Find the minimal elements in P.
c. Find the maximum element in P if it exists.
d. Find the minimum element in P if it exists.
e. Find all the upper bounds of ff2g; f4gg in P.
f. Find the least upper bound of ff2g; f4gg in P if it exists.
g. Find all the lower bounds of ff1; 3; 4g; f2; 3; 4gg in P.
h. Find the greatest lower bound of ff1; 3; 4g; f2; 3; 4gg in P if it
exists.
2. [10 pts.] Suppose (S1; =1) and (S2; =2) are partial orders. Prove that
(S1 × S2; =) is a partial order where (s1; s2) = (s0 1; s0 2) iff s1 =1 s0 1 and
s2 =2 s0 2.
3. [10 pts.] Show that (N × N; =), where = is lexicographical order on
N × N, is a well-order.
4. [10 pts.] The strict total order (R; <) is both dense and complete. Let
(R [ f-1; +1g; <) be the strict total order that extends (R; <) by
adding -1 and +1 as minimum and maximum elements. Show that
(R [ f-1; +1g; <) is also dense and complete.
15. [10 pts.] Show that (N; j) is a complete lattice.
6. [10 pts.] Suppose F is the set of partial functions f : N ! N. (Recall
that a partial function is a function f : A ! B that may be undefined
on some members of A. Hence, by this definition, a total function
is a partial function.) For f; g 2 F , f is a subfunction of g, written
f v g, if the domain Df of f is a subset of the domain of g and, for
all x 2 Df , f(x) = g(x). Show that (F; v) is a weak partial order.
7. [10 pts.] This is a continuation of the previous question.
a. Describe the set of minimal elements of (F; v).
b. Describe the set of maximal elements of (F; v).
c. Does (F; v) have a minimum element? If so, what is it?
d. Does (F; v) have a maximum element? If so, what is it?
e. Show that (F; v) is a not a lattice.
f. Show that (F; v) is a meet-semilattice.
8. [10 pts.] Let S be any set. Show that (f;; Sg; ;; S; [; \; ) is a boolean
algebra.
9. [10 pts.] A cofinite subset of a set S is a subset S0 of S such that the
complement of S0 in S is finite. Let S be the finite and cofinite subsets
of N . Show that (S; ;; N; [; \; ) is a boolean algebra.
10. [10 pts.] Show that the idempotent laws follow from the axioms of a
boolean algebra.
11. [10 pts.] Prove
nXi
=1
(2i – 1) = n2:
12. [10 pts.] Prove
nXi
=0
i2 = n(n + 1)(2n + 1)
6
:
13. [10 pts.] Let S be the set of bit strings defined inductively by:
a. “0” 2 S.
b. If s 2 S, then “0” + s 2 S and s + “0” 2 S.
c. If s 2 S, then , “0” + s + “1” 2 S and “1” + s + “0” 2 S.
s + t denotes the concatenation of s and t. Prove by structural induction that, for all strings s 2 S, the number of 1s in s is less than or
equal to the number of 0s in s.
214. [10 pts.] Let Nat be the natural numbers defined as an inductive type,
odd : Nat ! B be the function that maps the odd natural numbers
to true and the even natural numbers to false, and even : Nat ! B
be the function that maps the even natural numbers to true and the
odd natural numbers to false. Define odd and even simultaneously by
pattern matching using \mutual recursion”.
15. [10 pts.] Let mirror : BinTree ! BinTree be the function that maps a
binary tree to its \mirror image”.
a. Define mirror by pattern matching.
b. Prove
8 t : BinTree : mirror (mirror t) = t
by structural induction.
3