Glossary

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

de¬nition.

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.

Glossary

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

necessity

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

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))

Glossary

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

true.

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

condition.

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

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.)

Glossary

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.