C959: Discrete Math I latest updated version with 100% correct answers 2026-

Form

When an argument has been translated from English using symbols

Invalid

Describes an argument when the conclusion is false in a situation with all the hypotheses are are true

Valid

Describes an argument when the conclusion is true whenever the hypotheses are all true

Conclusion

The final proposition

Hypothesis

Each of the propositions within an argument

Argument

Sequence of propositions

Two Player Game

In reasoning whether a quantified statement is true or false, it is a useful way to think of the statement in which universal and existential compete to set the statement's truth value.

Nested Quantifier

A logical expression with more than one quantifier that binds different variables in the same predicate

Predicate

A logical statement whose truth value is a function of one or more variables

Domain of a variable

The set of all possible values for the variable

universal quantifier

∀ "for all"

universally quantified statement

∀x P(x)

Counterexample

For a universally quantified statement, it is an element in the domain for which the predicate is false.

existential quantifier

∃ "there exists"

Existentially quantified statement

∃x P(x)

Quantifier

Two types are universal and existential

Quantified Statement

Logical statement including universal or existential quantifier

Logical proof

A sequence of steps, each of which consists of a proposition and a justification for an argument

Arbitrary element

Has no special properties other than those shared by all elements of the domain

Particular element

May have properties that are not shared by all the elements of the domain

Theorem

Statement that can be proven true

Proof

Series of steps, each of which follows logically from assumptions, or from previously proven statements, whose final step should result in the statement of the theorem being proven

Axiom

Statements assumed to be true

Generic object

We don't assume anything about it besides assumptions given in the statement of the theorem

Proof by exhaustion

If the domain is small, might be easiest to prove by checking each element individually

Counterexample

An assignment of values to variables that shows that a universal statement is false

Direct proof

The hypothesis p is assumed to be true and the conclusion c is proven to be a direct result of the assumption; for proving a conditional statement

Rational number

A number that can be expressed as the ratio of two integers in which the denominator is non-zero

Proof by contrapositve

Proves a conditional theorem of the form p->c by showing that the contrapositive -c->-p is true

Even integer

2k for some integer k

Odd integer

2k+1 for some integer k

Irrational number

Real number that cannot be written as a fraction

Proof by contradiction

Starts by assuming that the theorem is false and then shows that some logical inconsistency arises as a result of this assumption

Indirect proof

Another name for a proof by contradiction

Proof by cases

For a universal statement, it breaks the domain into different classes and gives a different proof for each class. All of the domain must be covered.

Parity

Whether a number is odd or even

Absolute value

Of a real number x, is defined as |x| = -x if x ≤ 0, and |x| = x if x ≥ 0.

Set

A collection of objects

Elements

Objects in a set

Roster notation

Definition of a set by listing elements enclosed in curly braces with elements separated by commas

Empty set

Set with no elements, denoted Ø

Finite set

Set with finite number of elements

Infinite set

Set with infinite number of elements

Cardinality

Number of elements in set A, denoted |A|

Set N

Set of natural numbers

Set Z

Set of all integers

Set Q

Set of rational numbers

Set R

Set of real numbers

Set builder notation

A set is defined by specifying that the set includes all elements in a larger set that also satisfy certain conditions

Universal set

Set that contains all elements mentioned in a particular context, often denoted U

Venn diagram

Used to represents sets where a rectangle is used to denote the universal set U, and oval shapes to denote sets within U

Subset

A is a _______ of B if every element in A is also an element of B, denoted A⊆B

Proper subset

A is a ________ of B if A⊆B and A≠B, denoted A⊂B

Power set

The set of all subsets, denoted P(A) for set A

Intersection

Between sets A and B, it is the set of all elements that are elements of both A and B, denoted A ∩ B

Union

The set of all elements that are elements of A or B or both, denoted A∪B

Difference

For sets A and B, the set of elements that are in A but not in B, denoted A-B

Symmetric difference

For sets A and B, the set of elements that are a member of exactly one of A and B but not both, denoted A⊕B = (A-B) U (B-A)

Complement

Of set A, the set of all elements in U that are not elements of A, denoted Ā

Ordered pair

Written (x,y)

Entry

Name for the x or y in an ordered pair

Cartesian product

For two sets A and B, the set of all ordered pairs in which the first entry is in A and the second entry is B, denoted A x B

Ordered triple

Ordered list of three items, denoted (x, y, z)

Ordered n-tuple

An order list of n items, for n ≥ 4

String

Sequence of characters

Alphebet

Set of characters used in a set of strings

Length

Number of characters in a string

Binary string

A string whose alphabet is {0,1}

Bit

A character in a binary string

n-bit string

A string of length n, another way to describe length

Empty string

String with length of 0, denoted λ

Concatenation

If a & b are two strings, when a and be are put together, denoted ab

Disjoint

When two sets A and B have an empty intersection, A ∩ B = Ø

Pairwise disjoint

For a sequence of sets, A1, A2,...,An, when every pair of distinct sets in the sequence is disjoint

Partition

Of a non-empty set A, is a collection of non-empty subsets of A such that each element of A is in exactly one of the subsets

Function

That maps elements of a set X to elements of a set Y is a subset of X x Y such that for every x∈X there is exactly one y∈Y for which (x,y)∈f

Domain (functions)

The set x of function f

Target

The set Y of function f

Arrow diagram

Way to graphically represent a function with a finite domain

Range

For a function f:X→Y, an element is in it if and only if there is an x∈X such that (x,y)∈f

Equal functions

When functions f and g have the same domain and target and f(x) = g(x) for every element x in the domain, denoted f=g

Floor function

Maps real numbers to the nearest integer in the downward direction

Ceiling function

Rounds a real number to the nearest integer in the upward direction

Injective

For a function f:X→A the range of f is equal to the target A; for every a∈A, there is an x∈X such that f(x)=a

Surjective

For a function f:X→A, x1 ≠ x2 implies that f(x1) ≠ f(x2); f maps different elements in X to different elements in A

Bijective

When a function is injective and surjective

Bijection

Name of a bijective function

Onto

Another name for surjective

One-to-one

Another name for injective

Invertable

Characteristic of a function if there exists a function g with domain Y and range X with the property f(x)=y ⇔ g(y)=x

Inverse

As long as function f:X→Y is a bijection, it is obtained by exchanging the first and second entries in each pair f, denoted f^(-1)

Composition of a function

The process of applying a function to the result of another function

Identity function

Always maps a set onto itself and maps every element onto itself

Strictly increasing

For a function f, if whenever x1

Strictly decreasing

For a function f, if whenever x1

Boolean algebra

Set of rules and operation for working with variables whose values are either 0 or 1

Digital logic

Area of computer science concerned with designing computer circuitry

Boolean variables

Variables that can have a value of 0 or 1

Boolean expression

Built by applying Boolean operation to Boolean variables or constants 1 or 0

Equivalent (Boolean expressions)

If two Boolean expressions have the same value for every possible combination of values assigned to the variables contained in the expressions