Misplaced Pages

#665334

70-476: The syntax of the IIf function is as follows: All three parameters are required: Many languages have an operator to accomplish the same purpose, generally referred to as a conditional operator (or, less precisely, as a ternary operator); the best known is ?: , as used in C, C++, and related languages. Some of the problems with the IIf function, as discussed later, do not exist with a conditional operator, because

140-456: A is assigned T and b is assigned F , or 4) a is assigned F and b is assigned T . Given any truth assignment for a set of propositional symbols, there is a unique extension to an interpretation for all the propositional formulas built up from those variables. This extended interpretation is defined inductively, using the truth-table definitions of the logical connectives discussed above. Unlike propositional logic, where every language

210-418: A natural number arity is also assigned. The alphabet for the formal language consists of logical constants, the equality relation symbol =, all the symbols from the signature, and an additional infinite set of symbols known as variables. For example, in the language of rings , there are constant symbols 0 and 1, two binary function symbols + and ·, and no binary relation symbols. (Here the equality relation

280-477: A certain sort. One example of many-sorted logic is for planar Euclidean geometry . There are two sorts; points and lines. There is an equality relation symbol for points, an equality relation symbol for lines, and a binary incidence relation E which takes one point variable and one line variable. The intended interpretation of this language has the point variables range over all points on the Euclidean plane ,

350-456: A domain D , a collection of subsets of D , a collection of functions from D to D , etc. The relationship between these two semantics is an important topic in higher order logic. The interpretations of propositional logic and predicate logic described above are not the only possible interpretations. In particular, there are other types of interpretations that are used in the study of non-classical logic (such as intuitionistic logic ), and in

420-478: A fixed set of letters or symbols . The inventory from which these letters are taken is called the alphabet over which the language is defined. To distinguish the strings of symbols that are in a formal language from arbitrary strings of symbols, the former are sometimes called well-formed formulæ (wff). The essential feature of a formal language is that its syntax can be defined without reference to interpretation. For example, we can determine that ( P or Q )

490-455: A formal language for propositional logic are the propositional symbols, which are often denoted by capital letters. To make the formal language precise, a specific set of propositional symbols must be fixed. The standard kind of interpretation in this setting is a function that maps each propositional symbol to one of the truth values true and false. This function is known as a truth assignment or valuation function. In many presentations, it

560-524: A formal language, and as such itself is a syntactic entity. [REDACTED] Media related to Syntax (logic) at Wikimedia Commons 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. The general study of interpretations of formal languages

630-502: 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

700-508: A function that assigns each variable to an element of the domain. Then the T-schema can quantify over variations of the original interpretation in which this variable assignment function is changed, instead of quantifying over substitution instances. Some authors also admit propositional variables in first-order logic, which must then also be interpreted. A propositional variable can stand on its own as an atomic formula. The interpretation of

770-444: A given interpretation of all the sentence letters Φ and Ψ (i.e., after assigning a truth-value to each sentence letter), we can determine the truth-values of all formulas that have them as constituents, as a function of the logical connectives. The following table shows how this kind of thing looks. The first two columns show the truth-values of the sentence letters as determined by the four possible interpretations. The other columns show

SECTION 10

#1732773230666

840-489: A propositional variable is one of the two truth values true and false. Because the first-order interpretations described here are defined in set theory , they do not associate each predicate symbol with a property (or relation), but rather with the extension of that property (or relation). In other words, these first-order interpretations are extensional not intensional . An example of interpretation I {\displaystyle {\mathcal {I}}} of

910-443: A relation symbol across a logical connective, enlarging its scope in the process. Thus it is acceptable for relation symbols to be interpreted as being identically false. However, the interpretation of a function symbol must always assign a well-defined and total function to the symbol. The equality relation is often treated specially in first order logic and other predicate logics. There are two general approaches. The first approach

980-400: A system of arithmetic). A formula A is a syntactic consequence within some formal system F S {\displaystyle {\mathcal {FS}}} of a set Г of formulas if there is a derivation in formal system F S {\displaystyle {\mathcal {FS}}} of A from the set Г. Syntactic consequence does not depend on any interpretation of

1050-540: Is a many-to-one correspondence between certain elementary statements of the theory, and certain statements related to the subject matter. If every elementary statement in the theory has a correspondent it is called a full interpretation , otherwise it is called a partial interpretation . The formal language for propositional logic consists of formulas built up from propositional symbols (also called sentential symbols, sentential variables, propositional variables ) and logical connectives. The only non-logical symbols in

