Tiny introduction to logic
Henry S. Thompson
HCRC Language Technology Group
School of Informatics
University of Edinburgh
Architecture Domain
World Wide Web Consortium
Extracted from Towards a logical
foundation for XML Schema, XML Europe 2004
What is a logic, anyway?
- By 'a logic' I mean a pretty traditional three-part
story:
- A sentential form
- an inductive definition of what
constitutes a WFF (well-formed formula)
- A model theory
- a set-theoretic definition of possible
model
- An interpretation
- a constructive definition of what
it means for a WFF to be valid with respect to a model
A famous example from Frege
- First a BNF to define our WFFs:
- birds ::= 'doves' | 'crows' | . . .
- stuff ::= 'tar' | 'snow' | . . .
- color ::= 'black' | 'white' | . . .
- spred ::= 'is' | 'is not'
- ppred ::= 'are' | 'are not'
- lcon ::= 'and' | 'or'
- ssent ::= stuff ' ' spred ' ' color
- psent ::= birds ' ' ppred ' ' color
- sent ::= ssent | psent
- wff ::= sent | '(' wff ') ' lcon ' (' wff ')'
- Some examples of WFFs are then:
- crows are black
- snow is white
- (doves are black) or (doves are not black)
Famous example, cont'd
- Our models are very simple
- a set of individuals (the domain)
- a set of named disjoint subsets of
that set (the colourings)
- For example, one possible model would be
-
domain
- {a, b, c, d, e, f, g, h}
-
colourings
- {black:{a, b, c},
white:{d, e, f, g}}
Famous example, cont'd 2
- Finally the constructive definition of validity.
- A mapping from WFFs to conditions on a
model
- We use double square-brackets 〚〛to denote this
mapping
- We treat our birds and stuff as variables
- they
have an arbitrary association with individuals in a model
- We
denote the variable assignment function with the Greek letter iota (ι)
- The mapping rules then are as follows, using
X and Y is meta-variables over parts of WFFs:
-
〚(X) or (Y)〛 ==
(〚X〛) ∨
(〚Y〛)
-
〚(X) and (Y)〛 ==
(〚X〛) ∧
(〚Y〛)
-
〚X is Y〛 ==
ι(X) ∈ 〚Y〛
-
〚X are Y〛 ==
ι(X) ∈ 〚Y〛
-
〚X is not Y〛 ==
ι(X) ∉ 〚Y〛
-
〚X are not Y〛 ==
ι(X) ∉ 〚Y〛
-
〚white〛 == the set
named 'white' in the model
-
〚black〛 == the set
named 'black' in the model
Famous example, concluded
- Given the specific model above
- and a variable assignment
which maps 'doves' to 'f'
- the interpretation of the
last example WFF above, namely
(doves are black) or (doves are not
black)
is
- ( f ∈ {a, b, c} ) ∨ ( f ∉ {a,
b, c} )
- which is evidently true
- it should be clear that indeed it's a tautology
- All of which may serve to explain why Frege was not being childish when
he, famously, said
- 〚Snow is white〛 is true just in case
〚snow〛 is 〚white〛
[punctuation added
:-]