  Computability logic is a formal theory of computational tasks and resources.
Its formulas represent interactive computational problems, logical operators
stand for operations on computational problems, and validity of a formula is
understood as being a scheme of problems that always have algorithmic
solutions. A comprehensive online source on the subject is available at
http://www.cis.upenn.edu/~giorgi/cl.html . The earlier article "Propositional
computability logic I" proved soundness and completeness for the (in a sense)
minimal nontrivial fragment CL1 of computability logic. The present paper
extends that result to the significantly more expressive propositional system
CL2. What makes CL2 more expressive than CL1 is the presence of two sorts of
atoms in its language: elementary atoms, representing elementary computational
problems (i.e. predicates), and general atoms, representing arbitrary
computational problems. CL2 conservatively extends CL1, with the latter being
nothing but the general-atom-free fragment of the former.
