Discrete Mathematics (CS6105) PDF

Preview

Summary

xfgjfx...

Description

Discrete Math Final Quiz 1 The child of a child of a vertex is called -grandchild

It is the switching the hypothesis and conclusion of a conditional statement. -converse Try contrapositive

The number of simple digraphs with |V | = 3 is Answer: 512

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

Match the following properties of trees to its definition.

Proposition 4.2.3 Answer:

In a simple graph, the number of edges is equal to twice the sum of the degrees of the vertices. -False 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 number of edges incident to a vertex. -Degree of a vertex

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

The given graph is planar. -False

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

A connected graph with no cycles. -tree

How many spanning trees are possible in the given figure? Answer: 2

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

The minimum number of colors required in a proper vertex coloring of the graph. -Chromatic number Indicate which, if any, of the following three graphs G = (V, E, φ), |V | = 5, is not isomorphic to any of the other two. Answer: φ = (A {1,3} B {2,4} C {1,2} D {2,3} E {3,5} F {4,5} )

Discrete Math Midterm Exam 47/50 A function which renames the vertices. -isomorphism

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

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

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

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

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

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

The tree elements are called -nodes

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

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.

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

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

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

What is the matching number for the following graph? Answer: 4

is the simplest style of proof. -Direct proof 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

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.

Answer: 12

What is the minimum height height of a full binary tree? Answer: 2 wrong

Identify the propositional logic of the truth table given Answer: negation

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 not give me a cow. Answer: Neither

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

A _________ is a ___________ which starts and stops at the same vertex. Answer: Euler's circuit, Euler's path

¬P

Q is equivalent to :

Answer: P → Q

Given the diagram, answer the following questions : How many people takes tea and wine? Answer: 32 How many people takes coffee but not tea and wine? Answer: 45 What is the difference of persons who take wine and coffee to the persons who the persons who takes tea only? Answer: 15

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

Let A = {1, 2, 3, 4, 5} and B = {3, 4, 5, 6, 7} Find A ∩ B Answer: {3, 4, 5}

Let A = {1, 2, 3, 4, 5} and B = {3, 4, 5, 6, 7} Find A U B Answer: {1, 2, 3, 4, 5, 6, 7}

Let A = {1, 2, 3, 4, 5} and B = {3, 4, 5, 6, 7} Find A \ B Answer: {1, 2}

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

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

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

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

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

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

Let A = {1, 2, 3, 4, 5}, B = {3, 4, 5, 6, 7}, and C = {2, 3, 5}. Find A ∩ (B U C) Answer: {2,3,4,5}

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

Suppose P and Q are the statements: P: Jack passed math. Q: Jill passed math. Translate "¬(P ν Q) → Q" into English. Select one: -If Jack or Jill did not pass math, then Jill passed math.

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 not green, then the square is not blue. -True

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 (correct answer?)

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

Determine whether the sentence below is an atomic statement, a molecular statement, or not a statement at all. The customers wore shoes and they wore socks. -Molecular

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

Suppose P and Q are the statements: P: Jack passed math. Q: Jill passed math. Which of the following translates into “Jack and Jill both passed math” into symbols? Select one: -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? If the triangle is green, then the square is blue. -True (not necessarily true dapat to eh)

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 you will give me a cow, then I will not give you magic beans. -Converse

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

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

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. -false 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 you will not give me a cow, then I will not give you magic beans. -Converse

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

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

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

Determine whether the sentence below is an atomic statement, a molecular statement, or not a statement at all. The customers wore shoes. -Atomic

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

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

Discrete Math Prelim Quiz 2 match the following formulas to its corresponding sequence

geometric double summation

Suppose P and Q are the statements: P: Jack passed math. Q: Jill passed math. (a) Translate “Jack and Jill both passed math” into symbols. -di masagutan lol

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

What is the matching number for the following graph?

Answer: 4

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

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

Which of the following statements are equivalent to the implication, “if you win the lottery, then you will be rich,”? -It is necessary for you to win the lottery to be rich. -You will be rich if you win the lottery. -It is sufficient to win the lottery to be rich.

What is the missing term? 3,9,__,81.... Answer: 27

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

What is the line covering number of for the following graph?

Answer: 3

The sum of the geometric progression is called geometric series

-True

A graph is complete if there is a path from any vertex to any other vertex. -False

Given the series : 2,5,8,11.... What is the type of progression? (Answer: Arithmetic) What is the sum from 1st to 5th element?

¬(P

(Answer: 40)

Q) is logically equal to which of the following expressions?

Answer: ¬P

¬Q

A function which renames the vertices. -isomorphism

is the simplest style of proof -direct proof

The geometric sequences uses common ______ in finding the succeeding terms -factor

Match the truth tables to its corresponding propositional logic

Does a rational r value for r2 =6 exist? -No, a rational r does not exist. Deduction rule is an argument that is not always right. -False

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

Suppose P and Q are the statements: P: Jack passed math. Q: Jill passed math. Translate "¬(P ν Q) → Q" into English. Select one: -If Jack or Jill did not pass math, then Jill passed math.

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 not green, then the square is not blue. -True

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

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

Determine whether the sentence below is an atomic statement, a molecular statement, or not a statement at all. The customers wore shoes and they wore socks. -Molecular

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

Suppose P and Q are the statements: P: Jack passed math. Q: Jill passed math.

Which of the following translates into “Jack and Jill both passed math” into symbols? Select one: -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? If the triangle is green, then the square is blue. -True

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 you will give me a cow, then I will not give you magic beans. -Converse 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. -Contrapositive

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

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

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 you will not give me a cow, then I will not give you magic beans. -Converse

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

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

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

Determine whether the sentence below is an atomic statement, a molecular statement, or not a statement at all. The customers wore shoes. -Atomic

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

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

Let A = {1, 2, 3, 4, 5} and B = {3, 4, 5, 6, 7} Find A ∩ B Answer: {3, 4, 5}

Let A = {1, 2, 3, 4, 5} and B = {3, 4, 5, 6, 7} Find A U B Answer: {1, 2, 3, 4, 5, 6, 7}

Let A = {1, 2, 3, 4, 5} and B = {3, 4, 5, 6, 7} Find A \ B Answer: {1, 2}

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

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

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

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

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

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

...