Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
Топ:
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Техника безопасности при работе на пароконвектомате: К обслуживанию пароконвектомата допускаются лица, прошедшие технический минимум по эксплуатации оборудования...
Оценка эффективности инструментов коммуникационной политики: Внешние коммуникации - обмен информацией между организацией и её внешней средой...
Интересное:
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Дисциплины:
2017-11-17 | 465 |
5.00
из
|
Заказать работу |
|
|
Проблема разрешимости — вопрос, сформулированный в рамках какой-либо формальной системы, требующий ответа «да» или «нет», возможно, зависящего от значений некоторых входных параметров.
Например, проблема «дано два числа x и y, делится ли x на у?» является проблемой разрешимости. Ответ может быть дан либо «да» либо «нет» и зависит от значений xи y. Метод решения проблемы разрешимости, представленный в форме алгоритма, называется разрешающей процедурой для этой проблемы. Так, разрешающая процедура для проблемы разрешимости «дано два числа x и y, делится ли нацело x на у?» должна определять совокупность действий, которые следует предпринять для проверки делимости нацело x на у для данных x и y. Один из таких алгоритмов деление столбиком изучается в начальной школе. Остаток равный нулю означает ответ «да», иначе «нет». Проблема разрешимости, для которой существует разрешающая процедура, называется разрешимой.
Исследования в области теории рекурсии часто сфокусированы на проблемах разрешимости, поскольку к ним без потери общности сводятся многие задачи.
разрешения проблема (разрешимости проблема) - проблема
нахождения для данной дедуктивной теории общего метода, позволяющего решать, может ли отдельное утверждение, сформулированное в терминах теории, быть доказано в ней или нет. Этот общий метод, являющийся эффективной процедурой (алгоритмом), называется процедурой разрешения или разрешающей процедурой, а теория, для которой такая процедура существует, - разрешимой теорией.
Р. п. решается в классической логике высказываний с помощью таблиц истинности. Разрешающий алгоритм существует и для логики одноместных предикатов, для силлогизма категорического и других простых дедуктивных теорий. Но уже для логики предикатов общего решения Р. п. не существует. В математике также невозможно установить общий метод, который дал бы возможность провести различие между утверждениями, которые могут быть доказаны в ней, и теми, которые в ней недоказуемы.
|
Невозможность найти для теории общий разрешающий метод не исключает поиска процедуры разрешения для отдельных классов ее
утверждений.
СОКРАЩЕННЫЙ СПОСОБ РЕШЕНИЯ ПРОБЛЕМЫ РАЗРЕШИМОСТИ.
Все формулы алгебры логики делятся на три класса:
1)тождественно истинные,
2)тождественно ложные
3)выполнимые.
Формулу А называют тождественно истинной, если она при всех значениях входящих в неё переменных высказываний принимает значение 1(истина). Формулу А называют тождественно ложной, если она при всех значениях входящих в неё переменных принимает значение 0(ложь).Формулу A называют выполнимой, если она принимает значение 1(истина), хотя бы на одном наборе входящих в нее переменных и не является тождественно истинной.
Вопрос к какому классу формул относится текущая формула A и называется проблемой разрешимости. Эта проблема решается элементарно с помощью таблицы истинности, однако для больших формул таблицы очень громоздки и их использование затруднительно.
Эта задача носит название проблемы разрешимости. Очевидно, что проблема разрешимости алгебры логики разрешима, т.к. для каждой формулы алгебры логики может быть записана таблица истинности, которая и даст ответ на поставленный вопрос.
Однако практическое использование таблицы истинности для формулы при больших n затруднительно.
Существует другой способ, позволяющий, не используя таблицы истинности, определить, к какому классу относится формулаА. Этот способ основан на приведении формулы к нормальной форме (КНФ или ДНФ) и использовании алгоритма, который позволяет определить, является ли данная формула тождественно истинной или не является. Одновременно с этим решается вопрос о том, будет ли формула А выполнимой.
|
ОСНОВНЫЕ ЛОГИЧЕСКИЕ ВЫВОДЫ.
Правило вывода – это предписание, или разрешение позволяющее из суждения 1-ой логической структуры, как посылок, вывести суждения некоторой логической структуры, как заключения.
Особенности правил заключения в том, что признаки истинности заключения производятся на основе не содержания, а их структуры. Правила вывода записываются в виде схемы, которая состоит из 2-ух частей (сверху и снизу), разделённых вертикальной линией. Над чертой в столбец записываются логические схемы посылок, под чертой логические схемы заключения.
Все правила выводов логики высказываний делятся на 2-е группы:
Основные и Производные.
• Основные – это простые и очевидные правила, не нуждающееся в доказательстве. Основные делятся на прямые и косвенные.
• Прямые – это такие правила, которые указывают на непосредственно выводимость одних суждений из других.
• Косвенные – лишь дают возможность умозаключить о правомерности вывода одних суждений из других.
• Производные - сокращённый процесс вывода, выводятся из основных.
ВЫВОД ЛОГИЧЕСКИЙ – рассуждение, в котором осуществляется переход по правилам от высказывания или системы высказываний к высказыванию или системе высказываний. К логическому выводу обычно предъявляются (совместно или по отдельности) следующие требования: 1) правила перехода должны воспроизводить отношение следования логического (ту или иную его разновидность); 2) переходы в логическом выводе должны осуществляться на основе учета только синтаксических характеристик высказываний или систем высказываний.
В современной логике понятие логического вывода определяется для формальных систем, в которых высказывания представлены формулами. Обычно выделяют три основных типа формальных систем: аксиоматические исчисления, исчисления натурального вывода, исчисления секвенций. Стандартное определение логического вывода (из множества формул Г) для аксиоматического исчисления S таково: логический вывод в S из множества формул Г есть такая последовательность Α1... Аn формул языка исчисления S, что для каждой Ai (1 ≤i ≤n) выполняется, по крайней мере, одно из следующих трех условий: 1) Ai есть формула из Г; 2) Ai есть аксиома исчисления S; 3) Ai есть формула, получающаяся из предшествующей ей в последовательности А1...Аn формулы или из предшествующих ей в этой последовательности формул по одному из правил вывода исчисления S. Если α есть логический вывод в S из множества формул Г, то формулы из Г называются посылками a, a сам вывод α называется выводом в S из посылок Г; если при этом А есть последняя формула α, то α называется логическим выводом в S формулы А из посылок Г.Запись «Г ⊦sA» означает, что существует логический вывод в S формулы А из посылок Г. Логический вывод в S из пустого множества формул называется доказательством в S. Запись «⊦sA» означает, что существует доказательство в S формулы А. Формула А называется доказуемой в S,если⊦A. В качестве примера рассмотрим аксиоматическое исчисление S1 со стандартным определением вывода, являющееся вариантом классической логики высказываний. Алфавит этого исчисления содержит только пропозициональные переменные р1, р2,..., рn,..., логические связки ⊃, ⌉ и круглые скобки.
|
|
|
Таксономические единицы (категории) растений: Каждая система классификации состоит из определённых соподчиненных друг другу...
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!