definitions Flashcards
a divides b
there is a natural number k such that b = ak
a natural number p is prime if…
p is greater than 1 and the only numbers that divide p are 1 and p
a natural number that is COMPOSITE is…
neither 1 nor prime
For f(a) = b, the image is…
b
For f(a) = b, the pre-image is…
a
a proposition is
a sentence that has exactly one truth value, either T or F
the negation of a proposition P
is the proposition “not P”, which is true when P is false
given propositions P and Q, the conjunction of P and Q is true when…
both P and Q are true
given propositions P and Q, the disjunction of and Q is true when…
exactly at least one of P or Q is true
a tautology is…
a propositional form that is true for every assignment of truth values to its components
(ex. P∨~P)
a contradiction is…
a propositional form that is false for every assignment of truth values to its components
(ex. P∧~P)
two propositional forms are equivalent if…
they have the same truth tables
a denial of any proposition P is
any proposition equivalent to ~P (ex. ~~~P)
the conditional sentence, “if P, then Q” is true if…
P is false or Q is true
the conditional sentence, “if P then Q” is false if…
P is true and Q is false
the converse of P⇒Q is
Q⇒P
the contrapositive of P⇒Q
~Q ⇒ ~P
T or F: a statement and its converse are always equivalent
F
T or F: a statement and its contrapositive are equivalent
T
for propositions P and Q, the biconditional statement is…
the statement “P if and only if Q”
a biconditional sentence is true when
P and Q have the same truth values
open sentence
a sentence that contains variables, becomes a proposition when its variables are assigned specific values
truth set
the collection of objects that may be substituted to make an open sentence a true proposition
universe of discourse
the collection of objects that are available for consideration, often number systems ℂ, ℕ, ℚ, ℝ, ℤ
two open sentences are equivalent when…
they have the same truth set
T or F: the sentence (∃x)P(x) is always true
F, only true if P(x) is nonempty
T or F: (∀x)P(x) is always true
F, only true if the truth set of P(x) is the entire universe
two quantified statement are equivalent in a given universe if
they have the same truth value in that universe
two quantified statements are equivalent if
they are equivalent in every universe
(∃!x) P(x) is true when
the truth set of P(x) has exactly one element
theorem
a statement that describes a pattern or relationship among quantities or structures
a proof of a theorem is
a justification of the truth of the theorem that follows the principles of logic
axioms (or postulates)
a set of statement that are assumed to be true
in any proof at any time you may…
state an axiom, an assumption, or a previously proven result;
use the tautology rule;
use the replacement rule;
use a definition to state an equivalent to a statement earlier in the proof;
modus ponens rule
tautology rule
can state a sentence whose symbolic translation is a tautology
replacement rule
state a sentence equivalent to any statement earlier in the proof
lemma
a result that serves as a preliminary step, “stepping stone” to final result
modus ponens rule
after statements P and P⇒Q appear, state Q
direct proof of P⇒Q
assume P… therefore Q
Thus, P⇒Q
proof of P⇒Q by contrapositive
assume ~Q…
therefore ~P
thus ~Q⇒~P
therefore P⇒Q
when would you use proof by CP?
statements of either p and Q is negation or the connection berween denials is easier to understand
proof of P by contradiction
suppose ~P…
therefore Q…
therefore ~Q.
hence Q∧~Q is a contradiction
thus P
when might you use to do a proof by contradiction?
to prove any proposition P since direct proofs and proofs by CP can only be used for conditionals, proof by contradiction can also be use for conditionals
direct proof of (∀x) P(x)
let x be an arbitrary object in the universe…
hence P(x) is true.
therefore, (∀x) P(x) is true
proof of (∀x) P(x) by contradiction
suppose ~(∀x) P(x)
then (∃x)~P(x)
let t be an object such that ~P(t)…
therefore Q∧~Q which is a contradiction
thus (∃x)~P(x) is false so (∀x) P(x) is true
constructive proof of (∃x)P(x)
specify one particular object a
if necessary verify that a is in the universe…
therefore, P(a) is true.
thus, (∃x)P(x)
indirect proof of (∃x)P(x)
… therefore there must be an object a such that P(a) is true.
therefore (∃x)P(x) is true
proof of (∃x)P(x) by contradiction
suppose ~(∃x)P(x)
then (∀x) ~P(x)…
therefore ~Q∧Q which is a contrdiction
thus ~(∃x)P(x) is false
therefore, (∃x)P(x) is true
