Два сообщения, читанные 27 февраля и 23 марта 1882г

Вид материала

Документы

Содержание A=B. Однако, применение общего метода не всегда удобно. Бывают случаи, когда требуется построить одну какую-либо A=B требуется построить тождественную с ним максимальную систему посылок в единичной форме M на продуценты двух классов b и d, получим след. систему 4-х равенств: 1=b+d+M(a,0,c,0)=b+d+ac M на продуценты классов b,c,d

Подобный материал:

• Россия, 191186 Санкт-Петербург, Невский пр., 30, оф., 63.98kb.
• Руководитель управления образования, 85.22kb.
• Курс с 6 февраля по 1 марта, 205.63kb.
• Вед. 1- сегодня 14 февраля, 124.74kb.
• Информационный бюллетень местного самоуправления Издается асдг по с окмо с февраля, 1928.61kb.
• Информационный бюллетень местного самоуправления Издается асдг по с окмо с февраля, 1285.61kb.
• Информационный бюллетень местного самоуправления Издается асдг по с окмо с февраля, 1763.83kb.
• Информационный бюллетень местного самоуправления Издается асдг по с окмо с февраля, 1671.53kb.
• Информационный бюллетень местного самоуправления Издается асдг по с окмо с февраля, 1139.9kb.
• Информационный бюллетень местного самоуправления Издается асдг по с окмо с февраля, 1335.2kb.

§ 8. Частный приём разложения равенств на посылки

В предыдущих §§ изложен общий метод получения всевозможных логических нулей данного равенства A=B. Однако, применение общего метода не всегда удобно. Бывают случаи, когда требуется построить одну какую-либо систему, отвечающую равенству A=B. В таком случае вычисление элементов и потом их комбинирование может оказаться слишком длинным путем к этой цели. В виду этого мы находим не лишним указать некоторые частные приемы для получения известного рода систем непосредственно из данного равенства A=B, минуя предварительное вычисление отвечающих ему элементов. А именно, мы укажем способ непосредственного получения некоторых их таких систем, в которых число посылок есть 2 в различных степенях, начиная от 1-ой до (n-1)-й включительно³⁷. Способ этот вполне аналогичен изложенному выше общему способу и основан на приведении функции N, служащей логическом нулем равенства A=B, к однородному виду 1-го, 2-го, 3-го,…., (n-1)-го измерений.

По аналогии с алгеброй, условимся называть всякую функцию n классов F(a,b,c,d….) 1) однородной относительно a, коль скоро она приведена к виду Pa+Qa₁, где P и Q суть функции прочих классов b,c,d…; 2) однородной относительно двух классов a и b, если она имеет вид: αab+βab₁+γa₁b+δa₁b₁, где α,β,γ,δ, суть функции классов c,d…;

3) однородной относительно трех классов a,b,c, коль скоро она приведена к виду: p(abc)+q(abc₁)+r(ab₁c)+s(ab₁c₁)+t(a₁bc)+u(a₁bc₁)+v(a₁b₁c)+x(a₁b₁c₁), где p,q,r… не зависят от a,b и с. И т.д.

Понятно, что для приведения какой угодно функции F(a,b,c,d…) ко всевозможным однородным видам вполне пригодны формулы Буля, служащие к разложению функций по одному, двум, трем и т.д. классам, т.е. формулы

F(a,b,c,d…)=aF(1,b,c,d,…)+a₁F(0,b,c,d…)

F(a,b,c,d….)=abF(1,1,c,d…)+ab₁F(1,0,c,d…)+a₁bF(0,1,c,d…)+ +a₁b₁F(1,0,c,d…)

F(a,b,c,d…)=abcF(1,1,1,d…)+abc₁F(1,1,0,d…)+ab₁cF(1,0,1,d…)+ +ab₁c₁F(1,0,0,d…)+a₁bcF(0,1,1,d…)+a₁bc₁F(0,1,0,d…)+ +a₁b₁cF(0,0,1,d…)+a₁b₁c₁F(0,0,0,d…).

И т.д. Но будет короче и проще пользоваться для той же цели следующим простым правилом. Для приведения функции n классов к однородному виду i-го измерения в отношении каких-либо I классов, достаточно каждый член этой функции порознь привести к этому измерению, т.е. если в данный член не входят некоторые из помянутых i классов, то его надо умножить на тождественную единицу, составленную из этих недостающих классов. Тождественная же единица каких-либо классов p,q,r… есть (p+p₁)(q+q₁)(r+r₁)…

Когда, так или иначе, функция N, служащая полным логическим нулем равенства A=B, приведена к однородному виду известного измерения i, то соответственная система 2ⁱ равенством (некоторые, из которых могут оказаться тождествами 0=0) получится через приравнение нулю каждого члена функции N порознь.

Легко проследить логическое значение отдельных равенств в системах, получаемых через приведение функции N ко всевозможным однородным видам.

По приведении ее к однородному виду относительно одного какого-либо класса a, мы получаем вместо равенства 0=N или равенство 0=Pa+Qa₁, или, при употреблении формулы Буля, равенство 0=aN(1,b,c,d…)+a₁N(0,b,c,d…). Соответственная система будет 0=Pa, 0=Qa₁, или, при употреблении формулы Буля, равенство 0=aN(1,b,c,d…)+a₁N(0,b,c,d…). Соответственная система будет 0=Pa, 0=Qa₁, или же 0=aN(1), 0=a₁N(0), откуда и видно, что это есть пара равенств полного определения a двумя функциями: 1) функцией P₁ или Т₁(1) (или еще M(1)), содержащей в себе a, и 2) функцией Q или N(0) (или еще M₁(0)), содержащейся в a.

Делая функцию N однородной относительно двух классов a и b, мы получаем систему 2² равенств, а именно:

0=αab, 0=βab₁, 0=γa₁b, 0=δa₁b₁,

Или, при употреблении формулы Буля:

0=abN(1,1), 0=ab₁N(1,0), 0=a₁bN(0,1), 0=a₁b₁N(0,0).

Отсюда видим, что равенства такой системы служат к указанию, в каких функциях прочих классов c,d… содержатся различные конституанты классов a и b.

Приведение функции N к однородному виду относительно 3-х классов доставляет 2³ равенств, определяющих, в чем содержатся различные конституанты этих трех классов. И т.д. Наконец, как мы уже видели, приведение к n измерению приводит нас к 2ⁿ элементарных посылок, определяющих, какие элементарные конституанты всех n классов служат логическими нулями данного равенства A=B.

Напомним, что приведение функции N к i-му измерению через непосредственное приведение к этому измерению каждого ее члена вообще должно быть проще, чем употребление соответственных формул Буля, потому что оно не приводит нас к тождественным равенствам 0=0, которые потом должны быть отбрасываемы.

Для примера возьмем задачу, полный логический нуль которой есть

0=ac₁+bd=N(a,b,c,d)

(Эта задача должна быть противоположна предыдущей задаче о домовладельцах, богачах и проч.). Построим систему 2³ равенств, отвечающих приведению функции N к 3-му измерению относительно классов b,c,d.

Применяя формулу Буля, мы должны вычислить 2³, т.е. 8, символов, для которых получим:

N(a,1,1,1)=1, N(a,0,1,1)=0, N(a,1,1,0)=0, N(a,0,1,0)=0,

N(a,1,0,1)=2, N(a,0,0,1)=a, N(a,1,0,0)=a, N(a,0,0,0)=a.

Три равенства сведутся на тождество, и получается следующая система 5 равенств:

0=bcd, 0=bc₁d, 0=abc₁d₁, 0=ab₁c₁d, 0=ab₁c₁d₁.

Дело будет проще, если мы в равенстве 0=ac₁+bd начнем каждый член приводить к 3-му измерению относительно классов b,c,d. С этою целью, напишем это равенство в виде:

