Have there been results published that give an adequate set of n>2-ary
connectives that is capable of expressing all truth functions? I’m
looking for a general method of determing which sets of connectives are
adequate.
The only way I can think of for determining whether a set of n-ary
connectives is adequate is by writing out all the 2^{2^n} truth tables
of the nth order and then seeing if some adequate set of connectives
(e.g. {~, v}) can be defined in terms of some set of those truth
tables—that set will then be adequate (i.e. the connectives defined
in terms of those truth tables). But this method is obviously
impractical even for small n.
Thanks
Michael
"Michael De" <mike…@gmail.com> wrote in message
news:1136064626.626436.129270@f14g2000cwb.googlegroups.com…
> Have there been results published that give an adequate set of n>2-ary
> connectives that is capable of expressing all truth functions? I’m
> looking for a general method of determing which sets of connectives are
> adequate.
> The only way I can think of for determining whether a set of n-ary
> connectives is adequate is by writing out all the 2^{2^n} truth tables
> of the nth order and then seeing if some adequate set of connectives
> (e.g. {~, v}) can be defined in terms of some set of those truth
> tables—that set will then be adequate (i.e. the connectives defined
> in terms of those truth tables). But this method is obviously
> impractical even for small n.
Not sure if this helps.
There is a way to describe the truth tables of N valued logics.
Essentially, if you have adequate connectives for AND and OR,
you can describe any n-ary truth table in disjunctive normal form.
Since negation may not be uniquely defined in an n-ary logic,
I use a system where I assign each variable a logical value.
(This can be thought of as a set of N assignment connectives,
like the connective "always True").
Describing an n-ary logic truth table requires (n-1) expressions.
Example of a 3 valued logic AND connective:
0 = False
1 = True
2 = Don’t know
Truth table for (A AND B)
0 1 2 A
0 0 0 0
1 0 1 2
2 0 2 2
B
This truth table can be written using any two of these three expressions:
False = A0 OR B0
True = (A1 AND B1)
Don’t Know = (A1 AND B2) OR (A2 AND B1) OR (A2 OR B2)
Russell
– 2 many 2 count
- Hide quoted text — Show quoted text -
Russell Easterly wrote:
> "Michael De" <mike…@gmail.com> wrote in message
> news:1136064626.626436.129270@f14g2000cwb.googlegroups.com…
> > Have there been results published that give an adequate set of n>2-ary
> > connectives that is capable of expressing all truth functions? I’m
> > looking for a general method of determing which sets of connectives are
> > adequate.
> > The only way I can think of for determining whether a set of n-ary
> > connectives is adequate is by writing out all the 2^{2^n} truth tables
> > of the nth order and then seeing if some adequate set of connectives
> > (e.g. {~, v}) can be defined in terms of some set of those truth
> > tables—that set will then be adequate (i.e. the connectives defined
> > in terms of those truth tables). But this method is obviously
> > impractical even for small n.
> Not sure if this helps.
Not really but it is interesting–thank you. I had in mind an adequate
set of n>2-ary connectives for a 2-valued logic, but it would be nice
to have a more generalized method that applies to any n-valued logic
for finite n. I found in Church "Intro to Math. Logic" the adequate set
{[A,B,C], t, f} in which [A,B,C] is the ternary connective ‘conditioned
disjunction’. In case you’re interested, there is also:
* Alonzo Church, "Conditioned disjunction as a primitive connective for
the propositional calculus", Portugaliae Mathematica, Vol. 7 (1948),
pp. 87-90.
** Alan Rose, "Conditioned disjunction as a primitive connective for
the m-valued propositional calculus", Mathematische Annalen, Vol. 123
(1951), pp. 76-78
*** A. Rose, "Conditioned disjunction as a primitive connective for the
Erweiterter Aussagenkalkul", Journal of Symbolic Logic, Vol. 18, No.1
(1953), pp. 63-65
**** T. C. Wesselkamper, "A sole sufficient operator", Notre Dame
Journal of Formal Logic, Vol. 16, No. 1 (1975), pp. 86-89
These papers have shed a lot of light on the subject.
Michael
- Hide quoted text — Show quoted text -
> There is a way to describe the truth tables of N valued logics.
> Essentially, if you have adequate connectives for AND and OR,
> you can describe any n-ary truth table in disjunctive normal form.
> Since negation may not be uniquely defined in an n-ary logic,
> I use a system where I assign each variable a logical value.
> (This can be thought of as a set of N assignment connectives,
> like the connective "always True").
> Describing an n-ary logic truth table requires (n-1) expressions.
> Example of a 3 valued logic AND connective:
> 0 = False
> 1 = True
> 2 = Don’t know
> Truth table for (A AND B)
> 0 1 2 A
> 0 0 0 0
> 1 0 1 2
> 2 0 2 2
> B
> This truth table can be written using any two of these three expressions:
> False = A0 OR B0
> True = (A1 AND B1)
> Don’t Know = (A1 AND B2) OR (A2 AND B1) OR (A2 OR B2)
> Russell
> – 2 many 2 count
mitch wrote:
> not simple enough for a village idiot
> ————————————-
> The village idiot on sci.logic seems to have a problem
> with the fact that logic and mathematics is sometimes
> complicated.
How would you know that?
Where have I ever alleged that I have such a problem?
> Maybe the village idiot is right and I am wrong about
> everything I ever say concerning mathematics. That would
> be fine if I could get a decent discussion of the material.
> But, regardless of that state of affairs, there is one
> thing I know for certain:
> Only a village idiot could think
> mathematics ought to be inherently
> "simple"!
Here’s one thing I know for certain: I never said I thought
mathematics ought to be inherently simple, so you are welcome
to keep burning all of your own strawmen. Just don’t expect me
to meep when you accuse me of holding opinions I don’t hold.
As always, if you want to disagree with something *I* said, you have
to quote *ME* saying it. You DON’T get to just MAKE UP SHIT
and then call ME a village idiot for believing it, WHEN I NEVER SAID
I believed it.
- Hide quoted text — Show quoted text -
mitch wrote:
> Here is a discussion of simplicity by
> Gian-Carlo Rota:
> "There are other embarrassing counterexamples
> to our faith in simplicity. Perhaps the
> oldest and most dramatic is the fundamental
> theorem of geometry, going back to von Staudt
> in the early nineteenth century, stating
> the equivalence of synthetic and analytic
> projective geometry. No significant progress
> has been made in simplifying von Staudt’s
> proof. Even today, a full proof of von
> Staudt’s theorem takes no less than twenty
> pages, including a number of unspeakably
> dull lemmas.
This is NOT surprising to US.
WE KNOW how hard this stuff is, thanks to Cook and Turing.
Propositional satisfiability is NP-complete (for all practical
purposes exponential). First-order unsatisfiability is only SEMI-
decidable, i.e., there is NO LIMIT to how hard/long complicated
a first-order proof can get, at least not as a recursive function
of the combined lengths of the axioms and the conclusion.
Nothing in the standard classical first-order paradigm disputes the
difficulty of the proof of SOME theorems. So why are you attributing
hostility of that difficulty TO ME? COULD it just POSSIBLY be because
YOU ARE A TOTAL FUCKING ASSHOLE?
- Hide quoted text — Show quoted text -
mitch wrote:
> Here is a discussion of simplicity by
> Gian-Carlo Rota:
> "There are other embarrassing counterexamples
> to our faith in simplicity. Perhaps the
> oldest and most dramatic is the fundamental
> theorem of geometry, going back to von Staudt
> in the early nineteenth century, stating
> the equivalence of synthetic and analytic
> projective geometry. No significant progress
> has been made in simplifying von Staudt’s
> proof. Even today, a full proof of von
> Staudt’s theorem takes no less than twenty
> pages, including a number of unspeakably
> dull lemmas.
This begs the question of just how this ought to be formalized.
Practicing mathematicians are normally NOT logicians. The
people who care MOST about this are NOT going to be simultaneously
caring about how to prove theorems IN GENERAL. It almost seems
to me that this needs to be presented as a challenge problem to the
theorem-proving community. But that would take all the fun out of it
because it would require people first to pay some attention to how
to properly axiomatize the statement of the theorem at first-order.
THAT is something that you, mitch, epitomize the VERY OPPOSITE of.
REAL mathematicians are willing to do this in principle (they just
consider
it tedious and not normally worth bothering with), but you arrived here
in
high dudgeon alleging that that sort of preliminary hygiene was
fallacious,
was (gasp!) "logicism".
> Philosophers of mathematics
NOT the right class of people to be performing this
analysis, except to the extent that they are also logicians.
> have speculated that the difficulty in
> simplifying von Staudt’s proof may be due
> to the fact that the assertion is only
> valid in dimension 3 or greater, while in
> dimension 2 a plethora of awkward
> counterexamples has been found, the nasty
> non-Desarguian projective planes."
If these REALLY are "counterexamples" then they
would imply that the ORIGINAL proof WAS WRONG
and was therefore NOT a proof. How exactly does the
original proof formalize the fact that it only applies to three
or more dimensions? Is it really just in terms of a number of
dimensions n, with a simple n>2 as a hypothesis?
Again, these are questions that actual GEOMETERS could hardly
BRING themselves to CARE about. You would have to be a logician
to care.
But I’m not sure this is even a first-order proof anyway.
A lot of proofs of results over broad comprehensive categories
of things are not really first-orderizable; perhaps the classic
example is Cayley’s theorem (about permutations and groups).
You can prove this is as a theorem of set theory if you take a set-
theoretical approach to defining groups but everybody knows groups
are in fact broader than that. You just sort of can’t get a "big
enough"
universe. Much of mathematical proof in practice is NOT reduced to
first order, for reasons like that one. So if this proof also has that
property then it is not surprising that even people who specialize in
looking for better ways to prove things (With the help of computers)
are not making much headway.
Finally, since I was coming from a computer science perspective,
I would also like to point out that it goes without saying that the
kinds of proofs that WE find BEFORE the actual mathematicians
find them are PRECISELY the proofs that are long and complicated
and that no-one has yet figured out how to shorten; the first and
loudest
example would of course be the proof of the four-color map theorem,
something which ought to be near and dear to the heart of ANY geometer
and something that mitch COULD have, IF he were competent, highlighted
withOUT trying to impress everybody about how many more ancient
commentators he has read than the rest of us have.
Can you tell me where I can find a statement and proof of von Staudt’s
theorem and a discussion of the counterexamples in dimension two?