UGRD-CS6105 Discrete Mathematics

UGRD-CS6105 Discrete Mathematics
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 an initial condition together with a 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


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


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 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

 


The sum of the geometric progression is called geometric series
-True


¬(P ∨ Q) is logically equal to which of the following expressions?
- ¬P ∧ ¬Q. 


A sequence that involves a common difference in identifying the succeeding terms.
-Arithmetic Progression


De Morgan's law is used in finding the equivalence of a logic expression using other logical functions.
-True


A set of statements, one of which is called the conclusion and the rest of which are called premises.
-argument


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


Match the truth tables to its corresponding propositional logic
 

sequence is a function from a subset of the set of integers.


Assume the sequence: 1,3,5,7,9, …. 
What is the 20th term? 29 
What type of progression this suggest? Arithmetic


Deduction rule is an argument that is not always right.
-false



The geometric sequences uses common factor in finding the succeeding terms


What is the 4th and 8th element of a = n^(2) ?
- 16,64


How many possible output will be produced in a proposition of three statements?
- 8


¬P ∨ Q is equivalent to :
- P → Q


If the right angled triangle t, with sides of length a and b and hypotenuse of length c, has area equal to c 2/4, what kind of triangle is this?
-isosceles triangle

*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.


Find the contrapositive of the given statement. 
If you travel to London by train, then the journey takes at least two hours
-If your journey by train takes less than two hours, then you don’t travel to London.


Which of the following the logic representation of proof by contrapositive?
- P → Q = ¬Q → ¬P


A Euler circuit is a Euler path which starts and stops at the same vertex.


For all n in rational, 1/n ≠ n - 1
- False

*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


The tree elements are called nodes


A sequence of vertices such that consecutive vertices (in the sequence) are adjacent (in the graph). A walk in which no edge is repeated is called a trail, and a trail in which no vertex is repeated (except possibly the first and last) is called a path
-Walk


A function which renames the vertices.
-isomorphism


Solve for the value of n in : 
−4= n+7 over 6 
Answer: -31


What is the matching number for the following graph?
 


As soon as one vertex of a tree is designated as the root , then every other vertex on the tree can be characterized by its position relative to the root.


An undirected graph G which is connected and acyclic is called ____________.
-tree


 What is the minimum height height of a full binary tree?
- 3


Does a rational r value for r 2=6 exist?
- No, a rational r does not exist


direct proof is the simplest style of proof. 


Proofs that is used when statements cannot be rephrased as implications.
- Proof by Contradiction


If n is a rational number, 1/n does not equal n-1.
- True


Let ‘G’ be a connected planar graph with 20 vertices and the degree of each vertex is 3. Find the number of regions in the graph.
- 12

*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. 


It is an algorithm for traversing or searching tree or graph data structures.
-breadth first search


Which of the following statements is NOT TRUE?
-Any tree with at least two vertices has at least two vertices of degree two.


A Bipartite graph is a graph for which it is possible to divide the vertices into two disjoint sets such that there are no edges between any two vertices in the same set.
-True


The given graph is planar.
 
-TRUE


It is the switching the hypothesis and conclusion of a conditional statement.
-Concerse


The number of edges incident to a vertex.
-Degree of a vertex


Two graphs that are the same are said to be _______________
- isomorphic


A connected graph with no cycles.
- : tree


If two vertices are adjacent, then we say one of them is the parent of the other, which is called the child of the parent.


How many spanning trees are possible in the given figure?


Indicate which, if any, of the following three graphs G = (V, E, φ), |V | = 5, is not isomorphic to any of the other two.
- φ = (A {1,3} B {2,4} C {1,2} D {2,3} E {3,5} F {4,5} )


A graph F is a forest if and only if between any pair of vertices in F there is at most one path 


Indicate which, if any, of the following graphs G = (V, E, φ), |V | = 5, is not connected.
-  φ = ( a {1,2} b {2,3} c {1,2} d {1,3} e {2,3} f {4,5} )


The number of simple digraphs with |V | = 3 is
- 152


The minimum number of colors required in a proper vertex coloring of the graph.
 -Chromatic Number


Match the following properties of trees to its definition.
 
 

The child of a child of a vertex is called
- : Grandchild


In a simple graph, the number of edges is equal to twice the sum of the degrees of the vertices.
-False


 A bipartite graph has two distinct groups where no vertices in either group connecting to members of their own group


A simple graph has no loops nor multiple edges.
-True


 Euler paths must touch all edges
-True


These are lines or curves that connect vertices.
-Edges


Which of the following is false?
- A graph with one odd vertex will have an Euler Path but not an Euler Circuit.


Does this graph have an Euler Path, Euler Circuit, both, or neither? 
 

-Both



Paths start and stop at the same vertex.
-False


A sequence of vertices such that consecutive vertices (in the sequence) are adjacent (in the graph). A walk in which no edge is repeated is called a trail, and a trail in which no vertex is repeated (except possibly the first and last) is called a path.
- Walk


Circuits start and stop at _______________
-same vertex


All graphs have Euler's Path
-False


When a connected graph can be drawn without any edges crossing, it is called ________________ .
-Planar graph


Tracing all edges on a figure without picking up your pencil or repeating and starting and stopping at different spots
-Euler Circuit


How many edges would a complete graph have if it had 6 vertices?
-15


A path which visits every vertex exactly once
-Hamilton Path


connected graph has no isolated vertices


A sequence of vertices such that every vertex in the sequence is adjacent to the vertices before and after it in the sequence
-Walk