Propositional calculus

Propositional logic is a branch of logic that deals with statements and their linkage by connectives, starting from structureless elementary propositions ( atoms), where a truth value is assigned. In classical propositional logic, each statement is exactly one of the two truth values ​​"true" and assigned "false". The truth value of a compound statement can be determined without additional information from the truth values ​​of its sub- statements.

• 4.1 Introduction
• 4.2 syntax 4.2.1 components of the propositional language
• 4.2.2 Formation rules
• 4.2.3 Final Rules
• 4.2.4 axioms
• 4.2.5 Derivation and proof

• 4.3.1 Semantic validity, tautologies
• 4.3.2 Important semantic properties: satisfiability, falsifiability and unsatisfiability
• 4.3.3 Algebraic view
• 4.3.4 Normal Forms

History

Historically, the propositional logic goes back to Aristotle, who discussed the first time propositional principles, namely in his metaphysics the principle of contradiction and the law of excluded middle, and the theme of a indirect evidence in his first analysis. The bivalent propositional semantics developed somewhat later, the Megarian philosopher Diodorus Cronus and Philo. The statements and axiomatic semantics combined the Stoic Chrysippus of Soli, who formulated the first propositional calculus. The development of the propositional logic of the Stoics through the Middle Ages is often overlooked. A first complete and decidable formalization of propositional tautologies - though not yet for the propositional Close - George Boole created in 1847 with his algebraic logic calculus. The first propositional calculus with inference rules formulated Gottlob Frege as part of his Begriffsschrift in 1879. He was the template for the propositional calculus by Bertrand Russell in 1910, which later prevailed (see below).

To distinguish the classical propositional logic

Because in today's mathematics classical propositional logic has been instrumental in this article, this modern main type of propositional logic is handled. In general, the classical logic is characterized by two properties:

• Each statement has one of exactly two truth values, mostly "false" or "true" (the principle of bivalence or bivalence ).
• The truth value of each composite statement is uniquely determined by the truth values ​​of its sub-statements (the principle of extensionality or compositionality, see extensionality )

The principle of bivalence is often confused with the law of excluded middle.

The classical propositional logic is that field of classical logic, which studies the internal structure of sentences ( statements ) then, from which other sets ( subsets ) they are composed and how these subsets are linked. The internal structure of sentences that can not be broken down into further sub- sets in turn is not considered by the propositional logic. For example, the statement " All cats are dogs, and the earth is flat " is the conjunction ' and ' between the two shorter statements " All cats are dogs " and " The earth is flat " composed. These two statements are in turn no longer broken down into further statements that are made of propositional view so elementary or atomic. Others, built on propositional logic logical systems consider the internal structure of such atomic propositions; an important example is the predicate logic.

In contrast to classical logic do not arise classical logic systems when you pick up the principle of bivalence, the principle of extensionality or even both principles. Non-classical logics that arise from the abolition of the principle of bivalence, called multi-valued logic. The number of truth values ​​(in this case the usual: Pseudo- truth values) may be finite (eg, three-valued logic ), but is often infinite ( eg, fuzzy logic). In contrast, using logic that caused by removal of extensionality, connectives ( connectives ) in which the truth value of the composite set can no longer be unambiguously determined from the truth values ​​of its parts. An example of nichtextensionale logic is the modal logic that. Nichtextensionalen the digit operators " it is necessary that " and "it is possible that " introduces

Logical systems are not in a competitive relationship to truth or correctness in the logic. The question of which logic system to be used for a particular purpose, is more pragmatic.

Often logical systems and logical questions to be confused with non- logical questions or mixed, for example, with the metaphysical question of what logical system "right" is, that is the reality describing. There are differing views on this question, including the positivist position, that this question is meaningless. However, these issues are covered in other areas, such as philosophy, philosophy of science and linguistics.

If the classical propositional logic is discussed in this article, that is not to be understood as a metaphysical definition or even as an assertion that "all statements are true or false." There is only so that the classical propositional logic simply treated only those statements that are true or false. This is a large formal simplification that can be relatively easy to learn this system. Do we need from metaphysical or pragmatic reasons more than two truth values ​​, the classical propositional logic can serve as a starting point to set up a suitable logical system.

Colloquial Introduction

Simple statement ( elementary statement )

→ Main article: Statement ( logic)

