Examination Sheet № 9

Name:

Surname:

Group:

 

	Show that the set of reals is uncountable. Show that there is a bijection between the sets of all even natural numbers and the set of all integers.
	Basic counting principles. The sum rule. The product rule. Principle of inclusion-exclusion. Number of all functions from a set A to a set B. The Pigeonhole principle. The Generalized Pigeonhole principle. Show that there are either three mutual friends or three mutual enemies in a group of six people, such that each pair of individual of the group consists of two friends or two enemies.
	Construct the DNF, CNF and a polynomial for a proposition F(p,q,r) which is true iff (p,q,r) are from {(1, 1, 0), (1, 0, 0), (0, 0, 1), (0, 0, 0)}
	How many ways to select 23 ordered elements from a set consisting of 54 elements are there, if repetition is not allowed?
	Find a sequence {an : n = 0, 1, …} satisfying the recurrence relation xn + 6 = –6(xn–1 – 1) – 9xn–2, with the initial conditions a0 =1, a1 = –9.

 

 

Examination Sheet № 10

Name:

Surname:

Group:

 

	Propositions. Logical Operations: negation, conjunction, disjunction, implication, exclusive or, biconditional. Truth Tables. Bitwise logical operations. Tautology and a contradiction. Prove that (p → (q → r)) → ((p → q) → (p → r)) is a tautology without using truth tables. Propositional Equivalences. Tables of Logical Equivalences.
	Generalized permutation and combinations. Permutations and combinations with repetition. Permutations of sets with indistinguishable objects, distributing objects into boxes.
	Construct the DNF, CNF and a polynomial for a proposition F(p,q,r) which is true iff (p,q,r) are from {(1, 1, 0), (1, 0, 0), (0, 0, 1), (0, 0, 0)}
	How many ways to select 23 ordered elements from a set consisting of 54 elements are there, if repetition is not allowed?
	Find a sequence {an : n = 0, 1, …} satisfying the recurrence relation xn + 6 = –6(xn–1 – 1) – 9xn–2, with the initial conditions a0 =1, a1 = –9.