Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 22
Текст из файла (страница 22)
Кроме того, может быть повторена формула, полученная ранее. Вслед за двумя формулами П и О-ь В в качестве формулы может быть написано й), т. е. может быть применена схема заключения Оба элементарных акта формального вывода — подстановка и схема заключения — которые вводятся здесь нами впервые, представляют собой формальные аналоги простейших содержательных умозаключений — заключения от общего к частному (г)(с$пш «)е ошп>) и заключения от причины к следствию (шог)пэ ропепз гипотетического заключения).
В рамках теории истинпостных функций этим двум способам умозаключения соответствуют два правила, которые, как и ранее упоминавшиеся правила замены, констатируют некоторые элементарные по своему характеру математические факты. Эти правила гласят." 1. Если в какое-либо тождественно истинное выражение вместо одной или нескольких входящих в него переменных — всюду, где они встречаются,— подставить произвольные (построенные из переменных с помощью знаков б«, ')(', ),-ь и ) выражения, то полученное выражение снова будет тождественно истинным.
2. Если Я и Я -ь ) — тождественно истинные выражения, то 3 также является таковым. Первое правило усматривается из тех соображений, что подстановка не увеличивает совокупности значений какого-либо выражения. Второе правило получается ив того, что при тождественно истинном Я импликация Я -+ Й всегда принимает то же самое значение, что и В. й 3. Дедуктивная логика высказываний 1. Постановка задачи. Принятое соглашение наводит нас на мысль о том, нельзя ли все тождественно истинные выражения получить из небольшого их числа на основе двух этих правил, т. е.
применением подстановки и схемы заключения; иначе говоря, мы интересуемся вопросом о том, нельзя ли систему тождественно истинных выражений построить дедуктивно. То, что вообще можно обойтись конечным числом выражений, Взятых в качестве исходных формул, совсем не самоочевидно уя«е потому, что при неограниченном числе перемзнпых число тождественно истинных выражений также оказывается бесконечным. Однако в действительности конечного числа исходных формул все же хватает для вывода всей совокупности тождественно истинных выражений ').
Можно 1) Длл выражений, построенных только с помощью иыпликацли и отрицаяия (есе лствввествые функции среди них, конечно, уже содержатся), полную систему исходных формул впервые построил Фреге в своей книге Ведг1ПэсЬпй, е1ае бег ап>Ь>еепэсЬел пэсйаеЬ~1йе!е Реппе!эргэсЬе без гешеп Певйеаэ.— На11е, !879. Зта системе, состоящая яз следующих шести формул: А -~ (В -~. А), (А -~ (В -~ С)) -~- ( — » (А -~- С)), (А'-ь (В -~- С)) -~ ((А -~ В) -~.(А -» С)), (А -1- В) -«. ( ЧВ -» "1 А], А -~ 1")А, ~ )А-«.А, долгое время оставалась иеззиечеллей. В те же самое время широкую извествесть получила система «примитивных высказыэзвив», предлежеияая Уэйтхедом и Расселом е Рпос1р!а ша1Ьеп>а1!са, ч. 1.— ! е иэд.— Сэшйг!»)ле, !9!О.
При нашем способе записи эти зыснззыэалия имеют эид А ч'А-ьА, А--В ~/А, А >УВ-»В ЧА, (В -»- С) -» (А >У В вЂ” А ЧС). Система егэ, правда, ле елелие согласуется с рассмэтрвээемым здесь подходом, поскольку имллилацвя э яей яе фигурирует среди еелеэлых связок, э определяется через дизъюикцвю и егрицаиве, что с фермзльяей точки зрелия равнесвльие применению вашего правила замены 4а). Кояъюилция я зкзивэлевтлесть е «Рг!лс1р!э шз!Ьешэнсэ» вводятся таким же обрезом, с помощью определений, которые формально равносильны нашим правилам замены 26) в 4б).
Каждое такое епределевие мажет быть представлено двумя зсходаыии формулами, и полная система исходных формул для всего нашего исчисления высказываний получается, если к уцеыялутым четырем формулам добавить еще следующие шесть: ( )А ~/В)-ь(А -«В), (А -ьВ)-ь( )А ~/В), ( 1.4 >у )В) -ь 1 (Аг& В). ~(А & В) -~ ()А Ч 1В), ((А -«- В) & (В -э. А)) -~. (А В), (А В) -».
((А -э- В) & (В -ь А]). дидуктивная лоГикА ВыскАзыВАпин 1ГЛ 111 исч!1слзник Выскат>ыВАний даже, как показал А. Тарский, обойтись одной-единственной исход- ной формулой '). Теперь, по совершенной апалогни с дедуктивным построением элементарной геометрии, перед нами возникает задача выбора по возможности более простой и естественной системы исходных формул такой. чтобы максимально отчетливо была видна та роль, которая в процессе логического вывода отводится каждому из рас- сматриваемых способов сочетания предложений.
При этом импли- кация занимает особое положение, поскольку, н пример, упо- минание о пей содержится уже В схеме заключения. 2. Одна система исходных формул для дедуктивной логики высказываний; полнота этой системы. Ниже приводится система исходных формул, выбранная нами с учетом сформулированных требований. По аналогии с тем, как это сделаяо в «Основаниях геометрии» Гильберта, исходные формулы разбиты в ней па от- дельные группы. К Формулы для импликации: 4) А — >- ( — р А), 2) (А -ь (А ->- В)) -в. (А — >- В), 3) (А ->- В) -+ (( — С) -в- (А -в С)). .П. Формулы для конъюнкции: 1) Ас>>В-ьА, ') Этот результат (етяесящяйся к 1925 г.) изложен в работе: Л е с и е вс к в й (Ьезп!емвй! Б.).
С>пас)зйяе е!пев пепел Эувсешв бег Сгппсйалеп бег Магйещаг!Ь.— рпт>с)атаев!а Магй., 1929, 1>>. Взяв в качестве основной связки символ 1Пеффера А ( В (сА и В исключают друг друга>), Нико (в работе: )Ч (сей 1. А гейпс11еп !и 1Ье пптпЬег о! 1Ье рг!ш!!!че ргереюцепз е1!ел!с.— Ргес.
СашЬг. РМ1. Вес.. 1917, 19), впервые привел прямер елкой-елппствепяей исходной Формулы, которой достаточно длл того, чтобы с пемещые правила подстановки я слеяутещей схемы заключенна: 2( й((6! =) Ю ,получить все построенные с помощью штриха Шеффера тежлестчеяпе истинпые вмражевпя. Правда, применяемая здесь схема заключеппя ><вляетсп более спльпым средством, чем обычная схема 6 (>( >е Ф так как епа позволяет за одлп прием исключить два зырапсепнл сразу. Я. Лукасевлч и Себочпвсппй предтежнлн целый ряд формул таких, чте кажяеп пз плк хватает в качестве елвястнеппей псхелпей формулы (ппн прнмененпп еГ>мчней схемы заллючеппя) для спстемы выра>левай. построенных с помп>пью пмплпкапвн и етрнцаяпя. См, обзорный цонлат Лт>спсевпча я Тата >сего: Ь >т 1с а в ! е к ! с в 1., Т а т е 1с ! А. 1)п!етютсЬпп:еп 6Ьег с)еп Апазаяеп1са!291.— С.В.
Эес, Эс!. (>агчет!е 22, К)авве Ш, )кагасьнп, 1920. 2) А с>сВ-+.В, 3) (А — В) — ~ ((А — С) — (А -э В бс С)). П1. Формулы для дизъюнкции: 1)А-в.А т/В, 2)  — «А ~/В, 3) (А -ь С) -~ ((В -в- С) ь (А )/ В -ь С)). 1Ч. Формулы для эквивалентности: 1) (А В) -ь (А -в. В), 2) (А — В) — ( — ь А), 3) (А — ь В) -~ ((В -+- А) -ь (А В)). 'Ч.
Формулы для отрицания: 1) (А -~ В) — >- ( 1В -ь 1А ), 2) А — >. 11А, 3) 1 )А -~ А. Как легко показать, все формулы этой системы являются тож- дественно истипнымн выражениями, и потому из них могут быть выведены только тождественно истинные выражения. Но с дру- гой стороны, эта система является еще и полкой — в том смысле, что любое (построенное нз переменных с помощью символов &, ~/, 7, -+., -) тождественно истинное выражение может быть выве- дено из формул 1 — Ч при помощи сформулированных выше двух правил. Кратко наметим докааательство этого утверждения.
Во-перва>к, мы показываем, что ив нашей системы может быть выведена любая тонсдественно истинная конъюнктивная нормальная форма. Затею устанавливаем, что если выражение Я заменимо — в соответ- ствии с каким-либо направил замены 1 — 4 (быть может, в сочетании с правилом З2) — выражением м), то из формул нашей системы может быть выведена формула Я ->- 1. После этого наше утверждение может быть лолучепо следующим обрааом.
Пусть Я вЂ” тождественно истинное выражение. Как было показано ранее, Я в соответствии с правилами замены может быть преобразовано в некоторую копъюнктивную нормальную форму щ. Это преобразование может быть произведено в виде ряда замен, причем сначала будет заменено Я посредством Я„ затем Я, — посредством Я,...
и, наконец, ߄— посредством )1(. Каждая из втих замен производится в соответствии с правила- ми 1 — 4 и 32, и всякий раз заменимость является двусторонней. Просматривая этот ряд замен в обратном направлении, мы в соот- ветствии с ранее доказанным убенсдаемся, что из нашей системы выводимы импликации щ- Яь, Яь- Яь с, ...,Яз-+-Ят, Яс-ьр(. Далее, йт выводимо, так как оно представляет собой конъюнктив- пую нормальную форму, тождественно истинную по той причине, Д. Гнльверт, П, Бернайс ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ 1гл. нг 5 31 дедуктивнхя логикА ВыскАзыВАнии 99 что она представляет ту же самую истинностную функцию, что и выражение Я, которое предполагается тождественно истинным.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
