алгебра буля — это… Что такое алгебра буля?

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

Буль представляет логику как алгебру классов (будем обозначать их символами А, В, С,…). Основными операциями в А. Б. являются: сложение классов AE.B; умножение классов АCВ; дополнение класса А\’. Свойства этих операций описываются следующими аксиомами:

la. AE(BEC)=(AEB) EC — ассоциативность сложения;

16. AC(BCC)= (ACВ) EC — ассоциативность умножения;

2a.AEB= BEA — коммуникативность сложения;

2б.АCВ =ВCА — коммуникативность умножения;

3a.AE(ВCС)= =(AEB) C(AEC) — дистрибутивность сложения относительно умножения;

36.AC(BEC)==(ACB) E(ACC) — дистрибутивность умножения относительно сложения.

В А. Б. существуют два элемента 0 и 1, операции с которыми

подчиняются следующим соотношениям:

AE0=A;

AC1=A;

AEA\’=1;

ACA\’=0.

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

равна А: АEА=А, а не 2А, как в обычной алгебре. Точно так же и произведение двух A равно A: АCА=А, а не A2.

Важным законом А. Б. является принцип двойственности, согласно которому если в некотором справедливом равенстве мы заменим все вхождения E на C и C на E, 1 на 0 и 0 на 1, то получим равенство, двойственное первому и также справедливое. Примерами двойственных равенств являются приведенные выше аксиомы.

А.Б. широко применяется при проектировании и проверке электрических схем, в которых используются реле, работающие по принципу «да — нет», при программировании и проектировании ЭВМ, в операциях с переключателями, сигналами, схемами. В современной математической логике этот раздел значительно усовершенствован и разрабатывается как теория булевых алгебр, в том числе как алгебра множеств, алгебра высказываний и т. п. В области традиционной логики соотношения А. Б. часто используются для иллюстрации и прояснения отношений между объемами понятий.

Словарь по логике. — М.: Туманит, изд. центр ВЛАДОС. А.А.Ивин, А.Л.Никифоров. 1997.

Джордж Буль – отец математической логики

2 ноября 1815 года родился выдающийся английский математик и логик Джордж Буль

. Одним из главных успехов в его жизни стало создание в середине XIX века математической логики – раздела математики, который строится на применении формальных математических методов для решения логических задач. 

Можно сказать, любовь к математике у учёного была с рождения. Отец Джорджа Буля, простой ремесленник Джон Буль, глубоко интересовался наукой. Увлечение математикой пришло к выдающемуся учёному в подростковом возрасте, и именно тогда Джордж Буль решил посвятить всю свою жизнь этой науке. С юных лет был помощником учителя в частной школе в Донкастере, а затем и сам стал преподавать. 

Джордж Буль по праву считается отцом математической логики. Его именем назван раздел математической логики — булева алгебра (алгебра логики). В 1848 году была опубликована статья Джорджа Буля по началам математической логики — «Математический анализ логики, или опыт исчисления дедуктивных умозаключений», а в 1854 году появилась главная его работа — «Исследование законов мышления, на которых основаны математические теории логики и вероятностей». В этих трудах говорилось о возможности изучения свойств математических операций, осуществляемых не только над числами. Ученый рассуждал о символическом методе, который он применял как к изучению дифференцирования и интегрирования, так и к логическому выводу и теоретико-вероятностным рассуждениям. Именно он построил один из разделов формальной логики в виде некоторой «алгебры», аналогичной алгебре чисел, но не сводящейся к ней. А также создал своеобразную алгебру – систему обозначений и правил, применяемую к различного рода объектам — от чисел до предложений. Использование этой системы позволяло закодировать высказывания (утверждения, истинность или ложность которых требовалось доказать) с помощью символов своего языка, а затем управлять ими, как математическими числами. Основными операциями булевой алгебры представлены: конъюнкция (И), дизъюнкция (ИЛИ), отрицание (НЕ).

После смерти Джорджа Буля его систему стали применять для описания электрических переключателей схем. Говоря простым языком, ток в цепи может либо протекать, либо отсутствовать, подобно тому, как утверждение может быть либо истинным, либо ложным. Спустя несколько десятилетий ученые решили объединить созданный Джорджем Булем математический аппарат с двоичной системой счисления для описание двух состояний: утверждение истинно — утверждение ложно, лампочка горит — лампочка не горит, заложив тем самым основы для разработки цифрового электронного компьютера.

Материал подготовлен из открытых источников

Джордж Буль

200 лет со дня рождения Джорджа Буля :: Государственный Университет Телекоммуникаций

Джордж Буль родился 2 ноября 1815 года в Линкольне (Англия), в семье бедного башмачника. Хотя он был современником Ч. Бэббиджа, но происходил не из привилегированного класса, как Бэббидж.

Выходец из слоя общества, дети которого фактически были лишены посещения университета, Джордж должен был заниматься самостоятельно. Хотя промышленная революция уже произошла в Англии, знание древних языков было показателем уровня образования джентльмена. Конечно, ника­кой латинский или греческий не преподавали в школе, которую посещал Буль. Буль сам изучил греческий и латинский, пользуясь поддержкой малообразованного отца, и в возрасте 12 лет сумел перевести оду Хорейса на английский язык. Ничего не понимая в качестве техники перевода, гордый отец Буля все-таки напечатал его в местной газете. Некоторые специалисты заявляли, что 12-летний мальчик не мог сделать такой перевод, другие отме­чали серьезные технические дефекты перевода. 

Расширив общий метод Лейбница, сформулированный на 188 лет раньше, в котором все истинные причины были сведены к виду вычислений, английский математик Д. Буль в 1854 году заложил основу того, что мы сегодня знаем как математическую логику, опубликовав работу “Исследование законов мышления”.

В этой работе, изданной, когда ему было 39 лет, Буль свел логику к чрезвычайно простому типу алгебры, алгебры логики высказываний, которая представляла собой систему символов и правил, применяемую к различным объектам (числам, буквам, предложениям).

Его теория логики, основанная на трех основных действиях — AND (и), OR (или), NOT (не), — должна была стать в XX веке основой для разработки переключающих телефонных линий и проекта ЭВМ. Так же, как и идеями Лейбница, булевой алгеброй пренебрегали в течение многих лет после того, как она была создана.

Несмотря на большое значение булевой алгебры во многих других областях математики, необычайная работа Буля в течение многих лет считалась странностью. Как и Бэббидж, Буль был человеком, опередившим свое время. Это произошло раньше, чем Альфред Уайтхед и Бертран Рассел опубликовали свой трехтомник “Принципы математики” (1910—1913), в котором рассматривались вопросы формальной логики.

Жена Буля была племянницей Джорджа Эвереста, в 1841 году завершившего в Индии грандиозные по масштабам работы. В честь его заслуг высочайшая вершина мира Джомолунгма в Гималаях одно время даже именовалась Эверестом. Сама Мэри, в отличие от жен многих других математиков, понимала научные идеи своего мужа и своим внимани­ем и участием подвигала его на продолжение исследований. После его смер­ти она написала несколько сочинений и в последнем из них — “Философия и развлечения алгебры”, — опубликованном в 1909 году, пропагандировала математические идеи Джорджа.

У четы Булей было пять дочерей. Старшая, Мэри, вышла замуж за Ч. Хин-тона — математика, изобретателя и писателя-фантаста — автора широко из­вестной повести “Случай в Флатландии”, где описаны некие существа, жи­вущие в плоском двухмерном мире. Из многочисленного потомства Хинто-нов трое внуков стали учеными: Говард — энтомологом, а Вильям и Джоан — физиками. Последняя была одной из немногих женщин-физиков, принимавших участие в работе над атомным проектом в США.

Вторая дочь Булей, Маргарет, вошла в историю как мать крупнейшего анг­лийского механика и математика, иностранного члена Академии наук СССР Джеффри Тэйлора. Третья, Алисия, специализировалась в исследовании многомерных пространств и получила почетную ученую степень в Гронин-генском университете. Четвертая, Люси, стала первой в Англии женщиной-профессором, возглавившей кафедру химии.

Но наиболее известной из всех дочерей Булей стала младшая, Этель Лили­ан, вышедшая замуж за ученого — эмигранта из Польши Войнича. Войдя в революционную эмигрантскую среду, она написала прославивший ее на весь мир роман “Овод”. За ним последовало еще несколько романов и му­зыкальных произведений, а также перевод на английский язык стихотворе­ний Тараса Шевченко. Войнич скончалась в Нью-Йорке в возрасте 95 лет, немного не дожив до столетия со дня смерти своего знаменитого отца мате­матика Джорджа Буля.

Алгебра логики Джорджа Буля: VIKENT.RU

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

Однако, как бы то ни было, за свою короткую жизнь Буль добился высших научных отличий. К концу жизни он уже возглавлял кафедру математики в Куинз Колледж в Корке.

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

Ему удалось построить алгебру с формальными правилами, с помощью которой можно выразить любое высказывание, облечённое в словесную форму.

Так, например, можно принять, что х = «идёт дождь», а у = «идёт град». Тогда произведение ху будет означать, что «идёт дождь и град». После перевода таких обыденных словесных выражений в математические символы алгебра полностью вступает в свои права и выводы получаются уже чисто математическими средствами.

В начальный период исследования перед Булем возникла следующая проблема. В логике существует закон тождества, который просто утверждает, что вещь является самой собой. Алгебраически этот закон выражается равенством х = х (тождеством), и никто против этого не возражает.

Если в обычной речи мы повторяем одно и то же дважды, то смысл наших слов от этого не меняется. Этим мы можем лишь усилить высказывание, но формальные свойства утверждения «идёт дождь, идёт дождь» ничем не отличаются от свойств однократного утверждения «идёт дождь». Однако в булевой алгебре закон тождества необходимо было преобразовать, чтобы учесть, что х = х и хх = х.

Последнее выражение недопустимо в обычной алгебре, в которой х² = х представляет собой бессмыслицу. Более того, словесное выражение не меняет смысла от бесконечного повторения утверждения «идет дождь», так что в общем виде в алгебре логики получается, что хⁿ = х.

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

Однако Буль заметил, что это противоречие с классической алгеброй можно снять, если наложить определённые условия на численную интерпретацию всей построенной им алгебры. Поэтому он ввёл необходимое ограничение, заключающееся в том, что все алгебраические переменные могут принимать только два численных значения: 0 и 1.

При этом условии равенство хⁿ = х справедливо.

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

Нуль в алгебре Буля соответствует отрицанию, единица — утверждению.

Следовательно, х = 1 означает «идёт дождь», а у = 0 означает «града нет».
Вскоре Булю удалось разработать весьма совершенный математико-логический аппарат, основанный на этом принципе. Так, например, выражение (1 — х) у = 1 означает «град идёт, но дождя нет», а (1 — х) (1 — у) = 1 выражает суждение «нет ни дождя, ни града».

Стаффорд Бир, Кибернетика и управление производством, М., «Наука», 1965 г., с.113-114.

Алгебра Буля

§ 4 Функции алгебры логики

4.1 Алгебра Буля

         Как видно из равносильностей III группы, алгебра логики обладает коммутативными и ассоциативными законами относительно операций конъюнкции и дизъюнкции. Эти законы имеют место в алгебре чисел, поэтому над формулами алгебры логики можно производить те же преобразования, которые проводятся в алгебре чисел (раскрытие скобок, заключение в скобки, вынесение за скобки общего множителя).

 

            Рассмотрим непустое множество М элементов любой природы , в котором определены отношения «=» (равно) и три операции: «+» (сложение), «_*» (умножение) и «-» (отрицание), подчиняющиеся следующим аксиомам:

 

Коммутативные законы:

1а. x+y=y+x                       1б. x_*y=y_*x

 

Ассоциативные законы:

2а. x+(y+z)=(x+y)+z          2б. x_*(y_*z)=(x_*y)_*z

 

Дистрибутивные законы:

3а. (x+y)_*z=(x_*z)+(y_*z)      3б. (x_*y)+z=(x+z)_*(y+z)

 

Законы идемпотентности:

4а. x+x=x                           4б. x_*x=x

 

Закон снятия двойного отрицания:

5.

 

Законы де-Моргана:

6а.                   6б.

 

Законы поглощения:

7а. x+(y_*x)=x                       7б. x_*(y+x)=x

 

            Такое множество М называется булевой алгеброй. Если под основными элементами  рассматривать высказывания, а под операциями «+», «_*»,   «-» дизъюнкцию, конъюнкцию, отрицание соответственно, а знак равенства как знак равносильности, то, как следует из равносильностей I, II и III групп, все аксиомы булевой алгебры выполняются. Значит, алгебра логики является интерпретацией булевой алгебры.

 

О «ЛОГИЧЕСКОМ ИСЧИСЛЕНИИ» ДЖ. БУЛЯ | Пушкарский

Кант 1964 — Кант И. Критика чистого разума // Соч. в шести томах. Т. 3. М.: Мысль, 1964.

Пушкарский 2015 — Пушкарский А. Г. О судьбе центрального философского замысла создателя алгебры логики: к 200-летию Джорджа Буля // Вестник Балтийского федерального университета им. И. Канта. 2015. Вып. 12. C. 81–88.

Пушкарский 2019 — Пушкарский А. Г. Основной закон мышления: от Канта к Булю // Вестник Томского государственного университета. Философия. Социология. Политология. 2019. № 51. C. 114–128.

Стяжкин 1967 — Стяжкин Н. И. Формирование математической логики. М.: Наука, 1967.

Черноскутов 2012 — Черноскутов Ю. Ю. Язык и предмет логики в Британской логической традиции XIX века // Вестник Санкт-Петербургского университета. Сер. 6. 2012. Вып. 1. C. 3–15.

Черноскутов 2016 — Черноскутов Ю. Ю. Развитие семантических идей в Британской логике XIX века // РАЦИО.ru. 2016. № 17 (2). C. 111–133.

Boole 1847 — Boole G. The mathematical analysis of logic, being an essay towards a calculus of deductive reasoning. London: Macmillan, 1847.

Boole 1848 — Boole G. The Calculus of Logic // Cambridge and Dublin Mathematical Journal. 1848. Vol. III. P. 183–198.

Boole 1854 — Boole G. An investigation of the laws of thought, on which are founded the mathematical theories of logic and probabilities. London-Cambridge: Macmillan, 1854.

Boole 1997 — Boole G. Selected manuscripts on logic and its philosophy / [ed. by] lvor Grattan-Guinness, Gerard Bornet. Basel; Boston; Berlin: Birkhauser, 1997.

Gregory 1865 — Gregory D. F. The Mathematical Writings of Duncan Farquharson Gregory, M.A. / W. Walton, Ed.. Cambridge, UK: Deighton, Bell, 1865.

Hailperin 1986 — Hailperin T. Boole’s Logic and Probability. N.Y., 1986.

Hailperin 2000 — Hailperin T. Boole’s Algebra Isn’t Boolean Algebra (1981) // A Boole Anthology. Recent and Classical Studies in the Logic of George Boole. Springer-Science + Business Media, B.Y., 2000. P. 61–78.

Laita 1980 — Laita L. M. Boolean algebra and its extra-logical sources: the testimony of Mary Everest Boole // History and Philosophy of Logic. 1980. Vol. 1. P. 37–60.

Laita 2000 — Laita L. M. The Influence of Boole’s Search for a Universal Method in Analysis on the Creation of His Logic (1977) // A Boole Anthology. Recent and Classical Studies in the Logic of George Boole. Springer-Science + Business Media, B.Y., 2000. P. 45–59.

MacHale 2014 — MacHale D. The Life and Work of George Boole. A Prelude to The Digital Age. Cork University Press, 2014.

Буль Джордж

 XPOHOC ВВЕДЕНИЕ В ПРОЕКТ ФОРУМ ХРОНОСА НОВОСТИ ХРОНОСА БИБЛИОТЕКА ХРОНОСА ИСТОРИЧЕСКИЕ ИСТОЧНИКИ БИОГРАФИЧЕСКИЙ УКАЗАТЕЛЬ ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ ГЕНЕАЛОГИЧЕСКИЕ ТАБЛИЦЫ СТРАНЫ И ГОСУДАРСТВА ЭТНОНИМЫ РЕЛИГИИ МИРА СТАТЬИ НА ИСТОРИЧЕСКИЕ ТЕМЫ МЕТОДИКА ПРЕПОДАВАНИЯ КАРТА САЙТА АВТОРЫ ХРОНОСА Родственные проекты: РУМЯНЦЕВСКИЙ МУЗЕЙ ДОКУМЕНТЫ XX ВЕКА ИСТОРИЧЕСКАЯ ГЕОГРАФИЯ ПРАВИТЕЛИ МИРА ВОЙНА 1812 ГОДА ПЕРВАЯ МИРОВАЯ СЛАВЯНСТВО ЭТНОЦИКЛОПЕДИЯ АПСУАРА РУССКОЕ ПОЛЕ

Джордж Буль Буль Джордж (1815—1864) — английский логик и математик, разработал исторически первую систему математической логики, впоследствии названную алгеброй логики. Идея аналогии между алгеброй и логикой определила все направление его логических исследований, изложенных в двух основных трудах: «Математический анализ логики» (1847) и «Исследование законов мысли…» (1854). Философский словарь. Под ред. И.Т. Фролова. М., 1991, с. 54. Буль (Boole) Джордж (2.11.1815, Линкольн, — 8.12. 1864, Баллинтемнл, близ Корка), английский математик и логик. В работах «Математический анализ логики» («The mathematical analysis of logic», 1847), «Логические исчисление» («The calculus of logic», 1848), «Исследование законов мышления» («An investigation of the lows of thought…», 1854) Буль заложил основы математической логики. Именем Буля названы так называемые булевы алгебры — особые алгебраические системы, для элементов которых определены две операции. Философский энциклопедический словарь. — М.: Советская энциклопедия. Гл. редакция: Л. Ф. Ильичёв, П. Н. Федосеев, С. М. Ковалёв, В. Г. Панов. 1983. Литература: Льар Л., Английские реформаторы логики в XIX в., пер. с франц., СПБ, 1897; Venn J., Boole’s logical system, «Mind», 1876, v. l, № 4. Буль (Boole) Джордж (2.XI.1815, Линкольн — 8 октября 1864, Боллингтемпль, близ г. Корка, Ирландия) — английский математик и логик, основоположник алгебры логики. Математикой овладел путем самообразования. В 1849—1864 годы профессор математики в Куинс-колледже (Корк). В математическом анализе шел самостоятельным путем, но его основные достижения относятся к логике. В сочинении «Математический анализ логики» (L., 1847) изложил основы исторически первой алгебро-логической системы и выразил в ней ассерторическую силлогистику. В своем главном сочинении — «Исследование законов мысли» (L., 1854) детально развил алгебраическое построение логики, применив его к силлогистике и теории вероятностей, а также связав с психолого-эпистемологическими вопросами. Исходя из аналогии между математическими и логическими операциями, Буль ввел «логическое умножение» (пересечение классов, соответственно конъюнкцию высказываний), «логическое сложение» (некое приближение к строгой дизъюнкции, соответственно объединению классов с исключением их общей части). Введение универсального класса (так называемого «универсума рассуждения») и «логического вычитания» для классов позволило выражать отрицание (соответственно, дополнение класса до универсального), что дало полную систему операций логики классов (соответственно логики высказываний) и отвечающие ей законы. Представляя высказывания в виде равенств, Буль для формализации дедукции развил методику решения логических уравнений. Не будучи непосредственно булевой алгеброй, система Буля исторически явилась ее истоком (работы Джевонса). Б. В. Бирюков Новая философская энциклопедия. В четырех томах. / Ин-т философии РАН. Научно-ред. совет: В.С. Степин, А.А. Гусейнов, Г.Ю. Семигин. М., Мысль, 2010, т. I, А — Д, с. 325. Буль (Boole), Джордж (1815-1864), английский логик и математик, основатель математической, символической логики. Согласно Булю, общие законы логики по своей форме тождественны в основном общим законам чисел. Система слов языка должна быть заменена системой знаков —искусственных символов, имеющих строго определенное значение и могущих сочетаться друг с другом по известным постоянным законам. Символы эти заимствуются из алгебры, так же как и правила их комбинирования. Так, если условиться под X, Y, Z и т. д. подразумевать вещи и качества, объекты наших понятий, то знаки + ,—, X, = будут означать действия, при помощи которых сочетаются эти вещи: именно, + означает соединение объектов, то, что на обычном языке выражается словами «и», «или»; X означает принадлежность качества объекту; — означает выделение объекта из ряда других объектов; = означает тождество, понятия «есть» или «суть». «Все» или «целое» выражается при помощи знака 1, вследствие чего 1-х означает все, за исключением данного класса объектов. Так, например, предложение «светила суть солнце и планеты», если светила обозначить через X, солнце через Y и планеты через Z, представится в виде равенства: X=Y+Z. По Булю, свойства логического равенства совпадают вполне со свойствами алгебраического лишь при х=1 или 0. Под произведением X. Y понятий X и Y разумеется совокупность объектов, входящих в состав как понятия X, так и понятия Y, поэтому в математической логике X.X=X или X2=X. Исходя из этого равенства, Буль пытается дать формальное доказательство закона исключенного третьего. Если X2=X, то X—X2=0 или X (1—X)=0. Последнее же означает, что, если, например, X есть класс людей, следовательно, 1— X класс всех не-людей, то не может существовать класс таких индивидов, которые были бы одновременно и людьми и не-людьми. Уже последователь Буля — Джевонс указывал на ошибки, к которым приводит его метод. Если, например, X есть Цезарь, Y —завоеватель Галлии, Z—писатель, то не только X—Y+Z, но X—Y=Z, что явно неверно. Особенность символической логики состоит в том, что она игнорирует совершенно содержание изучаемых объектов и стоит на исключительно формальной точке зрения (см. Логика, Логика математическая, Диалектика). Формальные методы Буля, однако, целесообразно применил в некоторых чисто математических построениях, заложив, таким образом, начало, так называемой теории дистрибутивных операторов (…). Ц. Карев. Большая советская энциклопедия. Гл. ред. О.Ю. Шмидт. Том восьмой. Буковые – Варле. – М., АО Советская энциклопедия. – 1927. Колонка. 39. Сочинения: «The Mathematical Analysis of Logic», Cambridge, 1847; «An Investigation of the Laws of Thought», L., 1854. Литература: Бобынин, В. В., Опыты математического изучения логики, вып. 1, М., 1886; L. L i а г d, Les logiciens anglais contemporains, Paris, 1878; J. Venn, Symbolic Logic, L., 1881. Далее читайте: Философы, любители мудрости (биографический справочник ХРОНОСа).  Исторические лица Англии (Великобритании) (биографический указатель). Сочинения: Collected Logical Works, v. I, II. The Open Court: La Salle (111.), 1952. «The Mathematical Analysis of Logic», Cambridge, 1847; «An Investigation of the Laws of Thought», L., 1854. Литература: Стяжкин Н. И. Формирование математической логики Л,—М., 1967. Бобынин, В. В., Опыты математического изучения логики, вып. 1, М., 1886; Льяр Л. Английские реформаторы логики в 19 в., пер. с франц. СПб., 1897; L. Liагd, Les logiciens anglais contemporains, Paris, 1878; J. Venn, Symbolic Logic, L., 1881. Broadbent T. A. A. Georg Boole, in Dictionary of Sci. Biography, v. II, 1970; Venn J. Boole’s logical system. — «Mind», 1876, v. 1, N 4; Kneale W.&M. The Development of Logic. Oxf., 1978;

Математика булевой алгебры (Стэнфордская энциклопедия философии)

Булева алгебра (BA) — это множество \ (A \) вместе с двоичными операции + и \ (\ cdot \) и унарная операция \ (- \), а также элементы 0, 1 из \ (A \) такие, что выполняются следующие законы: коммутативность и ассоциативные законы сложения и умножения, законы распределения как для умножения над сложением, так и для сложения над умножение и следующие специальные законы:

\ [\ begin {align *} (х + (х \ cdot у) & = х \\ (х \ cdot (х + у) & = х \\ х + (-х) & = 1 \\ х \ cdot (-x) & = 0 \ конец {выравнивание *} \]

Эти законы лучше понять на базовом примере BA, состоящий из набора \ (A \) подмножеств множества \ (X \) замкнутых при операциях объединения, пересечения, дополнения с относительно \ (X \), с членами \ (\ varnothing \) и \ (X \).Можно легко вывести из этих аксиом многие элементарные законы, имея в виду этот пример для мотивации. Любая БА имеет естественный частичный порядок \ (\ le \) определил на нем, сказав, что \ (x \ le y \) тогда и только тогда, когда \ (x + у = у \). В нашем основном примере это соответствует \ (\ substeq \). Из Особое значение имеет двухэлементная БА, образованная набором \ (X \), чтобы иметь только один элемент. Двухэлементный БА показывает прямое связь с элементарной логикой. Два члена, 0 и 1, соответствуют к лжи и правде соответственно.Затем логические операции выражают обычные таблицы истинности для дизъюнкции (с \ (+) \), конъюнкции (с \ (\ cdot) \) и отрицанием (с \ (-) \). Важный элементарный В результате уравнение выполняется во всех БА тогда и только тогда, когда оно выполняется в двухэлементный БА. Затем мы определяем \ (x \ oplus y = (x \ cdot -y) + (y \ cdot -x) \). Тогда \ (A \) вместе с \ (\ oplus \) и \ (\ cdot \), вдоль с 0 и 1, образует кольцо с единицей, в котором каждый элемент идемпотентный. Наоборот, для такого кольца с добавлением \ (\ oplus \) и умножение, определите \ (x + y = x \ oplus y \ oplus (x \ cdot y) \) и \ (- x = 1 \ oplus x \).Это превращает кольцо в BA. Эти двое процессы противоположны друг другу и показывают, что теория Булевых алгебр и колец с единицей, в которых каждый элемент является идемпотенты по определению эквивалентны. Это ставит теорию БА в стандартный объект исследования в алгебре. Атом в БА — это ненулевой элемент \ (a \) такой, что не существует элемента \ (b \) с \ (0 \ lt б \ л а \). БА является атомарной, если каждый ненулевой элемент БА выше атом. Конечные БА атомарны, как и многие бесконечные БА.Под частичный порядок \ (\ le \) выше, \ (x + y \) — наименьшая верхняя граница \ (x \) и \ (y \), а \ (x \ cdot y \) — точная нижняя граница \ (х \) и \ (у \). Мы можем обобщить это: \ (\ Sigma X \) — наименьшее верхняя граница множества элементов \ (X \), а \ (\ Pi X \) — наибольшее нижняя граница множества \ (X \) элементов. Это не для всех множества во всех булевых алгебрах; если они существуют всегда, логическое алгебра называется полной.

Некоторые алгебраические конструкции имеют очевидные определения и простые свойства БА: подалгебры, гомоморфизмы, изоморфизмы и прямые произведения (даже бесконечного числа алгебр).Некоторые другие Стандартные алгебраические конструкции более характерны для БА. Идеал в BA — это подмножество \ (I \), замкнутое относительно +, с 0 в качестве члена, и такое что если \ (a \ le b \ in I \), то также \ (a \ in I \). Хотя нет сразу очевидно, это то же самое, что и теоретико-кольцевое концепция. Существует двойственное понятие фильтра (не имеющее аналога в кольца в целом). Фильтр — это подмножество \ (F \), замкнутое относительно \ (\ cdot \), имеющий 1 в качестве члена и такой, что если \ (a \ ge b \ in F \), то также \ (а \ в F \). Ультрафильтр на \ (A \) — это фильтр \ (F \) с следующие свойства: \ (0 \ not \ in F \), и для любого \ (a \ in A \) либо \ (а \ в F \) или \ (- а \ в F \).Для любого \ (a \ in A \) пусть

\ [ S (a) = \ {F: F \ text {является ультрафильтром на} A \ text {и} a \ in F \}. \]

Тогда \ (S \) — изоморфизм на БА подмножеств множества \ (X \) множества все ультрафильтры на \ (A \). Это устанавливает основной камень теорема о представлении и проясняет происхождение БА как конкретных алгебры множеств. Более того, множества \ (S (a) \) можно объявить базой топологии на \ (X \), что превращает \ (X \) в полностью несвязное компактное хаусдорфово пространство. Это устанавливает один-один соответствие между классом БА и классом таких пробелы.Как следствие, очень часто используемые в теории БА, многие топологические теоремы и концепции имеют последствия для БА. Если \ (x \) является элементом БА, пусть \ (0x = -x \) и \ (1x = x \). Если \ ((x \) (0), \ (\ ldots x (m — 1)) \) — конечная последовательность элементов BA \ (A \), то каждый элемент подалгебры в \ (A \), порожденный \ (\ {x (0), \ ldots, x (m — 1) \} \) можно записать как сумму мономов \ (e (0) x (0) \ cdot \ ldots \ cdot e (m — 1) x (m — 1) \) для \ (e \) в некотором наборе функций, отображающих \ (m = \ {0, \ ldots, m — 1 \} \) в \ (2 = \ {0, 1 \} \).Это алгебраическое выражение дизъюнктивной нормальной формы Теорема сентенциальной логики. Функция \ (f \) из множества \ (X \) образующие БА \ (А \) в БА \ (B \) продолжаются до гомоморфизм тогда и только тогда, когда

\ [ е (0) х (0) \ cdot \ ldots \ cdot e (m — 1) x (m — 1) = 0 \]

всегда означает, что

\ [e (0) f (x (0)) \ cdot \ ldots \ cdot e (m — 1) f (x (m — 1)) = 0. \]

Это критерий расширения Сикорского. Каждый BA \ (A \) может быть вложено в полный BA \ (B \) таким образом, что каждый элемент \ (B \) — точная верхняя граница набора элементов \ (A \).\ (B \) есть единственна с точностью до \ (A \) — изоморфизма и называется пополнением \ (А \). Если \ (f \) — гомоморфизм БА \ (А \) в полную БА \ (B \), и если \ (A \) — подалгебра в \ (C \), то \ (f \) может быть продолжается до гомоморфизма \ (C \) в \ (B \). Это Теорема Сикорского о продолжении. Еще одно общее алгебраическое понятие применительно к булевым алгебрам понятие свободного алгебра. Это может быть конкретно сконструировано для БА. А именно бесплатные BA на \ (\ kappa \) — это БА замкнутых открытых подмножеств двух элементов дискретное пространство возведено в степень \ (\ kappa \).

Есть много важных специальных классов булевой алгебры. как для внутренней теории БА, так и для заявок:

• Атомные БА, уже упомянутые выше.
• Безатомные БА, которые определены как БА без атомов. Например, любое бесконечное свободный БА безатомен.
• Полные BA, определенные выше. Это специально важен в основах теории множеств.
• Интервальные алгебры. Они получены из линейно упорядоченных множеств \ ((L, \ lt) \) с первым элементом следующим образом.Один берет самое маленькое алгебра подмножеств \ (L \), содержащая все полуоткрытые интервалы [\ (a, b) \) с \ (a \) в \ (L \) и \ (b \) в \ (L \) или равно \ (\ infty \). Эти БА полезны в изучение алгебр Линденбаума-Тарского. Каждый счетный БА изоморфна интервальной алгебре, а значит, счетная БА может быть описывается указанием упорядоченного множества, такого, что оно изоморфно соответствующая интервальная алгебра.
• Древовидные алгебры. Дерево — это частично упорядоченное множество \ ((T, \ lt) \) в в котором множество предшественников любого элемента упорядочено.Данный такое дерево рассматривается алгебра подмножеств \ (T \), порожденная всеми множествами вида \ (\ {b: a \ le b \} \) для некоторого \ (a \) в \ (Т \).
• Суператомные БА. Это БА которые не только атомарны, но таковы, что каждая подалгебра и гомоморфный образ атомарен.

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

1. Клеточность \ (c (A) \) БА есть верхняя грань мощности множеств попарно непересекающихся элементов \ (A \).
2. Подмножество \ (X \) БА \ (A \) является независимым, если \ (X \) — это набор свободных образующих подалгебры, генерирует. Независимость \ (A \) есть верхняя грань мощности независимых подмножеств \ (A \).
3. Подмножество \ (X \) БА \ (A \) плотно в \ (A \), если каждый ненулевой элемент \ (A \) является \ (\ ge \) ненулевым элементом \(ИКС\). \ (\ Pi \) — вес \ (A \) — это наименьшая мощность плотного подмножества \ (A \).
4. Два элемента \ (x, y \) из \ (A \) несравнимы если ни один из них не является \ (\ le \) другим. Супремум мощностей подмножество \ (X \) в \ (A \), состоящее из попарно несравнимых элементов — это несравнимость \ (A \).
5. Подмножество \ (X \) из \ (A \) неизбыточно, если ни один элемент из \ (X \) находится в подалгебре, порожденной другими.

Важным фактом, касающимся клеточности, является метод Эрдеша-Тарского. Теорема: если клеточность БА — особый кардинал, то существует фактически представляет собой набор непересекающихся элементов такого размера; на клеточность штатный лимит (недоступен), есть контрпримеры. Каждый бесконечная полная БА имеет независимое подмножество того же размера, что и алгебра. Каждый бесконечный BA \ (A \) имеет неизбыточную несравнимую подмножество, размер которого равен \ (\ pi \) — весу \ (A \). Каждый интервал алгебра имеет счетную независимость.Суператомная алгебра не даже иметь бесконечное независимое подмножество. Любая древовидная алгебра может быть вложено в интервальную алгебру. БА только с удостоверением личности автоморфизм называется жестким. Существуют жесткие полные БА, а также жесткие интервальные алгебры и жесткие древовидные алгебры.

В последнее время многие кардинальные функции типа min-max были учился. Например, малая независимость — это наименьший размер бесконечное максимальное независимое множество; и малая клеточность — это наименьший размер бесконечного разбиения единицы.

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

Очень важная конструкция, которая переносится на многие логики и многих алгебр, кроме булевых, является построением Булева алгебра связана с предложениями в некоторой логике.В Самый простой случай — это логика предложений. Здесь есть символы предложений, и общие связки, составляющие из них более длинные предложения: дизъюнкция, союз и отрицание. Для набора \ (A \) предложений в этом языке два предложения \ (s \) и \ (t \) эквивалентны по модулю \ (A \) тогда и только тогда, когда двусмысленность между ними является логическим следствие \ (A \). Классы эквивалентности могут быть преобразованы в БА. такой, что + соответствует дизъюнкции, \ (\ cdot \) — конъюнкции и \ (- \) к отрицанию. Любая БА изоморфна одной из этих форм.Можно сделайте нечто подобное для теории первого порядка. Пусть \ (T \) — теория первого порядка в языке первого порядка \ (L \). Мы называем формулы \ (\ phi \) и \ (\ psi \) эквивалент при условии, что \ (T \ vdash \ phi \ leftrightarrow \ psi \). Класс эквивалентности предложения \ (\ phi \) обозначается [\ (\ phi \)]. Пусть \ (A \) — совокупность всех классы эквивалентности по этому отношению эквивалентности. Мы можем сделать \ (A \) в БА следующими определениями, которые легко оправдано:

\ [\ begin {align *} [\ phi] + [\ psi] & = [\ phi \ vee \ psi] \\ [\ phi] \ cdot [\ psi] & = [\ phi \ wedge \ psi] \\ — [\ phi] & = [\ neg \ phi] \\ 0 & = [\ mathrm {F}] \\ 1 & = [\ mathrm {T}] \ конец {выравнивание *} \]

Каждая БА изоморфна БА Линденбаума-Тарского. алгебра.Однако одно из наиболее важных применений этих классических Алгебры Линденбаума-Тарского должны описать их для важных теорий. (обычно разрешимые теории). Для счетных языков это может быть сделано путем описания их изоморфных интервальных алгебр. Обычно это дает доскональное знание теории. Вот несколько примеров:

	Теория	Изоморфна интервальной алгебре на
(1)	по существу неразрешимая теория	\ (\ mathbb {Q} \), рациональные числа
(2)	БА	\ (\ mathbb {N} \ times \ mathbb {N} \), квадрат натуральных чисел, упорядоченный лексикографически
(3)	линейных заказов	\ (\ mathbf {A} \ times \ mathbb {Q} \) упорядочен антилексикографически, где \ (\ mathbf {A} \) — это \ (\ mathbb {N} ^ \ mathbb {N} \) в обычном порядке
(4)	абелевых групп	\ ((\ mathbb {Q} + \ mathbf {A}) \ times \ mathbb {Q} \)

В теории моделей можно принимать значения в любом полном БА, а не в двухэлементный БА.Эта теория булевозначных моделей была развита примерно в 1950–1970 годах, но с тех пор почти не работал. Но частный случай, булевозначные модели для теории множеств, очень авангард современных исследований в области теории множеств. Это фактически формирует эквивалентный способ взглянуть на форсирующую конструкцию Коэна, и имеет ряд технических преимуществ и недостатков. Философски это кажется более удовлетворительным, чем концепция принуждения. Мы описываем это случай теории множеств здесь; тогда станет очевидно, почему только завершать Рассматриваются БА.Пусть B — полная БА. Сначала мы определяем Булевозначный универсум \ (V (B) \). Обычный теоретико-множественный универсум можно отождествить с \ (V \) (2), где 2 — двухэлементная БА. Определение дается трансфинитной рекурсией, где \ (\ alpha, \ beta \) — порядковые числа, а \ (\ lambda \) — предельный порядковый номер:

\ [\ begin {align *} V (B, 0) & = \ varnothing \\ V (B, \ alpha + 1) & = \ {f: \ dom (f) \ subset V (B, \ alpha) \ text {and} \ range (f) \ subset B \} \\ V (B, \ lambda) & = \ bigcup _ {\ beta \ lt \ lambda} V (B, \ beta).\ конец {выравнивание *} \]

где \ (\ dom (f) \) — область определения функции \ (f \), а \ (\ range (f) \) — диапазон функции \ (f \). \ (B \) -значная вселенная является собственно класс \ (V (B) \), который является объединением всех этих \ (V \) s. Следующий определяется довольно сложной трансфинитной рекурсией над обоснованно устанавливает значение теоретико-множественной формулы с элементами булевозначной вселенной, присвоенной его свободным переменным:

\ [\ begin {align *} \ val {x \ in y} & = \ sum_ {t \ in \ dom (y)} \ val {x = t} \ cdot y (t) \\ \ val {x \ substeq y} & = \ prod_ {t \ in \ dom (x)} -x (t) + \ val {t \ in y} \\ \ val {x = y} & = \ val {x \ substeq y} \ cdot \ val {y \ substeq x} \\ \ val {\ neg \ phi} & = — \ val {\ phi} \\ \ val {\ phi \ vee \ psi} & = \ val {\ phi} + \ val {\ psi} \\ \ val {\ exists x \ phi (x)} & = \ sum_ {a \ in V (B)} \ val {\ phi (a)}.\ конец {выравнивание *} \]

Определение логической алгебры

Что такое булева алгебра?

Булева алгебра — это раздел математики, который занимается операциями с логическими значениями и включает двоичные переменные. Булева алгебра берет свое начало в книге математика Джорджа Буля 1854 года.

Отличительной чертой булевой алгебры является то, что она занимается только изучением двоичных переменных. Чаще всего логические переменные представлены с возможными значениями 1 («истина») или 0 («ложь»).Переменные также могут иметь более сложные интерпретации, например, в теории множеств. Булева алгебра также известна как бинарная алгебра.

Ключевые выводы

• Булева алгебра — это раздел математики, который имеет дело с операциями над логическими значениями с двоичными переменными.
• Логические переменные представлены в виде двоичных чисел для представления истин: 1 = истина и 0 = ложь.
• Элементарная алгебра имеет дело с числовыми операциями, тогда как булева алгебра имеет дело с логистическими операциями.
• Булева алгебра использует соединение, дизъюнкцию и отрицание, в отличие от сложения, вычитания, умножения и деления.
• Основное современное использование булевой алгебры — это языки компьютерного программирования.
• В финансах в моделях ценообразования биномиальных опционов используется булева алгебра, которая помогает определить, когда опцион должен быть исполнен.

Понимание логической алгебры

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

Понятие булевой алгебры было впервые введено Джорджем Булем в его книге Математический анализ логики и далее расширено в его книге Исследование законов мысли . Поскольку ее концепция была подробно описана, булевская алгебра в основном использовалась в языках программирования.Его математические цели используются в теории множеств и статистике.

Булева алгебра в финансах

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

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

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

Булевы алгебры — обзор

ТЕОРЕМА 1.6

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

Доказательство: пусть B булева алгебра. По теореме Стоуна о представлении (Si63, с. 353), B изоморфна совокупности всех открыто-замкнутых подмножеств полностью несвязного компактного хаусдорфового пространства X. Пусть B — открыто-замкнутое множество, соответствующее элементу b в B. Для любого Бэра мера (Ro68, стр.302, He58, стр.215) μ на X, мы можем определить состояние β _μ на B с помощью β _μ (b) = μ (B). Согласно теореме 3.1, стр.216, He58, присвоение μ ∼> β _μ устанавливает взаимно однозначное соответствие между (счетно-аддитивными) знаковыми мерами Бэра на X и (конечно-аддитивными) знаковыми состояниями на B; это соответствие является изоморфизмом векторного пространства.(f) = ∫fdμ для всех f ∈ C (X). (Любое f в C (X) измеримо по Бэру по определению; Ro68, pp.301-302.)

Пусть s _X будет множеством всех вероятностных мер Бэра на X, то есть s _X будет множество всех неотрицательных мер Бэра μ на X, таких что μ (X) = 1. (Ясно, что для любой ненулевой неотрицательной меры μ, μ / μ (X) находится в s _X , поэтому s _X является основание положительного конуса в м. ) Соответствие μ ∼> β _μ является аффинным изоморфизмом s _X на множество s _B всех (неотрицательных, нормированных) состояний на B.(е) = supf∈C (X) || f || = 1∫fdμ = | μ | (X).

По теореме Банаха-Алаоглу (Ro68, стр.202) замкнутый единичный шар м ₀ = {μ∈ | || μ || ≤1} является слабым * (т. е. w ( m , C (X))) компактным. Для положительных мер μ, μ = | μ | поэтому s _X содержится в слабом * компактном множестве m _0.

Теперь характеристическая функция χ _X находится в C (X), поэтому χ _X можно рассматривать как слабую * непрерывную линейную функционал на C (X) * (Si63, P.231ff), откуда на м , на χ _X (μ) = μ (X).Поскольку χ _X является слабым * непрерывным, м ₁ = χ _X ^-1 (1) является слабым * замкнутым множеством. Очевидно, s _X ⊆ м _1.

Мы только что видели, что s _X ⊆ м ₀ ∩ м ₁ ; мы утверждаем, что на самом деле s _X = м ₀ ∩ м ₁ . Предположим, что μ ∈ м ₀ ∩ м ₁ .Поскольку μ (X) = 1 по определению m ₁ , мы должны только показать, что μ неотрицательна. Предположим, что нет. Тогда существуют бэровское множество B и вещественное число x <0 с μ (B) = x. Поскольку μ (X) = 1. μ (X \ B) = 1 - x. Теперь для любого бэровского множества D | μ (D) | ≤ | μ | (D) (Ro68, проблема 28, с. 237), поэтому

|| μ || = | μ | (X) = | μ | (B) + | μ | (x \ B) ≥ | μ (B) | + | μ (x \ B) | = | x | + | 1 − x |> 1.

Это противоречит тому факту, что μ ∈ m ₀ , и мы заключаем, что μ должно быть неотрицательным.

Так как м ₀ слабый * компактный и м ₁ слабый * закрытый, s _X = м ₀ ∩ м ₁ слабый * компактный.Ясно, что s _X выпуклый. По теореме Крейна-Миллмана (Ro68, стр.207) каждый элемент s _X является слабым * пределом выпуклых комбинаций крайних точек. Теперь предположим, что β — элемент s _B , и пусть μ — соответствующая мера на X. Тогда μ — слабый * предел сети (μ _n ) мер в s _X , где μ _n можно записать как выпуклую комбинацию μn = Σi∈Intivi крайних точек v _i s _X .Поскольку отображение μ ∼> β _μ является аффинным изоморфизмом, δ _i = β v _i является чистым и, следовательно, по лемме 1.5 δ _i не имеет дисперсии. Кроме того, βn = βμn = Σi∈Intiδi. представляет собой выпуклую комбинацию бездисперсионных состояний. Осталось показать, что для любого b из B β _n (b) → β (b). По определению слабой * сходимости μ _n → μ тогда и только тогда, когда для любого f ∈ C (X) выполняется ∫fdμ _n → ∫fdμ. Если b ∈ B и B соответствующее открыто-открытое подмножество X, то χ _B ∈ C (X) и имеем

βn (b) = μn (B) = ∫χBdμ = μ (B) = β (b ).

Истоки булевой алгебры в логике классов: Джордж Буль, Джон Венн и К. С. Пирс

Введение

Рис. 1. Слева направо: пионеры булевой алгебры Джордж Буль, Джон Венн и Чарльз Сандерс Пирс (Источник: Архив истории математики MacTutor)

Практически в один и тот же день 1847 года видными британскими математиками были опубликованы две новые крупные работы по логике: Formal Logic [3] Августа Де Моргана (1806–1871) и The Mathematical Analysis of Logic [1] Джордж Буль (1815–1864).Оба автора стремились расширить границы традиционной логики, разработав общий метод представления и манипулирования логически обоснованными выводами или, как объяснил Де Морган в письме Булю 1847 года, разработать «механические способы выполнения переходов с обозначениями, которые представляют наши головная работа »[7, с. 25]. В отличие от метода, предложенного Де Морганом, подход Буля сделал значительный шаг в явном принятии алгебраических методов для этой цели. Как позже провозгласил сам Де Морган: «МистерОбобщение форм логики Буля, безусловно, является самым смелым и оригинальным. . . »(Цитируется в [4, с. 174]).

Несмотря на то, что он был явно алгебраическим по своей природе, смелый и оригинальный подход Буля привел к очень странной новой системе алгебры. Например, среди законов, которые выполняются в системе, можно найти как стандартный закон дистрибутивности умножения над сложением, \ (x (y + z) = xy + xz \), так и необычно выглядящий закон двойственной дистрибутивности сложения над умножением, \ (х + уz = (х + у) (х + z).\) В своей зрелой работе по логике, An Investigation of the Laws of Thought [2], опубликованной в 1854 году, Буль далее исследовал способы, которыми законы этой алгебраической системы похожи и отличаются от законов стандартной алгебры. как причины, по которым он удовлетворяет этим различным законам. По иронии судьбы, законов мысли изначально не был хорошо принят; Буль и его друг, которые понесли расходы на его первоначальную печать, вероятно, не возместили свои затраты. Однако абстрактная структура булевой алгебры, которая в конечном итоге действительно возникла из работ Буля, стала не только важной областью изучения математики, но и мощным инструментом в разработке и изучении электронных схем и компьютерной архитектуры.

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

• проект, который исследует применение логической алгебры к проблеме проектирования схем, представленный в статье Convergence Applications of Boolean Algebra: Claude Shannon and Circuit Design;
• проект, который исследует структуру булевой алгебры как абстрактную аксиоматизированную структуру, представлен в статье Convergence , Boolean Algebra as an Abstract Structure: Edward V.Хантингтон и аксиоматизация;
• настоящий проект «Истоки булевой алгебры в логике классов: Джордж Буль, Джон Венн и К.С. Пирс», который развивает элементарную теорию множеств на основе отрывков из оригинальных источников из собственных работ Буля и двух первых математиков, внесших изменения в Подход Буля к логике.

Все три проекта являются частью более крупной коллекции, опубликованной в Convergence, , и весь вводный курс дискретной математики можно преподавать на основе выбранных проектов в этой коллекции.Дополнительные проекты см. В разделе «Основные исторические источники в классе: дискретная математика и информатика».

Наш проект «Происхождение булевой алгебры в логике классов: Джордж Буль, Джон Венн и К. С. Пирс» готов для студентов, а исходный текст Latex также доступен для преподавателей, которые могут пожелать изменить проект для студентов. Подробные «Примечания для инструктора», представленные далее, также прилагаются к самому проекту.

Рисунок 2. Нижняя треть витража, посвященного Джорджу Буля, в соборе Линкольна в Линкольне, Англия, на месте рождения Буля (Источник: Wikimedia Commons)

На заметку инструктору

Проект «Истоки булевой алгебры в логике классов: Джордж Буль, Джон Венн и К. С. Пирс» предназначен для вводного или промежуточного курса дискретной или конечной математики, который включает изучение элементарной теории множеств. Без явного введения современных обозначений для операций над множествами, проект развивает современное понимание этих операций и их основных свойств в контексте ранних попыток разработать символическую алгебру для логики.Хотя проект фокусируется на том, что теперь будет называться «вводной теорией множеств», он также закладывает основу для более абстрактного обсуждения логической алгебры как дискретной аксиоматизированной структуры. Соответственно, этот проект можно также использовать как введение в один или оба сопутствующих проекта, описанных ниже, в любом курсе, который рассматривает логическую алгебру с точки зрения математики или информатики. За пределами определенного уровня математической зрелости, соизмеримого с типичным опытом работы в Calculus I, для этого проекта нет никаких предварительных условий.Сильные студенты на уровне подготовки к исчислению также могут завершить более ранние разделы этого проекта.

Рисунок 3. Джон Венн в несколько более старшем возрасте, чем на рисунке 1 (Источник: Convergence Portrait Gallery)

Начиная с работ Буля об использовании символической алгебры для представления логических классов в его Исследование законов мышления [2] (раздел 2), этот проект вводит операции логического сложения (т.е., объединение множеств), логического умножения (т. е. пересечения множеств) и логической разницы (т. е. разницы множеств) и исследует определенные ограничения, наложенные на их использование логическим значением, которые с тех пор были сняты. Также вводятся основные законы, управляющие этими операциями, поскольку они были развиты и обоснованы Булем; эти обоснования частично основывались на его определениях операций и частично на аналогии его символов с символами «стандартной алгебры». Затем проект следует за уточнениями системы Буля, сделанными Джоном Венном в его Symbolic Logic [8] ( Раздел 3) и Чарльз Сандерс Пирс в его «Об улучшении логического исчисления Буля» [5] (Раздел 4), причем уровень абстракции в этих разделах неуклонно повышается.Проект завершается (раздел 5) кратким изложением того, как булевская « Алгебра логики » соотносится с теорией элементарных множеств, как она обычно представляется сегодня, и обсуждает, как элементарная теория множеств (рассматриваемая как алгебраическая структура) служит конкретным примером теории множеств. логическая алгебра. Стандартные (для студентов) обозначения и свойства для операций теории множеств, используемые сегодня, включены и сравниваются со стандартными (для студентов) обозначениями и аксиомами для булевой алгебры в этом разделе. Вопросы, связанные с использованием языка и операциями над наборами, которые создают трудности для многих студентов, но которые игнорируются или не признаются современными авторами учебников, также подробно рассматриваются в трудах Буля и Венна (разделы 3 и 4) и далее исследуются в рамках проекта. вопросы в этих разделах.

Рисунок 4. Чарльз Сандерс Пирс в несколько более старшем возрасте, чем на Рисунке 1 (Источник: Convergence Portrait Gallery)

Следуя усовершенствованиям, внесенным в символьную алгебру Буля в руках Венна и Пирса, этот проект дает студентам возможность воочию увидеть, как происходит процесс разработки и совершенствования математической системы, как математики делают и объясняют свой выбор по ходу дела, и как стандарты строгости в этом отношении менялись с течением времени.Таким образом, помимо разработки свойств теории множеств как конкретного конкретного примера булевой алгебры, проект может исследовать множество математических тем, включая понятие обратной операции, концепцию двойственности, вопросы, связанные с математической математикой. обозначения и стандарты строгости и доказательства. Следуя одной или нескольким из этих тем в рамках проекта, преподаватели получают значительную свободу действий в адаптации проекта к своим целям для конкретной группы студентов. Инструктору рекомендуется заранее проработать все упражнения, чтобы определить, какие из них он может пропустить.Например, раздел 4 можно было бы полностью опустить, если бы преподаватель решил не исследовать доказательства элементарных свойств множества с более абстрактной точки зрения, принятой Пирсом. Для завершения проекта требуется примерно две недели.

Два сопутствующих проекта по булевой алгебре также доступны как продолжение этого вводного проекта, один или оба из которых также могут использоваться независимо от проекта Буля-Венна-Пирса. Кроме того, любой из двух сопутствующих проектов можно использовать как предварительный или как продолжение другого сопутствующего проекта.

Сопутствующий проект «Булева алгебра как абстрактная структура: Эдвард В. Хантингтон и аксиоматизация» исследует раннюю аксиоматизацию булевой алгебры как абстрактной структуры на основе прочтений из статьи Хантингтона 1904 года «Наборы независимых постулатов для алгебры логики». В дополнение к введению теперь стандартных аксиом для структуры логической алгебры, проект иллюстрирует, как использовать эти постулаты для доказательства некоторых основных свойств булевых алгебр. Конкретные вопросы проекта также дают студентам возможность попрактиковаться в использовании символических обозначений и побуждают их анализировать логическую структуру количественных утверждений.В проекте также исследуется использование Хантингтоном двузначной булевой алгебры на \ (K = \ {0, 1 \} \), которую впервые изучил Джордж Буль в его работе над логикой классов, в качестве модели для установления независимости и непротиворечивость одного из его наборов постулатов. В последнем разделе проекта обсуждаются современные (студенческие) обозначения и аксиомы для булевых алгебр, а также предлагаются несколько практических упражнений для закрепления идей, разработанных в предыдущих разделах.

Сопутствующий проект «Применение логической алгебры к проектированию схем: Клод Шеннон», основанный на новаторской статье Шеннона «Символьный анализ реле и коммутационных схем» [6], начинается с краткого обзора двух основных исторических предшественников работы Шеннона: Оригинальная работа Буля по логике и работа Хантингтона по аксиоматизации.Затем проект разрабатывает стандартные свойства логической алгебры в конкретном контексте схем и предоставляет студентам практику использования этих свойств для упрощения логических выражений. Двузначная логическая алгебра на \ (K = \ {0, 1 \} \) снова играет центральную роль в этой работе. Проект завершается исследованием концепции «дизъюнктивной нормальной формы» для логических выражений, опять же в контексте схем.

Реализация со студентами любого из этих проектов может быть достигнута посредством индивидуально заданной работы, работы в малых группах и / или обсуждения в классе; Комбинация этих учебных стратегий рекомендуется для того, чтобы воспользоваться разнообразием вопросов, включенных в проект.

Загрузите проект «Происхождение булевой алгебры в логике классов: Джордж Буль, Джон Венн и К. С. Пирс» в виде файла pdf, готового для использования в классе.

Загрузите изменяемый исходный файл Latex для этого проекта.

Дополнительные проекты см. В разделе «Основные исторические источники в классе: дискретная математика и информатика».

Библиография

[1] Бул, Г., Математический анализ логики, MacMillan, Barclay & MacMillan, Cambridge, 1847.Перепечатка Open Court, La Salle, 1952 г.

[2] Бул, Г., Исследование законов мысли, на которых основаны математические теории логики и вероятностей, Уолтон и Маберли, Лондон, 1854 г. Перепечатка Dover Publications, Нью-Йорк, 1958.

[3] Де Морган, А., Формальная логика: или, Исчисление вывода, необходимое и вероятное, Тейлор и Уолтон, Лондон, 1847.

[4] Меррилл Д., Август де Морган и логика отношений, Клувер, Дордрехт, 1990.

[5] Пирс К. С., Об улучшении логического исчисления Буля, Proceedings of the American Academy of Arts and Sciences, 7 (1867), 250-261. Перепечатано в Сборниках статей Чарльза Сандерса Пирса, Том III: Точная логика, К. Хартсхорн и П. Вайс (редакторы), Oxford University Press, Лондон, 1967, 3-15.

[6] Шеннон, К. Э., Символьный анализ реле и коммутационных цепей, Американский институт инженеров-электриков. Транзакции, 57 (1938), 713-723.Перепечатано в Claude Elwood Shannon: Collected Papers, N. J. A. Sloane и A. D. Wyner (редакторы), IEEE Press, New York, 1993, 471-495.

[7] Смит, Г. К., Переписка Буля-ДеМоргана, 1842-1864, Clarendon Press, Oxford, 1982.

[8] Venn, J., Symbolic Logic, MacMillan, London, 1894. Перепечатка Chelsea, Bronx, 1971.

Благодарность

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

Гивант, Стивен, Халмос, Пол: 9780387402932: Amazon.com: Книги

Из отзывов:

«Это отличный и столь необходимый всесторонний учебник для бакалавров по булевым алгебрам. Он содержит полное и подробное введение в фундаментальную теорию булевых алгебр.Книга, предназначенная для студентов-математиков, является, по словам первого автора, «существенно переработанной версией« Лекций по булевым алгебрам »Пола Халмоса. Он, безусловно, достигает заявленной цели — «провести средний курс между элементарными арифметическими аспектами предмета» и «более глубокими математическими аспектами теории» булевых алгебр ».

…

«Книга написана для студентов, уже имеющих навыки доказательства теорем. Однако, поскольку доказательства настолько подробны и ясны, он может хорошо работать в качестве текста для второго или даже первого курса, включающего существенные доказательства.По этой причине она также станет отличной книгой для студента, занимающегося самостоятельным обучением. Текст несколько неформален в том смысле, что иногда доказательства появляются в прозе, а не под заголовком «Доказательство», но всегда ясно, когда это делается. Хотя книга начинается с введения в булевы кольца, знание теории групп или колец не является необходимым условием для использования книги ».

…

«Таким образом,« Введение в булевы алгебры »- это жемчужина текста, заполняющая давний пробел в литературе для студентов.Он сочетает в себе лучшее из обоих миров, строго охватывая все фундаментальные теоремы и темы булевой алгебры, и в то же время он легко читается, детализирован и хорошо подготовлен для студентов бакалавриата. Это мой самый рекомендуемый текст для студентов, изучающих булевы алгебры ».

(Наташа Добринен. The Bulletin of Symbolic Logic , Vol. 16 (2), June 2010: 281-282)

«Введение в булевы алгебры…» предназначена для продвинутых студентов.Гивант (Колледж Миллса) и Халмос… используя ясную и точную прозу, построили абстрактную теорию булевых колец и алгебр с нуля. … В книге разработан необходимый топологический материал и включено приложение по теории множеств. … Включает обширную библиографию и более 800 упражнений на всех уровнях сложности. Подведение итогов: настоятельно рекомендуется. Студенты старших курсов, аспиранты, исследователи и преподаватели ». (С. Дж. Колли, Choice , том 46 (10), июнь 2009 г.)

« Авторы написали книгу для продвинутых студентов и начинающих аспирантов.… Авторы начинают с определения булевых колец и булевых алгебр, приводят примеры и основные факты и сравнивают оба понятия. … Есть большое количество упражнений разной степени сложности. Советы по решению более сложных проблем приведены в приложении. Инструкторам доступно подробное руководство по решениям для всех упражнений. Книга может служить основой для множества курсов ». (Мартин Виз, Zentralblatt MATH , том 1168, 2009 г.)

В смелом и освежающем неформальном стиле этот захватывающий текст представляет собой промежуточный курс между элементарными текстами, подчеркивающими связь с философией, логикой и проектированием электронных схем, и глубокими трактатами, предназначенными для продвинутых аспирантов и профессиональных математиков.Он написан для читателей, которые изучали математику в колледже не менее двух лет. Благодаря тщательно продуманной прозе, ясным объяснениям и проницательности, он направляет студентов к некоторым из более глубоких результатов булевой алгебры — и, в частности, к важным взаимосвязям с топологией, — не предполагая наличия знаний в алгебре, топологии и множестве теория. Части этих предметов, необходимые для понимания материала, развиваются в самом тексте.

Основные моменты книги включают теорему о нормальной форме; теорема о продолжении гомоморфизма; теорема об изоморфизме для счетных безатомных булевых алгебр; теорема о максимальном идеале; знаменитая теорема Стоуна о представлении; теоремы существования и единственности канонических расширений и пополнений; Теорема Тарского об изоморфизме факторов для счетно полных булевых алгебр и соответствующие контрпримеры Ханфа; и обширное рассмотрение алгебро-топологической двойственности, включая двойственность между идеалами и открытыми множествами, гомоморфизмами и непрерывными функциями, подалгебрами и факторпространствами, а также прямыми произведениями и компактификациями Стоуна-Чеха.

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

булевых алгебр | Джоэл Дэвид Хэмкинс

Это отрывок из моей незавершенной книги по разным элементарным темам логики, из главы, посвященной теории моделей. Я считаю, что булевозначные модели должны быть подняты до статуса стандартной основной темы элементарной теории моделей, примыкающей к сверхмощной конструкции. Теория булевозначных моделей прекрасна и доступна, как обобщающая, так и объясняющая сверхмощный метод, а также затрагивая более глубокие философские вопросы, касающиеся многозначной истины.

Давайте расширим нашу знакомую концепцию модели с классической логики предикатов до сравнительно фантастической области многозначной логики предикатов. Мы ищем концепцию модели с многозначной истинностью, с областью индивидов определенного типа и интерпретациями отношений, функций и констант на языке первого порядка, но в которой истины модели не обязательно являются черными и белые, но демонстрируют свои истинностные ценности в данной многозначной логике. Остановимся особенно на случае булевозначных моделей, используя полную булеву алгебру $ \ newcommand \ B {\ mathbb {B}} \ B $, поскольку этот случай был особенно хорошо разработан и успешен; теоретико-множественный метод принуждения, например, сводится к использованию $ \ B $ -значных моделей теории множеств с тщательно подобранными полными булевыми алгебрами $ \ B $ и был впечатляюще использован для установления широкого явления теоретико-множественной независимости, показывающего что многочисленные теоретико-множественные принципы, такие как аксиома выбора и гипотеза континуума, не зависят от других аксиом теории множеств.

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

Определение булевозначных моделей

В предыдущем разделе мы определили, что значит быть моделью в классической логике предикатов первого порядка — один определяет область модели, набор индивидов, которые будут составлять универсум модели, по которому будут располагаться все кванторы, а затем предоставляет интерпретации в этой области для каждого символа отношения, функционального символа и постоянного символа на языке.Например, для каждого символа отношения $ R $ и любого подходящего кортежа индивидов $ a, b $ из домена указывается, будет ли $ R (a, b) $ удерживаться в модели или нет.

Основная идея для определения того, что значит быть моделью в многозначной логике предикатов, состоит в том, чтобы заменить эти классические атомарные истины «да или нет» на многозначные атомарные утверждения истинности. В частности, для любой булевой алгебры $ \ B $ $ \ B $ -значная модель $ \ mathcal {M} $ на языке $ \ mathcal {L} $ состоит из области $ M $, элементы которой называются называет и присвоение $ \ B $ -значных значений истинности для всех простых атомарных формул с использованием параметров из этой области: $ \ newcommand \ boolval [1] {[\! [# 1] \!]} $ \ begin {eqnarray *}
% \ nonumber% Удалить нумерацию (перед каждым уравнением)
s = t & \ mapsto & \ boolval {s = t} \\
R (s_0, \ ldots, s_n) & \ mapsto & \ boolval {R ( s_0, \ ldots, s_n)} \\
y = f (s_0, \ ldots, s_n) & \ mapsto & \ boolval {y = f (s_0, \ ldots, s_n)}
\ end {eqnarray *}
Двойной -выражения в квадратных скобках здесь $ \ boolval {\ varphi} $ обозначают элемент булевой алгебры $ \ B $ — кто-то думает о $ \ boolval {\ varphi} $ как о $ \ B $ -истинном значении $ \ varphi $ в модель, и модель определяется указанием этих значений для простых атомарных формул.

Мы будем настаивать в любой булевозначной модели, чтобы атомарные значения истинности подчинялись законам равенства:
$$ \ begin {array} {rcl}
\ boolval {s = s} & = & 1 \\
\ boolval { s = t} & = & \ boolval {t = s} \\
\ boolval {s = t} \ wedge \ boolval {t = u} & \ leq & \ boolval {s = u} \\
\ bigwedge_ {i $$ \ begin {array} {rcl}
\ bigwedge_ {i \ bigvee_ {t \ in M} \ boolval {t = f (\ vec s)} & = & 1 \\
\ boolval {t_0 = f (\ vec s)} \ wedge \ boolval {t_1 = f (\ vec s)} & \ leq & \ boolval {t_0 = t_1}.\\
\ end {array} $$
Эти требования утверждают, соответственно, в контексте с логическими значениями, что аксиома равенства выполняется для приложения функции, что функция принимает некоторое значение и что функция принимает не более одного значения. Фактически, булевозначная модель обработки функций рассматривает их как определенные в их отношениях графа, и эти аксиомы функциональности гарантируют, что отношение имеет характеристики, которые можно было бы ожидать от такого отношения графа.

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

Булевозначное равенство

Природа равенства в булевозначной среде предлагает интересный отход от обычной классической трактовки, который стоит подробно обсудить. А именно, в классической логике предикатов с равенством различные элементы предметной области рассматриваются для представления различных индивидов в модели — утверждение $ a = b $ истинно в модели только тогда, когда $ a $ и $ b $ идентичны как элементы домен. Однако в настройке с логическим значением мы хотим ослабить это, чтобы позволить утверждениям о равенстве иметь промежуточное логическое значение.По этой причине отдельные элементы области не могут больше рассматриваться как представляющие определенно различных индивидов, поскольку утверждение равенства $ \ boolval {a = b} $ может иметь некоторую ненулевую или промежуточную степень истинности. Элементы домена булевозначной модели допускают некоторую нерешительность или неопределенность в отношении того, кем они являются и могут ли они быть идентичными. Вот почему мы думаем об элементах домена как о именах для отдельных лиц, а не как об отдельных лицах.Два разных имени могут иметь промежуточную истинностную возможность называть одного и того же или разных людей.

Расширение до логической истины

По определению, каждая $ \ B $ -значная модель предоставляет $ \ B $ -значные утверждения истинности для простых атомарных формул. Теперь мы распространяем эти булевозначные присвоения истинности на все утверждения языка с помощью следующей естественной рекурсии:
$$ \ begin {array} {rcl}
\ boolval {\ varphi \ wedge \ psi} & = & \ boolval {\ varphi} \ wedge \ boolval {\ psi} \\
\ boolval {\ neg \ varphi} & = & \ neg \ boolval {\ varphi} \\
\ boolval {\ exists x \, \ varphi (x, \ vec s)} & = & \ bigvee_ {t \ in M} \ boolval {\ varphi (t, \ vec s)}, \ text {если этот супремум существует в} \ B \\
\ end {array} $$
В правой части мы производим логические вычисления в каждом случае, используя операции булевой алгебры $ \ B $.В экзистенциальном случае супремум может охватывать бесконечный набор логических значений, если область определения модели бесконечна, и поэтому этот супремум не может быть реализован как элемент $ \ B $, если он не является полным. Именно поэтому обычно рассматриваются $ \ B $ -значные модели, особенно в случае полной булевой алгебры $ \ B $ — полнота $ \ B $ гарантирует, что этот супремум существует, и поэтому рекурсия имеет решение.

Читатель может проверить индукцией по $ \ varphi $, что общая аксиома равенства теперь имеет логическое значение единица.
$$ \ boolval {\ vec s = \ vec t \ wedge \ varphi (\ vec s) \ implies \ varphi (\ vec t)} = 1 $$
Булевозначная структура $ \ mathcal {M} $ — это полный если для каждой формулы $ \ varphi (x, \ vec x) $ в $ \ mathcal {L} $ и $ \ vec s $ в $ M $ существует некая $ t \ in M ​​$ такая, что $ \ boolval {\ exists x \, \ varphi (x, \ vec s)} = \ boolval {\ varphi (t, \ vec s)} $. То есть модель является полной, когда она достаточно богата именами, чтобы логическое значение каждого экзистенциального утверждения реализовывалось конкретным свидетелем, уменьшая бесконечную верхнюю грань в рекурсивном определении до единственного наибольшего элемента.

Простой пример

Для каждого натурального числа $ n \ geq 3 $ пусть $ C_n $ будет графом из $ n $ вершин, образующим $ n $ -цикл с отношением ребер $ x \ sim y $. Итак, у нас есть треугольник $ C_3 $, квадрат $ C_4 $, пятиугольник $ C_5 $ и так далее. Пусть $ \ B = P (\ set {n \ in \ newcommand \ N {\ mathbb {N}} \ N \ mid n \ geq 3}) $ будет набором степеней этих индексов, который образует полную булеву алгебру. Мы определяем модель $ \ B $ -значного графа $ \ mathcal {C} $ следующим образом. В качестве имен берем последовательности $ a = \ langle a_n \ rangle_ {n \ geq 3} $ с $ a_n \ in C_n $ для каждого $ n $.

Мы определяем отношения равенства и $ \ sim $ ребер для этих имен следующим образом:
\ begin {eqnarray *}
\ boolval {a = b} & = & \ set {n \ mid a_n = b_n} \\
\ boolval {a \ sim b} & = & \ set {n \ mid C_n \ newcommand \ удовлетворяет {\ models} \ удовлетворяет a_n \ sim b_n}.
\ end {eqnarray *}
Таким образом, два имени равны точно в той степени, в которой они имеют одинаковые координаты, а два имени связаны отношением ребер $ \ sim $ точно в той степени, в которой это верно для координат. Теперь легко проверить аксиомы равенства, поскольку $ a \ sim b $ истинно по крайней мере в той степени, в которой истинны $ a ‘\ sim b’ $, $ a = a ‘$ и $ b = b’ $. , поскольку если $ a_n = a’_n $, $ b_n = b’_n $ и $ a’_n \ sim b’_n $ в $ C_n $, то также $ a_n \ sim b_n $.Итак, это модель $ \ B $ -значного графа.

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

Позвольте мне утверждать, что неясно, является ли этот граф полным графом с каждой парой различных узлов, соединенных ребром.В конце концов, $ C_3 $ — это полный граф с тремя вершинами, и из приведенной ниже теоремы следует, что логическое значение утверждения $ \ forall x, y \, (x = y \ vee x \ sim y) $ содержит элемент $ 3 $ и, следовательно, это логическое значение не равно нулю. Между тем, утверждение о том, что граф не является полным, также получает ненулевое логическое значение, поскольку каждый $ C_n $, кроме $ C_3 $, имеет отдельные узлы без ребер между ними. В строгом смысле теоретико-графические истины $ \ mathcal {C} $ объединяют истины всех различных графов $ C_n $.

Отметим также, что по мере увеличения $ n $ узлы графов $ C_n $ становятся все более удаленными друг от друга. Исправьте любое имя $ \ langle a \ rangle_ {n \ geq 3} $ и выберите $ \ langle b \ rangle_ {n \ geq 3} $ так, чтобы расстояние между $ a_n $ и $ b_n $ в $ C_n $ не было ограничено. любой конкретной равномерной границей. Из $ \ mathcal {C} $ следует, что $ a $ и $ b $ не имеют определенного определенного конечного расстояния, и это можно рассматривать как то, в каком смысле $ \ mathcal {C} $ не связно.

Комбинация многих моделей

Давайте дополним предыдущий пример более общим анализом.Предположим, у нас есть семейство моделей $ \ set {M_i \ mid i \ in I} $ на общем языке $ \ mathcal {L} $. Пусть $ \ B = P (I) $ — множество степеней множества индексов $ I $, полная булева алгебра. Определим $ \ B $ -значную модель $ \ mathcal {M} $ следующим образом. Набор имен будет в точности произведением моделей $ M = \ prod_i M_i $, то есть $ I $ -наборок $ s = \ langle s_i \ mid i \ in I \ rangle $ с $ s_i \ в M_i $ для каждого $ i \ in I $, и простые атомарные значения истинности определяются следующим образом:
\ begin {eqnarray *}
\ boolval {s = t} & = & \ set {i \ in I \ mid s_i = t_i} \\
\ boolval {R (s, \ ldots, t)} & = & \ set {i \ in I \ mid M_i \ удовлетворяет R (s_i, \ dots, t_i)} \\
\ boolval {u = f (s, \ ldots, t)} & = & \ set {i \ in I \ mid M_i \ удовлетворяет u_i = f (s_i, \ dots, t_i)}.
\ end {eqnarray *}
Теперь можно доказать аксиомы равенства и функциональности, так что это $ \ B $ -значная модель.

Теорема. Булевозначная модель $ \ mathcal {M} $, описанная выше, является полной, и логическая истина может быть вычислена покоординатно:
$$ \ boolval {\ varphi (s, \ dots, t)} = \ set {i \ in I \ mid M_i \ удовлетворяет \ varphi (s_i, \ dots, t_i)}. $$

Доказательство. Мы доказываем это индукцией по $ \ varphi $ для утверждений, использующих только простые атомарные формулы, $ \ wedge $, $ \ neg $ и $ \ exists $.Простой атомарный случай — это часть того, что значит быть булевозначной моделью. Если теорема верна для $ \ varphi $, то она будет верна для $ \ neg \ varphi $, поскольку отрицание в $ \ B $ является дополнением в $ I $, а именно:
$$ \ boolval {\ neg \ varphi} = \ neg \ boolval {\ varphi} = I- \ set {i \ in I \ mid M_i \ удовлетворяет \ varphi} = \ set {i \ in I \ mid M_i \ удовлетворяет \ neg \ varphi}. $$
Если теорема верна для $ \ varphi $ и $ \ psi $, тогда она будет верна для $ \ varphi \ wedge \ psi $ следующим образом:
\ begin {eqnarray *}
\ boolval {\ varphi \ wedge \ psi} & = & \ boolval {\ varphi} \ wedge \ boolval {\ psi} \\
& = & \ set {i \ in I \ mid M_i \ соответствует \ varphi} \ cap \ set {i \ in I \ mid M_i \ удовлетворяет \ psi} \\
& = & \ set {i \ in I \ mid M_i \ удовлетворяет \ varphi \ wedge \ psi}.
\ end {eqnarray *}
Для кванторного случая $ \ exists x \, \ varphi (x, s, \ dots, t) $, выберите $ u_i \ in M_i $, для которого $ M_i \ удовлетворяет \ varphi (u_i, s_i, \ dots, t_i) $, если возможно. Отсюда следует, что
$$ \ set {i \ in I \ mid M_i \ удовлетворяет \ exists x \, \ varphi (x, s_i, \ dots, t_i)} = \ set {i \ in I \ mid M_i \ удовлетворяет \ varphi (u_i, s_i, \ dots, t_i)}, $$
и отсюда следует, что $ \ boolval {\ varphi (v, s, \ dots, t)} \ leq \ boolval {\ varphi (u, s , \ dots, t)} $, поскольку всякий раз, когда $ v_i $ преуспевает в качестве свидетеля, то же самое происходит и с $ u_i $. Следовательно, модель заполнена, и мы видим, что
\ begin {eqnarray *}
\ boolval {\ exists x \, \ varphi (x, s, \ dots, t)} & = & \ bigvee_ {v \ in M } \ boolval {\ varphi (v, s, \ dots, t)} \\
& = & \ boolval {\ varphi (u, s, \ dots, t)} \\
& = & \ set {i \ в I \ mid M_i \ удовлетворяет \ exists x \, \ varphi (x, s_i, \ dots, t_i)},
\ end {eqnarray *}
по желанию.$ \ Box $

Булевы сверхспособности

Каждую булевозначную модель можно преобразовать в классическую модель, двухзначную модель, с помощью простой факторной конструкции. Предположим, что $ \ mathcal {M} $ — $ \ B $ -значная модель некоторой булевой алгебры $ \ B $ и что $ \ mu \ newcommand \ of {\ substeq} \ of \ B $ — ультрафильтр на булевой алгебре. алгебра.

Определите отношение эквивалентности $ = _ \ mu $ на множестве имен с помощью
$$ a = _ \ mu b \ quad \ text {тогда и только тогда, когда} \ quad \ boolval {a = b} \ in \ mu.{\ mathcal {M} / \ mu} ([a] _ \ mu, \ ldots, [b] _ \ mu) \ quad \ text {тогда и только тогда, когда} \ quad \ boolval {R (a, \ dots, b)} \ in \ mu. $$
Для функциональных символов $ f $ определим
$$ [c] _ \ mu = f ([a] _ \ mu, \ dots, [b] _ \ mu) \ quad \ text {тогда и только тогда, когда} \ quad \ boolval {c = f (a, \ dots, b)} \ in \ mu. $$
Эти определения четко определены по модулю $ = _ \ mu $ именно потому, что свойства аксиомы равенства булевозначной модели $ \ mathcal {M} $. Например, если $ a = _ \ mu a ‘$, то $ \ boolval {a = a’} \ in \ mu $, но $ \ boolval {a = a ‘} \ wedge \ boolval {R (a)} \ leq \ boolval {R (a ‘)} $ по аксиоме равенства, и поэтому, если $ \ boolval {R (a)} $ находится в $ \ mu $, то так будет $ \ boolval {R (a’) } $.

Мы определили атомарную истину в фактор-структуре, ссылаясь на то, что значение истинности является $ \ mu $ -большим. Фактически, это сокращение будет продолжаться для всех утверждений истинности в фактор-структуре, что мы доказываем следующим образом.

Теорема. (теорема Чоша для булевых сверхстепеней)
Предположим, что $ \ mathcal {M} $ — полная $ \ B $ -значная модель для булевой алгебры $ \ B $, а $ \ mu \ of \ B $ — ультрафильтр . Тогда утверждение истинно в булевой фактор-структуре $ \ mathcal {M} / \ mu $ тогда и только тогда, когда логическое значение утверждения находится в $ \ mu $.
$$ \ mathcal {M} / \ mu \ удовлетворяет \ varphi ([a] _ \ mu, \ dots, [b] _ \ mu) \ quad \ text {тогда и только тогда, когда} \ quad \ boolval {\ varphi (a, \ dots, b)} \ in \ mu. $$

Доказательство. Докажем это индукцией по $ \ varphi $. Простой атомарный случай выполняется по определению фактор-структуры. Булевы связки $ \ wedge $, $ \ neg $ легко следуют из того, что $ \ mu $ является фильтром и что это ультрафильтр. Рассмотрим кванторный случай $ \ exists x \, \ varphi (a, \ dots, b, x) $, где по индукции теорема верна для самого $ \ varphi $.Если фактор-структура удовлетворяет экзистенциальному $ \ mathcal {M} / \ mu \, \ exists x \, \ varphi ([a], \ dots, [b], x) $, то существует имя $ c $ для которому удовлетворяет $ \ varphi ([a], \ dots, [b], [c]) $, и поэтому по индукции $ \ boolval {\ varphi (a, \ dots, b, c)} \ in \ mu $ , и в этом случае также $ \ boolval {\ exists x \, \ varphi (a, \ dots, b, x)} \ in \ mu $, поскольку последнее логическое значение не меньше первого. И наоборот, если $ \ boolval {\ exists x \, \ varphi (a, \ dots, b, x)} \ in \ mu $, то по полноте это экзистенциальное логическое значение реализуется некоторым именем $ c $, и поэтому $ \ boolval {\ varphi (a, \ dots, b, c)} \ in \ mu $, что по индукции означает, что фактор удовлетворяет $ \ varphi ([a], \ dots, [b], [c]) $ и, следовательно, также $ \ exists x \, \ varphi ([a], \ dots, [b], x) $ по желанию.$ \ Box $

Обратите внимание, как полнота использовалась в экзистенциальном случае индуктивного аргумента.

Булева алгебра

Булева алгебра Предыдущая: Сравнивая выразительную силу …

следующий: Второе доказательство компактности логики высказываний

Вверх: Дополнительные текстовые темы

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

, то мы имеем уравнения булевой алгебры .До 1900 года логическая алгебра на самом деле означала жонглирование уравнениями (и отрицательными уравнениями) для отражения правильных аргументов. В 1904 г. Хантингтон написал статью [1], в которой он рассмотрел Булевы алгебры как алгебраические структуры удовлетворяющие уравнениям, полученным из исчисления классов. Эта точка зрения стала доминирующей в 20-е годы прошлого века под влиянием М. Стоун и А. Тарский. Первоначально Стоун интересовался булевыми алгебрами, чтобы понять структуру колец функций. которые исследовались в функциональном анализе.Он написал две огромные статьи, одну об эквивалентности булевых алгебр и булевых колец, а другую — о двойственности между булевыми алгебрами и булевыми пространствами [= полностью несвязный компактный Хаусдорф пробелы]. Тарский изучал булевы алгебры, работая над абстрактным понятием «замыкание при дедуктивном следствии». В 1930-х годах Стоун доказал, что каждая булева алгебра изоморфна полю множеств и что уравнения, истинные для двухэлементной булевой алгебры, такие же, как уравнения, истинные для всех булевых алгебр; и эти уравнения были последствиями небольшой начальный набор определяющих уравнений.

Какое отношение имеет современный предмет булевой алгебры к логике высказываний? Не очень много. Булева алгебра сама по себе стала глубоким и увлекательным предметом, предлагающим гораздо больше, чем удобное обозначение анализировать простые цепочки рассуждений. Тем не менее на уровне эквивалентности и уравнений предметы логики высказываний, исчисления классов и булевых алгебр по существу одинаковы, как показано в следующей таблице:

Во второй половине 1800-х годов эти идентичности считались довольно захватывающими, и большинство из них были названы в честь выдающихся логиков — теперь только две приписываются ДеМоргану. до сих пор есть такое имя.

Можно принять тождества в третьем столбце как набор аксиом для булевой алгебры, но этот набор аксиом в некоторой степени избыточен. Хантингтона очень увлекала проблема поиска наборы аксиом для исчисления классов. Есть вариант набор аксиом, который он предложил (см. [2]), предложенный Гербертом Роббинсом в 1933 году, что только недавно было доказано определяют булевы алгебры (см. III.16 из LMCS ), а именно:

Поскольку эта проблема была такой сложной, можно поставить фундаментальный вопрос:

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

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

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

Как упоминалось в II.14.10 LMCS , аналогичный вопрос для пропозициональной логика оказалась неразрешимой. На поставленный выше вопрос МакНалти дал отрицательный ответ [3]. и Мурский [4].

E XERCISES

---

Каталожные номера

1

Э.В. Хантингтон, Наборы независимых постулатов для алгебры логики. Пер. АМС 5 (1904), 288-309.

2

Е.В. Хантингтон, Новые наборы независимых постулатов алгебры логики, с особым упором на Уайтхеда и Рассела Principia Mathematica. Пер. АМС 35 (1933), 274-304.

3

Г. Макналти, Проблема решения эквациональных базисов алгебр. Annals Math. Логика 11 (1976), 193-259.

4

В.Л. Мурский, Неразличимые свойства конечных систем тождественных отношений. Советская математика. Доклады 12 (1971), 183-186.