1120-582: Is a set of sentences in a formal language . 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 axioms , 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,

1190-502: Is a well-formed formula even without knowing whether it is true or false. A formal language W {\displaystyle {\mathcal {W}}} can be defined with the alphabet α = { △ , ◻ } {\displaystyle \alpha =\{\triangle ,\square \}} , and with a word being in W {\displaystyle {\mathcal {W}}} if it begins with △ {\displaystyle \triangle } and

1260-415: Is an idea , abstraction or concept , tokens of which may be marks or a metalanguage 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

1330-439: Is an example). When we speak about 'models' in empirical sciences , we mean, if we want reality to be a model of our science, to speak about an intended model . A model in the empirical sciences is an intended factually-true descriptive interpretation (or in other contexts: a non-intended arbitrary interpretation used to clarify such an intended factually-true descriptive interpretation.) All models are interpretations that have

1400-576: Is anything having to do with formal languages or formal systems 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 , systems , theorems and proofs 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

1470-649: Is at compile time unrolled to conditional statements. In this example a new strong type string named "someString" is created (using Type inference ) and the iif function will fill it depending on the outcome of the boolean expression. SQL Server 2012 and newer implements the IIF() function ( Transact-SQL ): IIf in C (and its variants) and Perl is the ?: conditional operator : IIf in Python : IIf (either) in Red and Rebol : Syntax (logic) In logic , syntax

SECTION 20

#1732773230666

1540-404: Is called formal semantics . The most commonly studied formal logics are propositional logic , predicate logic and their modal analogs, and for these there are standard ways of presenting an interpretation. In these contexts an interpretation is a function that provides the extension of symbols and strings of symbols of an object language. For example, an interpretation function could take

1610-665: Is composed solely of the symbols △ {\displaystyle \triangle } and ◻ {\displaystyle \square } . A possible interpretation of W {\displaystyle {\mathcal {W}}} could assign the decimal digit '1' to △ {\displaystyle \triangle } and '0' to ◻ {\displaystyle \square } . Then △ ◻ △ {\displaystyle \triangle \square \triangle } would denote 101 under this interpretation of W {\displaystyle {\mathcal {W}}} . In

1680-434: Is different sorts of variables represent different types of objects. Every sort of variable can be quantified; thus an interpretation for a many-sorted language has a separate domain for each of the sorts of variables to range over (there is an infinite collection of variables of each of the different sorts). Function and relation symbols, in addition to having arities, are specified so that each of their arguments must come from

1750-600: Is directly derivable from a sentence I i {\displaystyle {\mathcal {I}}_{i}} , then I i → I j {\displaystyle {\mathcal {I}}_{i}\to {\mathcal {I}}_{j}} turns out to be a true sentence, with → {\displaystyle \to } meaning implication , as usual. These requirements ensure that all provable sentences also come out to be true. Most formal systems have many more models than they were intended to have (the existence of non-standard models

1820-428: Is intended to represent set membership, and the domain of discourse in a first-order theory of the natural numbers is intended to be the set of natural numbers. The intended interpretation is called the standard model (a term introduced by Abraham Robinson in 1960). In the context of Peano arithmetic , it consists of the natural numbers with their ordinary arithmetical operations. All models that are isomorphic to

1890-467: Is known as a normal model , so this second approach is the same as only studying interpretations that happen to be normal models. The advantage of this approach is that the axioms related to equality are automatically satisfied by every normal model, and so they do not need to be explicitly included in first-order theories when equality is treated this way. This second approach is sometimes called first order logic with equality , but many authors adopt it for

1960-461: Is literally a truth value that is assigned, but some presentations assign truthbearers instead. For a language with n distinct propositional variables there are 2 distinct possible interpretations. For any particular variable a , for example, there are 2 =2 possible interpretations: 1) a is assigned T , or 2) a is assigned F . For the pair a , b there are 2 =4 possible interpretations: 1) both are assigned T , 2) both are assigned F , 3)

2030-491: Is little additional generality in studying non-normal models. Second, if non-normal models are considered, then every consistent theory has an infinite model; this affects the statements of results such as the Löwenheim–Skolem theorem , which are usually stated under the assumption that only normal models are considered. A generalization of first order logic considers languages with more than one sort of variables. The idea

