Brainscape's Knowledge GenomeTM

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


See full index

Discrete Math > 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

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

What are the truth tables?

A

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

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

What is the Negation truth table?

A

For any proposition P NOT(P) implies false

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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      |
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
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 a Finite State Machine?

A

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.

56
Q

What is FSM Transition?

A

The change from one state to another is called transition.

57
Q

Give examples of FSM.

A
  • 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.
58
Q

What is a mathematical model of computation?

A

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.

59
Q

What is a regular language in terms of FSM?

A

Language that can be expressed with a State Machine.

60
Q

What is a language in terms of FSM?

A

Set of strings which are made up of characters from a specified alphabet or set of symbols.

61
Q

What are the usage of regular languages in terms of FSM?

A

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.

62
Q

How a regular language can be generated?

A

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.

63
Q

What are the types of FSM?

A

Deterministic and Non-deterministic

64
Q

What are deterministic state machines?

A

There must be exactly one transition function for every input in the input alphabet from each state.

65
Q

What are Non-deterministic state machine?

A

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.

66
Q

What are the State Machine equivalence?

A

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

Discrete Math (2 decks)

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