|
| |
|
|
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)
|
|
|
|
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
|
Table of n, a(n) for n=1..15.
Matthew Scroggs, Logic Bot, pt. 2
Matthew Scroggs, List of tautologies
|
|
|
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
|
Cf. A277275, A277276
Sequence in context: A073768 A278534 A096855 * A024538 A279879 A279139
Adjacent sequences: A256117 A256118 A256119 * A256121 A256122 A256123
|
|
|
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
|
| |
|
|
