ISO/IEC 24707:2007

INTERNATIONAL ISO/IEC
STANDARD 24707
First edition
2007-10-01
Information technology — Common Logic
(CL): a framework for a family of logic-
based languages
Technologies de l'information — Logique commune (CL): un cadre pour
une famille de langages basés sur la logique

Reference number
©
ISO/IEC 2007
PDF disclaimer
This PDF file may contain embedded typefaces. In accordance with Adobe's licensing policy, this file may be printed or viewed but
shall not be edited unless the typefaces which are embedded are licensed to and installed on the computer performing the editing. In
downloading this file, parties accept therein the responsibility of not infringing Adobe's licensing policy. The ISO Central Secretariat
accepts no liability in this area.
Adobe is a trademark of Adobe Systems Incorporated.
Details of the software products used to create this PDF file can be found in the General Info relative to the file; the PDF-creation
parameters were optimized for printing. Every care has been taken to ensure that the file is suitable for use by ISO member bodies. In
the unlikely event that a problem relating to it is found, please inform the Central Secretariat at the address given below.

©  ISO/IEC 2007
All rights reserved. Unless otherwise specified, no part of this publication may be reproduced or utilized in any form or by any means,
electronic or mechanical, including photocopying and microfilm, without permission in writing from either ISO at the address below or
ISO's member body in the country of the requester.
ISO copyright office
Case postale 56 • CH-1211 Geneva 20
Tel. + 41 22 749 01 11
Fax + 41 22 749 09 47
E-mail copyright@iso.org
Web www.iso.org
Published in Switzerland
ii © ISO/IEC 2007 – All rights reserved

Contents Page
Foreword. vi
Introduction . vii
1 Scope .1
2 Normative references .2
3 Terms and definitions .2
4 Symbols and abbreviations .5
4.1 Symbols .5
4.2 Abbreviations.6
5 Requirements and design overview .6
5.1 Requirements.6
5.2 A family of notations .8
6 Common Logic abstract syntax and semantics .8
6.1 Common Logic abstract syntax. .8
6.2 Common Logic semantics .13
6.3 Importing and identification on a network .16
6.4 Satisfaction, validity and entailment.18
6.5 Sequence markers, recursion and argument lists: discussion .18
6.6 Special cases and translations between dialects .19
7 Conformance.20
7.1 Dialect conformance .20
7.2 Application conformance.22
7.3 Network conformance .22
Annex A (normative)    Common Logic Interchange Format (CLIF) .23
A.1 Introduction.23
A.2 CLIF Syntax .24
A.3 CLIF semantics .29
A.4 CLIF conformance .32
Annex B (normative) Conceptual Graph Interchange Format (CGIF).33
B.1 Introduction.33
B.2 CG Core Syntax and Semantics.39
B.3 Extended CGIF Syntax .45
B.4 CGIF conformance.51
Annex C (normative)    eXtended Common Logic Markup Language (XCL).54
C.1 Introduction.54
C.2 XCL Syntax .54
C.3 XCL Semantics.72
C.4 XCL Conformance.72
Bibliography .73
© ISO/IEC 2007 – All rights reserved iii

Figures Page
Figure 1 — Structure of a text and the taxonomy of the phrase category text .10
Figure 2 — Abstract syntax of sentence and its sub-categories.10
Figure 3 — Abstract syntax of a module.10
Figure 4 — Abstract syntax of a quantified sentence .11
Figure 5 — Abstract syntax of a boolean sentence .11
Figure 6 — Abstract syntax of an atom.12
Figure 7 — Abstract syntax of a term and term sequence .12
Figure B.1 — CG display form for John is going to Boston by bus. 33
Figure B.2 — CG display form for “If a cat is on a mat, then it is a happy pet” . 34
Figure B.3 — CL functions represented by actor nodes. 35

Tables Page
Table 1 — Interpretations of Common Logic Expressions 15
Table A.1 — CLIF Semantics 30
Table A.2 — Mapping from additional CLIF forms to core CLIF forms 31
Table B.1 — Mapping from CL abstract syntax to extended CGIF syntax 52

