login
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
OFFSET
1,5
COMMENTS
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.
LINKS
EXAMPLE
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).
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Matthew Scroggs, Mar 15 2015
EXTENSIONS
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
STATUS
approved