Какое программирование основано на булевой алгебре

Как и где в программировании используется математическая логика?

У нас преподша должна вести дискретную математику, но она ходит курить. Создается вопрос: либо ей все равно, либо дискретная математика нам не понадобится. Платы я по жизни не собираюсь паять, хотя зарекаться не стоит, но все же. Где возможно практическое применение данной области, помимо математическое софта?

• Вопрос задан более трёх лет назад
• 14405 просмотров

Комментировать
Решения вопроса 2

Веб-разработчик

Математическая логика — повсеместно. Начиная от простых условий в if-else, заканчивая операциями с базами данных, потому что язык запросов SQL предполагает оперирование с множествами. Насчет дискретной математики, тут очень важная часть — теория графов, потому что практически все хорошие алгоритмы поиска (да и сортировки тоже) основаны на деревьях. Так же довольно таки неплохо иметь представление о теории автоматов, что тоже используется, например, в алгоритмах поиска.

Ответ написан более трёх лет назад
Комментировать
Нравится 16 Комментировать

Заводчик кардиганов

Математическая логика — правила вывода, системы аксиом, теории, логические системы и т.п. — практически не используется. Возможно, какая-то её часть нужна при разработке компиляторов (формализация вывода типов, доказательства допустимости оптимизаций. ) и экспертных систем.
Булева алгебра нужна гораздо чаще. Но если вы выучите и поймёте правила преобразования логических выражений, этого будет достаточно. Даже предполные классы, скорее всего, не понадобятся. Хотя, если судьба забросит в программирование ПЛИС. там всё может быть.
Проходят ли в дискретной математике графы — не помню. Даже если да, то совсем не на том уровне (и не в том направлении), в котором они нужны в программировании.
Что могло бы пригодиться — конечные автоматы. Они нужны более, чем в одном месте. Но, опять же, в дискретной математике могут дать, разве что, общие факты про них.
Так что, в целом — это предмет для расширения кругозора и любителей головоломок разных уровней.

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

Булева алгебра — это раздел математики, занимающийся изучением операций с логическими значениями истинности. Она основана на системе, определяемой значениями «истина» и «ложь», обычно обозначаемыми как 1 и 0 соответственно. Основные операции булевой алгебры логики включают конъюнкцию (И), дизъюнкцию (ИЛИ) и отрицание (НЕ). Данные операции лежат в основе цифровой логики и имеют широкое применение в областях, таких как компьютерные науки, цифровая электроника и теория множеств. Свое название булева алгебра получила от фамилии британского математика Джорджа Буля.

«IT-специалист с нуля» наш лучший курс для старта в IT

IT-специалист с нуля

Наш лучший курс для старта в IT. За 2 месяца вы пробуете себя в девяти разных профессиях: мобильной и веб-разработке, тестировании, аналитике и даже Data Science — выберите подходящую и сразу освойте ее.

Профессия / 8 месяцев
IT-специалист с нуля

Попробуйте 9 профессий за 2 месяца и выберите подходящую вам

История булевой алгебры

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

Идеи Буля не сразу получили широкое распространение. Настоящее признание пришло после того, как в 1854 году он выпустил свой основополагающий труд «Исследование законов мысли, на которых основаны математические теории логики и вероятностей».

Работа Буля оказала значительное влияние на следующие поколения логиков и математиков. В конце 19-го века, работая над понятием множества и теорией отношений, немецкий ученый Готтлоб Фреге и итальянский математик Джузеппе Пеано независимо друг от друга продвинули идеи Буля еще дальше, формализовав их для использования в математической логике.

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

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

Курс для новичков «IT-специалист
с нуля» – разберемся, какая профессия вам подходит, и поможем вам ее освоить

Основные принципы булевой алгебры

В основе булевой алгебры лежат две критически важные концепции:

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

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

Операции в булевой алгебре

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

