Discrete Math - Definitions

Question 1

contrapositive

Answer 1

of a conditional proposition p -> q is (~q) -> (~p)

Every polynomial that is not continuous has at most one zero.

Question 2

converse

Answer 2

Switching the hypothesis and conclusion of a conditional statement. If Q then P

Every continuous polynomial as at least two zeroes.

Question 3

inverse

Answer 3

p → q is the proposition ∼ p →∼ q

Question 4

negation

Answer 4

There exists some polynomial with at least two zeroes that is not continuous.

Question 5

constructive proof

Answer 5

An existential proof is constructive if it explicitly produces the desired ob- ject (or gives an algorithm to produce it).

Question 6

floor

Answer 6

The floor of real number x is the largest integer n with n ≤ x.

Question 7

odd

Answer 7

A number x is odd if there is an integer n with x=2n+1.

Question 8

irreducible

Answer 8

A number is irreducible if it cannot be factored into two nonunits.

Question 9

cardinal number

Answer 9

A cardinal number measures the size of some set.

Question 10

ordinal number

Answer 10

An ordinal number measures sequential position, as compared to ‘first’.

Question 11

binary relation

Answer 11

A binary relation on A,B is a subset of A×B.

Question 12

union

Answer 12

The union of two sets is the set containing all the elements in either or both sets.

Question 13

injective

Answer 13

A function is injective if every pair of distinct elements in the domain get mapped to distinct elements of the codomain.

Question 14

Modus Tollens

Answer 14

A rule of deduction that concludes ∼ p from hypotheses p → q and ∼ q

Question 15

Syntax

Answer 15

A set of artificial rules about arrangements of otherwise meaningless symbols

Question 16

Semantics

Answer 16

The interpretation of symbols to derive meaning about other things

Question 17

tautology

Answer 17

A compound proposition that is true for every possible combination of truth values of its components

Question 18

symmetric difference

Answer 18

the set of elements which are in either of the sets and not in their intersection

A∆B for sets A, B is (A−B)∪(B−A) or (A∪B)−(A∩B)

Question 19

power set

Answer 19

set S is the set consisting of all the subsets of S (including the empty subset)

Question 20

union

Answer 20

A ∪ B for sets A, B is the set {x : x ∈ A or x ∈ B}

Question 21

valid

Answer 21

An argument/proof is valid if the conclusion must be true if all the premises are true

Question 22

vacuous proof

Answer 22

It proves the implication p->q by proving that ~p holds

Question 23

proof by contradiction

Answer 23

Takes as additional hypothesis the negation of the desired conclusion, and derives a contradiction

Question 24

proposition

Answer 24

A statement that must be true or false but not both or neither

Question 25

predicate

Answer 25

A collection of propositions indexed by one or more variables. A predicate is not a proposition, because it may be trie for certain values of its variable(s) and false for others

Question 26

GCD

Answer 26

Greatest Common Divisor - of integers a,b, not both zero, is the largest integer that divides each of them

Question 27

Union

Answer 27

With regards to two sets A,B it is the set that consists of those elements in A,B, or both.

Question 28

Maximal

Answer 28

A poset element “a” is if only there isn’t some different poset element “b” with a

Question 29

codomain

Answer 29

It is the set of a function in which it takes its values. Alternatively, it is the second set of the direct product, from which the function relation is drawn

Question 30

bijection

Answer 30

Only if a function is both one-to-one and onto.

Question 31

counterexample

Answer 31

An example which disproves a proposition

Question 32

subset

Answer 32

a set of which all the elements are contained in another set.

Question 33

power set

Answer 33

The set of all the subsets of a set

Question 34

Equivalence relation

Answer 34

the relation that holds between two elements if and only if they are members of the same cell within a set that has been partitioned into cells such that every element of the set is a member of one and only one cell of the partition

Question 35

partial order

Answer 35

a set if it has: 1. Reflexivity 2. Antisymmetry 3. Transitivity: and implies

Question 36

floor

Answer 36

the largest integer not greater than x

Question 37

ceiling

Answer 37

the smallest integer not less than x

Question 38

least upper bound

Answer 38

Let S be a nonempty set of real numbers that has an upper bound. Then a number c is called the least upper bound (or the supremum, denoted supS) for S iff it satisfies the following properties:

1. c>=x for all x in S.
2. For all real numbers k, if k is an upper bound for S, then k>=c.

Question 39

event

Answer 39

any subset of a sample space

Question 40

graph

Answer 40

a diagram showing the relation between variable quantities, typically of two variables, each measured along one of a pair of axes at right angles.

Question 41

tree

Answer 41

an undirected graph if each pair of distinct vertices has exactly one path between them

Question 42

modus ponens

Answer 42

If each of F and F=>G is either an axiom or a theorem formally deduced from axioms by application of inference rules, then G is also a formal theorem

Question 43

absolute complement

Answer 43

When all sets under consideration are considered to be subsets of a given set U, the absolute complement of A is the set of all elements in U but not in A

Ac ={x∈U|x̸∈A}.

Question 44

Total Order

Answer 44

a set plus a relation on the set (called a total order) that satisfies the conditions for a partial order plus an additional condition known as the comparability condition

If every pair of elements of A are comparable

Question 45

function

Answer 45

a relation between a set of inputs and a set of permissible outputs with the property that each input is related to exactly one output.

Question 46

pigeonhole principle

Answer 46

if n pigeons fly into k holes with n > k then some of the pigeonholes contain at least two pigeons

Question 47

Eulerian path

Answer 47

A path that contains all edges of a graph G

starts and ends at different vertices

Question 48

Euler circuit

Answer 48

A path that is also a circuit which contains all edges of a graph G

starts and ends at the same vertex

Question 49

Hamiltonian path

Answer 49

if it visits every vertex of the graph exactly once

Question 50

Hamiltonian circuit

Answer 50

A circuit that visits every vertex exactly once except for the last vertex which duplicates the first one

Question 51

countable

Answer 51

(of a set) having a finite number of elements.

(of a set) having elements that form a one-to-one correspondence with the natural numbers; denumerable; enumerable.