Система Фреге - Frege system
В сложность доказательства, а Система Фреге это пропозициональная система доказательства чьи доказательства представляют собой последовательности формулы полученный с использованием конечного набора звук и имплицитно полный правила вывода. Системы Фреге (более известные как Системы Гильберта в целом теория доказательств ) названы в честь Готлоб Фреге.
Формальное определение
Позволять K быть конечным функционально полный набор булевых связок и рассмотрим пропозициональные формулы построен из переменных п0, п1, п2, ... с помощью K-коннективы. Правило Фреге - это правило вывода вида
куда B1, ..., Bп, B формулы. Если р конечный набор правил Фреге, то F = (K,р) определяет систему вывода следующим образом. Если Икс - набор формул, а А формула, то F-производство А из аксиом Икс это последовательность формул А1, ..., Ам такой, что Ам = А, и каждый Аk является членом Икс, или он получен из некоторых формул Ая, я < k, путем подстановки правила из р. An F-доказательство формулы А является F-производство А из пустого набора аксиом (X = ∅). F называется системой Фреге, если
- F звук: каждый F-доказуемая формула - тавтология.
- F имплицитно полная: для каждой формулы А и набор формул Икс, если Икс влечет за собой А, то есть F-производство А из Икс.
Длина (количество строк) в доказательстве А1, ..., Ам является м. Размер доказательства - общее количество символов.
Система деривации F как указано выше, является опровергающим, если для любого несовместимого набора формул Икс, существует F-выведение фиксированного противоречия из Икс.
Примеры
- Исчисление высказываний Фреге это система Фреге.
- Есть много примеров здравых правил Фреге на Исчисление высказываний страница.
- Разрешение не является системой Фреге, потому что она работает только с предложениями, а не с формулами, построенными произвольным образом с помощью функционально полного набора связок. Более того, он не является имплицитно полным, т.е. мы не можем заключить из . Однако добавление ослабление правило: делает его имплицитно полным. Решение также опровергнуто.
Характеристики
- Теорема Рекхоу (1979) утверждает, что все системы Фреге p-эквивалент.
- Естественный вычет и последовательное исчисление (Система Генцена с разрезом) также p-эквивалентны системам Фреге.
- Имеются полиномиальные доказательства Фреге принцип голубятни (Buss 1987).
- Системы Фреге считаются достаточно сильными системами. В отличие, скажем, от разрешения, в доказательствах Фреге нет известных суперлинейных нижних оценок числа строк, а наиболее известные нижние оценки размера доказательств являются квадратичными.
- Минимальное количество раундов в испытатель-противник игра нужна для доказательства тавтологии пропорциональна логарифму минимального числа шагов в доказательстве Фреге .
Доказательство сильных сторон различных систем.
Расширенная система Фреге
Важное расширение системы Фреге, так называемое Расширенный Фреге, определяется с помощью системы Фреге F и добавление дополнительного правила вывода, которое позволяет вывести формулу , куда сокращает свое определение на языке конкретного F и атом не встречается в ранее выведенных формулах, включая аксиомы, и в формуле .
Цель нового правила вывода - ввести «имена» или ярлыки для произвольных формул. Это позволяет интерпретировать доказательства в расширенном Фреге как доказательства Фреге, работающие с схемы вместо формул.
Переписка повара позволяет интерпретировать Расширенный Фреге как неоднородный эквивалент теории Кука PV и теории Бусса. формализация допустимых (полиномиальных) рассуждений.
Рекомендации
- Крайичек, Ян (1995). «Ограниченная арифметика, логика высказываний и теория сложности», Cambridge University Press.
- Повар, Стивен; Рекхоу, Роберт А. (1979). «Относительная эффективность пропозициональных систем доказательства». Журнал символической логики. 44 (1): 36–50. Дои:10.2307/2273702. JSTOR 2273702.
- Басс, С. Р. (1987). «Доказательства полиномиального размера принципа пропозициональной ячейки», Journal of Symbolic Logic 52, стр. 916–927.
- Пудлак П., Бусс С. Р. (1995). «Как солгать, не будучи (легко) осужденным, и длина доказательств в исчислении высказываний», в: Computer Science Logic'94 (Pacholski and Tiuryn eds.), Springer LNCS 933, 1995, стр. 151–162.