Testwiki:Reference desk/Archives/Mathematics/2018 March 7

{| width = "100%"

|- ! colspan="3" align="center" | Mathematics desk |- ! width="20%" align="left" | < March 6 ! width="25%" align="center"|<< Feb | March | Apr >> ! width="20%" align="right" |Current desk > |}

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

March 7

Functional Completeness-Related Question

A is the set of formulae that are conjunction of the following clauses:

• clauses of the form $\mathrm{\neg }a$ or $\mathrm{\neg }a\vee \mathrm{\neg }b$
• clauses with the connector $\vee$ only (without $\mathrm{\neg }$)
• clauses with the connectors $\wedge ,\to$ (without $\mathrm{\neg }$), such that $\to$ appears in the clause exactly once

B is set of formulae defined just like A, but in the last kind of clauses they have also the connector $\vee$.

Is that true that $\mathrm{\forall }\psi \in B\mathrm{\exists }\phi \in A:\mathrm{\forall }x\in \{0,1{\}}^n(\mathrm{\exists }y\in \{0,1{\}}^m.\phi (x,y)\leftrightarrow \mathrm{\exists }z\in \{0,1{\}}^k.\psi (x,z))$?

I think I can solve this somehow with a technique similar to the one used for functional completeness proofs, but I can't figure out how exactly. עברית (talk) 19:53, 7 March 2018 (UTC)

Pretty sure I'm not understanding something, but it looks to me like A⊋B, so you could just take φ to be ψ. Maybe explain the context more? --RDBury (talk) 14:14, 8 March 2018 (UTC)

It's the opposite: B⊋A, since B has the extra connector. Is my question clear now? עברית (talk) 16:44, 8 March 2018 (UTC)

However, I found a better formulation of what I need:

We say that a formula $\phi \in C_{n,k}$ is 3-symmetric if $\mathrm{\forall }x\in \{0,1{\}}^n,y\in \{0,1{\}}^k,{\sigma }_1,{\sigma }_2,{\sigma }_3\in S_{k/3}:\phi (x,y)=\phi (x,{\sigma }_1(y_1),{\sigma }_2(y_2),{\sigma }_3(y_3))$ (where $S_n$ is the symmetric group)

$A_k$ is the set of k-variable formulae that are conjunction of expressions (or, clauses) that satisfy the following property: each expression uses the connectors $\wedge ,\to$ (but not $\mathrm{\neg },\vee$), such that $\to$ appears in the clause exactly once

$B_k$ is defined just like $A_k$, but in that case using the connector $\vee$ is also allowed.

$C_k$ is the set of k-variable formulae that satisfy the 3-symmetry.

Is the following statement true?

 $\mathrm{\forall }n,m\mathrm{\exists }d\mathrm{\exists }k\le (n+m{)}^d\mathrm{\forall }\phi \in C_{n,\max \{m,k\}}\mathrm{\forall }{\psi }_b\in B_m\mathrm{\exists }{\psi }_a\in A_k\mathrm{\forall }x\in \{0,1{\}}^n$
 $(\mathrm{\exists }y\in \{0,1{\}}^k.\phi (x,y)\wedge {\psi }_a(y)\leftrightarrow \mathrm{\exists }z\in \{0,1{\}}^m.\phi (x,z)\wedge {\psi }_b(z))$

Motivation: This is a definition of equivalence between two formulae (of course, it's different from the usual definition). I would like to define them as equal if either both have a "true" in their truth table or both don't have. But this definition is too weak, so I strengthened the definition: Even after "conjuncting" with any other formula, both have or both don't have a "true" in their truth tables. Finally, the question is whether the formulae in A are equivalent to the formulae in B. That is, whether adding the connector $\vee$ enlarges the group also under this definition of equivalence. עברית (talk) 18:39, 8 March 2018 (UTC)

I misinterpreted what you said before, but I'm still not entirely sure I understand the difference between A and B or what difference "conjuncting" with other expressions makes. In any case, maybe you should start with the simplest non-trivial case. I think here it would be m=3, n=0, φ(p, q, r) = p→(q∨r), ψ_b = True. What is the A-equivalent form of φ in this case? Once you have a few examples to go on, you will need to construct some kind of inductive argument, presumably based on the length of φ. This seems like a lot of work, but it would help to define A and B recursively as they do for formal languages. --RDBury (talk) 08:21, 9 March 2018 (UTC)

Could you clean up the statement you're asking about? You've clearly made mistakes in stating it. For example, phi has arity n, but you've fed it a tuple of length n + k + m.2601:245:C500:754:4831:C848:4E82:B552 (talk) 12:48, 9 March 2018 (UTC)

Thank you. I fixed this, and cleaned up my statement.

I thought about some solution: we can just copy all of the variables in the disjunction to separated clauses: for example ${\psi }_b=(a\wedge b)\to (c\vee (d\wedge e))$ goes to ${\psi }_a=[(a_1\wedge b_1)\to c]\wedge [(a_2\wedge b_2)\to (d\wedge e)]$.

However, in such a way the number of variables grows exponentially, so I added a new requirement that k is polynomial in n,m. עברית (talk) 07:06, 10 March 2018 (UTC)

Associated Legendre polynomials

I've done a few experiments with Mathematica, but have not found the general result.

Am I correct that the set $\frac{d}{dx}{P}_{\ell }^2(x),n\ge 2$ form an orthogonal set of polynomials under $\underset{-1}{\overset{1}{\int }}\frac{d}{dx}{P}_{\ell }^2(x)\frac{d}{dx}{P}_k^2(x)dx$? If so, what is the result for $\underset{-1}{\overset{1}{\int }}{(\frac{d}{dx}{P}_{\ell }^2(x))}^{2}dx$?--Leon (talk) 21:19, 7 March 2018 (UTC)

I get

$\begin{array}{cc}\underset{-1}{\overset{1}{\int }}(\frac{\partial }{\partial x}{P}_2^2(x))(\frac{\partial }{\partial x}{P}_4^2(x))\partial x& =\underset{-1}{\overset{1}{\int }}(\frac{\partial }{\partial x}(3(1-x^2)))\left(\frac{\partial }{\partial x}(\frac{15}{2}(7x^2-1)(1-x^2))\right)\partial x\\ & =\underset{-1}{\overset{1}{\int }}180(7x^4-4x^2)\partial x\\ & ={\left[180(7\frac{x^5}{5}-4\frac{x^3}{3})\right]}_{x=-1}^{x=1}\\ & =24\end{array}$

which is non-zero. The integral is zero if one of $k$ and $l$ is odd and one even, since the integrand is then odd in $x$. --catslash (talk) 12:38, 8 March 2018 (UTC)

I am not sure why you think that the first derivatives of associated Legendre polynomials form an orthogonal set? And what is n?Ruslik_Zero 20:25, 8 March 2018 (UTC)

n is the degree, as is clear from the condition that it be no less than the order - so $\frac{d}{dx}{P}_n^2(x),n\ge 2$ was intended. Orthogonality is not an entirely daft supposition, and could still be the case with the introduction of a suitable weight function. --catslash (talk) 13:15, 9 March 2018 (UTC)

My goals is a "complete" set of polynomials with the following properties.

1. $P_n(-1)=P_n(1)=0$.
2. $\underset{-1}{\overset{1}{\int }}{P}_n(x)P_m(x)dx=0$ if and only if $n\ne m$.
3. $\underset{-1}{\overset{1}{\int }}P{\text{'}}_n(x)P{\text{'}}_m(x)dx=0$ if and only if $n\ne m$.

When I says "complete", I mean being able to express all polynomials for which $P_n(-1)=P_n(1)=0$ is true, not all polynomials full stop.

I tried something with sines and cosines instead if polynomials, but whilst it "worked", it lacked other properties that I wanted.--Leon (talk) 13:33, 9 March 2018 (UTC)

You can read this or this. Ruslik_Zero 19:28, 9 March 2018 (UTC)