. 103
( 107 .)


Glossary / 567

clause specifying the basic elements of the de¬ned set, one or more
inductive clauses specifying how additional elements are generated from
existing elements, and a ¬nal clause, which tells us that all the elements
are either basic or in the set because of (possibly repeated) application
of the inductive clauses.

Inductive proof: Inductive proofs are used to establish claims about induc-
tively de¬ned sets. Given such a set, to prove that some property holds
of every element of that set we need a basis step, which shows that
the property holds of the basic elements, and an inductive step, which
shows that if the property holds of some elements, then it holds of any
elements generated from them by the inductive clauses. See Inductive

In¬x notation: In in¬x notation, the predicate or function symbol appears
between its two arguments. For example, a < b and a = b use in¬x
notation. Compare with Pre¬x notation.

Informal proof: See Proof.

Intersection (©): The operation on sets a and b that returns the set a © b
whose members are those objects common to both a and b.

Lemma: A lemma is a claim that is proven, like a theorem, but whose pri-
mary importance is for proving other claims. Lemmas are of less intrinsic
interest than theorems. (See Theorem.)

Literal: A literal is a sentence that is either an atomic sentence or the nega-
tion of an atomic sentence.

Logical consequence: A sentence S is a logical consequence of a set of
premises if it is impossible for the premises all to be true while the
conclusion S is false.

Logical equivalence: Two sentences are logically equivalent if they have the
same truth values in all possible circumstances.

Logical necessity: See Logical truth.

Logical possibility: We say that a sentence or claim is logically possible if
there is no logical reason it cannot be true, i.e., if there is a possible
circumstance in which it is true.

568 / Glossary

Logical truth: A logical truth is a sentence that is a logical consequence of
any set of premises. That is, no matter what the premises may be, it
is impossible for the conclusion to be false. This is also called a logical

Logical validity: An argument is logically valid if the conclusion is a logical
consequence of the premises.

Material conditional: A truth-functional version of the conditional if. . .
then. . . . The material conditional P ’ Q is false if P is true and Q is
false, but otherwise is true. (See Conditional.)

Modus ponens: The Latin name for the rule that allows us to infer Q from
P and P ’ Q. Also known as ’ Elimination.

Names: See Individual constants.

Necessary condition: A necessary condition for a statement S is a condition
that must hold in order for S to obtain. For example, if you must pass
the ¬nal to pass the course, then your passing the ¬nal is a necessary
condition for your passing the course. Compare with Su¬cient condition.

Negation normal form (NNF): A sentence of fol is in negation normal
form if all occurrences of negation apply directly to atomic sentences.
For example, (¬A § ¬B) is in NNF whereas ¬(A ∨ B) is not in NNF.

Numerical quanti¬er: Numerical quanti¬ers are those quanti¬ers used to
express numerical claims, for example, at least two, exactly one, no more
than ¬ve, etc.

Predicate: Predicates are used to express properties of objects or relations
between objects. Larger and Cube are examples of predicates in the
blocks language.

Pre¬x notation: In pre¬x notation, the predicate or relation symbol pre-
cedes the terms denoting objects in the relation. Larger(a, b) is in pre¬x
notation. Compare with In¬x notation.

Premise: A premise of an argument is one of the statements meant to sup-
port (lead us to accept) the conclusion of the argument.

Prenex normal form: A w¬ of fol is in prenex normal form if it contains
no quanti¬ers, or all the quanti¬ers are “out in front.”

Glossary / 569

Proof: A proof is a step-by-step demonstration that one statement (the con-
clusion) follows logically from some others (the premises). A formal proof
is a proof given in a formal system of deduction; an informal proof is
generally given in English, without the bene¬t of a formal system.

Proof by cases: A proof by cases consists in proving some statement S from
a disjunction by proving S from each disjunct.

Proof by contradiction: 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.

Proof by induction: See Inductive proof.
Proof of non-consequence: In a proof of non-consequence, we show that
an argument is invalid by ¬nding a counterexample. That is, to show
that a sentence S is not a consequence of some given premises, we have to
show that it is possible for the premises to be true in some circumstance
where S is false.
Proposition: Something that is either true or false. Also called a claim.

Quanti¬er: In English, a quanti¬ed expression is a noun phrase using a
determiner such as every, some, three, etc. Quanti¬ers are the elements
of fol that allow us to express quanti¬ed expressions like every cube.
There are only two quanti¬ers in fol, the universal quanti¬er (∀) and
the existential quanti¬er (∃). From these two, we can, however, express
more complex quanti¬ed expressions.
Reductio ad absurdum: See Proof by contradiction.
Satisfaction: An object named a satis¬es an atomic w¬ 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 w¬s with more than one free
variable is de¬ned similarly, using the notion of a variable assignment.
Scope: The scope of a quanti¬er in a w¬ is that part of the w¬ that falls
under the “in¬‚uence” of the quanti¬er. Parentheses play an important
role in determining the scope of quanti¬ers. For example, in

