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.

Logical possibilities in information.


In this overview we'll have a look at possible logical relations given an arbitrairy sets of units (or items).
This concerns the problem of combinatory explosion.
Below some rules are given about quantication of combinatory explosion in propositional logic and in predicate logic.

System of Logic.


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!

.

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.

2.  Combinatory possibilities.



2.1.  Semantic expansion .



2.1.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.1.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.1.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.1.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.1.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.1.6.  Inference schemes (Syntactic).

2.1.7.

 

Inferences , derivations (Semantic).




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 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.

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.

2.2.  Syntactic expansion.


When we want to record semantic structures outside our own thinking, or communicate them to others, we'll have to represent them into an empirical form, with a tempero-spatial structure, for example into linear structure of some language.

3.  Interpretation.


A crucial issue in daily life is: how can we assert the value of an arbitrary amount of information? This may apply in terms of, for instance, usefulness, credibility, plausibility, reliability, .. and, in the end, veracity. This actually means that we want to be able to reduce information back to some real properties of the domain to which she is refering. In other words, we're looking for a sensible, preferably an optimal interpretation.


3.2.  Semantical reduction.


How can we assess the logical 'status', i.e. the semantic value, of an arbirary argument? This means we want to be able to judge a certian subset of

U

·(v,d) at its truth valuee, in particular its logical validity.

3.2.1.  Consistent arguments.


What we like to know at least is whether arguments are to be taken 'seriously' at all, that is to say, qualify for an assessment of logical validity. Therefore we reasonably first take a look at arguments that, in principle, can be 'made true', or in other words, are satisfiable. That means that at least they are free from internal conflicts, in other words, they are consistent.
We must then take into account the collection of all the largest possible consistent subsets of

U

·(v.a).
There are four different variants of this, depending on the stage in the selection procedure that we can apply.
All of these variants, of course, we will view again without (syntactic) duplications within or between the subsets.

3.2.1.1.  Consistent Arguments: without immediate contradictions.


These are subsets of

U

·(v,d) without proven falsehood (falsum) or statements which are complementary.
The set of all possible unique consistent arguments, say

U

·(v,d) (

C

)
, thus consists of a (semantically weaker) selection of subsets from

U

·(v,d).

Example.


With two truth values (v

=

2, binary system) and two items (d

=

2) the set

U

·(v,d) (

C

)
may consist of the following subsets (consistent arguments), each with elements (logical relations) represented by proposition symbols and stated in arbitrary order:

U

·(v

=

2,d

=

2)
(

consis

)
 

=


{ {

$

(1111)}
,{

$

(1100)} ,{

$

(1010)} ,{

$

(0011)} ,{

$

(0101)}
,{

$

(1000)} ,{

$

(0100)} ,{

$

(0010)} ,{

$

(0001)}
,{

$

(1110)} ,{

$

(1101)} ,{

$

(1011)} ,{

$

(0111)}
,{

$

(1001)} ,{

$

(0110)} }.
The syntactical expressions (formulas) usually applied thereby for the associated logical relations are, respectively:

U

·(v

=

2,d

=

1)
(

C

)
 

=