2100-426: Is made True by the negation function. That would make F True again, since one of F s disjuncts, ¬Φ, would be true under this interpretation. Since these two interpretations for F are the only possible logical interpretations, and since F comes out True for both, we say that it is logically valid or tautologous. An interpretation of a theory is the relationship between a theory and some subject matter when there

2170-593: Is not a free variable of φ, are logically valid. This equivalence holds in every interpretation with a nonempty domain, but does not always hold when empty domains are permitted. For example, the equivalence [ ∀ y ( y = y ) ∨ ∃ x ( x = x ) ] ≡ ∃ x [ ∀ y ( y = y ) ∨ x = x ] {\displaystyle [\forall y(y=y)\lor \exists x(x=x)]\equiv \exists x[\forall y(y=y)\lor x=x]} fails in any structure with an empty domain. Thus

IIf - Misplaced Pages Continue

2240-437: Is not determined by the interpretation function. An interpretation often (but not always) provides a way to determine the truth values of sentences in a language. If a given interpretation assigns the value True to a sentence or theory , the interpretation is called a model of that sentence or theory. A formal language consists of a possibly infinite set of sentences (variously called words or formulas ) built from

2310-512: Is satisfied by every interpretation that satisfies ψ then φ is said to be a logical consequence of ψ). Some of the logical symbols of a language (other than quantifiers) are truth-functional connectives that represent truth functions — functions that take truth values as arguments and return truth values as outputs (in other words, these are operations on truth values of sentences). The truth-functional connectives enable compound sentences to be built up from simpler sentences. In this way,

2380-402: Is satisfied. Strictly speaking, a substitution instance such as the formula φ( d ) mentioned above is not a formula in the original formal language of φ, because d is an element of the domain. There are two ways of handling this technical issue. The first is to pass to a larger language in which each element of the domain is named by a constant symbol. The second is to add to the interpretation

2450-487: Is sufficiently powerful, such as the Peano axioms , can be both consistent and complete. 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 model . An interpretation is expressed in a metalanguage , which may itself be

2520-538: 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). A proposition is a sentence 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 truthbearers . A formal theory

2590-495: Is taken as a logical constant.) Again, we might define a first-order language L , as consisting of individual symbols a, b, and c; predicate symbols F, G, H, I and J; variables x, y, z; no function letters; no sentential symbols. Given a signature σ, the corresponding formal language is known as the set of σ-formulas. Each σ-formula is built up out of atomic formulas by means of logical connectives; atomic formulas are built from terms using predicate symbols. The formal definition of

2660-403: Is the same apart from a choice of a different set of propositional variables, there are many different first-order languages. Each first-order language is defined by a signature . The signature consists of a set of non-logical symbols and an identification of each of these symbols as either a constant symbol, a function symbol, or a predicate symbol . In the case of function and predicate symbols,

2730-409: Is to treat equality as no different than any other binary relation. In this case, if an equality symbol is included in the signature, it is usually necessary to add various axioms about equality to axiom systems (for example, the substitution axiom saying that if a = b and R ( a ) holds then R ( b ) holds as well). This approach to equality is most useful when studying signatures that do not include

2800-404: Is true or false. The following example uses IIf: It could also be written in the following way, using standard conditionals : The above example would also eliminate the problem of IIf evaluating both its truepart and falsepart parameters. Visual Basic 2008 (VB 9.0) introduced a true conditional operator , called simply "If", which also eliminates this problem. Its syntax is similar to

2870-405: Is usually associated with the rules (or grammar) governing the composition of texts in a formal language that constitute the well-formed formulas of a formal system. In computer science , the term syntax refers to the rules governing the composition of well-formed expressions in a programming language . As in mathematical logic, it is independent of semantics and interpretation. A symbol

IIf - Misplaced Pages Continue

2940-470: The IIf() call less useful than the conditional operator. To solve this issue, Microsoft developers had considered converting IIf to an intrinsic function; had this happened, the compiler would have been able to perform type inference and short-circuiting by replacing the function call with inline code. In Visual Basic , IIf is not the sole way to evaluate and perform actions based on whether an expression

3010-511: The data type of its arguments is Variant . If the function is called with arguments of other types (variables or literals), there will be additional overhead to convert these to Variant . There may also be additional overhead to check the argument types and convert one of them if they do not have the same type. Another issue with IIf arises because it is a library function: unlike the C-derived conditional operator, both truepart and

3080-435: The falsepart will be evaluated regardless of which one is actually returned. In the following code snippet: although TrueFunction is the function intended to be called, IIf will call both TrueFunction and FalseFunction . Similarly, While the intent may be to avoid a division by zero, whenever b is zero the error will actually happen. This is because the code in the snippet is executed as if by This issue makes

3150-464: The IIf function's syntax: $ iif() is present in mIRC script, with similar syntax. Calling /testiif will print out "testing $ iif: 1 execution(s)". mIRC's $ iif acts more like C's ?: than IIf() in VB since it won't pre-evaluate both. IIF() is a function in dBase and xBase (1992 and older). iif() is also a compiler magic function of Oxygene . It is not a real function and

3220-427: The area of investigation. Logical constants are always given the same meaning by every interpretation of the standard kind, so that only the meanings of the non-logical symbols are changed. Logical constants include quantifier symbols ∀ ("all") and ∃ ("some"), symbols for logical connectives ∧ ("and"), ∨ ("or"), ¬ ("not"), parentheses and other grouping symbols, and (in many treatments) the equality symbol =. Many of

3290-443: The commonly studied interpretations associate each sentence in a formal language with a single truth value, either True or False. These interpretations are called truth functional ; they include the usual interpretations of propositional and first-order logic. The sentences that are made true by a particular assignment are said to be satisfied by that assignment. In classical logic , no sentence can be made both true and false by

3360-499: The correct type (all subsets of the domain, all functions from the domain to itself, etc.). Thus the specification of a full interpretation is the same as the specification of a first-order interpretation. Henkin semantics , which are essentially multi-sorted first-order semantics, require the interpretation to specify a separate domain for each type of higher-order variable to range over. Thus an interpretation in Henkin semantics includes

3430-405: The creator of the language, usually by specifying a set of formation rules . Such a language can be defined without reference to any meanings of any of its expressions; it can exist before any interpretation is assigned to it – that is, before it has any meaning. Formation rules are a precise description of which strings of symbols are the well-formed formulas of a formal language. It

3500-421: The domain, functions from the domain, functions that take a subset of the domain and return a function from the domain to subsets of the domain, etc. All of these types of variables can be quantified. There are two kinds of interpretations commonly employed for higher-order logic. Full semantics require that, once the domain of discourse is satisfied, the higher-order variables range over all possible elements of

3570-459: The domain. The truth value of an arbitrary sentence is then defined inductively using the T-schema , which is a definition of first-order semantics developed by Alfred Tarski. The T-schema interprets the logical connectives using truth tables, as discussed above. Thus, for example, φ ∧ ψ is satisfied if and only if both φ and ψ are satisfied. This leaves the issue of how to interpret formulas of

SECTION 50

#1732773230666

3640-429: The equality relation, such as the signature for set theory or the signature for second-order arithmetic in which there is only an equality relation for numbers, but not an equality relation for set of numbers. The second approach is to treat the equality relation symbol as a logical constant that must be interpreted by the real equality relation in any interpretation. An interpretation that interprets equality this way

3710-412: The form ∀ x φ( x ) and ∃ x φ( x ) . The domain of discourse forms the range for these quantifiers. The idea is that the sentence ∀ x φ( x ) is true under an interpretation exactly when every substitution instance of φ( x ), where x is replaced by some element of the domain, is satisfied. The formula ∃ x φ( x ) is satisfied if there is at least one element d of the domain such that φ( d )

3780-400: The formal system. A formal system S {\displaystyle {\mathcal {S}}} 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 S {\displaystyle {\mathcal {S}}} . In another sense,

3850-408: 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. A formal language is a syntactic entity which consists of a set of finite strings of symbols which are its words (usually called its well-formed formulas ). Which strings of symbols are words is determined by

3920-422: The general study of first-order logic without comment. There are a few other reasons to restrict study of first-order logic to normal models. First, it is known that any first-order interpretation in which equality is interpreted by an equivalence relation and satisfies the substitution axioms for equality can be cut down to an elementarily equivalent interpretation on a subset of the original domain. Thus there

3990-609: The language L described above is as follows. In the interpretation I {\displaystyle {\mathcal {I}}} of L: As stated above, a first-order interpretation is usually required to specify a nonempty set as the domain of discourse. The reason for this requirement is to guarantee that equivalences such as ( ϕ ∨ ∃ x ψ ) ↔ ∃ x ( ϕ ∨ ψ ) , {\displaystyle (\phi \lor \exists x\psi )\leftrightarrow \exists x(\phi \lor \psi ),} where x