0=bd+(b₁+d₁)ac₁=bd+ab₁c₁+ac₁d₁. В отношении классов b,c,d, все три члена этого выражения суть 2-го измерения, и для приведения их к третьему достаточно умножить первый из них на c+c₁, второй на d+d₁ и третий на b+b₁, после чего получим:

0=bcd+bc₁d+ab₁c₁d+ab₁c₁d₁+abc₁d₁+ab₁c₁d₁.

Выбрасывая здесь 6-й член, потому что она есть повторение 4-го, мы получим 5 посылок, совершенно тех же, что и выше.

Наконец, не делая предварительного преобразования исходной формулы 0=ac₁+bd, мы должны умножить в ней 1-й член (который есть 1-го измерения относительно классов b,c,d) на (b+b₁)(d+d₁)=bd=bd₁+b₁d+b₁d₁, а второй на c+c₁. Получили бы:

0=abc₁d+abc₁d₁+ab₁c₁d+ab₁c₁d₁+bcd+bc₁d,

откуда должен быть выброшен 1-й член, потому что он содержится в последнем, и получится та же самая задача о 5 посылках.

В заключение этого § нужно заметить, что, следуя изложенным здесь приемам, мы далеко не исчерпаем даже таки систем, в которых число равенств есть 2 во всевозможных степенях до n─1-й включительно. Таким образом, необходимость изложенного вначале общего метода построения максимальной системы делается очевидной.

§ 9. Происхождение всевозможных функций из различных форм мира речи

Приведение какой угодно функции f ко всевозможным однородным видам можно рассматривать не только как средство для получения различных систем, отвечающих равенству f=0, но и как указание происхождения функции f из всевозможных универсальных единиц, составленных из различных комбинаций классов a,b,c,d…, фигурирующих в этой функции.

Делая функцию f однородной относительно a, т.е. приводя ее к виду Pa+Qa₁, мы указываем ее происхождение из конституантов a и a1 универсальной единицы одного a, т.е. 1=a+a₁. А именно, мы видим, что 1-й конституант этой единицы должен быть умножен на P, а второй на Q, после чего сложение итогов и доставить данную функцию f. Другими словами, мы видим, какие части помянутых конституантов должны быть сложены для образования данной функции. – Приводя ту же функцию ко второму измерению относительно двух классов a и b, т.е. к виду

α(ab)+β(ab₁)+γ(a₁b)+δ(a₁b₁),

мы указываем ее происхождение из тождественной единицы этих двух классов, т.е. из выражения

1=(a+a₁)( b+ b₁)= ab+ab₁+a₁b+a₁b₁.

А именно, конституанты этой единицы должны быть умножены соответственно на α, β, γ, δ и итоги должны быть сложены. Так определяется те части этих конституантов, сложение которых доставляет данную функцию. И т.д. Наконец, делая ту же функцию f однородной относительно всех n классов a,b,с,d…, мы указываем ее происхождение из универсальной единицы всех этих n классов, т.е. из выражения 1=(a+a₁)(b+ b₁)(с+с₁)…=(abсd)+…+(a₁b₁с₁d₁.), а именно, мы определяем какие конституанты этой единицы, взятые целиком, надо сложить для полученной данной функции. – Остановим наше внимание на этом последнем способе происхождения каждой функции f из универсальной единицы всех n классов, входящих в эту функцию. Как видим, в однородном виде n-го измерения, всякая функция f приводится к виду простой суммы нескольких элементарных конституантов. Другими словами, коэффициенты при конституантах суть единицы (при происхождении же из прочих тождественных единиц коэффициенты при конституантах суть функций: напр. P и Q суть функций b,c,d,...; α, β, γ, δ суть функций c,d,…). Отсюда открывается возможность сделать следующее важное заключение: всевозможные функции n классов через последовательное приравнивание нулю всех ее членов по одному, по два, по три и т.д. до (n-1). Отсюда же открывается, что число логических функций, какие только можно составить из данных n классов, должно быть меньше ₂2ⁿ.

§ 10. Основные свойства конституантов

Чтобы вполне закончить рассмотрение 1-го подразделения первоначальной нашей задачи, указанной в начале этой главы, считаем необходимым обратить внимание на следующие два основных свойства конституантов одного и того же измерения, составленных из одних и тех же классов. Эти два свойства, не требующие дальнейших пояснений, суть: 1) Сумма всех таких конституантов всегда есть 1 и 2) произведение двух (и более) из них всегда =0. В силу второго из этих свойств, конституанты одного и того же порядка от одних и тех же классов не имеют ничего общего между собой, не зависят друг от друга и не выражаются один через другой или через какую-либо комбинацию других. Наоборот, конституанты различных порядков выражаются одни через другие. Напр., конституант 2-го порядка ab разбивается на два конституанта 3-го порядка: abc и abc₁, на 4 конституанта 4-го порядка: abcd, abcd₁, abc₁d и abc₁d₁. И т.д.

Вторым из указанных свойств однородных конституантов можно воспользоваться для построения след. сокращенного правила перемножения функций, разложенных на однородные конституанты. Произведение двух разложений F=ks’+ls’’+ms’’’+… и F’=k’s’+l’s’’+m’s’’’+…, где s’, s’’, s’’’ … суть конституанты одного и того же измерения, составленные из одних и тех же классов, всегда будет: FF’=kk’s’+ll’s’’+mm’s’’’+…. Правило это (весьма полезное) установлено еще Булем, но, по недосмотру, не попало в наше введение к настоящей статье, и мы пользуемся случаем, чтобы восполнить этот пробел.

§ 11. Нахождение элементарных посылок в единичной форме. Способ разложения функций на множители

Обращаемся ко второму подразделению первоначальной задачи, т.е. пусть для равенства A=B требуется построить тождественную с ним максимальную систему посылок в единичной форме. Нет сомнения, что, взяв отрицания найденных по предыдущему элементарных логических нулей данного равенства, мы получим максимальную систему в единичной форме. Однако, существует прямой путь для этой цели, основанный на способе разложения логических функций на множители, и так как этот способ сам по себе может иметь значение в математич. логике, то я и займусь его изложением. Считаю нужным прибавить, что задачу о замещении равенства A=B всевозможными системами мне удалось решить первоначально именно этим путем, и только впоследствии я убедился, что натуральнее и проще она решится для нулевой формы искомых посылок. Таким образом, если в прямой способ математич. логики натуральнее иметь дело с логическими, то в обратном, наоборот, с логическими нулями.

Вот рассуждения, которые привели меня к построению обратного способа математич. логики.

Зная, что ряд посылок, превращенных в единичную форму: 1=M’, 1=M’’, 1=M’’’, …, тождественно замещаются одним равенством 1= M’M’’M’’’…=M, я заключил, что, наоборот, для замещения равенства A=B системой необходимо и достаточно превратить его в единичную форму 1=M и разбить функцию M на множители, после чего останется только приравнять каждый из этих множителей порознь единице. Осталось найти способ для разложения логических функций на множители. Изыскание такого способа долго меня затрудняло, п.ч. не удавалось найти твердой точки опоры. После многих попыток, я убедился, что основание для такого способа должно заключаться в правилах отрицания логических сумм и произведений. Эти правила состоят в том, что отрицание произведения равно сумме отрицаний сомножителей и отрицание суммы равно произведению отрицаний слагаемых. В силу этих правил, желая разбить какую угодно функцию M на множители, мы должны составить отрицание этой функции, т.е. M₁, разбить на его суммы, и взять отрицание этого разложения, после чего функция M и окажется разбитой на множители. Таким образом, если мы обратимся к формулам Буля, представляющим всевозможные разложения функций на суммы, и возьмем их отрицания, то получим формулы для всевозможных разложений функций на множители. Так получается следующий ряд разложений одной и той же функции на множители:

