A$1$

$1$

A$1$

$2$

HPIT$4004$ Discrete Mathematics for Computing $2023-2024$

Assignment $1$: Sets, Propositional Logic, Quantificational Logic Total: $100$ marks

$($Total $7$ marks$)$ Let $S=\{a,b,c,d,e,f,g\}$ represent the seven segments of the LED font $($Figure $1).$ Using the given order, each element in the set is coded using a binary string. For example, the LED font number $2$ is represented by the set $\{a,b,c,f,g\}$ or the binary string $1110011.$

Figure $1$: LED font with seven segments

$($a$)(1$ mark$)$ How many elements are there in $P(S)?$

$($b$)(3$ marks$)$ To which set in $P(S)$ does the binary string $0111100$ correspond? What is the corresponding LED font number it represents?

$($c$)(1$ mark$)$ Write the binary string that corresponds to the LED font number $3.$

$($d$)(1$ mark$)$ Write the set that corresponds to the LED font number $7.$

$($e$)(1$ mark$)$ Which binary string corresponds to $\frac{O}{?}?$

$($Total $10$ marks$)$ Draw a Venn diagram to illustrate the set of numbers $D=\{1,2,$dots,$7\}$ and the set of numbers $M=\{1,2,$dots,$12\},$ representing the days and the months, respectively.

$($Total $19$ marks$)$ Use the sets $P=p$:$p$ is a prime number, $x=x$:$x$ is an integer, and $Z^{+}$for the following:

$($a$)(2$ marks$)$ List the first $10$ smallest elements of $P.$

$($b$)(2$ marks$)$ Describe the set $x$ using the listing method.

$($c$)(3$ marks$)$ Describe the set $Y$ using the inclusion method.

$($d$)(2$ marks$)$ Describe the set $Z$ using the listing method.

$($e$)(4$ marks$)$ Determine which of the sets are finite and which are infinite.

$($f$)(1$ mark$)$ What is the intersection of the set $P$ and $Y?$

$($g$)(1$ mark$)$ What is the union of the set $P$ and $Z^{+}?$

$($h$)(1$ mark$)$ What is the symmetric difference between the set $Y$ and $x?$

$($i$)(1$ mark$)$ What is the difference between the set $Y$ and $x?$

$($j$)(1$ mark$)$ What is the intersection between the set $\frac{O}{?}$ and $P?$

$($k$)(1$ mark$)$ What is the union between the set $\frac{O}{?}$ and $P?$

$($Total $27$ marks$)$ In this question, you are required to express the statements using predicates and quantifiers. State the meanings of each predicates clearly in each subquestions.

$($a$)(9$ marks$)$ Express the statements $($i$)$ "There are some students.", $($ii$)$ "There are some courses.", and $($iii$)$ "Some students enrolls in some courses." using predicates and quantifiers.

$($b$)(9$ marks$)$ Express the statements $"$No student is enrolled in all courses." using predicates and quantifiers.

$($c$)(9$ marks$)$ Express the statements "Every course has at least one student enrolled." using predicates and quantifiers.

$($Total $16$ marks$)$

$($a$)(3$ marks$)$ Simplify $(po+p)o+p.$

$($b$)(5$ marks$)$ By constructinng a truth table using the propositions $p,q,$ and $r,$ illustrate whether the operation $o+$ is associative.

$($c$)(5$ marks$)$ Justify whether $(p^{{?}^{?}}r)o+(q^{{?}^{?}}r)-=(po+q{)}^{{?}^{?}}r.$

$($d$)(3$ marks$)$ Provide an example proposition $($in English$)$ that illustrates $(po+p).$

$($Total $21$ marks$)$

$($a$)(5$ marks$)$ Is it possible to find a logically equivalent form of the statement $(not{p}^{{?}^{?}}q)r$ that uses only negation, disjunction, and$/$or conjunction? Justify your answer.

$($b$)(7$ marks$)$ Simplify $((p^{{?}^{?}}q)r)harr(p(qr)).$

$($c$)(9$ marks$)$ Given any statement form, is it possible to find a logically equivalent form that uses only negation and disjunction? Justify your answer.

End $-$