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)

Glossary

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

predicates.

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,

562

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

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.

Glossary

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

true.

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

literals.

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

properties.

Glossary

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

class.

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.

Glossary

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