# 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 :-]