Help
Options
Didn't know it?
click below
click below
Knew it?
click below
click below
Don't Know
Remaining cards (0)
Know
retry
shuffle
restart
0:00
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.
Normal Size Small Size show me how
Normal Size Small Size show me how
MLFCS
Mathematical & Logical Foundations of CS
| Question | Answer |
|---|---|
| What does m ∣ n mean? | m is a divisor of n, meaning m divides n. |
| How is (a div m), (a mod m) ∈ ℤ defined? | For each integer a, there exists unique q, r ∈ ℤ , 0 <= r <= m, a = qm + r. So, a = (a div m)m + a(mod m), m is the modulus, a div m is the quotient, a mod m is the remainder. |
| What is a proposition? | A statement that is true or false. |
| What is a predicate? | A proposition about a variable x. |
| How do you prove/disprove P(x) ⇒ Q(x)? | To prove P(x) implies Q(x): - Suppose there's an x where P(x) is true. - Explain why Q(x) is also true. To disprove, find a counterexample. |
| What does it mean for a, b to be congruent modulo m? | a mod m = b mod m, i.e a and b have same remainder when dividing by m. |
| If an integer a mod m is any b, what is ab? | 1 mod m. |
| What must be true for a^-1 (mod m) to exist? | There exists integers x and y such that: ax + my = 1. If a, m are coprime. |
| What is GCD? | Greatest common divisor. |
| How does Euclid's algorithm work? | Euclid’s algorithm works by finding a GCD of two integers by repeatedly dividing the larger number by the smaller one, replacing larger number with remainder, until remainder becomes zero. |
| What does it mean for two numbers a, b to be coprime? | If gcd(a, b) = 1. |
| What is the general form of an inductive proof? i.e proving ∀n . P(n) | - A base case : P(0) - An industive step: Prove P(n) -> P(n+1) |
| What is a sequence? | A function whose domain is the natural numbers. |
| What does the chinese remainder theorem do and how does it work? | Finds simultaneous congruences. Given x ≡ a1 (mod m1), x ≡ a2 (mod m2), gcd (m1, m2) = 1, and solutions given by x ≡ N(modm1, m2), then: If m1x + m2y = 1, then N = a2m1x + a1m2y. |
| What is a set? | A collection of elements where orders and repeats do not matter. |
| Define the following set elements: 1. { x ∣ P(x) } 2. { } 3. X ⊆ Y 4. ∣ X ∣ 5. P(X) 6. X x Y | 1. Set of x such p(x) is true. 2. Empty set. 3. X is a subset of Y. 4. Cardinality, i.e number of elements 5. Powerset of X (set of all subsets) 6. Product of sets X, Y. |
| What is the difference between [a, b], (a, b) and [a, b)? | [a, b] = Closed interval, a ≤ x ≤ b (a, b) = Open interval, a < x < b [a,b) = Half-open interval, a ≤ x < b |
| What is the template for strengthened induction? | Before induction, confirm you can prove ∀n . P(n) by direct induction. Otherwise, find Q(n) with Q(n) ⇒ P(n) that is amenable to induction. Then, prove ∀n . Q(n) by induction, stating predicate Q(n) first. Finally, prove Q(n) ⇒ P(n). |
| What is X^2? | Set pairs {( x,y) ∣ x, y ∈ X} |
| How do you draw a relation as a graph? | - Draw elements of X as vertices -When x R y draw an edge from x to y |
| What is a reflexive relation? | Every element relates to itself. |
| What is a symmetric relation? | If two nodes are connected, they go either way. |
| What is a transitive relation? | Wherever you can go in two steps, there is a one step shortcut. |
| What is an equivalence relation? | A relation that is reflexive, transitive and symmetric. |
| If R is an equivalence relation on X, what is the equivalence class? | [x], = { y ∈ X ∣ x R y} |
| How do you generate an equivalence relation? | Reflexivity: Add in all pairs (x, x) for x ∈ X Symmetry: When x R y, add pair (-y, x) Transitivity: When x R y ^ y R z, add pair (x, z) (this may be repeated) |
| What is a domain vs codomain? | Domain: set of inputs Codomain: set of outputs |
| What makes a function total and single-valued? | Total: For all x ∈ X, there is y ∈ Y with x f y. Single-valued; for all x ∈ X, there is at most one y ∈ Y with x f y. |
| What is an injection? | When distinct inputs go to distinct outputs. |
| What is a surjection? | When every potential output is the image of some input. |
| What is a bijection? | A one-to-one correspondence, i.e an injection and a surjection. |
| What is arity and fixity? | Arity: Number of arguments a terminal symbol takes. Fixity: Place where it occurs with respect to arguments. |
| What is an abstract syntax tree (AST)? | A tree that displays an expression derived from BNF (Backus-Naur Form) grammar, e.g breaking down 0+1+2 |
| What is a metavariable / schematic variable? | Variables that act as placeholders for any element derivable from a grammar rule. |
| What would the substitution exp/1 mean? | Maps the variable exp to 1, e.g (exp + 0 = 0 exp)[exp/1] returns 1 + 0 = 0 1. |
| What is a substitution operation? | An operation that replaces all occurrences of keys by corresponding values. E.g, eq[s] takes equality eq, a substitution s, and replaces all values s by values in eq. |
| What is an atomic proposition? | Propositions that cannot be broken down into smaller parts. |
| List inference rules in propositional logic. | And-introduction [^I] Implication-elimination [-> E] Implication-introduction [-> I] False-elimination [⊥E] True-introduction [⊤ I] Negation-elimination [-E] |
| What is natural deduction? | A natural style of constructing a proof by applying inference rules. |
| What do classical reasoning systems rely on? | Boolean truth values. |
| What inference rules are used in classical reasoning, but NOT constructive reasoning? | - Double Negation Elimination (DNE): --A is A, (-A) -> False is A. - Law of Excluded Middle (LEM): For each A, we can always prove one of A or -A, without knowing which is true. |
| What do semantics do? | Assign meanings with formulas, the basic notation being truth values. |
| What is a truth assignment? | A function assigning a truth value for each atomic proposition. E.g if a formula is P V Q, a truth assignment could be ϕ(P) = T, ϕ(Q) = F |
| When is A satisfiable and valid? | Satisfiable: There exists a valuation ϕ on atomic propositions such that ϕ(A) = T. Valid: ϕ(A) = T for all possible valuations ϕ. |
| What is the difference between syntactic and semantic? (in terms of validity of an argument) | Syntactically: can derive conclusion from premises Semantically: conclusion is true whenever premises are. |
| What is soundness and completeness? | Soundness: A deduction system is sound w.r.t a semantics if every provable formula is valid. Completeness: a deduction system is complete w.r.t a semantics if every valid formula is provable. |
| What are pros and cons between using truth tables compared to natural deduction? | Pros: Simple, easy to automate, generates counterexamples if invalid. Cons: Shows validity in a restricted setting rather than an actual proof, size of table is huge whereas natural deduction scales better. |
| What is Conjunctive Normal Form (CNF)? | A conjunction of CNF clauses, which is basically ANDs connecting clauses. (ANDs connecting ORs). Cannot have implications. |
| What is Disjunctive Normal Form (DNF)? | A disjunction of DNF clauses with literals, which is basically ORs connecting clauses (ORs connecting ANDs). E.g, A -> B is -A V B. Cannot have implications. |
| What is the difference between predicate logic and propositional logic? | Proposition logic allows us to state facts, but cannot state properties of and relations between objections, e.g parity. That's why predicate logic exists. |
| What is predicate logic and it's ingredients? | Contains propositional logic, and allows us to reason about members of a domain. Ingredients are predicates, quantifiers, variables, functions and constants. |
| Explain the difference between free and bound variables. | Bound: Consider ∀ x. even(x) v odd(x): x is bound by quantifier ∀ Renaming a bound variable does not change meaning. Free: Consider ∀ y.x <= y. y is bound, x is free. Variables are free if not bound. Renaming free variables change the meaning |
| What is a signature? | The pair of a collection of function symbols, and a collection of predicate symbols, along with their arities. |
| What is a model, given a signature? | A model provides the interpretation of all symbols. A model provides interpretations for function symbols (e.g add) and predicate symbols (e.g even). They replace truth assignments. |
| How do you prove a logical equivalence A⇔ B? | Prove we can derive B from A. Prove we can derive A from B. |
| What makes an augmented matrix be in echelon form? | 1. Every row with zero entries only is below rows with non-zero entries. 2. First non-zero entry of each row is to the right of a leading entry above. |
| What makes an augmented matrix be in reduced row echelon form? | 1. In row echelon form 2. Every leading entry is 1 3. Every entry above/below leading entry is 0. |
| Given an augmented matrix, what is the general method of computing reduced row echelon form? | 1. Use row operations to get row echelon form. 2. Get a reduced row echelon form of result. (row ops) 3. Extract solution: If there is a row form (0, ..., 0 ∣ 1), no solution Otherwise, solution formed by equations xi = b - a(i+1)x(i+1) -...-a(n)x(n) |
| What is redundancy and inconsistency of constraints? | Unique solution = some redundant constraints No redundant constraint = Inconsistent (no solution) |
| What is the vector space? | A set V with abstract vector elements, which has a zero vector, and allows for operation of scalar multiplication and vector addition. |
| What form can every expressions with vectors take when normalizing using axioms? | r(1)v(1) + ... + r(k)v(k) Called a linear combination |
| What makes S linearly dependent vs. linear independent? | S is linearly dependent if for some vectors in S, and some non-zero r1... rk.. r(1)v(1) + .... + r(k)v(k) = 0 S is linearly independent if r(1)v(1) + ... + r(k)v(k) = 0 entails r1 = ... = rk = 0 |
| What is the span and basis in vector space? | The span is the set of all linear combinations of the vectors. The basis is the set of vectors that are linear independent and span the vector space. |
| Explain what coordinates are, and what are coordinates of (x, y) ∈ R^2 in B = {(3,4), (5, 6)}? | Coordinates are unique coefficients in linear combinations of basis vectors (x, y) = a(3, 4) + b(5, 6) Follows that a = (5y-6x) / 2, b = (4x - 3y) / 2 |
| Given coordinates (x, y), and a rotation θ counterclockwise to point (x', y'), what is x' and y' in terms of x and y? | y' = (cosθ)x + (sinθ)y x' = (-sinθ)x + (cosθ)y |
| What is a linear operator? | Transformations that preserve linear structure. For example, given vector spaces V and W, a map F: V -> W is a linear operator if F(rv) = rF(v), F(v + w) = F(v) + F(w) General examples include scaling and zero operators. |
| How do you transpose a matrix? | Swap the rows and columns. |
| What are the steps in the Algorithm for Computing Inverse Matrix on matrix A? | 1. Form augmented matrix (A ∣ I ) 2. Use elementary row operations to obtain (I ∣ B) 3. If succeeded, A^-1 = B, otherwise A^-1 does not exist. |
| What is the rank of a matrix? | The maximum number of linearly independent row vectors or column vectors. (non zero rows in reduced row echelon form) Row rank = column rank |
| What must be true for a matrix A be invertible? | If and only if A is n x n and n = rank A |
| What makes two vectors v1 and v2 orthogonal? | Their dot product, v1 ⋅ v2 = 0. |
| What are orthogonal operators? | Operators that preserve distances and angles, confined to a dimension. |
| What makes an n x n matrix A orthogonal? | If (A^T)A = I |
| What makes a basis orthogonal and orthonormal? | Orthogonal if every vector in the basis is orthogonal to each other, i.e vi ⋅ vj = 0. Orthonormal if each vector in an orthogonal basis has length 1. |
| What is a householder reflection? | A linear transformation describing a reflection about a hyperplane containing the origin. They are orthogonal |
| Given a square n x n matrix A, what makes a column vector v eigenvector? | If Av = λv, for some real λ, with v being the corresponding eigenvalue. |
| What makes a matrix rank-deficient? | If the rank is less than the maximum possible, i.e rows and columns are not linearly independent. |
Created by:
user-2035207