• Конъюнкция (И). Это операция, которую можно сравнить с функцией логического умножения. Результат конъюнкции двух утверждений истинен только тогда, когда оба утверждения истинны. В символической форме, если у нас есть две булевы переменные A и B, их конъюнкция записывается как A ∧ B. В контексте электронных схем это можно представить как серию переключателей, где ток течет только тогда, когда все переключатели замкнуты.
• Дизъюнкция (ИЛИ). Это логическое сложение, где результат операции истинен, если хотя бы одно из утверждений истинно. Она обозначается как A ∨ B и представляет цепь, в которой ток течет, если хотя бы один переключатель замкнут. В более широком смысле, дизъюнкция используется для создания условий, где действие выполняется при соблюдении хотя бы одного из нескольких критериев.
• Отрицание (НЕ). Операция, меняющая значение переменной на противоположное. Если A истинно, тогда ¬A (читается как «НЕ A») будет ложно, и наоборот. Это аналог включения переключателя, который прерывает ток в электрической цепи, изменяя ее состояние с «активно» на «неактивно».

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

• Исключающее ИЛИ (XOR). Операция, истинное значение которой получается, если ровно одно из утверждений истинно. Эта операция полезна в ситуациях, когда необходимо различать строго одно состояние от другого.
• Импликация (ЕСЛИ…, ТО…). Принцип, по которому истинность следствия (B) зависит от истинности условия (A). В символической записи A → B истинно, если из истинного A следует истинное B либо когда A ложно вне зависимости от B.
• Эквиваленция (ТОГДА И ТОЛЬКО ТОГДА). Это отношение между двумя утверждениями, которое говорит о том, что они имеют одинаковую истинностную оценку. В символическом виде A ↔ B показывает, что A и B или оба истинны, или оба ложны.

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

Отрицание (НЕ). В этой таблице всего две строки, поскольку отрицание применяется только к одному входному значению. Столбец «¬A» показывает противоположное исходному значение.

A	¬A
0	1
1	0

Конъюнкция (И). Здесь уже сложнее: есть четыре возможные комбинации входных значений для A и B. Только когда оба входа истинны (оба равны 1), результат тоже будет истинным.

A	B	A ∧ B
0	0	0
0	1	0
1	0	0
1	1	1

Дизъюнкция (ИЛИ). В случае операции «ИЛИ» нужно всего лишь одно истинное значение, чтобы результатом была истина, это видно в столбце A ∨ B.

A	B	A ∨ B
0	0	0
0	1	1
1	0	1
1	1	1

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

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

Виды булевой алгебры

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

• Классическая. Это та форма булевой алгебры, с которой большинство людей знакомо. Она оперирует двумя значениями — истиной (1) и ложью (0) — и использует основные логические операции, такие как конъюнкция (И), дизъюнкция (ИЛИ) и отрицание (НЕ). Классическая булева алгебра широко применяется в области цифровой электроники и компьютерного архитектурного проектирования.
• Множественная. Еще одна форма, которая допускает работу с наборами элементов (множествами) и операции над ними, такие как пересечение, объединение и дополнение, аналогичные операциям И, ИЛИ и НЕ соответственно. Алгебра множеств является основой для теоретической информатики и теории множеств.
• Многозначная (модальная). Этот вид расширяет классическую булеву алгебру, вводя более двух значений истинности. Модальная логика включает понятия возможности и необходимости и может использоваться для формализации рассуждений о заявлениях, в которых истина может изменяться в зависимости от контекста или времени.
• Булевы функциии выражения. Это отдельная категория, в которую входят формальные алгебраические представления, состоящие из переменных и логических операций. Булевы функции используются для конструирования сложных логических схем и создания программного обеспечения, где требуется выполнение конкретных логических условий или операций.
• Вычислительная. Эта разновидность булевой алгебры фокусируется на роли логических операций и структур в контексте вычислений. Принципы вычислительной булевой алгебры широко применяются в компьютерных науках, особенно в области проектирования алгоритмов и оптимизации программного кода.
• Реляционная. Этот тип занимается логическими отношениями между элементами множеств. Он важен в теории баз данных и информационного поиска, где часто используются операторы, включающие соединение, выборку и проекцию данных.
• Проектная (сетевая). Учитывает логические связи в проектных схемах, например в сетевом анализе и проектировании систем вычислительных сетей. Здесь важны такие концепции, как взаимоисключение, зависимость и секвенирование событий.

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

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

А́лгебра ло́гики Джо́рджа Бу́ля (бу́лева а́лгебра) [1] — раздел математической логики, изучающий высказывания [2] и операции над ними.

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

