Exam text content

MATH.MA.210 Discrete mathematics Hxam, 08.05.2024
Answer five questions out of the

following six. All questions have the same value.
Questions

GQ We define the following propositions:
P means “Tt is lunchtime”, q means "It is a working day”
Also we define the following predicates:

A(x) means person 2 is hungry. B(«)
C(x) means & goes out.

The universal set is some set of people, that includes at least the person ” Jack” .

; and 7 means "It is sunny”.

means the person « eats at the university restaurant.

(a) Write the following sentence as a formula: "If it is sunny, then Jack will go out, and if
he is out and hungry, he will eat at the university restaurant”

(b) Write the following sentence as a formula: "If it is not sunny,

no one will go out on a
weekday”

(c) Write the following sentence as a formula:

”No one eats at the university restaurant if
it is not lunchtime and a working day”.

Q Prove the following is true for n € Z,. using induction:
n
(S2@i-1)) = 1? .
=I

3. The city has 12 electric busses. The city has 40 blue buses and 20 red buses. The city employs
25 foreign drivers. 6 electric buses are blue. 8 electric buses are driven by foreign drivers.
How many buses are there that have one or more of the characteristics: electric, blue, or
driven by foreigners? Use the inclusion exclusion principle.

4./Let A and B be sets such that |A| = m and |B| =n, and assume that m <n.

(a) How many different functions f : A B exist?
(b) How many of these functions are injections?
(c) If m =n, prove that an injection must be a bijection.

:
‘5. Let the operation x be defined for odd integers Z°% such that
cxy=x+y-1

7 Prove that Z°4 with the operation x forms a group, and explain what is the identity element
xh rat of the group, and how to calculate the inverse for each element.

6) (a) What is the remainder when 4119 is divided by 5?

(b) Which of the following equations have unique solutions, and why/why not?
solutions (i.e., all equivalence classes, obviously,
when a solution exists)

i. 4g = 7 mod 12
ii. 4g =7mod 11
iii. 22 = 6 mod 12

List all
as there are infinite many solutions
APPENDIX; Some helpful formulas and definitions

Definition 1. Ifa relation is reflexive, symmetric, and transitive, we call it an equivalence relation
or simply an equivalence.

Definition 2. A group is a pair (G,«) where G is a set ¢ is an operation on G with the following
properties

1, Associativity: (ab) ec =ae(bec) for a, b, and ce G.
2. Identity element: There exists an element e € G such that ea = aee=a for every aEG.

3. Inverse: for every a € G there is an element a~! € G such that aea-! =a-1 ea =e.

Definition 3. Let n € Z,. If for two numbers a,b € Z we have n | (a — 5), we say that a is
congruent with 6 modulo n and we denote a = b (mod n) or a =n b.