Module 2

Question 1

What is predicate calculus?

Answer 1

The symbolic analysis of predicates and quantified statements.

Question 2

What is statement calculus?

Answer 2

The symbolic analysis of ordinary compound statements.

Question 3

What is a predicate?

Answer 3

A sentence the contains a finite number of variables and becomes a statement when specific values are substituted for variables.

Question 4

What is the predicate domain?

Answer 4

The set of all values that may be substituted in place of the variable.

Question 5

What is the truth set?

Answer 5

The set of all elements that make the predicate true.

Question 6

How is the truth set denoted?

Answer 6

{x E D | P(x)}

Question 7

What is a quantified?

Answer 7

A word that refers to a quantity such as “some” or “all” and tell for how many elements a given predicate is true.

Question 8

What is the universal quantifier?

Answer 8

Upside down A, means “for all”

Question 9

What can be used instead of “for all”?

Answer 9

“For arbitrary”
“For every”
“For any”
“For each”
“Given any”

Question 10

When are universal statements true?

Answer 10

True if, and only if, it is true for every x in its domain.

Question 11

What is the method of exhaustion?

Answer 11

Showing the truth of the predicate separately for each individual element in the domain.

Question 12

What is the existential qualifier?

Answer 12

Backwards E, denotes “there exists”

Question 13

What can be used instead of “there exists”?

Answer 13

“There is a”
“We can find a”
“There is at least one”
“For some”
“For at least we one”

Question 14

When are existential statements true?

Answer 14

True if, and only if, the predicate is true for at least one value in the domain.

Question 15

What form does a universal conditional statement have?

Answer 15

Ax, if P(x) then Q(x)

Question 16

What is implicit quantification?

Answer 16

P(x) => Q(x), every element in the truth set of P(x) is in Q(x).

Question 17

What does P(x) <=> Q(x) mean?

Answer 17

P(x) and Q(x) have identical truth sets.

Question 18

What is the negation of a universal statement?

Answer 18

It is logically equivalent to an existential statement saying there is one value that is the negation of the predicate.

Question 19

What is the negation of an existential statement?

Answer 19

It is logically equivalent to a universal statement with the negation if the predicate.

Question 20

When is an integer even?

Answer 20

If, and only if, n=2*(some integer)

Question 21

When is an integer odd?

Answer 21

If, and only if, n=(2*(some integer))+1

Question 22

When is an integer prime?

Answer 22

If, and only if: n>1, for all positive integers r and s, if n=rs, and r or s =n.

Question 23

When is an integer composite?

Answer 23

If, and only if: n>1, for all positive integers r and s, n=rs with 1

Question 24

What is a constructive proof of existence?

Answer 24

Find a value in the domain to prove the predicate is true or provide instructions for finding such a value.

Question 25

What is a nonconstructive proof of existence?

Answer 25

Show either: (a) that the existence of a value of x that makes the predicate the predicate true is guaranteed by an axiom or theorem (b) that the assumption that there is no such x leads to a contradiction.

Question 26

What is a disproof by counterexample?

Answer 26

To disprove a statement by finding a value of x for which the statement is false.

Question 27

What is the method of generalizing from the generic particular?

Answer 27

To show that every element of a set satisfies a certain property, suppose x is a particular but arbitrarily chosen element of the set, and show that x satisfies the property.

Question 28

What is the method of direct proof?

Answer 28

1. Express statement in quantifiable terms. 2. Utilize method of generalizing from the generic particular. 3. Show conclusion is true by using definitions, previous results, and logical inference.

Question 29

What is existential instantiation?

Answer 29

If the existence of a certain kind of object is assumed or has been deduced then it can be given a name, as long as that name is not currently being used to denote something else.

Question 30

What is a corollary?

Answer 30

A statement whose truth can be immediately deduced from a theorem that has already been proven.

Question 31

What is the definition if divisibility?

Answer 31

If n and d are integers and d =/=0, n is divisible by d if, and only if, n=d*(some integer)

Question 32

What are the two rules of divisibility?

Answer 32

1) if one positive integer divides another positive integer, then the first is less than or equal to the second. 2) only divisors of 1 are 1 and -1

Question 33

What is the method of proof by division if cases?

Answer 33

If many cases are presented for the same conclusion, separating them out individually

Question 34

What is the method of proof by contraposition?

Answer 34

1. Express statement to be proved in form: Ax in D, if P(x) then Q(x) 2. Rewrite as contrapositive: Ax in D, if Q(x) is false then P(x) is false 3. Probe contrapositivity by direct proof.