{ {' T'}
,{' 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.


The size of this set is, with slightly larger basic parameters, rather hard to compute. Here follows is an approximation formula:
{ v, d, t, u

|

( u(

C

)
((u(

C

)

=

|

U

·(v,d)(

C

)

|

);
(u1 ((U*[u1]

U

·(v,d) ); ((U*[u1] ) (CONSIS(U*[u1] );
((U*[u1](

C

)

:=

U*[u1] ) (U*[u1] (

C

)

U

·(v,d) (

C

)
)
(u[u1](

C

)

=

|

U*[u1](

C

)

|

)   (1

u[u1](

C

)

(t /2 ) ) ) ) )u1 );
(

U

·(v,d)(

C

)

:=

(U*[u1](

C

)
) );
(u(

C

)
 

=

(u1 := 1,

..

u )
(U *[u1](

C

)

U

·(v,d)(

C

)
)

|

u[u1] ) );
(u(

C

)
 

<

(t1 :=1,

..

(t /2 ) )
(

binomial

((t /2 ), t1 )

*

b ) ) )u )t, d , v }.
{ (k1

U

·(v ,d) (

consis,max

)

:

  size =.. [ingewikkeld]
) }.

In a binary system.


Eg., under (v

=

2 );
from (d

=

{1, 2, 3,

..

} );
follows (u (

consis,max

)

=

{5, 941, CA 7,6 *10**39,

..

} ).
{Nb. How is u(

C

)
to be calculated for any tuple (v,d)? There are various calculation methods for this.
The starting point is always the set

T

·(v,d) (with size t).
(1) The most extentional method:
Code the logical relations herein as digital truth value patterns.
Construct the power set, the collection of all forms of reasoning

U

·(v,d ).
Go through all subsets of this collection, and check them for consistency.
First of all, each subset falls off with length (l >

B

·(v,d) )/2) because these will always contain at least one complementary pair of elements.
Next, approach each remaining subset as a conjunction, and apply exhaustive semantic reduction to it.
When the outcome is false (falsum), the subset falls off.
If not, add her to the number of consistent subsets.
This is a completely reliable method, however already at (d > 2) it becomes practically unfeasible due to the huge size of

U

·(v,d) and rapidly increasing length of the subsets.
(2) A more economical method is as follows:
Remove from

T

·(v,d) the element falsum. The result is the consistent basic set.
Then build a matrix for the consistent subsets, sorted in ascending order of length, obviously to the maximum extent (l ≤

T

·(v,d))/2). Clearly, the first group of these subsets forms the consistent basic collection, and the elements herein obviously have length 1.
Now add for each next length to each already existing subset always one more element from the consistent basic set, for which applies:
• The element is not yet present in that subset.
• The thus extended subset does not yet occur in the group of the same length.
• The newly created subset, if approached as a conjunction to which exhaustive semantic reduction is applied, does not result in false (falsum).
This way we will have to 'remember' much less different, and less long, subsets at the same time.
In case of a limited (d ≤ 2) this appears to be an exact and efficient method.
Unfortunately, with a larger d this method soon also becomes unfeasible due to increasing subset length.
E.g. for (d

=

3) the numbers at subset lengths 1 to 5 quickly become colossal: {255, 29360, 1806000, 69443724, 1914019296, .. }.
(3) A third method works completely intentionally, but with very rough estimates.
We saw above that the size of

T

·(v,d) can be obtained, inter alia, from the sum of the the binomial coefficients per subset of

T

·v,d of the number of logical relationships t above the possible length t1 of that subset.
The consistent version of

U

·v,d will deviate from this on two points:
• Lengths of the subsets amount up to (l ≤

T

·(v,d))/2);
• The number of consistent subsets by length will always be less than the corresponding binomial coefficient. This part can be estimated on roughly average 0.9 percent.
E.g. for (d

=

3) a trend can be derived which finalizes at CA 7,6 *10**39.

3.2.1.2.  Consistent arguments of (1), without semantic redundancy within arguments.


This set is identical to the preceding one, but now after (exhaustive) paraphrasing reduction within each subset.
In effect, all logically 'weaker' elements within the subsets disappear, without loss of information. As a result, many 'double' subsets appear, which of course may be deleted, likewise without loss of information.
The set of all possible unique minimal consistent arguments, say

U

·(v,d )(

Cm

)
, thus consists of a (semantically equivalent) compression of

U

·(v,d)(

C

)
- through paraphrasing and then doublure reductions of its subsets.

Size.


Interestingly, the size of this set is equal to that of the set

T