В математических выражениях множеству сопоставляется множество .

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

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

Булевы функции

Полный набор булевых функций для n переменных представлен в таблице, называемой таблицей истинности. Каждая функция соответствует своему набору переменных x в множестве или, сокращённо, . Количество переменных x в каждом наборе составляет 2 n > . Общее число функций для n переменных составляет m = 2 2 n >>

Функции n переменных
X1	X2	…	Xn-1	Xn	Ym = fm(X1,X2,…,Xn-1,Xn)
1e-06	0	0	.	0	0	Y0 = f0 (0,0,…,0,0)
2e-06	0	0	.	0	1	Y1 = f1 (0,0,…,0,1)
3e-06	0	0	.	1	0	Y2 = f2 (0,0,…,1,0)
4e-06	0	0	.	1	1	Y3 = f3 (0,0,…,1,1)
5e-06	.	.	.	.	.	.
6e-06	1	1	.	1	0	Ym-1 = fm-1 (1,1,…,1,0)
7e-06	1	1	.	1	1	Ym = fm (1,1,…,1,1)

Функции одной переменной

Наборы булевых функций для одной переменной [4] , когда n = 1, представлены в приведённой ниже таблице истинности. Количество функций согласно формуле m = 2 2 n >> составляет 2 2 1 >> = 4. Обозначим их как Y₀, Y₁, Y₂, Y₃

Функции одной переменной
X	Y0	Y1	Y2	Y3
1e-06	0	0	0	1	1
2e-06	1	0	1	0	1

• Функция Y₀ не зависит от значений переменной x и носит название «константа ноль» (const 0);
• Функция Y₁ повторяет значения переменной x и носит название «тождественная функция»;
• Функция Y₂ имеет значения, инверсные значениям переменной x и носит название «функция НЕ» или «логическое отрицание»;
• Функция Y₃ не зависит от значений переменной x и носит название «константа единица» (const 1);

Функции двух переменных

Наборы булевых функций для двух переменных [4] , когда n =2, представлены в приведённой ниже таблице истинности. Количество функций согласно формуле m = 2 2 n >> составляет 2 2 2 >> = 16. Обозначим их как Y₀, Y₁, Y₂,…, Y₁₅

Функции двух переменных
X1	X2	Y0	Y1	Y2	Y3	Y4	Y5	Y6	Y7	Y8	Y9	Y10	Y11	Y12	Y13	Y14	Y15
1e-06	0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
2e-06	0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
3e-06	1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
4e-06	1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

Легко заметить, что сочетания «0» и «1» в значениях функций соответствуют их номерам, записанным в двоичной системе счисления. Например, номер функции Y₁, равный 1 в десятичной системе счисления, в двоичной записывается как 0001. Соответственно Y₂ имеет номер 2₁₀ = 0010₂, последняя функция Y₁₅ имеет номер 15₁₀ = 1111₂ Приведенная таблица истинности отражает все возможные булевы функции от двух переменных. Они имеют названия и специальные обозначения.

Логические элементы

В общем случае в качестве логических элементов могут использоваться любые устройства, которые могут принимать два устойчивых противоположных состояния типа «включено/выключено». Они могут быть электромеханическими, электронными (в частности, на диодах или транзисторах), пневматическими, гидравлическими, оптическими и другими. В ряде случаев, например, когда в системах управления необходимо применять взрывобезопасные устройства, в качестве логических элементов используют пневматические клапаны. Рассмотрим логические элементы [5] , выполненные в виде электронных устройств, каждое из которых предназначено для выполнения определённой логической функции. Обработка информации производится в виде обработки электрических сигналов низкого и высокого уровней, соответствующих переменным «0», «1» в двоичной логике, то есть эти устройства выполняют логическую операцию над входными сигналами и позволяют получить на выходе сигналы в той же форме «0», «1», соответствующие значению выполняемой логической функции. Ниже рассмотрены таблицы истинности, названия и обозначения функций, имеющих наибольшее прикладное применение, а также мнемонические изображения соответствующих им логических элементов. Таблицы истинности и логические элементы приведены для двух входных переменных, но в ряде случаев правило распространяется на любое количество переменных. Например, логический элемент, реализующий функцию «И» (см. ниже), теоретически может иметь 1,2,3,…, k входов.

