Назад в библиотеку

Логико‑вероятностный анализ и его история

Автор: И. А. Рябинин
Источник: Логико‑вероятностный анализ и его история, "http://www.ipme.nw.ru/ ...



Джордж Буль (2.11.1815–8.12.1864) — английский математик и логик был безусловно в самом начале этой истории. Его книга Исследование законов мышления, на которых основаны математические теории логики и вероятностей [1], изданная в Лондоне в 1854 году, явилась глубокой идеей Буля о применимости математической логики к теории вероятностей.

А в неопубликованной при его жизни работе [2] он даже упоминает о возможности использования вероятностных оценок в логических построениях, то есть о возможности численного определения высказываний (propositions).

Буль заложил основы математической логики. Имя Буля получили так называемые булевы алгебры.

Однако первооткрывателем логиковероятностного анализа (ЛВА) следует признать Платона Сергеевича Порецкого (3.10.1846–9.08.1907) — русского математика и логика, который 25 октября 1886 года в своем Сообщении (Решение общей задачи теории вероятностей при помощи математической логики [3]) придал строгую научную форму идее Буля о применимости математической логики к теории вероятностей.

В §1 Сообщения [3] он ставит философский вопрос: возможно ли приложение учения о качественных символах (логических классах) к учению о символах количественных (вероятностях)?

И отвечает: возможно.

На стр.3 [3] дано первое определение ЛВА... Отсюда открывается общий путь для определения вероятностей: найти логическую связь между событием, которого вероятность ищется, и другими событиями, вероятности которых даны, а затем сделать переход от логического равенства между событиями к алгебраическому равенству между их вероятностями.

Изюминка этого определения кроется в выделенном автором слове переход. Отсюда начинается описание главного результата автора. Для возможности пользоваться правилом несовместности необходимо уметь каждый логический многочлен

A ∨ B ∨ C ∨ D ∨ ... (1)

приводить к дизъюнктному (по современному — ортогональному) виду, т.е. к виду

A ∨ A B ∨ A B C ∨ A B C D ∨ ..., (2)

где A есть отрицание A, B — отрицание B и т.д.

Здесь я привел современные правила обозначения логических сумм ∨ и отрицаний A (у П. С. Порецкого + и Aо соответственно).

Оба многочлена логически равнозначны, но отличаются тем, что к первому из них не применимо предыдущее правило, тогда как к второму применимо.

Вероятность логической суммы

P (A ∨ B ∨ C ∨ D),

будучи приведена к дисъюнктному виду, разбивается на арифметическую сумму вероятностей

P (A) + P (A B) + P (A B C) + P (A B C D). (3)

Из теории вероятностей известно, если два и более события суть независимы, то вероятность их совпадения равна произведению их отдельных вероятностей. Это значит, что если a,b,c ... — суть простые события, не связанные между собою никакими логическим отношениями, то

P (abc ...) = P (a) P (b) P (c) ...

и

P (A) + P (A) P (B) + P (A) P (B) P (C) + ... (4)

На стр. 7 в качестве примера представлен авторский алгоритм ортогонализации для дизъюнкции

ab ∨ cd. (5)
  1. Производится внешняя ортогонализация
    2. ab ∨ ab cd. (6)
  2. Затем отрицание ab по закону де Моргана преобразуется в дизъюнкцию двух отрицаний
    3. ab = a ∨ b. (7)
  3. Производится внутренняя ортогонализация
    4. a ∨ b = a ∨ ab. (8)
  4. Объединяются все три операции
    5. ab ∨ cd = ab ∨ abcd = ab ∨ (a ∨ b)cd =
    ab ∨ (a ∨ ab)cd = ab ∨ acd ∨ abcd.    		 (9)

Последнее выражение есть ортогональная дизъюнктивная нормальная форма (ОДНФ), которая позволяет вычислить вероятность

P (ab ∨ cd) = P (ab) ∨ P (acd) ∨ P (abcd). (10)

Таким образом, именно П. С. Порецкий в 1886 году открыл строгий математический метод вычисления вероятности сложного события через вероятности простых событий.

