RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. LOMI, 1971 Volume 20, Pages 170–174 (Mi znsl2406)

On biconjunctive reduction classes

V. P. Orevkov


Abstract: A predicate formula is biconjunctive if it is of the form
$$ P\biggl(\bigvee_{i=1}^l\&_{j=1}^{\delta_i}F_{ij}\biggr) $$
where $P$ is prefix, $\delta_i\leq2$ and $F_{ij}$ are atomic formulas possibly with negation. There are described 4 classes of biconjunctive formulas each having both undecidable problem of derivability in classical predicate calculus and undecidable problem of finite refutability.



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025