Система Фреге - 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.