Copyright © 2004, S. Marc Cohen Revised 5/31/04
Glossary-8
Prefix vs. infix notation: In prefix notation, the predicate or relation symbol precedes its arguments,
e.g., Larger(a, b). In infix notation, the relation symbol appears between its two arguments,
e.g., a = b.
Premise: A statement meant to support (lead us to accept) the conclusion of an argument.
Prenex form: An
FOL sentence is in prenex form when all its quantifiers are “out in front.” More
precisely, an
FOL sentence is in prenex form when it contains no quantifier that is preceded by
any symbol other than a quantifier. Thus, ∀x ∃y (F(x) → R(x, y)) and Cube(a) are both in
prenex form. (The second example may seem surprising, but since it contains no quantifiers at
all, it contains no quantifier that is preceded by any other symbol, and so counts as being in
prenex form.) On the other hand, ∀x (F(x) → ∃y R(x, y)) and ∀x ¬∃y R(x, y) are not in prenex
form. Every
FOL sentence is equivalent to some sentence in prenex form.
Presupposition: The presuppositions of a sentence S are those conditions that must be fulfilled in order
for S to have a truth value, i.e., in order for S to make any claim at all. Whereas Russell’s theory
of descriptions holds that a sentence of the form the F is G logically implies that there exists an
F, Strawson’s theory contends that such sentences presuppose the existence of an F, rather than
logically imply it. So whereas Russell says that if nothing is F, the sentence the F is G is false,
Strawson maintains that in this case the sentence is neither true nor false.
Proof by cases: A proof strategy that consists in proving some statement S from a disjunction by
proving S from each disjunct. (See Disjunction Elimination.)
Proof by contradiction (indirect proof): To prove ¬S by contradiction, we assume S and prove a
contradiction. In other words, we assume the negation of what we wish to prove and show that
this assumption leads to a contradiction. (See Negation Introduction.)
Proofs without premises A proof without premises, as the name implies, contains no premises. Such a
proof typically begins with a subproof assumption and ends when all subproofs have been closed.
The conclusion of a proof without premises is called a theorem of the system of proof. In a sound
system, every theorem is a logical consequence of the empty set of premises, i.e., is a logical
truth. (See Soundness, Theorem.)
Reflexive: a binary relation R is reflexive iff everything stands in the relation R to itself, i.e., R satisfies
the condition that ∀x R(x, x).
Satisfaction: An object named a satisfies an atomic wff S(x) if and only if S(a) is true, where S(a) is
the result of replacing all free occurrences of x in S(x) with the name a. Satisfaction for wffs
with more than one free variable is defined similarly. For example, an ordered pair of objects
named a and b, respectively, satisfies an atomic wff S(x, y) if and only if S(a, b) is true, where
S(a, b) is the result of replacing all free occurrences of x in S(x, y) with the name a and all free
occurrences of y with the name b.
Scope of quantifier: The scope of a quantifier in a wff is that part of the wff that falls under the
“influence” of the quantifier. Parentheses play an important role in determining the scope of
quantifiers. When a quantifier is immediately followed by a left parenthesis, the scope of that
quantifier is the wff that is contained between that parenthesis and the right parenthesis that is its
mate.