I tried to post the following as a question (with previous edits) on the logic section of Mathoverflow. They've put it on hold as unclear as to what I'm asking. Is Mathoverflow even open to such a question, which has stood as open for a long time, getting asked in the first place?
Title:
What is the Shortest Axiom of Classical Conditional-Negation Propositional Calculus?
Suppose that we only have propositional variables and connectives. Suppose our rules of inference are detachment {Cα β , α } ⊢ β ,
and uniform substitution. Suppose that we have a binary connective "C"
and a unary connective "N". In 1953 C. A. Meredith found what is
currently the shortest single axiom of classical C-N
(Conditional-Negation) propositional calculus [p. 302 of A. N. Prior's
Formal Logic indicates this and references Prior's paper " 'Single
Axioms for the Systems (C, N), (C, O), and (A, N) of the Two-valued
Propositional Calculus' JCS, vol. i, No. 3 (July 1953), pp. 155-64.
Systems 1.5, 3.13, 6.13, 6.14.):
CCCCCpqCNrNsrtCCtpCsp.
Or using another prefix notation
→→→→→pq→¬r¬srt→→tp→sp.
So given the first notation, the formation rules are:
The longest subformula which ends with the first "t" is thus CCCCpqCNrNsrt. The longest subformula which ends with the second "p" is thus "Ctp", and "s" is the longest subformula corresponding to the third "0" spot. Thus, the main breaks of the formula can get located by the following "|" marks.
Furthermore, the main breaks of CCCCpqCNrNsrt is given by C|CCCpqCNrNsr|t, and so on.
Suppose we have a 2-valued model of C and N given by the following table:
If there exists a unique shortest axiom up to re-symbolization of variables and connectives, what is the shortest axiom which allows us to deduce a known axiom system for classical propositional calculus, such as the following axiom set?
The length of an axiom is defined by the number of symbols it has when fully expressed as a well-formed formula.
Title:
What is the Shortest Axiom of Classical Conditional-Negation Propositional Calculus?
Suppose that we only have propositional variables and connectives. Suppose our rules of inference are detachment {C
CCCCCpqCNrNsrtCCtpCsp.
Or using another prefix notation
→→→→→pq→¬r¬srt→→tp→sp.
So given the first notation, the formation rules are:
- All lower case letters of the Latin alphabet, as well as any lower case letters of the Latin alphabet sub-scripted by Hindu-Arabic numerals are formulas.
- If x is a formula, then so is Nx.
- If x and y are formulas, then so is Cxy.
- Nothing else is a formula in this context.
- Assign -1 to all lower case letters, as well as all lower case letters which are sub-scripted.
- Assign 0 to N.
- Assign 1 to C.
- Sum the assigned numbers as you precede from left to right throughout any given string.
- A string will qualify as a formula if and only if it either starts and ends with -1, or if it starts with a member of {0, 1} and -1 is only reached at the spot corresponding to the last letter of the string, and that string ends with -1.
C C C C C p q C N r N s r t C C t p C s p
| | | | | | | | | | | | | | | | | | | | |
1 2 3 4 5 4 3 4 4 3 3 2 1 0 1 2 1 0 1 0 -1
The longest subformula which ends with the first "t" is thus CCCCpqCNrNsrt. The longest subformula which ends with the second "p" is thus "Ctp", and "s" is the longest subformula corresponding to the third "0" spot. Thus, the main breaks of the formula can get located by the following "|" marks.
C|CCCCpqCNrNsrt|C|Ctp|C|s|p.
Furthermore, the main breaks of CCCCpqCNrNsrt is given by C|CCCpqCNrNsr|t, and so on.
Suppose we have a 2-valued model of C and N given by the following table:
C 0 1 N
0 1 1 1
1 0 1 0
Does there exist any shorter single axiom, which under the rules
above allows us to deduce all tautologies, and only those tautologies in
the 2-valued model? Does there exist another single axiom of the same
length?If there exists a unique shortest axiom up to re-symbolization of variables and connectives, what is the shortest axiom which allows us to deduce a known axiom system for classical propositional calculus, such as the following axiom set?
- CpCqp. [p
→ (q→ p)]. - CCpCqrCCpqCpr. [(p
→ (q→ r))→ ((p→ q)→ (p→ r))]. - CCNpNqCqp. [(
¬ p→ ¬ q)→ (q→ p)].
The length of an axiom is defined by the number of symbols it has when fully expressed as a well-formed formula.
No comments:
Post a Comment