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 threepart
story:
 A sentential form
 an inductive definition of what
constitutes a WFF (wellformed formula)
 A model theory
 a settheoretic 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 squarebrackets 〚〛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 metavariables 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
:]