·(v,d), in which each logical relation takes up precisely one separate subset, with exception of the one element falsum.
{ v, d, t, u(

C

)

|

(u(

Cm

)
((u(

Cm

)

=

|

U

·(v,d)(

Cm

)

|

);
(u(

Cr

)
((u (

Cr

)

=

|

U

·(v,d) (

Cr

)

|

);
(u1(

C

)
((U* [u1](

C

)

U

·(v,d)(

C

)
);
(u1(

Cr

)
((U* [u1](

Cr

)

:=

parf-rdc.

(U* [u1](

C

)
) (U*[u1] (

Cr

)

U

·(v,d )(

Cr

)
) )u1(

Cr

)
) )u1(

C

)
) )u(

Cr

)
);
(

U

·(v,d)(

Cr

)

:=

((u1(

C

)
:= 1,

..

u(

C

)
)
(u1(

Cr

)
(u1(

Cr

)

=

u1(

C

)
)u1(

Cr

)

|

U*[u1](

Cr

)
) ) );
((

U

·(v,d)(

Cm

)

:=

doub-rdc.

(

U

·(v,d)(

Cr

)
);
(u1(

Cm

)
((U* [u1](

Cm

)

U

·(v,d)(

Cm

)
);
((u[u1](

Cm

)

=

|

U*[u1](

Cm

)

|

)   (u[u1](

Cm

)

=

1 ) ) )u1 (

Cm

)
) );
(u(

Cm

)
 

=

(U*[u1](

Cm

)

U

·(v,d)(

Cm

)
)

|

u[u1](

Cm

)
;
 

=

(t -1 ) ) )u(

Cm

)
)u(

C

),
t, d, v }.

In a binary system.


Eg., under (v

=

2 );
from (d

=

{1, 2, 3,

..

} );
follows (u (

consis,max;mnm

)

=

{3, 15, 255,

..

} ).

3.2.1.3.  Consistent arguments of (2), without semantic redundancy between arguments.


Next we consider the arguments of

U

·(v,d)(

Cm

)
that may each, being a domain state from

B

 (v,d), directly constitute an image of the associated domain.
As we saw before, each of these consists of d object states

H

 (v,d) : for each object precisely one.
The paraphrase reduced set of all possible unique minimal consistent arguments, say

U

·(v,d)(

Cmr

)
, thus consists of a selection of subsets of

U

·(v,d)(

Cm

)
.

Size.


The size of

U

·(v,d)(

Cmr

)
is of course equal to b.
{ v, d, b, u(

Cm

)

|

(u(

Cmr

)
((u(

Cmr

)

=

|

U

·(v,d)(

Cmr

)

|

);
((

U

·(v,d)(

Cmr

)

:=

parf-rdc.

(

U

·(v,d)(

Cm

)
) );
(u1(

Cmr

)
((U *[u1](

Cmr

)

U

·(v,d)(

Cmr

)
)
((u[u1](

Cmr

)

=

|

U*[u1](

Cmr

)

|

)   (u[u1](

Cmr

)

=

d ) ) ) u1(

Cmr

)
);
(

U

·(v,d)(

Cmr

)

:=

(U*[u1](

Cmr

)
) );
(u(

Cmr

)
 

=

(U*[u1](

Cmr

)

U

·(v,d)(

Cmr

)
)

|

u[u1];
 

=

b ) ) )u(

Cmr

)
)u(

Cm

),
b, d, v }.

Example.


The previous version of the 'minimal' set,

U

·(v

=

2,d

=

1)
(

Cm

)
,   after this operation:

U

·(v

=

2,d

=

1)
(

Cmr

)
 

=

{ {

$

(10)} ,{

$

(01)} };
The syntactical expressions (formulas) usually applied thereby for the associated logical relations are, respectively:

U

·(v

=

2,d

=

1)
(

Cmr

)
 

=

{ {' A'} ,{'A'} }.
We can view the situation also with a slightly larger set.

Example.


With two truth values (v

=

2, binary system) and two items (d

=

2) the set

U

·(v,d)(

Cmr

)
may consist of the following subsets with elements (truth-value patterns), in arbitrary order:

U

·(v,d)(

Cmr

)
 

=

{ {

$

(1000) } ,{

$

(0100) } ,{

$

(0010) } ,{

$

(0001) } }.
The syntactical expressions (formula's) usually applied thereby for the associated logical relations are, respectively:

U

·(v,d)(

Cmr

)
 

=

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

In a binary system.


Eg., under (v

=

2 );
from (d

=

{1, 2, 3,

..

} );
follows (u (

consis,max;mnm,rdc.

)

=

{2, 4, 8,

..

} ).

3.2.1.4.  Consistent arguments of (3), with all derivable consistent reasoning links.


These are the so-called 'maximally consistent' subsets (Not to be confused with the set under (1)).
For this type of (sub)sets precise criteria are defined.
(1) It only contains arguments which are compatible (consistent) with the other elements within the (sub)set.
(2) Each semantically different element that will be added to the (sub)set will lead to contradiction with one ore more elements present, thus inconsistency of the (sub)set.
The set of all possible unique 'maximally consistent' arguments, say

U

·(v,d )(

mC

)
, consists of all subsets of

U

·(v,d) (

Cmr

)
that are maximally extended while still staying consistent.
The result thus consists of a selection from

U

·(v,d)(

C

)
of those (unique, consistent) subsets of maximal size that are (naturally) still internally consistent, and also mutually consistent.
Each subset of the set

U

·(v,d) (

mC

)
belongs to the class, or type, of so called Hintikka sets.
(The reverse doesn't necessarily apply).

Size.


The size of

U

·(v,d)(

mC

)
equals half of t .
{ v, d, b, t, u(

C

)

|

(u(

mC

)
((u(

mC

)

=

|

U

·(v,d)(

mC

)

|

);
(u1(

C

)
((U* [u1](

C

)

U

·(v,d)(

C

)
); (((u[ u1](

C

)

=

|

U*[u1](

C

)

|

) (1

u[u1](

C

)

(t /2 ) ) );
((u[u1](

C

)

=

(t /2 ) )
(u1(

mC

)
((U* [u1](

mC

)

:=

U*[u1](

C

)
) (U*[u1](

mC

)

U

·(v,d)(

mC

)
) )u1(

mC

)
);
(

U

·(v,d)(

mC

)

:=

(U*[u1](

C

)
) );
(u(

mC

)
 

=

|

(u1(

mC

)
:= 1,

..

u(

mC

)
)
(U*[u1] (

mC

)

U

·(v,d) (

mC

)
) u[u1];
 

=

b ) ) )u(

mC

)
)u(

C

),
t, d, v }.

In a binary system.


Eg., under (v

=

2 );
from (d

=

{1, 2, 3,

..

} );
follows (u(

mC

)

=

2, 8, 128, 32 768,

..

} ).

Example.


The previous version of the 'minimal' set,

U

·(v

=

2,d

=

1)
(

consis

)
  after this operation:

U

·(v

=

2,d

=

1)
(

mC

)
 

=

{ {

$

(11), ,

$

(10)} ,{

$

(11), ,

$

(01)} };
The syntactical expressions (formula's) usually applied thereby for the associated logical relations are, respectively:

U

·(v

=

2,d

=

1)
(

mC

)
 

=

{ {' T' ,' A'} ,{' T' ,'A'} }.
We can view the situation also with a slightly larger set.

Example.


With two truth values (v

=

2, binary system) and two items (d

=

2) the set

U

·(v,d) (

mC

)
may consist of the following 4 subsets of each 8 elements (truth value patterns), here stated in arbitrary order, and in the usual syntactical formula forms:

U

·(v

=

2,d

=

2)
(

mC

)
 

=


{ {

$

(1000) ,

$

(1100) ,

$

(1010) ,

$

(1001) ,

$

(1110) ,

$

(1101) ,

$

(1011)

$

(1111) }
,{

$

(0100) ,

$

(1100) ,

$

(0101) ,

$

(0110) ,

$

(1110) ,

$

(1101) ,

$

(0111)

$

(1111) }
,{

$

(0010) ,

$

(0011) ,

$

(1010) ,

$

(0110) ,

$

(1110) ,

$

(1011) ,

$

(0111)

$

(1111) }
,{

$

(0001) ,

$

(0011) ,

$

(0101) ,

$

(1001) ,

$

(1101) ,

$

(1011) ,

$

(0111)

$

(1111) } }.
The syntactical expressions (formulas) usually applied thereby for the associated logical relations are, respectively:

U

·(v

=

2,d

=

2)
(

mC

)
 

=


{ {'( A B)' ,' A' ,' B' ,'( A B)' ,'( A B)' ,'(A B)' ,'( A B)' ,' T' }
,{'( A B)' ,' A' ,'B' ,'( A

#

B)' ,'( A B)' ,'( A B )' ,'(A B)' ,' T' }
,{'(A B)' ,'A' ,' B' ,'( A

#

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

3.2.2.  True arguments.


At last we examine which of the consistent arguments may be true.
For such an so-called evaluation there are two possibilities.

3.2.2.1.  Validity - independent of domain.


Logically valid is in any case one or more of the consistent arguments of the (maximal) collection of possible minimal consistent arguments,

U

·(v,d) (

Cm

)
.
The set of all possible unique logically valid arguments, say

U

·(v,d) (

Cmd

)
, thus in all cases consists of one complex element: the disjunction of all arguments from that set, each of which as said consisting of one logical relation.

Size.


{ v, d, u(

Cm

)

|

( u(

Cmd

)
((u(

Cmd

)

=

|

U

·(v,d)(

Cmd

)

|

);
(n ((n

=

u (

Cm

)
) ((n

=

(t -1 ) )
(

U

·(v,d)(

Cmd

)
 

:=

{U*[1](

Cm

)
U *[2](

Cm

)

..

U* [n](

Cm

)
};
 

:=

((u1(

Cm

)
:= 1,

..

u(

Cm

)
)
(U*[u1](

Cm

)

U

·(v,d)(

Cm

)
)u1(

Cm

)

|

U*[u1] (

Cm

)
) ) ) )n );
(u(

Cmd

)
 

=

1 ) )u (

Cmd

)
)u(

Cm

)
, d, v }.

Example.


With two truth values (v

=

2, binary system) and two items (d

=

2) the set

U

·(v,d) (

Cmd

)
consists of one subset with one element (truth value pattern):

U

·(v

=

2,d

=

2)
(

Cmd

)
 

=

{ {

$

(1111) } }.
The syntactical expression (formula) usually applied thereby for the associated logical relation is:

U

·(v

=

2,d

=

2)
(

Cmd

)
 

=

{ {'T' } }.

3.2.2.2.  Truth - dependent of domain.


Only when we apply the arguments to a specific domain, will clarify whether one or more domain states of

B

·(v,d) apply, or so to say 'are the case'. By this, paraphrasing reduction takes place of each of the yet 'open' options from the disjunction of consistent arguments

U

·(v,d)(

Cmd

)
(through transferent equivalence reduction). Because this disjunction tegelijk contains all possibilities of satisfiable arguments, this operation boils down to exhausting degressive reduction.
The final result of this is the set of all possible unique true arguments, zeg

U

·( v,d)(

rdu

)
. This consists in all possible cases of one element: 'truth' ( verum, that is value '

$

1').
With this, we lose by the way every possiblity to derive any further information, in other words, all logical power. This last step therefore brings us at the end of the entire cycle of expansion and reduction of a logical system within the range of its value scale.

Size.


{ v, d, u(

Cmr

)

|

( u(

rdu

)
((u(

rdu

)

=

|

U

·(v,d)(

rdu

)

|

);
(u1(

Cmr

)
((U*[u1](

Cmr

)

U

·(v,d) (

Cmr

)
) ((U*[u1](

Cmr

)
)

$

=

1 ) ((U*[ u1](

Cmr

)

$

1 )
((

U

·(v,d)(

rdu

)

=

U*[u1](

Cmr

)
) (

U

·(v,d)(

rdu

)

$

1 ) ) ) ) )u1(

Cmr

)
);
(u(

rdu

)
 

=

1 ) )u (

rdu

)
)u(

Cmr

)
, d, v }.

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 )
%