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

Найдено 5 определений
Показать: [все] [проще] [сложнее]

Автор: [российский] Время: [советское] [современное]

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

Источник: Философия науки. Краткий энциклопедический словарь. 2008 г.

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

Источник: Философский энциклопедический словарь

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

Источник: Философская Энциклопедия. В 5-х т.

разрешения проблема
РАЗРЕШЕНИЯ ПРОБЛЕМА — задача поиска алгоритма, решающего массовую проблему, состоящую из однотипных вопросов о конструктивных объектах (словах над фиксированным конечным алфавитом), ответы на которые даются с помощью некоторого алгоритма; этот алгоритм является решением данной Р. п. и называется для данной проблемы разрешающим алгоритмом, или алгоритмом, решающим данную проблему. Примеры: построение таблицы истинности для пропозициональной формулы и проверка главного столбца на отсутствие значения «ложь» есть алгоритм, решающий Р. п. классической логики высказываний; множество простых натуральных чисел (числа записываются, напр., в десятичной системе счисления; число называется простым, если это натуральное число, больше или равное 2, имеющее только два натуральных делителя — самое себя и 1) и соответствующая проблема выяснения простоты натурального числа разрешима с помощью алгоритма перебора возможных делителей. Близкой является проблема разрешимости, отличающаяся от Р. п. тем, что требуется лишь обосновать существование алгоритма, решающего данную проблему. В большинстве случаев положительное решение проблемы разрешимости достигается предъявлением соответствующего алгоритма, т.е. на самом деле решается и Р. п., а отрицательное решение (обоснование отсутствия требуемого алгоритма) является таковым для обоих видов проблем. Бывают случаи, когда проблема разрешимости положительно решена для некоторой задачи, в то время как соответствующая Р. п. остается открытой.         Первый пример отрицательного решения Р. п. был получен в 1936 г. А. Черчем: логика предикатов первого порядка неразрешима, т.е. не существует алгоритма, который по произвольной формуле логики предикатов давал бы ответ, является ли эта формула тождественно истинной (общезначимой). С тех пор задача выяснения, является ли теория разрешимой, стала стандартным вопросом для всякой вновь формулируемой теории. Очень многие естественные теории оказались неразрешимыми, например аксиоматическая арифметика, элементарная теория групп. С другой стороны, имеются многочисленные весьма содержательные теории, которые разрешимы. Таковы, напр., арифметика Пресбургера (арифметика без умножения), теория действительных чисел и элементарная геометрия.         В последние десятилетия в связи с приложениями к проблемам, имеющим практическое значение, к Р. п. относят и вопросы оптимизации найденных алгоритмов, т.е. требуется не только предоставить разрешающий алгоритм, но и обосновать, что этот алгоритм имеет наименьшую возможную сложность вычисления в том или ином смысле (по затратам времени, памяти и т.п.). С точки зрения этой подпроблемы Р. п. многие теории (или множества конструктивных объектов), для которых Р. п. были положительно решены, оказались практически неразрешимыми или, по крайней мере, найденные алгоритмы не годятся для практического применения. Хрестоматийными примерами являются проблемы выяснения тождественной истинности и выполнимости формул логики высказываний: алгоритм, состоящий в построении таблицы истинности для проверяемой формулы, принципиально дает решение обеих проблем, однако он практически не применим, поскольку требует для своей реализации экспоненциально растущих затрат времени в зависимости от числа переменных в проверяемых формулах.         А.В. Чагров         Лит.: Черч А. Введение в математическую логику. М., I960; Ершов ЮЛ. Проблемы разрешимости и конструктивные модели. М., 1980; Справочная книга по математической логике. Ч. III. Теория рекурсии. М., 1982; Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. М., 1983.

Источник: Энциклопедия эпистемологии и философии науки

РАЗРЕШЕНИЯ ПРОБЛЕМА
возникла в связи с осознанием невозможности провести некоторые построения дозволенными методами. Первыми примерами неразрешимых задач явились решение в радикалах уравнений выше четвертой степени и невозможность провести некоторые построения циркулем и линейкой.
Общая формулировка проблемы разрешения следующая: дан класс методов Ф, дан класс проблем Р. Можно ли найти единый метод/ Ф (разрешающий метод), позволяющий решить каждую из проблем Р, для которой в принципе существует решение?
Часто в текстах по логике и математике рассматривается более частная формулировка проблемы разрешения, называемая алгоритмической разрешимостью, в которой разрешающий метод должен быть алгоритмом, т. е. класс методов Ф фиксируется и считается множеством алгоритмов. Исторически алгоритмическая неразрешимость была первым явно выделенным случаем общей проблемы разрешения. В последнее время в связи с осознанием разницы между теоретической и практической вычислимостью появилась третья формулировка, когда разрешающий метод — не просто алгоритм, а алгоритм ограниченной сложности. Напр., линейная разрешимость — разрешимость программой, вычислимая за линейное время относительно длины исходных данных, NP-полная проблема — проблема, разрешимая лишь программой полного перебора.
Примерами в разной степени неразрешимых проблем являются: построение модели любой непротиворечивой классической теории — неразрешима однозначно определенными (без аксиомы выбора) теоретико-множественными функционалами; проверка истинности формул арифметики либо (соответствия) программ их спецификации — неразрешима средствами формальных теорий с алгоритмически заданным множеством аксиом; проверка доказуемости в формальной арифметике или в классической логике предикатов — алгоритмически неразрешима; задача нормализации выводов в логике предикатов — неразрешима примитивно-рекурсивными алгоритмами; задача перестройки естественного вывода в резолюционный — неразрешима алгоритмами, делающими не более шагов, где и — длина вывода, k — любое фиксированное число; проверка тавтологичности формул классической логики высказываний — переборно разрешима, но неразрешима менее чем переборными алгоритмами.
Заметим, что неразрешимость проблемы означает лишь отсутствие единого метода, хотя в каждом конкретном случае ее можно пытаться решать, если решение не претендует на слишком большую общность. В последнее время выявилось общее свойство частных решений неразрешимых проблем: по мере расширения класса решаемых задач сложность методов с некоторого момента быстро растет, а эффективность столь же быстро убывает.
Точно так же результат о достаточно простой разрешимости проблемы может оказаться дезориентирующим, если эта достаточная простота достигается лишь на очень больших объектах, а для малых все равно приходится практически действовать перебором. Примером здесь может служить классическая задача о раскраске карт четырьмя цветами. Сведение к неразрешимым проблемам стало столь же мощным методом установления некорректности задач либо решений, каким является в физике сведение к возможности построить вечный двигатель. Напр., того, кто написал программу, ищущую зацикливание в других программах, не будут слушать, если он сам не предоставит примеры, когда его программа не работает либо работает неправильно, Неразрешимость проблемы разложения числа на простые множители достаточно простым алгоритмом стала основой современной теории надежных индивидуальных шифров. Одним из методов решения неразрешимых проблем является переход к вероятностным алгоритмам разрешения и к квантовым вычислениям. Показано, что для многих переборных задач есть быстрые алгоритмы, решающие их со сколь угодно близкой к 1 заранее заданной вероятностью.
Н. Н. Непейвода

