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

• Конспект лекций
• Лекции, программа
• Литература
• Задачи

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

Черухин Д. Ю. Сравнение булевых базисов. Часть 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)

• Лекция 1 (04.10.2006) Булевы функции, формулы, базисы. Меры сложности формул и функций, их сравнение. [1, Гл. 1, §8;  2]
• Лекция 2 (11.10.2006) Эквивалентность различных мер сложности функций при фиксированном базисе. [1, Гл. 2, §2]
• Лекция 3 (18.10.2006) Бесповторная выразимость. Признак сравнения базисов. Максимальный базис. [2]
• Лекция 4 (08.11.2006) Метод Субботовской. Нижняя оценка сложности линейной функции в максимальном базисе. Пример неэквивалентных базисов. [1, Гл. 8, §4]
• Лекция 5 (15.11.2006) Нижняя и верхняя оценки сложности линейной функции в базисе, содержащем медиану. [3]
• Лекция 6 (06.12.2006) Нижняя и верхняя оценки сложности линейной функции в обобщённо-монотонных базисах. Бесконечно убывающая цепь базисов. [3]
• Лекция 7 (13.12.2006) Критерий эквивалентности максимальному базису. [2]

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

• Лекция 8 (28.02.2007) Метод получения нижних оценок сложности в базисе P₂(2), состоящем из всех двуместных функций. Сравнение базисов P₂(2) и P₂(3). [4]
• Лекция 9, часть 2, часть 3 (14.03.2007) Продолжение лекции 8.
• Лекция 10 (04.04.2007) Метод получения нижних оценок сложности в базисе P₂(n). Сравнение базисов P₂(n) и P₂(n+1). Бесконечно убывающая цепь базисов P₂(n). [4]

Литература

для 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 = P₂(2) (P₂(n) - множество всех булевых функций от n аргументов), B = {&, +(mod 2), 1};
   в) A = P₂(3), B = P₂(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. Дана последовательность булевых функций f₁, f₂, ... и базис B. Определить, имеет ли сложность функции f_n (в классе формул над базисом B) вид O(N( f_n )) при n, стремящемся к бесконечности, где N( f ) - число аргументов функции f ?
   а) f_n = x₁ + ... + x_n (mod 2), B = {xy V xz V yz, -, 0, 1};
   б) f_n = x₁ + ... + x_n (mod 2), B = {xy V xz V yz, -, 0, 1};
   в) f₁(x₁, x₂, x₃) = x₁x₂ V x₁x₃ V x₂x₃, f_n+1(x₁, ..., x_3^(n+1)) = f_n( f₁(x₁, x₂, x₃), ..., f₁(x_{3^(n+1) - 2}, x_{3^(n+1) - 1}, x_3^(n+1))), B = {&, V, -};
   г*) последовательность f₁, f₂, ... из п. в), B = P₂(2).

Страница обновлена: T16.443