Аннотация:
Находится граница для длины конъюнкции некоторых пропозициональных формул, для которой каждая невыполнимая формула содержит невыполнимую подформулу. В частности, этот метод применим для формул в конъюнктивной нормальной форме с ограничениями на число истинных литералов в составе каждой элементарной дизъюнкции, а также для 2-КНФ, для симметричных 3-КНФ, для конъюнкций функций голосования от трёх литералов. При доказательстве используется нижняя оценка ранга некоторых матриц.
Полный текст:
PDF файл (167 kB)