iv © ISO/IEC 2007 – All rights reserved

Foreword
ISO (the International Organization for Standardization) and IEC (the International Electrotechnical
Commission) form the specialized system for worldwide standardization. National bodies that are members of
ISO or IEC participate in the development of International Standards through technical committees
established by the respective organization to deal with particular fields of technical activity. ISO and IEC
technical committees collaborate in fields of mutual interest. Other international organizations, governmental
and non-governmental, in liaison with ISO and IEC, also take part in the work. In the field of information
technology, ISO and IEC have established a joint technical committee, ISO/IEC JTC 1.
International Standards are drafted in accordance with the rules given in the ISO/IEC Directives, Part 2.
The main task of the joint technical committee is to prepare International Standards. Draft International
Standards adopted by the joint technical committee are circulated to national bodies for voting. Publication as
an International Standard requires approval by at least 75 % of the national bodies casting a vote.
Attention is drawn to the possibility that some of the elements of this document may be the subject of patent
rights. ISO and IEC shall not be held responsible for identifying any or all such patent rights.
ISO/IEC 24707 was prepared by Joint Technical Committee ISO/IEC JTC 1, Information technology,
Subcommittee SC 32, Data management and interchange.
© ISO/IEC 2007 – All rights reserved v

Introduction
Common Logic is a logic framework intended for information exchange and transmission. The framework
allows for a variety of different syntactic forms, called dialects, all expressible within a common XML-based
syntax and all sharing a single semantics.
Common Logic has some novel features, chief among them being a syntax which is signature-free and
permits 'higher-order' constructions such as quantification over classes or relations while preserving a first-
order model theory, and a semantics which allows theories to describe intensional entities such as classes or
properties. It also fixes the meanings of a few conventions in widespread use, such as numerals to denote
integers and quotation marks to denote character strings, and has provision for the use of datatypes and for
naming, importing and transmitting content on the World Wide Web using XML.

vi © ISO/IEC 2007 – All rights reserved

INTERNATIONAL STANDARD ISO/IEC 24707:2007(E)

Information technology — Common Logic (CL): a framework for
a family of logic-based languages
1 Scope
This International Standard specifies a family of logic languages designed for use in the representation and
interchange of information and data among disparate computer systems.
The following features are essential to the design of this International Standard:
• Languages in the family have declarative semantics. It is possible to understand the meaning of
expressions in these languages without appeal to an interpreter for manipulating those
expressions.
• Languages in the family are logically comprehensive — at its most general, they provide for the
expression of arbitrary first-order logical sentences.
• Interchange of information among heterogeneous computer systems.
The following are within the scope of this International Standard:
• representation of information in ontologies and knowledge bases;
• specification of expressions that are the input or output of inference engines;
• formal interpretations of the symbols in the language.
The following are outside the scope of this International Standard:
• the specification of proof theory or inference rules;
• specification of translators between the notations of heterogeneous computer systems;
• computer-based operational methods of providing relationships between symbols in the logical
“universe of discourse” and individuals in the “real world”.
This International Standard describes Common Logic’s syntax and semantics.
It defines an abstract syntax and an associated model-theoretic semantics for a specific extension of first-
order logic. The intent is that the content of any system using first-order logic can be represented in this
International Standard. The purpose is to facilitate interchange of first-order logic-based information between
systems.
Issues relating to computability using this International Standard (efficiency, optimization, etc.) are not
addressed.
© ISO/IEC 2007 – All rights reserved 1

