Logic & Proofs
This symbol means "for all"
What is ∀?
The set containing no elements
What is the empty set (∅)?
This term describes a function that is one-to-one and onto
What is a bijection?
Number of ways to choose r items from n
What is combination (nCr)?
A graph with no cycles
What is a tree?
The machine used to recognize regular languages
What is a finite automaton?
This is the method of proving a statement by assuming the opposite
What is proof by contradiction?
This symbol means 'element of'
What is ∈?
This function maps every element in the domain to a unique range element
What is a function?
Arrangement of r items from n
What is permutation (nPr)?
This graph connects every pair of nodes
What is a complete graph?
These expressions define patterns in strings
What are regular expressions?
This rule allows you to derive Q from P → Q and P
What is modus ponens?
The result of combining two sets
What is union (∪)?
A function with the same input and output
What is the identity function?
The rule used to count the number of ways independent events occur
What is the multiplication rule?
A graph with one component and a path between any two vertices
What is a connected graph?
This type of grammar generates context-free languages
What is a context-free grammar?
This is the method of demonstrating truth using steps and reasoning
What is a mathematical proof?
The set of elements in both A and B
What is intersection (∩)?
A relation that is reflexive, symmetric, and transitive
What is an equivalence relation?
This rule is used when events overlap
What is the inclusion-exclusion principle?
This is a node in a graph
What is a vertex?
The set of strings over an alphabet
What is a language?
This proof technique shows a base case and inductive step
What is mathematical induction?
This symbol means 'subset'
What is ⊆?
A function from a set to itself
What is an endomorphism?
This factorial expression represents permutations of n distinct objects
What is n!?
This data structure can be represented as a set of nodes and edges
What is a graph?
This model consists of states, transitions, and accepting states
What is a state machine?