Course / training:

Method for Logical Analysis


Principles of Formal logic.



Combinatory Explosion in Logical Systems





Combinatory Explosion in Logical Systems



Introduction:

the emergence of a System of Logic.



Judgment makes use of information.


Our judgments and estimations are in many ways like our other reactions and decisions.
They are based on information we have available - at conscious as well as subconscious levels.

Information and difference.


About the concept of 'information' a lot of different views and understands exist. To avoid misunderstandings, and grasp its essential meaning, it's useful to first look at its most characteristic property. This becomes apparant when we try to conceive of a situation where she is totally absent.
Clearly, without any information there is only utter chaos, senseless 'noise', total vagueness, a completely non-knowing.
Information only comes into play with the perception of any difference. As soon as a distinction can be made - eg a difference between on/off, in/out, true/false, etc. - some order emerges. Only then reasoning becomes possible, and logic applies. Every amount of information thus implies at least one difference.

Information and ordering.


Any difference on its turn implies at least two 'things', phenomena or states in an area in reality. Thus, based on distinctions, combinations of things can be be considered.
Between these things simultaneously exists at least one order, ie the one that necessarily follows from their difference as perceived.
Moreover, in order to make any sense to us, information in general can not purely consist of loose data. We view the information in a certain cohesion. This implies that it allows for some ordering to be distinguished.
Viewed in reverse, every ordered state, or structure, represents in itself a certain amount of information.

Logical relations.


Given a random collection of elements, we may take a look at the logical relations that are possible between those elements. The logical relations refer to the range of states or values which the elements can take seperately, as well as through their mutual derivation relations.

Information and reasoning.


By combining data, we may obtain more complex forms of information.
Naturally, we do this by means of our thinking.
Every train of thought, and in fact every process of information processing, has the general form of a reasoning, that is to say:
Reasoning:
A number of input data are combined, and next certain data are derived from the combination.
The ways in which those combinations can be made, and the values that these combinations can take, are determined by the laws of logic.
Of course these properties certainly apply to judgments and estimations. They are to be considered as reasonings, in that they operate on certain information, and produce information thereafter.

Laws of logic.


The logical laws only apply to the relations between data, ie the combinations and derivations, and not to the individual data (such as direct observations and feelings). They also apply independently of the content and the nature of the data, which includes possible variations in subject, domain, problem, purpose, application, scope, etc..

Levels of logical complexity.


Each form of reasoning, or argument, consists of a combination of one or more distinct logical relations.
Orderings, and therefore arguments, are possible in every imaginable form, but also in every unthinkable form: they are virtually unlimited in possible variation, complexity and size. As will be show below, in a few steps this already reaches far beyond the limits of the imagination and comprehension of people, and even beyond the capacities of calculation and data storage of physical and even theoretical computers of any conceivable size.
Fortunenately, all of these possible forms can be sorted out en judged with help of the laws of logic. Therefore, understanding the laws of logic is indispensable for every judgment being meaningful and reliable. For the optimal use of logic, a clear understanding of the minimal levels of logical complexity and their proportions is indispensable.

1.

 

Foundations of a Logical system.



In this overview we look at the logical possibilities that follow from an arbitrary collection units (items or objects). We'll see in what ways combinatorial explosion occurs, to what extent this happens and what consequences it has for the complexity of information processing and judgment regarding the input data.
To limit ourselves to the most generally valid principles we will focus on a logical system which itself is of minimal complexity. From this system, propositionlogic can be derived, but also, with the necessary additions, more complex systems such as predicate logic and modal logic.
In general applies that the consequences of combinatorial explosion and complexity themselves increase in explosive ways with each degree of increasing refinement of the logical system which we apply.

Logical system at semantic level.


S!

: a logical system ('apparatus', calculus).

S!

PPL :

S!

is a system in propositional logic (

PPL

) (or higher).

S!

PDL-I :

S!

is a system in predicate logic (

PDL-I

), first-order logic (

FOL

) (or higher).
SEM!(

S!

) : the semantics, a set of ordering rules, of

S!

.

Logical system at syntactical level.


L!

: a formal system (language system).

L!

PPL :

L!

is a language/system in propositional logic (or higher).

L!

PDL-I :

L!

is a language/system in predicate logic, first-order logic,

FOL

, (or higher).
SYN!(

L!

) : the syntaxis, or grammer, a set of ordering rules, of

L!

.
WFF*(

L!

)) : the set of well-formed statements (formulas) of

L!

.

1.

 

Starting parameters.



1.1.

 

Objects.