Конъюнкция (логическое умножение). Операция «И»

Логический элемент, реализующий функцию конъюнкции, называется схемой логического умножения или схемой «И». Функция принимает значение «1» в том и только в том случае, когда все её аргументы принимают значение «1». Запись функции: Y = A ∧ B, Y = A & B. В таблице, приведённой выше для булевых функций от двух переменных, это функция Y₁. Обозначение на схеме:

Применение линейного программирования к задачам алгебры логики Текст научной статьи по специальности «Математика»

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

i Надоели баннеры? Вы всегда можете отключить рекламу.

Похожие темы научных работ по математике , автор научной работы — Сдвижков О.А.

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

APPLICATION OF LINEAR PROGRAMMING TO THE TASKS OF LOGICAL ALGEBRA

Significant variables of Boolean functions are found in the article with the help of linear programming. Boolean functions are checked for monotonicity and linearity . The problem of the shortest covering of a Boolean matrix is generalized, as is the problem of the shortest covering of a Boolean matrix with a given defect. Generalized problem of the shortest covering is reduced to the problem of linear programming. As a consequence we obtain a linear programming problem, to which the classical problem of the shortest covering of a Boolean matrix is reduced. Examples are given where problems of the theory of Boolean functions are solved with the help of linear programming.

Текст научной работы на тему «Применение линейного программирования к задачам алгебры логики»

DOI: https://doi.org/10.23670/IRJ.2017.64.037 Сдвижков О.А.

Кандидат физико-математических наук, доцент, Российский государственный университет туризма и сервиса ПРИМЕНЕНИЕ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ К ЗАДАЧАМ АЛГЕБРЫ ЛОГИКИ

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

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

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

Ключевые слова: оптимизация, булева функция, монотонность, линейность, кратчайшее покрытие.

PhD in Physics and Mathematics, Associate Professor, Russian State University of Tourism and Service APPLICATION OF LINEAR PROGRAMMING TO THE TASKS OF LOGICAL ALGEBRA

Significant variables of Boolean functions are found in the article with the help of linear programming. Boolean functions are checked for monotonicity and linearity.

The problem of the shortest covering of a Boolean matrix is generalized, as is the problem of the shortest covering of a Boolean matrix with a given defect. Generalized problem of the shortest covering is reduced to the problem of linear programming. As a consequence we obtain a linear programming problem, to which the classical problem of the shortest covering of a Boolean matrix is reduced.

Examples are given where problems of the theory of Boolean functions are solved with the help of linear programming.

Keywords: optimization, Boolean function, monotonicity, linearity, shortest covering.

Статья посвящена сведению ряда задач теории булевых функций [1], [2], [9], [10], включая задачу о кратчайшем покрытии булевой матрицы и ее обобщения, к задачам линейного программирования [3, 4] и решению их методами линейного программирования. Такой подход является достаточно эффективным, так как методы решения задач линейного программирования поддерживаются, вообще говоря, во всех современных информационных математических приложениях, включая [5], [6], [7], [8].

Во всех примерах данного исследования применялась надстройка «Поиск решения» (в оригинале «Solver») программного комплекса Excel.

§ 1. Существенные переменные булевых функций

Переменная x. называется [2] существенной переменной булевой функции f = f (x,х2. xn), если найдутся такие значения остальных переменных, при которых выполняется:

