Proofs Theory Flashcards
Theory for mathematical proofs.
What is a proof?
Logical argument that establishes beyond any doubt that something is true.
What are everyday types of reasoning?
Inductive and Deductive reasoning
What is inductive reasoning?
Drawing a conclusion from what we see around us.
Give example for Inductive reasoning?
If all the sheep you have ever seen are white you might conclude that all sheep are white.
If you use inductive reasoning be open to revisit your conclusion once there are new evidence.
What is deductive reasoning?
Starting from a general statement that you know for sure is true and drawing conclusions from there.
Give example for deductive reasoning?
If you know for a fact that all sheep like to eat grass and you know that the creature in front of you is a sheep then you know it likes grass.
This kind of reasoning is rock solid. It can only go wrong if your promise is false (all sheep like grass) or if your observation is false (the creature in front of you is not a sheep).
What is Axiom?
A statement or proposition which is regarded as being established accepted or self evidently true.
What is direct proof?
One of the most familiar forms of proof. It can be used to prove statements of the form “if P then Q” or “P implies Q”. The method of the proof is to take an original statement “P” which we assume is true and use to show directly that another statement “Q” is true
What are the steps of direct proof?
- Assume the statement “P” is true.
- Use what we know about “P” and other facts as necessary to deduce that another statement “Q” is true, that is to show “P implies Q” is true.
What is proof by contradiction?
This method is not limited to proving just conditional statements. It can be used to prove any kind of statements.
The idea is to assume what we want to prove is “FALSE” and then show that this assumption leads to nonsense which means that our assumption is true.
What is the description of proof by contradiction?
If an assertion implies something false then the assumption itself must be false.
What is The Well-Ordering principle?
It is proof method with the following property:
- Every nonempty set S of non-negative integers has a least element.
This property is not true for subset of the integers or the positive real numbers.
What is propositional logic?
Branch of mathematical logic which studies the logical relationships between propositions taken as a whole and connected via logical connectives.
How propositional logic can be represented?
In propositional logic a statement is represented by a symbol (or letter) whose relationship with other statements is defined via connectives.
The statement is defined by its truth value which is either true or false.
What is a proposition?
A statement that is either true or false.
How can propositions be chained together?
Propositions can be chained together via connectives.
Greeks carry swords OR javelins.
G IMPLIES (S OR J)
What are propositions truth values?
Each of the propositions is assigned a truth value.
V(P) evaluates the proposition P i.e. returns its truth value.
What are the connectives
In propositional logic, relationships between propositions are represented by connectives.
NOT (Negation), AND (Conjugation), OR (Disjunction), If…Then (Conditional), If and only if (Biconditional).
Describe Negation connective
Symbol: ¬
Description: NOT
Describe Conjugation connective
Symbol: /\
Description: AND
Describe Disjunction connective
Symbol: \/
Description: OR
Describe Conditional connective
Symbol: —>
Description: If…Then
Describe Biconditional connective
Symbol:
Description: If AND ONLY IF
What are the truth tables?
Truth tables are a way of visualizing the truth values of propositions.
What is the Negation truth table?
For any proposition P NOT(P) implies false
P | ¬P |
| T | F |
| F | T |
What is the Conjugation truth table?
Evaluates to true if both of the propositions are true.
| P | Q | P /\ Q | | F | F | F | | F | T | F | | T | F | F | | T | T | T |
What is Disjunction truth table?
Evaluates to true if either of the propositions are true.
| P | Q | P \/ Q | | F | F | F | | F | T | T | | T | F | T | | T | T | T |
What is Conditional truth table?
Evaluates to false only if Q is false when P is true.
| P | Q | P ---> Q | | F | F | T | | F | T | T | | T | F | F | | T | T | T |
What is Biconditional truth table?
Evaluates to true if both propositions are consistent
| P | Q | P Q | | F | F | T | | F | T | F | | T | F | F | | T | T | T |
What is a predicate?
A proposition with variables. If predicate is true depends on the value of the variables.
P(x,y) = [x+2=y]
P(1,3) is T
P(1,4) is F
What are the quantifier symbols
∀x - For all x
∃y - There exists some y
What is a set?
Unordered group of objects which are treated as a single object.
Give examples for sets
Set of real numbers: R
Set of complex numbers: C
Set of integers: Z
Set of positive integers: N
Empty set: ∅
{7, "Albert", pi/2, T}What are the properties of a Set?
The order of elements does not matter.
An element is either in or not in a set.
E.x. {7, pi/2, 7} = {7, pi/2}
Describe set membership?
X is a member of A: X∈A
Symbol for membership: ∈
Symbol for non-membership: ∉
What is a Power set?
A set containing all the subsets of another set
A = {B | B ⊆ A}
pow({T, F}) = {{T}, {F}, {T, F}, ∅}
What are the set operations
There are several useful operations one can use to combine, compare, analyze sets.
Describe Union set operations
Elements that are both in A and B
A∪B = {x | x ∈ A OR x ∈ B}
{1, 2, 3} ∪ {3, 4, 5} = {1, 2, 3, 4, 5}
Describe Intersection set operation
Elements that are in A and B
A∩B = {x | x ∈ A AND x ∈ B}
Describe Difference (relative complement) set operation
A-B = {x | x ∈ A AND x ∉ B}
Describe Complement set operation
The set of all elements that are not in A
¬A = D-A = {x | x ∈ A}
What is binary relation?
Association of elements of one set called domain with the elements of another set called codomain.
Jason —–> (6.042, 6.012)
Joan —–> (6.003)
Yihui —–> (6.012)
Adam —–> ()
Jason is registered for 6.042 notation:
Jason R 6.042 –> infix notation
R(Jason, 6.042) –> prefix notation
(Jason, 6.042) ∈ R | –> suffix notation
(Jason, 6.042) ∈ graph(R) |
What is a function?
A function is a relation for which each value from the Domain is associated with exactly one value from the codomain.
In other words a function is:
A function is an equation for which any x that can be plugged into the equation will yield exactly one y out of the equation.
What is mathematical image?
In mathematics an image is the subset of a function’s codomain which is the output of the function from a subset of it’s domain.
Evaluating a function at each element of a subset X of the domain, produces a set called the image of X.
If x is a member of X, then f(x) = y (the value of f when applied to x) is the image of x under f. y is alternatively known as the output of f for argument x.
R(Jason) = {6.042, 6.012}
R - function
Jason - element X
{6.042, 6.012} - image of X(Jason) under R(relation)
What is reverse binary relation?
If we have 2 sets domain and codomain reverse switches domain and codomain.
What is inverse mathematical image (R^(-1))?
If we have 2 sets domain and codomain reverse switches domain and codomain.
R^(-1)(6.012) = {Jason, Yihui}
R^(-1)({6.012, 6.003}) = {Jason, Joan, Yihui}
Describe partial function relational mapping properties
One or less arrows out from every element.
One or less elements of the domain associates with 1 or less elements from the codomain.
o -------->+ o -------->+ o + o--------->+ o + o--------->+
Describe total function relational mapping properties
Exactly one arrow out from every element
Every element of the domain associates with one or less elements from the codomain.
\+
o -------->+
o -------->+
o -------->+
o--------->+
o--------->+
o--------->+
\+
Describe total relation relational mapping properties
One or more arrows out from every element.
Every element of the domain associates with 1 or more elements of the codomain.
\+
o -------->+
o -------->+ +
o -------->+
o--------->+ + +
o--------->+
o--------->+ + + +
\+
Describe surjection relational mapping properties
One or more arrows in for every element.
Every element in codomain is associated with some elements of domain.
o o -------->+ o o -------->+ + o o--------->+ + o--------->+ o
Describe injection relational mapping properties
One or less arrows in for every element
One or less elements from the domain associates with one or less elements from codomain
o + o ------\->+ o |>+ o -------->+ o + o-------\->+ o--------|>+
Describe bijection relational mapping properties
It is a total function that is an injection and a surjection.
o -------->+ o -------->+ o--------->+ o--------->+ o--------->+
What is Mathematical induction?
Fundamental proof technique. It is especially useful when proving that statement is true for all positive integers.
What is Induction statement?
Given a statement P(n) that depends on a positive integer n and you have to prove that this statement holds for positive integers.
Step 1: Prove that P(k) is true
k = starting value of the statement
Step 2: Prove that P(k+1) is true.
What is a Finite State Machine?
Mathematical model of computation.
It is an abstract machine that can be in exactly one of a finite number of states at any given time.
The FSM can change from one state to another in response to some external inputs.
What is FSM Transition?
The change from one state to another is called transition.
Give examples of FSM.
- Vending Machine - dispense products when the proper combination of coins is deposited.
- Elevators - Their sequence of stops is determined by the floors requested by the riders.
- Traffic Lights - which change sequence when cars are waiting.
- Combination locks - require the input of a combination of numbers in proper order.
What is a mathematical model of computation?
A model which describes how a set of outputs are computed given a set of inputs.
This model describes how unites of computations and communications are organized.
The computation complexity of an algorithm can be measured given a model of computation.
What is a regular language in terms of FSM?
Language that can be expressed with a State Machine.
What is a language in terms of FSM?
Set of strings which are made up of characters from a specified alphabet or set of symbols.
What are the usage of regular languages in terms of FSM?
They are useful to recognize patterns in data and group certain computational problems together. Once this is done they can take similar approaches to solve the problems, grouped together.
How a regular language can be generated?
A FSM M describes a given language L. M is said to ACCEPT a string W if the machine starts in a start state, undergoes some series of state transitions, and ends up in accepting state. We say that the machine M RECOGNIZES the language L if M ACCEPTS all strings W that are in L.
A language is a regular language if there is a FSM that recognizes it.
What are the types of FSM?
Deterministic and Non-deterministic
What are deterministic state machines?
There must be exactly one transition function for every input in the input alphabet from each state.
What are Non-deterministic state machine?
They are not required to have transition function for every symbol in the input alphabet and there can be multiple transition functions in the same state for the same symbol.
NFA’s can use null transitions which are indicated by ∈.
Null transitions allow the machine to jump from one state to another without having to read an input symbol.
What are the State Machine equivalence?
Non deterministic finite automata are equivalent to Deterministic finite automata and back.
- Every NDFA can be converted to DFA
- Every DFA can be converted to NDFA
What is the invariant principle?
Invariant is a quantity that remains constant during the execution of a given algorithm. In other words none of the allowed operations changes the value of the invariant.
Given a starting state S1 and a rule for transitions, invariants allow us to determine which states we can reach from S1.
