Part 1: Boolean Algebra:
1. Write x ⊕ y in disjunctive normal form and conjunctive normal form. Using of these forms, simplify these expressions:
a) x ⊕ 0
b) x ⊕ 1
c) x ⊕ x
d) x ⊕ x ̅
2. Find the sum-of-products expansions of the Boolean function F(x, y, z) that equals 1 if and only if:
a) x = 0.
b) xy = 0.
c) x + y = 0.
d) xyz = 0
3. Express each of these Boolean functions using the operators ⋅ and −.
a) x + y + z
b) x + y ̅(x ̅ + z)
c) (x + y ̅ ) ̅
d) x ̅(x + y ̅ + z ̅)
Part 2: Sets:
1. For each of these pairs of sets, determine whether the first is a subset of the second, the second is a subset of the first, or neither is a subset of the other.
a) the set of people who speak English, the set of people who speak English with an Australian accent
b) the set of fruits, the set of citrus fruits
c) the set of students studying discrete mathematics, the set of students studying data structures
d) the set of students in the college of computing and IT, the set of students at UDST
2. Determine whether these statements are true or false.
a) ∅ ∈ {∅}
b) ∅ ∈ {∅, {∅}}
c) {∅} ∈ {∅}
d) {∅} ∈ {{∅}}
e) {∅} ⊂ {∅, {∅}}
f ) {{∅}} ⊂ {∅, {∅}}
g) {{∅}} ⊂ {∅, {{∅}}}
h) ∅ ⊂ {{∅}, {{∅}}}
3. Can you conclude (with a proof) that A = B if A, B, and C are sets such that
a) A ∪ C = B ∪ C?
b) A ∩ C = B ∩ C?
c) A ∪ C = B ∪ C and A ∩ C = B ∩ C?
4. Sets in python
a) Write a code to generate the set setA of positive integers less than 1000 which last two digits are divisible by 43 (example 186 is in the set because 86 is divisible by 43)
b) Write a code to generate the set setB of positive integers less than 1000 which first two digits are divisible by 24 (example 725 is in the set because 72 is divisible by 24)
c) Write a code to compute setC the union of setA and setB
d) Write a code to compute setD the intersection of setA and setB
e) Check using a python code that |setA|+|setB|=|setC|+|setD|
f) Write a function cartesian that has two sets as input and returns their cartesian product as output (without importing any library)!
g) Use your function to find the cartesian product between setD and the set of colors on a traffic light.
Part 1: Boolean Algebra
Disjunctive Normal Form (DNF) and Conjunctive Normal Form (CNF) of x ⊕ y:
DNF: (x ∧ ¬y) ∨ (¬x ∧ y) CNF: (x ∨ y) ∧ (¬x ∨ ¬y)
a) x ⊕ 0: DNF: (x ∧ ¬0) ∨ (¬x ∧ 0) = x ∧ ¬x = 0 CNF: (x ∨ 0) ∧ (¬x ∨ ¬0) = x ∧ ¬x = 0
b) x ⊕ 1: DNF: (x ∧ ¬1) ∨ (¬x ∧ 1) = ¬x ∨ x = 1 CNF: (x ∨ 1) ∧ (¬x ∨ ¬1) = 1
c) x ⊕ x: DNF: (x ∧ ¬x) ∨ (¬x ∧ x) = 0 ∨ 0 = 0 CNF: (x ∨ x) ∧ (¬x ∨ ¬x) = x ∧ ¬x = 0
d) x ⊕ ¬x: DNF: (x ∧ ¬¬x) ∨ (¬x ∧ ¬x) = x ∨ ¬x CNF: (x ∨ x) ∧ (¬x ∨ ¬x) = x ∧ ¬x
Sum-of-Products expansions of F(x, y, z):
a) F(x, y, z) = x’ + y + z
b) F(x, y, z) = xy’z’
c) F(x, y, z) = xyz’
d) F(x, y, z) = xy’z + xyz’
Expressing Boolean functions using ⋅ and −:
a) x + y + z: Using ⋅: x ⋅ y ⋅ z Using −: (¬(¬(¬x ⋅ ¬y) ⋅ ¬z))
b) x + y ̅(x ̅ + z): Using ⋅: x + y’⋅(x’ + z) Using −: (¬(¬(¬(¬(¬x’) ⋅ ¬y’) ⋅ ¬(¬z))))
c) (x + y ̅ ) ̅: Using ⋅: ¬(x + y’) Using −: (¬((¬(¬(¬(¬(¬(¬x’)) ⋅ ¬y’))))))
d) x ̅(x + y ̅ + z ̅): Using ⋅: x’⋅(x + y’ + z’) Using −: (¬(¬(¬((¬(¬((¬(¬(¬(¬(¬(¬(¬(¬(¬(¬(¬(¬x)))))))))))))))))
Part 2: Sets
Subset determination:
a) The set of people who speak English is a subset of the set of people who speak English with an Australian accent. b) The set of citrus fruits is a subset of the set of fruits. c) Neither set is a subset of the other as they represent different areas of study. d) Neither set is a subset of the other as they represent different groups of students.
True or False:
a) True b) True c) False d) True e) False f) True g) True h) True
Conclusions regarding set equality:
a) A = B cannot be concluded from A ∪ C = B ∪ C. b) A = B can be concluded from A ∩ C = B ∩ C. c) A = B can be concluded from both A ∪ C = B ∪ C and A ∩ C = B ∩ C.
Sets in Python:
a)
setA = {n for n in range(1000) if n % 100 % 43 == 0}
b)
setB = {n for n in range(1000) if n // 100 % 24 == 0}
c)
setC = setA.union(setB)
d)
setD = setA.intersection(setB)
e)
len_setA = len(setA)
len_setB = len(setB)
len_setC = len(setC)
len_setD = len(setD)
sum_AB = len_setA + len_setB
sum_CD = len_setC + len_setD
sum_AB == sum_CD # Returns True if the equation holds
f)
def cartesian(set1, set2):
return {(a, b) for a in set1 for b in set2}
set_product = cartesian(setD, {‘red’, ‘yellow’, ‘green’})
g)
traffic_light_colors = {‘red’, ‘yellow’, ‘green’}
cartesian_product = cartesian(setD, traffic_light_colors)
