What are the functions of logic

Boolean functions




In a bivalent propositional logic are (suitably specified) statements of a natural or formal language Truth values from the crowd B. rated. The evaluation of a statement with the value 0 means that this statement is "false" (in a certain "real world"), that is, "does not apply" in this world. Correspondingly, other values ​​are also written instead of "0", for example "F" or "falseIf, on the other hand, statement A is evaluated with 1, this means that it is "true" or "applies" in this world. Therefore, instead of "1", the values ​​"W", "true"or" T "is used.

Examples of such statements in natural language are about

"7 is a prime number", which is assigned the truth value 1 (in the "world of natural numbers"), or
"9 is a prime number"which is assigned the truth value 0.

For the connection of (simple) statements to increasingly complex expressions (formulas), certain operations are made available for which it is clearly defined how the truth values ​​of the simple statements determine the truth values ​​of the more complex expressions. One speaks of (logical) junctions, Connectors or Functors. From a mathematical point of view these are functions of different arithmetic. They are also named after George Boole (1815 - 1864), one of the founders of mathematical logic Boolean functions. The one- and two-digit Boolean functions that are possible in principle can be read from the following two tables.

Arity

Here are in the column under the Proposition variables, the one argument of the respective function, the possible values ​​(0 and 1) and then the function value in the relevant line under the function. For example, in the case and in the case.

The column describes the function that assigns the constant value 0 to each statement. So it does not depend on the variable at all and is therefore not called essentially single digits considered. It is briefly mentioned on these web pages 0 designated.

Accordingly, describes the function that assigns the constant value 1 to each statement. It also does not depend on the variable, nor is it called essentially single digits considered. Here she is briefly with 1 designated.

The functions for the columns and on the other hand are the only possible essentially single-digit Boolean functions. The identical function not really needed, so that is the only single-digit logical connector. He will negation or negation called and noted in the form. There are also other spellings such as or usual. It reads as "not A" or "It does not count as A".

Therefore, the statement "¬ (9 is a prime number)" (or equivalent to "9 is not a prime number") is assigned the truth value 1, so it is true.

Arity

A.B.f1f2f3f4f5f6f7f8f9f10f11f12f13f14f15f16
000000000011111111
010000111100001111
100011001100110011
110101010101010101

In addition to the already known constant Boolean functions and, which are also referred to as or for arity (as is the case with every arity), there are other functions that are not essentially two-digit, namely and that only depend on, and and that only depend on. All others are essentially two-digit functions and can therefore be used as separate logical joiners.

The function describes the conjunction or and linkage of the two statements and, written: or also, read: "and" or "both and".

The function describes the Disjunction or alternative or or link of the two statements and, written:, read: "or". The compound statement is then true if at least one of the two partial statements is true, but both may also be true.

In contrast, the function describes the Antivalence or exclusive-or-shortcut of the two statements and, written:, read: "either or". The compound statement is therefore true if and only if exactly one of the two partial statements is true and the other is false. Since the combination of the truth values ​​0 and 1 is the same as the addition modulo 2, one sometimes also writes.

The function describes the implication or Subjunction or logical conclusion or if, then link of the two statements and, written: or or, read: "if, then" or "follows from" or "only if" or "is sufficient for". It is only wrong if the partial statement (the premise) is true and the partial statement (the Conclusion) not correct.

The function describes the logical equivalence or Bijunction or equivalence of the two statements and, written: or, read: "if and only if" or "is equivalent to" or "is necessary and sufficient for".

The function describes the Nihilition or the Peirce arrow (after Charles Sanders Peirce, 1839-1914) or the NOR link of the two statements and, written:, read: "neither nor".

The function describes the intolerance or the Sheffer stroke (after Henry Maurice Sheffer, 1882 - 1964) or the NAND link of the two statements and, written: or, read: "not at the same time and".

The function describes the reverse implication or Replication, read: "if, then" or "if" or "is necessary for". It arises from the implication by interchanging the two arguments and is therefore actually superfluous.

Finally, the two functions are also usually not described by their own connectors, since they can be expressed by the negation and the implication or the reverse implication.

The extent to which some of these connectives can be represented by others in general follows from considerations on the equivalence of formulas.


Author: Udo Hebisch
Date: 08/26/2010