A statement A is a sentence that is either true (w, true, true, 1 ) or not true ( f, false, false, 0). This applies to both simple as well as for related statements. " Half-truths " does not exist. A statement can be both ordinary language come from and the language of mathematics. An elementary proposition is a statement that no propositional operations ( not, and, or, if ... then, if and only if ) includes.

Examples of elementary propositions:

• Munich is 781 km away from Hamburg.
• : 9 is divisible by 3.
• Eintracht Frankfurt is in the next season German football champions.
• All cars are green.

Is obviously true, however, is wrong. you have to consider first before you can decide whether is true or false. Whether is true, you can not decide now. This will turn out until the end of next football season.

In classical propositional logic a statement is either true or not true, even if you do not know the truth. That is, for example, in the unsolved mathematical problems the case.

Note: is an all- statement; the structure of such statements is subject to the predicate logic. In terms of propositional logic, it is an elementary statement.

Negated statement - negation

→ Main article: Negation

The denial or negation (also: sentence negation, external negation, contradictory opposite ) a statement A statement is that ¬ A, which is only true if A is false, and that is just wrong then, if A is true. Simple: The negation of a statement A rotates the truth value of A into its opposite.

One always the negation of a statement A is replaced by the fact that you, the phrase " It is not the case that" prefixing. Although a natural language sentence can also deny, by using the word " not " or some other negative formulation fits in a suitable place - but it's not always easy to recognize, use and formulation which is to be inserted where. Formally, one writes for " not A" in the common notation ( notation ) ¬ A, in English and in the Boolean algebra also "NOT A" sometimes " ~ A".

We deny the above examples:

• It is not the case that Munich is 781 km away from Hamburg.
• It is not the case, that is divisible by 3 9.
• It is not the case that Eintracht Frankfurt is in the next season German football champions.
• It is not the case that all the cars are green. ( It may well be also green cars, but there is at least one car that is not green. )

In general, for the negation:

• If a statement is true, the negation is false.
• If a statement is false, the negation is true.
• A statement can not be both true and false.
• The statements and can not be simultaneously true.

And -linked statements - Conjunction

→ Main article: conjunction ( logic)

A conjunction is a composite of two statements statement that asserts the truth of its Sub statements. Colloquially connects two propositions A and B by the conjunction " and" to a conjunction " A and B" in the logical language is mostly used the sign ( notation: ), and occasionally the ampersand, the ampersand (&).

• Speech: A and B
• Notation:
• In English and in the Boolean algebra and A AND B

The statement is always true if both A and B are true. Otherwise is wrong, namely when either A or B or both statements are false.

Examples of an AND operation:

A: 9 is divisible by 3 B: 9 is a square number

These sub- statements and their negations are now linked to each other by:

• : 9 is divisible by 3 and 9 is a square.
• : 9 is not divisible by 3, and 9 is a square.
• : 9 is divisible by 3 and 9 is not a square number.
• : 9 is not divisible by 3 and 9 is not a square number.

Only is true because it is true and is also true.   is wrong, because it is wrong.   is wrong, because it is wrong.   is wrong because both is wrong.

Nichtausschließendes Or - disjunction

→ Main article: disjunction

A disjunction is a compound statement, which claims that at least one of its sub-statements is true. The disjunction in this sense is also called nichtausschließendes Or. ( But note: The term " disjunction " was and is often used for the exclusive or, " either ... or" Some authors therefore use for the Nonexclusive Or the term adjunction. . ) The symbol " " comes from the Latin word " vel " what on German " or "means.

• Speech: " A or B"; more precisely: " A or B or both ", often in legal or medical texts: " A and / or B"
• Notation:
• In English and in the Boolean algebra and A OR B

The statement is true whenever at least one of the sub-statements A or B is true, or if the two parts are true. Otherwise is wrong, namely when both A and B are false.

Example of an OR operation:

• A: 9 is divisible by 3
• B: 9 is a square number

These sub- statements and their negations are now linked to each other by:

• : 9 is divisible by 3 or 9 is a square number.
• : 9 is not divisible by 3 or 9 is a square number.
• : 9 is divisible by 3 or 9 is not a square number.
• : 9 is not divisible by 3 or 9 is not a square number.

Is true because both are true.   is true because it is true.   is true because it is true. Only is wrong because both are wrong.

Material implication

→ Main article: implication

The material implication, also known as conditional or subjunction expresses the sufficient condition: She says that the truth of a sentence is a sufficient condition for the truth of the other set. We write

Or

• A is a sufficient condition for B.
• Even if A, then B.
• A implies that B.
• B is a necessary condition for A. That B if a necessary condition for A, if A is a sufficient condition for B, is an at first sight surprising and perhaps counterintuitive, but true statement. Subchapter Sufficient and necessary condition is trying to make this connection visible.
• A implies B.
• Only if B, then A.

Or even

• If A, then B.

In a conditional is called the antecedent A, B the consequent or succedent.

Examples:

• The fact that it is raining, is a sufficient condition to ensure that the road is wet.
• Even when it rains, the road is wet.
• When it rains, the road is wet.
• Only when the road is wet, it can rain.
• If person x has a car of the BMW brand, x has a car.
• If a number n is divisible by 6, then the number n is divisible by 3.

The reading of " if ... then " is problematic, as the natural language " if ... then " especially contextual relationships such as causality or temporal proximity are expressed. All this makes the material implication not she mentions only the formal context: "The fact that it is raining, is a sufficient condition to ensure that the road is wet ." On the question of why this is a sufficient condition - whether on the basis of a causal relationship or even accidentally - that material implication does not comment.

When reverse is referred to the closing of. For example, this means:

• If the road is not wet, it does not rain.
• Only when it is not raining does not wet the road.
• If person x does not have a car then x has no car of the BMW brand.
• Only if person x has no car of the BMW brand, x has no car.
• When the number n is not divisible by 3, then n is not divisible by 6.
• Only if n is not divisible by 6, n is not divisible by 3.

Colloquially you can occasionally further - entice statements - false:

• Because it was not raining, the road can not be wet. This conclusion is incorrect because the road can be wet for other reasons ( broken pipe, exercise the fire ... ).
• X has no car of the BMW brand, so x has no car. Wrong, because he could indeed have a Mercedes.
• N is not divisible by 6, that n is not divisible by 3. Even this conclusion is wrong. The number 15 is not divisible by 6 and very probably by 3

This means that if the conclusion is true, then is obtained from the statement ¬ A no statement about B; B can be true or false. ( "Ex falso sequitur quodlibet " - " from falsehood follows Any " )

The implication is an important tool in mathematics. Most mathematical proofs use the concept of implication.

Biconditional

→ Main article: biconditional

The biconditional, often called object- linguistic equivalence or substantive equivalence expresses the necessary and sufficient condition, that says that a proposition A is true then exactly when a statement B is true. One writes:

And reads

• A is the case when B is the case.
• A iff B.
• A is equivalent to B.
• A is the case if and only if B is true.

Even when biconditional a purely formal statement is made that says nothing about a possible substantive context of A and B.

Instead of saying, you can also say that A that B is a sufficient condition for A is a sufficient condition for B, and so. In fact, these two statements are logically equivalent.

Example:

• The natural number n is divisible by 6 if and only if n is divisible by 3 and by 2. If n is divisible by 6, it follows that n is divisible by 3 and by two. But the opposite also holds: If n is divisible by 3 and by 2, then n is divisible by 6.
• Today is Tuesday if and only if tomorrow is Wednesday.

The biconditional as compound statement within the logical language (see object language ) is often confused with the concept of logical equivalence or mixed. The logical equivalence is a meta-language, usually formulated in natural language property of two statements of the logical language. A connection between logical equivalence and biconditional is only insofar as the Metatheorem is that a biconditional iff is a tautology if the two propositions A and B are logically equivalent.

Or Negative

→ Main article: contra-

The exclusive Or ( contra- or non-equivalence ), " either A or B" means that exactly one of the two linked statements is true of him. According to an exclusive or is false only if both A and B are false, but if both are true. ( Some authors use the term alternative for the Negative Or. )

Although the exclusionary Or is a concept with which you are dealing in natural language over and over again, it is not introduced in most logic languages ​​as a separate connective. Instead, the exclusive or is expressed for example as a negated biconditional, ie as.

Great importance enjoys the exclusive Or in contrast, switching algebra, where ( eXclusive OR) is usually written as XOR.