4060-423: The language is free to examine the type and delay evaluation of the operands, as opposed to simply passing them to a library function. These examples evaluate mathematical expressions and return one of two strings depending on the outcome. Because IIf is a library function, it will always require the overhead of a function call, whereas a conditional operator will more likely produce inline code. Furthermore,

4130-473: The line variable range over all lines on the plane, and the incidence relation E ( p , l ) holds if and only if point p is on line l . A formal language for higher-order predicate logic looks much the same as a formal language for first-order logic. The difference is that there are now many different types of variables. Some variables correspond to elements of the domain, as in first-order logic. Other variables correspond to objects of higher type: subsets of

4200-493: The logical connectives and quantifiers. To ascribe meaning to all sentences of a first-order language, the following information is needed. An object carrying this information is known as a structure (of signature σ), or σ-structure, or L -structure (of language L), or as a "model". The information specified in the interpretation provides enough information to give a truth value to any atomic formula, after each of its free variables , if any, has been replaced by an element of

4270-432: The one just given are also called standard; these models all satisfy the Peano axioms . There are also non-standard models of the (first-order version of the) Peano axioms , which contain elements not correlated with any natural number. While the intended interpretation can have no explicit indication in the strictly formal syntactical rules , it naturally affects the choice of the formation and transformation rules of

SECTION 60

#1732773230666

4340-460: The predicate T (for "tall") and assign it the extension { a } (for "Abraham Lincoln"). All our interpretation does is assign the extension {a} to the non-logical constant T , and does not make a claim about whether T is to stand for tall and 'a' for Abraham Lincoln. Nor does logical interpretation have anything to say about logical connectives like 'and', 'or' and 'not'. Though we may take these symbols to stand for certain things or concepts, this

4410-399: The proof theory of first-order logic becomes more complicated when empty structures are permitted. However, the gain in allowing them is negligible, as both the intended interpretations and the interesting interpretations of the theories people study have non-empty domains. Empty relations do not cause any problem for first-order interpretations, because there is no similar notion of passing

4480-423: The same interpretation, although this is not true of glut logics such as LP. Even in classical logic, however, it is possible that the truth value of the same sentence can be different under different interpretations. A sentence is consistent if it is true under at least one interpretation; otherwise it is inconsistent . A sentence φ is said to be logically valid if it is satisfied by every interpretation (if φ

4550-441: The set of σ-formulas proceeds in the other direction: first, terms are assembled from the constant and function symbols together with the variables. Then, terms can be combined into an atomic formula using a predicate symbol (relation symbol) from the signature or the special predicate symbol "=" for equality (see the section " Interpreting equality" below). Finally, the formulas of the language are assembled from atomic formulas using

4620-400: The specific cases of propositional logic and predicate logic, the formal languages considered have alphabets that are divided into two sets: the logical symbols ( logical constants ) and the non-logical symbols. The idea behind this terminology is that logical symbols have the same meaning regardless of the subject matter being studied, while non-logical symbols change in meaning depending on

4690-405: The study of modal logic. Interpretations used to study non-classical logic include topological models , Boolean-valued models , and Kripke models . Modal logic is also studied using Kripke models. Many formal languages are associated with a particular interpretation that is used to motivate them. For example, the first-order signature for set theory includes only one binary relation, ∈, which

4760-457: The syntactical system. For example, primitive signs must permit expression of the concepts to be modeled; sentential formulas are chosen so that their counterparts in the intended interpretation are meaningful declarative sentences ; primitive sentences need to come out as true sentences in the interpretation; rules of inference must be such that, if the sentence I j {\displaystyle {\mathcal {I}}_{j}}

4830-410: The truth value of the compound sentence is defined as a certain truth function of the truth values of the simpler sentences. The connectives are usually taken to be logical constants , meaning that the meaning of the connectives is always the same, independent of what interpretations are given to the other symbols in a formula. This is how we define logical connectives in propositional logic: So under

4900-450: The truth-values of formulas built from these sentence letters, with truth-values determined recursively. Now it is easier to see what makes a formula logically valid. Take the formula F : (Φ ∨ ¬Φ). If our interpretation function makes Φ True, then ¬Φ is made False by the negation connective. Since the disjunct Φ of F is True under that interpretation, F is True. Now the only other possible interpretation of Φ makes it False, and if so, ¬Φ

#665334