Page 131 - Discrete Mathematics and Its Applications

110 1 / The Foundations: Logic and Proofs

p ∧ q (conjunction of p and q): the proposition “p and q,” argument form: a sequence of compound propositions involv-
which is true if and only if both p and q are true ing propositional variables
p ⊕ q (exclusive or of p and q): the proposition “p XOR q,” premise: a statement, in an argument, or argument form, other
which is true when exactly one of p and q is true than the final one
p → q (p implies q): the proposition “if p, then q,” which is conclusion: the final statement in an argument or argument
false if and only if p is true and q is false form
converse of p → q: the conditional statement q → p valid argument form: a sequence of compound propositions
contrapositive of p → q: the conditional statement ¬q →¬p involving propositional variables where the truth of all the
premises implies the truth of the conclusion
inverse of p → q: the conditional statement ¬p →¬q valid argument: an argument with a valid argument form
p ↔ q (biconditional): the proposition “p if and only if q,” rule of inference: a valid argument form that can be used in
which is true if and only if p and q have the same truth the demonstration that arguments are valid
value fallacy: an invalid argument form often used incorrectly as a
bit: eithera0ora1 rule of inference (or sometimes, more generally, an incor-
Boolean variable: a variable that has a value of 0 or 1 rect argument)
bit operation: an operation on a bit or bits circular reasoning or begging the question: reasoning where
bit string: a list of bits one or more steps are based on the truth of the statement
bitwise operations: operations on bit strings that operate on being proved
each bit in one string and the corresponding bit in the other theorem: a mathematical assertion that can be shown to be
string true
logic gate: a logic element that performs a logical operation conjecture: a mathematical assertion proposed to be true, but
on one or more bits to produce an output bit that has not been proved
logic circuit: a switching circuit made up of logic gates that
proof: a demonstration that a theorem is true
produces one or more output bits
axiom: a statement that is assumed to be true and that can be
tautology: a compound proposition that is always true
used as a basis for proving theorems
contradiction: a compound proposition that is always false lemma: a theorem used to prove other theorems
contingency: a compound proposition that is sometimes true corollary: a proposition that can be proved as a consequence
and sometimes false
of a theorem that has just been proved
consistent compound propositions: compound propositions
vacuous proof: a proof that p → q is true based on the fact
for which there is an assignment of truth values to the vari-
that p is false
ables that makes all these propositions true
trivial proof: a proof that p → q is true based on the fact that
satisfiable compound proposition: a compound proposition
q is true
for which there is an assignment of truth values to its vari-
direct proof: a proof that p → q is true that proceeds by show-
ables that makes it true
ing that q must be true when p is true
logically equivalent compound propositions: compound
propositions that always have the same truth values proof by contraposition: a proof that p → q is true that pro-
predicate: part of a sentence that attributes a property to the ceeds by showing that p must be false when q is false
subject proof by contradiction: a proof that p is true based on the
propositional function: a statement containing one or more truth of the conditional statement ¬p → q, where q is a
variables that becomes a proposition when each of its vari- contradiction
ables is assigned a value or is bound by a quantifier exhaustive proof: a proof that establishes a result by checking
a list of all possible cases
domain (or universe) of discourse: the values a variable in a
propositional function may take proof by cases: a proof broken into separate cases, where these
∃xP(x) (existential quantification of P(x)): the proposition cases cover all possibilities
that is true if and only if there exists an x in the domain withoutlossofgenerality:anassumptioninaproofthatmakes
such that P(x) is true it possible to prove a theorem by reducing the number of
∀xP(x) (universal quantification of P(x)): the proposition cases to consider in the proof
that is true if and only if P(x) is true for every x in the counterexample: an element x such that P(x) is false
domain constructive existence proof: a proof that an element with a
logically equivalent expressions: expressions that have the specified property exists that explicitly finds such an ele-
same truth value no matter which propositional functions ment
and domains are used nonconstructive existence proof: a proof that an element with
free variable: a variable not bound in a propositional function a specified property exists that does not explicitly find such
an element
bound variable: a variable that is quantified rational number: a number that can be expressed as the ratio
scope of a quantifier: portion of a statement where the quan- of two integers p and q such that q = 0
tifier binds its variable uniqueness proof: a proof that there is exactly one element
argument: a sequence of statements satisfying a specified property