Applicable in

PPL

and further.

D

* : (referential) domain or population, set of elements d[i];   with (i

=

1, .. d).
d : domain- or population-size; total number of objects, domain-elements ('things', phenomena, items, variables) d[i] within

D

*.

D

*

=

{d[1], .. d[i], .. d[d] }.
d

=

|

D

*

|

.

Example.


With two items (d

=

2 ), the set

D

·d may consist of the following elements (objects), represented by proposition symbols and stated in arbitrary order:
{ (d

=

2 ) (

D

·d

=

{' A' ,' B'} ) }.
Eventually, the domain may be empty. That would make the inference system

S!

[s1] however extremely minimal, if not futile.
Some examples of statements in such a 'minimal' system, stated in a formal language:
{ (d

=

0 ) (

D

·d

=

{} ) : ({}

=

(v) {} ); (({})

$

=

(v)

$

0 ); ({}

=

(r)

$

0 ); etc.}.
Likewise, the domain may consist of only one element. But then the inference systems

S!

[ s1] also remains very simple.
Some examples of statements in such a 'primitive' system, stated in a formal language:
{ (d

=

1 ) (

D

*

=

{d [1]} ) : ((d[1] )

$

=

(v)

$

1 ); ((d[ 1] )

$

=

(v)

$

0 ); etc.}.

Range.


When the number of objects is less then one, any reasoning becomes meaningless.
On the other hand, when it is infinite, an inconceivable amount of reasoning concerning the domain becomes practically undecidable.
For a domain which is manageable, the following applies:
{ (d  

=

|

D

*(

mgb

)

|

); (1

d

<

0 ) }.

1.2.

 

Values.


Generally applicative to objects.

V

* : value system or 'value palette', set of values v[j];   waarbij (j

=

1, ..v).
v : total number of values, state values, object values or signal values (valences ); e.g. truth values, v[j] in

V

*.

V

*

=

{v[1], .. v[j], .. v[v] }.
v

=

|

V

*

|

.

Example.


With two values (v

=

2 ) the set

V

·v may consist of the following elements (values), represented by value constants and stated in arbitrary order:
{ (v

=

2 ) (

V

·v

=

{0 ,1 } ) }.

Range.


When the number of values is less then two, any assignment of value becomes meaningless, and thus any attempt to meaningful reasoning becomes impossible.
On the other hand, when this number is infinite, almost any reasoning concerning the domain becomes practically undecidable.
For a value set which is sensible and manageable, the following applies:
{ (v  

=

|

V

*(

mgb

)

|

); (2

v

<

0 ) }.
In

PDL

some further parameters come into play.
(2a) p : total number of predicate-variables (attributes, predicate names); including identity, '='.
(2b) r : (maximum) number of argument-places, or arity, for each predicate name.
(We may eventually use for simplicity and security the maximum over all predicate names).
(2c) n : total number of elements (individuals, objects) in the referential domain (the population).
The (maximum) number of items a in

PDL

is a derivate of the latter three.
{p

a

(p *MAX(1,(r *n)) }.
In other words, when for a

PDL

system we have sufficient information about the parameters p, r and n, we can calculate a, and may reason further following the rules for a

PPL

system.

Below we explore which combinatorial possibilities are generated by these parameters on the semantic level and the syntactic level respectively.

2.

 

Semantic expansion.



2.1.

 

Elementary object states .


Object states constitute pairs or tupels (the Cartesisch product) from the v values and d elements.
They reflect the domain at an observational level.
At a semantical level these are truth statements with respect to separate objects.
In logical language these are e.g. literals, ground instances, or 'witnesses'.
They resemble samples from a population.

H

·(v,d) : The set of all possible unique object states.

Example.


With two truth values (v

=

2, binary system) and two items (d

=

2) the set

H

·(v,d) may consist of the following elements (object states), represented by proposition symbols and stated in arbitrary order:
(

H

·(v

=

2,d

=

2)

=

  {' A' ,'¬A' ,' B' ,'¬B' } ).

Size.


h : The total number of possible unique object states.
{ v, d

|

(h (( h

=

|

H

·(v,d)

|

);
(h  

=

(

|

V

·v

|

,

|

D

·d

|

);

=

v *d   ) )h ) d, v }.

In a binary system.


Under (v

=

2 ) applies:

H

·(v,d) is just as large as the doubling of set

D

·d.
Eg., under (v

=

2 );
from (d

=

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10,

..

} );
follows (h

=

{ 2, 4, 6, 8, 10, 12, 14, 16, 18, 20,

..

} ).

