РАЗРЕШЕНИЯ ПРОБЛЕМА

РАЗРЕШЕНИЯ ПРОБЛЕМА, или: Разрешимости пробле­ма,  — проблема нахождения для данной дедуктивной теории общего метода, позволяющего решать, может ли отдельное утверждение, сфор­мулированное в терминах теории, быть доказано в ней или нет. Этот общий метод, являющийся эффективной процедурой (алгоритмом), называется процедурой разрешения или разрешающей процедурой, а теория, для которой такая процедура существует, — разрешимой теорией. Р. п. решается в классической логике высказываний с помощью таблиц истинности. Разрешающий алгоритм существует и для логи­ки одноместных предикатов, для силлогизма категорического и дру­гих простых дедуктивных теорий. Но уже для логики предикатов общего решения Р. п. не существует. В математике также невозможно установить общий метод, который дал бы возможность провести различие между утверждениями, которые могут быть доказаны в ней, и теми, которые в ней недоказуемы. Невозможность найти для теории общий разрешающий метод не исключает поиска процедуры разрешения для отдельных классов ее утверждений.


Смотреть больше слов в «Словаре по логике»

РАЗРЕШИМАЯ ТЕОРИЯ →← РАЗРЕШАЮЩАЯ ПРОЦЕДУРА

Смотреть что такое РАЗРЕШЕНИЯ ПРОБЛЕМА в других словарях:

РАЗРЕШЕНИЯ ПРОБЛЕМА

        важное понятие логики. Р. п. данного множества А конструктивных объектов (См. Конструктивные объекты) (относительно некоторого объемлющего множ... смотреть

РАЗРЕШЕНИЯ ПРОБЛЕМА

РАЗРЕШЕНИЯ ПРОБЛЕМА, важное понятие логики. Р. п. данного множества А конструктивных объектов (относительно нек-рого объемлющего множества V конструк... смотреть

РАЗРЕШЕНИЯ ПРОБЛЕМА

РАЗРЕШЕНИЯ ПРОБЛЕМА     РАЗРЕШЕНИЯ ПРОБЛЕМА — возникла в связи с осознанием невозможности провести некоторые построения дозволенными методами. Первы... смотреть

РАЗРЕШЕНИЯ ПРОБЛЕМА

        РАЗРЕШЕНИЯ ПРОБЛЕМА — задача поиска алгоритма, решающего массовую проблему, состоящую из однотипных вопросов о конструктивных объектах (словах ... смотреть

РАЗРЕШЕНИЯ ПРОБЛЕМА

алгоритмическая проблема, в к-рой для заданного множества Атребуется построить алгоритм, разрешающий Аотносительно другого множества В, включающе... смотреть

РАЗРЕШЕНИЯ ПРОБЛЕМА

один из наиболее важных видов массовых проблем. Р. п. данного множества А конструктивных объектов (относительно нек-рого объемлющего множества V конструктивных объектов) наз. проблему построения алгоритма, распознающего по всякому объекту из множества V, принадлежит ли он множеству А или нет. Р. п. (более подробно – Р. п. для доказуемости) формальной системы (или исчисления) наз. Р. п. множества всех доказуемых формул этой системы относительно множества всех ее формул. Семантич. Р. п. (или Р. п. для истинности) интерпретированной формальной системы (формализованного языка) наз. Р. п. множества всех истинных формул системы относительно множества всех ее формул. (Для обозначения понятия "проблема разрешения" долгое время применялся термин "проблема разрешимости", однако этим термином правильнее обозначать проблему: "имеет ли решение данная Р. п.".) Р. п. множеств совпадают по существу и с проблемами распознавания свойств. Проблемой распознавания заданного св-ва (для объектов из заданной совокупности конструктивных объектов) наз. проблему построения алгоритма, распознающего по всякому объекту из заданной совокупности, обладает он заданным св-вом или нет. Всякая проблема распознавания св-ва есть в то же время Р. п. множества всех тех объектов, к-рые обладают этим св-вом. В свою очередь Р. п. множества есть проблема распознавания св-ва принадлежности к этому множеству. В частности, Р. п. для доказуемости является проблемой распознавания доказуемости, а Р. п. для истинности есть проблема распознавания истинности. См. также ст. Алгоритм, Массовая проблема, Метатеория и лит. при них. В. Успенский. Москва. ... смотреть

РАЗРЕШЕНИЯ ПРОБЛЕМА

или: Разрешимости пробленма, аЧ проблема нахождения для данной дедуктивной теории общего метода, позволяющего решать, может ли отдельное утверждение, сфорнмулированное в терминах теории, быть доказано в ней или нет. Этот общий метод, являющийся эффективной процедурой (алгоритмом), называется процедурой разрешения или разрешающей процедурой, а теория, для которой такая процедура существует, — разрешимой теорией. Р. п. решается в классической логике высказываний с помощью таблиц истинности. Разрешающий алгоритм существует и для логинки одноместных предикатов, для силлогизма категорического и друнгих простых дедуктивных теорий. Но уже для логики предикатов общего решения Р. п. не существует. В математике также невозможно установить общий метод, который дал бы возможность провести различие между утверждениями, которые могут быть доказаны в ней, и теми, которые в ней недоказуемы. Невозможность найти для теории общий разрешающий метод не исключает поиска процедуры разрешения для отдельных классов ее утверждений.<br>... смотреть

РАЗРЕШЕНИЯ ПРОБЛЕМА

одна из осн. проблем, встающих в связи с построением формализованных дедуктивных теорий. Ее положительное или отрицательное решение для каждой конкретной формальной теории связано соответственно с существованием или несуществованием нек-рого общего метода (или алгоритма), позволяющего конечным числом действий выяснить, является ли произвольная формула рассматриваемой теории доказуемой (истинной) в данной системе. Р. п. положительно решается, напр., в исчислении высказываний и в формализованной аристотелевской силлогистике. Однако уже для исчисления предикатов общего решения этой проблемы не существует. Невозможность найти для к.-л. формальной теории общий разрешающий метод не исключает поисков таких решений для отдельных классов формул этой теории. ... смотреть

РАЗРЕШЕНИЯ ПРОБЛЕМА (РАЗРЕШИМОСТИ ПРОБЛЕМА)

проблема нахождения для данной дедуктивной теории общего метода, позволяющего решать, может ли отдельное утверждение, сформулированное в терминах теор... смотреть

T: 276