Proofs Theory Flashcards

Question

What is the Negation truth table?

Answer 1

For any proposition P NOT(P) implies false | P | ¬P | | T | F | | F | T |

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

Evaluates to true if both propositions are consistent ``` | P | Q | P Q | | F | F | T | | F | T | F | | T | F | F | | T | T | T | ```

Answer 6

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

Answer 7

∀x - For all x | ∃y - There exists some y

Answer 8

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

Answer 9

``` 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} ```

Answer 10

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}

Answer 11

X is a member of A: X∈A Symbol for membership: ∈ Symbol for non-membership: ∉

Answer 12

A set containing all the subsets of another set A = {B | B ⊆ A} pow({T, F}) = {{T}, {F}, {T, F}, ∅}

Answer 13

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

Answer 14

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}

Answer 15

Elements that are in A and B A∩B = {x | x ∈ A AND x ∈ B}

Answer 16

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

Answer 17

The set of all elements that are not in A ¬A = D-A = {x | x ∈ A}

Answer 18

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

Answer 19

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.

Answer 20

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)

Answer 21

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

Answer 22

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}

Answer 23

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--------->+ ```

Answer 24

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--------->+ + ```

Answer 25

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--------->+ + + + + ```

Answer 26

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

Answer 27

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--------|>+ ```

Answer 28

It is a total function that is an injection and a surjection. ``` o -------->+ o -------->+ o--------->+ o--------->+ o--------->+ ```

Answer 29

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

Answer 30

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.

Answer 31

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.

Answer 32

The change from one state to another is called transition.

Answer 33

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

Answer 34

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.

Answer 35

Language that can be expressed with a State Machine.

Answer 36

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

Answer 37

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.

Answer 38

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.

Answer 39

Deterministic and Non-deterministic

Answer 40

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

Answer 41

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.

Answer 42

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

Answer 43

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.

Proofs Theory Flashcards

Theory for mathematical proofs.