Method of 'Formal Logic'
Diagrams
Logical levels and criteria
Contents
1. Level I: Truth / Falsity of statements
2. Level II: Satisfiability / validity
2.1. Truth-values table for PPL - bivalid, for two variables.
2.2. Truth-values table for PDL - bivalid, for two variables.
2.3. Truth / validity and logical power.
2.4. Formulas in standarized vorm.
2.5. Judging theories. (sets of propositions).
2.6. Contingency and Presupposition.
2.7. Basic Valid and Invalid derivations.
2.8. Validity, Satisfiability and Contingency.
2.9. Relations between logical criteria of level II.
2.2. Truth-values table for PDL - bivalid, for two variables.
2.3. Truth / validity and logical power.
2.4. Formulas in standarized vorm.
2.5. Judging theories. (sets of propositions).
2.6. Contingency and Presupposition.
2.7. Basic Valid and Invalid derivations.
2.8. Validity, Satisfiability and Contingency.
2.9. Relations between logical criteria of level II.
4. Table with some Milestones in Meta-logic
5. Criteria in formal logic
Meta-truth: logical criteria
Logical quality |
|---|
Level I:
Truth / Falsity
of statements
1.1. Truth-values table for PPL for two variables.
In a formal logical system all possible logical relations are completely defined by a chosen vocabulary by means of a Truth values-table.
The Truth-values table for the most simple logical system, propositional logic (PPL), covers - for any chosen formalism or format - in any way all basic combinations that are involved in the most elementary beginning of any form of reasoning. Because of this, it really provides the very first, necessary foundings of accurate combinatory thinking.
Truth-values table PPL - for one variable.
This Truth-values table contains all possible orderings of values of two variables (propositions) in PPL, than can adopt two values.
The basis consists of one variable by two values = two basic combinations. With this, two orders are possible of series of truth values: each of which reflects a unique logical relation. Thus the following table arises of the most simple nature, of two rows by two columns is four cells.
| 1 | 2 |
|---|---|
| 1 | 0 |
| 0 | 1 |
| T | F |
| A | ¬A |
| ¬B | B |
Truth values |
||
|---|---|---|
1 |
± |
0 |
True,verum: Verification. | Unspecified,uninterpreted: Indefinite. | False,falsum: Falsification. |
Truth value(value, valor): |
||
$(G)=1. | (0 <$(G)<1). | $(G)=0. |
Truth value assignment(valuation): |
||
| V!(G) :=1. | ¬V!(G)  {0,1}. | V!(G) :=0. |
Truth value determination(evaluation), through a finite proof: |
||
 i E![i]
 G. | (¬i E![i]
G)  (¬j E!
[j] ¬G). | i E![i]
¬G. |
Interpretation(denotation, assignment): |
||
m M![m] G. | (¬m M![m]G) (¬n
M![n]¬G). | m M![m] ¬G. |
Level II:
Satisfiability / validity
2.1. Truth-values table for PPL - bivalid.
This truth-values table contains all possible ordenings of values under the combination of two variables that each can adopt two values.
Its base consists of 2 values to the power of 2 variables = 4 basic combinations or (possible) domain states.
With this, 2 to the power of 4 = 16 orders are possible of series of truth values.
Each of these reflects a unique logical relation, or (possible) domain states-relation.
Thus the following table arises of 4 rows by 16 columns is 64 cells; each containing one precise truth value.
Table bivalid value combinations - with two variables, interpreted for PPL |
|||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 |
| 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 |
| ¬F | ¬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) |
| A \ B | A
 B | A
 B | A ||B |
||||||||||||
2.2. Truth-values table for PDL - bivalid.
In predicate logic (PDL) attributes (or predicates) may be applied to various domain elements.
Because of this, the combinatory possibilities again increase in hyper-exponential ways.
Next, in PDL so-called quantors may be applied to predications on object-variables, to represent systematic relations between predications with identical predicate names, on identical variable names in a concise manner (conjunctive relations through universal quantors, disjunctive relations through existential quantor). However, before we succeed in finding these regularities, we still have tot deal with that combinatory explosion.
Following here is a simple example: for a bivalid system, of a 'tiny' size: consisting of one predicate, of arity one, and a domain of only two elements. With this we end up again with 16 possible logical relations.
Table bivalid value combinations - with two variables, interpreted for PDL |
|||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 |
| T | F | A1 | A 2 | ¬A1 | ¬A2 | A
1 A2 | A1
¬A2 | ¬A1
A2 | ¬A1
¬A2 | A1
A2 | A1
¬A2 | ¬A1
A2 | ¬A1
¬A2 | A1
A2 | A1 # A 2 |
| ¬T | ¬F | ¬¬A1 | ¬¬A 2 | ¬A1 | ¬A2 | ¬(¬A
1 ¬A2) | ¬(¬A
1 A2) | ¬(A
1 ¬A2) | ¬(A
1 A2) | ¬(¬A
1 ¬A2) | ¬(¬A
1 A2) | ¬(A
1 ¬A2) | ¬(A
1 A2) | ¬(A 1 # A2) | ¬(A1
A2) |
| A1 \ A2 | A1 A2 |
A1 A2 |
A1 |A2 |
||||||||||||
 x A[x] |
¬x A[x] |
x A[x] |
¬x A[x] |
||||||||||||
| ¬x ¬A[x] |
x ¬A[x] |
¬x ¬A[x] |
x ¬A[x] |
||||||||||||
2.3. Truth value and logical power.
Logical power is inversely proportional to truth value.
Given a formula F - that is a each possible logical relation under formal system
L!
- of set T * (with size t=
v**(v**d)). The following applies:
(a)
F is derivable from the maximum logical power in
{ j ( (F[j]
T*) 
($0
F[j]) )j;
j ($0 F
[j]) j;
($0 ( j
F[j]) );
($0 ( j F
[j]) );
($0 ( j
F[j]) );
($0 (T*
)) }.
(b)
F serves to derive the minimum logical power in
{ j ( (F[j]
T*) (F[j]
j (F[j]
(( j F
[j])
(( j F
[j])
((j F[j])
((T*)
(c)
Combining (a) and (b).
{ j ( (F[j]
T*) ( ($0
F[j]) (F[j]
j ( ($0 F
[j]) (F[j]
( ($0 (j
F[j]) ) ( (
j F[j])
( ($0 (j
F[j]) ) ( (
j F[j])
( ($0 (j F
[j]) ) ( (j F[j])
( ($0 (j
F[j]) ) ( (
j F[j])
( ($0 (T*
)) ( (T*)
($0
In formal logic a set of logical formulas is called a theory. The formulas in the set in general refer to statements or arguments (propositions).
In formal logic a number of standarized forms exists by which formulas or sets of formulas can be represented in a clear, precise and compact manner, so that they can be processed and be judged efficiently, so-called normal forms. ]-->
A convenient form for formulas when we want to judge them is the Conjunctive Normal Form (
A,
}.
General structure of a
{ (T*
( k ( (K*[k]
(K*[k] [ F[2] .. ] ] F[n[k]]
} )
(n[k]
(K*[k]
(j[k]=1,..n[k]) F[j[k]] } )
( ( j ( (F[j]
K*[k])
F[j] [ G[j,2] .. G[m[j[k]]]
] ] } )
(m[j[k]]
( (F[j]
(h[j[k]]=1,..h[n[k]]) G[h[j[k]]]) } )
( (0 (0
How can we judge the logical 'status', or semantical value, of such a set? This is dependent of the formal system, or the logical language in which the set has been formulated.
We can only mention some preconditions that in general apply to judge a set of formulas.
To be distinguished:
Notice how only the latter relation is necessarily always valid, and may also be derivable in a explicit, complete, precise and secure way .. (although dependent of finitely-provability and Decidability).
{ A formula F[j] is contingent:
j ( CONTIN(F[j] );
Logical power and contradiction.
F is derivable from the maximum logical power in
L!
: i.e. contradiction (falsity under all conditions); or falsity; or truth value$
0.{ j ( (F[j]
T*) ($0
F[j]) )j;j ($0 F
[j]) j;($0 ( j
F[j]) );($0 ( j F
[j]) );($0 ( j
F[j]) );($0 (T*
)) }.Logical power and truth.
F serves to derive the minimum logical power in
L!
: i.e. validity (truth under all conditions); or truth; or truth value$
1.{ j ( (F[j]
T*) (F[j]
$
1) )j;j (F[j]
$
1) j;(( j F
[j]) $
1 );(( j F
[j]) $
1 );((j F[j])
$
1 );((T*)
$
1 ) }.Contradiction, Logical power and truth.
Combining (a) and (b).
{ j ( (F[j]
T*) ( ($0
F[j]) (F[j]
$
1) ) )j;j ( ($0 F
[j]) (F[j] $
1 ) )j; ( ($0 (j
F[j]) ) ( (
j F[j])
$
1 ) ); ( ($0 (j
F[j]) ) ( (
j F[j])
$
1 ) ); ( ($0 (j F
[j]) ) ( (j F[j])
$
1 ) ); ( ($0 (j
F[j]) ) ( (
j F[j])
$
1 ) ); ( ($0 (T*
)) ( (T*)
$
1) );($0 $
1) }.2.4. Formulas in standarized vorm.
In formal logic a set of logical formulas is called a theory. The formulas in the set in general refer to statements or arguments (propositions).
In formal logic a number of standarized forms exists by which formulas or sets of formulas can be represented in a clear, precise and compact manner, so that they can be processed and be judged efficiently, so-called normal forms. ]-->
A convenient form for formulas when we want to judge them is the Conjunctive Normal Form (
CNF
). A formula inCNF
consists of a conjunction of disjunctions. In other words, on the mainline of argument ation a juxtaposition of one or more conjuncts exists, while each conjunct is a disjunction consisting of at least one simple formula (an atom or a literal).A
CNF
thus makes only use of the connectives {¬,,
}.General structure of a CNF
set:
{ (T* =
WFF*(L!
PDl)); ( k ( (K*[k]
CNF
*(T*))(K*[k] =
{ [ F[1] [ F[2] .. ] ] F[n[k]]
} )(n[k] =
|
K*[k]|
)(K*[k] =
{
(j[k]=1,..n[k]) F[j[k]] } ) ( ( j ( (F[j]
K*[k])F[j] =
{ [ G[j,1] [ G[j,2] .. G[m[j[k]]]
] ] } )(m[j[k]] =
|
F[j]|
( (F[j] =
{
(h[j[k]]=1,..h[n[k]]) G[h[j[k]]]) } ) ( (0 >
j[k]≥
n[k] ) (0 >
h[j[k]]≥
m[j[k]]) ) ) )j )k ) }.2.5. Judging theories (sets of propositions).
How can we judge the logical 'status', or semantical value, of such a set? This is dependent of the formal system, or the logical language in which the set has been formulated.
We can only mention some preconditions that in general apply to judge a set of formulas.
General requirements for judging a theory :
(a)
{ k ( (K*[k]
( ( j ( (F[j]
K*[k])
( (F[j]
( ( ( h ( (G[h[j[k]]]
F[j]) (G[h[j[k]]]
) (K*[k]
(b)
{ k ( (K*[k]
( ( j ( (F[j]
K*[k])
( (F[j]
( ( ( h ( (G[h[j[k]]]
F[j]) (G[h[j[k]]]
) (K*[k]
(c)
Neither (a) nor (b).
The set is valid (is a tautology).
{ k ( (K*[k]
CNF
*(T*)) ( ( j ( (F[j]
K*[k]) ( (F[j]$
=
1) ( (|
F[j]|
>
1) ( h ( (G[h[j[k]]]
F[j]) (G[h[j[k]]]
$
=
1) )h ) ) ) )j )(K*[k]$
=
1) )k }.(b)
The set is inconsistent (contains contradiction).
{ k ( (K*[k]
CNF
*(T*)) ( ( j ( (F[j]
K*[k]) ( (F[j]$
=
0) ( (|
F[j]|
>
1) ( h ( (G[h[j[k]]]
F[j]) (G[h[j[k]]]
$
=
0) )h ) ) ) )j )(K*[k]$
=
0) )k }.(c)
The set is contingent (is undecided).
Neither (a) nor (b).
2.6. Contingency and Presupposition.
To be distinguished:
(1) Logical presupposition is what completes the grounds of an invalid inference pattern
(in particular, contingency), thus making the latter valid.
She is only bounded to universal abstract patterns following laws and principles of a system of (formal, or combinatory) logic.
(2) Linguistic presupposition is different: namely, what is implied by a language expression or sign-giving regardless of any truth value of the latter in her references (is as it where a consequens in termines).
She is bounded to specific language symbols and structures following conventional rules of syntax and lexicon of a (human) language system.
Both are therefore not directly physically-bound (i.e. not to time, space, energy, matter).
(3) A prejudice is an internal, mental or psychological content, in particular of cognitive nature.
Thus she is bounded to a person or group (performative, author, source). Because of this, she is at least in part, and at least first - through neuro-physiology - physically-bound. Thus she is essentially incidental of nature (although possibly of relative long duration). She precedes in time actual conclusions, decisions, utterances, behavior, etc..
The mutual relations:She is only bounded to universal abstract patterns following laws and principles of a system of (formal, or combinatory) logic.
(2) Linguistic presupposition is different: namely, what is implied by a language expression or sign-giving regardless of any truth value of the latter in her references (is as it where a consequens in termines).
She is bounded to specific language symbols and structures following conventional rules of syntax and lexicon of a (human) language system.
Both are therefore not directly physically-bound (i.e. not to time, space, energy, matter).
(3) A prejudice is an internal, mental or psychological content, in particular of cognitive nature.
Thus she is bounded to a person or group (performative, author, source). Because of this, she is at least in part, and at least first - through neuro-physiology - physically-bound. Thus she is essentially incidental of nature (although possibly of relative long duration). She precedes in time actual conclusions, decisions, utterances, behavior, etc..
(·) Any given language expression may imply a linguistic presupposition.
(·) A linguistic presupposition may originate from the presence of a psychological (cognitive) content - or, not too rarely, absence of such.
(·) A psychological (cognitive) content may entirely or partly be construed on basis of the presence of prejudice.
(·) A prejudice may come from an invalid inference c.q. contingency.
(·) An invalid inference, in particular a contingency, necessarily and simultaneously implies a logica l presupposition.
(·) A linguistic presupposition may originate from the presence of a psychological (cognitive) content - or, not too rarely, absence of such.
(·) A psychological (cognitive) content may entirely or partly be construed on basis of the presence of prejudice.
(·) A prejudice may come from an invalid inference c.q. contingency.
(·) An invalid inference, in particular a contingency, necessarily and simultaneously implies a logica l presupposition.
Notice how only the latter relation is necessarily always valid, and may also be derivable in a explicit, complete, precise and secure way .. (although dependent of finitely-provability and Decidability).
{ A formula F[j] is contingent:j ( CONTIN(F[j] );
• F[j] is neither true, nor false;
( ((¬ F[j])
(¬ ¬F[j]))
( ((¬ F[j])
(¬ ¬F[j]))
• The truth-value pattern c[t] of F[j] lies between
( t ( (F[j]$ = c[t]
) ($0
• There exists a formula X[i]) that is logically equivalent to F[j], and that is syntactically identical to the maximal semantical reduct of F[j], i.e. F[j]
( i ( ( (F[j]
X[i])
(F[j]
((¬ X[i])
(¬ ¬X[i])) );
(X[i] F[j]);
(X[i] (
F[j]));
('Assuming X[i] satisfies F[j])' *
('F[j] presupposes X[i])' * )
i ) )j }.
$
0[00..] and$
1[11..]. ( t ( (F[j]$ = c[t]
) ($0 <
c[t]<
$
1) )t;• There exists a formula X[i]) that is logically equivalent to F[j], and that is syntactically identical to the maximal semantical reduct of F[j], i.e. F[j]
equiv-reduc
.( i ( ( (F[j]
X[i])(F[j]equiv-reduc
=
(syn
) X[i])((¬ X[i])
(¬ ¬X[i])) );(X[i] F[j]);
(X[i] (
F[j]));('Assuming X[i] satisfies F[j])' *('F[j] presupposes X[i])' * )
i ) )j }.2.7. Basic Valid and Invalid derivations.
(a)
(Semantical equivalent-reduction; Paraphrase).
(Semantical degressive-reduction; Subsumption).
(non sequitur [nonseq] fallacy).
(Contradiction; Reductio ad absurdum).
Equivalent-validity.
(Semantical equivalent-reduction; Paraphrase).
E.g.: { h j ( (¬F[h]
G[j]) 
(F[h]
G[j]) )j ,h }.
(b) h j ( (¬F[h]
G[j]) (F[h]
G[j]) )j ,h }.Degressive-validity.
(Semantical degressive-reduction; Subsumption).
E.g.: { h j ( (F[h]
G[j]) (k l ( (F[h]
C[k]) (G[j]
D[l]) )l ,k ) )j ,h }.
(c) h j ( (F[h]
G[j]) (degres
) (k l ( (F[h]
C[k]) (G[j]
D[l]) )l ,k ) )j ,h }.
Contingent-invalidity.
(non sequitur [nonseq] fallacy).
E.g.: { h j ( (F[h]
G[j]) (k ( (F[h] D
[k]) G[j] )k ) (
l ( F[h] (G[j]
C[l]) )l ) ) )j ,h }.
(d) h j ( (F[h]
G[j]) (nonseq
) ( (k ( (F[h] D
[k]) G[j] )k ) (
l ( F[h] (G[j]
C[l]) )l ) ) )j ,h }.Inconsistent-invalidity.
(Contradiction; Reductio ad absurdum).
E.g.: { h j ( (F[h]
G[j]) (¬G[j]) )j ,h
}.
h j ( (F[h]
G[j]) (contrad
) (F[h]¬G[j]) )j ,h
}.
2.8. Validity, Satisfiability and Contingency.
Diagram Validity / Satisfiability / Contingentie |
||
|---|---|---|
1 |
± |
0 |
Not necessarily untrue:Satisfiable,'Logically possible'. (Is not yet equivalent to 'possibly true').
SATBL(G);
(TAUT(G) CONTIN(G);¬ ¬G;((G ) (¬
(¬G ) ) );{ k ( (G$ = c
[k]) (c[k] >$0) )k };{ j F[j]
G };{ m M![m] G }.{ j ((F[j]
¬F[j]) G) }; |
Impossibly true:Unsatisfiable,Logically excluded. 'Excluded grounds'.
¬SATBL(G);
¬G;{ k ( (G$ = c
[k]) (c[k] = $0) )k };{¬j ((¬
¬F[j]) (F[j]
G)) };{¬m M![m] G }.{ j ((F[j]
¬F[j]) G) }; |
|
Consistency,Widerspruchsfreiheit. Set K* is consistent: From K* no contradiction is derivable.
CONSIS(K*);
{ ¬( (K*  G)
(K* ¬G) ) }; { ¬(K*
 ) }; { j ( ¬( (K*
F[j]) (K*
¬F[j]) )j }; { j ( ¬( {K*
 F[j]}
)¬( {K* ¬F[j]}
) )j }; { ¬j ( ( F[j]
K* )( ¬F[j] K
* ) )j }. |
Inconsistency,Inconsistent-invalidity. Set K* is inconsistent. From K* a contradiction can be derived.
INCNS(K*);
¬CONSIS(K*); { (K* G)
(K* ¬G) }; { K*
}; { j ( (K*
F[j]) (K*
¬F[j])j }; { j ( ( {K*
F[j]}
)( {K* ¬F[j]}
) )j }; { j ( ( F[j]
K* )( ¬F[j] K*
) )j }. |
|
Consistency theorem,Fundamental theorem (Model-existence theorem): 'Consistency implies Satisfiability'. (Every subset : (Consistent Satisfiable)).
{CONSIS(K*)
SATBL(K*)};{¬(K*
) ¬(K*
 )}. |
||
Necessarily / always true:Valid,Tautology, Valid-satisfiability.
TAUT(G);
G;{ k ( (G$ = c
[k]) (c[k] = $1) )k };{¬j ((¬
¬F[j]) (F[j]
¬G)) };{¬m M![m] ¬G }.{¬j (F[j]
¬F[j] G) }; |
Undecided:Contingency,Contingent-invalidity, Contingent-satisfiability. Insufficiently grounded, Indefinite.
CONTIN(G);
{SATBL(G) ¬TAUT(G)};{(¬ G) (¬
¬G)};{ k ( (G$ = c
[k])($0 <c[k]<$1) )k };{ j ((¬
¬F[j]) (F[j]
G)) } { k ((¬
¬F[k]) (F[k]
¬G)) };{ (m M![m] G)(n M! [n] ¬G) }. |
|
Not necessarily-true:Invalid,non sequitur [nonseq]:
NONSEQ(G);
¬TAUT(G);(CONTIN(G) ¬SATBL(G);¬ G;{ k ( (G$ = c
[k]) (c[k] <$1) )k };{ j ((¬
¬F[j]) (F[j]
¬G)) };{ m M![m] ¬G }. |
||
Correctness(Soundness in-formele-zin): 'Derivable implies logical consequence'. Set K* is correct. (Every subset :(Derivable Logical consequence).
CORRECT(K*);
{DRVBL(K*,G) SEQUIT(K*
,G)}; { (K* G)
(K* G) }; { j ( (K*
F[j]) (K*
F[j]) ) }. |
||
Completeness(Vollständigkeit). 'Validity implies Derivability'. Set K* is complete: (Every subset :(Logical consequence Derivable)).
COMPLET(K*);
{SEQUIT(K*,G) DRVBL(K*
,G)}; { (K* G)
(K* G) }; { j ( (K*
F[i]) (K*
F[j]) ) }. |
||
Maximal consistency :Set K* is maximally consistent: (Every subset :(Logical consequence Derivable)).
MAXCONS(K*);
{ CONSIS(K*) COMPLET(K*) };
{ (K* G)
(K* G) }; { j ( (K*
F[j]) (K*
F[j]) )j }; { j ( CONSIS(K* \ {F[j]
})¬CONSIS(K* {F[j]
}) )j }; { j ( ( (F[j]
K*) ( {K* ¬F[j]
} ) ) ( ¬(F[j] K*)
¬( {K* F
[j]} ) ) )j };Implications: { j ( (F[j]
K*)||(¬F[j]K*) )
j }; |
||
| (·) Completeness of
PPL: proof by Emil L. Post (1920, Introduction to a general theory of elementary propositions). (·) Completeness of PDL-I: proof by Kurt F. Gödel (1929/1930, Über die Vollständigkeit des Logikkalküls). |
(·) Incompleteness of
elementary arithmetic (first-order theory of natural numbers according to the logicistic research program,
that was based on classic logic in the Organon of Aristotelis, and had been further developed in the
Grundgesetze der Arithmetik of F.L. Gottlob Frege (1893, 1903) and the Principia Mathematica of
Bertrand Russell and Alfred North Whitehead, parts I-III (1910, 1912, 1913): proved by Kurt Gödel (1931, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme 1 ). |
|
2.9. Relations between logical criteria of level II.
(1)
(By assumption or (re)presentation).
'From strong to weak'.
( Valid Satisfiable /Consistent
).
( Unsatisfiable /Inconsistent /Contradiction
Invalid ).
(2)
(By assumption or (re)presentation).
'From Weak to stromg'.
Valid statement or inference.
(By assumption or (re)presentation).
'From strong to weak'.
( Valid Satisfiable /Consistent
). ( Unsatisfiable /Inconsistent /Contradiction
Invalid ).(2)
Invalid statement or inference: Fallacy.
(By assumption or (re)presentation).
'From Weak to stromg'.
¬ ( Valid Contingent ).
¬ ( Valid Invalid ).
¬ ( Valid Unsatisfiable /
Inconsistent /Contradiction ).
( Valid Contingent ).¬
( Valid Invalid ).¬
( Valid Unsatisfiable /
Inconsistent /Contradiction ).
¬ ( Satisfiable /Consistent Valid
).
¬ ( Satisfiable /Consistent
Contingent ).
¬ ( Satisfiable /Consistent Invalid
).
¬ ( Satisfiable /Consistent
Unsatisfiable /Inconsistent /Contradiction ).
( Satisfiable /Consistent Valid
).¬
( Satisfiable /Consistent
Contingent ).¬
( Satisfiable /Consistent Invalid
).¬
( Satisfiable /Consistent
Unsatisfiable /Inconsistent /Contradiction ).
¬ ( Contingent Valid ).
¬ ( Contingent Satisfiable /
Consistent ).
¬ ( Contingent Invalid ).
¬ ( Contingent Unsatisfiable /
Inconsistent /Contradiction ).
( Contingent Valid ).¬
( Contingent Satisfiable /
Consistent ).¬
( Contingent Invalid ).¬
( Contingent Unsatisfiable /
Inconsistent /Contradiction ).
¬ ( Invalid Valid
¬ ( Invalid Satisfiable /Consistent
).
¬ ( Invalid Contingent ).
¬ ( Invalid Unsatisfiable /
Inconsistent /Contradiction ).
( Invalid Valid¬
( Invalid Satisfiable /Consistent
).¬
( Invalid Contingent ).¬
( Invalid Unsatisfiable /
Inconsistent /Contradiction ).
¬ ( Unsatisfiable /Inconsistent /Contradiction
Valid ).
¬ ( Unsatisfiable /Inconsistent /Contradiction
Satisfiable /Consistent ).
¬ ( Unsatisfiable /Inconsistent /Contradiction
Contingent ).
( Unsatisfiable /Inconsistent /Contradiction
Valid ).¬
( Unsatisfiable /Inconsistent /Contradiction
Satisfiable /Consistent ).¬
( Unsatisfiable /Inconsistent /Contradiction
Contingent ).Level III.
Decidability and Recursivity of formal systems
Diagram Decidability and Recursivity |
|||
|---|---|---|---|
1 |
± |
||
Decidable:The question whether an expression G has a definite (truth) value, can always be answered: The (truth) value of G is always derivable through a finite proof. |
UnDecidable:The question whether an expression G has a definite (truth) value, can not always be answered: The (truth) value of G is not always derivable through a finite proof. |
||
| G is Truth-value
Decidable:
DECIDBL(G);
{( ( G
$1) )||( ( G $0) ) };{( (
G ) ) ||( (
¬G ) ) };Implications: { ( (
G ) ||(
¬G ) ) }.{ (
( G ||¬G ) ) };{ ( G ||¬G ) };{ G ||¬G } (always logical value).$1 (truth). |
G is
Not truth-value deDecidable:
¬DECIDBL(G);
{ (¬ ( G
$1) )(¬
( G $0) ) };{ (¬ (
G ) ) (¬ (
¬G ) ) };Implications: { ¬ ( (
G ) ||(
¬G ) ) };{ ¬ (
( G ||¬G ) ) };{ ¬ ( G ||¬G ) };{ } (no logical value);$0 (no truth). |
||
G is Validity
Decidable:{ ( (
G) ) ||( (¬
G) ) };Implications: { ( (
G ) ||( ¬
G ) ) };{ ( G ) ||( ¬ G ) }.{ TAUT(G) ||¬SATBL(G) } (always validity value).$1 (truth).G is determinate. |
G is Not validity
Decidable:{ (¬ (
G) ) (¬ (¬
G) ) }; Implications: { ¬ ( (
G ) ||( ¬
G ) ) }.{ ¬( G )
¬( ¬G ) }.{ CONTIN(G) } (no validity value).$0 (no truth).G is indeterminate. |
||
Recursive:For all input, the system will be 'halting' (terminating in finite time). |
Non-recursive:For some input the system will be infinitely 'looping'. |
||
|
RC(G);
{ RE(G) CO-RE(G) };{ ( (
G) ) ||( (¬
G) ) };Implications: { ( (
G) ||(¬
G) ) }. |
¬RC(G);
{ ¬RE(G) ¬CO-RE(G) }.{ (¬ (
G) ) (¬ (¬
G) ) };Implications: { ¬ ( (
G) ||(¬
G) ) }. |
||
Recursively |
Co-recursively |
|
|
| Set K* is Recursively enumerable: If K* has a result, then that will always be provable.
RE(K*);
{ k ( (Ks*[k]
K*)j ( (Ks*[k]
F[j])(Ks*[k]
F[j]) )j )k }. |
Complement of K*
is Recursively enumerable: If K* has no result, then that will always be provable.
CO-RE(K*);
{ k ( (Ks*[k]
K*)j ( ¬(Ks*[k]
F[j])¬(Ks*[k]
F[j]) )j )k }. |
Set K* is not Recursively enumerable: If K* has a result, then that will not always be provable.
¬RE(K*);
{ k ( (Ks*[k]
K*)j ( (Ks*[k]
F[j])¬(Ks*[k]
F[j]) )j )k }. |
Complement of K*
is not Recursively enumerable: If K* has no result, then that will not always be provable.
¬CO-RE(K*);
{ k ( (Ks*[k]
K*)j ( ¬(Ks*[k]
F[j])¬¬(Ks*[k]
F[j]) )j )k }. |
| Set K* is Recursively enumerable (through Turing Machine procedure): If K* has a result, then that will always be computable.
RE(K*)TM;
{ k ( (Ks*[k]
K*)j h ((TM[h](Ks*[k]) F[j])
m (TM[m](K*
) (TM[h](Ks*[k]) F
[j]) )m )h ,j )k }. |
Complement of K*
is Recursively enumerable (through Turing Machine procedure): If K* has no result, then that will always be computable.
CO-RE(K*)TM;
{ k ( (Ks*[k]
K*)j h (¬(TM[h](Ks*[k]) F[j])
m ( (TM[m](K*
) ¬(TM[h](Ks*[k]) F
[j]) )m )h ,j )k }. |
Set K* is not Recursively enumerable (through Turing Machine procedure): If K* has a result, then that will not always be computable.
¬RE(K*)TM;
{ k ( (Ks*[k]
K*)j h ((TM[h](Ks*[k]) F[j])
¬m (TM[m](K*
) (TM[h](Ks*[k]) F
[j]) )m )h ,j )k }. |
Complement of K*
is not Recursively enumerable (through Turing Machine procedure): If K* has no result, then that will not always be computable.
¬CO-RE(K*)TM;
{ k ( (Ks*[k]
K*)j h (¬(TM[h](Ks*[k]) F[j])
¬m (TM[m](K*
) ¬(TM[h](Ks*[k]) F
[j]) )m )h ,j )k }. |
(·) 'Effective procedure' (Hilbert, 1900, 1928). (·) 'Recursive function' (Gödel, 1930, 1931). (·) 'Lambda definable function' (Church, 1935, 1936). (·) 'Turing Machine computable function' (Turing, 1936, 1937). |
(·) UnDecidability/ non-recursivity of elementary calculus of natural numbers (elementary number theory): proof by Alonzo Church, (1935/1936, An Unsolvable Problem of Elementary Number Theory). (·) UnDecidability/ non-recursivity of entire elementary arithmetic (first order arithmetic): proof by Alan M. Turing (1936/1937, On computable numbers, with an application to the Entscheidungsproblem). |
||
4.
Table with Some Milestones in Meta-logic
| Author | Year | Formalism | Domain | Criterion | |
|---|---|---|---|---|---|
| Hilbert | 1900,1928 | Effective procedure (hypothetical) | Mathematics, Logic | Decidability; Entscheidbarheit; Entscheidungs-definitheit; |
|
| Post | 1920 |
Truth table method | PPL | Completeness; Vollständigkeit. |
|
| Gödel | 1929/1930 | Deduction | PDL-I | Completeness; Vollständigkeit. Recursively enumerable |
|
| Gödel | 1931 | Gödel-numbering | PDL-I, Arithmetic of Natural numbers First-order theory of natural numbers (Principia Mathematica) | Einige formal unentscheidbare Satze: Incompleteness; Unvollständigkeit. Not recursively enumerable. |
|
| Church | 1935/1936 | Lambda-calculus (Lambda-definable): Recursive functions of positive integers | PDL-I, Arithmetic of
Natural numbers: Elementary number theory | Unsolvable problem: UnDecidability; Unentscheidbarheit. |
|
| Turing | 1936/1937 | (Universal) Turing machine (Turing machine computability) | PDL-I, Arithmetic: First order arithmetic | UnDecidability; Unentscheidbarheit. |
5. Criteria in formal logic
In the overview ' Criteria in Formal Logic' the most important criteria in formal logic are being discussed.
These criteria may be applied to formulas, sentences, sets, theories and (language) systems in logic.
They are meant to represent entirely accurate the most essential characteristics of certain data: quality, scope, possibilities but also limitations.
Criteria in Formal Logic
(1)
Criteria for decisions about content aspects of language expressions.
A.o. satisfiability, validity, contingency, finite-satisfiability, compactness, etc..
(2)
Criteria for decisions about aspects of form and structure of statements.
A.o. derivability, provability, consistency.
(3)
Ie. projections from semantics to syntax.
A.o. completeness.
(4)
Ie. projections from syntax to semantics.
A.o. consistency theorem, correctness, Decidability.
Semantic criteria
Criteria for decisions about content aspects of language expressions.
A.o. satisfiability, validity, contingency, finite-satisfiability, compactness, etc..
(1a) Satisfiability: (Logical possibility): Truth under at least one possible interpretation.
((Well-formed not-Refuted)
Satisfiable).
(1b) Validity (tautology):) Truth under any possible interpretation.
((Well-formed always-True)
Valid).
(1c) Contingency: Satisfiable, but not valid.
(Truth under at least one possible interpretation, maar not all).
((Well-formed (Satisfiable
not-Valid)) Contingent).
(1d) Finite-satisfiability: A (sub)set of formulas is finite and satisfiable.
(((Sub)set (Well-formed
(Finite Satisfiable)))
Finite-satisfiable).
(1e) Compactness: If every finite subset of a - possibly infinite - set is satisfiable,
that the entire set is satisfiable.
(((Every subset: (Well-formed
Finitely satisfiable)) Satisfiable)
Compact).
((Well-formed not-Refuted)
Satisfiable).((Well-formed always-True)
Valid).(Truth under at least one possible interpretation, maar not all).
((Well-formed (Satisfiable
not-Valid)) Contingent).(((Sub)set (Well-formed
(Finite Satisfiable)))
Finite-satisfiable).(((Every subset: (Well-formed
Finitely satisfiable)) Satisfiable)
Compact).(2)
Syntactical criteria.
Criteria for decisions about aspects of form and structure of statements.
A.o. derivability, provability, consistency.
(2a) Derivability: Derivable through syntactical production rules.
((Well-formed result of purely formal operations)
Derivable).
(2b) Provability (finite-derivability): Syntactical derivable through a finite derivation chain.
(((Well-formed result of finite
series of purely formal operations) Finite-derivable)
Provable).
(2c) Consistency: Derivable guarantees non-contradiction.
((Derivable Non-contradiction)
Consistent).
(2d) Maximal consistency: Consistency guarantees inconsistency with every possible
(nonredundant, conjunctive) expansion.
((Consistent (adding of any other formula
inconsistent)) Maximally consistent).
(2e) Negation-completeness: A set K* contains for every well-formed formula in the language either
the confirmation, or the negation.
((Every subset: (Well-formed (Truth decision
(either True, or False)))) Negation-complete
).
((Well-formed result of purely formal operations)
Derivable).(((Well-formed result of finite
series of purely formal operations) Finite-derivable)
Provable).((Derivable Non-contradiction)
Consistent).((Consistent (adding of any other formula
inconsistent)) Maximally consistent).((Every subset: (Well-formed (Truth decision
(either True, or False)))) Negation-complete
).(3)
Semantical criteria, in relation to syntax:
Ie. projections from semantics to syntax.
A.o. completeness.
(3a) Syntactical - Adequacy.
Satisfiability guarantees Consistency.
((Every subset: (Satisfiable Consistent))
Adequate).
(3b) Syntactical - Completeness (proof potential, Vollständigkeit): Truth/ validity
guarantees Derivability.
((Every subset: (True/ valid Derivable))
Complete).
Satisfiability guarantees Consistency.
((Every subset: (Satisfiable Consistent))
Adequate).((Every subset: (True/ valid Derivable))
Complete).(4)
Syntactical criteria, in relation to semantics:
Ie. projections from syntax to semantics.
A.o. consistency theorem, correctness, Decidability.
(4a) Fundamental theorem, consistency theorem: Consistency guarantees satisfiability.
((Every subset: (Consistent Satisfiable))
Fundamental theorem).
(4b) Logical correctness of formal systems ('soundness', in weak sense, deductive power):
Derivability guarantees Validity.
((Every subset: (Derivable True/ Valide))
Correct)).
(4c) Logical 'soundness' of formal systems (in strong sense): Derivability guarantees
Logical Consequence.
((Every subset: (Derivable
Logical consequent)) Sound).
(4d) Reductio ad absurdum: Logical validity guarantees Non-contradiction.
((Well-formedness (Opposite/Negation
(Some conjunct subset: (Contradiction derivable: inconsistent))))
True/ Valid).
(4e) Decidability (decision capacity) of formal systems: Syntactical well-formedness guarantees
validity decision.
(Well-formedness (Validity decision:
(either Valid, or Invalid))) Validity Decidable).
((Every subset: (Consistent Satisfiable))
Fundamental theorem).((Every subset: (Derivable True/ Valide))
Correct)).((Every subset: (Derivable
Logical consequent)) Sound).
In other words, from provability of contradiction derived from the opposite, follows logical validity.
Principle of proof by 'refutation of the opposite'.
Principle of proof by 'refutation of the opposite'.
((Well-formedness (Opposite/Negation
(Some conjunct subset: (Contradiction derivable: inconsistent))))
True/ Valid).(Well-formedness (Validity decision:
(either Valid, or Invalid))) Validity Decidable).
C.P. van der Velde © 2006, 2018.