Proofs

Question 1

proposition

Answer 1

a statement that is either true or false

Question 2

predicate

Answer 2

a proposition whose truth depends on the value of one or more variables

Question 3

axiom

Answer 3

a proposition that is simply accepted as true

Question 4

proof

Answer 4

a sequence of logical deductions from axioms and previously proved statements that concludes with the proposition in question

Question 5

theorem

Answer 5

an important true proposition

Question 6

lemma

Answer 6

a preliminary proposition useful for proving later propositions

Question 7

corollary

Answer 7

a proposition that follows in just a few logical steps from a theorem

Question 8

What is a proposition of the form “IF P, THEN Q” called?

Answer 8

implication

“IF P, THEN Q” is the general form of an implication and is often written as “P IMPLIES Q.” Thus, given specific P and Q, “P IMPLIES Q.” is itself a proposition and can be either true or false.

Question 9

A fundamental inference rule says:

“P IMPLIES Q.”
___________
Q

What is this inference rule called?

Answer 9

Modus Ponens

Question 10

What is the statement above the line of an implication called?

Answer 10

predicate

Question 11

What is the statement below the line of an implication called?

Answer 11

the conclusion or the consequent

Question 12

Proving a proposition’s contrapositive is as good as (and sometimes easier than) proving the proposition itself. Which of the following is logically equivalent to the contrapositive of “P IMPLIES Q.”

Answer 12

NOT(Q) IMPLIES NOT(P)

Question 13

At the end of a proof, it is customary begin a proof with ___ and then to write down either the delimiter _____ or the symbol _____.

Answer 13

A proof should begin with “Proof by …” and end with “QED” or a square symbol

Question 14

What is Proof by Contradiction

Answer 14

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

Question 15

What is Proof by Cases?

Answer 15

Reasoning by cases breaks a complicated problem into easier subproblems

Question 16

Based on the video and slides, when might we want to prove by cases?

Answer 16

Proof by cases might be used when:

(1) a complicated proof could be broken into cases
(2) where each case is simpler to prove and
(3) the cases together cover all possibilities

Question 17

What is the well ordering principle?

Answer 17

Every nonempty set of nonnegative integers has a least element.

Question 18

What is DeMorgan’s Law

Answer 18

When P and Q are true

NOT(P or Q) is equivalent to NOT(P) and NOT(Q)

Question 19

How does Proof by Truth table work?

Answer 19

It verifies a proof by confirming you get the same truth value in all possible environments.

Question 20

“valid” formula (or a tautology)

Answer 20

if and only if it’s true in all environments. No matter what you set the variables to, it’s going to come out to be true.

Question 21

satisfiable formula

Answer 21

So a formula is satisfiable if and only if it’s true in some environment.

Question 22

The equivalence of two propositional formulas could be proved by comparing their _____, notably the _____ column.

Answer 22

truth tables, final

Question 23

A rule is _____ an assignment of truth values that makes all antecedents true the consequent is _____.

Answer 23

sound, valid

Question 24

Godel’s Completeness Theorem

Answer 24

The good news theorem: you only need to know a few axioms & rules to prove all valid formulas (in theory; in practice, you need to know lot of rules on how to apply theorem)

Question 25

What is the second meta-theorem regarding Predicate Calculas

Answer 25

(Predicate Calculus) there is no procedure to determine whether a quantified formula is valid (in contrast to propositional formulas).

Question 26

We have a procedure to fix any problem.
If the range of “p” is the set of procedures and “i” is in the set of issues, pick the quantifiers that complete the statement.

___. p fixes i

Answer 26

All i exists p

Question 27

Set

Answer 27

informally: a set is a collection of mathematical objects, and the idea is that you treat the collection of objects as one new object.
e. g’s of sets include real numbers, complex numbers, integers, and an empty set

Question 28

set-theoretic equality

Answer 28

A intersection ( B union C) = (A intersection B) union ll(A union C)

Question 29

Binary relations

Answer 29

A binary relation is a mathematical object that associates elements of one set called the domain with elements of another set called the codomain.

Question 30

The range of a relation is:

Answer 30

Equal to or smaller than the codomain

Question 31

A total injection has _____ arrows out of each element in the domain

Answer 31

greater than or equal to 1
&
less than or equal to 1

Question 32

surjective binary relation

Answer 32

There is greater than or equal to 1 arrow in to every element of B

Question 33

Function (binary relation)

Answer 33

There’s less than or equal to 1 arrow out of every element of A, that’s what function means.

Question 34

What are the mapping lemmas for the size/relation for finite binary relations the codomains for bijection, surjection, and injection

Answer 34

A bij B IFF |A| = |B|
A surj B IFF |A| >= |B|
A inj B IFF |A| <= |B|

Question 35

Schroeder-Bernstein theorem

Answer 35

A surj B surj A IMPLIES A bij B

Question 36

for finite sets A and B, A inj B is the equivalent to:

Answer 36

There exists a total injective relation from A to B

There exists a surjective function from B to A

There exists a bijection from A to some subset of B

|A| <= |B|

Question 37

A relation R from a set A to a set B is total iff

Answer 37

R^-1(B) = A

R is (>= 1) - out

(see 1.7 Binary relations for more info)

Question 38

total relation

Answer 38

Total relation means there’s at least one arrow out every domain element.

Another way to say total is to say that if you look at the inverse image of the codomain, it is equal to the domain.

A = R-1 (B)

R is (>=1) - out

Question 39

surjection (relational mappings)

Answer 39

At least one arrow into every point in the codomain.

In other words, every value in the co domain is mapped to a value within the domain.

In terms of set operations that R is a surjection if and only if the image of the domain is the codomain.

R surj B iff R(A) = B

Question 40

injections (relational mappings)

Answer 40

an injection is a relation where there is at most one arrow into every element in the codomain.

Question 41

R is an injection iff R^-1 is

Answer 41

a function

Question 42

R is a bijection iff R^-1 is

Answer 42

a bijection

Question 43

R is a surjection iff R^-1 is

Answer 43

total

Question 44

R is a function iff R^-1 is

Answer 44

an injection

Question 45

what is the template for an induction proof

Answer 45

Proof: (by induction on n)

The induction hypothesis, P(n)

Question 46

Floyd’s Invariant Principle

Answer 46

if you have a property that you begin with, and it doesn’t change making a step, it’s never going to change. And that’s all that Floyd’s invariant principle states.

We use preserved invariance to prove that a property is true in all states. It’s a methodology.