login
Number of tautologies and contradictions in propositional calculus of length n.
2

%I #11 Oct 10 2016 07:50:13

%S 0,0,0,0,2,8,14,26,63,215,527

%N Number of tautologies and contradictions in propositional calculus of length n.

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

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

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

%C The formulas are defined by the following rules:

%C - every variable is a formula;

%C - if A is a formula, then ~A is a formula;

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

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

%C A formula is a contradiction if it is false for any assignment of truth values to the variables.

%C This sequence is increasing, as adding a ~ to the start of a tautology or contradiction gives a contradiction or tautology one symbol longer.

%H M. Scroggs, <a href="http://mscroggs.co.uk/blog/35">Logical Contradictions</a>

%H M. Scroggs, <a href="http://www.mscroggs.co.uk/blog/tautologies.txt">List of tautologies</a>

%H M. Scroggs, <a href="http://www.mscroggs.co.uk/blog/contradictions.txt">List of contradictions</a>

%e The contradictions of length 6 are ~(a<->a), ~(a->a), (~a*a), (~a<->a), (a*~a) and (a<->~a): 6 formulas, and the tautologies of length 6 are (~a+a) and (a+~a): 2 formulas. So a(6) = 6+2 = 8.

%Y Equals A256120 plus A277275

%K nonn,more

%O 1,5

%A _Matthew Scroggs_, Oct 08 2016