|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Об алгоритмической неразрешимости некоторых проблем распознавания для пропозициональных исчисленийстатья Научно-популярная статья
- Автор: Боков Г.В.
- Журнал: Интеллектуальные системы. Теория и приложения (ранее: Интеллектуальные системы по 2014, № 2, ISSN 2075-9460)
- Том: 18
- Номер: 4
- Год издания: 2014
- Издательство: [б.и.]
- Местоположение издательства: М.
- Первая страница: 207
- Последняя страница: 214
- Аннотация: В данной работе мы рассмотрим пропозициональные исчисления, формулы которых образованы логическими связками, содержащими классическую импликацию, а правилами вывода выступают операции modus ponens и подстановка. Известно, что в общем случае проблема распознавания выразимости одних исчислений через другие алгоритмически неразрешима. В данной работе будут рассмотрены частные случаи этой проблемы: распознавание аксиоматизации, распознавание расширения и распознавание полноты. В частности будет показано, что проблема распознавания расширения алгоритмически неразрешима для любого исчисления, а проблемы распознавания аксиоматизации и полноты алгоритмически неразрешимы для любого исчисления, из которого выводима формула x -> ( y -> x ).
- Добавил в систему: Боков Григорий Владимирович