Источник: Новая философская энциклопедия

Найдено научных статей по теме — 15

Читать PDF
117.61 кб

ГУАМ и проблемы разрешения конфликтов в Грузии

Закареишвили Паата
На саммите, состоявшемся 22 апреля 2005 года в Кишиневе, ГУУАМ (Грузия, Украина, Узбекистан, Азербайджан, Молдова) наконец-то (на восьмом году со дня ее создания) перешагнула свой Рубикон и заявила о своих политических амбициях.
Читать PDF
129.43 кб

Роль логики в разрешении проблемы употреблений языка

Конверский Анатолий Евгеньевич
Развитие логики предполагает включение в ее предметное поле новых логических норм, а также использование современного логического инструментария для освещения традиционных проблем логики.
Читать PDF
289.55 кб

Научный подход к разрешению ключевых проблем г. Якутска

Корнилова З. А.
Читать PDF
1.16 мб

Проблемы социального посредничества в разрешении конфликта

Килясханов Хизри Шапиевич, Попова Татьяна Владимировна, Курносенко Андрей Анатольевич
В статье, предлагаемой вниманию читателей, авторами отмечается, что конфликтность переходит в дальнейшие процессы, отражая изменения собственной интенсивности, адресности и сущности аксиологических установок.
Читать PDF
393.08 кб

Проблемы поставок вооружений в страны СНГ и пути их разрешения

Смолин Артем Вадимович
В сфере поставок вооружения в страны СНГ со стороны России (учитывая безусловное лидерство последней в вопросах поставок вооружения) имеется ряд проблем как со стороны внутренних противоречий стран СНГ, так и со стороны геополитич
Читать PDF
306.49 кб

Основные экологические проблемы российских городов и стратегия их разрешения

Ляховенко Олег Игоревич, Чулков Дмитрий Игоревич
В статье рассматриваются основные экологические проблемы городов, а также факторы, оказывающие негативное воздействие на природную среду.
Читать PDF
139.52 кб

Водно-энергетические проблемы Центральной Азии и возможные пути их разрешения

Гусев Леонид Юрьевич
В статье говорится о современном состоянии водных проблем Центральной Азии. Отмечается, что проблемы в этой сфере берут свое начало еще в 30-х гг. ХХ в.
Читать PDF
1.35 мб

Медиация как альтернативный способ разрешения споров - проблемы и перспективы

Вагапова Л.Х.
В статье рассмотрены основные проблемы развития института медиации: низкая осведомленность граждан о данной процедуре, недоверие медиаторам, скептическое отношение к ним, низкая компетентность медиатора.
Читать PDF
16.31 мб

Методологический подход как современный вариант разрешения проблемы сложности

Розин В.М.
В статье методология анализируется еще с одной точки зрения, а именно как один из современных способов, позволяющих преодолевать сложность изучаемых явлений.
Читать PDF
738.45 кб

Роль конструктивного диалога культур в разрешении проблем глобализирующегося мира

Толок Екатерина Сергеевна
Статья посвящена анализу роли конструктивного диалога культур в разрешении проблем глобализирующегося мира.
Читать PDF
194.58 кб

Основные тенденции в разрешении проблемы военно-профессионального самоопределения

Асриев А. Ю.
Читать PDF
296.68 кб

Проблемы развития конфликтогенных ситуаций в Центральной Азии и процесс их разрешения

Курбонова Зульфия Махманабиевна
В данной статье содержится анализ потенциальных конфликтов в Центральной Азии, на основе которого предлагается стратегия миростроительства в регионе.
Читать PDF
6.27 мб

Актуальные проблемы профессионального воспитания сотрудников УИС и пути их разрешения

Н. Б. Лелик
Читать PDF
628.80 кб

Проблемы природообустройства при реновации угольных шахт Донбасса и пути их разрешения

Джерелей Дарья Александровна
Целью исследования является обоснование выбора оптимальных путей природообустройства при закрытии шахт Донецкого угольного бассейна.
Читать PDF
374.55 кб

Осознание противоречий в самоотношении как путь разрешения проблем в подростковом возрасте

Ундуск Елена Николаевна

Похожие термины:

  • Разрешимости (разрешения) проблема

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

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