Спецкурс "Сравнение булевых базисов"


Конспект лекций

Черухин Д. Ю. Сравнение булевых базисов. Часть I. - М.: График Без Границ, 2008. - 55 c.

  • Оригинал-макет части I (лекции 1-6): ps.gz (905K)
  • Частично обработанные записки лекций 1-9: ps.gz (230K)
  • Исходные тексты: rar (603K; WinRAR)

   Брошюра содержит обработанный конспект лекций спецкурса "Сравнение булевых базисов", который автор прочёл на мехмате МГУ в 2006/7 уч. г. Тематика спецкурса относится к дискретной математике, точнее, к теории сложности булевых функций. Спецкурс посвящён вопросам сравнения различных мер сложности формул исчисления высказываний, вычисляющих булевы функции. Исследуются несколько естественных мер сложности, так или иначе связанных с длиной формулы, при этом в качестве базиса рассматривается произвольная полная конечная система булевых функций. В спецкурсе излагаются результаты предшественников и автора, достаточно полно представляющие данную проблематику.

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

   Для студентов, специализирующихся в области дискретной математики.

   Часть I содержит лекции 1-6 и состоит из глав I "Введение" и II "Сравнение обобщенно-монотонных базисов".

   На обложке использован рисунок художника Александра Шумилина.


Лекции, программа

Лекции прочитаны на мехмате МГУ в 2006/07 уч. г. Имеется аудиозапись почти всех лекций; ссылка на аудиофайл находится на заголовке лекции.

1-й семестр (осень 2006)

2-й семестр (весна 2007)


Литература

для 1-го семестра

  [1]   Нигматуллин Р. Г. Сложность булевых функций. - М.: Наука, 1991. (глава 8 - djvu)
  [2]   Субботовская Б. А. О сравнении базисов при реализации функций алгебры логики формулами // Докл. АН СССР. - 1963. - Т. 149, № 4. - С. 784-787. (djvu)
  [3]   Черухин Д. Ю. О сложности реализации линейной функции формулами в конечных булевых базисах // Дискретная математика. - 2000. - Т. 12, вып. 1. - С. 135-144.

для 2-го семестра

  [4]   Черухин Д. Ю. Об одной бесконечной последовательности улучшающихся булевых базисов // Дискретный анализ и исследование операций. - 1997. - Т. 4, № 4. - C. 79-95. (djvu)


Задачи

  1. Определить, какие из перечисленных мер сложности формул эквивалентны для любого фиксированного базиса:
       а) длина формулы (общее число символов, включая запятые и скобки);
       б) число входящих в формулу запятых;
       в) число графически различных подформул данной формулы;
       г) число вхождений в формулу символов нелинейных функций;
  2. В каком отношении находятся два заданных булевых базиса A и B: они эквивалентны, несравнимы или один из них (и какой именно) строго предшествует другому; в последнем случае, верно ли, что один из них непосредственно предшествует другому?
       а) A = {/} (/ - штрих Шеффера, x/y = x&y), B = {&, V, -};
       б) A = P2(2) (P2(n) - множество всех булевых функций от n аргументов), B = {&, +(mod 2), 1};
       в) A = P2(3), B = P2(2) U {xy V xz V yz};
       г) A = {xy V xz V yz, -, 0, 1}, B = {xy V xz V yz, -, 0, 1}.
  3. Рассмотрим частично упорядоченное множество булевых базисов с отношением предшествования. Существует ли в нём:
       а) бесконечное число различных эквивалентных друг другу базисов;
       б) бесконечное число несравнимых базисов;
       в) бесконечное число неэквивалентных базисов, строго предшествующих (непосредственно предшествующих) некоторому фиксированному базису;
       г) бесконечное число неэквивалентных базисов, которым строго предшествует (непосредственно предшествует) некоторый фиксированный базис?
  4. Дана последовательность булевых функций f1, f2, ... и базис B. Определить, имеет ли сложность функции  fn (в классе формул над базисом B) вид O(N( fn )) при n, стремящемся к бесконечности, где N( f ) - число аргументов функции f ?
       а)  fn = x1 + ... + xn (mod 2), B = {xy V xz V yz, -, 0, 1};
       б)  fn = x1 + ... + xn (mod 2), B = {xy V xz V yz, -, 0, 1};
       в)  f1(x1, x2, x3) = x1x2 V x1x3 V x2x3fn+1(x1, ..., x3^(n+1)) =  fn( f1(x1, x2, x3), ..., f1(x3^(n+1) - 2, x3^(n+1) - 1, x3^(n+1))), B = {&, V, -};
       г*)  последовательность f1, f2, ... из п. в), B = P2(2).

Страница обновлена: T8.570