Discrete Mathematics Answers

R1={(a, b) € R |a >b|}, the "greater than relation.

R2=(a, b) € R|a>=b|}. the "greater than or equal to relation

R3=(a, b) €R |a < b), the "less than" relation.

R4=(a, b). the "less than or equal to

R5=(a , b) € R |a = b|. the "equal to" relation

In the grammar of natural languages, such as Sesotho, noun words are categorised into equivalent noun classes, based on their generating “stems”. A stem is a noun word prefix, which is the “first syllable” of the noun word, from where suffixes could be attached to generate different noun words. In Sesotho, in particular, the equivalence noun classes are based on the following two relations:

R₁: A noun word x is related to another noun word y iff x and y have the same stem

R₂: A noun word x is related to another noun word y iff x and y have no stems. R₂

generates the equivalence Class 9.

a) Prove that:

i) R₁ is an equivalence relation

ii) R₂ is also an equivalence relation

b)

i) List any three (3) noun words belonging to Class 9

ii) Show that “se” is a stem by showing that C(“sekatana”) is an equivalence class by listing any first eleven (11) words in it.

a) Write a finite state machine (FSM) for an automatic reversible 6 modulo counter as follows:

The counter counts 0, 1, 2, 3, 4, 5 (when its internal memory input is registering 0) and reverses: 5 4, 3, 2, 1, 0 (when its internal memory input is registering 1)

b) As a result of a) above, design and implement a minimal logic circuit for the

automatic reversible 6 modulo counter. If the counter were to enter any of the

unwanted states, it should be reset to count from 0 on the next clock pulse.

Hint: The counter uses 4 bits. Let the most significant bit (MSB) be the memory bit

that the counter will set as 0 for counting up and will reset it to 1 when counting

downwards.

a) Find a restricted statement form in conjunctive normal form (CNF) logically

equivalent to the statement form:

¬P Q "\\land" ¬R

b) Find a restricted statement form in disjunctive normal form (DNF) logically

equivalent to the statement form:

¬P Q "\\land" ¬R

a) Let \mathbb{N} be the set of natural numbers, O, the set of odd numbers and S, the set of

square numbers. Consider the bijections:

f : \mathbb{N} "\\to" O, f(n) = 2n + 1

g : O   S, g(d)=\frac{d2 -2d +1}{4}
Consider f \circ g.

Determine whether or not the specified composition is possible. If it is not possible,

explain in details why it is not. If it is possible, then

i) compute:

1. the resulting composition

2. the corresponding image set

ii) Determine whether or not the specified composition is a bijection.

Consider the human race. Suppose a person x is related to another human being y if x

has the same father as y.

a) Prove that this is an equivalence relation.

b) Compute C(Thabane) and C(Mosisili)

c) Can C(Thabane) and C(Mosisili) ever intersect? If so, how so. If not, why not.

d) Compute the partition of the human race under this relation.

Consider the statement form

(P \downarrow Q) \downarrow R

Now, find a restricted statement form logically equivalent to it, in

a) Disjunctive normal form (DNF).

b) Conjunctive normal form (CNF).

a) Prove that the set { \downarrow } is an adequate set of connectives.

............................................................................................................................ \

b) Consider the set

F = {y | y = ax³ + b},

a, b being constants such that a != 0 and x   \mathbb {R}.
Is F \approx \mathbb{R}? If so, prove it. If not, explain in details why it is not the case.

a) Consider the function, bin, that converts an integer to a binary digit as:

bin : Z 6{-1, 0, 1}, bin(x) = x congruence modulo 2.

Now, define the logical NOT function as:

NOT: Z"\\to" {0, 1}, NOT(x)="\\begin{Bmatrix}\n 0, if x != 0\\\\\n 1, if x=0 \n\\end{Bmatrix}"

i) Write C++ code for the logical NOT function specified above.

ii) Using the function defined in i) above, write in C++ the polymorphic logical exor

function:

int exor(int x, int y):- it returns x r y

int exor(int * bits, int N):- it returns the exor of the N binary integers, bits.

b) As a result of a) above, write in C++ the polymorphic logical not exor function,

nexor:

int nexor(int x, int y):- it returns the negation of x r y

int nexor(int * bits, int N):- it returns the nexor of the N binary integers, bits