Эволюцию идей математической логики нельзя представить в виде восходящей кривой. Периоды расцвета зачастую сменяются моментами регрессии и частичного упадка.

Здесь полезно вспомнить критику московского логика и математика Б. М. Кояловича [4, стр.417], который огонь своей критики направлял против практической неэффективности алгебры логики, которая, как ему казалось, была принципиально не способна давать плодотворные внелогические приложения.

Переводчик на русский язык книги Л. Кутюра Алгебра логики профессор И. В. Слешинский, отвечая Кояловичу, смог лишь указать на работу Порецкого Решение общей задачи теории вероятностей при помощи математической логики, заметив, что Порецкий несколько рационализировал и развил Буля в этом вопросе.

Тогда Коялович сослался на то обстоятельство, что ни в одном из крупных современных ему трактатов по теории вероятностей (и среди них в монографии [5] русского академика А.А.Маркова) нет никакого упоминания о существовании какой‑либо связи этой научной дисциплины с алгеброй логики.

Однако в 1910 году физик Пауль Эренфест первым предложил использовать математическую логику в технике. Он писал: Символическая формулировка даст возможность «вычислять» следствия из таких сложных посылок, в которых при словесном изложении почти или совершенно невозможно разобраться. В качестве примера он приводил схемы проводов автоматической телефонной станции.

И только С. Н. Берштейн не испугался формальной разницы между качественными и количественными символами, и ровно через 30 лет разработал первую (по времени) аксиоматику логики высказываний для аксиоматизации теории вероятностей [6].

Как писал Валерий Иванович Гливенко в своей работе [10, стр.274]: Самые вероятности С. Н. Берштейн предложил рассматривать как вероятности истинности предложений. При этом отпадает необходимость в формулировке специальной аксиоматики для понятия события, и мы можем пользоваться готовой аксиоматикой предложений.

Думаю, что Сергей Натанович был знаком с работой П. С. Порецкого [3], который в 1870 году окончил физикоматематический факультет Харьковского университета, в котором с 1907 по 1933 г. преподавал и С. Н. Берштейн.

Невостребованность практикой (первой половиной ХХ столетия) привела к забвению выдающихся математических результатов Порецкого П. С. и Берштейна С. Н. Этому способствовали и трудности в добыче их публикаций. Ссылаясь на работу [3] только по ее названию в книгах [7,8,9], как на начало развития логиковероятностного метода, я все же тогда не отождествлял Порецкого П. С. с первооткрывателем логиковероятностного анализа.

В условиях 30х годов — да и последующих десятилетий тоже — логика в СССР требовала защиты и в философском, и в математическом сообществах.

Софья Александровна Яновская в совместной энциклопедической статье с В. И. Гливенко в 1938 году о математической логике объявила ее просто наукой о рассуждениях в математике. Подобное толкование математической логики предохраняло её от нападок сторонников диалектической логики. В 1943 году она организовала на механикоматематическом факультете МГУ научноисследовательский семинар по математической логике, которым руководила совместно с И. И. Жегалкиным и П. С. Новиковым. Её работы в области математической логики подготовили открытие 3 марта 1959 года кафедры математической логики на том же факультете МГУ, при создании которой выполнила основную организаторскую работу, была профессором кафедры до последних дней свой жизни (24.10.1966).

Первым заведующим кафедрой был Андрей Андреевич Марков (22.09.190311.10.1979). С января 1980 по октябрь 1987 заведующим кафедрой был Андрей Николаевич Колмогоров (25.04.190320.10.1987).

В большой статье 1947 года о Математике в её историческом развитии [11] А. Н. Колмогоров всего одним предложением отмечает роль математической логики.

Эти исследования вырастают в большой самостоятельный отдел М. — Математическую логику. Основы математической логики создаются в 19 в. Дж. Булем, П. С. Порецким, Э. Шрёдером, Г. Фреге, Дж. Пеано и др.. Больше о П. С. Порецком и его научном вкладе в ЛВА не сказано ничего.