f (xi, •••, Х—1 ,0 x-+i , xn ) * f (xi , ••• (1)

В противном случае, она называется несущественной или фиктивной переменной.

Следовательно, если в таблице истинности функции f = f (x:,х2,•••, xn) существует пара строк, которые

различаются только по значениям i-х элементов и по (п+1)-х элементов, то переменная xi является существенной, иначе она является фиктивной.

Пусть индексы принимают значения k = i, 2, •„, 2n, j = i, 2, •••,n + i, с^. — элементы таблицы истинности функции f, ик и vk — двоичные (булевы) переменные. Тогда справедлива следующая теорема.

Теорема 1. Проверка переменной xt функции f = f(x:,Х2,„•,xn) на существенность сводится к задаче линейного программирования, в которой ^ = 2 тогда и только тогда, когда переменная x. является существенной:

Z = Z (U + vi ) ^ max , (2)

Z cjuk + Z ckjvk = i> j n +i>; (3)

Zck,uk -Zck,vk = ° j * i-‘n+i>; (4)

Z uk ^i; Z vk ^i . (5)

Пример 1. Проверить, что переменная x является фиктивной переменной функции f = (11001100).

1. В диапазон A1:D8 вводим таблицу истинности.

2. Диапазон Е1:Е8 оставляем за переменными щ.

3. Диапазон F1:F8 оставляем за переменными vk .

4. Для наглядности заливаем диапазон E1:F8 желтым цветом.

5. В ячейку А9 вводим формулу =СУММПРОИЗВ(А1:А8;$Е$1:$Е$8) и копируем ее в остальные ячейки диапазона A9:D9.

6. В ячейку А10 вводим формулу =СУММПРОИЗВ(А1:А8^$1№$8) и копируем ее в остальные ячейки диапазона A10:D10.

7. В ячейку Е9 вводим формулу =СУММ(Е1:Е8) и копируем ее в F9.

8. В ячейке G10 записываем формулу целевой функции =E9+F9.

9. В ячейку А11 вводим формулу =А9+А10 и копируем ее в D11.

10. В ячейку В11 вводим формулу =В9-В10 и копируем ее в С11.

11. Вызываем надстройку «Поиск решения» и задаем значения параметров (рис. 1).

Рис. 1 — Значения параметров проверки XI на существенность 11. Кнопка «Найти решение» возвращает сообщение, что решение найдено, и результаты (рис. 2).

Рис. 2 — Результаты проверки х1 на существенность Так как г = 1 < 2, то переменная х1 является фиктивной.

§ 2. Монотонность и линейность булевых функций

Функция f = f (Xj,X2. Xn) называется монотонной [9], если для любых наборов (a,a2,•••, an) и

По аналогии с теоремой 1 доказывается следующая теорема. Теорема 2. Проверка функции f = f,X2. Xn) на монотонность сводится к задаче линейного

программирования, в которой ^ = 2 тогда и только тогда, когда функция f не монотонная:

2″ 2″ Ё ckn+1щ =1; Ё ckn+1vk = 0;

Пример 2. Проверить функцию f = (10101100) на монотонность. Первые 8 пунктов такие же, как примере 1.

9. В ячейке А11 записываем формулу =А10-А9 и копируем ее в ячейки В11:С11.

10. Вызываем надстройку «Поиск решения» и задаем значения параметров поиска решения (рис. 3).

Рис. 3 — Значения параметров проверки на монотонность 12. Кнопка «Найти решение» возвращает сообщение, что решение найдено, и результаты (рис. 4).

Рис. 4 — Результаты проверки на монотонность

Так как = 2, то функция не монотонная, монотонность, как минимум, нарушается в 1-ой и 2-ой строках таблицы истинности.

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

Функция / = / , хг. хп ) называется линейной [2], если ее можно представить в виде:

/ = а © ах Ф а2х2 Ф. Ф апхп. Теорема 3. Проверка функции / = /(^. ) на линейность сводится к задаче линейного программирования с двоичными переменными а0, а. аи и целочисленными переменными Ъх, Ъ2. Ъ2„ , которая имеет решение тогда и только тогда, когда функция / линейная:

Еак ^ таХ ао + Есаа] = 2ЪЪ + С п+1’1 = 1,2. 2п.

Пример 3. Проверить на линейность функцию / = (11000011).

1. Вводим в диапазон Л1:Б8 таблицу истинности функции.

2. Диапазон Л9:Б9 оставляем за переменными а0, а, а2, а (заливаем диапазон желтым цветом), диапазон Е1:Е8

оставляем за переменными Ъ ,Ъ . , Ъ (тоже заливаем диапазон желтым цветом).

3. В ячейку в1 вводим формулу =$Л$9+СУММПРОИЗВ(Л1:С1;$Б$9:$Б$9) и копируем ее в ячейки 02:в8.

4. В ячейку II вводим формулу =в1-2*Б1 и копируем ее в ячейки 12:18.

