. 102
( 107 .)


tences in virtue of the meanings of the truth-functional connectives alone.

First-order Consequence
(FO Con)

FO Con allows you to infer any sentence that follows from the cited sentences
in virtue of the meanings of the truth-functional connectives, the quanti¬ers
and the identity predicate.

Analytic Consequence
(Ana Con)

In theory, Ana Con should allow you to infer any sentence that follows
from the cited sentences in virtue of the meanings of the truth-functional
connectives, the quanti¬ers, the identity predicate and the blocks language
predicates. The Fitch implementation of Ana Con, however, does not take
into account the meaning of Adjoins or Between due to the complexity these
predicates give rise to.

Inference Procedures (Con Rules)

Ambiguity: A feature of natural languages that makes it possible for a single
sentence to have two or more meanings. For example, Max is happy or
Claire is happy and Carl is happy, can be used to claim that either Max
is happy or both Claire and Carl are happy, or it can be used to claim
that at least one of Max and Claire is happy and that Carl is happy.
Ambiguity can also arise from words that have two meanings, as in the
case of puns. Fol does not allow for ambiguity.

Antecedent: The antecedent of a conditional is its ¬rst component clause.
In P ’ Q, P is the antecedent and Q is the consequent.

Argument: The word “argument” is ambiguous in logic.

1. One kind of argument consists of a sequence of statements in which
one (the conclusion) is supposed to follow from or be supported by
the others (the premises).
2. Another use of “argument” refers to the term(s) taken by a pred-
icate in an atomic w¬. In the atomic w¬ LeftOf(x, a), x and a are
the arguments of the binary predicate LeftOf.

Arity: The arity of a predicate indicates the number of arguments (in the
second sense of the word) it takes. A predicate with arity of one is called
unary. A predicate with an arity of two is called binary. It™s possible for
a predicate to have any arity, so we can talk about 6-ary or even 113-ary

Atomic sentences: Atomic sentences are the most basic sentences of fol,
those formed by a predicate followed by the right number (see arity) of
names (or complex terms, if the language contains function symbols).
Atomic sentences in fol correspond to the simplest sentences of English.

Axiom: An axiom is a proposition (or claim) that is accepted as true about
some domain and used to establish other truths about that domain.

Boolean connective (Boolean operator): The logical connectives conjunc-
tion, disjunction, and negation allow us to form complex claims from
simpler claims and are known as the Boolean connectives after the logi-
cian George Boole. Conjunction corresponds to the English word and,

Glossary / 563

disjunction to or, and negation corresponds to the phrase it is not the
case that. (See also Truth-functional connective.)

Bound variable: A bound variable is an instance of a variable occurring
within the scope of a quanti¬er used with the same variable. For exam-
ple, in ∀x P(x, y) the variable x is bound, but y is “unbound” or “free.”

Claim: Claims are made by people using declarative sentences. Sometimes
claims are called propositions.

Completeness: “Completeness” is an overworked word in logic.

1. A formal system of deduction is said to be complete if, roughly
speaking, every valid argument has a proof in the formal system.
This sense is discussed in Section 8.3 and elsewhere in the text.
(Compare with Soundness.)
2. A set of sentences of fol is said to be formally complete if for
every sentence of the language, either it or its negation can be
proven from the set, using the rules of the given formal system.
Completeness, in this sense, is discussed in Section 19.8.
3. A set of truth-functional connectives is said to be truth-functionally
complete if every truth-functional connective can be de¬ned using
only connectives in the given set. Truth-functional completeness is
discussed in Section 7.4.

Conclusion: The conclusion of an argument is the statement that is meant to
follow from the other statements, or premises. In most formal systems,
the conclusion comes after the premises, but in natural language, things
are more subtle.

Conditional: The term “conditional” refers to a wide class of constructions
in English including if. . . then. . . , . . . because. . . , . . . unless. . . ., and the
like, that express some kind of conditional relationship between the two
parts. Only some of these constructions are truth functional and can be
represented by means of the material conditional of fol. (See Material

Conditional proof: Conditional proof is the method of proof that allows
one to prove a conditional statement P ’ Q by temporarily assuming P
and proving Q under this additional assumption.

Conjunct: One of the component sentences in a conjunction. For example,
A and B are the conjuncts of A § B.

564 / Glossary

Conjunction: The Boolean connective corresponding to the English word
and. A conjunction of sentences is true if and only if each conjunct is

Conjunctive normal form (CNF): A sentence is in conjunctive normal
form if it is a conjunction of one or more disjunctions of one or more

Connective: An operator for making new statements out of simpler state-
ments. Typical examples are conjunction, negation, and the conditional.

Consequent: The consequent of a conditional is its second component clause.
In P ’ Q, Q is the antecedent and P is the consequent.

Context sensitivity: A predicate, name, or sentence is context sensitive
when its interpretation depends on our perspective on the world. For
example, in Tarski™s World, the predicate Larger is not context sensitive
since it is a determinate matter whether one block is larger than another,
regardless of our perspective on the world, whereas the predicate LeftOf
depends on our perspective on the blocks world. In English many words
are context sensitive, including words like I, here, now, friend, home,
and so forth.

Counterexample: A counterexample to an argument is a possible situation
in which all the premises of the argument are true but the conclusion is
false. Finding even a single counterexample is su¬cient to show that an
argument is not logically valid.

Contradiction (⊥): Something that cannot possibly be true in any set of
circumstances, for example, a statement and its negation. The symbol
⊥ represents contradiction.

Corollary: A corollary is a result which follows with little e¬ort from an
earlier theorem. (See Theorem.)

Deductive system: A deductive system is a collection of rules and a speci¬-
cation of the ways they can be use to construct formal proofs. The system
F de¬ned in the text is an example of a deductive system, though there
are many others.

Determinate property: A property is determinate if for any object there is
a de¬nite fact of the matter whether or not the object has that property.
In ¬rst-order logic we assume that we are working with determinate

Glossary / 565

Determiner: Determiners are words such as every, some, most, etc., which
combine with common nouns to form quanti¬ed noun phrases like every
dog, some horses, and most pigs.

Disjunct: One of the component sentences in a disjunction. For example, A
and B are the disjuncts of A ∨ B.

Disjunction: The basic Boolean connective corresponding to the English
word or. A disjunction is true if at least one of the disjuncts is true.
(See also Inclusive disjunction and Exclusive disjunction.)

Disjunctive normal form (DNF): A sentence is in disjunctive normal form
if it is a disjunction of one or more conjunctions of one or more literals.

Domain of discourse: When we use a sentence to make a claim, we always
implicitly presuppose some domain of discourse. In fol this becomes
important in understanding quanti¬cation, since there must be a set of
objects under consideration when evaluating claims involving quanti-
¬ers. For example, the truth-value of the claim “Every student received
a passing grade” depends on our domain of discourse. The truth-values
may di¬er depending on whether our domain of discourse contains all
the students in the world, in the university, or just in one particular

Domain of quanti¬cation: See Domain of discourse.

Empty set: The unique set with no elements, often denoted by ….

Equivalence classes: An equivalence class is the set of all things equivalent
to a chosen object with respect to a particular equivalence relation. More
speci¬cally, given an equivalence relation R on a set S, we can de¬ne an
equivalence class for any x ∈ D as follows:

{y ∈ D | x, y ∈ R}

Equivalence relation: An equivalence relation is a binary relation that is
re¬‚exive, symmetric, and transitive.

Exclusive disjunction: This is the use of or in English that means exactly
one of the two disjuncts is true, but not both. For example, when a
waiter says “You may have soup or you may have salad,” the disjunction
is usually meant exclusively. Exclusive disjunctions can be expressed in
fol, but the basic disjunction of fol is inclusive, not exclusive.

566 / Glossary

Existential quanti¬er (∃): In fol, the existential quanti¬er is expressed by
the symbol ∃ and is used to make claims asserting the existence of some
object in the domain of discourse. In English, we express existentially
quanti¬ed claims with the use of words like something, at least one thing,
a, etc.

First-order consequence: A sentence S is a ¬rst-order consequence of some
premises if S follows from the premises simply in virtue of the meanings
of the truth-functional connectives, identity, and the quanti¬ers.

First-order structure: A ¬rst-order structure is a mathematical model of
the circumstances that determine the truth values of the sentences of
a given ¬rst-order language. It is analogous to a truth assignment for
propositional logic but must also model the domain of quanti¬cation
and the objects to which the predicates apply.

First-order validity: A sentence S is a ¬rst-order validity if S is a logical
truth simply in virtue of the meanings of the truth-functional connec-
tives, identity, and the quanti¬ers. This is the analog, in ¬rst-order logic,
of the notion of a tautology in propositional logic.

Formal proof: See Proof.

Free variable: A free variable is an instance of a variable that is not bound.
(See Bound variable.)

Generalized quanti¬er: Generalized quanti¬ers refer to quanti¬ed expres-
sions beyond the simple uses of ∀ (everything) and ∃ (something); ex-
pressions like Most students, Few teachers, and Exactly three blocks.

Inclusive disjunction: This is the use of or in which the compound sentence
is true as long as at least one of the disjuncts is true. It is this sense of or
that is expressed by fol™s disjunction. Compare Exclusive disjunction.

Indirect proof: See Proof by contradiction.

Individual constant: Individual constants, or names, are those symbols of
fol that stand for objects or individuals. In fol is it assumed that each
individual constant of the language names one and only one object.

Inductive de¬nition: Inductive de¬nitions allow us to de¬ne certain types
of sets that cannot be de¬ned explicitly in ¬rst-order logic. Examples of
inductively de¬ned sets include the set of w¬s, the set of formal proofs,
and the set of natural numbers. Inductive de¬nitions consist of a base


. 102
( 107 .)