В 1938 году В. И. Шестаков и К. Шеннон дали строгое обоснование возможности использования исчисления высказываний для описания релейноконтактных схем. Исходя из этих работ, Михаил Александрович Гаврилов создал стройную теорию анализа и синтеза релейноконтактных схем, в которой для функций, записанных в дизъюнктивной нормальной форме (ДНФ) также требовался переход к ОДНФ, названной им канонической формой [12, стр.213].

Глубокие идеи Буля о расширении формализма алгебры логики на вероятности в 1956 году способствовали появлению работы французского математика N.Rouche [13], в которой он указывает, как нужно изменить совершенную дизъюнктивную нормальную форму (СДНФ), чтобы вместо логических переменных можно было подставить вероятности их осуществления и таким образом получить вероятность осуществления сложного высказывания.

Вторичное независимое открытие алгоритма ортогонализации произошло в 1963 году в Институте математики (Новосибирск) в отделении Вычислительной техники специалистом по счетнорешающим приборам и устройствам Мерекиным Юрием Владимировичем. В это время задача о вероятности вычисления обращения в единицу булевой функции (N. Rouche) уже считалась тривиальным решением. Для решения прикладных задач применение СДНФ считалось нерациональным изза большого числа дизъюнктивных членов. Возникла необходимость построения короткой ортогональной формы, которая и была получена в 1963 году [14]. На мой вопрос Ю. В. Мерекину в апреле 2011 года о Порецком П. С. , 03.05.2011 был получен такой ответ: ... Работа П. С. Порецкого 1887 года мною не использовалась.

Третье независимое открытие ортогонализации произошло в 1973 году итальянцами Luidge Fratta и Ugo Montanari [15] с помощью карт Карно и понятия Disjoint Products — несовместных произведений

DP = Pi & Pj = 0. (9)

Развитие ЛВА происходит трудами инженеров [4,7,8,9,12] и попытки привлечь чистых математиков к этой проблеме пока не имели успеха. Поэтому критика ЛВА в стиле Б. М. Кояловича в начале 20 века, что ни в одном трактате по теории вероятностей нет никакого упоминания о существовании какой‑либо связи вероятности с алгеброй логики, продолжается и сейчас.

Могу лишь с сожалением добавить, что и в конце 20 века отсутствует не только научная оценка ЛВА, но даже упоминание имени П. С. Порецкого в учебнике Математическая логика [16] А. Н. Колмогорова, А. Г. Драгалина.

Прав И. Слешинский, который в некрологе 10 августа 1907 года писал, что имя Порецкого более известно за границей, чем на его родине.

На этом фоне неудивительна и критика ЛВА современных математиков [17, 18] в духе отрицания возможности применения учения о качественных символах к учению о символах количественных. Так профессор Голота Я. Я. считает, что Алгебра логики высказываний исходит из полной определённости объектов изучения. Теория же вероятностей предполагает неопределённость в совершении событий. Таким образом, в одной теории объединяются отрицающие друг друга начала: полная определённость и неопределённость. Не говорит ли это об очевидном противоречии, лежащим в основе логико‑вероятностной теории? Или в другом месте [17]: Да и само понятие вероятности, вобравшее в себя многовековой опыт употребления его, не дает повода считать, что традиционное представление о вероятности допускает понимание вероятности как оценку истинности высказываний.

Другой ученый доктор технических наук Соколюк В. Н. в работе [18,стр.103], рассуждая об адекватности логики мировоззренческим принципам, пишет…Если придерживаться теории вероятностей, то следует признать, что абсурдно говорить об «истинности событий» и о «вероятности высказываний», поскольку истинность — характеристика высказываний, но не событий, а вероятность — характеристика событий, но не высказываний. Каждое высказывание феноменально. Бессмысленно говорить об их массовости в теоретико‑вероятностном смысле, хотя многие «ученые» даже пишут книги и создают теории, которые ведут в никуда [7].

Чтобы ознакомится с теориями, которые ведут в никуда в отечественной практике рекомендую статью [19], в которой на примерах из 42 источниках сообщаются сведения о логико‑вероятностном анализе как аппарате исследования надежности, живучести и безопасности структурно‑сложных систем любой природы.

