Module 2 Flashcards
What is predicate calculus?
The symbolic analysis of predicates and quantified statements.
What is statement calculus?
The symbolic analysis of ordinary compound statements.
What is a predicate?
A sentence the contains a finite number of variables and becomes a statement when specific values are substituted for variables.
What is the predicate domain?
The set of all values that may be substituted in place of the variable.
What is the truth set?
The set of all elements that make the predicate true.
How is the truth set denoted?
{x E D | P(x)}
What is a quantified?
A word that refers to a quantity such as “some” or “all” and tell for how many elements a given predicate is true.
What is the universal quantifier?
Upside down A, means “for all”
What can be used instead of “for all”?
“For arbitrary” “For every” “For any” “For each” “Given any”
When are universal statements true?
True if, and only if, it is true for every x in its domain.
What is the method of exhaustion?
Showing the truth of the predicate separately for each individual element in the domain.
What is the existential qualifier?
Backwards E, denotes “there exists”
What can be used instead of “there exists”?
“There is a” “We can find a” “There is at least one” “For some” “For at least we one”
When are existential statements true?
True if, and only if, the predicate is true for at least one value in the domain.
What form does a universal conditional statement have?
Ax, if P(x) then Q(x)
What is implicit quantification?
P(x) => Q(x), every element in the truth set of P(x) is in Q(x).
What does P(x) <=> Q(x) mean?
P(x) and Q(x) have identical truth sets.
What is the negation of a universal statement?
It is logically equivalent to an existential statement saying there is one value that is the negation of the predicate.
What is the negation of an existential statement?
It is logically equivalent to a universal statement with the negation if the predicate.
When is an integer even?
If, and only if, n=2*(some integer)
When is an integer odd?
If, and only if, n=(2*(some integer))+1
When is an integer prime?
If, and only if: n>1, for all positive integers r and s, if n=rs, and r or s =n.
When is an integer composite?
If, and only if: n>1, for all positive integers r and s, n=rs with 1
What is a constructive proof of existence?
Find a value in the domain to prove the predicate is true or provide instructions for finding such a value.
What is a nonconstructive proof of existence?
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.
What is a disproof by counterexample?
To disprove a statement by finding a value of x for which the statement is false.
What is the method of generalizing from the generic particular?
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.
What is the method of direct proof?
- Express statement in quantifiable terms.
- Utilize method of generalizing from the generic particular.
- Show conclusion is true by using definitions, previous results, and logical inference.
What is existential instantiation?
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.
What is a corollary?
A statement whose truth can be immediately deduced from a theorem that has already been proven.
What is the definition if divisibility?
If n and d are integers and d =/=0, n is divisible by d if, and only if, n=d*(some integer)
What are the two rules of divisibility?
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
What is the method of proof by division if cases?
If many cases are presented for the same conclusion, separating them out individually
What is the method of proof by contraposition?
- Express statement to be proved in form: Ax in D, if P(x) then Q(x)
- Rewrite as contrapositive: Ax in D, if Q(x) is false then P(x) is false
- Probe contrapositivity by direct proof.