2 Normative references
The following referenced documents are indispensable for the application of this document. For dated
references, only the edition cited applies. For undated references, the latest edition of the referenced
document (including any amendments) applies.
ISO/IEC 2382-15:1999, Information technology — Vocabulary — Part 15: Programming languages
ISO/IEC 10646:2003, Information technology — Universal Multiple-Octet Coded Character Set (UCS)
ISO/IEC 14977:1996, Information technology — Syntactic metalanguage — Extended BNF
3 Terms and definitions
For the purposes of this document, the following terms and definitions apply.
3.1
atom
sentence form which has no subsentences as syntactic components
NOTE Can be either an equation, or an atomic sentence consisting of a predicate applied to an argument sequence.
3.2
axiom
any sentence which is assumed to be true, from which others are derived, or by which they are entailed
NOTE In a computational setting, an axiom is a sentence which is never posed as a goal to be proved, but only used
to prove other sentences.
3.3
Common Logic Interchange Format
CLIF
KIF-based syntax that is used for illustration purposes in this International Standard
NOTE It is one of the concrete syntaxes as described in Annex A. The name “KIF” is not used for this syntax in order
to distinguish it from the commonly used KIF dialects. No assumptions are made in this International Standard with
respect to KIF semantics; in particular, no equivalence between CLIF and KIF is intended.
3.4
conceptual graph
CG
graphical or textual display of symbols arranged according to the style of conceptual graph theory
3.5
Conceptual Graph Interchange Format
CGIF
text version of conceptual graphs whose rules of formation conform to Annex B of this International Standard
NOTE Sometimes may refer to an example of a character string that conforms to Annex B. Intended to convey
exactly the same structure and semantics as an equivalent conceptual graph.
3.6
conceptual graph theory
form of first-order logic which represents existential quantification and conjunction via the assertion of logical
constructs called concepts and relations, which are arranged in an abstract or visually displayed graph
NOTE Conceptual graph theory was introduced by John Sowa [1].
2 © ISO/IEC 2007 – All rights reserved

3.7
denotation
relationship holding between a name or expression and the thing to which it refers
NOTE Also used, with “of,” to mean the entity being named, i.e. the referent of a name or expression.
3.8 dialect
concrete instance of Common Logic syntax that shares (at least some of) the uniform semantics of Common
Logic
NOTE A dialect may be textual or graphical or possibly some other form. A dialect by definition is also a conforming
language (see 7.1 for further details).
3.9
discourse name
name whose interpretation is in the universe of discourse
NOTE There is no assumption that different names are interpreted as different individuals. A single individual in the
universe of discourse may be denoted by two or more distinct names.
3.10
domain of discourse
See universe of discourse.
3.11
eXtensible Common Logic Markup Language
XCL
XML-based syntax for Common Logic
3.12
individual
one element of the universe of discourse
NOTE The universe of discourse is the set of all individuals.
3.13
Internationalized Resource Identifier
IRI
string of Unicode characters conforming to the syntax described in [2] and intended for use as an Internet
network identifier syntax which can accommodate a wide variety of international character forms
NOTE Intended to replace Uniform Resource Identifier as an Internet standard for network identifiers.
3.14
interpretation
formal specification of the meanings of the names in a vocabulary of a Common Logic dialect in terms of a
universe of reference.
NOTE 1 An interpretation in turn determines the semantic values of all complex expressions of the dialect, in particular
the truth values of its sentences.
NOTE 2 See 6.2 for a more precise description of how an interpretation is defined.
3.15
Knowledge Interchange Format
KIF
text-based first order formalism, using a LISP-like list notation
NOTE 1 KIF, introduced by Mike Genesereth [3], originated with the Knowledge Sharing Effort sponsored by the US
DARPA.
NOTE 2 KIF forms the basis for one of the three Common Logic dialects included in this International Standard.
© ISO/IEC 2007 – All rights reserved 3

