Chapter 1 Flashcards
premise
the statement(s) preceding the conclusion
nested quantifier
one quantifier is within the scope of another
E!xP(x)
unique quantification of P(x)
“there exists only one”
unsatisfiable
when the compound proposition is false for all assignments of truth values to its propositional variables (contradiction)
satisfiable
if there is an assignment of truth values to its propositional variables that makes the compound proposition true (tautology or contingency)
tautology
a compound proposition that is always true, no matter what the truth values of its propositional variables are
precedence rules
existential/ universal, negation, conjunction, disjunction, conditional, biconditional
atomic proposition
a proposition that cannot be expressed in terms of simpler propositions
truth values
true or false
propositional variables
variables that represent propositions
proposition
a statement that is either true or false, not both
proof by contradiction
formal proof
all steps are supplied and the rules for each step in the argument is given
!p
negation of p
the truth value of !p is the opposite of p
“not p”
p <–> q
biconditional statement
true when both p and q have the same truth value and false otherwise
“p if and only if q”
p XOR q
exclusive or
true when only one proposition is true and false otherwise
“p or q, not both”
p || q
disjunction of p and q
false when both p and q are false and true otherwise
“p or q”
p && q
conjunction of p and q
true when both p and q are true and false otherwise
“p and q”
ExP(x)
existential quantification of P(x)
“there exists”
AxP(x)
universal quantification of P(x)
“for all”
“for each”
p == q
logically equivalent
compound propositions that have the same truth values in all cases
(if p <–> q is a tautology)
theorem
a statement that has been proven to be true
lemma
a less important theorem that is helpful in the proof of other results
definition of an even number
the integer n is even if there exists an integer k, such that n = 2k
definition of an odd number
the integer n is odd if there exists an integer k, such that n = 2k - 1
proof by contraposition
p –> q
conditional statement
false when p is true and q is false, and true otherwise
“if p, then q”
p is the hypothesis
q is the conclusion
compound proposition
the combination of one or more propositions to form new propositions using logical operators
contradiction
a compound proposition that is always false, regardless of the truth values of its propositional variables
solution
when a particular assignment of truth values makes the compound proposition true
postconditions
the statements that the output should satisfy
domain of discourse
asserts that a property is true for all values of a variable in a particular set of values
definition of a rational number
the real number r is rational if there exists integers p and q, where q != 0, such that r = p / q
counterexample
an element for which P(x) is false is a counterexample of AxP(x)
informal proof
more than one rule of inference may be used in each step, the axioms being assumed and the rules of inference used are not explicitly stated
argument form
a sequence of compound propositions involving propositional variables
clause
a disjunction of variables or the negations of these variables
contingency
a compound proposition that is neither a tautology nor a contradiction
q –> p
converse of p –> q
false when p is false and q is true
!p –> !q
inverse of p –> q
false when p is false and q is true
!q –> !p
contrapositive of p –> q
false when p is true and q is false
predicate
refers to a property that the subject of the statement can have
P(x), where P denotes the predicate
preconditions
the statements that describe valid input
quantification
expresses the extent to which a predicate is true over a range of values
argument
a sequence of statements that end with a conclusion
valid
the conclusion must follow from the truth of the preceding statements
fallacies
common forms of incorrect reasoning that lead to invalid arguments
conjecture
a statement that is being proposed as true
corollary
a theorem that can be established directly from a theorem that has been proven
axioms
also called postulates
statements we assume to be true
proof
a valid argument that establishes the truth of a theorem
