Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 24
Текст из файла (страница 24)
Лукасевич, обе последние формулы могут быть заменены одной формулой 1 3), что и приводит нас к системе 1 1) — 1 3). Наша система формул 1 — У устроена таким образом, что если исключить из нее формулу Ч 3), т. е. формулу 1 "1А — ь А, то выводимыми окажутся лишь такие импликативные формулы, которые являются позитивно тождественными '). Далев, наша система формул обладает тем свойством, что каждая ив ее формул независима от всех остальных, т.е.
из всех остальных не выводится. Однако даже небольшие изменения этой системы могут способствовать возникновению различных зависимостей. Например, если мы заменим третью из формул для конъюнкции 11 3) следующей, более простой формулой: А — ~- (В ->. (А А В)), то формула 1 1) окажется выводимой нз формул 1 2), 3) и формул для конъюнкции з).
Если вместо формулы 'Ч 2): А -+ 1 1А взять формулу (А — ~ 1А)-э )А, то формула 1 2) окажется выводимой из формул 1 1), 3) и формул для отрицания. Вообще, в направлении уменьшения числа формул наша система может быть усовершенствована самыми различными способа- ') Сяотоыз наших формул 1, П равнозначна система, которую А. Гойтяпг приводит з качестве общей дяя кмплккзцяк я дяя кояъюпкцяя в ого формаякззцяя пятуяцяопксгской логики (Н о у 11 о 3 А.
)>1о (оппз1зп Вояе1п дог пкп!1!ошзмвсЬоп Ьох)Ь.— БпюшхвЬог. ргопз. Айза. %1зз., Мз1Ь.-РЬув. К1аззе, 1930. 2) Для дязъюякцяя Гойткпг тоже берет формулы П1. з) Напротив, если мы вместо формулы П 3) возьмем формулу (А — ~- В) -~- (А — ь А % В), посредством которой формула П 3) может быть заменена з сяогеме формул 1 я П, то иккакях новых зависимостей ко возникнет. Что касается вопроса о возможности 'замены форнупьг П1 3) формулой (А -ьВ) -~-(А УВ-ъВ), то такая возможность существует я системе формул 1, 1П, Ч, а значит, я подавно во всей системе 1 — Ч; если же ыы опустим формулу Ч 3), то зта возможность ясчозпот.
ми. Так, например, вместо системы, состоящей из наших шести формул 1 и Ч, достаточно взять систему из трех формул: (А ->. В) -+- ((В -ь С) ->- (А ->- С)), (А -ь ( 1А — ~- В)), (~А — >- А) — А, а таньке систему А — +- ( — >- А), (А — ь (В ->- С)) -~ ((А — >. В) — ь (А — >- С)), ( 1А -ь. 1В) — ь ( — >- А).
Обе эти системы были предложены Лукасевичем, причем им было установлено, что обв опн достаточны для того, чтобы можно было вывести все тождественно истинные выран<ения, построенные с помощью нмпликацин и отрицания. Следует также отметить, что формулы Ч 1), 2), 3) фигурируют в уже упоминавшейся системе Фреге в качестве исходных формул рассмотренного нм дедуктивного исчисления в>доказываний '). 3 4.
Доказательства независимости, проводимые методом оценок 1. Логическая интерпретация как оценка; общий метод. Доказательства рааличных сформулированных здесь утзернвдений о выводимости тех или иных формул мы можем опустить, так как в дальнейшем мы не будем пользоваться дедуктивной структурой логики высказываний. Однако мы приведем здесь докавательство того, что каждая из формул 1 — У невависил>а от всех остальных.
С этой целью мы разберем некоторый общий метод, который будет применяться в этом доказательстве. К этому методу нас приводит рассмотрение того отношения, в котором находятся друг к другу дедуктивная логика высказываний и теория истинностных функций. Если мы будем трактовать связки -ь, А, 'Ч',, 1 как истинностные функции, то для системы дедуктивной логики высказываний в том виде, как она охарактеризована формулами 1 — У, мы тем самым получим определенного рода интерпретацию. При рассмотрении этой интерпретации мы можем отвлечься от той в собственном смысле слова логической точки зрения, ') Сы.
сноску яз с. 95. Впрочем, з системе Фрого формула (А -ь ( — ь С)) -~ (В -ь (А — ь С))1 является язляшэой. Это может быть легко установлено о помощью упоыяяутых систем Лукзсовяча, ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИИ ГРЛ. »ы $ «3 метод ОненОИ и докАзАтельстВА незАВисимости «о5 в результате которой формулы логики высказываний приобретают характер правил умозаключений. Здесь будет не важно, что значениями истинностных функций и их аргументов являются именно «нстина» и «ложь». Важно будет лишь то, что мы будем иметь дело с вполне определенными функциями, которые, как и их аргументы, способны принимать лишь одни и те же два аначения— например а и р. Определение этих функций дается нашими прежними таблицами, в которых мы заменим «истину» посредством а, а «ложь» — посредством р.
Мы можем также дать эти определения в виде некоторых равенств, а именно: определение функции-+. с помощью равенств будет иметь вид а-».и =и, р- () =с, а=и, а -э. Р = р; определение функции ~ с помощью равенств будет иметь вид: 1а = р, 1р = а; определения А. н ~/ с помощью равенств будет иметь вид: а Ь и = а ~( и =- а, (1 А р = р ~/ р = р, и й (1 = () бс и = р, и ~/ () = р ~/ а = и; определение с помощью равенств будет иметь вид: а а=р р=а, а р=р а=р. В соответствии со сказанным, тождественная истинность какого- либо выражения означает, что на основании приведенных определений его значение будет тождественно равно а.
А рассуждение, которое убеждает нас в том, что система формул 1 — У доставляет одни лишь тождественно истинные формулы, в яовой абстрактной системе обозначений выглядит следующим образом. Сначала мы убеждаемся, что выражения 1 — У в силу определения -~ и других логических знаков тождественно принимают значение и. Затем остается лишь показать, что применение правил вывода к формулам, тождественно принимающим значение а, снова приводит только к таким формулам, которые обладают этим свойством. Для правила подстановки этот факт является непосредственно очевидным, так как в результате подстановки запас значений какого-либо выражеяия увеличиться не может. Что же касается схемы заключения, то мы теперь должнь1 показать, что если вырая1епия Я и Я вЂ” » 'лз тождественно принимают значение а, то ю также тождественно принимает это же самое значение.
В самом деле, если Я в качестве значения принимает и, то Я «- д) принимает то же самое значение, что и а-» лз; но согласно определению функции -~-, выражение и -+- ш всегда принимает то же самое значение, что и я). Таким образом, поскольку Я -+- В принимает в качестве значения и, это же самое значение принимает такя<е и 5. Из приведенного рассуждения, в частности, получается, что из формул 1 — У никогда не могут быть одновременно выведены два вырая<ения Я и ~Я, второе из которых является отрицанием первого. В самом деле, если Я тождественно принимает значение а, то ~Я будет тождественно принимать значение ~а = р. Требующаяся при таком подходе проверка того, что выражения 1 — У тождественно принимают значение а, на первый взгляд кажется утомительной.
Однако соответствующим разбором случаев она может быть сделана более короткой и обозримой. Продемонстрируем это на примере формулы 1 3): (А -~ В) -» ((В -+ С) — з-(А -з- С)). Пусть уже установлено, что вырая«ения А -+ (В -э. А) и А -+- А тождественно принимают значение и. Тогда далее можно рассудить следующим образом.
Среди значений, которые будут подставлены вместо А, В и С, по крайней мере два долясны будут совпасть. Если совпадут значения В и С, то А -» С примет то я<е самое значение, что и А -« В,и тогда значение рассматриваемого нами выражения 1 3) окажется одним из значений выражения А — » (В .э-А), т. е. а.
Если же совпадут значения А и С, то А -~ С примет значение а, и так как а-+. а = р — а = и (а потому и всякое выражение вида Я вЂ” » а в качестве значения примет и), то получится, что (А -+- В) -~. ((В -». С) -+ (А -э С)) = (А -»- В) -э (( — ~- С) -+.и) = (А -э В) — ~ а =- а. Наконец, если совпадут значения А н В, то совпадут также и значения  — ~- С и А -~ С. Значит, ( — С) -«- (А — С) примет в качестве значения и, а отсюда следует, что (А -~. В) -«- (( †» С) -+.(А — ~ С)) = (А †» В) — ~ а = а. ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИИ $41 метод Оценок и докАЕАтельстВА незАВисимОсти 197 [гл.
Ит 2. Доказательетво независимости рассматриваемой системы исходиых формул; еще одно доказательство независимости. Изложенный способ доказательства мы теперь обобщим таким образом, чтобы его можно было испольэовать для проведения доказательств независимости. Обобщение это будет заключаться в том, что вместо определений для — б~ Ч 'позаимствованных нами из таблиц, задающих соответствующие истинностные функции, мы рассмотрим некоторые другие определения, беря за основу ту или иную конечную область значений.
Из атой области значений мы выделим определенную подобласть— подобласть так называемых в ы д е л е н н ы х з н а ч е н и й— В отведем ей ту роль, которую в рассмотренном выше случае играло а. Такого рода определение символов-+-,8~, ~/,, ~ как функций в соответствующей конечной области, в сочетании с указанием выделенных значений, мы будем для краткости называть о ц е нк о й. Ту оценку, которая соответствует заданию истипностных функций, мы будем называть н о р м а л ь н о й о ц е н к о й.
Чтобы показать, что данная формула 0 не может быть выведена из формул Я» Яы будет достаточно указать оценку со следующими свойствами. Выражения ЯО, ЯА принимают одни только выделенные значения. Коли, далее, выражения 1Е и Я -+. Й принимают только выделенные значения, то тем же свойством обладает и ь. Выражение Я, напротив, принимает также и невыделенные значения. Ксли эти условия окажутся выполненными, то тем самым фактически будет установлена невыводимость 0; действительно, перечисленные вьппе свойства оценки гарантируют нам, что, исходя иэ формул Я„..., ЯА, принимающих одни только выделенные значения, и применяя правило подстановки и схему заключения, мы снова будем получать лишь формулы с выделенными значениями и, следовательно, никогда не сможем получить формулу П.
Теперь, пользуясь этим методом, мы для каждой из формул 1 — Ч докажем ее невыводимость иэ остальных формул системы. Для формул из групп 11 — У с этой целью можно будет воспользоваться такими оценками, которые отличаются от нормальной только в определении логического символа, вводимого рассматриваемой группой формул. Поэтому для формул 11 — 17 доказательства независимости мы можем свести в одну таблицу, в которой для каждой формулы 5, входящей в одну из упомянутых групп, мы приведем определение для вводимого этой группой симВола, задающее ту отличающуюся от нормальной оценку, при помощи которой доказывается независимость формулы Я.
от остальных формул 1 — У. Это определение всякий раз можно будет выразить посредством одного-единственного определяющего Равенства, которое должно выполняться при любом распределении значений а и р длн фигурирующих в этом равенстве переменных. Независимость этой формулы Я будет вытекать из того, что при сопоставленной этой формуле оценке формула 5 для определенного набора значений переменных (который также указывается в таблице) примет значение р, в то время как любая другая из формул 1 — 17 при этой оценке будет принимать апачение а. Проверку этого обстоятельства нужно проводить лишь для формул той группы, к которой принадлежит сама 5, так как отличие оценки„сопоставленной формуле 7, от нормальной проявляется лишь в отношении этих формул.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