5. В ячейку Е10 вводим формулу целевой функции =СУММ(Л9:Б9).

6. Вызываем надстройку «Поиск решения» и задаем значения параметров поиска решения (рис. 5).

Рис. 5 — Значения параметров проверки на линейность 6. Кнопка «Найти решение» возвращает сообщение, что решение найдено, и результаты (рис. 6).

А Б с D Е F G Н 1

1 0 0 0 1 0 1 1

2 0 0 1 1 0 1 1

3 0 1 0 0 1 2 0

4 0 1 1 0 1 г 0

5 1 0 0 0 1 2 0

6 1 0 1 0 1 2 0

7 1 1 0 1 1 3 1

S 1 1 1 1 1 3 1

Рис. 6 — Результаты проверки на линейность

Так как решение найдено, то функция является линейной, причем из данных диапазона A9:D9 следует f — 10 X 0 .

§ 3. Кратчайшие покрытия булевых матриц

Пусть задана булева матрица C — (с^ ) вида m х n , в каждой строке и в каждом столбце которой есть хотя бы одна

единица. Строка i называется покрывающей столбец j, если с, — 1. Под покрытием матрицы С понимают совокупность

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

Назовем задачу нахождения минимальной совокупности строк матрицы С, покрывающих не менее n-k столбцов, k е , задачей о кратчайшем покрытии с дефектом k. Понятно, что задача о кратчайшем покрытии является задачей о кратчайшем покрытии с дефектом k =0.

Пусть надо найти решение задачи о кратчайшем покрытии с дефектом k. Введем в рассмотрение булевы переменные

X, значения которых определим условиями: х. = 1, если i-я строка входит в кратчайшее покрытие, иначе х. = 0. Дополнительно к этим переменным введем булевых переменные y ■, значения которых: y. — 1, если j-й столбец

покрывается кратчайшим покрытием с дефектом k, иначе y. — 0 . В этих переменных справедлива следующая теорема.

Теорема 4. Задача о кратчайшем покрытии с дефектом k булевой матрицы С сводится к задаче линейного программирования:

с11Х1 + C21X2 + — + Cm1Xm — У

с12 X1 + C22 X2 + ••• + Cm 2 Xm — У2

С1пХ1 + С2пХ2 + ••• + СтпХт ^ Уп

У + У2 + ••• + Уп ^ п » к

Следствие. Задача о кратчайшем покрытии булевой матрицы С сводится к задаче линейного программирования:

с11 X1 + C21 X2 + ••• + Cm1xm — 1 с12 X1 + C22 X2 + ••• + Cm 2 Xm — 1

с,х + Ct„X^ + ••• + CX — 1

Пример 4. Найти кратчайшее покрытие булевой матрицы

011010 001101 110100у

1. Вводим элементы матрицы в диапазон A1:F4, диапазон Ш: Ш оставляем за независимыми переменными

(заливаем желтым цветом).

2. В ячейку А6 вводим формулу =СУММПРОИЗВ(Л1:Л4;$H$1:$H$4) и копируем ее в остальные ячейки диапазона Л6^6.

3. Целевую функцию записываем в ячейке 15 формулой =СУММ(Н1:Н4).

4. Вызываем надстройку «Поиск решения» и задаем значения параметров поиска решения (рис. 7).

Рис. 7 — Значения параметров нахождения кратчайшего покрытия

5. Команда «Найти решение» возвращает сообщение, что решение найдено, и результаты (рис. 8), показывающие, что кратчайшее покрытие состоит из строк 1, 2, 4.

А в с О Е ¥ G н I

1 0 1 0 1 0 1 1

2 0 1 1 0 1 0 1

3 0 0 1 1 0 1 О

4 1 1 0 1 0 0 1

Рис. 8 — Результаты нахождения кратчайшего покрытия

Пример 5. Найти кратчайшее покрытие с дефектом 1 матрицы С, заданной в примере 4. Первые 3 пункта такие же как в решении примера 4.

4. Ячейки диапазона Л5^5 оставляем за переменными у. (заливаем ячейки желтым цветом).

5. В ячейку в5 вводим формулу =СУММ(Л5^5).

6. Вызываем надстройку «Поиск решения» и задаем значения параметров поиска решения (рис. 9).

Рис. 9 — Параметры нахождения кратчайшего покрытия с дефектом 1

6. Команда «Найти решение» возвращает сообщение, что решение найдено, и результаты (рис. 10), показывающие, что кратчайшее покрытие дефекта 1 состоит из строк 2, 4:

A Б С D Е F G Н

1 0 1 0 1 0 1 0

2 0 1 1 0 1 0 1

3 0 0 1 1 0 1 0

4 1 1 0 1 0 0 1

5 1 1 1 1 1 О 5 2|

6 r r 1 г 2 г 1 г 1 г 1 0

Рис. 10 — Результаты нахождения кратчайшего покрытия с дефектом 1

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

Список литературы / References

1. Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения. 3 -е издание. / Я.М. Ерусалимский — М.: Вузовская книга, 2000. — 280 с.

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

3. Галеев Э.М. Оптимизация: теория, примеры, задачи: Учебное пособие. / Э.М. Галеев — М.: УРСС, 2002. — 304 с.

4. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. / О.П. Кузнецов, Г.М. Адельсон-Вельский — 2-е изд., перераб. и доп. — М.: Энергоатомиздат, 1988. — 480 с.

5. Сдвижков О.А. Дискретная математика и математические методы экономики с применением VBA Excel. / О.А. Сдвижков — М.: ДМК Пресс, 2012. — 212 с.

6. Сдвижков О.А. Математика в Excel 2003. / О.А. Сдвижков — М.: СОЛОН-Пресс, 2005. — 192 с.

7. Сдвижков О.А. Математика на компьютере: Maple 8. / О.А. Сдвижков — М.: СОЛОН-Пресс, 2003. — 176 с.

8. Сдвижков О.А. MathCAD-2000. / О.А. Сдвижков — М.: Издательско-торговая корпорация «Дашков и К», 2002. -204 с.

9. Супрун В.П. Основы теории булевых функций. / В.П. Супрун — М.: ЛЕНАНД, 2017. — 208 с.

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

Список литературы на английском языке / References in English

1. Erusalimskij Ja.M. Diskretnaja matematika: teorija, zadachi, prilozhenija. 3-e izdanie [Discrete mathematics: the theory, task, appendix. 3 editions] / Ja.M. Erusalimskij — M.: Vuzovskaja kniga, 2000. — 280 p. [in Russian]

2. Gavrilov G.P., Sapozhenko A.A. Zadachi i uprazhnenija po diskretnoj matematike: Ucheb. posobie. — 3-e izd., pererab. [Tasks and exercises on discrete mathematics: studies] / G.P. Gavrilov, A.A. Sapozhenko — M.: FIZMATLIT, 2003. — 416 p. [in Russian]

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

3. Galeev Je.M. Optimizacija: teorija, primery, zadachi: Uchebnoe posobie. [Optimization: the theory, examples, tasks] / Je.M. Galeev — M.: URSS, 2002. — 304 p. [in Russian]

4. Kuznecov O.P., Adel’son-Vel’skij G.M. Diskretnaja matematika dlja inzhenera [Discrete mathematics for the engineer] / O.P. Kuznecov, G.M. Adelson-Velskij / — 2-e izd., pererab. i dop. — M.: Jenergoatomizdat, 1988. — 480 p. [in Russian]

5. Sdvizhkov O.A. Diskretnaja matematika i matematicheskie metody jekonomiki s primeneniem VBA Excel [Discrete mathematics and mathematical methods of economy with application VBA Excel] / O.A. Sdvizhkov — M.: DMK Press, 2012. -212 p. [in Russian]

6. Sdvizhkov O.A. Matematika v Excel 2003 [Mathematics in Excel 2003] / O.A. Sdvizhkov — M.: SOLON-Press, 2005. -192 p. [in Russian]

7. Sdvizhkov O.A. Matematika na komp’jutere: Maple 8 [Mathematics on the computer: Maple 8] / O.A. Sdvizhkov — M.: SOLON-Press, 2003. — 176 p. [in Russian]

8. Sdvizhkov O.A. MathCAD-2000 [MathCAD-2000] / O.A. Sdvizhkov — M.: Izdatelsko-torgovaja korporacija «Dashkov and C», 2002. — 204 p. [in Russian]

