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 |