3.16
operator
distinguished syntactic role played by a specified component within a functional term
NOTE The denotation of a functional term in an interpretation is determined by the functional extension of the
denotation of the operator together with the denotations of the remaining components.
3.17
predicate
〈Common Logic〉 distinguished syntactic role played by exactly one component within an atomic sentence
NOTE The truth value of an atomic sentence in an interpretation is determined by the relational extension of the
denotation of the predicate together with the denotations of the remaining components.
3.18
segregated dialect
dialect in which some names are non-discourse names
NOTE In an interpretation of a segregated dialect, the denotations of the non-discourse names are in the universe of
reference, but not in the universe of discourse.
3.19
sentence
〈Common Logic〉 unit of logical text which is true or false, i.e. which is assigned a truth-value in an
interpretation
3.20
sort
any subset of the universe of discourse over which some quantifier is allowed to range
NOTE Related to the definition of “type” (see 3.24). Generally used to mean a proper subset of the individuals in the
universe of discourse.
3.21
sorted logic
logic system (whether first-order or not) which requires that all nonlogical symbols be assigned to a sort
3.22
term
〈Common Logic〉 expression which denotes an individual, consisting of either a name or, recursively, a
function term applied to a sequence of arguments, which are themselves terms
3.23
traditional first-order logic
TFOL
traditional mathematical formulations of logic as introduced chiefly by Russell, Whitehead, Peano, Frege,
Peirce and Tarski dealing with n-ary predication, the Boolean operators (including negation) and
quantification, and in which every proposition is either determinately true or determinately false
NOTE Languages for traditional first-order logic specifically exclude predicate quantifiers and the use of the same
name in both predicate and argument position in atomic sentences, both of which are permitted (though not required) in
Common Logic. Languages for traditional first-order logic fall within the category of segregated dialects in CL (see 6.1.3).
4 © ISO/IEC 2007 – All rights reserved

3.24
type
logical framework in which expressions in the logic are classified into syntactic or lexical categories (types)
and restricted to apply only to arguments of a fixed type
NOTE 1 In practice, a type represents a class of individuals.“Type theory” usually refers to a particular class of such
logics in which relation symbols are separated into orders, with relations of order n applying only to those of lower orders.
NOTE 2 A type is more restricted than a sort in that a type imposes intensional or categorical constraints on which
individuals are members of the type category, whereas a sort refers only to any subset of individuals in the domain over
which some quantifier is presumed to operate.
3.25
universe of discourse
domain of discourse
set of all the individuals in an interpretation, i.e. the set over which the quantifiers range
NOTE Required to be a subset of the universe of reference, and may be identical to it.
3.26
universe of reference
set of all the entities needed to define the meanings of logical expressions in an interpretation
NOTE 1 Required to be a superset of the universe of discourse, and may be identical to it.
NOTE 2 Segregated dialects are commonly described to have a universe of discourse, without mentioning the universe
of reference; and for non-segregated dialects the universes of discourse and of reference are identical. The distinction
makes it possible to provide a single semantics which can cover both styles of dialect. Non-segregated dialects which treat
the universes of discourse and of reference as identical may simply refer to ‘the universe’ of an interpretation.
3.27
Uniform Resource Identifier
URI
sequence of ASCII characters conforming to the syntax forms defined in [4]
NOTE At the time of writing, the Internet standard syntax for network identifiers. It is likely to be obsoleted by
Internationalized Resource Identifier.
4 Symbols and abbreviations
These symbols and abbreviations are generally for the main clauses of the standard. Some annexes may
introduce their own symbols and abbreviations which will be grouped together within that annex.
4.1 Symbols
Some of these symbols represent terms which are defined in clause 3.
fun a mapping from UR to functions from UD * to UD
I I I I
I an interpretation, in the model-theoretic sense
int a mapping from names in a vocabulary V to UR ; informally, a means of associating names in V to
I I
referents in UR
I
rel a mapping from UR to subsets of UD *
I I I
seq a mapping from sequence markers in V to UD *
I I
© ISO/IEC 2007 – All rights reserved 5

