DISCRETE MATHEMATICS

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

The customers wore shoes. 

-Atomic

The square and the triangle are both green. 

-False

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.

 You will give me a cow and I will not give you magic beans.

-Contrapositive

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

-Molecular – Conditional

Everybody needs somebody sometime. 

-Atomic -(dis)Conjunction - conditional

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

Customers must wear shoes.

-Not a statement
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

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?
- P Λ Q

The customers wore shoes and they wore socks

-Molecular

The square and the triangle are both blue.

-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

The square is not blue or the triangle is green

-False

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

-Molecular – ConDitional

If the triangle is not green, then the square is not blue.

-True

For a function f:N→N,f:N→N, a recursive definition consists of an initial

condition together with a recurrence relation.

The sum of the first 100 odd positive integers. 

-Atomic -(Dis)conjunction - CONDITIONAL
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.

An argument is said to be valid if the conclusion must be true whenever the premises are all
true.
-True

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

match the following formulas to its corresponding sequence

-Geometric Series

-,Arithmetric

match the following formulas to its corresponding sequence

-Geometric

-Double summation

Assume the sequence: 1,3,5,7,9, ….

-29

-Arithmetric

The study of what makes an argument good or bad.

-Logic 

 How many people like apples only? 2

 How many people like only one of the three? 26

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

A function which renames the vertices.

- isomorphism

In how many different ways can the letters of the word 'OPTICAL' be arranged so that the
vowels always come together?
-720
Determine whether the sentence below is an atomic statement, a molecular statement, or
not a statement at all.
-Not a statement

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.

    f  (1) = 4

What is the element n in the domain such as f(n) = 1 = 2

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

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

-Converse

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 
  Find f (1).

-1

If the triangle is green, then the square is blue.

-True

Find A U B
-{3, 4, 5}

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

-False

The tree elements are called

-NODES

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

-

Find f (1).
-

Find A ∩ B

-{3,4,5}

Find A \ B

-{1, 2}

-{1, 2, 6, 7}

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

-37

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

-False

The number of edges incident to a vertex.

-Degree of a vertex
An undirected graph G which is connected and acyclic is called ____________.
-Tree
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 graph F is a FOREST if and only if between any pair of vertices in F there is at most ONE
PATH

A graph T is a tree if and only if between every pair of distinct vertices of T there is a unique
path.

A statement which is true on the basis of its logical form alone.

- Tautology

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

-Converse

-Neither

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

-Neither

surjective and injecive are opposites  of each other.

-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.
-Planar graph

What is the missing term?

-27

The sum of the geometric progression is called geometric series

-True

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

-Arithmetic

-40

A graph in which every pair of vertices is adjacent.

- Complete graph

The geometric sequences uses common  in finding the succeeding terms.

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

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

-Arithmetic Progression

Two edges are adjacent if they share a vertex.

-True

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

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

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

-15

Match the following properties of trees to its definition.

Propositi Answer 1
on 4.2.3 Any tree w ith at least tw o vertices has at least tw o vertices of degree one.
-
Propositi Answer 2
on 4.2.4 4 Let T be a tree w ith v vertices and e edges. Then e v 1.
Propositi Answer 3
on 4.2.1 A graph T is a tree if and only if betw een every pair of distinct vertices of T there is a unique path.
Corollary Answer 4
4.2.2 A graph F is a forest if and only if betw een any pair of vertices in F there is at most one path

Previous page

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

It is a connected graph containing no cycles.

-Tree

Two graphs that are the same are said to be _______________

- isomorphic

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

It is an algorithm for traversing or searching tree or graph data structures.

- depth first search.

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

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

A connected graph with no cycles.

-Tree

A path which visits every vertex exactly once

- Eulerian trail

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.

The child of a child of a vertex is called

- grandchild

What is the matching number for the following graph?

-4

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

How many spanning trees are possible in the given figure?

-2

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

-

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.

- Bipartite

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.

GIven the function :

          f : Z → Z defined by f(n) =  3n
Which of the following is a  possible range of the function?
-

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

-¬P ∨ ¬Q

Identify the propositional logic of the truth table given

-conjunction

-disjunction

¬P ∨ Q is equivalent to :
- P → Q
IN combinations, the arrangement of the elements is in a specific order.
-False

Match the truth tables to its corresponding propositional logic

PvQ

-Disjunction

P^Q

-Conjunction

PQ

-Implication

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

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

-False

A TREE connected graph with no cycles. (If we remove the requirement that the graph is
connected, the graph is called a forest.) The vertices in a tree with degree 1 are called
LEAVES

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

Deduction rule is an argument that is not always right.

-False

3,9,__,81....

-27

graph has no isolated vertices.

A EULER CIRCUIT is a EULER PATH which starts and stops at the same vertex.

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

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 sequence of vertices such that every vertex in the sequence is adjacent to the vertices
before and after it in the sequence

-Walk

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

- False

All graphs have Euler's Path

-False

Euler paths must touch all edges.

- True

Paths start and stop at the same vertex.

-False

Circuits start and stop at _______________

-  same vertex

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

-True

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

Which of the following the logic representation of proof by contrapositive?

- P → Q = ¬Q → ¬P

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

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

Direct Proof is the simplest style of proof.

Does a rational r value for  r2 =6 exist?

- No, a rational r does not exist.

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

−4= n+7 over 6

- -31 = n
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.

A path which visits every vertex exactly once

- Eulerian trail
A graph is an ordered pair G (V, E) consisting of a nonempty set V (called the vertices) and a
set E (called the edges) of two-element subsets of V.
- True

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

Which of the following is false?

- A graph with one odd vertex will have an Euler Path but not an Euler Circuit.

The given graph is planar.

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

Which of the following statements is NOT TRUE?

- Any tree with at least two vertices has at least two vertices of degree two.