Course / training:Method for Logical AnalysisPrinciples of Formal logic.Combinatory Explosion in Logical SystemsContents
System of Logic
1. Starting parameters
2. Combinatory possibilities.
2.1. Semantic expansion.
3. Interpretation.
2.1.1. Elementary object states.
2.2. Syntactic expansion.2.1.2. Domain states. 2.1.3. Logical relations. 2.1.4. Truth values table. 2.1.5. Arguments. (Semantic). [ 2.1.6. Inference schemes (Syntactic). [ 2.1.7. Inferences, derivations (Semantic).
3.1. Syntactic reduction.
3.1.1. Language signs to reasoning links.
3.2. Semantic reduction.3.1.2. Reasoning links to Derivations. 3.1.3. Derivations to Arguments.
3.2.1. Consistent arguments.
3.2.1.1. Consistent
Arguments: without immediate contradictions.
3.2.2. True arguments.3.2.1.2. Consistent arguments of (1), without semantical redundancy within arguments. 3.2.1.3. Consistent arguments of (2), without semantical redundancy between arguments. 3.2.1.4. Consistents arguments of (3), with all derivable consistent reasoning steps. Combinatory Explosion in Logical SystemsIntroduction: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:
The ways in which those combinations can be made, and the values that these combinations can take, are determined by
the laws of logic.A number of input data are combined, and next certain data are derived from the combination. 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).S!) : the semantics, a set of ordering rules, ofS!.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).L!) : the syntaxis, or grammer, a set of ordering rules, ofL!.WFF*( L!)) : the set of well-formed statements (formulas) ofL!.1. Starting parameters.1.1. Objects.Applicable in PPLand 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 setD·d may consist of the following elements (objects), represented by proposition symbols and stated in arbitrary order: { (d =2 )(D·d={' A' ,' B'} ) }.S![s1] however extremely minimal, if not futile.Some examples of statements in such a 'minimal' system, stated in a formal language:
{ (d
Likewise, the domain may consist of only one element. But then the inference systems =0 )(D·d={} ) : ({}=(v) {} ); (({})$=(v)$0 ); ({}=(r)$0 ); etc.}.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 setV·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
In =|V*(mgb)|);(2 ≤v<0 ) }.PDLsome further parameters come into play.
(2a) p : total number of predicate-variables (attributes, predicate names); including identity, '='.
The (maximum) number of items a in (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). PDLis a derivate of the latter three.{p ≤a≤(p *MAX(1,(r *n)) }.PDLsystem we have sufficient information about the parameters p, r and n, we can calculate a, and may reason further following the rules for aPPLsystem.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 setH·(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 setD·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-square (Χ2), 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 setB·(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 }.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 - ofD·d . I.e.:
(v
=2)(b =|B·(2,d)|;=|P**d|).
Eg., under (v
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):=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,..} ).
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 setT·(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 ofD·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 setV·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.
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 setU·(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 ofT·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 ofD· 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). |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
) 
U*[u1](
(u1(