Еще большее число примеров использования ЛВА в зарубежной литературе представлено в публикациях [20, 21, 22]. Там они встречаются под названиями:

Возросший спрос на ЛВА во второй половине 20 века возник в задачах оценки надежности и безопасности структурно‑сложных систем любой природы. Повышенный интерес к ЛВА связан также с развитием ЭВМ, то есть с компьютеризацией методов ЛВА.

Идея Буля о применимости математической логики к теории вероятностей привела не только к развитию ЛВА, но и разработке вероятностной логики (ВЛ).

Предметом логики вероятностей является вычисление вероятности истинности высказываний, принимающих только два значения: истинно (1), ложно (0).

Предметом вероятностной логики является оценка истинности высказываний (гипотез), принимающих множество значений в промежутке (0 ≤ x ≤ 1).

Иначе говоря, в первом случае имеют дело с двузначной логикой, во втором — с многозначной логикой. В связи со сказанным, логикавероятностей (ЛВ) естественно проще вероятностной логики (ВЛ).

Все формулы теории вероятностей для сложных событий y=f(x1, ..., xn), являющихся функциями независимых в совокупности событий x1, ..., xn, становятся правильными логическими формулами при замене событий на соответствующие суждения (propositions).

Это замечательное явление, как заметил доктор физико‑математических наук, профессор Николай Васильевич Хованов, имеет место потому, что у суждений только два значения истинности — (ложь) 0, (истинно) 1.

А пустое ∅ и полное Ω события, имеющие вероятности P {∅} = 0 и P [Ω] = 1, независимы ни от других событий, ни друг от друга, ни от себя самих.

Возвращаясь к вопросу о возможности приложения учения о качественных символах к учению о символах количественных, обратим внимание на слово пропозиция.

О каких предложениях, высказываниях или суждениях идет речь в логико‑вероятностном анализе? Конечно не о любых, а только о тех, на которые возможен ответ: да либо нет, то есть о контрадикторных противоположностях, а не о контрарных. Такая оппозиция возникла, например, в теории надежности, где рассматриваются только два состояния (работоспособное и отказ). В середине 20 века еще трудно было свыкнуться с возможностью количественной оценки надежности. Однако к 70‑м годам классическое определение вероятности отказа, как численной меры объективной возможности такого случайного события, через частоту отказов, стало вполне естественным и общепринятым среди инженеров и технической общественности.

Следует подчеркнуть, что взаимные переходы от языка высказываний к языку событий и обратно совершаются таким образом, что каждому событию сопоставляется высказывание о его наступлении, а высказыванию сопоставляется событие, состоящее в том, что оно оказалось истинным.

Контрадикторные оппозиции (белое — небелое) встречаются не только в надежности, но и в других проблемных областях (безопасность, живучесть, валидность и др.). Критик ЛВА профессор Я. Я. Голота считает, что реальный мир — это мир контрарных отношений (белое — черное). Автор работы [23] считает, что логика контрарных отношений — это логика реального бытия, а логика контрадикторных отношений — это логика идеального бытия. Конечно, между белым и черным можно вставить целую радугу цветов (гипотез) и это ближе к реальному миру, но я остаюсь все же приверженцем идеализированного бытия, которое и проще, и честнее.

В качестве заключения истории развития ЛВА будем надеяться, что не только Н. В. Хованов, но и другие математики разберутся в заслугах Дж. Буля, П. С. Порецкого, С. Н. Берштейна, В. И. Гливенко, С. А. Яновской, Ю. В. Мерекина о применимости математической логики к теории вероятностей, и в своих трудах четко выскажутся по данному вопросу.

А отвечая на критику Б. М. Кояловича о принципиальной неспособности алгебры логики давать плодотворные внелогические приложения [4, стр.417], приведем краткий аннотированный список из 150 публикаций зарубежных периодических изданий по вопросам оценивания структурно‑сложных систем [21] и еще 23 публикации (см. Приложение 1) по различным алгоритмам SDP.

