(Last modified Tue Jan 22 22:41 2008)
λ
What is logic?
That's a good question ... some possible answers follow:
- Logic is the study of formulae made up of true-false variables
combined using
¬ "not",
∧ "and",
∨ "or",
and parentheses
(plus some more complicated things like
∀ ∃
and
).
- Logic is the abstraction of thought to its simplest possible components:
we consider whether something is true or false only,
and we analyze it based on its structure and
whether its components are true or false.
- Logic is the study of reasoning made recursively compositional.
In logic,
we study structures whose meaning is determined by
the meaning of their substructures
and the fashion in which those substructures are combined.
Perhaps it is more effective,
especially at first,
to talk about what we can do with logic.
Some of the things we can do are:
- construct a formula whose structure mirrors that of an assertion in English
(or some other natural language).
- determine whether a formula is never true, sometimes true, or always true.
- calculate whether one formula implies another.
- construct a proof of a formula (in various ways).
- evaluate the expressiveness or reliability of a logic language or proof system.
Logics
There are a number of standard logics:
- propositional logic (PL)
-
in which the only variables are those whose value is either true or false;
- first-order logic (FOL)
-
in which we additionally have variables
that refer to any of a domain of objects.
This allows
predicates
on objects that produce true or false,
functions
on objects that return other objects,
and
quantifiers
over the domain
that apply their subformula to each object in the domain.
First-order logic is the strongest logic that is
complete and
compact and
for which every
countable,
satisfiable set of statements
has a model
whose domain is the natural numbers.
- second-order logic
-
in which we additionally have variables
that refer to any of a set of predicates,
and variables that refer to any of a set of functions.
This allows
quantifiers over sets of predicates or functions
that apply their subformula with each predicate or function in the set.
- modal logic
-
a first-order logic in which we additionally have modalities
of necessity and possibility.
- temporal logic
-
a modal logic in which necessity and possibility
are viewed, in a way,
as quantifiers over time,
that apply their subformulae to each possible time
in the future.
Each logic language can be described from several viewpoints,
and these viewpoints are the same for every language.
- Syntax
- We can describe the syntax of the language,
that is, the form of formulae in the language.
- Semantics
- We can describe the semantics of the language,
that is,
the truth-value of formulae in the language,
specified in terms of the syntactic form of those formulae.
- Interpretation
- We can describe the interpretations
that are possible for formulae in the language,
or how a formula may be applied to a particular world
and its truth-value (or other aspects) determined.
- Proof
- We can describe some proof rules
by which collections of true formulae may be extended.
A particular set of rules may be
sound (only proving true formulae),
complete (proving every true formula),
both, or neither.
Meta-language
The study of logic demands us to take a step back:
it requires us to talk about logic formulae as subjects of study,
frequently in ways that are themselves PL-like.
To keep things straight,
we distinguish the object language from the meta-language.
The object language is the logic language we are studying,
which may be propositional logic, first-order logic,
or any other logic.
The meta-language is the language in which we express
properties of, relations between, and conclusions about
formulae in the object language,
or of/between/about two or more object languages.
Because logic is an abstraction of thought,
not surprisingly
the meta-language contains properties, relations, and conclusions
similar to those in the languages of logic.
To ensure that we are saying what we think we are,
we make a careful distinction
between object language concepts
and meta-language concepts.
For example,
we will define the
conjunction of two subformulae
as a formula that is true if both subformulae are true,
and false otherwise.
The "and" that we used in the definition
is clearly related to conjunction.
However, "and" is also clearly a meta-language concept,
distinct from the object-language concept of conjunction,
and if it were not distinct we would be defining conjunction circularly.
As another example,
we will use both
variables and
metavariables.
A variable represents an object in the domain of
a predicate logic or first-order logic language.
Such a variable can appear wherever an object can be named.
A metavariable represents entire formulae in the logic,
and can appear in a formula wherever a subformula can.
Although both these are variables in the general sense,
they do not represent the same kind of entities
and cannot be interchanged.
