Truth tree

from Wikipedia, the free encyclopedia

In logic, a truth tree or tree method is a method of checking statements to see whether they are tautologies .

Main article: Tree calculus

The tree method is a form of reductio ad absurdum : the assumption that a statement is true in every case ( tautology ) is proven by showing that the opposite can never occur. A truth tree therefore begins with assigning the truth value 0 ( false ) to a statement . Next, the statement is structured in such a way that each case receives its own branch for the occurrence of the truth value, at the end of which there are all partial conditions with corresponding truth values. The same procedure is used with the ends of these branches until a contradiction can be determined within a branch. When this happens, it is shown that this case is not possible and the branch is closed (usually with an x ​​at the end of the branch). If no branches remain consistent until the end of the breakdown, it has been shown that the initial statement is actually always wrong. This proves that the statement is a tautology.

Two examples

A simple tautology

The statement is intended to serve as a simple example of a tautology . Obviously, it always becomes true, since the negation ( ) reverses the truth value of A. The main operator is the or ( ). It becomes true if at least one of the two linked elements is true.

So we now assume that the statement is false (1 means true, 0 false).

: 0

Now the statement must be broken down in such a way that every case in which the main operator receives the specified truth value is included in a branch. This is possible in the case of or only in one case: both parts are wrong.

: 0

| : 0 : 0 X


A direct contradiction arose: If A is false, A would not necessarily have to be true and vice versa. This closes the only branch and shows that the opposite of the assumption that the statement is true can never be true.

Contingent truth

The tree method cannot also be used to check whether a statement is a tautology or inconsistent (never becomes true). Strictly speaking, this means that the contingency of a statement cannot be checked in a single procedure. In principle, however, it is possible to start the truth tree with the truth value 1 and thus carry out an inconsistency test.

In the following, however, a case for a tautology test with a negative result will be shown. Apparently the statement is not a tautology. The statement is only true if A and B have the same truth value.

The implication (right arrow) is the main operator. It only becomes false if the antecedent (first part) is true and the consequent (second part) is false.

: 0

| :1

: 0

There are two possibilities for this case: Either A is true and B is false or A is false and B is true (because: A or B is true but A and B is false).

: 0

| : 1 : 0 / \ | | A : 1       A : 0 B : 0       B : 1





Neither of the two resulting branches contains a contradiction. So there are two cases for which the statement becomes false.