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

Author

Adam Wang, Feb 20 2025

Keywords

• nonn
• more

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.

Examples

			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.
		

Links

• 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

Crossrefs

Cf. A000629, A381325.

Formula

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