Negation of a linked statement ( De Morgan's law )

→ Main article: De Morgan's law

Negation of a conjunction

The negation of the conjunction " A and B" ( in the logical notation: ) is " It is not the case that A and B are true " ( in the logical notation: ). This is logically equivalent to the statement " A is not, or B is not the case (or both )" ( in a logical notation: ).

An example:

If the statement

Would deny, then you can say either

Or they say

In the Boolean algebra is often the connective NAND used, where "A NAND B" the same truth- value curve has as the term " ".

Negation of a disjunction

The negation of the disjunction " A or B (or both )" ( in the logical notation: ) is " It is not the case that A or B is true " ( in logical notation: ). This is logically equivalent to the statement " A is not the case, and B is not the case," ( in logic notation: ).

An example:

If the statement

Would deny, it is said

According to the law of De Morgan but you can now also say:

Or more beautiful in German

In Boolean algebra, the NOR connective is used, the same truth- value curve has as saying.

Sufficient and necessary condition

This section is the first often perceived as counter-intuitive relationship between sufficient and necessary condition, as it was mentioned in the section on material implication, again pick up and elaborate.

Consider once more the material implication.

It is said A is sufficient for B: Even when the case A, and B is the case.

Conversely, you can also say: B is necessary for A. Without A B can not be met.

How is this related?

We know that the truth of A pulls from B to the truth, because A is indeed a sufficient condition for B. Thus, it is simply not possible that A occurs without B would therefore also occur: B is thus forced to the case if A is true. B is "necessary" for A.

This relationship is in truth so pretty simple; Main reason that it is often initially perceived as counter-intuitive, is probably the difficulty of " if ... then " on the one hand and the purely formal necessary and sufficient condition to distinguish between the many colloquial meanings on the other hand strictly.

With the colloquial " if ... then " one might almost always express a substantive ( causal and / or temporal ) relation between antecedent and consequent: " rain causes road wetness ", " First, the rain falls only after the road is wet ." If one misunderstands the sufficient condition in this sense, it is clear that the formulated in reverse order necessary condition " Only when the road is wet, it is raining " strange looks " rain causes but road wet, how can it ever be concluded that wet road caused the rain? "

All this does not tell from the material implication. "A is a sufficient condition for B " means simply that if the statement A is true, the statement B is true - timeless and incoherent, not " later " or "because".

Said analog is the necessary condition, "B is a necessary condition for A ', only the out that B is true if A is. But exactly what is the definition of the conditional A → B.

Formal access

Introduction

At least while reading aloud of sentences like:

Will require that tells him what's the point of self-conscious layperson.

The response of the logician: We will try to bring security in the rules of logical inference. Since the Sophists the West is clear that seemingly automatic inferences can lead to manifestly absurd results. Again and again paradoxes were formulated and felt by great thinkers as a challenge. Logicians, therefore, attempt to redefine the rules of argumentation as strict as possible.

The introductory example makes it clear that this requires a separation of the levels of language is essential: The formal statement A ∧ B is to be explained, that is spoken on a metalinguistic level of the testimony of A as well as on the statement B.

An attempt to do this, is to concretely define the propositional logic as a formal system, as calculus (a type of a formal system ). The terms " true" and " false" did not come into this system before initially. Instead axioms are set to be viewed simply as strings, from which further derivable strings are derived on the basis of certain rules of inference.

Of course, the goal here is that in a formal system only strings ( sentences ) can be derived that are true even with a plausible interpretation. On the other hand, all records that are as "true" interpreted, can also be derived. The first is the need for accuracy, the second according to the completeness of the formal system; both properties are under calculus: The term calculus in logic described.

For the classical propositional logic with which we are dealing here, there are calculi ( formal systems ), which are both accurate and complete. For more complex logical systems (eg set theory ), it is impossible to give a complete calculus that is correct - this insight was in 1931 by Kurt Gödel proved ( Gödel's incompleteness theorem ).

Syntax

There are many different ways to define the syntax ( "grammar" ) of a logical formal language; usually this is done in the context of a calculus. The following definition is therefore to be understood as an example of just how well a calculus for classical propositional logic look. For more examples of concrete calculi can be found under tree calculus, conceptual notation, systems, natural deduction, sequent calculus or resolution calculus. Another axiomatic calculus is given as an example in the article Hilbert calculus, a graphical calculus in the article Existential Graphs.

Building blocks of the propositional language

As components of the propositional language set of letters to ( " atomic formulas ", set of constants ), connectives and structure characters. Set of letters to the characters P0, P1, P2, ... be. Connectives are to be the character ¬, ∧, ∨, → and ↔. As a division sign the parentheses are intended to serve.

Formally this can be expressed as follows, for example:

Let V be the ( countably infinite) set of atomic formulas ( set of characters ):

Let J be the set of connectives and structure characters:

The alphabet of the logical language is the set V ∪ J, ie the union of atomic formulas, connectives and structure characters.

Formation rules

The formation rules determine how to form the building blocks of the propositional language sentences ( formulas ).

Here are propositional formulas as words over the alphabet of the logical language, over V ∪ J are defined inductively as follows:

• All atomic formulas F ∈ V ( ie all sentence letters) are formulas.
• If F is a formula, so is ( ¬ F ) is a formula. ( This formula is called the negation of F. )
• If F and G be two (not necessarily different ) formulas, so is (F ∧ G ) is a formula. ( This formula is called the conjunction of F and G. )
• If F and G be two (not necessarily different ) formulas, so is (F ∨ G ) is a formula. ( This formula is called a disjunction of F and G. )
• If F and G be two (not necessarily different ) formulas, so is (F → G ) is a formula. ( This formula is called material implication or conditional tense of F and G. )
• If F and G be two (not necessarily different ) formulas, so is (F ↔ G ) is a formula. ( This formula is called biconditional of F and G. )
• Nothing else is a propositional formula.

Rules of inference

→ Main article: Final rule

Final rules are generally transformation rules ( transformation rules ) that are applied to existing formulas and create new formulas from them. If one sets up a calculus for a logical system, then choose the transformation rules so that they generate from existing formulas such formulas that semantically follow from the output formulas - that's why the term " rule of inference " ( a conclusion ).

Within the syntax of the final rules, however, are purely formal transformation rules, which are of no further meaning for themselves.

On specific rules of inference are only two are given: The ponendo modus ponens and the substitution rule.

See also: Calculus

Axioms

→ Main article: Axiom

Axioms are excellent (in the sense of: highlighted) formulas of the propositional language. The distinction is that they are within a proof or a derivation (see below) was used without further justification.

Pragmatic choose such formulas as axioms which are tautologies semantically, so always apply, and help to shorten proofs. Within the syntax of the axioms are, however, purely formal objects, which are of no substantive meaning or justification.

Axioms are generally optional, that is, a calculus can do entirely without axioms, if he has sufficiently many and powerful rules of inference. Axiom Free calculi are, for example, the natural deduction systems or tree calculi.

Here is an example of a axiomatic calculus are shown, namely those that Whitehead and Russell presented in its 1910-1913 incurred Principia Mathematica. The Principia Mathematica calculus for propositional logic consists of the following axioms ( of which the fourth redundant, that is not absolutely necessary, because derivable from the other axioms is ):

To be able to derive from these axioms also those valid records containing other than the connectives occurring in the axioms, they are returned by the following definition to the existing connectives:

As an alternative to - as here - concrete axioms can also axiom schemata indicate in which case one does without a substitution rule. If one interprets the above axioms as an axiom schemata, then would, for example, the first axiom schema, for infinitely many axioms, namely replacing all instances of that schema.

Derivation and proof

→ Main article: Derivation ( logic)

A derivation is a list of ascending numbered sets, which begins ( the premises of the derivation ) or axioms with one or more assumptions. All following these rates are either also axioms (for some calculi, other assumptions are permissible) or are from one or more of the preceding lines created by the application of inference rules. The last sentence in the list is the conclusion of the derivation.

A derivation is called premises without proof. Often, however, the words " derivation " and "evidence" are used synonymously.

If it is possible to derive from a set of assumptions ( premises ) Δ a conclusion P, then we also write.

If it is possible, a set P without the use of assumptions to derive ( prove ), then one also writes. In this case, P is known theorem.

The character goes back to the concept-script, that work, in which Gottlob Frege in 1879 specified the first formalization of predicate logic.

In classical propositional logic one selects the final rules so that it is possible with their help derive all valid arguments (and only valid arguments ); the question of validity is in the following section, " Semantics", treated.

Semantics

Outside the logic semantics called a field of research which focuses on the importance of language and their parts. Often the word semantics is used interchangeably with the word meaning.

Even within the logic is what semantics to significance: why namely, the expressions of a formal language - assign a meaning - for example of the things mentioned language of propositional logic. In the logic, which is usually made ​​very formal.

In the center of the (formal) semantics is a summary function ( sometimes referred to as evaluation function Denotationsfunktion, logical values, function) that assigns a meaning to the formulas of the logical language. Formally speaking, the evaluation function is a mapping from the set of formulas of the language in the set of truth values ​​. Often, the evaluation function is denoted by the uppercase letter V.

In classical propositional logic, the evaluation function is very simple: the principle of bivalence demands that they must provide exactly one of exactly two truth values ​​for each formula to be evaluated; and the principle of extensionality requires that the evaluation function in assessing a complex set must consider only the evaluation of its subsets.

Each atom, so each set of letters (Atom) assigned by fixing a truth value. It is said that atoms are interpreted. It is thus established that, for example, P0 is true that P1 is false and P2 that is also wrong. Thus, the assessment of the building blocks of the logical language is satisfied. Formally, such a valuation - called interpretation and often referred to v with the lowercase letters - a function in the mathematical sense, ie a mapping from the set of atoms in the set of truth values ​​.

If the evaluation function V is applied to an atom, that is, if it is to evaluate an atom, it provides the interpretation of that atom in the sense of the above paragraph. In other words, it provides the value of the rating V assigns atom.

In order to evaluate the composite formulas must be defined for each connective, which truth value, the evaluation function for the different truth-value combinations that his arguments can take. In classical propositional logic is done usually by means of truth tables, because there are only a few manageable ways.

The unary connective ¬, the negation is defined in the classical propositional logic so that it reverses the truth value of its argument into its opposite, so " no": If the evaluation of a formula X is true, then the evaluation function for ¬ X provides false; but rated X wrong, then returns true, the evaluation function for ¬ X. The truth table looks like this:

The truth-value curves of the two -digit connectives used are defined in the classical propositional logic as follows:

Generally, there are four -digit and two-digit sixteen connectives for classical propositional logic. The treated here only logical language therefore restricted to the connectives ¬, ∧, ∨, → and ↔, because these are the most common and because they are also content still best known for the everyday language. From a formal point of view is the only condition that you want to meet in the choice of connectives, which can be expressed that with the chosen connectives all other theoretically possible connectives; one says: That the amount of the chosen connectives is functionally complete. This requirement is met when made ​​here choice.

For details on how many and which connectives are there and how many connectives are needed to achieve functional completeness is described in Chapter connective.

Semantic validity, tautologies

Semantic validity is a property of the formulas or of arguments. ( An argument is the claim that some of the statements made ​​- the premises - a specific statement - the conclusion -. Follows )

A formula of propositional language is said to be semantically valid if the formula under all interpretations - is true - that is, under all assignments of truth values ​​to the atoms occurring in it; if it is, so to speak universally valid; In other words: If the truth table for this statement in each row, the result shows true. This is called semantically valid formulas and tautologies and writes, if a tautology, formally as follows:

An argument is said to be semantically valid if, and the conclusion is true under the assumption that all the premises are true. In the formulation of Gottfried Wilhelm Leibniz: from truths only truth follows. This definition must of course also be taken formally, and this takes place as follows: An argument is exactly then semantically valid if all assignments of truth values ​​to occur in premises and conclusion atoms, in which the evaluation function for all premises returns the value true, even for the conclusion returns the value true.

To express that a set of formulas ( the set of premises ) is a formula ( the conclusion ) follows semantically, to write formally as follows:

Note the graphic similarity and difference between the content (chapter " derivation and proof" ) and: The first formulation - expresses the syntactic validity of the argument, that says that from the formulas in the formula can be derived using the rules of inference of the selected calculus can. however, claims the semantic validity that follows in the classical propositional logic as in the previous paragraphs as the Leibnizian from truths only truth is defined.

See also: decidable

Important semantic properties: satisfiability, falsifiability and unsatisfiability

In addition to the validity ( generality ) property, there are some other important properties: satisfiability, falsifiability and unsatisfiability. In contrast to the validity, the property formulas or arguments may be, are satisfiability, falsifiability and unsatisfiability properties of sets or set of quantities.

• A formula is called satisfiable if there is at least one interpretation of their occurring in atoms ( set of characters ), under which the formula is true.
• A formula is called refutable if there is at least one interpretation of the atoms occurring in it, under which the formula is wrong.
• A formula is called unsatisfiable if it is false under all interpretations of the set of letters occurring in it.
• A set of formulas is called satisfiable if all the formulas contained in it are fulfilled.

The question whether a formula (or a set of formulas ) has one of the above-mentioned characteristics, as well as the question whether a formula that is a tautology is general, not be solved efficiently for general formulas: Although the truth table is a decision procedure for each of these questions, but includes a truth table for a statement or a statement amount in n atoms lines; the truth table method is nothing more than a brute-force method.

Each of these problems can be attributed to the question of whether a particular formula is fulfilled:

• A formula is a tautology if and only if is unsatisfiable.
• A formula is refutable if and only if is satisfiable.

The question whether a statement is satisfiable is called satisfiability or SAT problem ( after the English word for satisfiability, satisfiability ). The SAT problem plays an important role in theoretical computer science and complexity theory. The satisfiability problem for general (arbitrary) formulas is NP-complete, that is, (assuming that P not equal to NP ) is not solvable in polynomial running time.

For certain proper subsets of formulas of the propositional language the SAT problem is still faster, that is, solvable in polynomial time limited computing time. Such a subset of the Horn formulas which are conjunctions of disjunctions whose disjuncts denied or un- united -atoms, said within such a disjunction, however, more than one atom may be straight one.

Algebraic view

When one considers the semantics, which was erected here for classical propositional logic, then you recognize certain regularities. For example, if the evaluation function applied to a statement of the form X ∧ W, where W is to be any true statement, then you realize that the evaluation function for X ∧ W always returns the truth value true if V ( X) = is true ( that is, V (X ∧ w) = v (x) ). Structurally equivalent laws apply in other semantics, including those that are set up for all other non- logical systems. For the arithmetic applies, for example, that the local evaluation function (called VArithmetik ) for an expression of the form X Y always returns the value of X, provided that the value of Y is zero: VArithmetik (X Y) = VArithmetik ( X), if VArithmetik (Y ) = null.

A formal science that examines such structural regularities is the abstract algebra (usually part of mathematics, but also in computer science ). In abstract algebra is examined, for example, for which there is a neutral element links, i.e., an element N, the op for a link results in that the following applies ( for any X): X OP N = X. As would say from algebraic point of view that there is exactly for classical propositional conjunct a neutral element, namely true and that there are also exactly is a neutral element for addition in arithmetic, namely the number zero. As an aside it should be mentioned that there are neutral elements for other connectives; the neutral element for the disjunction is false: V (X ∨ F) = V ( X) if V ( F) = false.

The formal algebra considered formal semantics purely according to their structural properties. They are identical, then there is between them from algebraic point of view there is no difference. From algebraic point of view, more precisely, from the perspective of formal algebra semantics for classical propositional logic is a divalent Boolean algebra. Other formal systems whose semantics respectively form a Boolean algebra, the Boolean algebra and elementary set theory. From algebraic point of view, therefore, exists between these disciplines is no difference.

Normal Forms

Every propositional formula can be rewritten in disjunctive normal form into an equivalent formula in conjunctive normal form and an equivalent formula.

Metatheory

In the meta-theory, the properties of logical systems are analyzed: the logical system in the metatheory of the investigation.

A meta-theoretical question is, for example, if a contradiction can be derived in a calculus.

The present section is to consider some important meta-theoretical issues from the perspective of propositional logic.

A meta-theoretical result, for example, the finding that all the correct calculations are also consistent. Another meta-theoretical result is the finding that a consistent calculus does not have to be automatically correct: It is readily possible to set up a calculus in which not a contradiction can be derived, but in which, for example, are not generally valid statement of the form "A ∨ B" can be derived. Such a calculus would be from the former base consistent, the latter reason but incorrect.

Another very simple result is the finding that a complete calculus does not have to be automatically correctly or just consistent. The simplest example would be a calculus in which every formula of propositional language is derived. Since each formula is derivable, all tautologies are derivable, who are formulas: This makes the calculus completely. However, since every formula is derivable, the formula P0 ∧ ¬ P0 and the formula A ∨ B is derivable in particular: The former makes the calculus inconsistent, the latter is incorrect.

The ideal that should satisfy a calculus is correct and complete: If that's the case, then it is the ideal calculus for a logic system, because it all semantically valid sentences (and only those ) can be derived. So are the two questions of whether a concrete calculus is correct and / or complete and whether it is even possible for a particular logical system, specify a correct and complete calculus, two particularly important metatheoretical issues.

Demarcation and Philosophy

The classical propositional logic, as outlined here, is a formal logical system. As such, it is one among many that are of equal importance from a formal viewpoint, and the very specific characteristics: The most consistent, most are correct, some are complete, and some are even decidable. From a formal point of view the logical systems, not in competition behavior with regard to truth or correctness.

Clearly distinguished from formal, internal logical questions are out of logical questions: those of utility ( applicability ) of individual systems for a particular purpose and those on the philosophical, especially metaphysical status of individual systems.

The usefulness of consideration is the simpler, the differences of opinion are less profound and less severe with respect. Classical propositional logic, for example, has proven itself in describing electronic circuits (switching algebra) or to the formulation and simplification of logical expressions in programming languages. Predicate logic is often used when it comes to formalize knowledge of facts and automated drawing conclusions, as happens prologue including in the context of the programming language. Fuzzy logics, nonmonotone, multivalued and also paraconsistent logics are very welcome when it comes to dealing with stocks of knowledge, in which statements are to be stored with different degrees of level of certainty or even contradictory statements, yet meaningful conclusions to be drawn from the entire stock. Although there can be very large differences of opinion depending on the application, which logical system is better suited to the nature of the problem for all involved is palpable immediately and in the same way. Single Scientific considerations and issues play mainly from in this area.

( Yet ) are controversial as such pragmatic considerations of philosophical questions and metaphysical nature. Paradigmatic is the question, " which logical system is properly ", where " right" here is meant as: Which logical system not only simplifies some aspect of reality model, but the reality that adequately describes Being as a whole. It is added to this question many different opinions including imported from philosophical positivism opinion that the question as a whole is meaningless.

In the area of metaphysical questions, the question whether there was such a thing as a metaphysical principle of bivalence, ie whether through true / false statements about reality fit into the scheme or not covered. This question is independent of the question whether the study of two - or many-valued logics is practically useful, even if a metaphysical principle of bivalence there, you could use easy to apply many-valued logics, about to take epistemic situations, for example, statements of close, which, though metaphysically true or false, one of which is not, or not yet known which of the two is the case. Conversely, you can also apply if such a metaphysical principle does not apply binary logic due to its simplicity for such applications prefer in which must be handled only with records that are actually true or false.

The question of a metaphysical principle of bivalence is not answered like most metaphysical questions definitively satisfactory. An early objection to such a principle, Aristotle presented for discussion the issue of statements about future matters was ( "Tomorrow it rain "). If statements about Future were true or false today, it is argued, then the future must be predetermined to the last detail. Another objection that is raised is that there are statements whose truth can not be practically or theoretically determined - for example, can the truth of " The lawn in front of the white house was on February 1, 1870 exactly 6,120,375, 4 blades of grass "does not find easy.

Proponents of a metaphysical bivalence principle often invoke the behavior of Metatheoretikern, so by mathematicians or logicians who make statements about formal systems: No matter how multi-valued or not classically the system under study is that Metavermutungen, Metabehauptungen and Metafeststellungen here taken are always two-valued: A calculus, also a para consistent or nonmonotoner, is always used as either consistent or inconsistent considered, and a logical system is always either correct or incorrect, complete or not complete, decidable or undecidable, never "a bit " of both. Advocates interpret this as evidence that there is indeed a strict distinction by giving true and false in reality, or that it is at least reasonable to assume such.

Another philosophical question is after the metaphysical status of the investigation object of logic, that is, by what logical systems, calculi, logical values ​​actually "are".

The Platonic point of view is that the characters and constructs used in the logic have an extra- logical meaning that they for real, existing (though of course non- physical ) are named objects. In this sense, there is such a thing as the true and the false, abstract objects that are of the characters " true" and " false" named.

The counterpoint to Platonism would nominalism, the existence of only granting the characters that are manipulated in the logic. Object of logic are characters, and the action of the logician is the manipulation of characters. The symbols denote nothing, something like the truth or falsity does not exist then. The basic dispute between the mathematics of the nominalist position would correspond to the formalist direction.

A middle position would take a philosophical constructivism, according to which characters denote Although no independently existing objects, by dealing with the characters but objects are constructed.