Terms and Definitions
Atomic Sentences – most basic sentences of FOL; formed by a predicated of arity
n, followed by n terms.
Complex Sentences – not atomic, these sentences are formed when atomic
sentences are combined with truth-functional connectives.
Completeness – three ways in which it may be defined:
1) A formal system of deduction is said to be complete if every valid argument
has a proof in the formal system (see 8.3)
2) A set of sentences in 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
3) A set of truth-functional connectives is said to be truth-functionally complete
if every truth-functional connective can be defined using only connectives in
the given set (see 7.4)
Completeness Theorem – if a sentence S is a tautological consequence of P1,...,
Pn, then P1,..., Pn can be used to prove S.
This tells us that the introduction and elimination rules are complete for the logic of
truth-functional connectives: anything that is a logical consequence simply in virtue
of the meanings of the truth-functional connectives can be prove in a complete
This also gives a method for showing that an argument has a proof without actually
having to find such a proof.
Deductive System – a collection of rules and a specification of the ways they can
be used to construct formal proofs
1) The negation of a conjunction is logically equivalent to the disjunction of the
negations of the original conjuncts.
2) The negation of a disjunction is equivalent to the conjunction of the negations
of the original disjuncts
Determiners – phrases which combine with common nouns to form quantified
noun phrases. Examples of determiners include every, some, and most and
examples of quantified phrases include every dog, some horses, and most pigs.
Domain of Discourse – the set of objects under consideration when evaluating
First-Order Consequence – S is a first-order consequence of P if S follows from P
simply in virtue of the meanings of the truth-functional connectives, identity, and the quantifiers.
First-Order Validity – S is a first-order validity if S is a logical truth simply in virtue
of the meanings of the truth-functional connectives, identity, and the quantifiers.
Generalized Quantifiers – quantified expressions beyond the simple uses of
“everything” and “something;” expressions such as “most students,” “few
teachers,” and “exactly three blocks.”
Indirect Proof – proof by contradiction.
Individual Constant – symbols of FOL that stand for objects or individuals; in FOL
each individual constant names one and only one object
Literal – a sentence that is either an atomic sentence or the negation of an atomic
Logical Consequence – sentence S is a logical consequence of premises P1...Pn 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; this also means that they are
logical consequences of each other.
Logical Possibility – a sentence/claim is logically possible if there is no logical
reason it cannot be true
Logical Truth – a