Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Semester 1 2024 > MATH255 - Mid Term Exam > Flashcards

MATH255 - Mid Term Exam Flashcards

1
Q

What is a statement

A

An expression that is either true or false, without ambiguity.Example: “I am a man”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is a True Statement

A

Definition: A logically valid statement that is true.Example: “3 + 4 = 7”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is a Not Statement

A

Definition: A statement negated using the “~” symbol.Example: “~(3 + 4 = 7)”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is Ambiguity

A

Definition: Lack of clarity or uncertainty in a statement.Example: “x > 2” (ambiguous because it depends on the value of x)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is There exists

A

Definition: Indicates the existence of at least one element satisfying a condition.Example: “There exists x such that x < 2”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is a False Statement

A

Definition: A logically invalid statement that is false.Example: “If x^2 = 9, then x = 1 or x = -1”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is a Conjunction

A

Definition: A logical operation that combines two statements into a single statement, true only if both original statements are true.Example: “It is raining outside” ^ “I am wearing a raincoat”p ^ q “and”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is a Disjunction

A

Definition: A logical operation that combines two statements into a single statement, true if at least one of the original statements is true.Example: “I take the bus to school” v “I take the train to school”p v q “or”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is a Conditional

A

Definition: A statement that implies that if one condition is met, another condition must also be met.Example: “If I work hard, then I do well.”p > q “implies”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is a Tautology

A

Definition: A compound statement that is always true, regardless of the truth values of its components.Example: “p v ~p”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is a Fallacy

A

Definition: A compound statement that is always false, regardless of the truth values of its components.Example: “p ^ ~p”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is a Biconditional

A

Definition: A statement that implies two conditions are equivalent.Example: “x^3 = -8” <-> “x = -2”p <-> q “p implies q, but also q implies p”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is Equivalence Laws

A

Definition: A set of logical laws that describe how logical operators interact with each other.Example: Commutative, Associative, Distributive, etc.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is a Contingency

A

Definition: A statement that is sometimes true and sometimes false, neither a tautology nor a fallacy.Example: “p ^ q”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is Equivalence

A

Definition: Two statements are logically equivalent if they have identical truth table values.Example: “p ≡ ~(~p)”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is Substitution Rule

A

Definition: If in a tautology all instances of a variable are replaced by the same statement, it remains a tautology.Example: p^~p turns into q^~q

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What is Distributive Laws

A

Definition: Laws stating how one operation distributes over another.Example: p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What is Associative Laws

A

