Булева алгебра и ее применение при построении математических моделей

Стр.2

Стр.3

Стр.4

УДК 512.563(075) ББК 22.1я7 C30 Рецензенты: канд. физ.-мат. наук, доц. М . Н . С а уш к и н , канд. физ.-мат. наук, доц. М . Е . Ф е д и н а Семенова, Ирина Владимировна С30 Булева алгебра и ее применение при построении математических моделей: учебное пособие / И.В. Семенова. – Самара : Издательство Самарского университета, 2023. – 100 с. : ил. ISBN 978-5-7883-1870-7 В пособии изложены основные вопросы булевой алгебры. Рассмотрены свойства булевых функций, методы их минимизации и приведения к нормальным формам. Приведено описание всех замкнутых классов булевых функций, а также методы определения полноты систем таких функций. Кроме того, в пособии рассматриваются вопросы практического применения булевой алгебры при построении математических моделей в различных областях. Помимо основных понятий и теоретических результатов, пособие включает алгоритмы и примеры решения типовых задач, поэтому оно является не только дополнением к материалам лекций по курсу «Дискретная математика», но и поддержкой самостоятельной работы обучающихся по направлениям подготовки 02.03.01 Математика и компьютерные науки и 02.03.03 Математическое обеспечение и администрирование информационных систем. Подготовлено на кафедре информатики и вычислительной математики. УДК 512.563(075) ББК 22.1я7 ISBN 978-5-7883-1870-7 2 © Самарский университет, 2023

Стр.2

СОДЕРЖАНИЕ Введение ............................................................................................. 5 1 Основные понятия математической логики и их применение при моделировании процесса человеческого мышления ......... 6 2 Булевы (двоичные) наборы ....................................................... 10 3 Булевы функции .......................................................................... 12 3.1 Способы задания булевых функций .................................... 12 3.2 Элементарные булевы функции ........................................... 14 3.3 Равносильность булевых функций ...................................... 15 3.4 Существенные и фиктивные переменные ........................... 19 4 Двойственность ............................................................................ 20 5 Дизъюнктивные и конъюнктивные нормальные формы всюду определенных булевых функций ..................................... 27 5.1 Разложение булевых функций по переменным .................. 27 5.2 Дизъюнктивные и конъюнктивные нормальные формы ... 28 5.3 Совершенные дизъюнктивные и конъюнктивные нормальные формы ..................................................................... 34 6 Минимизация нормальных форм всюду определенных булевых функций ............................................................................ 42 6.1 Метод Квайна......................................................................... 42 6.2 Карты Карно ........................................................................... 48 7 Полнота и замкнутость систем булевых функций ................ 56 7.1 Полнота систем булевых функций ...................................... 56 7.2 Замыкание систем булевых функций .................................. 58 7.3 Класс булевых функций T0, сохраняющих ноль ................ 59 7.4 Класс булевых функций T1, сохраняющих единицу .......... 60 7.5 Класс самодвойственных булевых функций S ................... 60 3

Стр.3

7.6 Класс линейных булевых функций L. Полином Жегалкина .................................................................... 62 7.7 Класс монотонных булевых функций M ............................. 66 7.8 Критерий Поста ..................................................................... 68 7.9 Базис полной системы булевых функций ........................... 77 8 Применение булевой алгебры при моделировании электронных устройств. Функциональные схемы .................. 80 9 Применение булевой алгебры при моделировании электрических цепей. Релейно-контактные схемы ................. 86 10 Применение булевой алгебры при построении математических моделей в различных областях ..................... 92 Список использованных источников ......................................... 98 4

Стр.4