Module 2 Flashcards

1
Q

What is predicate calculus?

A

The symbolic analysis of predicates and quantified statements.

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

What is statement calculus?

A

The symbolic analysis of ordinary compound statements.

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

What is a predicate?

A

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

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

What is the predicate domain?

A

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

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

What is the truth set?

A

The set of all elements that make the predicate true.

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

How is the truth set denoted?

A

{x E D | P(x)}

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

What is a quantified?

A

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

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

What is the universal quantifier?

A

Upside down A, means “for all”

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

What can be used instead of “for all”?

A
“For arbitrary”
“For every”
“For any”
“For each”
“Given any”
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

When are universal statements true?

A

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

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

What is the method of exhaustion?

A

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

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

What is the existential qualifier?

A

Backwards E, denotes “there exists”

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

What can be used instead of “there exists”?

A
“There is a”
“We can find a”
“There is at least one”
“For some”
“For at least we one”
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

When are existential statements true?

A

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

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

What form does a universal conditional statement have?

A

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

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

What is implicit quantification?

A

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

17
Q

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

A

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

18
Q

What is the negation of a universal statement?

A

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

19
Q

What is the negation of an existential statement?

A

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

20
Q

When is an integer even?

A

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

21
Q

When is an integer odd?

A

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

22
Q

When is an integer prime?

A

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

23
Q

When is an integer composite?

A

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

24
Q

What is a constructive proof of existence?

A

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

25
Q

What is a nonconstructive proof of existence?

A

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.

26
Q

What is a disproof by counterexample?

A

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

27
Q

What is the method of generalizing from the generic particular?

A

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.

28
Q

What is the method of direct proof?

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

What is existential instantiation?

A

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.

30
Q

What is a corollary?

A

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

31
Q

What is the definition if divisibility?

A

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

32
Q

What are the two rules of divisibility?

A

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

33
Q

What is the method of proof by division if cases?

A

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

34
Q

What is the method of proof by contraposition?

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