Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Math for CS A > Proofs Theory > Flashcards

Proofs Theory Flashcards

Theory for mathematical proofs.

1
Q

What is a proof?

A

Logical argument that establishes beyond any doubt that something is true.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are everyday types of reasoning?

A

Inductive and Deductive reasoning

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is inductive reasoning?

A

Drawing a conclusion from what we see around us.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Give example for Inductive reasoning?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is deductive reasoning?

A

Starting from a general statement that you know for sure is true and drawing conclusions from there.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Give example for deductive reasoning?

A

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).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is Axiom?

A

A statement or proposition which is regarded as being established accepted or self evidently true.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is direct proof?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What are the steps of direct proof?

A
  • 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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is proof by contradiction?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is the description of proof by contradiction?

A

If an assertion implies something false then the assumption itself must be false.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is The Well-Ordering principle?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is propositional logic?

A

Branch of mathematical logic which studies the logical relationships between propositions taken as a whole and connected via logical connectives.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

How propositional logic can be represented?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is a proposition?

A

A statement that is either true or false.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

How can propositions be chained together?

A

Propositions can be chained together via connectives.
Greeks carry swords OR javelins.

G IMPLIES (S OR J)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What are propositions truth values?

A

Each of the propositions is assigned a truth value.

V(P) evaluates the proposition P i.e. returns its truth value.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What are the connectives

A

In propositional logic, relationships between propositions are represented by connectives.

NOT (Negation), AND (Conjugation), OR (Disjunction), If…Then (Conditional), If and only if (Biconditional).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Describe Negation connective

A

Symbol: ¬
Description: NOT

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Describe Conjugation connective

A

Symbol: /\
Description: AND

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Describe Disjunction connective

A

Symbol: \/
Description: OR

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Describe Conditional connective

A

Symbol: —>
Description: If…Then

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Describe Biconditional connective

A

Symbol:
Description: If AND ONLY IF

24
Q

What are the truth tables?

A

Truth tables are a way of visualizing the truth values of propositions.

25
Q

What is the Negation truth table?

A

For any proposition P NOT(P) implies false

P | ¬P |
| T | F |
| F | T |

26
Q

What is the Conjugation truth table?

A

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      |
27
Q

What is Disjunction truth table?

A

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      |
28
Q

What is Conditional truth table?

A

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         |
29
Q

What is Biconditional truth table?

A

Evaluates to true if both propositions are consistent

|  P  |  Q  |  P  Q  |
|  F  |  F   |       T         |
|  F  |  T   |       F         |
|  T  |  F   |       F         |
|  T  |  T   |       T         |
30
Q

What is a predicate?

A

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

31
Q

What are the quantifier symbols

A

∀x - For all x

∃y - There exists some y

32
Q

What is a set?

A

Unordered group of objects which are treated as a single object.

33
Q

Give examples for sets

A 
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}
34
Q

What are the properties of a Set?

A

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}

35
Q

Describe set membership?

A

X is a member of A: X∈A

Symbol for membership: ∈
Symbol for non-membership: ∉

36
Q

What is a Power set?

A

A set containing all the subsets of another set

A = {B | B ⊆ A}

pow({T, F}) = {{T}, {F}, {T, F}, ∅}

37
Q

What are the set operations

A

There are several useful operations one can use to combine, compare, analyze sets.

38
Q

Describe Union set operations

A

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}

39
Q

Describe Intersection set operation

A

Elements that are in A and B

A∩B = {x | x ∈ A AND x ∈ B}

40
Q

Describe Difference (relative complement) set operation

A

A-B = {x | x ∈ A AND x ∉ B}

41
Q

Describe Complement set operation

A

The set of all elements that are not in A

¬A = D-A = {x | x ∈ A}

42
Q

What is binary relation?

A

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) |

43
Q

What is a function?

A

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.

44
Q

What is mathematical image?

A

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)

45
Q

What is reverse binary relation?

A

If we have 2 sets domain and codomain reverse switches domain and codomain.

46
Q

What is inverse mathematical image (R^(-1))?

A

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}

47
Q

Describe partial function relational mapping properties

A

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--------->+
48
Q

Describe total function relational mapping properties

A

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--------->+
               \+
49
Q

Describe total relation relational mapping properties

A

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--------->+ + + +
               \+
50
Q

Describe surjection relational mapping properties

A

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
51
Q

Describe injection relational mapping properties

A

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--------|>+
52
Q

Describe bijection relational mapping properties

A

It is a total function that is an injection and a surjection.

o -------->+
o -------->+
o--------->+ 
o--------->+
o--------->+
53
Q

What is Mathematical induction?

A

Fundamental proof technique. It is especially useful when proving that statement is true for all positive integers.

54
Q

What is Induction statement?

A

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.

55
Q

What is the invariant principle?

A

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.

Math for CS A (2 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions