A381325 Number of false implications over all possible pairs of unique logical sentences of n quantified variables in prenex normal form with a fixed proposition.

1, 19, 499, 19471, 1094011, 85044319, 8823674539

Offset

1,2

Comments

The total number of unique logical sentences of n quantified variables in prenex normal form (PNF) with a fixed proposition is given by A000629. Essentially, a logical sentence is in PNF iff it is a string of quantifiers followed by a proposition.

Note that for an arbitrary proposition, the only two possible implications are: firstly, "for all x_1" -> "exists x_1", and, secondly, "exists x_1 forall x_2" -> "forall x_2 exists x_1". The sequence is formed by counting all the number of implications between all valid PNFs for a fixed proposition.

For example, a(1)=1, because "forall x P(x)" and "exists x P(x)" both imply themselves, and the former implies the latter. However, the latter does not imply the former.

Links

Table of n, a(n) for n=1..7.

Adam Wang, Determining Implication of Fixed Matrix Prenex Normal Forms Can Be Decided in Linear Time, arXiv:2504.15294 [cs.DS], 2025.

Wikipedia, Prenex Normal Form

Formula

a(n) = A000629(n)^2 - A381324(n).

Crossrefs

Cf. A000629, A381324.

Sequence in context: A348321 A284220 A201711 * A243784 A158583 A009081

Adjacent sequences: A381322 A381323 A381324 * A381326 A381327 A381328

Keyword

nonn,more

Author

Adam Wang, Feb 20 2025

Status

approved