F(a,b,c,d...)=[a+ F(0,b,c,d…)][a₁+F(1,b,c,d,…)]

F(a,b,c,d…)=[a+b+F(0,0,c,d…)][a+b₁+F(0,1,c,d,…)][a₁+b+F(1,0,c,d…)]
[a₁+b₁+F(1,1,c,d,…)]

F(a,b,c,d...)=[a+b+c+F(0,0,0,d…)][a+b+c₁+F(0,0,1,d,…)]
[a+b₁+c+F(0,1,0,d…)][a+b₁+c₁+F(0,1,1,d,…)][a₁+b+c+F(1,0,0,d…)] [a₁+b+c₁+F(1,0,1,d,…)][a₁+b₁+c+F(1,1,0,d,…)][a₁+b₁+c₁+F(1,1,1,d…)].

И т.д. Закон построения этих формул очевиден.

В каждой из них каждый множитель представляет продуцент, сложенный с известным символом. Таким образом, если формулы Буля суть формулы разложения функций по конституантам различных порядков, то наши формулы можно назвать формулами разложения функций по продуцентам различных порядков. Одна и та же функция f(a,b,c,d…), разложенная напр. в отношении a и b по конституантам и продуцентам, будет:

f(a,b,c,d…)=abf(1,1)+ab₁f(1,0)+a₁bf(0,1)+a₁b₁f(0,0)=[a+b+f(0,0)]
[ a+b₁+f(0,1)][ a₁+b₁+f(1,0)][ a₁+b₁+f(1,1)].

Причем одни и те же символы фигурируют в обоих ее разложениях. А потому, раз эти символы для какой-нибудь функции вычислены, легко составить разложение этой функции, как на конституанты, так и на продуценты.

Понятно, что для построения в единичной форме максимальной системы, отвечающей равенству A=B, необходимо, превратить это равенство в форму 1=M, разложить функцию M на продуценты n-го порядка. Так получается следующая схематическая система 2ⁿ равенств:

1=a+b+c+d+…+M(0,0,0,0,…)

1=a₁+b+c+d+…+M(1,0,0,0,…)

1=a+b₁+c+d+…+M(0,1,0,0,…)

……………………………………………

1=a₁+b₁+c₁+d₁+…+M(1,1,1,1,…)

Здесь каждый из символов может быть только или единицей или нулем. Коль скоро символ =1, то соответственное равенство сводится на тождество 1=1 и выпадает из системы. Когда же символ =0, то он сам выпадает из равенства. А потому все равенства фактически максимальной системы состоят в указании на то, какие из элементарных продуцентов данных n классов служат частными логическими единицами в задаче A=B.

Имея максимальную систему элементарных единиц задачи и перемножая последние между собою по два, по три и т.д., мы получим всевозможные системы, отвечающие данному равенству A=B. – Разлагая же функцию M на всевозможные продуценты порядка низшего, чем n, мы получили бы различные системы, число посылок которых = числу 2 в различных степенях.

Обратимся к примеру. Построим еще несколько задач на тему

1=ac₁+bd=M(a,b,c,d),

Предполагая по-прежнему, что a означает домовладельцев, b богачей, c купцов, d старообрядцев.

Разлагая функцию M на продуценты в отношении одного класса a, мы получим след. задачу о двух посылках: 1=a+M(0)=a+bd, 1=a₁+M(1)=a₁+c₁+bd, которым можно придать, например, такой вид: a=a+(b₁+d₁), c=c(a₁+bd). След. посылками одной из задач на взятую тему могли бы быть следующие две: 1) все небогатые горожане, а так же все не старообрядцы были в числе домовладельцев; 2) купцы принадлежали частью к не домовладельцам, частью же к богатым старообрядцам.

