После окончания в 1946 году Второй мировой войны Клини в звании капитан-лейтенанта оставил службу и вернулся в Висконсинский университет. Ушёл на пенсию в 1979 г.

Помимо математической логики Клини увлекался альпинизмом, прекрасно разбирался в грибах, был искусным рассказчиком анекдотов. У него был громкий голос, так что всегда можно было узнать, не видя его, находится ли он в здании или нет [19].

Умер Стивен Коул Клини 25 января 1994 в Мэдисоне, штат Висконсин.

8.6 Эмиль Леон ПОСТ

11 февраля 1897 года в городе Августов в семье польских евреев Арнольда и Перл Пост родился Эмиль. А через 7 лет в поисках лучшей жизни семья Постов перебралась в Нью-Йорк. Вскоре из-за несчастного случая Эмилю пришлось пережить потерю руки, но он с этим научился справляться. Он успешно закончил спецшколу для особо одаренных детей Нью-Йорка и продолжил учёбу в колледже, который находился рядом со школой.

Мы сейчас знаем Поста как замечательного исследователя в области математической логики. Но во время учёбы в колледже он не проявлял особого интереса в этом направлении - он увлёкся астрономией. А на последнем курсе написал статью, в которой содержались важные идеи о преобразовании Лапласа. Но студент не решился опубликовать её, и она увидела свет лишь в 1930 году.

В 1917 году Эмиль получил степень бакалавра в области математики и поступил в Колумбийский университет, где в 1920 получил степень доктора философии. После получения докторской степени Э. Пост отправился в Принстонский университет, где поработал год, а затем вернулся в Колумбийский университет. Здесь его настигла болезнь маниакально-депрессивного характера, с которой он был вынужден бороться всю жизнь и которая, конечно, ограничила его возможные достижения. В 1924 году Пост отправился в Корнелл, но снова заболел. Он возобновил работу в 1927 году учителем средней школы в Нью-Йорке, а в 1932 году он начал работать в том же колледже, который когда-то закончил, и оставался там до конца жизни с перерывами из-за болезни.

В 1929 году он женился на Гертруде Сингер. Их дочь Филлис вспоминает, что все преподаватели колледжа располагались в одной комнате с большим столом в середине. И хотя учебная нагрузка отца была 16 контактных часов в неделю, он не мог продуктивно заниматься наукой в колледже, предпочитая работать дома. И Гертруда делала всё, чтобы муж мог всецело посвятить себя математике. Она ухаживала за малышкой Филлис, перепечатывала рукописи Эмиля, вела все домашние и финансовые дела.

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

После опроса Э.Пост вытаскивал 3-5 карточек и подробно объяснял по каждой новый материал. Студенты были бы рады, если бы он успевал рассказать по всем картам до звонка. Но звучал звонок, и на вопросы не оставалось времени. Удивительно, но эта, казалось бы, негибкая педагогическая методика была чрезвычайно успешна, и Пост была очень популярным преподавателем.

Один из его студентов 1943-го года вспоминал: «Эмиль Леон Пост был коренастым мужчиной, неизменно одетым в костюм-«тройку». Пустой рукав тщательно был заправлен в боковой карман. Лектор постоянно энергично ходил перед доской, говоря чётко и ясно. Внезапно он поворачивался, чтобы что-то написать мелом на доске. Это движение всегда приводило к тому, что рукав наконец освобождался из своего плена и (к облегчению аудитории) свободно болтался. Нам казалось, что эта свобода движения освобождала и его мышление во время лекции».

Умер Эмиль Леон Пост 21 апреля 1954 года. Его ранняя смерть в 57 лет была почти наверняка прямым следствием лечения маниакально-депрессивного заболевания электрическим током. После одного из ударов током у Поста случился сердечный приступ, который он не смог перенести [20].

Э.Л.Пост в результате почти 20-летней работы получил ряд фундаментальных результатов в математической логике, в частности, одно из наиболее употребительных определений понятий непротиворечивости и полноты формальных систем; доказательства функциональной полноты и дедуктивной полноты (в широком и узком смысле) исчисления высказываний. Он изучил системы многозначной логики с более чем тремя значениями истинности; дал одно из первых (независимое от А. М. Тьюринга) определений понятия алгоритма в терминах «абстрактной вычислительной машины» и формулировку основного тезиса теории алгоритмов о возможности описать любой конкретный алгоритм посредством этого определения. Э.Л. Пост доказал выразимость общерекурсивных функций и предикатов через примитивно рекурсивные, доказал так называемую теорему о нормальной форме; доказал алгоритмическую неразрешимость ряда проблем математической логики и алгебры и др.[21].

8.7 Иван Иванович ЖЕГАЛКИН

