MATH255 - Mid Term Exam Flashcards
What is a statement
An expression that is either true or false, without ambiguity.Example: “I am a man”
What is a True Statement
Definition: A logically valid statement that is true.Example: “3 + 4 = 7”
What is a Not Statement
Definition: A statement negated using the “~” symbol.Example: “~(3 + 4 = 7)”
What is Ambiguity
Definition: Lack of clarity or uncertainty in a statement.Example: “x > 2” (ambiguous because it depends on the value of x)
What is There exists
Definition: Indicates the existence of at least one element satisfying a condition.Example: “There exists x such that x < 2”
What is a False Statement
Definition: A logically invalid statement that is false.Example: “If x^2 = 9, then x = 1 or x = -1”
What is a Conjunction
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”
What is a Disjunction
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”
What is a Conditional
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”
What is a Tautology
Definition: A compound statement that is always true, regardless of the truth values of its components.Example: “p v ~p”
What is a Fallacy
Definition: A compound statement that is always false, regardless of the truth values of its components.Example: “p ^ ~p”
What is a Biconditional
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”
What is Equivalence Laws
Definition: A set of logical laws that describe how logical operators interact with each other.Example: Commutative, Associative, Distributive, etc.
What is a Contingency
Definition: A statement that is sometimes true and sometimes false, neither a tautology nor a fallacy.Example: “p ^ q”
What is Equivalence
Definition: Two statements are logically equivalent if they have identical truth table values.Example: “p ≡ ~(~p)”
What is Substitution Rule
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
What is Distributive Laws
Definition: Laws stating how one operation distributes over another.Example: p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
What is Associative Laws
Definition: Laws stating that the grouping of operands does not change the result.Example: (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
What is Commutative Laws
Definition: Laws stating that the order of operands does not change the result.Example: p ∨ q ≡ q ∨ p
What is Double Negation Law
Definition: The negation of a negated statement.Example: ∼∼ p ≡ p
What is De Morgan’s Laws
Definition: Laws describing how negation distributes over logical operators.Example: ∼(p ∨ q) ≡ ∼p ∧ ∼q
What is Implication Laws
Definition: Laws relating to conditional statements.Example: p ↔ q ≡ (p → q) ∧ (q → p)
What is Main Connective
Definition: The primary logical operator in a compound statement that binds it together.Example: In (p ∨ q) → (r ∧ s), “→” is the main connective.
What is Universal Quantifier
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.”
What is Existential Quantifier
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.”
What is Predicate
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”
What is Universal Quantifier Example
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.”
What is Domain
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).
What is Truth Set
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}.
What is Existential Quantifier Example
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.”
What is Negation of Existential Statement
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.
What is Negation of Universal Statement
Definition: The process of negating a universal statement to make it an existential statement.Example: ~∀x ∈ R, x > 0 becomes ∃x ∈ R, x ≤ 0.
What is Direct Proof
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.
What is Modus Ponens
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.
What is Proof by Contradiction
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.
What is Modus Ponens Example
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).
What is Law of Syllogism
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.
Law of Syllogism Example
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).
What is Law of Contrapositive
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.
What is Law of Contrapositive Example
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).
What is Negation mean
~
What is Conjunction mean
What is Disjunction mean
v
What is Conditional mean
->
What is Biconditional mean
<->
What is ~
Negation
What is ^
Conjunction
What is v
DIsjunction
What is ->
Conditional
What is <->
Biconditional
What is the truth table for Negation
P ~PT FF T
What is Proof by Contradiction
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
What is the truth table for Disjunction
p q pvqT T FT F TF T TF F F
What is the truth table for Conjunction
p q p^qT T TT F FF T FF F F
What is the rule for remembering Bi-Conditional truth table values
TT and FF = True but TF and FT are False
What is the truth table for Conditional
p q p>qT T TT F FF T TF F T
What is the rule for remembering Conditional truth table values
p implies q is true in all cases except for true implies false (TF = False)
What is ∀
Universal Quantifier - “For All”
What is the truth table for Bi-Conditional
p q p>qT T TT F FF T FF F T
What is ∃
There Exists/Is
What is ∈
Set of / in a set of
What is Z
All/every WHOLE number
What is /∈
Element is not in a set of
What is R
Every real number/every imaginable number
What is ∴
Therefore
What is Z++
Every whole positive number
What is N
Natural number - Positive whole number
What is Ø
Empty set
What is A ⊆ B
A is a subset of B
What is ≠
Not equal to
What is ≤
Less than or equal to
What is A∪B
A UNION B
What is A∩B
A INTERSECTION B
What is Ā or A’
Complement of A
What is |S|
Cardinality |S| = n and say S has cardinality n (number of elements is n) Note: |∅| = 0
What is Z \ A
The \ means without so here it is Z without A, aka the Difference
Does Order in Sets matter?
In set theory, order is not important. For example, {1, 3} is the same as {3, 1}. Sets are unordered collections of elements.
What is with Repeats in Sets
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.
What is Finite Set
A set that contains a finite (limited) number of elements.
What is Infinite Set
A set that contains an infinite (unlimited) number of elements.
What is Natural Numbers (N)
The set of natural numbers consists of all positive whole numbers, including zero (0, 1, 2, 3, …).
What is Universe (U)
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.
What is Integers (Z)
The set of integers includes all whole numbers, both positive and negative, as well as zero (-3, -2, -1, 0, 1, 2, 3, …).
What is Rational Numbers (Q)
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.
What is Q
Rational Numbers
What is Set Notation
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.
What is Empty Set (∅)
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.
What is Subset (⊆)
Set A is a subset of set B (A ⊆ B) if every element of A is also in B.
What is Cardinality of a Set
The cardinality of a set is the number of elements it contains. It is denoted as |S|.
What is Superset
If A is a subset of B, then B is a superset of A.
What is Identity Element
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
What is Inverse Element
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
What is Commutative
An operation is commutative if the order of the operands does not affect the result. For example, addition and multiplication are commutative operations.
What is Associative
An operation is associative if the grouping of operands does not affect the result. For example, addition and multiplication are associative operations.
What is Well-Ordered Set
A set is well-ordered if every nonempty subset of the set has at least one smallest element.
What is Distributive
An operation is distributive if it distributes over another operation. For example, multiplication is distributive over addition.
What is Intersection (∩)
The intersection of sets A and B (A ∩ B) is the set containing all elements that are in both A and B.
What is Union (∪)
The union of sets A and B (A ∪ B) is the set containing all elements that are in either A or B.
What is Set Difference (B - A or B\A)
The set difference B - A (or B\A) contains all elements that are in B but not in A.
What is Complement (Ā or A’)
The complement of set A (Ā or A’) contains all elements that are not in A with respect to the universe U.
What is the difference between a ( and [ in sets
‘(‘ means the -2 is not included/counted‘]’ means the 5 is included/counted
What does (2, 5] mean
All the numbers between 2 and 5 but not counting 2
{1} ∈ {x ∈ N : x^2 = 1}is this true or false
False as the Universe is Natural numbers and given is a set not N
What is Cardinality of an empty set
0
{0,2} ⊆ {1,2,3}True or false
False as 0 is not in set 2
{1,2} ⊆ {1,2,3}True/False?
True as all of A is in B
What is a subset
A subset is a set A derived from set B such that every element of set A is in set B
What is a graph in graph theory?
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.
What is a loop in a graph?
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
What are parallel edges in a graph?
Parallel edges are two or more edges that share the same endpoint(s) in a graph.
What is a simple graph?
A simple graph is a graph that does not contain loops or parallel edges.
What is the definition of adjacent vertices in a graph?
Two vertices in a graph are considered adjacent if they are connected by an edge.
What is a subgraph in graph theory?
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.
What is a complete graph?
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.
What is a bipartite graph?
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.
What is a complete bipartite graph?
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.
How is the degree of a vertex defined in a graph?
The degree of a vertex v, denoted as δ(v), is the number of edges incident on v, counting loops twice.
Define the degree of a graph.
The degree of a graph is the maximum degree among all its vertices.
Define the degree of a vertex.
The amount of edges connecting to it
What does the Handshake Theorem state
The Handshake Theorem states that the degree of a graph is equal to twice the number of its edges.
What is a tree in graph theory?
A tree is a connected graph that has no simple circuits (loops) or loops.
What is a spanning tree in a graph?
A spanning tree of a graph is a subgraph that includes every vertex of the original graph and is itself a tree.
Do all connected graphs have spanning trees?
Yes, every connected graph has at least one spanning tree.
What is a weighted graph?
A weighted graph is a graph in which each edge has an associated positive weight.
How does Prim’s Algorithm build a minimum spanning tree?
Prim’s Algorithm builds a minimum spanning tree by selecting a vertex and expanding outward, adding one edge and one vertex at each step.
How does Kruskal’s Algorithm find a minimum spanning tree?
Kruskal’s Algorithm finds a minimum spanning tree by examining edges in increasing weight order and adding edges that do not create circuits.
