## UGRD-CS6105 Discrete Mathematics

**Prelim Q1 to Prelim Exam, Midterm Q1, Q2, Finals Q1, Q2 **

**Prelim Q1 to Prelim Exam, Midterm Q1, Q2, Finals Q1, Q2**

Classify the sentence below as an atomic statement, a molecular statement, or not a statement at all. If the statement is molecular, identify what kind it is (conjuction, disjunction, conditional, biconditional, negation)

Everybody needs somebody sometime.

-Atomic N/A

Classify the sentence below as an atomic statement, a molecular statement, or not a statement at all. If the statement is molecular, identify what kind it is (conjuction, disjunction, conditional, biconditional, negation).

We can have donuts for dinner, but only if it rains.

-Molecular Conditional

Let A = {1, 2, 3, 4, 5} and B = {3, 4, 5, 6, 7}

Find A ∩ B

-{3, 4, 5}

Let A = {1, 2, 3, 4, 5} and B = {3, 4, 5, 6, 7}

Find A \ B

-{1, 2}

Determine whether the sentence below is an atomic statement, a molecular statement, or not a statement at all.

• The customers wore shoes.

-Molecular

Classify the sentence below as an atomic statement, a molecular statement, or not a statement at all. If the statement is molecular, identify what kind it is (conjuction, disjunction, conditional, biconditional, negation).

Every natural number greater than 1 is either prime or composite.

-Molecular Conditional

Find the cardinality of R = {20,21,...,39, 40}

| R | = 21

Find the cardinality of S = {1, {2,3,4},0}

| S | = 3

Let A = {1, 2, 3, 4, 5} and B = {3, 4, 5, 6, 7}

Find A U B

-{1, 2, 3, 4, 5, 6, 7}

Classify the sentence below as an atomic statement, a molecular statement, or not a statement at all. If the statement is molecular, identify what kind it is (conjuction, disjunction, conditional, biconditional, negation). The sum of the first 100 odd positive integers.

-Atomic N/A

In my safe is a sheet of paper with two shapes drawn on it in colored crayon. One is a square, and the other is a triangle. Each shape is drawn in a single color. Suppose you believe me when I tell you that if the square is blue, then the triangle is green. What do you therefore know about the truth value of the following statement?

The square and the triangle are both green. - The statement is FALSE

Find | R | when R = {2, 4, 6,..., 180}

- 90

Let A = {3, 4, 5}. Find the cardinality of P(A)

- 8

In my safe is a sheet of paper with two shapes drawn on it in colored crayon. One is a square, and the other is a triangle. Each shape is drawn in a single color. Suppose you believe me when I tell you that if the square is blue, then the triangle is green. What do you therefore know about the truth value of the following statement?

The square and the triangle are both blue. - The statement is FALSE

The cardinality of {3, 5, 7, 9, 5} is 5.

-False

n my safe is a sheet of paper with two shapes drawn on it in colored crayon. One is a square, and the other is a triangle. Each shape is drawn in a single color. Suppose you believe me when I tell you that if the square is blue, then the triangle is green. What do you therefore know about the truth value of the following statement?

If the triangle is not green, then the square is not blue. - The statement is TRUE

Determine whether the sentence below is an atomic statement, a molecular statement, or not a statement at all.

• Customers must wear shoes. - Not a Statement

Find |A ∩ B| when A = {1, 3, 5, 7, 9} and B {2, 4, 6, 8, 10}

- 0

Classify the sentence below as an atomic statement, a molecular statement, or not a statement at all. If the statement is molecular, identify what kind it is (conjuction, disjunction, conditional, biconditional, negation).

The Broncos will win the Super Bowl or I’ll eat my hat.

-Molecular Conjunction

GIven the function :

f : Z → Z defined by f = 3n

Which of the following is a possible range of the function?

-all multiples of three

For a function f : N → N, a __recursive __definition consists of

**together with a**

*an initial condition*

__recurrence relation.__Find f (1).

- 4

In how many different ways can the letters of the word 'OPTICAL' be arranged so that the vowels always come together?

- 720

How many 3-letter words with or without meaning, can be formed out of the letters of the word, 'LOGARITHMS', if repetition of letters is not allowed?

- 720

Consider the function f : N → N given by f (0) 0 and f (n + 1) f + 2n + 1. Find f (6).

- 36

Rule that states that every function can be described in four ways: algebraically (a formula), numerically (a table), graphically, or in words.

- Rule of four

Defined as the product of all the whole numbers from 1 to n.

-Factorial

Out of 7 consonants and 4 vowels, how many words of 3 consonants and 2 vowels can be formed?

- 210

IN combinations, the arrangement of the elements is in a specific order.

-false

The ________________________ states that if event A can occur in m ways, and event B can occur in n disjoint ways, then the event “A or B” can occur in m + n ways.

-Additive principle

Answer the following: f (1) = __4__