ЖЕГАЛКИН Иван Иванович родился в 1869 году в городе Мценске (Орловская губерния, Российская империя). Окончив Орловскую гимназию, он поступил в Московский университет на математическое отделение физико-математического факультета. В 1893 году окончил университет, получив дипломом 1-й степени. Иван Иванович поначалу служил в нескольких учреждениях: в Госбанке и на курсах при Обществе распространения коммерческого образования. В 1900 году Иван Иванович становится преподавателем реального училища К. Мазинга. Через два года он выдержал экзамен на магистрат и стал приват-доцентом университета.

В 1907 году защитил магистерскую диссертацию «Трансфинитные числа», которая была первой монографией по теории множеств в отечественной и мировой литературе. В 1911 году Иван Иванович вместе с другими преподавателями, несогласными с министром просвещения Л. А. Кассо. и проводимой им политики, покинул университет. Он начинает преподавать на Высших женских курсах, где с 1906 года временно исполнял обязанности декана факультета. Кроме того, Иван Иванович заведовал библиотекой и был членом Московского математического общества.

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

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

С 1930 года он возглавляет кафедру математического анализа физико-механического факультета МГУ, а в Московском областном пединституте заведует кафедрой математики. Иван Иванович был инициатором создания научного семинара по математической логике, который впоследствии (в 1959 году) был преобразован в кафедру математической логики. Доктор физико-математических наук (1935), заслуженный деятель науки РСФСР (1945) И.И. Жегалкин был награждён Орденом Трудового Красного Знамени [22].

Скончался великий математик в 1947 году. Его похоронили в Москве, на Ваганьковском кладбище

Заключение

Мы рассмотрели сравнительно небольшой раздел математической логики, представляющий теоретическое обоснование очень важному промышленному применению булевых функций. Благодаря критерию Э.Л.Поста можно определить, какие функции образуют функционально полную систему (ФПС), и принимать решение, какие элементы стоит изготавливать для того, чтобы из них можно было конструировать сколь угодно сложные дискретные управляющие устройства.

Вы узнали, что такое ФПС булевых функций и что такое замкнутый класс, какие функции образуют замкнутый класс, какова мощность того или иного замкнутого класса и какие замкнутые классы надо исследовать, чтобы опознать ФПС.

Хотелось бы надеяться, что Вам, уважаемый читатель, стали немного ближе и Джордж Буль, который уже в 12 лет самостоятельно изучил пять языков, и непонятый современниками Огастес де Морган, и умерший в бедности и забвении философ Чарльз Сандерс Пирс, и не публиковавший своих исследований Генри Морис Шеффер, и альпинист, громкоголосый любитель анекдотов Стефен Коул Клини, и страдающий от психической болезни однорукий Эмиль Леон Пост, и наш российский математик Иван Иванович Жегалкин, который не побоялся протестовать против политики тогдашнего министра просвещения.

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

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

Источники литертауры

1. Быкова С.В., Буркатовская Ю.Б. Булевы функции. Учебно-методическое пособие. Часть IV. - Томск: Томский госуниверситет, 2006. - 42 с.

2. Ахметова Н.А., Усманова З.М. Дискретная математика. Функции алгебры логики. Учебное пособие. - Уфа: УГАТУ, 2002. - 126 с.

3. Прилуцкий М.Х. Методическое пособие по курсу "Математические основы информатики" Часть 1. - Нижний Новгород: Нижегородский госуниверситет, 2000. - 81 с.

4. Киселёва Л.Г., Смирнова Т.Г. Функции алгебры логики в примерах и задачах: Учебно-методическое пособие. - Нижний Новгород: Нижегородский госуниверситет, 2008. - 57 с.

5. Яблонский С.В. Введение в дискретную математику. - М.: Наука, 1986. -384 с.

6. Марченков С.С. Булевы функции. - М.: ФИЗМАТЛИТ, 2002. - 68 с.

7. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике : Учеб. пособие. - 3-е изд., перераб. - М.: ФИЗМАТЛИТ, 2005. - 416 с.

8. Гиндикин С.Г. Алгебра логики в задачах. - М.: ФИЗМАТЛИТ, 1972. - 288 с.

9. Яблонский С.В., Гаврилов Г.П., Кудрявцев В.Б. Функции алгебры логики и классы Поста. - М., Наука, 1966 - 120 с.

10. Новиков П.С. Элементы математической логики. М.: ФИЗМАТГИЗ, 1959. - 400 с.

11. Клини С.К. Введение в метаматематику, пер. с англ., М.: Иностр. лит., 1957

12. Большая советская энциклопедия [Электронный ресурс]. Режим доступа: http://dic.academic.ru/dic.nsf/bse/122206/ ПОЛНОТА

13. Философская энциклопедия. В 5 томах. - М.: Советская энциклопедия, под ред. Ф.В. Константинова. 1960-1970.

14. Википедия. [Электронный ресурс] Режим доступа:

http://ru.wikipedia.org/wiki/Буль,_Джордж

15. Энциклопедический словарь. [Электронный ресурс] Режим доступа: http://dic.academic.ru/dic.nsf/es/10266/ Буль

16. Попов Ю.П. Элементы истории и теории логики. [Электронный ресурс] Режим доступа:

http: //vpn.int.ru/index.php?name=Biography&op=page&pid=791.

17. Энциклопедический словарь, 2009 [Электронный ресурс] Режим доступа: http://dic.academic.ru/dic.nsf/es/44076/ Пирс.

18. An American logician (Mathematician). WorldTechForum. Henry Maurice Sheffer, [Электронный ресурс] Режим доступа: http://worldtechforum.blogspot.ru/2012/11/henry-maurice-sheffer-american-logician.html

19. J J O'Connor and E F Robertson. Stephen Cole Kleene. MacTutor History of Mathematics. [Электронный ресурс] Режим доступа:

http://www-history.mcs.st-andrews.ac.uk/Biographies/Kleene.html

20. J J O'Connor and E F Robertson. Stephen Cole Kleene. MacTutor History of Mathematics. [Электронный ресурс] Режим доступа:

http://www-history.mcs.st-andrews.ac.uk/Biographies/ Post.html

21. Российские универсальные энциклопедии Брокгауз-Ефрон и Большая Советская Энциклопедия, объединенный словник. [Электронный ресурс] Режим доступа:

http://gatchina3000.ru/great-soviet-encyclopedia/bse/091/869.htm

22. Большая биографическая энциклопедия,2009. [Электронный ресурс] Режим доступа:

http://dic.academic.ru/dic.nsf/enc_biography/138319/ ЖЕГАЛКИН

Пртложение 1. ЭЛЕМЕНТАРНЫЕ БУЛЕВЫ ФУНКЦИИ ОПРЕДЕЛЕНИЕ ТАБЛИЦЕЙ ИСТИНОСТИ

НАЗВАНИЯ И ОБОЗНАЧЕНИЯ

f₀ = 0 - константа 0.

f₁₅ =1 - константа 1.

f₃(x) = x - переменная x (тождественная функция).

f₅(y) = y - переменная y (тождественная функция).

f₁₂(x) = , x, ¬x - отрицание x, инверсия x;

читается « не x», « неверно, что x ».

f₁₀(y) = , y, ¬y - отрицание y, инверсия y ;

читается « не y», « неверно, что y».

f₁(x, y) = x&y, хy, xy - конъюнкция, логическое умножение;

читается « х и y ».

f₇(x, y) = xy - дизъюнкция, логическое сложение;

читается « х или y ».

f₆(x, y) = xy - сложение по модулю два,

дизъюнкция с исключением;

читается « х плюс y».

f₁₃(x, y) = x y - импликация, логическое следование;

читается « х импликация y », « х влечёт y».

«если x, то y».

f₉(x, y) = xy , x~ y - эквиваленция, эквивалентность;

читается «х эквивалентно y »;

f₂(x, y) = xy = (xy) - антиимпликация, левая коимпликация;

читается « x не имплицирует y».

f₈(x, y) = xy = (xy) - стрелка Пирса, антидизъюнкция,

функция Вебба, функция Даггера;

читается «х стрелка Пирса y».

f₁₄(x, y) = x|y = (xy) - штрих Шеффера, антиконъюнкция;

читается « х штрих Шеффера y »

f₁₁(x, y) = y x - обратная импликация;

читается « y импликация x », « y влечёт х». «если y, то x».

f₄(x, y) = xy = (yx) - правая коимпликация;

читается « y не имплицирует x ».

Приложение 2. ПРАВИЛА РАВНОСИЛЬНЫХ ПРЕОБРАЗОВАНИЙ ФОРМУЛ

Рецензия

на учебное пособие доцента М.Я. Товштейна

«ФУНКЦИОНАЛЬНО ПОЛНЫЕ СИСТЕМЫ БУЛЕВЫХ ФУНКЦИЙ»

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

Именно этому приложению посвящено данное пособие М.Я. Товштейна. Но, как принято в обучении, всё начинается с азов. Поэтому в пособии излагаются базовые теоретические сведения, необходимые будущим прикладникам, а именно - ответу на вопрос: как определить, позволяет ли набор некоторых булевых функций выразить любую другую булеву функцию.

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

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

Заведующий кафедрой информационных систем

Набережночелнинского института Казанского (Приволжского)

федерального университета, канд.физ.-мат.наук, доцент

Валиев Р.А.

Размещено на Allbest.ru