Range.


The number h remains liniar (polynomial) in d.
(2

h

<

0 ).

Complexity class.


The set

H

·(v,d) remains within the class of countable infinite sets (denumerable sets).
Thus it can be searched algorithmically (it is tracktable) - with a singletape Turing machine - in linear polynomial computational time (

P-TIME

).
(

H

·(v,d)

POLY

(d**1 );

TIME

(d );

P-TIME

).

2.2.

 

Domain states.


Domain states consist of conjunct combinations of all objects with their specific values, ie various object states.
They reflect the domain in a purely descriptive way.
At a semantical level these are truth statements with respect to the state of the entire domain.
They are similar to the cells (categories of variance) in a so-called contingency table ( cross tabulation, of 'crosstab'), which forms the basis of numerous statistical measures for the comparision of variances, in particular Chi-square2), and variants or derivates of the latter, such as correlation coefficient, regression coefficient, Student's t, F, Fisher z, etc..

B

·(v,d) : The set of all possible unique domain states.

Example.


With two truth values (v

=

2, binary system) and two items (d

=

2) the set

B

·(v,d) may consist of the following elements (domain states), represented by proposition symbols and stated in arbitrary order:
(

B

·(v

=

2,d

=

2)

=

{'( A B)' ,'( A ¬B)' ,'(¬A B)' ,'(¬A ¬B)' } ).

Size.


b : The total number of possible unique domain states.
The number b equals the number of repetition variantions, or, sequence variations with replacement i.e. repetition, with size (length) d from v elements.
{ v, d

|

(b ( b

=

|

B

·(v,d)

|

;
(b  

=

(d1 := 1,

..

d )
v;  

=

v **d )b )d, v }.
This number determines the length of the digital truth-value patterns of the logical relations.
It is equal to the number of rows in the truth-values table.

In a binary system.


Under (v

=

2 ) applies:

B

·(v,d) is just as large as the set of all possible subsets - the power set - of

D

·d . I.e.:
(v

=

2) (b

=

|

B

·(2,d)

|

;

=

|

P

**d

|

).
Eg., under (v

=

2 );
from (d

=

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10,

..

} );
follows (b

=

{ 2, 4, 8, 16, 32, 64, 128, 256, 512, 1 024,

..

} ).
In a binary system the number of domain states represents the quantity of signal, signal content, or signal capacity, which is measured as the amount of domain elements d in bits (binary digits):
b = lg2 d bits.

Range.


The number b remains exponential in d.
(2

b

<

0 **0 );

Complexity class.


The set

B

·(v,d) remains within the class of uncountable infinite sets, which have the size of the continuum (cardinality of the continuum).
Thus it can only be searched algorthmically in exponential computational time (

EXP-TIME

).
(

B

·(v,d)

EXP-TIME

(d ) ).

2.3.

 

Logical relations.


Logical relations reflect the domain at an analytical level.
At a semantical level they constitute the possible conditional truth statements with respect to the entire domain or parts of it.
In logical languages these are e.g. truth-value patterns, formulas, propositions, theorems, and the like.
They correspond to the columns in the truth-values table.

T

·(v,d) : The set of all possible unique logical relations.

Example.


With two truth values (v

=

2, binary system) and two items (d

=

2), the set

T

·(v,d) may consist of the following elements (logical relations ), represented by proposition symbols and stated in arbitrary order:

T

·(v

=

2,d

=

2)

=


{' T' ,' F'
,' A' ,' B' ,'¬A' ,'¬B'
,'( A B)' ,'( A ¬B)' ,'(¬A B)' ,'(¬A ¬B)'
,'( A B)' ,'( A ¬B)' ,'(¬A B)' ,'(¬A ¬B)'
,'( A B)' ,'( A

#

B)' } ).

Size.


t : The total number of possible unique logical relations.
The number t equals the numer of order variations or permutations with repetition with size (length) b from v elements.
{ v, d, b

|

( t ((t

=

|

T

·(v,d)

|

);
(t  

=

(b1 := 1,

..

b )
v;  

=

|

B

·(v,b)

|

;

=

v **

|

B

·(v,d)

|

;

=

v **(v **d) ) )t )b, d, v }.

In a binary system.


Under (v

=

2 ) applies:

T

·(v,d) is just as large as the power set of the power set of

D