What is the element n in the domain such as f = 1
__2__

Find an element n of the domain such
that f = n.
**3**

Additive principle states that if given two sets A and B, we have |A × B| |A| · |B

-false

Given the diagram, answer the following questions :

How many people takes tea and wine? **32 **

How many people takes coffee but not tea and wine? **45 **

What is the difference of persons who take wine and coffee to the persons who the persons who
takes tea only? __15__

Let A, B and C represent people who like apples, bananas, and carrots respectively. The number of people in A = 10, B = 12 and C = 16. Three people are such that they enjoy apples, bananas as well as carrots. Two of them like apples and bananas. Let three people like apples and carrots. Also, four people are such that they like bananas and carrots.

How many people like apples only?
__2__

How many people like only one of the three?
__26__

It is a rule that assigns each input exactly one output

-Function

Determine the number of elements in A U B.

- 18

In my safe is a sheet of paper with two shapes drawn on it in colored crayon. One is a square, and the other is a triangle. Each shape is drawn in a single color. Suppose you believe me when I tell you that if the square is blue, then the triangle is green. What do you therefore know about the truth value of the following statement?

If the triangle is green, then the square is blue. - The statement is TRUE

A **bijection **is a function which is both an injection and surjection. In other words, if
every element of the codomain is the image of exactly one element from the domain

Consider the statement, “If you will give me a cow, then I will give you magic beans.” Determine whether the statement below is the converse, the contrapositive, or neither.

• You will give me a cow and I will not give you magic beans. - Converse

surjective and injecive are opposites of each other.

-false

The **inverse image**
of a a subset B of the codomain is the set f −1 (B) {x ∈ X : f (x) ∈ B}.

The **range**
is a subset of the codomain. It is the set of all elements which are assigned
to at least one element of the domain by the function. That is, the range is the set of all outputs.

Which of the following translates into “Jack and Jill both passed math” into symbols?

-P Λ Q

The square is not blue or the triangle is green. - The statement is FALSE

Suppose P and Q are the statements:

P: Jack passed math.

Q: Jill passed math.

Translate "¬(P ν Q) → Q" into English.

-If Jack or Jill did not pass math, then Jill passed math.

Consider the statement, “If you will give me a cow, then I will give you magic beans.” Determine whether the statement below is the converse, the contrapositive, or neither.

• If I will give you magic beans, then you will give me a cow. - Neither

Consider the statement, “If you will give me a cow, then I will give you magic beans.” Determine whether the statement below is the converse, the contrapositive, or neither.

If I will not give you magic beans, then you will not give me a cow. - Contrapositive

Arithmetic progression is the sum of the terms of the arithmetic series.

-False

Given the series : 2,5,8,11....

What is the type of progression? __Arithmetic__

What is the sum from 1st to 5th element? **40**

What is the missing term?

3,9,__,81....

- 27

Identify the propositional logic of the truth table given

-negation

The study of what makes an argument good or bad.

-Logic

match the following formulas to its corresponding sequence

**is the same truth value under any assignment of truth values to their atomic parts.**

__Logic Equivalence__**is a function from a subset of the set of integers.**

__sequence__

**29**

**Arithmetic**

**in finding the succeeding terms**

__factor__**Solution:*

*(a2+b2 )/4=(1/2)ab*

*Multiply both sides by 4 to get:*

*a 2+b2=2ab*

*Solving for 0 we get:*

*a 2-2ab+b2=0*

*And factoring the polynomial we get:*

*(a-b)2=0*

*Take the square root of both sides:*

*±(a-b)=0 a=b Therefore, a triangle with two equal sides is an ISOSCELES Triangle.*

**is a**

__Euler circuit__**which starts and stops at the same vertex.**

__Euler path__**Solution:*

*1 ? n2 - n 0 ?*

*n2 - n - 1*

*Solve the quadratic*

*n = ( - (-1) ± √ (1 - 4(1)(-1))) / 2(1)*

*n = ( 1 ± √ 5 ) / 2*

*√ 5 is an irrational number, therefore*

*(1/n) ≠ n - 1 for rational n's*

__nodes__

**, then every other vertex on the tree can be characterized by its position relative to the root.**

__root____is the simplest style of proof.__

**irect proof****Solution*

*By the sum of degrees theorem,*

*20 ∑ i=1 deg(Vi) = 2|E|*

*20(3) = 2|E|*

*|E| = 30*

*By Euler’s formula,*

*|V| + |R| = |E| + 2*

*20+ |R| = 30 + 2*

*|R| = 12*

*Hence, the number of regions is 12.*

**of the parent.**

__child__**if and only if between any pair of vertices in F there is at most**

__forest__

__one path__**graph has two distinct groups where no vertices in either group connecting to members of their own group**

__bipartite__Paths start and stop at the same vertex.

**graph has no isolated vertices**

__connected__