Discrete Mathematics

Discrete Mathematics

Module Description

The course covers the basic concepts and techniques of discrete mathematics.  The course includes the discussion of mathematical logic, propositions, quantifiers, predicates, proof techniques, mathematical induction, fundamentals of set theory, sets, power sets, algebra of sets, relations, functions, count ability and finiteness, graphs and trees.

The square and the triangle are both green	The Statement is FALSE
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	{1, 2}
The square and the triangle are both blue	The Statement is FALSE
If the triangle is not green, then the square is not blue.	The Statement is TRUE
The Broncos will win the Super Bowl or I’ll eat my hat.	Molecular - Conjunction
Every natural number greater than 1 is either prime or composite.	Molecular - Conditional
The customers wore shoes and they wore socks	Molecular
Find |A ∩ B| when A = {1, 3, 5, 7, 9} and B {2, 4, 6, 8, 10}	0
Find the cardinality of S = {1, {2,3,4},0}  | S | =	3
The customers wore shoes	Atomic
Everybody needs somebody sometime	Atomic – N/A
The cardinality of {3, 5, 7, 9, 5} is 5.	FALSE
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}
Customers must wear shoes	Not a Statement
Let A = {3, 4, 5}. Find the cardinality of P(A)	8
Find the cardinality of R = {20,21,...,39, 40}  | R |	21
Let A = {1, 2, 3, 4, 5} and B = {3, 4, 5, 6, 7}  Find A ∩ B	{3, 4, 5}
The sum of the first 100 odd positive integers	Atomic – N/A
Find | R | when R = {2, 4, 6,..., 180}	90
It is a rule that assigns each input exactly one output	function
Defined as the product of all the whole numbers from 1 to n	factorials
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
Which of the following is a  possible range of the function	all multiples of three
Determine the number of elements in A U B.	18
Out of 7 consonants and 4 vowels, how many words of 3 consonants and 2 vowels can be formed?	210
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
Find f (1).	4
Additive principle states that if given two sets A and B, we have |A × B| |A| · |B|	False
IN combinations, the arrangement of the elements is in a specific order.	False
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
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
How many people like apples only?	2
How many people like only one of the three?	26
For a function f : N → N, a ______ definition consists of an ________ together with a _________	Recursive - initial condition  - recurrence relation
Consider the function f : N → N given by f (0) 0 and f (n + 1) f  + 2n + 1. Find f (6).	36
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
In how many different ways can the letters of the word 'OPTICAL' be arranged so that the vowels always come together?	720
If I will not give you magic beans, then you will not give me a cow	Contrapositive
If you will give me a cow, then I will not give you magic beans	Neither
Out of 7 consonants and 4 vowels, how many words of 3 consonants and 2 vowels can be formed?	210
Find |A ∩ B| when A = {1, 3, 5, 7, 9} and B {2, 4, 6, 8, 10}	0
surjective and injecive are opposites  of each other	False
Find | R | when R = {2, 4, 6,..., 180}	90
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	bijection
If the triangle is green, then the square is blue	The Statement is TRUE
Additive principle states that if given two sets A and B, we have |A × B| |A| · |B|.	False
The sum of the first 100 odd positive integers	False
The square is not blue or the triangle is green	The Statement is TRUE
Determine the number of elements in A U B.	18
The ____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	range
of a a subset B of the codomain is the set f −1 (B) {x ∈ X : f (x) ∈ B}.	inverse image
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
Translate "¬(P ν Q) → Q" into English	If Jack or Jill did not pass math, then Jill passed math.
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
You will give me a cow and I will not give you magic beans	Neither
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
If I will give you magic beans, then you will give me a cow	Converse
If you will not give me a cow, then I will not give you magic beans	Neither
It is a rule that assigns each input exactly one output	function
The customers wore shoes and they wore socks	Molecular
Which of the following translates into “Jack and Jill both passed math” into symbols?	P Λ Q
Arithmetic progression is the sum of the terms of the arithmetic series	False
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
is the same truth value under any assignment of truth values to their atomic parts.	Logic equivalence
Match the truth tables to its corresponding propositional logic
is a function from a subset of the set of integers.	sequence
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 ___ in finding the succeeding terms.	factor
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
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 ____ is a ___which starts and stops at the same vertex.	Euler circuit - Euler path
For all n in rational, 1/n ≠ n - 1	false
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	-31
What is the matching number for the following graph?	4
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
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	No, a rational r does not exist.
is the simplest style of proof.	direct 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
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.
The sum of the geometric progression is called geometric series	true
What is the 20th term?	29
What type of progression this suggest?	Arithmetic
Arithmetic progression is the sum of the terms of the arithmetic series.	false
Two edges are adjacent if they share a vertex.	true
Every connected graph has a spanning tree.	true
An undirected graph G which is connected and acyclic is called ____________.	tree
The number of edges incident to a vertex	Degree of a vertex
A graph T is a tree if and only if between every pair of distinct vertices of T there is a unique path.	true
How many possible output will be produced in a proposition of three statements?	8
A statement which is true on the basis of its logical form alone.	Tautology
A spanning tree that has the smallest possible combined weight.	minimum spanning tree
A tree is the same as a forest.	False
A ___ 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 __	Tree - leaves
¬P ∨ Q is equivalent to :	P → Q
Deduction rule is an argument that is not always right.	False
If n is a rational number, 1/n does not equal n-1	true
Which of the following statements is NOT TRUE?	Any tree with at least two vertices has at least two vertices of degree two.
What is the line covering number of for the following graph?	3
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
What is the minimum height height of a full binary tree?	3
An argument is said to be valid if the conclusion must be true whenever the premises are all true.	true
The study of what makes an argument good or bad.	logic
It is an algorithm for traversing or searching tree or graph data structures.	breadth first search
For all n in rational, 1/n ≠ n - 1	false
How many simple non-isomorphic graphs are possible with 3 vertices?	4
A graph is complete if there is a path from any vertex to any other vertex.	false
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 graph
An argument form which is always valid.	deduction rule
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
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.	Converse
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 ___ of the parent	child
How many spanning trees are possible in the given figure?	4
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 ___if and only if between any pair of vertices in F there is at most ___	forest - 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	512
The minimum number of colors required in a proper vertex coloring of the graph.	Chromatic Number
Corollary 4.2.2	A graph F is a forest if and only if between any pair of vertices in F there is at most one path
Proposition 4.2.3	Any tree with at least two vertices has at least two vertices of degree one.
Proposition 4.2.4	4 Let T be a tree with v vertices and e edges. Then e v - 1.
Proposition 4.2.1	A graph T is a tree if and only if between every pair of distinct vertices of T there is a unique path.
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 ___ graph has two distinct groups where no vertices in either group connecting to members of their own group	bipartite
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
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
A ______ graph has no isolated vertices	connected
A sequence of vertices such that every vertex in the sequence is adjacent to the vertices before and after it in the sequence	Walk
The square and the triangle are both green.	The statement is FALSE
The square and the triangle are both blue.	The statement is FALSE
Defined as the product of all the whole numbers from 1 to n.	factorials
The square is not blue or the triangle is green.	The statement is FALSE
A sequence of vertices such that every vertex in the sequence is adjacent to the vertices before and after it in the sequence	walk
It is a connected graph containing no cycles.	tree
If the triangle is green, then the square is blue.	The statement is TRUE
These are lines or curves that connect vertices.	edges