The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A256120 Number of tautologies in propositional calculus of length n. 2
0, 0, 0, 0, 2, 2, 12, 6, 57, 88, 373, 554, 2198, 5413, 20397 (list; graph; refs; listen; history; text; internal format)



a(n) is the number of tautologies that are n symbols long in propositional calculus with the connectives not (~), and (*), or (+), implies (->) and if and only if (<->).

When measuring the length of a tautology, all brackets must be included. The connectives -> and <-> are counted as one symbol each (but writing them as such requires non-ASCII characters).

Formally, the language used for this sequence contains the symbols a-z and A-Z (the variables),~,*,+,->,<->,( and ).

The formulas are defined by the following rules:

* Every variable is a formula.

* If A is a formula, then ~A is a formula.

* If A and B are formulas, then (A*B), (A+B), (A->B) and (A<->B) are all formulas.

A formula is a tautology if it is true for any assignment of truth values to the variables.


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

Matthew Scroggs, Logic Bot, pt. 2

Matthew Scroggs, List of tautologies


The tautologies of length 5 are (a->a) and (a<->a).

The tautologies of length 6 are (~a+a) and (a+~a).

The tautologies of length 7 are (~~a->a), (~~a<->a), (~a->~a), (~a<->~a), (a->~~a), (a<->~~a), ~(~a<->a), ~(~a*a), ~(a<->~a), ~(a*~a), ~~(a->a) and ~~(a<->a).


Cf. A277275, A277276

Sequence in context: A073768 A278534 A096855 * A024538 A279879 A279139

Adjacent sequences:  A256117 A256118 A256119 * A256121 A256122 A256123




Matthew Scroggs, Mar 15 2015


More terms from Matthew Scroggs, Mar 27 2015

Typo in a(11) corrected by Matthew Scroggs, Mar 27 2015

a(13) corrected, and a(14)-a(15) added by Matthew Scroggs, Jul 02 2020



Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 3 14:58 EST 2021. Contains 341762 sequences. (Running on oeis4.)