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

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an 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 $\neg a$ or $\neg a\vee \neg b$
• clauses with the connector $\vee$ only (without $\neg$)
• clauses with the connectors $\wedge ,\to$ (without $\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 $\forall \psi \in B\exists \varphi \in A:\forall x\in \{0,1\}^{n}(\exists y\in \{0,1\}^{m}.\varphi (x,y)\leftrightarrow \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 $\varphi \in C_{n,k}$ is 3-symmetric if $\forall x\in \{0,1\}^{n},y\in \{0,1\}^{k},\sigma _{1},\sigma _{2},\sigma _{3}\in S_{k/3}:\varphi (x,y)=\varphi (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 $\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?

 $\forall n,m\exists d\exists k\leq (n+m)^{d}\forall \varphi \in C_{n,\max\{m,k\}}\forall \psi _{b}\in B_{m}\exists \psi _{a}\in A_{k}\forall x\in \{0,1\}^{n}$
 $(\exists y\in \{0,1\}^{k}.\varphi (x,y)\wedge \psi _{a}(y)\leftrightarrow \exists z\in \{0,1\}^{m}.\varphi (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\geq 2$ form an orthogonal set of polynomials under $\int _{-1}^{1}{\frac {d}{dx}}P_{\ell }^{2}(x){\frac {d}{dx}}P_{k}^{2}(x)dx$? If so, what is the result for $\int _{-1}^{1}\left({\frac {d}{dx}}P_{\ell }^{2}(x)\right)^{2}dx$?--Leon (talk) 21:19, 7 March 2018 (UTC)

I get

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

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\geq 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. $\int _{-1}^{1}P_{n}(x)P_{m}(x)dx=0$ if and only if $n\neq m$.
3. $\int _{-1}^{1}P'_{n}(x)P'_{m}(x)dx=0$ if and only if $n\neq 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)