Развертывая туже функцию M на продуценты двух классов b и d, получим след. систему 4-х равенств: 1=b+d+M(a,0,c,0)=b+d+ac₁;
1=b+d₁+M(a,0,c,1)=b+d₁+ac₁; 1=b₁+d+M(a,1,c,0)=b₁+d+ac₁; 1=b₁+d₁+M(a,1,c,1)=b₁+d₁+1=1.

Здесь последнее равенство есть тождество. Остаются 3 посылки, из которых первую мы решим относительно b, вторую относительно d₁, третью относительно ac₁. Получим:

b=b+(d+ac₁)1=b+d₁(a₁+c)

d₁=d₁+(b+ac₁)₁=d₁+b₁(a₁+c)

ac₁=ac₁+(b₁+d)₁=ac₁+bd₁.

След. одою из задач на заданную тему могла бы служить следующие задача о 3-х посылках: 1) между богачами встречались такие не старообрядцы, которые или были купцами, или не были домовладельцами; 2) все небогатые не домовладельцы и все небогатые купцы не были старообрядцами; и 3) богатые не старообрядцы относились к домовладельцам из купцов.

Развертывание той же функции M на продуценты классов b,c,d доставит нам 8 посылок:

1=b+c+d+M(a,0,0,0)=a+b+c+d

1=b+c+d₁+M(a,0,0,1)=a+b+c+d₁

1=b+c₁+d+M(a,0,1,0)=b+c₁+d+0=b+c₁+d

1=b+c₁+d₁+M(a,0,1,1)=b+c₁+d₁+0=b+c₁+d₁

1=b₁+c+d+M(a,1,0,0)=a+b₁+c+d

1=b₁+c+d₁+M(a,1,0,1)=b₁+c+d₁+1=1

1=b₁+c₁+d+M(a,1,1,0)=b₁+c₁+d+0=b₁+c₁+d

1=b₁+c₁+d₁+M(a,1,1,1)=b₁+c₁+d₁+1=1.

Здесь две посылки суть тождества. Остаются только 6 посылок, которые и можно рассматривать, как 6 посылок новой задачи на туже тему 1=ac₁+bd. Но эти же 6 посылок можно скомбинировать, например, в след. задачу о 3-х посылках

1=(a+b+c+d)(b+c₁+d₁)=b+(a+c+d)(c₁+d₁)=b+ac₁+ad₁+cd₁+c₁d; 1=(a+b+c+d₁)(a+b₁+c+d)=a+c+(b+d₁)(b₁+d)=a+c+bd+b₁d₁; 1=(b+c₁+d)(b₁+c₁d)=c₁+d.

Определяя из 1-й посылки b₁, из второй a+c, и придавая 3-й нулевую форму, будем иметь:

b₁=b₁(ac₁+ad₁+cd₁+c₁d)

a+c=(a+c)+(b₁+d₁)(b+d)=a+c+bd₁+b₁d

0=cd₁,

т.е. та самая задача, которую мы уже имели в § 5.

Желая, наконец, построить максимальную систему элементарных посылок, мы должны собственно вычислить 2⁴, т.е. 16 символов. Однако, гораздо проще можно получить максимальную систему из предыдущей системы о шести посылках, сделав в ней переход от неэлементарных посылок к посылкам элементарным. Дело в том, что в этой системе все посылки суть продуценты, частью 4-го, частью же 3-го порядка. Эти последние и надо привести к 4-му порядку. Вообще для перехода от продуцента данного порядка к продуцентам следующего, на 1 высшего, порядка с успехом можно пользоваться следующей предлагаемой нами формулой:

g=(g+p)(g+p₁).

На этом основании

b+c₁+d=(a+b+c₁+d)(a₁+b+c₁+d)

b+c₁+d₁=(a+b+c₁+d₁)(a₁+b+c₁+d₁)

b₁+c₁+d=(a+b₁+c₁+d)(a₁+b₁+c₁+d).

След. посылками максимальной системы в данном случае будут служить следующие девять: