- Questions & Answers
- Accounting
- Computer Science
- Automata or Computationing
- Computer Architecture
- Computer Graphics and Multimedia Applications
- Computer Network Security
- Data Structures
- Database Management System
- Design and Analysis of Algorithms
- Information Technology
- Linux Environment
- Networking
- Operating System
- Software Engineering
- Big Data
- Android
- iOS
- Matlab

- Economics
- Engineering
- Finance
- Thesis
- Management
- Science/Math
- Statistics
- Writing
- Dissertations
- Essays
- Programming
- Healthcare
- Law

- Log in | Sign up

Table of Points for marking purposes. Do not write in this table.

multiple-choice true-or-false short-answer long-answer TOTAL

max points possible XXXXXXXXXXpoints

points obtained

Multiple-Choice Questions.

Write your choice in the answer box. No justification is needed.

Q1. Let A = {1, 2} and let B = {s, t, u, v, w}. How many injective functions are there

from A to B?

A. 20 B. 25 C. 32

D. 0 E. 10 F. None of the previous answers.

Answer: [2 points]

Q2. Let R be the equivalence relation on the set A = {�6,�2, 0, 1, 4, 5, 6, 7, 15} defined by

xRy ()

⇣

x ⌘ y (mod 5) or x ⌘ �y (mod 5)

⌘

Which one (if any) of the following statements is true?

A. {�6, 6} is an equivalence class with respect to R.

B. [�2]R = [6]R.

C. P =

�

{�6,�2}, {0}, {1, 4, 5, 6, 7, 15}

is the partition of A into equivalence classes.

D. P =

�

{�6, 1, 4, 6}, {�2, 7}, {0, 5, 15}

is the partition of A into equivalence classes.

E. 4R7.

F. None of the above.

Answer: [2 points]

2

Q3. One of the following statements is false. Which one?

A. A \ (B [ C) = (A \ B) [ (A \ C)

B. A \ (B [ C) = A [ (B [ C)

C. A [ (B \ C) = A \ (B \ C)

D. (A [ B) \ C = (A \ C) [ (B \ C)

E. (A [B) [ C = (A [B) \ C

Answer: [2 points]

Q4. How many strings of length 6 with symbols from {a, b, c, d, e} start with ‘ace’ or end with

‘ee’ ? (this is inclusive or)

A. 755 B. 36 C. 750 D. 35 E. 745 F. 34

Answer: [2 points]

3

Q5. Let G be a graph with 7 vertices and 10 edges. If every vertex of G has degree 2 or 3, then

how many vertices of each degree does G have?

A. G has 0 vertices of degree 2 and 7 vertices of degree 3.

B. G has 1 vertex of degree 2 and 6 vertices of degree 3.

C. G has 2 vertices of degree 2 and 5 vertices of degree 3.

D. G has 3 vertices of degree 2 and 3 vertices of degree 3.

E. G has 4 vertices of degree 2 and 3 vertices of degree 3.

F. No such graph exists.

Answer: [2 points]

Q6. How many binary strings of length 7 contain at least 5 zeros?

A. 21 B. 32 C. 96 D. 4 E. 49 F. 29

G. None of the above.

Answer: [2 points]

4

True-or-False Questions.

Circle the co

ect responses. No justification is needed.

Q7. Consider the following three graphs: [1.5 points]

G H L

Circle the co

ect responses.

G is a tree. T F

H is a forest. T F

L is a tree. T F

Q8. Consider the following sets: [3 points]

S =

�

Ø, 1, {1}

and T =

�

1, {Ø, 1}

Circle the co

ect responses.

|S ⇥ T | = 9. T F

�

{1}

✓ S T F

|S \ T | = 2 T F

�

{1}, {1}

�

2 T ⇥ S T F

|S [ T | = 4 T F

|P(T )| = 4 T F

5

Q9. Consider the following relation on the set : [2 points]

xRy () x(1 + y) is even.

What properties does the relation R possess? Circle the co

ect responses.

R is reflexive. T F

R is symmetric. T F

R is antisymmetric. T F

R is transitive. T F

Q10. Consider the following propositions with atomic variables x and y: [2.5 points]

P1 : x ^ ¬y

P2 : ¬x _ ¬y

P3 : x ! y

C : y ! x

Circle the co

ect responses.

The set {P1, P2, P3} is a consistent set of propositions. T F

The set {P1, P2} is a consistent set of propositions. T F

The argument (P1 ^ P2 ^ P3) ! C is a valid argument. T F

The compound proposition P1 ^ P2 ! C is a tautology. T F

Compound propositions P1 and ¬P3 are logically equivalent. T F

6

Short-Answer Questions.

Write your final answer in the answer box.

Wherever indicated, you must

iefly justify your answers to receive full marks.

Q11. Let a, b. and c be propositional variables.

Give a disjunctive normal form (DNF) for the following compound proposition:

P : (a $ b) ^ (b _ ¬c)

DNF for P :

Justification: [1.5 points]

7

Q12. Fully evaluate the following expression:

✓

9

6

◆

+

✓

9

7

◆

=

Justification: [1.5 points]

Q13. Consider the following sequence:

(0, 1, 2, 3, 4, 5, 5)

(a) Does there exist a graph with the above degree sequence? Circle: YES NO

If so, draw an example of such a graph; otherwise,

iefly explain why no such graph

exists.

(b) Draw an example of a tree whose degree sequence is (1, 1, 1, 1, 3, 3).

No justification is needed. [2 points]

8

Q14. Determine the coe�cient of

1

x8

in the expansion of

✓

3x2 +

5

x4

◆10

.

Your answer may include unevaluated factorials, binomial coe�cients, powers, products,

or sums.

Coe�cient of x

�8

:

Justification: [2.5 points]

9

Q15. Give an example of a compound proposition P such that

• P consists of the propositional variables x, y, and z (all three variables must be

used).

• P contains only the logical connectives ¬ and ! and P must contain both these

connectives.

• P is a contradiction (justification required below).

Make sure your proposition P contains only the variables x, y, and z, the logical con-

nectives ¬ and ! and appropriate parentheses.

P =

Justification that P is a contradiction: [2 points]

10

Q16. Let f : ! ⇥ be a function defined by f(x) = (x3, x4). [3.5 points]

Answer the following questions regarding the above function f .

To justify your answers, either give a proof or a concrete numerical counterexample.

Is f is injective? Circle: YES NO

Justification (proof or counterexample):

Is f is surjective? Circle: YES NO

Justification (proof or counterexample):

Is f is invertible? Circle: YES NO

No justification is needed for this part.

11

Q17. Which of the following four graphs are bipartite? [2 points]

For each graph, circle the co

ect response and justify your answer by either giving a prope

2-colouring of the graph, or by indicating an odd cycle in the graph.

G Is G bipartite? Circle: YES NO

H Is H bipartite? Circle: YES NO

K Is K bipartite? Circle: YES NO

L Is L bipartite? Circle: YES NO

12

Long-Answer Questions.

Detailed solutions are required.

Q18. Let m be a positive integer.

Give a proof by contradiction of the following statement:

Statement:

If 3m+1 ma

les are placed into m jars, then at least one jar will contain at least 4 ma

les.

[5 points]

13

Q19. Use Mathematical Induction to prove that

(2n)! is a multiple of 2n+1 for all integers n � 2.

Clearly state the proposition to be proved, Basis of Induction, Induction Hypothesis, and

Induction Step. Clearly indicate where the Induction Hypothesis is used in your proof.

[5 points]

14

Q20. Use a truth tree to determine whether or not the proposition P below is a tautology. If

you claim that P is not a tautology, give all counterexamples.

P :

�

c _ (b ! ¬a)

�

$ ¬(a ^ b)

Clearly indicate the root of the tree. Use the

anching rules precisely as taught in class. Do

not use equivalences. Do not skip steps or combine

anching rules. Make sure your truth

tree is fully grown.

Complete truth tree:

Is P a tautology? Circle: YES NO

If you circled NO, give all counterexamples:

[5 points]

15

Q21. Define a binary relation R on the set A = {binary strings of length 4} as follows:

For all strings s, t 2 A,

sRt if and only if s and t have the same number of ones.

(a) Prove that R is an equivalence relation.

(b) Give the equivalence class of the string s = ‘1010’ with respect to the relation R.

h

‘1010’

i

R

=

[5 points]

16

Q22a. Consider the following two graphs: [4 points]a

c

d

e

f

G

z

xw

v

u

y

H

Are G and H isomorphic? If so, give an isomorphism between them and verify that you

function is an isomorphism; otherwise, clearly explain why they are not isomorphic.

Q22b. Now consider these two graphs:

5 6 7 8

1 2 3 4

K

w x y z

s t u v

L

Are K and L isomorphic? If so, give an isomorphism between them and verify that you

function is an isomorphism; otherwise, clearly explain why they are not isomorphic.

17

Extra page for scrap work.

:-)

18

Answered 2 days AfterApr 11, 2022

CamScanner 04-14-2022 01.57.37

SOLUTION.PDF## Answer To This Question Is Available To Download

- 1)An April 21, 2009, USA Today article titled “On road, it’s do as I say, not as I do” reported that 58% of U.S. adults speed up to beat a yellow light. Suppose you conduct a survey in your hometown...SolvedMay 16, 2022
- Assessment 3 Students will be exploring and analysis the application of information technology related to the topic which are identified by students, and they must recognize an application that can be...SolvedMay 10, 2022
- Name: AMAT 220: Linear Algebra Final Exam May, 2022 Show all work for each problem in the space provided. If you run out of room for an answer, continue on the back of the page. Question Points Bonus...SolvedMay 05, 2022
- Question 7 (15 marks) SECTION 3 A car manufacturer states that its new model does 32.5 miles per gallon (mpg). A recent independent study of 50 of the new cars showed a mean mpg of only 30.4 with a...SolvedMay 03, 2022
- Question 3 (15 marks) a variable has a normal distribution with an arithmetic mean of 100 and a standard deviation of 10. what is the probability that values will be115 or greater. Question 4 (15...SolvedMay 03, 2022
- I am looking to take 3 proctored exams this Friday and would like someone to take them for me. Classes 1. Calculus 1 2. Physics 101 and 3. Discrete Mathematics. The tests are multiple choice...SolvedMay 02, 2022
- Name: _________________________ XXXXXXXXXXT h e P re ci se D ef in it io n o f a L im it 1.4 The Precise Definition of a Limit Ticket in the Door In order to be prepared for class you must watch the...SolvedMay 01, 2022
- 1) The Environmental Protection Agency (EPA) is charged with monitoring “acid rain," a term for the fall of water through an acidic atmosphere. Acidity is measured on the pH scale, where pure water...SolvedApr 25, 2022
- ENGR 202: ENGINEERING ANALYSIS II NUMERICAL INTEGRATION Name: April 21, 2022 Consider an elastic pendulum shown in the below figure. The motion of the system is described by the following two...SolvedApr 25, 2022
- Linear Algebra Practice test, please check attached fileSolvedApr 23, 2022

Copy and Paste Your Assignment Here

About Us | Contact Us | Help | Privacy Policy | Revision and Refund Policy | Terms & Conditions | Honor Code

Copyright © 2022. All rights reserved.