Pages Navigation Menu
Submit scientific paper, scientific publications, International Research Journal | Meždunarodnyj naučno-issledovatel’skij žurnal

ISSN 2227-6017 (ONLINE), ISSN 2303-9868 (PRINT), DOI: 10.18454/IRJ.2227-6017
ЭЛ № ФС 77 - 80772, 16+

DOI: https://doi.org/10.23670/IRJ.2017.64.037

Download PDF ( ) Pages: 116-123 Issue: № 10 (64) Part 3 () Search in Google Scholar
Cite

Cite


Copy the reference manually or choose one of the links to import the data to Bibliography manager
Sdvizhkov O.A., "APPLICATION OF LINEAR PROGRAMMING TO THE TASKS OF LOGICAL ALGEBRA". Meždunarodnyj naučno-issledovatel’skij žurnal (International Research Journal) № 10 (64) Part 3, (2017): 116. Wed. 22. Nov. 2017.
Sdvizhkov, O.A. (2017). PRIMENENIE LINEYNOGO PROGRAMMIROVANIYA K ZADACHAM ALGEBRY LOGIKI [APPLICATION OF LINEAR PROGRAMMING TO THE TASKS OF LOGICAL ALGEBRA]. Meždunarodnyj naučno-issledovatel’skij žurnal, № 10 (64) Part 3, 116-123. http://dx.doi.org/10.23670/IRJ.2017.64.037
Sdvizhkov O. A. APPLICATION OF LINEAR PROGRAMMING TO THE TASKS OF LOGICAL ALGEBRA / O. A. Sdvizhkov // Mezhdunarodnyj nauchno-issledovatel'skij zhurnal. — 2017. — № 10 (64) Part 3. — С. 116—123. doi: 10.23670/IRJ.2017.64.037

Import


APPLICATION OF LINEAR PROGRAMMING TO THE TASKS OF LOGICAL ALGEBRA

Сдвижков О.А.

 Кандидат физико-математических наук, доцент, Российский государственный университет туризма и сервиса

ПРИМЕНЕНИЕ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ К ЗАДАЧАМ АЛГЕБРЫ ЛОГИКИ

Аннотация

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

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

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

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

 

Sdvizhkov O.A.

PhD in Physics and Mathematics, Associate Professor, Russian State University of Tourism and Service

APPLICATION OF LINEAR PROGRAMMING TO THE TASKS OF LOGICAL ALGEBRA

Abstract

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. Существенные переменные булевых функций

Переменная 22-11-2017 14-41-49 называется [2] существенной переменной булевой функции 22-11-2017 14-41-15, если найдутся такие значения остальных переменных, при которых выполняется:

22-11-2017 14-41-06                                     (1)

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

Следовательно, если в таблице истинности функции 22-11-2017 14-41-15 существует пара строк, которые различаются только по значениям i-х элементов и по (n+1)-х элементов, то переменная  является существенной, иначе она является фиктивной.

Пусть индексы принимают значения 22-11-2017 14-41-29 – элементы таблицы истинности функции 22-11-2017 14-41-41 – двоичные (булевы) переменные. Тогда справедлива следующая теорема.

Теорема 1. Проверка переменной 22-11-2017 14-41-49 функции 22-11-2017 14-41-15 на существенность сводится к задаче линейного программирования, в которой 22-11-2017 14-43-47  тогда и только тогда, когда переменная 22-11-2017 14-41-49 является существенной:

22-11-2017 14-44-35

Доказательство. В силу (2, 5) выполняется 22-11-2017 14-44-48. Если 22-11-2017 14-43-47, то в силу (5) только одна из переменных 22-11-2017 14-45-08 принимает значение 1 и только одна из переменных 22-11-2017 14-46-13 принимает значение 1, причем в силу (3) индексы этих переменных различны, но тогда из (3, 4) следует (1). В случаях, отличных от 22-11-2017 14-43-47, методом «от противного» легко доказывается, что условие (1) не выполняется.

Пример 1. Проверить, что переменная 22-11-2017 14-46-40  является фиктивной переменной функции  22-11-2017 14-45-40.

  1. В диапазон A1:D8 вводим таблицу истинности.
  2. Диапазон Е1:Е8 оставляем за переменными 22-11-2017 14-45-08.
  3. Диапазон F1:F8 оставляем за переменными 22-11-2017 14-46-13.
  4. Для наглядности заливаем диапазон Е1:F8 желтым цветом.
  5. В ячейку А9 вводим формулу =СУММПРОИЗВ(A1:A8;E1:E8) и копируем ее в остальные ячейки диапазона A9:D9.
  6. В ячейку А10 вводим формулу =СУММПРОИЗВ(A1:A8;F1:F8) и копируем ее в остальные ячейки диапазона A10:D10.
  7. В ячейку Е9 вводим формулу =СУММ(E1:E8) и копируем ее в F9.
  8. В ячейке G10 записываем формулу целевой функции =E9+F9.
  9. В ячейку А11 вводим формулу =А9+А10 и копируем ее в D11.
  10. В ячейку В11 вводим формулу =В9-В10 и копируем ее в С11.
  11. Вызываем надстройку «Поиск решения» и задаем значения параметров (рис. 1).

image021

Рис. 1 – Значения параметров проверки х1 на существенность

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

image022

Рис. 2 – Результаты проверки х1 на существенность

Так как 22-11-2017 14-46-31, то переменная 22-11-2017 14-46-40 является фиктивной.

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

Функция 22-11-2017 14-42-01 называется монотонной [9], если для любых наборов 22-11-2017 14-47-08 и 22-11-2017 14-47-18 таких, что 22-11-2017 14-47-29 такие наборы называются сравнимыми, выполняется:

22-11-2017 14-47-48

В противном случае, она немонотонная.

По аналогии с теоремой 1 доказывается следующая теорема.

Теорема 2. Проверка функции 22-11-2017 14-42-01 на монотонность сводится к задаче линейного программирования, в которой 22-11-2017 14-43-47 тогда и только тогда, когда функция 22-11-2017 14-50-01 не монотонная:

 22-11-2017 14-48-22

Пример 2. Проверить функцию 22-11-2017 15-08-35 на монотонность.

Первые 8 пунктов такие же, как примере 1.

  1. В ячейке А11 записываем формулу =А10-А9 и копируем ее в ячейки В11:С11.
  2. Вызываем надстройку «Поиск решения» и задаем значения параметров поиска решения (рис. 3).

image034

Рис. 3 – Значения параметров проверки на монотонность

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

image035

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

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

Функция 22-11-2017 14-42-01 называется линейной [2], если ее можно представить в виде:

22-11-2017 14-48-46

Теорема 3. Проверка функции 22-11-2017 14-42-01 на линейность сводится к задаче линейного программирования с двоичными переменными 22-11-2017 14-49-09 и целочисленными переменными  22-11-2017 14-49-17, которая имеет решение тогда и только тогда, когда функция 22-11-2017 14-50-01 линейная:

22-11-2017 14-49-33

Пример 3.  Проверить на линейность функцию 22-11-2017 15-12-14.

  1. Вводим в диапазон A1:D8 таблицу истинности функции.
  2. Диапазон A9:D9 оставляем за переменными 22-11-2017 14-49-44(заливаем диапазон желтым цветом), диапазон Е1:Е8 оставляем за переменными 22-11-2017 14-49-54(тоже заливаем диапазон желтым цветом).
  3. В ячейку G1 вводим формулу =A9+СУММПРОИЗВ(A1:C1;B9:D9) и копируем ее в ячейки G2:G8.
  4. В ячейку I1 вводим формулу =G1-2*E1 и копируем ее в ячейки I2:I8.
  5. В ячейку Е10 вводим формулу целевой функции =СУММ(A9:D9).
  6. Вызываем надстройку «Поиск решения» и задаем значения параметров поиска решения (рис. 5).

image045

Рис. 5 – Значения параметров проверки на линейность

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

image046

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

Так как решение найдено, то функция является линейной, причем из данных диапазона A9:D9 следует 22-11-2017 14-50-20.

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

Пусть задана булева матрица22-11-2017 14-50-32 вида 22-11-2017 14-50-43 в каждой строке и в каждом столбце которой есть хотя бы одна единица. Строка i называется покрывающей столбец j, если 22-11-2017 14-50-55. Под покрытием матрицы С понимают совокупность строк, покрывающих все столбцы матрицы С. Задача о кратчайшем покрытии булевой матрицы С состоит в нахождении покрытия, которое имеет минимальное число строк, такое покрытие называют кратчайшим [9].

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

Пусть надо найти решение задачи о кратчайшем покрытии с дефектом k. Введем в рассмотрение булевы переменные 22-11-2017 14-51-15, значения которых определим условиями:  22-11-2017 14-51-15= 1, если i-я строка входит в кратчайшее покрытие, иначе 22-11-2017 14-51-15 = 0. Дополнительно к этим переменным  введем булевых переменные 22-11-2017 14-51-31, значения которых: 22-11-2017 14-51-42, если j-й столбец покрывается кратчайшим покрытием с дефектом k, иначе 22-11-2017 14-51-58. В этих переменных справедлива следующая теорема.

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

22-11-2017 14-52-10

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

22-11-2017 14-52-25

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

22-11-2017 14-52-34

  1. Вводим элементы матрицы в диапазон A1:F4, диапазон H1: H4 оставляем за независимыми переменными (заливаем желтым цветом).
  2. В ячейку А6 вводим формулу =СУММПРОИЗВ(A1:A4;H1:H4) и копируем ее в остальные ячейки диапазона A6:F6.
  3. Целевую функцию записываем в ячейке I5 формулой =СУММ(H1:H4).
  4. Вызываем надстройку «Поиск решения» и задаем значения параметров поиска решения (рис. 7).

image060

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

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

image061

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

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

Первые 3 пункта такие же как в решении примера 4.

  1. Ячейки диапазона A5:F5 оставляем за переменными (заливаем ячейки желтым цветом).
  2. В ячейку G5 вводим формулу =СУММ(A5:F5).
  3. Вызываем надстройку «Поиск решения» и задаем значения параметров поиска решения (рис. 9).

image062

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

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

image063

Рис. 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]
  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]

Leave a Comment

Your email address will not be published. Required fields are marked *

Лимит времени истёк. Пожалуйста, перезагрузите CAPTCHA.