∀x(P(x) ’ Q(x)) ’ S(x)

the scope of the quanti¬er extends only over P(x) ’ Q(x). If we were to
add another set of parentheses, e.g.,

∀x((P(x) ’ Q(x)) ’ S(x))

570 / Glossary

the scope of the quanti¬er would extend over the entire sentence.

Sentence: In propositional logic, atomic sentences are formed by combining
names and predicates. Compound sentences are formed by combining
atomic sentences by means of the truth functional connectives. In fol,
the de¬nition is a bit more complicated. A sentence of fol is a w¬ with
no free variables.

Soundness: “Sound” is used in two di¬erent senses in logic.

1. An argument is sound if it is both valid and all of its premises are
2. A formal system is sound if it allows one to construct only proofs
of valid arguments, that is, if no invalid arguments are provable
within the system. (Compare with Completeness.)

Su¬cient condition: A su¬cient condition for a statement S is a condition
that guarantees that S will obtain. For example, if all you need to do
to pass the course is pass the ¬nal, then your passing the ¬nal is a
su¬cient condition for your passing the course. Compare with Necessary

Tautological consequence: A sentence S is a tautological consequence of
some premises if S follows from the premises simply in virtue of the
meanings of the truth-functional connectives. We can check for tauto-
logical consequence by means of truth tables, since S is a tautological
consequence of the premises if and only if every row of their joint truth
table that assigns true to each of premise also assigns true to S. All
tautological consequences are logical consequences, but not all logical
consequences are tautological consequences.

Tautological equivalence: Two sentences are tautologically equivalent if
they are equivalent simply in virtue of the meanings of the truth-functional
connectives. We can check for tautological equivalence by means of truth
tables since two sentences Q and S are tautologically equivalent if and
only if every row of their joint truth table assigns the same value to the
main connectives of Q and S.

Tautology: A tautology is a sentence that is logically true in virtue of its
truth-functional structure. This can be checked using truth tables since
S is a tautology if and only if every row of the truth table for S assigns
true to the main connective.

Glossary / 571

Term: Variables and individual constants are terms of a ¬rst-order language,
as are the results of combining an n-ary function symbol f with n terms
to form a new term.

Theorem: In formal systems, a theorem of is any statement that has been
proven from some given set of axioms. Informally, the term “theorem”
is usually reserved for conclusions that the author ¬nds particularly
interesting or important. (Compare Corollary and Lemma.)

Truth assignment: A function assigning true or false to each atomic sen-
tence of a ¬rst-order language. Used to model the informal notion of a
world or set of circumstances.

Truth-functional connective: A sentence connective with the property that
the truth value of the newly formed sentence is determined solely by the
truth value(s) of the constituent sentence(s), nothing more. Examples
are the Boolean connectives (¬ , § , ∨) and the material conditional and
biconditional (’, ”).

Truth table: Truth tables show the way in which the truth value of a sen-
tence built up using truth-functional connectives depends on the truth
values of the sentence™s components.

Truth value: The truth value of a statement in some circumstances is true
if the statement is true in those circumstances, otherwise its truth value
is false. This is an informal notion but also has rigorous counterparts
in propositional logic, where circumstances are modeled by truth as-
signments, and in ¬rst-order logic where circumstances are modeled by
¬rst-order structures.

Universal quanti¬er (∀): The universal quanti¬er is used to express uni-
versal claims. Its corresponds, roughly, to English expressions such as
everything, all things, each thing, etc. (See also Quanti¬ers.)

Union (∪): The operation on sets a and b that returns the set a ∪ b whose
members are those objects in either a or b or both.

Validity: “Validity” is used in two ways in logic:

1. Validity as a property of arguments: An argument is valid if the
conclusion must be true in any circumstance in which the premises
are true. (See also Logical validity and Logical consequence.)

572 / Glossary

2. Validity as a property of sentences: A ¬rst-order sentence is said
to be valid if it is logically true simply in virtue of the meanings of
its connectives, quanti¬ers, and identity. (See First-order validity.)

Variable: Variables are expressions of fol that function somewhat like pro-
nouns in English. They are like individual constants in that they may
be the arguments of predicates, but unlike constants, they can be bound
by quanti¬ers. Generally letters from the end of the alphabet, x, y, z,
etc., are used for variables.


. 103
( 107 .)