Список использованной литературы

  1. Boole George, An Investigation of the Laws of Thought, on which founded the Mathematical Theories of Logic and Probabilities, London, 1854.
  2. Boole George, On propositions numerically definite, January 1, 1869, Cambridge Philosophical Society.
  3. Порецкий П.С. Решение общей задачи теории вероятностей при помощи математической логики.- Собрание протоколов 60-го заседания секции физико-математических наук общества естествоиспытателей при Казанском университете, Казань, 1886,с.1-34.
  4. Труды Казанской секции физ.мат.наук. Серия 1., 1887, т.5, с.83-116.
  5. Стяжкин Н.И.Формирование математической логики. М.: Наука, 1967, 508с.
  6. Марков А.А. Исчисление вероятностей, СПб, 1900.
  7. Бернштейн С.Н. Опыт аксиоматического обоснования теории вероятностей// Сообщения Харьковского Математического общества, вторая серия, том XV, 1917, с.209-274.
  8. Рябинин И.А., Черкесов Г.Н. Логико-вероятностные методы исследования надежности структурно-сложных систем. М.: Радио и связь, 1981,-264с.
  9. Рябинин И.А. Надежность и безопасность структурно-сложных систем. СПб.: Политехника. 2000,-248с.
  10. Рябинин И.А. Надежность и безотказность структурно-сложных систем. СПб.: Изд-во С.-Петерб. Ун-та, 2007,-276 с. Второе издание.
  11. Гливенко В.И. Курс теории вероятностей. М-Л, 1939, 275с.
  12. Колмогоров А.Н. Развитие математики в СССР. Большая советская энциклопедия, - 1947. - т. «СССР», - с.1318-1323.
  13. Гаврилов М.А., Девятков В.В., Пупырев Е.И. Логическое проектирования дискретных автоматов// Изд-во Наука, М., 1977.
  14. Rouche N. Extension aux probabilites du formalisme de l’algebre logique//Revue HF, 1956, N5 (Руш Н. Расширение формализма алгебры логики на вероятности).
  15. Мерекин Ю.В. Решение задач вероятностного расчета однотактных схем методом ортогонализации // Вычислительные системы. 1963. Вып.4.
  16. L.Fratta, U.G.Montanari, A Boolean Algebra Method for Computing the Terminal Reliability in a Communication Network, IEEE Trans. Circuit Theory, vol CT-20, 1973 May, pp 203-211.
  17. Колмогоров А.Н., Драгалин А.Г. Введение в математическую логику. М.: Издательство Московского Университета, 1982.
  18. Голота Я.Я. О двух вычислительных вольностях, огорчающих логика// http://www.inftach.webservis.ru/ ....
  19. Соколюк В.Н. Парадокс современного бытия// Философский век, Альманах 7, Между физикой и метафизикой: наука и философия, Санкт-Петербург, 1998, с.100-107.
  20. Рябинин И.А. Логико-вероятностный анализ и его современные возможности.// Биосфера, Том 2, №1, СПб, 2010, с.23-28.
  21. Рябинин И.А. История возникновения, становления и развития логико-вероятностного исчисления в мире// Труды международной научной школы «Моделирование и анализ безопасности и риска в сложных системах» (МАБР-2011), СПб, 2011, с.15-35.
  22. Рябинин И.А., Струков А.В. Кратко аннотированный список публикаций зарубежных периодических изданий по вопросам оценивания надежности структурно-сложных систем// Труды международной научной школы Моделирование и анализ безопасности и риска в сложных системах (МАБР-2011), СПб, 2011, с. 363-379.
  23. Рябинин И.А. Логико-вероятностный анализ проблем надежности и безопасности.//Saarbrucken, Deutschland, 2012, Palmariun, Academic Publishing, 263pp.
  24. Голота Я.Я. О Новом подходе, основанном на логике контрарных отношений, к оценке надежности // Международная конференция по мягким вычислениям и измерениям. Сб. докладов. Т.1, СПб., 27-29 июня 2007г. – СПб. Изд-во СПбГЭТУ «ЛЭТИ», 2007.