·d.
(v

=

2) (t

=

|

T

·(2,d)

|

;

=

|

P

**b

|

;

=

|

P

**|

P

**d

|

|

).
Eg., under (v

=

2 );
from (d

=

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10,

..

} );
follows (t

=

{4, 16, 256, 65 536, 4 294 967 296, 1.844674407371 *(10**19), 3.402823669209 *(10**38), 1.157920892373 *(10**77), 1.340780792994 *(10**154), 1.797693134862 *(10**308),

..

} ).

Range.


The number t remains hyper-exponential in d.
(2

t

<

0 **(0 ** 0 ) );

Complexity class.


The set

T

·(v,d) can be searched in hyper-exponential computational time (

2-EXP-TIME

).
(

T

·(v,d)

2-EXP-TIME

(d ) ).

2.4.

 

The Truth-values table.


Given a domain

D

·d and value set

V

·v, the possible immediate logical relations-between-relations are completely defined through the so-called truth-values table.
This is construed on basis of systematic value assignment (validation) of the objects by a simple standarized algorithm. The objects each in turn go through the range of values, through so-called 'nested' cycles ( loops), thus getting their unique, ordered truth-value patterns. Next, all other ordered value combinations are filled in. In this way a closed, coherent table arises of all possible sequences of (truth) values given parameters (d,v).
The value patterns are simular to statements with at least one proverb, or clause, in other words, 'sentences'.
In a binary system, they are expressed by binary numbers. Each of them has length of b value constants. These are simular to characters or symbols in written language.
The length b equals the amount of information in standard units: bits.
Furthermore, the table represents, with perfect garantees, all possible elementary logical relations together with their definite, immediate mutual logical relations.

Example.


Truth value table for a logical system with (v =2) values and (d=2) variables, interpreted for proposition logic (

PPL

), predicate logic (

PDL

), and shorthand Skolem form (

Sk

) respectively.

Table   bivalid value combinations
- with two variables, interpreted for PDL and PPL


No. Value pattern Logical relation in

PPL

Logical relation in

PDL

Logical relation in

Sk

Logical power
1 1 1 1 1

T

¬

F

X

¬

X

      0
2 0 0 0 0

F

¬

T

X

¬

X

      1
3 1 1 0 0

A

1
¬¬

A

1
        0.50
4 1 0 1 0

A

2
¬¬

A

2
        0.50
5 0 0 1 1 ¬

A

1
¬

A

1
        0.50
6 0 1 0 1 ¬

A

2
¬

A

2
        0.50
7 1 0 0 0

A

1

A

2
¬(¬

A

1 ¬

A

2)
  x

A

[x]
¬x ¬

A

[x]

A

[x]
0.75
8 0 1 0 0

A

1 ¬

A

2
¬(¬

A

1

A

2)
        0.75
9 0 0 1 0 ¬

A

1

A

2
¬(

A

1 ¬

A

2)
        0.75
10 0 0 0 1 ¬

A

1 ¬

A

2
¬(

A

1

A

2)

A

1 \

A

2
¬x

A

[x]
x ¬

A

[x]
¬

A

[x]
0.75
11 1 1 1 0

A

1

A

2
¬(¬

A

1 ¬

A

2)
  x

A

[x]
¬x ¬

A

[x]

A

[

c

s

]
0.25
12 1 1 0 1

A

1 ¬

A

2
¬(¬

A

1

A

2)

A

1

A

2
      0.25
13 1 0 1 1 ¬

A

1

A

2
¬(

A

1 ¬

A

2)

A

1

A

2
      0.25
14 0 1 1 1 ¬

A

1 ¬

A

2
¬(

A

1

A

2)

A

1 |

A

2
¬x

A

[x]
x ¬

A

[x]
¬

A

[

c

s

]
0.25
15 1 0 0 1

A

1

A

2
¬(

A

1 #

A

2 )
        0.50
16 0 1 1 0

A

1 #

A

2
¬(

A

1

A

2)
        0.50

Size.


tw : The total number of cells in the truth-values table.
The number tw naturally becomes even larger than t, being the product of the number of domain states (rows) b, and the number of domain-state relations (columns) t:
{ v, d, b, t

|

( tw ((tw

=

|

T

·(v,d)w

|

);
(tw
 

=

|

(

T

*(v,d ),

B

*(v,d) )

|

;  

=

(

|

T

*(v,d)

|

*

|

B

*(v,d)

|

);  

=

(

|

B

*( v,b)

|

*

|

B

*(v,d)

|

);
 

=

v **(v **d ) *v **d;  

=

v **((v **d) +d ) ) )tw )t , b, d, v }.

In a binary system.


Under (v

=

2 ) applies:
{ (v

=

2 ) ( tw  

=

|

T

·(2,d)w

|

;  

=

2 **((2 **d) +d ) ) }.
E.g., under (v

=

2 );
from (d

=

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10,

..

} );
follows (tw

=

{8, 64, 2 018, 1 048 576, 137 438 953 472, 1.18059162071744 *(10**21), 4.35561429658752 *(10**40), 2.96427748447488 *(10**79), 6.86479766012928 *(10**156 ), 1.840837770098688 *(10**311),

..

};
respectively in bytes (64-bits): {0.125, 1, 32, 16384, 2 147 483 648, 1.844674407371 ·(10**19 ), 6.805647338418 ·(10**38), 4.631683569492 ·(10**77), 1.072624634395 ·(10 **155), 2.876309015779 ·(10**309),

..

} );

2.5.

 

Arguments (Semantic).


In setting up an argument we usually don't make use of all possible logical relations about the subject in question, but a certain selection, or subset, of

T

·(v,d).
Arguments constitute of unique combinations of logical relations (i.e. without doubles).
At a semantic level these are sets of conditional truth-value statements which we regard in conjunction.
They reflect the domain at a discursive level.
In logical languages these are sets of truth-value patterns, formulas, propositions, theoremes, and the like: so called 'theories'.
For a solid analysis we have to take all possible selections into account.

U

·(v,d) : The set of all possible unique arguments.

Example.


In an extremely simple, so to say 'primitive' logical system, with two truth values (v

=

2, binary system) and only one item (d

=

1), the set

U

·(v,d) may consist of the following subsets (arguments), represented here as combinations of logical relations stated in terms of propositiesymbols, and in arbitrary order:

U

·(v

=

2,d

=

1)

=


{ {}
,{' T'}
,{' T' ,' F'} {' T' ,' A'} {' T' ,'¬A'}
,{' T' ,' F' ,' A'} ,{' T' ,'F' ,'¬A'} ,{' T' ,' A' ,'¬A'}
,{' T' ,' F' ,' A' ,'¬A'}
,{' F'}
,{' F' ,' A'} ,{' F' ,'¬A'}
,{' F' ,' A' ,'¬A'}
,{' A'}
,{' A' ,'¬A'}
,{¬A'} }.

Size.


u : The total number of possible unique arguments.
The number u equals the sum of all possible unique unsorted selections (without internal repetition) from

T

·(v,d) - i.e. of the binomial coefficients of t above the length (number of logical relations) t1 of each subset of

T

·v,d .
{ v, d, t

|

( u ((u

=

|

U

·(v,d)

|

);
(u1 ((U*[u1]

U

·(v,d) ); ((u[u1]

=

|

U* [u1]

|

)   (1

u [u1]

t )
(t1 ((u[u1]

=

t1 ) ((U*[u1] U·t1 ) (U· t1

U

·(v,d) ) ) ) t1 ) ) )u1 );
(u
 

=

(u1 := 1,

..

u )
u[u1];
 

=

(t1 := 1,

..

t )
(

|

U·t1

|

);
 

=

(t1 := 1,

..

t )

binomial

(t, t1 );
 

=

|

T

·(v,t)

|

;

=

2 **

|

T

·(v,d)

|

;

=

2 **(v **(v **d)) ) )u )t, d, v }.

In a binary system.


Under (v

=

2 ) applies:

U

·(v,d) is just as large as the power set of the power set of the power set of

D

· d.
(v

=

2 ) (u

=

|

U

·(2,d)

|

;

=

|

P

**t

|

;

=

|

P

**|

P

**b

|

|

;

=

|

P

**|

P

**|

P

**d

|

|

|

).
Eg., under (v

=

2 );
from (d

=

{1, 2, 3,

..

} );
follows (u

=

{16, 65 536, 1.157 920 892 373 ·(10**77),

..

} ).

Range.


The number u remains ultra-exponential in d.
(2

u

<

2 **( 0 **(0 ** 0 ) ) );

Complexity class.


The set

U

·(v,d) can be searched in ultra-exponential computational time (

3-EXP-TIME

).
(

U

·(v,d)

3-EXP-TIME

(d ) ).

[ 2.6.  Inference schemes, derivations, (semantic ).

(1)

Reasoning as derivation.


A very general mode of reasoning which occurs 'in nature' is the one in which at least one thinking step is taken. This means that from a certain collection of data (facts, connections) another set of data is derived.
Such a derivation has as its main connective the implication.
Briefly, every reasoning has the form 'premise implies conclusion'.
Eg.: (X Y ).
NB. Aristotle formulated a principle for the reasoning form called the syllogism, that is in fact valid for each form of argument: "The syllogism is a discourse in which, certain things being laid down, another thing follows necessarily, simply because those things are laid down." (Aristotle, Prior Anal., 1, 1).
An argument in a system with a scale of v values about a domain with d objects will therefore have the form of a derivation with the form:
Eg.: (X·(v,d) Y·(v, d) ).
In general, we reason from a set of premises (premises) to a collection of conclusions.
This means that both the premise group as the conclusion group consists of a certain subset of

U

·(v,d).
(a) The premise is shaped by a certain subset from

U

·(v,d), say

U

·(v,d)[k1] with length (size) l[k1] elements.
(b) The conclusion is shaped by some (different or the same) subset say

U

·(v,d )[m1] with length (size) l[m1] elements.

R

·(v,d)[k1,m1]: reasoning from (an element of)

U

·(v,d) to (an element of)

U

·(v,d ).
Broadly speaking, this takes the form:
(v d

|

k1 m1 (

R

·(v,d)[k1, m1]
(

U

·(v,d)[k1]

U

·(v,d)[m1] ) ) ).

Eg. (PPL): v1 d1 ( v1

=

2; d1

=

4;

D

·d1

=

{A, B, C, D };
k1 k2 ( (

U

·(v1,d1)[k1]

U

·(v1,d1) ); (

U

·(v1,d1)[k2]

U

·(v1,d1) );
(

U

·(v1,d1)[k1]

U

·(v1,d1)[k2] );
(

U

·(v1,d1)[k1]

=

{A, (B ¬C ) };
(

U

·(v1,d1)[k2]

=

{¬A B ), (C ¬ D ) } );

R

·(v,d)[k1,m1]

:=

((A, (B ¬C ) ) (¬A B ), (C ¬D ) ) );

(2)

De verzameling van afleidingen.


R

·(v,d)[

U

]
: the set of all possible unique inferences or conclusions at the semantic level.
(v d

|

R

·(v,d )[

U

]

:=

(k1 := 1,

..

u )
(m1 := 1,

..

u )

R

·(v,d)[

U

]
[k1,m1] ) );
This means that the set of all possible unique forms of reasoning under the parameters {v,d} is formed by a matrix:
(v d

|

R

·(v,d )[

U

]

:=

(

U

·(v,d)

X

U

·(v,d)) );

Size.


ru: the total number of possible unique inferences or conclusions at the semantic level.
The size of the collection is of course formed by the Cartesian product ( u·u).
r·(v,d)u

=

|

R

·(v,d)[

U

]

|

;

=

u ·(v,d)·2.
This series largely corresponds to the values (2 **A001146 (d ) )**2.

(2)

Derivations are at semantic level bipartite.


As mentioned, a collection

U

·(v,d) contains subsets

U

·(v,d)[k1] each consisting of unique combinations of logical relations from the collection

T

·(v,d). All those elements have their own logical validity value which is unique within

T

·(v, d). When we combine these values, for example in a premise or conclusion within a derivation, then according to the logical laws at semantic level, the immediate result is paraphrase reduction of the combination to one logical validity value which in turn corresponds to one logical relation in

T

·(v,d). This means that as a net result, premise and conclusion each contain (again: at semantic level) only one element. Therefore, at semantic level we can calculate logical derivations as propositions with only two simple elements.

2.7.

 

Minimal inferences, derivations (Semantic).



(1)

De verzameling redeneringen in hun minimale parafrase vorm.


The set of reasonings in their minimal paraphrase form.


Each of the subsets in the two components of the derivation can therefore always be reduced according to logical laws to the smallest possible logical-semantic content: in this case, logical relations in a domain with d objects.
We consider the components as mentioned in conjunction.
For convenience, we assume a binary system. This always has two values: valence
(v

=

2 ).
This system has a number of logical relationships as we saw earlier:
(t  

=

v **(v **d ) ).
The set of possible arguments can therefore be reduced to its paraphrase reduct version at semantic level.

R

·(v,d)[

T

]
the set of all possible unique minimal reasoning or conclusions at semantic level.
(v d

|

(k1 m1 (

R

·(v,d)[

U

]
[k1,m1]
(

U

·(v,d)[k1] in conjunctie

U

·(v,d)[m1] in conjunctie );
(

Cj

(

U

·(v,d)[k1 ]

Cj

(

U

·(v,d) [m1] );
(

U

·(v,d)[k1]

syn

par-rdc

U

·(v ,d)[m1]

syn

par-rdc

);

par-rdc

(p1 q1 ( (

T

·(v,d)[p1]

T

·(v,d)[q1] );

R

·(v,d)[

T

]
[p1,q1] ;

R

·(v,d)[

T

]

:=

(p1 := 1,

..

u )
(q1 := 1,

..

u )

R

·(v,d)[

T

]
[p1,q1] ) ) );
The paraphrase reduct versions of premise and conclusion will therefore each consist of exactly one element from each of the original subsets k1, m1, from

U

·(v,d).
This means that the set of all possible unique minimal forms of reasoning under the parameters {v,d} is formed by a matrix
(v d

|

R

·(v,d )[

T

]

:=

(

T

·(v,d)

X

T

·(v,d) );

Omvang.


r t: The total number of all possible unique minimal reasoning or conclusions.
Obviously, the size of this collection is formed by the Cartesian product (t·t).
r·(v,d)t

=

|

R

·(v,d)[

T

]

|

;

=

t ·(v,d)·2.

In a binary system.


Eg., under (v

=

2 );
from (d

=

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10,

..

} );
follow quantities of derivation relations (t2

=

{ 16, 256, 65 536, 4 294 967 296, 1.844674407371 ·(10**19), 3.402823669209 ·(10**38), 1.157920892373 ·(10 **77), 1.340780792994 ·(10**154), 1.797693134862 ·(10**308), 3.231700607131 ·(10**616),

..

} ).
This series largely corresponds with A001146(d ) **2;

=

A001146(d +1 ) .

(2)

Evaluation of arguments.


Ultimately, we want to know whether an argument is valid, in other words valid. In other words, which of the derivation relations from the matrix

R

·(v,d)[

T

]
are valid?
Each element of the matrix

R

·(v,d)[

T

]
is easy to solve like any implication according to the rules of the general truth value table.
(2.1)

Encoding as binary numbers.


Each of the logical relationships in the components of

R

·(v,d)[

T

]
can be endoded in the simplest logical system, propoposition logic (PPL), as a binary truth value pattern.
Each of these value patterns is an element of the set (value patterns of) logical relationships

T

·(v,d)[k1].
This means, as we have seen, that each of these binary patterns has a length of:
b·(v,d)

=

v·**d.
(2.2)

Paraphrase reduction to one binary number.


The results again consist of binary truth value patterns.
(2.3)

Interpretation of the binary outcome.


Rules for interpretation of a binary truth value pattern:
(a) Not all bits are set to 0 or 1 : undecided, indefinite contingency.
(b) All bits are set to 0 or 1 : decided.
(b1) All bits are set to 0: contradiction (non-satisfiability).
Only true if 'true implies false' (i.e.

$

1

$

0 ).
(b2) Not all bits are set to 0, and neither are they to 1 : (definitite) contingency.
(b2.1) Not all bits are set to 0 : consistency (satisfiability).
(b2.2) Not all bits are set to 1 : invalidity (presupposition, c.q. fallacy).
(b3) All bits are set to 1: validity.

(3)

Valid reasonings.


The total number of all possible unique contradictory reasoning or conclusions is simply the same as that of any set of disjunctions: exactly one.
The total number of all possible unique consistent reasoning or conclusions is therefore simply r·( v,d)t -1.

Size.


xt: The total number of all possible unique valid reasonings or conclusions.
The formula for the number of valid derivation relations xt with valence v =2 and number of objects d is:
xt·(v,d)

=

(v +1)·**b ;

=

(v +1)·**(v·**d);

In a binary system.


Eg., under (v

=

2 );
from (d

=

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10,

..

} );
folow as quantities of valid implications:
{ 9, 81, 6561, 43046721, 1.853 ·(10 **015), 3.4337 ·(10 **030), 1.179 ·(10 **061), 1.39 ·(10 **122), 1.93 ·(10 **244), 3.7339 ·(10 **488), // .. } );
This series largely corresponds to the powers of 3 of the powers of 2. See A011764 (OEIS A011764) in the the on-line encyclopedia of integer sequences.
Same range as percentages of valid implications:
{ 56.25, 31.64, 10.01, 1.00229, 0.01, 0.00001, 1.01822 ·(10 **-012), 1.03677 ·(10 **-030 ), 1.074897 ·(10 **-062), 1.1554 ·(10 **-124), .. } );

(4)

Table.


Below is a table with the most important dimensions of the collections mentioned above.


This table shows how combinatorial possibilities in a simple logical system quickly lead to a search space of astronomical proportions. For example, with 10000 items you can make a number of 'minimal arguments' (at semantic level) whose number consists of a number of digits where just the length of the number can be represented with an exponent (decimal logarithm) which in turn has a length of 3011 digits. In other words, not the number itself is 3011 digits long, but the exponent with which her length can be represented.

(5)

For comparision.


To put the above numbers somewhat in perspective, the following are some examples of large numbers occurring in nature (all according to fairly rough estimates).

In the universe.


• The number of galaxy clusters: approx. 4 ·10 **8.
• The number of galaxies in the universe: approx. 10 **11.
• The number of stars per galaxy: approx. 10**8 to 10**14.
• The number of stars in 'our' galaxy, the Milky Way: approx. 10**11.
• The number of stars in the observable universe: approx. 10 **22.
• The number of molecules in the observable universe: approx. 10 **80.

On Earth.


• The total number of fish in the oceans: approx. 3.5 ·10 **9.
• The number of ants on Earth: approx. 3.5 ·10 **12.
• The total number of grains of sand on all beaches on earth: approx. 10 **21.

In the human body.


• The number of cells in the human body: approx. 10 **14.
• The number of different proteins that can be built from 100 amino acids: approx. 10 **130.

To highlight two examples:
With 5 items, you can make almost as many -unique, minimal- arguments as the total number of grains of sand on all beaches on Earth.
With 7 items, which is the average memory capacity of our conscious attention window, you can make almost as many -unique, minimal- arguments as molecules existing in the observable universe.

These -literally- astronomical numbers indicate the level of complexity and thus decision problems.
It does not help to resort to a more advanced logical system. As a general rule, the more advanced the logical system, the more expressive power it has, but the less decision-making power. With each step towards a more advanced logical system, such as modal logic, multivalued logic, predicate logic, etc., and also so-called 'fuzzy logic', the numbers and problems of complexity and decidability are only increasing explosively again!
Clearly, without sufficient knowledge and skills of logical proof and testing, possible arguments about more than two items are already almost impossible to assess.

C.P. van der Velde © 2014, 2018.
Combinatory explosion in PPL.
Truth values (valence) v =2  (Binary system)
Unique items (atoms) Pattern length (characters) Logical relations (formulas) Combinations of 2 formulas Valid implications (amount) Valid implications (ppt.)
1
2
4
16
9 56.25%
2
4
16 256
81 31.65%
3
8
256
65536
6561
10.01%
4
16
65536
4294967296
43046721
1.002290163230%
5
32
4294967296
1.844674407371
·(10 019 [ 2])
1.853020188852
·(10 015 [ 2])
0.010045242576 74%
6
64
1.844674407371
·(10 019 [ 2])
3.402823669209
·(10 038 [ 2])
3.433683820293
·(10 030 [ 2])
0.000010090689 83316%
7
128
3.402823669209
·(10 038 [ 2])
1.157920892373
·(10 077 [ 2])
1.179018457774
·(10 061 [ 2])
1.018220213090
·(10 -012 [ 2])%
8
256
1.157920892373
·(10 077 [ 2])
1.340780792994
·(10 154 [ 3])
1.390084523771
·(10 122 [ 3])
1.036772402346
·(10 -030 [ 2])%
9
512
1.340780792994
·(10 154 [ 3])
1.797693134862
·(10 308 [ 3])
1.932334983229
·(10 244 [ 3])
1.074897014265
·(10 -062 [ 2])%
10
1024
1.797693134862
·(10 308 [ 3])
3.231700607131
·(10 616 [ 3])
3.733918487411
·(10 488 [ 3])
1.155403591277
·(10 -124 [ 3])%
100
1.267650600228 ·(10 030 [ 2])
10 381600854690 078004800107 713800
[ 30]
)
10 763201709380 156009600215 427600
[ 30]
)
10 604823044926 916660000603 060000
[ 30]
)
10 -158378664453 239349599612 367600
[ 28]
)%
1000
1.071508607186 279
·( 10 301 [ 3])
3.225562313751 201148898 088040
·( 10 300 [ 3])
6.451124627502 402297796176 080
·( 10 300 [ 3])
5.112395311035 022942430048 300
· 10 300 [ 3])
1.338729316467 379355366127 780
·(10 -298 [ 3])%
10000
1.995063116881
·(10 3010 [ 4])
10 (6.005738414240 562400144864 482
·10 **3010 )

10 (1.201147682848 112480028972 896400
·10 **3011 )

10 (9.518870175711 834000304730 005
·10 **3010 )

10 (2.492606652769 290799984998 959
·10 **-3008 )
%