COMP9020 MST 12s2 Solutions
Kai 2012
Exercise 1 How many integers that are not divided by 3 are there between 123 and 66789?
The number of multiples of k in the interval [n .. m] is m − n−1 . So we calculate the number of
Copyright By PowCoder代写 加微信 powcoder
integers between 123 and 66789 as
66789 − (123 − 1) = 66667 (1) and the number of integers that are divided by 3 between 123 and 66789 as
66789 123 − 1
3 − 3 = 22263 − 40 = 22223 (2)
Subtracting (2) from (1) gives our result: 66667 − 22223 = 44444. Exercise 2 What is gcd(9876543213, 9876543210)?
gcd(9876543213, 9876543210) = gcd(3, 9876543210) = gcd(3, 0) = 3 since 3|9876543210.
Exercise 3 Let S, T, U, and V be sets. Prove that (S ∩ T) × (U ∩ V ) = (S × U) ∩ (T × V ).
(s, u) ∈ (S ∩ T ) × (U ∩ V ) ⇔ s ∈ (S ∩ T ) ∧ u ∈ (U ∩ V ) ⇔s∈S∧s∈T∧u∈U∧u∈V ⇔s∈S∧u∈U∧s∈T∧u∈V
⇔ (s, u) ∈ (S × U ) ∧ (s, u) ∈ (T × V ) ⇔ (s, u) ∈ (S × U ) ∩ (T × V )
Exercise4 Letφ1 =(p⇒(q∨r)),φ2 =(s⇒(q∨p)),andφ=φ1∧φ2.
1. Draw Karnaugh maps for the three formulae, φ1, φ2, and φ.
2. Read off a minimal DNF for φ.
3. Give a minimal CNF for ¬φ1.
commutativity of ∧
Def. of ∩
1. (To improve legibility, only the false entries are marked. It turns out to be convenient to give the first two maps over the whole set of propositions rather than just the involved three. That way, the third map is trivailly obtained from the first two, and I can just copy&paste the LATEX code.)
p p p ̄ p ̄ φ 2 : p p p ̄ p ̄ φ : p p p ̄ p ̄
q s ̄ q s ̄ q s ̄ qsqsqs q ̄0 s q ̄ 00s q ̄0 00s q ̄0 s ̄ q ̄ s ̄ q ̄0 s ̄ r ̄ r r r ̄ r ̄ r r r ̄ r ̄ r r r ̄
2. A minimal DNF for φ is q∨pr∨p ̄s ̄.
3. A minimal CNF for ¬φ1 is obtained most easily by reading off a minimal DNF for φ1 and then using
de Morgan. A minimal DNF for φ1 is p ̄∨q∨r. Hence p∧q ̄∧r ̄is a minimal CNF for ¬φ1. Exercise 5 Suppose Portia puts a dagger in one of three caskets and places the following inscriptions on
the caskets:
Gold casket: The dagger is in this casket.
Silver casket: The dagger is not in this casket.
Lead casket: At most one of the caskets has a true inscription.
Portia tells her suitor to pick a casket that does not contain the dagger. Which casket should the suitor choose? Formalise the problem in propositional logic and calculate an answer.
We formalise using six propositions:
g is true iff the dagger is in the gold casket,
s is true iff the dagger is in the silver casket,
l is true iff the dagger is in the lead casket,
G is true iff the inscription on the gold casket is true,
S is true iff the inscription on the silver casket is true, and
L is true iff the inscription on the lead casket is true.
We need to model that there’s a dagger in precisely one of the caskets.
(g ⇔ s ̄l) ∧ (s ⇔ g ̄l) ∧ (l ⇔ g ̄s ̄) (3)
The inscriptions are modeled as follows.
G⇔g (4) S ⇔ ¬s (5) L ⇔ ((G ⇒ S ̄L ̄) ∧ (S ⇒ G ̄L ̄) ∧ (L ⇒ G ̄S ̄)) (6)
A quick check reveals that both g and s are consistent with (3)–(6). Our only hope is hence l. We deduce the following consequences from l being true:
L ⇔ (L ̄ ∧ L ̄)
by (3) and (4) (7) by (3) and (5) (8) by (6)–(8) (9)
But L ⇔ L ̄ is equivalent to false, contradicting our assumption about l being true. We conclude that the suitor must pick the lead casket to be safe.
Exercise 6 In B5, what is the value of (0,0,1,1,1)∧(0,1,0,1,0)?
Recall that “∧” in Bn corresponds to the bit-wise “and”, so the result is (0∧0,0∧1,1∧0,1∧1,1∧0)=(0,0,0,1,0) .
Exercise 7 How many Boolean algebra isomorphisms of P({a,b,c}) onto B3 are there? Explain your answer briefly.
Such an isomorphism is completely determined by how we map the atoms, which in this case are the singleton sets {a}, {b}, and {c}. They must be mapped onto the atoms of B3, which are 001, 010, and 100. Thereare3!=3·2·1=6ontofunctionsbetweensetsofsize3,soouransweris6.
Exercise 8 Let S be a finite set and let n ∈ N. How many 1. functions,
2. onto functions,
3. binary relations, and
4. n-ary relations
are there on S? Explain your answers briefly.
1. |S||S| — for every element a free choice between all elements 2. |S|! — onto functions on finite sets are 1–1 (permutations) 3. 2(|S|2) — size of the powerset of the set of pairs
4. 2(|S|n) — size of the powerset of the set of n-tuples
There was a severe typo in the exam whence I had to discard the last question. Exercise9LetS,T,andUbesets. LetR1 ⊆S×TandR2 ⊆T×U. Provethat(R1;R2)← =
(R2←); (R1←).
(I use the notation ∃x(P(x)) to express “there exists an x such that P(x) is true.”)
(u, s) ∈ (R1; R2)← ⇔ (s,u) ∈ R1;R2
⇔ ∃t ((s, t) ∈ R1 ∧ (t, u) ∈ R2)
⇔ ∃t ((t, s) ∈ R1← ∧ (u, t) ∈ R2←) ⇔ ∃t ((u, t) ∈ R2← ∧ (t, s) ∈ R1←) ⇔ (u, s) ∈ (R2←); (R1←)
Def. of .←
Def. of .←
commutativity of ∧
Def. of ;
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com