Syntax (logic)
Encyclopedia
In logic
, syntax is anything having to do with formal language
s or formal system
s without regard to any interpretation
or meaning
given to them. Syntax is concerned with the rules used for constructing, or transforming the symbols and words of a language, as contrasted with the semantics of a language which is concerned with its meaning.
The symbols
, formulas
, system
s, theorem
s, proofs
, and interpretations
expressed in formal languages are syntactic entities whose properties may be studied without regard to any meaning they may be given, and, in fact, need not be given any.
Syntax is usually associated with the rules (or grammar) governing the composition of texts in a formal language that constitute the well-formed formula
s of a formal system.
In computer science
, the term syntax
refers to the rules governing the composition of meaningful texts in a formal language, such as a programming language
, that is, those texts for which it makes sense to define the semantics
or meaning, or otherwise provide an interpretation.
, abstraction
or concept
, tokens
of which may be marks or a configuration of marks which form a particular pattern. Symbols of a formal language need not be symbols of anything. For instance there are logical constants which do not refer to any idea, but rather serve as a form of punctuation in the language (e.g. parentheses). A symbol or string of symbols may comprise a well-formed formula if the formulation is consistent with the formation rules of the language. Symbols of a formal language must be capable of being specified without any reference to any interpretation of them.
of symbol
s which are its words (usually called its well-formed formula
s). Which strings of symbols are words is determined by fiat by the creator of the language, usually by specifying a set of formation rule
s. Such a language can be defined without reference
to any meaning
s of any of its expressions; it can exist before any interpretation
is assigned to it – that is, before it has any meaning.
of symbol
s are the well-formed formula
s of a formal language. It is synonymous with the set of strings
over the alphabet
of the formal language which constitute well formed formulas. However, it does not describe their semantics
(i.e. what they mean).
expressing something true
or false
. A proposition is identified ontologically
as an idea
, concept
or abstraction
whose token instances
are patterns of symbols
, marks, sounds, or strings
of words. Propositions are considered to be syntactic entities and also truthbearer
s.
s in a formal language
.
s, or have both. A formal system is used to derive
one expression from one or more other expressions. Formal systems, like other syntactic entities may be defined without any interpretation
given to it (as being, for instance, a system of arithmetic).
of a set Г of formulas if there is a formal proof
in formal system
of A from the set Г.
Syntactic consequence does not depend on any interpretation
of the formal system.
is syntactically complete (also deductively complete, maximally complete, negation complete or simply complete) iff for each formula A of the language of the system either A or ¬A is a theorem of 
. In another sense, a formal system is syntactically complete iff no unprovable axiom can be added to it as an axiom without introducing an inconsistency
. Truth-functional propositional logic and first-order predicate logic
are semantically complete, but not syntactically complete (for example the propositional logic statement consisting of a single variable "a" is not a theorem, and neither is its negation, but these are not tautologies
). Gödel's incompleteness theorem shows that no recursive system that is sufficiently powerful, such as the Peano axioms
, can be both consistent and complete.
. An interpretation is expressed in a metalanguage
, which may itself be a formal language, and as such itself is a syntactic entity.
Logic
In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...
, syntax is anything having to do with formal language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
s or formal system
Formal system
In formal logic, a formal system consists of a formal language and a set of inference rules, used to derive an expression from one or more other premises that are antecedently supposed or derived . The axioms and rules may be called a deductive apparatus...
s without regard to any interpretation
Interpretation (logic)
An interpretation is an assignment of meaning to the symbols of a formal language. Many formal languages used in mathematics, logic, and theoretical computer science are defined in solely syntactic terms, and as such do not have any meaning until they are given some interpretation...
or meaning
Meaning (linguistics)
In linguistics, meaning is what is expressed by the writer or speaker, and what is conveyed to the reader or listener, provided that they talk about the same thing . In other words if the object and the name of the object and the concepts in their head are the same...
given to them. Syntax is concerned with the rules used for constructing, or transforming the symbols and words of a language, as contrasted with the semantics of a language which is concerned with its meaning.
The symbols
Symbol (formal)
For other uses see Symbol In logic, symbols build literal utility to illustrate ideas. A symbol is an abstraction, tokens of which may be marks or a configuration of marks which form a particular pattern...
, formulas
Well-formed formula
In mathematical logic, a well-formed formula, shortly wff, often simply formula, is a word which is part of a formal language...
, system
Formal system
In formal logic, a formal system consists of a formal language and a set of inference rules, used to derive an expression from one or more other premises that are antecedently supposed or derived . The axioms and rules may be called a deductive apparatus...
s, theorem
Theorem
In mathematics, a theorem is a statement that has been proven on the basis of previously established statements, such as other theorems, and previously accepted statements, such as axioms...
s, proofs
Formal proof
A formal proof or derivation is a finite sequence of sentences each of which is an axiom or follows from the preceding sentences in the sequence by a rule of inference. The last sentence in the sequence is a theorem of a formal system...
, and interpretations
Interpretation (logic)
An interpretation is an assignment of meaning to the symbols of a formal language. Many formal languages used in mathematics, logic, and theoretical computer science are defined in solely syntactic terms, and as such do not have any meaning until they are given some interpretation...
expressed in formal languages are syntactic entities whose properties may be studied without regard to any meaning they may be given, and, in fact, need not be given any.
Syntax is usually associated with the rules (or grammar) governing the composition of texts in a formal language that constitute the well-formed formula
Well-formed formula
In mathematical logic, a well-formed formula, shortly wff, often simply formula, is a word which is part of a formal language...
s of a formal system.
In computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, the term syntax
Syntax of programming languages
In computer science, the syntax of a programming language is the set of rules that define the combinations of symbols that are considered to be correctly structured programs in that language. The syntax of a language defines its surface form...
refers to the rules governing the composition of meaningful texts in a formal language, such as a programming language
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
, that is, those texts for which it makes sense to define the semantics
Semantics
Semantics is the study of meaning. It focuses on the relation between signifiers, such as words, phrases, signs and symbols, and what they stand for, their denotata....
or meaning, or otherwise provide an interpretation.
Symbols
A symbol is an ideaIdea
In the most narrow sense, an idea is just whatever is before the mind when one thinks. Very often, ideas are construed as representational images; i.e. images of some object. In other contexts, ideas are taken to be concepts, although abstract concepts do not necessarily appear as images...
, abstraction
Abstraction
Abstraction is a process by which higher concepts are derived from the usage and classification of literal concepts, first principles, or other methods....
or concept
Concept
The word concept is used in ordinary language as well as in almost all academic disciplines. Particularly in philosophy, psychology and cognitive sciences the term is much used and much discussed. WordNet defines concept: "conception, construct ". However, the meaning of the term concept is much...
, tokens
Type-token distinction
In disciplines such as philosophy and knowledge representation, the type-token distinction is a distinction that separates an abstract concept from the objects which are particular instances of the concept...
of which may be marks or a configuration of marks which form a particular pattern. Symbols of a formal language need not be symbols of anything. For instance there are logical constants which do not refer to any idea, but rather serve as a form of punctuation in the language (e.g. parentheses). A symbol or string of symbols may comprise a well-formed formula if the formulation is consistent with the formation rules of the language. Symbols of a formal language must be capable of being specified without any reference to any interpretation of them.
Formal language
A formal language is a syntactic entity which consists of a set of finite stringsString (computer science)
In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....
of symbol
Symbol (formal)
For other uses see Symbol In logic, symbols build literal utility to illustrate ideas. A symbol is an abstraction, tokens of which may be marks or a configuration of marks which form a particular pattern...
s which are its words (usually called its well-formed formula
Well-formed formula
In mathematical logic, a well-formed formula, shortly wff, often simply formula, is a word which is part of a formal language...
s). Which strings of symbols are words is determined by fiat by the creator of the language, usually by specifying a set of formation rule
Formation rule
In mathematical logic, formation rules are rules for describing which strings of symbols formed from the alphabet of a formal language are syntactically valid within the language. These rules only address the location and manipulation of the strings of the language. It does not describe anything...
s. Such a language can be defined without reference
Reference
Reference is derived from Middle English referren, from Middle French rèférer, from Latin referre, "to carry back", formed from the prefix re- and ferre, "to bear"...
to any meaning
Meaning (linguistics)
In linguistics, meaning is what is expressed by the writer or speaker, and what is conveyed to the reader or listener, provided that they talk about the same thing . In other words if the object and the name of the object and the concepts in their head are the same...
s of any of its expressions; it can exist before any interpretation
Interpretation (logic)
An interpretation is an assignment of meaning to the symbols of a formal language. Many formal languages used in mathematics, logic, and theoretical computer science are defined in solely syntactic terms, and as such do not have any meaning until they are given some interpretation...
is assigned to it – that is, before it has any meaning.
Formation rules
Formation rules are a precise description of which stringsString (computer science)
In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....
of symbol
Symbol (formal)
For other uses see Symbol In logic, symbols build literal utility to illustrate ideas. A symbol is an abstraction, tokens of which may be marks or a configuration of marks which form a particular pattern...
s are the well-formed formula
Well-formed formula
In mathematical logic, a well-formed formula, shortly wff, often simply formula, is a word which is part of a formal language...
s of a formal language. It is synonymous with the set of strings
String (computer science)
In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....
over the alphabet
Alphabet
An alphabet is a standard set of letters—basic written symbols or graphemes—each of which represents a phoneme in a spoken language, either as it exists now or as it was in the past. There are other systems, such as logographies, in which each character represents a word, morpheme, or semantic...
of the formal language which constitute well formed formulas. However, it does not describe their semantics
Semantics
Semantics is the study of meaning. It focuses on the relation between signifiers, such as words, phrases, signs and symbols, and what they stand for, their denotata....
(i.e. what they mean).
Propositions
A proposition is a sentenceSentence (linguistics)
In the field of linguistics, a sentence is an expression in natural language, and often defined to indicate a grammatical unit consisting of one or more words that generally bear minimal syntactic relation to the words that precede or follow it...
expressing something true
Truth
Truth has a variety of meanings, such as the state of being in accord with fact or reality. It can also mean having fidelity to an original or to a standard or ideal. In a common usage, it also means constancy or sincerity in action or character...
or false
Falsity
Falsity or falsehood is a perversion of truth originating in the deceitfulness of one party, and culminating in the damage of another party...
. A proposition is identified ontologically
Ontology
Ontology is the philosophical study of the nature of being, existence or reality as such, as well as the basic categories of being and their relations...
as an idea
Idea
In the most narrow sense, an idea is just whatever is before the mind when one thinks. Very often, ideas are construed as representational images; i.e. images of some object. In other contexts, ideas are taken to be concepts, although abstract concepts do not necessarily appear as images...
, concept
Concept
The word concept is used in ordinary language as well as in almost all academic disciplines. Particularly in philosophy, psychology and cognitive sciences the term is much used and much discussed. WordNet defines concept: "conception, construct ". However, the meaning of the term concept is much...
or abstraction
Abstraction
Abstraction is a process by which higher concepts are derived from the usage and classification of literal concepts, first principles, or other methods....
whose token instances
Type-token distinction
In disciplines such as philosophy and knowledge representation, the type-token distinction is a distinction that separates an abstract concept from the objects which are particular instances of the concept...
are patterns of symbols
Symbol (formal)
For other uses see Symbol In logic, symbols build literal utility to illustrate ideas. A symbol is an abstraction, tokens of which may be marks or a configuration of marks which form a particular pattern...
, marks, sounds, or strings
String (computer science)
In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....
of words. Propositions are considered to be syntactic entities and also truthbearer
Truthbearer
Truth-bearer is a term used to designate entities that are either true or false and nothing else. The thesis that some things are true while others are false raises the question of the nature of these things. Since there is divergence of opinion on the matter, the term truthbearer is used to be...
s.
Formal theories
A formal theory is a set of sentenceSentence (mathematical logic)
In mathematical logic, a sentence of a predicate logic is a boolean-valued well formed formula with no free variables. A sentence can be viewed as expressing a proposition, something that may be true or false...
s in a formal language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
.
Formal systems
A formal system (also called a logical calculus, or a logical system) consists of a formal language together with a deductive apparatus (also called a deductive system). The deductive apparatus may consist of a set of transformation rules (also called inference rules) or a set of axiomAxiom
In traditional logic, an axiom or postulate is a proposition that is not proven or demonstrated but considered either to be self-evident or to define and delimit the realm of analysis. In other words, an axiom is a logical statement that is assumed to be true...
s, or have both. A formal system is used to derive
Proof theory
Proof theory is a branch of mathematical logic that represents proofs as formal mathematical objects, facilitating their analysis by mathematical techniques. Proofs are typically presented as inductively-defined data structures such as plain lists, boxed lists, or trees, which are constructed...
one expression from one or more other expressions. Formal systems, like other syntactic entities may be defined without any interpretation
Interpretation (logic)
An interpretation is an assignment of meaning to the symbols of a formal language. Many formal languages used in mathematics, logic, and theoretical computer science are defined in solely syntactic terms, and as such do not have any meaning until they are given some interpretation...
given to it (as being, for instance, a system of arithmetic).
Syntactic consequence within a formal system
A formula A is a syntactic consequence within some formal system of a set Г of formulas if there is a formal proofDerivation
Derivation may refer to:* Derivation , a function on an algebra which generalizes certain features of the derivative operator* Derivation * Derivation in differential algebra, a unary function satisfying the Leibniz product law...
in formal system
Formal system
In formal logic, a formal system consists of a formal language and a set of inference rules, used to derive an expression from one or more other premises that are antecedently supposed or derived . The axioms and rules may be called a deductive apparatus...
of A from the set Г.Syntactic consequence does not depend on any interpretation
Interpretation (logic)
An interpretation is an assignment of meaning to the symbols of a formal language. Many formal languages used in mathematics, logic, and theoretical computer science are defined in solely syntactic terms, and as such do not have any meaning until they are given some interpretation...
of the formal system.
Syntactic completeness of a formal system
A formal system is syntactically complete (also deductively complete, maximally complete, negation complete or simply complete) iff for each formula A of the language of the system either A or ¬A is a theorem of . In another sense, a formal system is syntactically complete iff no unprovable axiom can be added to it as an axiom without introducing an inconsistencyConsistency
Consistency can refer to:* Consistency , the psychological need to be consistent with prior acts and statements* "Consistency", an 1887 speech by Mark Twain...
. Truth-functional propositional logic and first-order predicate logic
Predicate logic
In mathematical logic, predicate logic is the generic term for symbolic formal systems like first-order logic, second-order logic, many-sorted logic or infinitary logic. This formal system is distinguished from other systems in that its formulae contain variables which can be quantified...
are semantically complete, but not syntactically complete (for example the propositional logic statement consisting of a single variable "a" is not a theorem, and neither is its negation, but these are not tautologies
Tautology (logic)
In logic, a tautology is a formula which is true in every possible interpretation. Philosopher Ludwig Wittgenstein first applied the term to redundancies of propositional logic in 1921; it had been used earlier to refer to rhetorical tautologies, and continues to be used in that alternate sense...
). Gödel's incompleteness theorem shows that no recursive system that is sufficiently powerful, such as the Peano axioms
Peano axioms
In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are a set of axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano...
, can be both consistent and complete.
Interpretations
An interpretation of a formal system is the assignment of meanings to the symbols, and truth values to the sentences of a formal system. The study of interpretations is called formal semantics. Giving an interpretation is synonymous with constructing a modelStructure (mathematical logic)
In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations which are defined on it....
. An interpretation is expressed in a metalanguage
Metalanguage
Broadly, any metalanguage is language or symbols used when language itself is being discussed or examined. In logic and linguistics, a metalanguage is a language used to make statements about statements in another language...
, which may itself be a formal language, and as such itself is a syntactic entity.
See also
- Symbol (formal)Symbol (formal)For other uses see Symbol In logic, symbols build literal utility to illustrate ideas. A symbol is an abstraction, tokens of which may be marks or a configuration of marks which form a particular pattern...
- Formation ruleFormation ruleIn mathematical logic, formation rules are rules for describing which strings of symbols formed from the alphabet of a formal language are syntactically valid within the language. These rules only address the location and manipulation of the strings of the language. It does not describe anything...
- Formal grammarFormal grammarA formal grammar is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax...
- Syntax (linguistics)SyntaxIn linguistics, syntax is the study of the principles and rules for constructing phrases and sentences in natural languages....
- Syntax (programming languages)
- Mathematical logicMathematical logicMathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
- Well-formed formulaWell-formed formulaIn mathematical logic, a well-formed formula, shortly wff, often simply formula, is a word which is part of a formal language...