Аннотация:
С помощью сетей доказательств исследуется алгоритмическая сложность проблемы выводимости в некоторых фрагментах исчисления Ламбека. Доказана NP-полнота этой задачи для одностороннего фрагмента и для фрагмента без умножения, а также для вариантов этих фрагментов, допускающих пустые антецеденты.
Библиография: 12 наименований.
Ключевые слова:исчисление Ламбека, алгоритмическая сложность, сети доказательств.
Полный текст:
PDF файл (591 kB)