V a vocabulary, which is a set of names and sequence markers
UD the universe of discourse; a non-empty set of individuals that an interpretation I is “about” and over
I
which the quantifiers are understood to range
UR the universe of reference, i.e. the set of all referents of names in an interpretation I
I
X* the set of finite sequences of the elements of X, for any set X
4.2 Abbreviations
These abbreviations are used in this International Standard. See clause 3 for definitions or further elaboration
on these terms.
CG Conceptual graph
CGIF Conceptual Graph Interchange Format
CL Common Logic
CLIF Common Logic Interchange Format
DF Display form (used in Annex B)
EBNF Extended Backus-Naur Format, as in ISO/IEC 14977:1996.
FO First-order
IRI Internationalized Resource Identifier
KIF Knowledge Interchange Format
OWL Web Ontology Language
RDF Resource Definition Framework
RDFS Resource Definition Framework Schema
TFOL traditional first order logic
URI Uniform Resource Identifier
XCL eXtensible Common Logic Markup Language
XML eXtensible Markup Language
5 Requirements and design overview
This clause is informative. Its purpose is to briefly describe the purposes of Common Logic and the overall
guiding principles and constraints on its content.
5.1 Requirements
Common Logic has been designed and developed with several requirements in mind, all arising from its
intended role as a medium for transmitting logical content on an open communication network. The use of
“should” in the rest of clause 5 indicates a desired goal but is not required of either CL or its conforming dialect
(in accordance with Annex H of ISO/IEC Directives – Part 2).
6 © ISO/IEC 2007 – All rights reserved

5.1.1 Common Logic should include full first-order logic with equality.
Common Logic syntax and semantics shall provide for the full range of first-order syntactic forms, with their
usual meanings. Any conventional first-order syntax will be directly translatable into Common Logic without
loss of information or alteration of meaning.
5.1.2 Common Logic should provide a general-purpose syntax for communicating logical
expressions.
a. There should be a single XML syntax for communicating Common Logic content.
b. The language should be able to express various commonly used 'syntactic sugarings' for logical forms
or commonly used patterns of logical sentences.
c. The syntax should relate to existing conventions; in particular, it should be capable of rendering any
content expressible in RDF, RDFS, or OWL.
d. There should be at least one compact, human-readable syntax defined which can be used to express
the entire language.
5.1.3 Common Logic should be easy and natural for use on the Web
a. The XML syntax should be compatible with the published specifications for XML, URI syntax, XML
Schema, Unicode, and other conventions relevant to transmission of information on the Web.
b. URIs and URI references should be usable as names in the language.
c. URIs should be usable to give names to expressions and sets of expressions, in order to facilitate Web
operations such as retrieval, importation, and cross-reference.
5.1.4 Common Logic should support open networks
a. Transmission of content between Common Logic-aware agents should not require negotiation about
syntactic roles of symbols, or translations between syntactic roles.
b. Any piece of Common Logic text should have the same meaning, and support the same entailments,
everywhere on the network. Every name should have the same logical meaning at every node of the
network.
c. No agent should be able to limit the ability of another agent to refer to any entity or to make assertions
about any entity.
d. The language should support ways to refer to a local universe of discourse and be able to relate it to
other such universes.
e. Users of Common Logic should be free to invent new names and use them in published Common
Logic content.
5.1.5 Common Logic should not make arbitrary assumptions about semantics
a. Common Logic does not make gratuitous or arbitrary assumptions about logical relationships between
different expressions.
b. If possible, Common Logic agents should express these assumptions in Common Logic directly.
© ISO/IEC 2007 – All rights reserved 7

5.2 A family of notations
This (informative) section describes what is meant by a “family” of languages and gives some of the rationale
behind the development of Common Logic.
If we follow the convention whereby any language has a grammar, then Common Logic is a family of
languages rather than a single language. Different Common Logic languages, referred to in this International
Standard as dialects, may differ sharply in their surface syntax, but they have a single uniform semantics and
can all be transcribed into the common abstract syntax. Membership in the family is defined by being inter-
translatable with the other dialects while preserving meaning, rather than by having any particular syntactic
form. Several existing logical notations and languages, therefore, can be considered to be Common Logic
dialects.
A Common Logic dialect called CLIF based on KIF (see Annex A) is used in giving examples throughout this
International Standard. CLIF can be considered an updated and simplified form of KIF 3.0 [3], and hence a
separate language in its own right, and so a complete self-contained description is given which can be
understood without reference to the rest of the specification. Conceptual graphs [1] are also a well-known form
of first-order logic for machine processing; the CGIF language is specified in Annex B. An XML dialect using
CL semantics is specified in Annex C.
6 Common Logic abstract syntax and semantics
This section describes the normative aspects of Common Logic’s syntax and semantics.
6.1 Common Logic abstract syntax.
We describe the syntax of Common Logic ‘abstractly’ here in order to not be committed to any particular
dialect’s syntactic conventions.
6.1.1 Abstract syntax categories
Each of the following entries is called an abstract syntax category. Additional terms in the entries may identify
sub-categories, or may identify constituent parts of the category. Those terms being defined here are
underlined for clarity. Other terms may be found in the definitions of clause 3.
6.1.1.1 A text is a set, list, or bag of phrases. A piece of text shall optionally be identified by a name. A
Common Logic text may be a sequence, a set, or a bag of phrases; dialects may specify which is intended or
leave this undefined. Re-orderings and repetitions of phrases in a text are semantically irrelevant. However,
applications which transmit or re-publish Common Logic text shall preserve the structure of texts, since other
applications are allowed to utilize the structure for other purposes, such as indexing. If a dialect imposes
conditions on texts, these conditions shall be preserved by conforming applications. A text may be empty.
6.1.1.2 A phrase is either a module, a sentence, an importation, or a text with an attached comment.
6.1.1.3 A comment is a piece of data. Comments may be attached to other comments and to commented phrases.
No particular restrictions are placed on the nature of Common Logic comments; in particular, a comment may
be Common Logic text. Particular dialects may impose conditions on the form of comments.
6.1.1.4 A module consists of a name, an optional set of names called the exclusion set, and a text called the
body text. The module name indicates the ‘local’ universe of discourse in which the text is understood; the
exclusion set indicates any names in the text which are explicitly excluded from this local universe. A module
name may also be used to identify the module.
6.1.1.5 An importation contains a name. The intention is that the name identifies a piece of Common Logic
content represented externally to the text, and the importation re-asserts that content in the text. The
notion of identification is discussed more fully in clause 6.3.1 below.
6.1.1.6 A sentence is either a quantified sentence or a Boolean sentence or an atom, or a sentence with an
attached comment, or an irregular sentence.
8 © ISO/IEC 2007 – All rights reserved

6.1.1.7 A quantified sentence has (i) a type, called a quantifier, (ii) a finite, nonrepeating sequence of names
and sequence markers called the binding sequence, each element of which is called a binding of the
quantified sentence, and (iii) a sentence called the body of the quantified sentence. Every Common
Logic dialect shall distinguish the universal and the existential types of quantified sentence. A name
or sequence marker which occurs in the binding sequence is said to be bound in the body. Any
name or sequence marker which is not bound in the body is said to be free in the body.
6.1.1.8 A Boolean sentence has a type, called a connective, and a number of sentences called the
components of the Boolean sentence. The number depends on the particular type. Every Common
Logic dialect shall distinguish five types of Boolean sentences: conjunctions and disjunctions, which
have any number of components, implications and biconditionals, which have exactly two
components, and negations, which have exactly one component.
NOTE The current specification does not recognize any particular irregular sentence forms. This category is included
in the abstract syntax to accommodate syntactic extensions to Common Logic whose semantics cannot be fully defined
within Common Logic. Examples include modalities, non-monotonic connectives and imperative constructions.
6.1.1.9 An atom is either an equation containing two arguments, which are terms, or is an atomic sentence,
which consists of a term, called the predicate, and a term sequence called the argument sequence,
the elements of which are called arguments of the atom.
NOTE Dialects which use a name to identify equality may consider it to be a predicate, and treat an equation as an
atomic sentence.
6.1.1.10 A term is either a name or a functional term, or a term with an attached comment.
6.1.1.11 A functional term consists of a term, called the operator, and a term sequence called the argument
sequence, the elements of which are called arguments of the functional term.
6.1.1.12 A term sequence is a finite sequence of terms or sequence markers.
NOTE Term sequences may be empty, but a functional term with an empty argument sequence shall not be
identified with its operator, and an atomic sentence with an empty argument sequence shall not be identified with its
predicate.
6.1.1.13 A vocabulary is a set of names and sequence markers.
6.1.1.14 Names and sequence markers are disjoint syntax categories, and each is disjoint from all other
syntax categories.
This clause completely describes the abstract syntactic structure of Common Logic. Any fully conformant
Common Logic dialect shall provide an unambiguous syntactic representation for each of the above types of
recognized expressions, except for irregular sentences.
Sentence types are commonly indicated by the inclusion of explicit text strings, such as “forall” for universal
sentence and “and” for conjunction. However, no conditions are imposed on how the various syntactic
categories are represented in the surface forms of a dialect. In particular, expressions in a dialect are not
required to consist of character strings.
6.1.2 Metamodel of the Common Logic Abstract Syntax
In order to better describe the structure of the abstract syntax, this section provides a metamodel showing
relationships among the syntactic categories, and describes some of the rationale for decisions. The abstract
syntax categories and their allowable structure is depicted using UML class diagram notation [5].
© ISO/IEC 2007 – All rights reserved 9

Figure 1 — Structure of a text and the taxonomy of the phrase category text

Figure 2 — Abstract syntax of sentence and its sub-categories

Figure 3 — Abstract syntax of a module
10 © ISO/IEC 2007 – All rights reserved

Figure 4 — Abstract syntax of a quantified sentence
Figure 4 depicts the abstract syntax of a quantified sentence. A universally quantified sentence is a quantified
sentence whose quantifier is universal. An existentially quantified sentence is a quantified sentence whose
quantifier is existential.
Figure 5 — Abstract syntax of a boolean sentence
© ISO/IEC 2007 – All rights reserved 11

Figure 6 — Abstract syntax of an atom

Figure 7 — Abstract syntax of a term and term sequence
6.1.3 Abstract syntactic structure of dialects
A dialect which provides only some types of the Common Logic expressions is said to be a syntactically partial
Common Logic dialect, or syntactically partially conformant. In particular, a dialect that does not include
sequence markers, but is otherwise fully conformant, is known as a syntactically compact dialect. See clause
7.1 for a description of some relationships between syntactic and semantic conformance.
Dialects may in addition provide for other forms of sentence construction not described by this syntax, but in
order to be fully conformant, such constructions shall either be new categories defined in terms of these
categories, or be extensions of these categories (e.g. new kinds of Boolean sentence, or kinds of quantifier)
which are equivalent in meaning to a construction using just this syntax, interpreted according to the Common
Logic semantics; that is, they can be considered to be systematic abbreviations, or macros; also known as
“syntactic sugar”. The CLIF dialect, described in Annex A, contains a number of syntactic sugared forms for
quantified and atomic sentences. (Other types of compliance are also recognized: see clause 7 for a full
account of conformance.)
The only undefined terms in the abstract syntax clause are name and sequence marker. The only required
syntactic constraint on the basic lexical categories of name and sequence marker are that they shall be
exclusive. Dialects intended for transmission of content on a network should not impose arbitrary or
unnecessary restrictions on the form of names, and shall provide for certain names to be used as identifiers
of Common Logic texts; that is, character strings used as identifiers in a dialect shall be parseable as
Common Logic names in that dialect. Dialects intended for use on the Web should allow Universal Resource
Identifiers, International Resource Identifiers and URI references to be used as names [2] [4]. Common Logic
dialects should define names in terms of Unicode (ISO/IEC 10646:2003) conventions.
12 © ISO/IEC 2007 – All rights reserved

There is no notion of ‘bound variable’ in the CL abstract syntax. Names that can occur bound are not required
to be lexically distinguished from those that can (only) occur free, nor are names required to be partitioned into
distinct classes such as relation, function or individual names. There are no sortal restrictions on names.
Particular Common Logic dialects may make these or other distinctions between subclasses of names, and
impose extra restrictions on the occurrence of types of names or terms in expressions – for example, by
requiring that names that can occur bound (i.e., the variables of traditional first-order languages) be written
with a special prefix, as in KIF, or with a particular style, as in Prolog; or by requiring that operators be in a
distinguished category of relation names, as in traditional first-order syntax.
A dialect may impose particular semantic conditions on some categories of names, and apply syntactic
constraints to limit where such names occur in expressions. For example, the CLIF syntax treats numerals as
having a fixed denotation, and prohibits their use as identifiers.
A dialect may require some names to be non-discourse names, which are understood not to denote entities in
the universe of discourse. This requirement may be imposed, for example, by partitioning the vocabulary or by
requiring names that occur in certain syntactic positions to be non-discourse. A dialect with non-discourse
names is called segregated. Names which are not non-discourse names are called discourse names.
A segregated dialect shall provide sufficient syntactic constraints to guarantee that in any syntactically legal
text of the dialect:
• Every name shall be classified as either discourse or as non-discourse.
• No name shall be classified as both discourse and non-discourse.
• No non-discourse name shall be an argument of an atom or functional term.
• No non-discourse name shall be bound in a quantified sentence.
As the presence of non-discourse names affects the semantics, special conditions apply to segregated
dialects.
A dialect which is not segregated is called non-segregated. All names in a non-segregated dialect are
discourse names.
6.2 Common Logic semantics
The semantics of Common Logic is defined in terms of a satisfaction relation between Common Logic text and
mathematical structures called interpretations.
The vocabulary of a Common Logic text is the set of names and sequence markers which occur in the text. In
a segregated dialect, the names in vocabularies are partitioned into discourse names and non-discourse
names.
An interpretation I of a vocabulary V is a set UR , the universe of reference, with a distinguished nonempty
I
subset UD , the universe of discourse, and four mappings:
I
• rel from UR to subsets of UD * = { | x ,…,x ∈ UD } (i.e., the set of finite sequences of
I I I 1 n 1 n I
elements of UD ). Note that the empty sequence is in UD *, for any UD ;
I I I
• fun from UR to total functions from UD * into UD , that is, to functions that map each sequence in
I I I I
UD * to a (unique) element of UD ;
I I
• int from names in V to UR , such that int (v) is in UD if and only if v is a discourse name;
I I I I
NOTE If the dialect recognizes irregular sentences, then they are treated as names of propositions, and int
I
also includes a mapping from the irregular sentences of a text to the truth values { true, false }.
• seq from sequence markers in V to UD *.
I I
© ISO/IEC 2007 – All rights reserved 13

Intuitively, UD is the universe or domain of discourse containing all the individual things the interpretation is
I
'about' and over which the quantifiers range. UR is a potentially larger set of things that might also contain
I
entities which are not in the universe of discourse. In particular, UR might contain relations not in UD to serve
I I
as the interpretations of the non-discourse names in a segregated dialect. All names are interpreted in the
same way, whether or not they are understood to denote something in the universe of discourse; that is why
there is only a single interpretation mapping that applies to all names, regardless of their syntactic role. In
particular, rel (x) is in UD * even when x is not in UD . When considering only segregated dialects, the
I I
I
elements of the universe of reference which are outside the universe of discourse may be identified with their
corresponding values of the rel and fun mappings, which are then re-interpreted to be the identity mapping.
I I
The resulting construction maps predicates directly to relations and operators to functions, yielding a more
traditional interpretation structure for the segregated syntax of traditional first-order logic. On the other hand,
when considering only non-segregated dialects, the distinction between universes of reference and discourse
is unnecessary, since they may be considered to be identical. The distinction is made here in order to give a
uniform treatment of both segregated and non-segregated dialects.
Irregular sentences are treated as though they were arbitrary propositional variables. Note this does not affect
the CL interpretations of any CL sentences which occur as syntactic components of an irregular sentence.
Note also that, although sequence markers are mapped into finite sequences in an interpretation, these
sequences are not denoted by names, and so ar
...