Definition: Laws stating that the grouping of operands does not change the result.Example: (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What is Commutative Laws

A

Definition: Laws stating that the order of operands does not change the result.Example: p ∨ q ≡ q ∨ p

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What is Double Negation Law

A

Definition: The negation of a negated statement.Example: ∼∼ p ≡ p

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What is De Morgan’s Laws

A

Definition: Laws describing how negation distributes over logical operators.Example: ∼(p ∨ q) ≡ ∼p ∧ ∼q

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What is Implication Laws

A

Definition: Laws relating to conditional statements.Example: p ↔ q ≡ (p → q) ∧ (q → p)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What is Main Connective

A

Definition: The primary logical operator in a compound statement that binds it together.Example: In (p ∨ q) → (r ∧ s), “→” is the main connective.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is Universal Quantifier

A

Definition: Symbolized as ∀, it means “For all.” Used in predicate logic to denote that a statement applies to all elements in a given domain.Example: ∀x ∈ D, p(x) means “For all x in the domain D, p(x) is true.”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

What is Existential Quantifier

A

Definition: Symbolized as ∃, it means “There exists.” Used in predicate logic to indicate that there is at least one element in a given domain for which a statement is true.Example: ∃x ∈ D, p(x) means “There exists an x in the domain D for which p(x) is true.”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

What is Predicate

A

Definition: A variable statement that evaluates to true or false when specific values are substituted for its variables.Example: p(x): “x is an integer less than 5”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

What is Universal Quantifier Example

A

Definition: An example illustrating the use of the universal quantifier (∀) in a statement.Example: ∀x ∈ D, p(x) means “For all x in the domain D, p(x) is true.”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

What is Domain

A

Definition: The set of all possible values that can be substituted into a predicate.Example: Domain of p is Z (the set of all whole numbers).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

What is Truth Set

A

Definition: A subset of the domain that contains the elements for which the predicate is true.Example: Truth set of p(x) contains {-2, -1, 0, 1, 2, 3, 4}.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

What is Existential Quantifier Example

A

Definition: An example demonstrating the use of the existential quantifier (∃) in a statement.Example: ∃x ∈ D, p(x) means “There exists an x in the domain D for which p(x) is true.”

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

What is Negation of Existential Statement

A

Definition: The process of negating an existential statement to make it a universal statement.Example: ~∃x ∈ Z, x is even becomes ∀x ∈ Z, x is not even.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

What is Negation of Universal Statement

A

Definition: The process of negating a universal statement to make it an existential statement.Example: ~∀x ∈ R, x > 0 becomes ∃x ∈ R, x ≤ 0.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

What is Direct Proof

A

Definition: A method of proof that starts with given assumptions and progresses in a forward manner to reach a conclusion.Example: Proving that if 3x - 9 = 15, then x = 8.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

What is Modus Ponens

A

Definition: A valid form of argument where if you have a conditional statement “If p, then q” and you know p is true, you can conclude that q is true.Example: If p, then q; p; ∴ q.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

What is Proof by Contradiction

A

Definition: A proof technique that assumes the opposite of what needs to be proved, and then shows that this assumption leads to a contradiction, thus establishing the original statement’s truth.Example: Proving that for all n ∈ N, if n^2 is even, then n is even, by contradiction.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

What is Modus Ponens Example

A

Definition: An example illustrating the use of Modus Ponens in a logical argument.Example: If it’s raining (p), then I will bring an umbrella (q); It’s raining (p); ∴ I will bring an umbrella (q).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

What is Law of Syllogism

A

Definition: A valid form of argument where if you have two conditional statements “If p, then q” and “If q, then r,” you can conclude “If p, then r.”Example: If p, then q; If q, then r; ∴ If p, then r.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

Law of Syllogism Example

A

Definition: An example illustrating the use of the Law of Syllogism in a logical argument.Example: If I study (p), I will pass the exam (q); If I pass the exam (q), I will graduate (r); ∴ If I study (p), I will graduate (r).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

What is Law of Contrapositive

A

Definition: A valid form of argument that states if you have a conditional statement “If p, then q,” the contrapositive statement “If ~q, then ~p” is also true.Example: If p, then q; ∴ If ~q, then ~p.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
40
Q

What is Law of Contrapositive Example

A

Definition: An example demonstrating the use of the Law of Contrapositive in a logical argument.Example: If it’s a square (p), then it has four sides (q); ∴ If it doesn’t have four sides (~q), then it’s not a square (~p).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
41
Q

What is Negation mean

A

~

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
42
Q

What is Conjunction mean

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
43
Q

What is Disjunction mean

A

v

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
44
Q

What is Conditional mean

A

->

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
45
Q

What is Biconditional mean

A

<->

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
46
Q

What is ~

A

Negation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
47
Q

What is ^

A

Conjunction

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
48
Q

What is v

A

DIsjunction

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
49
Q

What is ->

A

Conditional

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
50
Q

What is <->

A

Biconditional

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
51
Q

What is the truth table for Negation

A

P ~PT FF T

52
Q

What is Proof by Contradiction

A

It is taking the statement and proving it is true/false by attempting to make it the opposite (false/true) and depends if it is possible or not

53
Q

What is the truth table for Disjunction

A

p q pvqT T FT F TF T TF F F

54
Q

What is the truth table for Conjunction

A

p q p^qT T TT F FF T FF F F

55
Q

What is the rule for remembering Bi-Conditional truth table values

A

TT and FF = True but TF and FT are False

56
Q

What is the truth table for Conditional

A

p q p>qT T TT F FF T TF F T

57
Q

What is the rule for remembering Conditional truth table values

A

p implies q is true in all cases except for true implies false (TF = False)

58
Q

What is ∀

A

Universal Quantifier - “For All”

59
Q

What is the truth table for Bi-Conditional

A

p q p>qT T TT F FF T FF F T

60
Q

What is ∃

A

There Exists/Is

61
Q

What is ∈

A

Set of / in a set of

62
Q

What is Z

A

All/every WHOLE number

63
Q

What is /∈

A

Element is not in a set of

64
Q

What is R

A

Every real number/every imaginable number

65
Q

What is ∴

A

Therefore

66
Q

What is Z++

A

Every whole positive number

67
Q

What is N

A

Natural number - Positive whole number

68
Q

What is Ø

A

Empty set

69
Q

What is A ⊆ B

A

A is a subset of B

70
Q

What is ≠

A

Not equal to

71
Q

What is ≤

A

Less than or equal to

72
Q

What is A∪B

A

A UNION B

73
Q

What is A∩B

A

A INTERSECTION B

74
Q

What is Ā or A’

A

Complement of A

75
Q

What is |S|

A

Cardinality |S| = n and say S has cardinality n (number of elements is n) Note: |∅| = 0

76
Q

What is Z \ A

A

The \ means without so here it is Z without A, aka the Difference

77
Q

Does Order in Sets matter?

A

In set theory, order is not important. For example, {1, 3} is the same as {3, 1}. Sets are unordered collections of elements.

78
Q

What is with Repeats in Sets

A

Repetition of elements in a set is not relevant. For example, {1, 3} is the same as {3, 3, 1, 3, 1, 1, 3}. Sets do not count repetitions; they only consider distinct elements.

79
Q

What is Finite Set

A

A set that contains a finite (limited) number of elements.

80
Q

What is Infinite Set

A

A set that contains an infinite (unlimited) number of elements.

81
Q

What is Natural Numbers (N)

A

The set of natural numbers consists of all positive whole numbers, including zero (0, 1, 2, 3, …).

82
Q

What is Universe (U)

A

In set theory, the universe (U) is a concept used to define the context or scope for sets. It represents the set of all elements relevant to a particular problem.

83
Q

What is Integers (Z)

A

The set of integers includes all whole numbers, both positive and negative, as well as zero (-3, -2, -1, 0, 1, 2, 3, …).

84
Q

What is Rational Numbers (Q)

A

The set of rational numbers consists of all numbers that can be expressed as the quotient or ratio of two integers. For example, fractions like 1/2 or -3/4 are rational numbers.

85
Q

What is Q

A

Rational Numbers

86
Q

What is Set Notation

A

The use of curly braces, such as { … }, is used to denote sets. For example, {1, 2, 3} represents a set with the elements 1, 2, and 3.

87
Q

What is Empty Set (∅)

A

The empty set is a set with no elements. It is denoted as ∅ or {} and is used to represent a set with no satisfying elements.

88
Q

What is Subset (⊆)

A

Set A is a subset of set B (A ⊆ B) if every element of A is also in B.

89
Q

What is Cardinality of a Set

A

The cardinality of a set is the number of elements it contains. It is denoted as |S|.

90
Q

What is Superset

A

If A is a subset of B, then B is a superset of A.

91
Q

What is Identity Element

A

An identity element is an element that, when combined with another element using a specific operation, leaves the other element unchanged. For example, 0 is the additive identity, and 1 is the multiplicative identity.e * x = x

92
Q

What is Inverse Element

A

An element’s inverse is the value that, when combined with the original element using a specific operation, results in the identity element.x * y = e

93
Q

What is Commutative

A

An operation is commutative if the order of the operands does not affect the result. For example, addition and multiplication are commutative operations.

94
Q

What is Associative

A

An operation is associative if the grouping of operands does not affect the result. For example, addition and multiplication are associative operations.

95
Q

What is Well-Ordered Set

A

A set is well-ordered if every nonempty subset of the set has at least one smallest element.

96
Q

What is Distributive

A

An operation is distributive if it distributes over another operation. For example, multiplication is distributive over addition.

97
Q

What is Intersection (∩)

A

The intersection of sets A and B (A ∩ B) is the set containing all elements that are in both A and B.

98
Q

What is Union (∪)

A

The union of sets A and B (A ∪ B) is the set containing all elements that are in either A or B.

99
Q

What is Set Difference (B - A or B\A)

A

The set difference B - A (or B\A) contains all elements that are in B but not in A.

100
Q

What is Complement (Ā or A’)

A

The complement of set A (Ā or A’) contains all elements that are not in A with respect to the universe U.

101
Q

What is the difference between a ( and [ in sets

A

‘(‘ means the -2 is not included/counted‘]’ means the 5 is included/counted

102
Q

What does (2, 5] mean

A

All the numbers between 2 and 5 but not counting 2

103
Q

{1} ∈ {x ∈ N : x^2 = 1}is this true or false

A

False as the Universe is Natural numbers and given is a set not N

104
Q

What is Cardinality of an empty set

A

0

105
Q

{0,2} ⊆ {1,2,3}True or false

A

False as 0 is not in set 2

106
Q

{1,2} ⊆ {1,2,3}True/False?

A

True as all of A is in B

107
Q

What is a subset

A

A subset is a set A derived from set B such that every element of set A is in set B

108
Q

What is a graph in graph theory?

A

A graph consists of a pair of finite sets: a nonempty set of vertices (V) and a set of edges (E), where each edge is associated with a subset of V containing 1 or 2 vertices.

109
Q

What is a loop in a graph?

A

A loop is an edge with only one endpoint, essentially a connection from a vertex to itself in a graph.It counts as two edges to its own vertex

110
Q

What are parallel edges in a graph?

A

Parallel edges are two or more edges that share the same endpoint(s) in a graph.

111
Q

What is a simple graph?

A

A simple graph is a graph that does not contain loops or parallel edges.

112
Q

What is the definition of adjacent vertices in a graph?

A

Two vertices in a graph are considered adjacent if they are connected by an edge.

113
Q

What is a subgraph in graph theory?

A

A graph H is a subgraph of a graph G if every vertex and edge in H is also present in G, and the edges in H have the same endpoints as in G.

114
Q

What is a complete graph?

A

A complete graph, denoted as K^n, is a simple graph with n vertices where every pair of distinct vertices is connected by an edge.

115
Q

What is a bipartite graph?

A

A bipartite graph is a simple graph that can be divided into two sets of vertices (U and W) such that all edges connect a vertex from set U to a vertex in set W.

116
Q

What is a complete bipartite graph?

A

A complete bipartite graph, denoted as Km,n, is a simple graph with two sets of vertices {v1, … , vm} and {w1, … , wn}, where there is an edge from each vi to each wj, and no edges within either set.

117
Q

How is the degree of a vertex defined in a graph?

A

The degree of a vertex v, denoted as δ(v), is the number of edges incident on v, counting loops twice.

118
Q

Define the degree of a graph.

A

The degree of a graph is the maximum degree among all its vertices.

119
Q

Define the degree of a vertex.

A

The amount of edges connecting to it

120
Q

What does the Handshake Theorem state

A

The Handshake Theorem states that the degree of a graph is equal to twice the number of its edges.

121
Q

What is a tree in graph theory?

A

A tree is a connected graph that has no simple circuits (loops) or loops.

122
Q

What is a spanning tree in a graph?

A

A spanning tree of a graph is a subgraph that includes every vertex of the original graph and is itself a tree.

123
Q

Do all connected graphs have spanning trees?

A

Yes, every connected graph has at least one spanning tree.

124
Q

What is a weighted graph?

A

A weighted graph is a graph in which each edge has an associated positive weight.

125
Q

How does Prim’s Algorithm build a minimum spanning tree?

A

Prim’s Algorithm builds a minimum spanning tree by selecting a vertex and expanding outward, adding one edge and one vertex at each step.

126
Q

How does Kruskal’s Algorithm find a minimum spanning tree?

A

Kruskal’s Algorithm finds a minimum spanning tree by examining edges in increasing weight order and adding edges that do not create circuits.

Semester 1 2024 (5 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions