Re: [math-fun] Parenthesizing
If the arrows are taken as implication, as in the predicate calculus, then Jim's question seems to make good sense to me. (But the question can of course be asked in general with other meanings assigned to the arrows.) —Dan -----
Do all the Catalan-many parenthesizations of p_1 --> p_2 --> ... --> p_n yield distinct Boolean functions?
That doesn't quite parse. ... -----
I assumed the intended interpretation of (a --> b) was ((!a) or b). Tom Dan Asimov writes:
If the arrows are taken as implication, as in the predicate calculus, then Jim's question seems to make good sense to me.
(But the question can of course be asked in general with other meanings assigned to the arrows.)
—Dan
-----
Do all the Catalan-many parenthesizations of p_1 --> p_2 --> ... --> p_n yield distinct Boolean functions?
That doesn't quite parse. ... -----
Yes, ((!p) or q) is what I meant by p --> q. Jim On Fri, Dec 1, 2017 at 7:45 PM, Tom Karzes <karzes@sonic.net> wrote:
I assumed the intended interpretation of (a --> b) was ((!a) or b).
Tom
Dan Asimov writes:
If the arrows are taken as implication, as in the predicate calculus, then Jim's question seems to make good sense to me.
(But the question can of course be asked in general with other meanings assigned to the arrows.)
—Dan
-----
Do all the Catalan-many parenthesizations of p_1 --> p_2 --> ... --> p_n yield distinct Boolean functions?
That doesn't quite parse. ... -----
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I am up early, a little restless and sleep-deranged. I find myself musing about methodical ways to organize parenthesizations, motivated by the need problems like this pose to iterate through them efficiently and elegantly. Suppose we have an ordered sequence of n+1 terms, a_0 ... a_n. We want to apply a binary function to some adjacent pair of terms, replacing that pair with the function value, obtaining a shortened sequence of n terms. Then we want to do the same thing to the shortened sequence, and repeat until there is just a single term left; that is, we will pick an adjacent pair and apply the function n times. The first time, we are picking from among n positions; the second time, from (n-1), and so on. The Catalan numbers are not the factorials, so we are counting some equivalent application-sequences more than once. Let's insist that, to achieve a given application-sequence, we always insist on combining the leftmost "available" pair earliest. That is, although the application-sequence represented by "(ab)(cd)" can be achieved by picking pairs in the order 3, 1, 1 or 1, 2, 1, we will consider the second order to be the canonical one. A canonical application-sequence must not display any drops of more than 1, I think, and my feeling is that this is the only constraint. So for four terms, the allowable sequences are (1, 1, 1), (1, 2, 1), (2, 1, 1), (2, 2, 1), (3, 2, 1). For five terms, the permissible ones are 1111, 1121, 1211, 1221, 1321, 2111, 2121, 2211, 2221, 2321, 3211, 3221, 3321, 4321, which gives the desired count of 14. The constraint is similar enough to other characterizations of the Catalan numbers that I hold myself convinced. If we reverse the order of these index-sequences, we arrive at the following characterization: C_n is the number of n-tuples of positive integers, starting with 1, with no increases of more than 1. If I were just a little more diligent I would write the approximately ten-line Haskell program to look for different application-sequences of the boolean implication-function to sequences of N boolean arguments with identical truth-tables. (My intuition is that there aren't any; that these are all distinct.) On Fri, Dec 1, 2017 at 10:51 PM, James Propp <jamespropp@gmail.com> wrote:
Yes, ((!p) or q) is what I meant by p --> q.
Jim
On Fri, Dec 1, 2017 at 7:45 PM, Tom Karzes <karzes@sonic.net> wrote:
I assumed the intended interpretation of (a --> b) was ((!a) or b).
Tom
Dan Asimov writes:
If the arrows are taken as implication, as in the predicate calculus, then Jim's question seems to make good sense to me.
(But the question can of course be asked in general with other meanings assigned to the arrows.)
—Dan
-----
Do all the Catalan-many parenthesizations of p_1 --> p_2 --> ... --> p_n yield distinct Boolean functions?
That doesn't quite parse. ... -----
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I think so too. I checked up to 12 variables and found no duplicates. Tom Allan Wechsler writes:
If I were just a little more diligent I would write the approximately ten-line Haskell program to look for different application-sequences of the boolean implication-function to sequences of N boolean arguments with identical truth-tables. (My intuition is that there aren't any; that these are all distinct.)
THERE we go. I knew somebody more energetic than me would step up. Thank you, Tom. On Sat, Dec 2, 2017 at 7:52 AM, Tom Karzes <karzes@sonic.net> wrote:
I think so too. I checked up to 12 variables and found no duplicates.
Tom
Allan Wechsler writes:
If I were just a little more diligent I would write the approximately ten-line Haskell program to look for different application-sequences of the boolean implication-function to sequences of N boolean arguments with identical truth-tables. (My intuition is that there aren't any; that these are all distinct.)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Different patterns of parentheses must give different functions; the parentheses can be unambiguously derived from the truth table. Let B be the boolean function. First note that p_n=T must always give B(p_1...)=True, so fix p_n = F. Now p_{n-1} must be either the head or the tail of an implication, so we have either .... -> p_{n-1} ) -> F or ...-> (p_{n-1} -> F) We are in the second case if and only if p_{n-1}=F always yields B(p_1...)=T, in which case we fix p_{n-1}=T and proceed recursively. Otherwise the possibilities are ... -> p_{n-2} ) -> p_{n-1} ) ->F or ... -> (p_{n-2} -> p_{n-1}) -> F We are in the second case if and only if (p_{n-2} -> p_{n-1})=F always yields B(p_1...)=T, and we can keep going in this way to get the entire parenthesization. On Sat, Dec 2, 2017 at 10:20 AM, Allan Wechsler <acwacw@gmail.com> wrote:
THERE we go. I knew somebody more energetic than me would step up. Thank you, Tom.
On Sat, Dec 2, 2017 at 7:52 AM, Tom Karzes <karzes@sonic.net> wrote:
I think so too. I checked up to 12 variables and found no duplicates.
Tom
Allan Wechsler writes:
If I were just a little more diligent I would write the approximately ten-line Haskell program to look for different application-sequences of the boolean implication-function to sequences of N boolean arguments with identical truth-tables. (My intuition is that there aren't any; that these are all distinct.)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
PHEW. I am relieved. On Sat, Dec 2, 2017 at 1:16 PM, Michael Collins <mjcollins10@gmail.com> wrote:
Different patterns of parentheses must give different functions; the parentheses can be unambiguously derived from the truth table. Let B be the boolean function. First note that p_n=T must always give B(p_1...)=True, so fix p_n = F. Now p_{n-1} must be either the head or the tail of an implication, so we have either
.... -> p_{n-1} ) -> F or ...-> (p_{n-1} -> F)
We are in the second case if and only if p_{n-1}=F always yields B(p_1...)=T, in which case we fix p_{n-1}=T and proceed recursively.
Otherwise the possibilities are
... -> p_{n-2} ) -> p_{n-1} ) ->F or ... -> (p_{n-2} -> p_{n-1}) -> F
We are in the second case if and only if (p_{n-2} -> p_{n-1})=F always yields B(p_1...)=T, and we can keep going in this way to get the entire parenthesization.
On Sat, Dec 2, 2017 at 10:20 AM, Allan Wechsler <acwacw@gmail.com> wrote:
THERE we go. I knew somebody more energetic than me would step up. Thank you, Tom.
On Sat, Dec 2, 2017 at 7:52 AM, Tom Karzes <karzes@sonic.net> wrote:
I think so too. I checked up to 12 variables and found no duplicates.
Tom
Allan Wechsler writes:
If I were just a little more diligent I would write the approximately ten-line Haskell program to look for different application-sequences of the boolean implication-function to sequences of N boolean arguments with identical truth-tables. (My intuition is that there aren't any; that these are all distinct.)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (5)
-
Allan Wechsler -
Dan Asimov -
James Propp -
Michael Collins -
Tom Karzes