Podcast
Questions and Answers
If division with remainder gives a remainder of 0, this means that a ______ b.
If division with remainder gives a remainder of 0, this means that a ______ b.
divides
When a divides b, a is a ______ of b.
When a divides b, a is a ______ of b.
divisor
When a divides b, b is ______ by a.
When a divides b, b is ______ by a.
divisible
A positive integer p > 1 is considered a ______ if its only positive integer divisors are 1 and p.
A positive integer p > 1 is considered a ______ if its only positive integer divisors are 1 and p.
The ______ Theorem of Arithmetic states that each integer > 1 can be expressed uniquely as a product of primes, up to order.
The ______ Theorem of Arithmetic states that each integer > 1 can be expressed uniquely as a product of primes, up to order.
To determine if n is prime, one common algorithm involves trying to divide n by a = 2, 3,... while a is less than or equal to ______.
To determine if n is prime, one common algorithm involves trying to divide n by a = 2, 3,... while a is less than or equal to ______.
An algorithm to find a prime divisor of n will find the least a ≤ √n which divides n, or, if no divisor is found among the a ≤ √n, then n itself is ______.
An algorithm to find a prime divisor of n will find the least a ≤ √n which divides n, or, if no divisor is found among the a ≤ √n, then n itself is ______.
A statement is considered a ______ if it evaluates to true under all possible interpretations of its variables.
A statement is considered a ______ if it evaluates to true under all possible interpretations of its variables.
A statement is a ______ if it evaluates to false under every possible interpretation.
A statement is a ______ if it evaluates to false under every possible interpretation.
The logical equivalence $p \rightarrow q \equiv (\neg p) \lor q$ shows that a conditional statement can be expressed using negation and ______.
The logical equivalence $p \rightarrow q \equiv (\neg p) \lor q$ shows that a conditional statement can be expressed using negation and ______.
The ______ laws allow for the 'expansion' of combinations of and and or in logical expressions.
The ______ laws allow for the 'expansion' of combinations of and and or in logical expressions.
According to the provided text, all truth functions can be expressed in terms of $\land$, $\lor$, and ______.
According to the provided text, all truth functions can be expressed in terms of $\land$, $\lor$, and ______.
Checking whether a formula $\phi$ with n variables is a tautology requires $2^n$ computations, indicating ______ growth with the increase in the number of variables.
Checking whether a formula $\phi$ with n variables is a tautology requires $2^n$ computations, indicating ______ growth with the increase in the number of variables.
The ______ law, $p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p)$, states that $p$ is equivalent to $q$ if $p$ implies $q$ and $q$ implies $p$.
The ______ law, $p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p)$, states that $p$ is equivalent to $q$ if $p$ implies $q$ and $q$ implies $p$.
Since $p \lor (q \lor r) \equiv (p \lor q) \lor r$, either side can be written as $p \lor q \lor r$, which is similar to how the ______ property works in algebra.
Since $p \lor (q \lor r) \equiv (p \lor q) \lor r$, either side can be written as $p \lor q \lor r$, which is similar to how the ______ property works in algebra.
The greatest ______ of positive integers m and n is denoted as gcd(m, n).
The greatest ______ of positive integers m and n is denoted as gcd(m, n).
For an integer $n > 1$, if it has a divisor, it has a divisor $ \leq \sqrt{n}$, because for any divisor $a > \sqrt{n}$ we also have the divisor $n/a$, which is $< \sqrt{n}$. This fact is used in recognizing ______.
For an integer $n > 1$, if it has a divisor, it has a divisor $ \leq \sqrt{n}$, because for any divisor $a > \sqrt{n}$ we also have the divisor $n/a$, which is $< \sqrt{n}$. This fact is used in recognizing ______.
The ______ algorithm repeatedly divides the greater number by the smaller, keeping the smaller number and the remainder.
The ______ algorithm repeatedly divides the greater number by the smaller, keeping the smaller number and the remainder.
In the Euclidean Algorithm, if the remainder r equals ______, the algorithm terminates and returns the last non-zero remainder as the GCD.
In the Euclidean Algorithm, if the remainder r equals ______, the algorithm terminates and returns the last non-zero remainder as the GCD.
The ______ Euclidean algorithm allows us to express the greatest common divisor d of two numbers m and n as a linear combination: am + bn = d.
The ______ Euclidean algorithm allows us to express the greatest common divisor d of two numbers m and n as a linear combination: am + bn = d.
Given the equation am + bn = d, where d is the gcd(m, n), the values a and b can be found by working ______ through the steps of the Euclidean algorithm.
Given the equation am + bn = d, where d is the gcd(m, n), the values a and b can be found by working ______ through the steps of the Euclidean algorithm.
In the example provided, to find the solution to 237a + 105b = 3 using the extended Euclidean algorithm, substitutions are made based on rearrangements of lines from the original ______ algorithm working.
In the example provided, to find the solution to 237a + 105b = 3 using the extended Euclidean algorithm, substitutions are made based on rearrangements of lines from the original ______ algorithm working.
The Euclidean algorithm determines the greatest common divisor (GCD) of two numbers without needing to find their ______ divisors.
The Euclidean algorithm determines the greatest common divisor (GCD) of two numbers without needing to find their ______ divisors.
A sentence ψ is a ______ consequence of a sentence φ, if ψ = T whenever φ = T.
A sentence ψ is a ______ consequence of a sentence φ, if ψ = T whenever φ = T.
The statement φ ≡ ψ means (φ ⇒ ψ) and (ψ ⇒ φ), indicating that logical equivalence is ______.
The statement φ ≡ ψ means (φ ⇒ ψ) and (ψ ⇒ φ), indicating that logical equivalence is ______.
Unlike logical equivalence, the logical consequence (⇒) is not ______, meaning that if φ ⇒ ψ, it does not necessarily follow that ψ ⇒ φ.
Unlike logical equivalence, the logical consequence (⇒) is not ______, meaning that if φ ⇒ ψ, it does not necessarily follow that ψ ⇒ φ.
In predicate logic, ∀ is a quantifier that means '______' indicating that a statement holds true for all instances of a variable within a specified domain.
In predicate logic, ∀ is a quantifier that means '______' indicating that a statement holds true for all instances of a variable within a specified domain.
In predicate logic, ∃ is a quantifier that means '______' indicating the existence of at least one element that satisfies a given condition.
In predicate logic, ∃ is a quantifier that means '______' indicating the existence of at least one element that satisfies a given condition.
A predicate, such as P(n) : 'n is prime,' is not a proposition because its truth value depends on the value of n; thus, it acts as a ______ that yields a Boolean value based on its input.
A predicate, such as P(n) : 'n is prime,' is not a proposition because its truth value depends on the value of n; thus, it acts as a ______ that yields a Boolean value based on its input.
The tautology 'if p implies q and p is true then q is true' can be represented using logical notation as an application of ______.
The tautology 'if p implies q and p is true then q is true' can be represented using logical notation as an application of ______.
Predicates with one variable are often referred to as ______, while those with two or more variables are commonly called relations.
Predicates with one variable are often referred to as ______, while those with two or more variables are commonly called relations.
The language of predicate logic is based on predicate symbols, variables, constants, brackets, $\forall$, $\exists$ and ______.
The language of predicate logic is based on predicate symbols, variables, constants, brackets, $\forall$, $\exists$ and ______.
A sentence in predicate logic is considered ______ if it evaluates to true under all possible interpretations.
A sentence in predicate logic is considered ______ if it evaluates to true under all possible interpretations.
An interpretation of a symbol such as $P(n)$ must include both the range of the variable $n$, as well as stating those $n$ for which $P(n)$ is ______.
An interpretation of a symbol such as $P(n)$ must include both the range of the variable $n$, as well as stating those $n$ for which $P(n)$ is ______.
Unlike propositional logic, there are infinitely many different ______ of each formula in predicate logic.
Unlike propositional logic, there are infinitely many different ______ of each formula in predicate logic.
The statement $\forall x \exists y Q(x, y) \rightarrow \exists x \forall y Q(x, y)$ is false if $Q(x, y)$ is interpreted as $x < y$ on the ______ numbers.
The statement $\forall x \exists y Q(x, y) \rightarrow \exists x \forall y Q(x, y)$ is false if $Q(x, y)$ is interpreted as $x < y$ on the ______ numbers.
A sentence $\psi$ is a logical ______ of a sentence $\phi$ if any interpretation that makes $\phi$ true also makes $\psi$ true.
A sentence $\psi$ is a logical ______ of a sentence $\phi$ if any interpretation that makes $\phi$ true also makes $\psi$ true.
We write $\phi \Rightarrow \psi$ if $\psi$ is a consequence of $\phi$, which is equivalent to stating that the implication $\phi \rightarrow \psi$ is ______.
We write $\phi \Rightarrow \psi$ if $\psi$ is a consequence of $\phi$, which is equivalent to stating that the implication $\phi \rightarrow \psi$ is ______.
Sentences $\psi$ and $\phi$ are considered ______, written as $\psi \equiv \phi$, if each is a consequence of the other.
Sentences $\psi$ and $\phi$ are considered ______, written as $\psi \equiv \phi$, if each is a consequence of the other.
______ expresses the fact that each natural number n can be reached by starting at 0 and going upwards a finite number of times.
______ expresses the fact that each natural number n can be reached by starting at 0 and going upwards a finite number of times.
The principle of well-ordering asserts that every non-empty set of natural numbers contains a ______ element.
The principle of well-ordering asserts that every non-empty set of natural numbers contains a ______ element.
Proofs that 'work downwards' and appeal to well-ordering are sometimes called ______.
Proofs that 'work downwards' and appeal to well-ordering are sometimes called ______.
To prove that any integer > 2 has a prime divisor, if n is not prime, we let $n_1 < n$ be a ______ of n.
To prove that any integer > 2 has a prime divisor, if n is not prime, we let $n_1 < n$ be a ______ of n.
The formula $1 + a + a^2 + ... + a^n = \frac{a^{n+1} - 1}{a - 1}$ is likely to require ______ induction for its proof.
The formula $1 + a + a^2 + ... + a^n = \frac{a^{n+1} - 1}{a - 1}$ is likely to require ______ induction for its proof.
The statement $¬(p_1 ∨ p_2 ∨ p_3 ∨ ... ∨ p_n) ≡ (¬p_1) ∧ (¬p_2) ∧ (¬p_3) ∧ ... ∧ (¬p_n)$ is an example of ______ Law.
The statement $¬(p_1 ∨ p_2 ∨ p_3 ∨ ... ∨ p_n) ≡ (¬p_1) ∧ (¬p_2) ∧ (¬p_3) ∧ ... ∧ (¬p_n)$ is an example of ______ Law.
When proving that each fraction $\frac{n}{m} < 1$ is a sum of distinct fractions with numerator 1, the fractions must be ______.
When proving that each fraction $\frac{n}{m} < 1$ is a sum of distinct fractions with numerator 1, the fractions must be ______.
In the context of well-ordering and descent, an ______ descending sequence of natural numbers is impossible.
In the context of well-ordering and descent, an ______ descending sequence of natural numbers is impossible.
Flashcards
What signifies that 'a' divides 'b'?
What signifies that 'a' divides 'b'?
When dividing 'b' by 'a', if the remainder is 0, 'a' divides 'b'.
Divisor/Factor vs. Divisible/Multiple
Divisor/Factor vs. Divisible/Multiple
A number 'a' is a divisor/factor of 'b' if 'b' is divisible/a multiple of 'a'.
What is a prime number?
What is a prime number?
A positive integer greater than 1 that is only divisible by 1 and itself.
Fundamental Theorem of Arithmetic
Fundamental Theorem of Arithmetic
Signup and view all the flashcards
Primality Test Algorithm
Primality Test Algorithm
Signup and view all the flashcards
Finding a Prime Divisor
Finding a Prime Divisor
Signup and view all the flashcards
How to find a prime divisor of n.
How to find a prime divisor of n.
Signup and view all the flashcards
Why is 1 not a prime number?
Why is 1 not a prime number?
Signup and view all the flashcards
Greatest Common Divisor (GCD)
Greatest Common Divisor (GCD)
Signup and view all the flashcards
Euclidean Algorithm
Euclidean Algorithm
Signup and view all the flashcards
Prime Recognition Rule
Prime Recognition Rule
Signup and view all the flashcards
Extended Euclidean Algorithm
Extended Euclidean Algorithm
Signup and view all the flashcards
Bézout's Identity
Bézout's Identity
Signup and view all the flashcards
First step Euclidean Algorithm (237, 105)
First step Euclidean Algorithm (237, 105)
Signup and view all the flashcards
Euclidean Algorithm Step
Euclidean Algorithm Step
Signup and view all the flashcards
GCD(237, 105)
GCD(237, 105)
Signup and view all the flashcards
Tautology
Tautology
Signup and view all the flashcards
Contradiction
Contradiction
Signup and view all the flashcards
p → q ≡ (¬p) ∨ q
p → q ≡ (¬p) ∨ q
Signup and view all the flashcards
∨ (Disjunction)
∨ (Disjunction)
Signup and view all the flashcards
∧ (Conjunction)
∧ (Conjunction)
Signup and view all the flashcards
¬ (Negation)
¬ (Negation)
Signup and view all the flashcards
Logical Equivalence
Logical Equivalence
Signup and view all the flashcards
p ↔ q ≡ (p → q) ∧ (q → p)
p ↔ q ≡ (p → q) ∧ (q → p)
Signup and view all the flashcards
Modus Ponens
Modus Ponens
Signup and view all the flashcards
Logical Consequence (φ ⇒ ψ)
Logical Consequence (φ ⇒ ψ)
Signup and view all the flashcards
Logical Equivalence (φ ≡ ψ)
Logical Equivalence (φ ≡ ψ)
Signup and view all the flashcards
Predicate
Predicate
Signup and view all the flashcards
Universal Quantifier (∀)
Universal Quantifier (∀)
Signup and view all the flashcards
Existential Quantifier (∃)
Existential Quantifier (∃)
Signup and view all the flashcards
Boolean-valued Function
Boolean-valued Function
Signup and view all the flashcards
Property (in logic)
Property (in logic)
Signup and view all the flashcards
Predicate Logic Language
Predicate Logic Language
Signup and view all the flashcards
Valid Sentence
Valid Sentence
Signup and view all the flashcards
Interpretation
Interpretation
Signup and view all the flashcards
Logical Consequence
Logical Consequence
Signup and view all the flashcards
Equivalence
Equivalence
Signup and view all the flashcards
False Predicate Logic Sentence
False Predicate Logic Sentence
Signup and view all the flashcards
Induction
Induction
Signup and view all the flashcards
Well-ordering
Well-ordering
Signup and view all the flashcards
Infinite descent
Infinite descent
Signup and view all the flashcards
Prime Divisor Theorem
Prime Divisor Theorem
Signup and view all the flashcards
Proof by descent
Proof by descent
Signup and view all the flashcards
Well-Ordering and Descent
Well-Ordering and Descent
Signup and view all the flashcards
Strong Induction
Strong Induction
Signup and view all the flashcards
Proof that √2 is irrational
Proof that √2 is irrational
Signup and view all the flashcards
Study Notes
- These are study notes for the MAT1830 course
- Discrete mathematics studies objects with distinct separated values, like integers
- Discrete mathematics is vital to computer science
- The importance of proving results is emphasized
Course Topics
- Numbers
- Logic
- Induction and recursion
- Sets, functions, and relations
- Probability
- Graph theory
Proofs
- A proof is essentially just a water-tight argument that a certain statement must be true
- Proofs are useful even when something is believed to be true
Maths in Computer Science
- Number theory enables secure communication in cryptography
- Logic is used in digital circuit design and in program control flow
- Induction and recursion are used to study algorithms and their effectiveness
- Functions are important in the theory of programming, and relations are vital in database theory and design
- Probability assists in understanding randomized algorithms
- Probability enables the creation of systems that deal with uncertain situations
- Graph theory is used in software for allocation and scheduling problems
Divisors
- Integer a divides integer b, b = qa for integer q
- If a divides b:
- a is a divisor of b
- a is a factor of b
- b is divisible by a
- b is a multiple of a.
Primes
- Prime number p > 1, positive integer divisors are 1 and p
- The first few prime numbers are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43
Fundamental Theorem of Arithmetic
- Each integer > 1 can be expressed in exactly one way, up to order, as a product of primes
- If an integer n > 1 has a divisor, it has a divisor < √n
Algorithm for Recognizing Primes
- Try dividing n by a = 2, 3,... while a ≤ √n
Finding Divisors
- Finds a prime divisor of n
- Either the least a <√n which divides n
- or, if no divisor among the a ≤ √n, n is prime
Euclidean Algorithm
- Finds the greatest common divisor of positive integers m and n, gcd(m, n), without finding prime divisors.
- Repeats division of greater number by smaller, keeping the smaller number and remainder
Fact
- If a, b, and k are integers, then gcd(a - kb, b) = gcd(a, b)
Extended Euclidean Algorithm
- If the Euclidean algorithm finds gcd(m, n) = d, it can work backwards to find integers a and b such that am + bn = d
Congruences
- Integers a and b are congruent modulo n, a ≡ b (mod n)
- n divides a - b
Substitutions with Congruences
- If a ≡ b (mod n) and b ≡ c (mod n), then a ≡ c (mod n)
Adding, Subtracting, and Multiplying Congruences
- If a₁ ≡ b₁ (mod n) and a₂ ≡ b₂ (mod n), then:
- a₁ + a₂ ≡ b₁ + b₂ (mod n)
- a₁ - a₂ ≡ b₁ - b₂ (mod n)
- a₁a₂ ≡ b₁b₂ (mod n)
Division
- If a ≡ b (mod n) and d divides a, b, and n, then a/d ≡ b/d (mod n/d)
Solving Linear Congruences
- To find integers x that congruences satisfy ax ≡ b (mod n), find d = gcd(a, n)
Procedure if d = 1
- Find integers x' and y' such that ax' - ny' = b
- Integers x that satisfy the original congruence are those for which x ≡ x' (mod n).
Procedure if d > 1 and d divides b:
- Divide through the congruence by d to get the equivalent congruence x ≡ (mod ).
- Then use the method above on the new congruence.
Procedure if d doesn't divide b:
- The congruence has no solutions
Modular Inverses
- Integer a modulo n is an integer x such that ax ≡ 1 (mod n)
- Such an inverse will exist if and only if gcd(a,n) = 1
- If inverses exist, they can be found using the extended Euclidean algorithm
Propositional Logic
- The simplest and most commonly used part of logic
Proposition
- Any sentence with a definite truth value (true= T or false= F)
- Propositions are denoted by letters and combined into compound propositions by connectives
Connectives
- Connectives include ∧ (and), ∨ (or), and ¬ (not)
- Defined to agree with the most common interpretations of the words "and," "or," and "not"
Truth Tables
- Used to define connectives and show the truth value of compound propositions under all possible combinations of truth values for their components
Implication
- Truth function p → q corresponds to "if p then q"
- p→ q is true when p is false
Other Connectives
- ↔ (“if and only if”)
- ∨ (“exclusive or”)
- The sentence p ↔ q is true exactly when the truth values of p and q agree
- p ∨ q is true exactly when the truth values of p and q disagree
Symbols
- A and V are similar to the symbols ∩ and U for set intersection and union
Tautologies and Contradictions
- A sentence in propositional logic is a formula with variables that can take the values T and F
- The possible interpretations of are all assignments of values to its variables
If a sentence in propositional logic has value T under all interpretations, it is a tautology
- Like "always true"
If a sentence in propositional logic has value F under all interpretations, it is a contradiction
- Like "always false"
- Whether is a tautology, a contradiction, or neither is checked by computing every value
Logical Equivalence
- Sentences are logically equivalent if they are the same truth function
- ↔ q is a tautology
Useful Equivalences: Equivalence Law
- p ↔ q ≡ (p → q) ∧ (q → p)
Useful Equivalences: Implication Law
- p → q¬ ≡ (p) ∨ q
Useful Equivalences: Double Negation Law
- p¬¬ ≡ p
Useful Equivalences: Commutative Laws
- p∧q≡q∧p
- p∨q≡q∨p
Useful Equivalences: Distributive Laws
- p∧ (q ∨ r)≡ (p ∧ q) ∨ (p ∧ r)
- p∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
Useful Equivalences: De Morgan’s Laws
- ¬(p ∧ q)≡ (¬ p) ∨ (¬ q)
- ¬ (p ∨ q) ¬≡ (p) ∧ (q)
Useful Equivalences: Identity Laws
- p∧T≡p
- p∨F≡p
Useful Equivalences: Annihilation Laws
- p∧F≡F
- p∨T≡T
Useful Equivalences: Inverse Laws
- p∧ (¬ p) ¬≡ F
- p∨ (¬ p) ¬≡ T
Useful Equivalences: Absorption Laws
- p∧ (p ∨ q)≡ p
- p ∨ (p ∧ q)≡ p
Rules of Inference: Replacement
Any sentence may be replaced by a logically equivalent sentence
Contrapositives
- x → y ≡ (¬ y) → (¬x)
- (¬ y) → (¬x) is the contrapositive of x → y
Logical Consequence
A sentence & is a logical consequence of a sentence $, if & = T whenever = T
- Written as ¢ ⇒ ψ.
- is the same as to say that → is a tautology, but ¢ ⇒ ψmakes it clearer that we discussing relation between the sentences
- Any sentence & logically equivalent to is a logical consequence of , but not all consequences of are eqivalent to it
Predicates and Quantifiers: Properties
- More expressive than propositional logic by admitting predicates
- Stand for properties or relations
Quantifiers
– ∀ (meaning “for all”) – ∃ (meaning “there exists” or “there is”)
Building Sentences from Predicates
- To create sentence replace predicate variables by constants
- Quantifiers and connectives combine logic statements
Alternating Quantifiers: Combination
- Combinations such as ∀x∃y, “for all x there is a y”
- common in mathematics
- can be confusing
- These help recall the difference between ∀x∃y...and ∃y∀x
Predicate Logic: Valid Sentences
- The language is based in predicate symbols, variables, brackets, constants, ∀,∃,and connectives
Consequence and equivalence
- a sentence if is a logical consequence of a sentence ¢ if any interpretation which makes true makes & true
- Written ¢ ⇒ & if & ia consequence of -this is the same as saying ¢ → is valid
Useful Equivalences: Infinite De Morgan's laws
- Two important equivalences involving quantifiers
- ∀xP(x)∃ = x¬P(x)-
- ∃∀xP(x)= x¬P(x) Two important equivalences involving quantifiers
Mathematical Induction
– Principle used in style of proof called proof by induction, in two steps –Base Step: Proof that required property P true for 0. –Induction Step: Proof that if P(k) true then P(k + 1) is true, for each k ∈ N
###Starting the Base Step higher Not always appropriate to start the induction at 0
Sums of Series
Induction is used to prove that sum formulas are correct
Well-Ordering of Natural Numbers
Every set of natural numbers has a least element.
Proofs by Descent
Equivalent to induction.
Sets
- Vital when expressing mathematics formally A set is an unordered collection of objects called its elements or numbers There are no notions such as order, multiplicity
Subsets
Given A and B, A is a subset of B when every element of A is an element of B
Characteristic functions
Used to specify a subset A of B, which tells which elements of B are in A, which are not
Set and Properties
A and B may only be equal given certain conditions
Operations on Sets: Venn Diagrams
Visualize set operations by showing sets A,B, etc wihin a rectangle representing the univesal set U
Union
A U B of sets A and B consist of the elements in A or B
Intersection ANB
The set of intersection of a function set A and B onsist of the elements in A and B
Difference A — B.
The difference A - B of sets A and B consists of the elements in A and not in B
Cartesian Product A × B
The set of order pairs A x B = {(a + b) : aEA and beA}, where it produces a cartesian product of set A an d B A X B and Multiplication - This also has to do with geometry
Functions: Defining functions
A function consists of a domain , co-domain, and a set of pair from X x Y that has exactly one ordered pair X x X Formally representation = {x E R} and y value
Arrow Notation
- can define square: R → R or square :R → R≥o
- functions are usually are not 1 to 1.
One to One Functions
There are some easier to work with because each y in the image of f there is only X e X to give fix 13.2 =Arrow notations
Cartesian Product of two variables
x=R x R → R by sum ( x,y) =x +y; for functions of variables is that output would be numbers from two variables
Sequences
- An infinite sequence can be viewed as a function f: NR
- Inputs to f are natural numbers
- outputs are real numbers
Characteristic functions
- A subject of N can be represented , for example the set of square represented by function X:N→{0,1} defined by x(n) 1-if n is
Boolean Functions
- The connectives A , V → B
- Is completely defined by on T and F
- They are defined this way so they agreed with truth tables
- Now we switch cases with this new value Note B →B is a function a single variable , so and it is easy understand
Characteristic function and Subsets of n
Some things have to be a new one Example A and B in order to function a and b in each element A to B of all A and B There are two variables with 359 functions
Composition and Inversion
- Complicated functions use the following stats square add and cube function in R to R
- Function f: x →y & =go h( )
Identify Functions
- Function is called a function on each set
Inverse Function
F:A→A are id to B&
- F°g & go f ifa
Conditions for Inversion
1 there one to one = one to other 2 log= e
Operations
is particular type of function with code main
Transformations of graph
(a11 @12)x by matrix by dot product of matrix
Inverting 2 variables
Walks
Graph Theory
A graph consists a fine point of objects called vertices together with a set unordered pairs These graphs are normally repped by pictures, The diagrams allow for some graphs to give u all the information with the points and lines
Adjacency Matrix
A matrix whose (i,j) is the quantity of all
The product of matrices dot products from matrices
Degree-A vertex with graph is no number if edges of G that includes
Tree
A graph connected that has no sub graph a circle
Spanning Tree
Has any corrected graph contains as spawning three
- This is Poved by Induction on the number of edges Base Step : if gas no edge but connected Induction step : If has a spanning Tree
Breadth -first Ording
- It's a level 0 type It Has one edge for the Roots
Queues
- The Root vertex is first in the queue Vertices Ajacent are in the head Each vertex doesn't come from the other
Spanning Tree
Is what comes from the root first This Helps the Q, & the tree grow Depth has algo uses Stack.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Related Documents
Description
Explore the concepts of divisibility, divisors, and prime numbers. Learn about the Fundamental Theorem of Arithmetic and methods for primality testing. Understand tautologies and contradictions in mathematical statements.