Приложение 1

  1. M.O.Locks, A minimizing algorithm for sum of disjoint products, IEEE Trans. Reliability, vol R-36, NO.4, October 1987, pp 445-458.
  2. F.Beichelt, L.Spross, An improved Abraham-method for generating disjoint sums, IEEE Trans. Reliability, vol R-36, NO.4, October 1987, pp 70-74.
  3. F.Beichelt, L.Spross, Comments on ‘An improved Abraham-method for generating disjoint sums, IEEE Trans. Reliability, vol R-38, NO.4, October 1989, pp 422-424.
  4. K.D.Heidtmann, Smaller Sums of Disjoint Products by Subproduct Inversion, IEEE Trans. Reliability, vol R-38, NO.3, August 1989, pp 305-311.
  5. J.M.Wilson, An Improved Minimizing Algorithm for Sum of Disjoint Products, IEEE Trans. Reliability, vol R-39, NO.1 April 1990, pp 42-45.
  6. M.Veeraraghavan, K.S.Trivedi, An Improved Algorithm for Symbolic Reliability Analysis, IEEE Trans. Reliability, vol R-40, NO.3 August 1991, pp 347-358.
  7. M.O.Locks, J.M.Wilson, Note on Disjoint Products Algorithms, IEEE Trans. Reliability, vol R-41, NO.1 March 1992, pp 81-84.
  8. S.Soi, S.Rai, Experimental results on preprocessing of paths/cuts terms in sum of disjoint products technique, IEEE Trans. Reliability, vol R-42, NO.1 March 1993, pp 24-33.
  9. S.Rai, M.Veeraraghavan, K.Trivedi, A Survey of Efficient Reliability Computation Using Disjoint Products Approach, Networks, Vol.25, 1995, pp 147-165.
  10. P.Marquis, S.Sadaoui, A New Algorithm for Computing Theory Prime Implicates Computations, AAAI-96 Proceedings, 1996, Knowledge Compilation, pp 504- 509
  11. T.Luo, K.S. Trivedi, An Improved Algorithm for Coherent-System Reliability, IEEE Trans. Reliability, vol R-47, NO.1 March 1998, pp 73-78.
  12. E.Chanelet, Y.Dutuit, A.Rauzy, T.Bouhoufani, An Optimized Procedure To Generate Sums of Disjoint Products, Reliability Engineering and System Safety, 65 (1999), pp 289-294.
  13. B. Anrig , F. Beichelt, Disjoint Sum Forms in Reliability Theory, ORiON, Vol. 16, No. 1, pp. 75-86, 2001.
  14. L.Traldi, Disjoint products and S-patitions, Lafayette College, pp 1-24.
  15. T.Bengtsson, A.Martinelli, E.Dubrova, A Fast Heuristic Algorithm for Disjoint Decomposition of Boolean Functions, CAT, pp 1-5.
  16. A.O. Balan, An Enhanced Approach to Network Reliability Using Boolean Algebra, An Honors Thesis presented to the Departments of Computer Science and Mathematics of Lafayette College on May 16, 2003, pp 1-43.
  17. Rauzy A., Chatelet, Dutuit Y., Berenguer C., A practical comparison of methods to assess sum-of-product, Reliability Engineering and System Safety, 79, No1, (2003), pp 33-42.
  18. A.O. Balan, L.Traldi, Preprocessing Minpath for Sum of Products, IEEE Trans. Reliability, vol R-52, NO.3 September 2003, pp 289-294.
  19. N.Drechsler, M.Hilgemeier, G.Fey, R. Drechsler, Disjoint Sum of Product Minimization by Evolutionary Algorithms, University of Bremen, pp 1-10.
  20. A. Rauzy, A New Methodology to Handle Boolean Models With Loops, IEEE Trans. Reliability, vol R-52, NO.1 March 2003, pp 96-105.
  21. L.Traldi, Non-minimal sums of disjoint products, Report, Lafayette College, pp 1-3.
  22. L.Traldi, A conjecture about sums of disjoint products, Lafayette Colledge, pp 1-4.
  23. G.Castanon, A.M.Sarmiento,R.Ramires, A.Aragon-Zavala, Software tool for network reliability and availability analysis, Center of Electronics and Telecommunications, Mexico, pp 1-13.