9. Suprun V.P. Osnovy teorii bulevyh funkcij [Bases of the theory Boolean functions] / V.P. Suprun — M.: LENAND, 2017. -208 p. [in Russian]

10. Jablonskij S.V. Vvedenie v diskretnuju matematiku [Introduction in discrete mathematics] / S.V. Jablonskij — M.: Science, 1986. — 384 p. [in Russian]

DOI: https://doi.org/10.23670/IRJ.2017.64.026 Смольянов А.Г.

Кандидат физико-математических наук, Национальный исследовательский Мордовский государственный университет им. Н.П. Огарёва ИСПОЛЬЗОВАНИЕ КОНТРОЛЛЕРОВ АВТОМАТИЗАЦИИ ПРИЛОЖЕНИЙ MICROSOFT OFFICE В УПРАВЛЕНЧЕСКОЙ ДЕЯТЕЛЬНОСТИ КАФЕДРЫ ВУЗА

В целях оптимизации взаимодействия между Учебно-методическим управлением (УМУ) и кафедрами ВУЗа предложена компьютерная система, позволяющая автоматизировать информационные процессы, связанные с формированием расчетов нагрузки кафедр и распределением учебных поручений. Использование удаленного сервера позволило собрать кафедральные сведения в одном хранилище и оперативно получать общую и детальную картину по расчетам нагрузки и её распределению по всему ВУЗу. Практическое внедрение системы ускорило решение различных организационных задач и принятие управленческих решений. Система позволила более строго контролировать цифровой материал, связанный с организацией учебного процесса на кафедре. Подсистема генерации различных документов на стороне УМУ и на стороне кафедры позволила полностью автоматизировать подготовку ряда повседневных документов в электронном виде, исключив во многих случаях излишний бумажный документооборот.

Ключевые слова: расчет нагрузки кафедры, информационная система, технология COM, сервер автоматизации, контроллер автоматизации, Microsoft Office, генерация документов, компьютерная программа «Расчет:Распределение».

PhD in Physics and Mathematics, National Research Ogarev Mordovia State University USING THE CONTROLLERS OF AUTOMATION OF MICROSOFT OFFICE APPLICATIONS IN THE MANAGEMENT ACTIVITY OF HIGH SCHOOL DEPARTMENTS

In order to optimize the interaction between the Educational-methodical management (EMM) and the departments of the university, a computer system is proposed that allows to automate the information processes associated with the calculation of the load of the departments and the distribution of training assignments. Using a remote server made possible to collect the department’s information in one repository and quickly obtain a general and detailed picture of the load calculations and its distribution throughout the university. The practical implementation of the system accelerated the solution of various organizational tasks and the adoption of managerial decisions. The system allowed to more strictly control digital material related to the organization of the educational process at the department. The subsystem of generation of various documents on the side of the EMM and on the side of the department allowed to fully automate the preparation of a number of everyday documents electronically, eliminating in many cases excessive paperwork.

Keywords: load calculation of the department, information system, COM technology, automation server, automation controller, Microsoft Office, documents generation, computer program «Calculation: Distribution».

В последние годы в обществе обозначилась устойчивая тенденция на массовый переход к электронному документообороту и интенсивному использованию инструментальных средств разработки программ, позволяющих автоматизировать процессы генерации электронных документов различных форматов. Появилась возможность интегрировать прикладные программы с генераторами отчетов, а также генерировать документы определенных форматов посредством доступа к интерфейсам «родных» систем этих документов [1], [2], [3], [4], [5]. Технологии web-программирования в этом направлении тоже развиваются. В качестве примера нового инструмента для автоматизации документов можно назвать пакет PHPOffice [6], [7]. Сегодня появляются генераторы отчетов нового поколения, к примеру, на основе PHP. Одна из технологий позволяет вставить в определенные места шаблона документа Microsoft Office код PHP и получить готовый документ формата Microsoft Word или Microsoft Excel. Причем в качестве источников данных при формировании документа могут быть файлы форматов DOS, ASCII, PDF, XML, dBase, ODBC, ORACLE, Microsoft SQL и других. Такую замечательную возможность дает, к примеру, продукт Script