A381325 -id:A381325 - cp's OEIS frontend

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

3, 17, 177, 3029, 76713, 2677637, 122836857

Offset: 1

Adam Wang, Feb 20 2025

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.

			a(1)=3, 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.

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

Cf. A000629, A381325.

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula