Сборник материалов выездных школ команды Москвы на Всероссийскую математическую олимпиаду

• Название: Сборник материалов выездных школ команды Москвы на Всероссийскую математическую олимпиаду
• Дата: 19.09.2022
• Размер: 3.42 Mb.
• Имя файла: matprob.pdf
• Тип: Сборник; #684321
• страница: 18 из 31

б) цветных ожерелий из n бус. Сколькими способами можно раскрасить в a цветов грани а) правильного тетраэдра б) куба?
Раскраски, совмещающиеся в (трехмерном) пространстве, считаются одинаковыми. а) Сколько существует различных (те. неизоморфных) неориентированных графов с 4 вершинами?

б) Ас вершинами?
в), г) Тоже для ориентированных графов. Отображения {0, 1}
n
→ {0, 1} (те. функции алгебры логики от n переменных) называются конгруэнтными, если они становятся равными после переименования переменных.
а) Найдите число b функций алгебры логики от n переменных с точностью до конгруэнтности.
б) Докажите, что существует lim n→∞
n!b n
/2 2
n
, и найдите этот предел

Комбинаторика классов эквивалентности 8. Сформулируйте общую теорему, которую можно было бы применять вместо повторения приведенного решения задачи 2 в).
Вот ответ.
Лемма Бернсайда. Пусть заданы конечное множество M и семейство {g
1
= id M, g
2
, . . . , g n
} преобразований этого множества,
замкнутое относительно композиции и взятия обратного элемента,
где id M — тождественное отображение множества M в себя. Назовем элементы множества M эквивалентными, если один можно перевести в другой одним изданных преобразований. Тогда число классов эквивалентности равно n
P
k=1
f ix(g i
), где f ix(g i
) — число элементов множества M, которые преобразование g переводит в себя.
(Чтобы сделать этот и следующие результаты менее доступными,
их обычно формулируют и доказывают на языке абстрактной теории групп.)
Назовем (конечной) группой конечное семейство G преобразований
(т. е. перестановок) некоторого конечного множества, замкнутое относительно композиции и взятия обратного элемента (те. если f, g ∈ то f
−1
∈ G и f ◦ g ∈ M). Дальнейшие задачи особенно интересны тем,
кто уже решал задачи про перестановки. а) Любая группа содержит тождественное преобразование.
б) Если число n преобразований в группе G простое, то для любого нетождественного преобразования g∈G имеем G={g, g
2
, . . . , g n
=id M Если в группе G найдется преобразование g, для которого G =
= {g, g
2
, . . . , g n
= id M }, то группа G называется циклической. Группа называется бициклической (этот термин не общепринят, если для некоторых целых p > 1 и q > 1 и преобразований g, h ∈ G выполнено g
h = hg, g p
= id M , h q
= id M и G = {g k
h l
| 1 6 k 6 p, 1 6 l 6 q}.
10. Приведите пример бициклической группы из 4 элементов. Любая ли группа из n преобразований является циклической или бициклической для а) n = б) n = в) n = где. Теорема Лагранжа. Если H — подгруппа группы G (те. подмножество группы G, также являющееся группой, то количество элементов в G делится на количество элементов в H.
13*. Теоремы Силова. Пусть p — простое, n делится на p и не делится на p k+1
, а G — группа из n элементов. Докажите, что

Гл. 10. Подсчеты в комбинаторике а) в G имеется подгруппа из p k
элементов;
б) число таких подгрупп сравнимо с 1 по модулю в) для любых двух таких подгрупп H и найдется такое преобразование, что H
′
= {ghg
−1
| h ∈ г) если p и q — простые, p < q и q − 1 не делится на p, то любая группа из pq преобразований является циклической или бициклической.
Зачетные задачи 1; 2 а) баба) б 6 а) в 9 а) б 11 в).
Задачи на комбинаторные покрытия
2)
(10–11)
А. Я. Канель-Белов
Данная подборка посвящена прежде всего тем ситуациям, когда покрытия используются как метод решения. В большинстве случаев рассматриваются связи между объектами и эти связи покрываются, 3. 21 девочка и 21 мальчик участвуют в математическом соревновании. Оказалось, что каждый участник решил не более 6 задач для каждой пары, состоящей из мальчика и девочки, найдется задача, которую они оба решили.
Докажите, что некоторую задачу решило не менее трех мальчиков и не менее трех девочек, 6. На математической олимпиаде участникам было предложено задач. Оказалось, что каждая пара задач была решена более чем 2/5 от общего числа участников, но никто не решил все 6 задач.
Докажите, что найдутся по крайней мере два участника, каждый из которых решил ровно 5 задач, 6. Пусть n > 3 и C
1
, . . . , C
n
— круги единичного радиуса сцен- трами O
1
, . . . , O
n
, такие что любая прямая пересекает не более трех из них. Докажите, что − 1)π
4 2003, 1. Пусть A есть элементное подмножество множества = {1, 2, . . . , 10 6
}. Докажите, что для некоторых натуральных t
1
, . . .
. . . , t
100
∈ S следующие множества A
j
= {x + t j
| x ∈ A}, j = 1, . . . , попарно не пересекаются.
2)
Указаны год и номер задачи на Международной математической олимпиаде

Оценка Виссера мощности пересечений 2006, 6. Каждой стороне b выпуклого многоугольника P поставлена в соответствие наибольшая из площадей треугольников, содержащихся в P , одна из сторон которых совпадает с b. Докажите, что сумма площадей, соответствующих всем сторонам многоугольника P , не меньше удвоенной площади многоугольника P Указания, 3. Каждая задача рассматривается как связь между мальчиками и девочками. Свяжем с ней пару (a, b), где a — число решивших мальчиков, а b — девочек. Если то, что требуется доказать, не выполнено, то для каждой задачи либо a 6 2, либо b 6 2. Рассматриваемая задача покрывает ab пар мальчик-девочка (всего пар 21 2
). Кроме того i
6 6 · 21 и i
6 6 · 21. Решение задачи завершается подсчетом.
Похожим образом решается задача, 6.
2002, 6. Рассмотрите фазовое пространство прямых. С использованием идеи фазового пространства рекомендуем познакомиться поре- шению задачи 4.6 (об альпинистах, опубликованном в № 6 Математического просвещения, 2002 гс, или по книге Арнольд В. И.
Обыкновенные дифференциальные уравнения, 1.1.2, где разбирается задача Н. Н. Константинова о возах, 1. Последовательность {t j
} строится поэтапно, возможность построения осуществляется исходя из соображения покрытия, 6. Используйте шевеление покрытия при движении одной из вершин с постоянной скоростью все площади меняются линейно
3)
Оценка Виссера мощности пересечений (А. Б. Скопенков
1. В парламенте из R депутатов образовано k комиссий по n человек в каждой. (То есть дано элементное множество и k его элементных подмножества) При R = 2
a
, n = 2
a−1
, k = 4 обязательно найдутся два подмножества, пересекающиеся хотя бы по 2
a−3
элементам.
б) При R = 2
a
, n = 2
a−1
, k = 2
a необязательно найдутся два подмножества, пересекающиеся более чем по 2
a−2
элементам.
в) При R = 2
a
, n = 2
a−1
, k = обязательно найдутся два подмножества, пересекающиеся хотя бы по 2
a−2
элементам.
3)
См. раздел Треугольники и катастрофы в этой книге, с. 447.

Гл. 10. Подсчеты в комбинаторике г) При R = 1600, n = 80, k = 60 необязательно найдутся два подмножества, пересекающиеся хотя бы по 5 элементам.
д)* При R = p(s − 1)
2
(p простое, n = p(s − 1), k = p
2
+ p необязательно найдутся два подмножества, пересекающиеся хотя бы по s эле- ментам.
е) При R = 1600, n = 80, k = 40 обязательно найдутся два подмножества, пересекающиеся хотя бы по 3 элементам.
ж)* При R = 1600, n = 80, k = 16000 обязательно найдутся два подмножества, пересекающиеся хотя бы по 4 элементам.
Указание к еж если не получается, то см. следующую задачу. Дискретный вариант леммы Виссера. В парламенте из депутатов образовано k комиссий по n человек в каждой. Тогда найдутся две комиссии, имеющие более s общих членов,
а) если s 6 n
2
/(2R) и k > б) если s 6 n
2
/(2R) ив) если s 6 n
2
/(
√
2R) и k > г) если s 6 n
2
/(
N
√
2R) и k > для некоторого N д) если s < n
2
/R и k >
n − s
(n
2
/R) − s
(≃ R/n при s ≪ n 6 Эту задачу интересно сравнить со следующей теоремой.
Теорема Фрэнкла—Вильсона. В парламенте из R депутатов образовано комиссий по n человек в каждой. Если p > 2 простое, R =
= 4p
α
, n = R/2 и k > 2C
R/4−1
R−1
, то обязательно найдутся две комиссии,
имеющие ровно R/4 общих членов. а) Оценка из задачи 2 а) точная (сформулируйте сами, в каком смысле).
б) При каких R, k, n, s в парламенте из R депутатов с k комиссиями по n человек в каждой обязательно найдутся две комиссии, имеющие не менее s общих членов?
Подмножество отрезка [0, 1] называется хорошим, если оно является объединением конечного числа непересекающихся интервалов. Мерой
(длиной) |E| хорошего множества E называется сумма длин его интервалов. а) Если E
1
, . . . , E
k
— непересекающиеся хорошие множества меры каждое и E
0
— хорошее множество меры 1/k, то |E
0
∩ E
j
| > для некоторого б) Придумайте пример бесконечного семейства хороших множеств меры 1/2 каждое, чтобы мера пересечения любых двух из них не превосходила бы в) Тоже для множеств меры 1/k и меры пересечения не более 1/k
2

Оценка Виссера мощности пересечений 2
′
. Лемма Виссера. Если E
1
, . . . , E
k
, . . . ⊂ [0, 1] — хорошие множества меры m каждое, то найдутся i, j, для которых а) |E
i
∩ E
j
| > б) |E
i
∩ E
j
| > в) Тоже для хороших (те. являющихся объединением конечного количества многоугольников с непересекающимися внутренностями) подмножеств единичного квадрата и их меры (определите сами, что это такое).
Задача поясняет роль множителей 0,99 ив лемме Виссера.
4. Теорема Пуанкаре—Каратеодори о возвращении множества) Пусть E ⊂ [0, 1] — хорошее множество положительной меры и f : [0, 1] → [0, 1] — взаимно однозначное отображение, сохраняющее хорошие подмножества и их меры. Тогда существуют сколь угодно большие, для которых |E ∩ f n
(E)| > Здесь через f обозначается я итерация отображения f :
f n
= f ◦ f ◦ . . . ◦ f
|
{z
}
n раз
Для доказательства необходимо также f с n < 0:
f n
= f
−1
◦ f
−1
◦ . . . ◦ f
−1
|
{z
}
|n| раз б) Тоже для взаимно однозначного отображения f круга единичной площади в себя (например, любого движения этого круга, сохраняющего хорошие подмножества и их меры (определите сами, что это такое. Теорема Хинчина. В условиях теоремы Пуанкаре—Каратеодори а) существуют сколь угодно большие n, для которых |E ∩ f n
(E)| б) существует такое (большое) L, что для любого целого M число n из пункта а) можно найти среди чисел M , M + 1, . . . , M + Указания и решения. г) Разобьем всех парламентариев на 400 = 20 · 20 четверок. Занумеруем четверки парами (i, j) целых чисел, 1 6 i, j 6 20. Каждая комиссия будет объединением двадцати четверок. Первая комиссия является объединением четверок (1, j), 1 6 j 6 20. Вообще, я комиссия при 6 i 6 20 является объединением четверок (i, j) по 1 6 j 6 20. А я комиссия при 21 6 j 6 40 является объединением четверок (i, j − 20) по 6 i 6 20. И я комиссия при 41 6 k 6 60 является объединением всех

Гл. 10. Подсчеты в комбинаторике четверок (i, j), в которых i − j − k делится на 20 и 1 6 i, j 6 20. Тогда любые две комиссии имеют менее 5 (более точно, 0 или 4) общих членов.
д) См. Квант, 1997, № 2, с. 24, решение задачи M1566 (этот пример принадлежит Н. Б. Васильеву).
е) Если любые две комиссии имеют не более 2 общих членов, то число всех парламентариев не меньше 40 · 80 − (40 · 39/2) · 2 = 40 · 41 >
> 1600 (это частный случай формулы включений-исключений). Полученное противоречие доказывает нужное утверждение.
ж) Аналогично задачам 2 г) или 2 д) (см. ниже. Утверждение верно даже для R = 1600, n = 80, k = 77.
2. а) Аналогично задаче 1 е).
б) Аналогично задаче 1 е. Найдите наибольшее значение выражения − 1)/[k(k − 1)] по k (где m = в) Примените рассуждение изб) к декартову квадрату парламента
(т. е. к множеству упорядоченных пар, в котором образовано k комиссий, являющихся декартовыми квадратами исходных комиссий.
г) Тоже, что в 2 в, для декартовой N -й степени.
д) См. Квант, 1997, № 2, с. 24, решение задачи M1566 (это решение придумано участниками Всероссийской олимпиады 1996 года, где эта задача предлагалась девятиклассникам под номером 4).
2
′
. Аналогично задаче 2.

ГЛАВА МНОГОМЕРНЫЙ КУБ
Пункты данной главы можно изучать независимо друг от друга.
Для некоторых задач нужно знакомство с биномиальными коэффи- циентами.
Комбинаторика мерного куба (А. Б. Скопенков
0. Расставьте на шахматной доске нескольких коней, чтобы каждый бил четырех других. s)

n + 1
k + 1

=

n k + 1

+

n а n + 1
k + 1
o
= (k + 1)
n n
k + 1
o
+
n n
k o
;
l)
n + 1
k + 1
=
n k + 1
+ (2
n−k
− 1)
n Здесь k

— количество элементных подмножеств элементного множества (другое обозначение C
k n
);
n n
k o
— количество разбиений элементного множества на k непустых подмножеств.
Чтобы определить n
k
, рассмотрим 2
n состояний (узоров) набора из n упорядоченных лампочек (каждая лампочка может быть включена или выключена. Выключателем назовем произвольное подмножество этого набора (неформально говоря, это подмножество состоит из тех лампочек, к которым выключатель подсоединен. Нажатие на выключатель преобразует узор, изменяя на противоположное состояние всех лампочек этого выключателя. Семейство узоров задается данным набором выключателей, если нажатиями на эти выключатели из узора,
в котором ни одна лампочка не светит, можно получить в точности данное семейство узоров. Так вот k
есть количество семейств узоров,
каждое из которых можно задать k выключателями и нельзя задать

Гл. 11. Многомерный куб меньшим числом выключателей. (Научно n
k называется количеством мерных линейных подпространств линейного пространства Z
n
2
.)
∗) Найдите явную формулу для Указание. Пункты l) и ∗) непросты. Если у вас не получается, то оставьте их и возвращайтесь к ним по мере решения следующих. а) Какое наименьшее число партий можно организовать среди n человек, чтобы политические взгляды любых двух были бы различны
(т. е. чтобы для любых двух человек нашлась бы партия, в которую один из них входит, а другой нет (Один человек может входить в несколько партий.)
б) Тридцать три буквы русского алфавита кодируются последовательностями из нулей и единиц длины n. При каком наименьшем n кодирование можно выбрать однозначным?
в) Если при получении сообщения возможна ошибка вне более чем одном разряде, те. если коды различных букв должны отличаться по крайней мере в трех разрядах, то n = 8 разрядов не хватит.
г)* Если возможна ошибка вне более чем двух разрядах, то n = разрядов не хватит.
д)* Найдите наименьшее число разрядов, достаточное для кодирования изв. Имеется табло с n горящими лампочками. Каждый выключатель может быть подсоединен к некоторым лампочкам. При нажатии на кнопку выключателя соединенные с ним лампочки меняют свое состояние горящие тухнут, а негорящие загораются. Какое наименьшее число выключателей необходимо, чтобы можно было зажечь любой набор лампочек (не входящие в этот набор лампочки гореть не должны. а) При фиксированном n число C
k максимально при k = б) На математической олимпиаде предлагалось n задач. Выяснилось, что для каждых двух школьников A и B нашлась задача, которую решили не решили задача, которую решил B, ноне решил Какое максимально возможное количество школьников могло быть при этом условии?
На математическом языке эта задача формулируется так найти максимальное количество элементов в таком семействе подмножеств элементного множества, что ни одно из подмножеств семейства не содержится (собственно) в другом.
в) Какое наименьшее число комитетов можно организовать среди n человек, чтобы для любых двух людей A и B нашелся бы комитет,

содержащий A и не содержащий B?

Структуры наконечном множестве (11). А. Б. Скопенков
277
Занумеруем депутатов числами 1, 2, . . . , n и сопоставим каждому комитету множество депутатов, которые в нем участвуют. На математическом языке предыдущая задача формулируется так какое минимальное количество подмножеств можно выбрать в элементном множестве,
чтобы для любых его элементов A, B нашлось бы выбранное подмножество, содержащее A и не содержащее г) В элементном подмножестве даны подмножества A
1
, . . . , A
k
, состоящие из a
1
, . . . , a элементов соответственно. Если ни одно из них не содержит другое, то+ . . . +
1
C
a k
n
6 1.
Указания
Введем понятие мерного куба, которое, в частности, поможет решить задачу T. Для каждого подмножества множества U
n
= {1, 2, . . . , нарисуем точку. При этом на й этаж поместим точки, соответствующие элементным множествам. Соединим точки отрезком, если одно множество получается из другого добавлением одного элемента. Тогда соединяемые отрезком точки лежат на соседних этажах. Полученный граф называется мерным кубом. Происхождение названия полученная картинка есть изображение вершин куба в мерном пространстве с соединенными отрезком соседними вершинами.
Ответ к задаче A а ⌈log
2
n⌉, где через ⌈x⌉ обозначается наименьшее целое число, не меньшее числа План решения задачи T б. Для любого a существует семейство из подмножеств, удовлетворяющее этому условию. Далее, C
a Назовем цепью подмножеств множества U
n путь снизу вверх от ∅ к на мерном кубе, те. набор (X
0
, X
1
, X
2
, . . . , X
n
), где X
0
= ∅, X
1
=
= {a
1
}, X
2
= {a
1
, a
2
}, . . . , X
n
= {1, . . . , n}. В любой цепи имеется не более одного множества из нашего семейства подмножеств X
1
, . . . , Через подмножество размера a проходит a!(n − a)! 6 [n/2]! · (n − цепей. Всего цепей n!. Поэтому размер искомого семейства не может быть больше, чем n!
[n/2]!(n − [n/2])!
= C
[n/2]
n
1∗) Если наше линейное пространство имеет размерность n, то выбрать в нем независимое подмножество размера k можно 2 0
) · (2
n
− 2 1
) · . . . · (2
n
− 2
k−1
)
способами.
Ответ:
n k
=
(2
n
− 1)(2
n−1
− 1) . . . (2
n−k+1
− 1)
(2
k
− 1)(2
k−1
− 1) . . . (2 1
− 1)

Гл. 11. Многомерный куб
Структуры наконечном множестве
1)
(11)
А. Б. Скопенков
В предыдущей теме рассмотрены некоторые классические и, напер- вый взгляд, различные комбинаторные задачи. На самом деле они являются частными случаями общей проблемы. Цель предлагаемого цикла задач — рассказать об этой и близких проблемах.
Рассмотрим множество U
n целых чисел от 1 до n. Обозначим через множество всех его подмножеств.
Алгеброй на множестве U
n называется семейство его подмножеств,
которое вместе с любыми подмножествами A и B содержит также их объединение A ∪ B, пересечение A ∩ B и дополнение ¯¯
A := U
n
\ A. Например алгебра на U
n
; {∅, {1, 2, 3}} и {∅, {1}, {2, 3}, {1, 2, алгебры на Базисом алгебры называется наименьшее (по включению) ее подсемейство, такое что любой элемент алгебры можно выразить через X
1
. . . X
k с помощью операций пересечения, объединения и дополнения. Задача A a) предыдущего раздела равносильна нахождению наименьшего числа множеств в базисе алгебры 2
U
n
A. 1) Найдите все алгебры на U
1
, и U
3 2) Разбиением множества U
n называется неупорядоченный набор, X
2
, . . . , X
k
} подмножеств X
i
⊂ U
n
, для которого U
n
= X
1
∪ X
2
∪ . . .
. . . ∪ X
k и X
i
∩ X
j
= ∅ при любых i 6= j. Установите взаимно однозначное соответствие между алгебрами на U
n и разбиениями множества U
n
3) Количество элементов произвольной алгебры есть степень двойки) Размеры разных базисов одной алгебры могут быть различны.
Линейным пространством на множестве U
n называется семейство его подмножеств, которое вместе с любыми подмножествами и B содержит также их симметрическую разность A ⊕ B. Например,
любая алгебра является линейным пространством {∅}, {∅, {1, 2}},
{∅, {1}, {2}, {1, 2}} и {∅, {1, 3}, {2, 3}, {1, 2}} — линейные пространства на U
3
. Определение базиса линейного пространства и его связь с задачей из предыдущего раздела аналогичны случаю алгебр. 1) Любое линейное пространство содержит ∅.
2) Найдите все линейные пространства на U
1
, и U
3 3) В линейном пространстве не может быть ровно 3 элемента.
1)
Благодарю Никокошева Илью за полезные обсуждения

Структуры наконечном множестве 4) Количество элементов произвольного линейного пространства есть степень двойки 2
k
. Число k есть размер любого его базиса. Оно называется размерностью линейного пространства. В частности, размеры любых двух базисов данного линейного пространства одинаковы.
Топологией на множестве U
n называется семейство его подмножеств,
которое содержит ∅, U
n и вместе с любыми подмножествами A и содержит также A ∩ B, A ∪ B. Например, любая алгебра является топологией и {∅, {1}, {2}, {1, 2}, {1, 3}{1, 2, 3}} топологии на U
3
. Определение базиса топологии и его связь с задачей Т виз предыдущего раздела аналогичны случаю алгебр. 1) Найдите все топологии на U
1
, и U
3
. Убедитесь, что существует топология, число элементов которой не является степенью двойки) Любая ли топология является линейным пространством Можно ли симметрическую разность выразить через пересечение и объединение Задача 1*. а) Найдите рекуррентную формулу для числа всех алгебр (числа Белла) Для числа N
L
(n) линейных пространств докажите N
L
(2n) ∼
∼ C · 2
n
2
t) Найдите количество топологий на элементном множестве (нерешенная задача. Цепью топологий называется такая последовательность топологий между любыми двумя соседними членами которой нельзя вставить еще одну топологию (те. для любого i не существует топологии B, для которой. Аналогично определяются цепи алгебр и линейных пространств) Все цепи алгебр (линейных пространств) имеют одинаковую длину (какую) Приведите пример цепей топологий различной длины, 4) Найдите наибольшую длину D
+
T
(n) и наименьшую длину) цепей топологий. l) Шириной W
L
(n) (семейства всех линейных пространств на называется максимальное количество элементов линейных пространств,
ни одно из которых не содержится (собственно) в другом. Найдите

Гл. 11. Многомерный куба) Найдите W
A
(n).
t)* Найдите W
T
(n) (нерешенная задача. Базой на множестве U
n называется семейство его подмножеств, которое содержит U
n и вместе с любыми подмножествами и B содержит также A ∩ B. Примеры баз любая топология, 2}, {2, 3}, {2}, U
4
} — база на U
4 5. Структурой на множестве U
n называется семейство его подмножеств, которое замкнуто относительно некоторого заданного набора операций. Например, если заданный набор операций пуст, то решетка структур совпадает с мерным кубом. Определение базиса структуры и ее других характеристик аналогичны случаю алгебр.
Решите для других типов структур аналоги приведенных выше задач. Полный список различных типов структур называется решеткой
Поста.
Указания
A. 2) Разбиению U
n
= X
1
∪ X
2
∪ · · · ∪ X
k поставьте в соответствие семейство всех множеств, полученных объединением некоторых из, . . . , X
k
3) Следует из задачи A 2).
4) Рассмотрите алгебру и два базиса, один — из множеств {1, и {1, 3}, другой — из множеств {1}, {2}, {3}.
L. 4) Докажите существование какого-либо базиса.
Введем определения, которые пояснят связь между различными разделами задачи, а также помогут решить их.
Нарисуем все алгебры (на U
n
— эти слова мы дальше опускаем. Проведем стрелку от алгебры A к алгебре B, если A ( B и между ними нельзя вставить никакую другую алгебру. Полученный граф называют решеткой алгебр.
Разбиение H = H
0
⊔ H
1
⊔ . . . ⊔ H
m множества всех алгебр называется разбиением на этажи, если для любых двух соединенных стрелкой алгебр A ⊂ B номер этажа алгебры A на единицу меньше номера этажа алгебры Ясно, что решетка алгебр допускает разбиение на этажи. (Какие алгебры находятся нам этаже?)
Аналогично случаю алгебр вводятся понятия решетки линейных пространств и ее разбиения на этажи. Ясно, что решетка линейных пространств допускает разбиение на этажи. (Какие линейные пространства находятся нам этаже

Теорема Поста о выразимости для функций алгебры логики
281
Аналогично случаю алгебр вводится понятие решетки топологий.
Можно определить также понятие ее разбиения на этажи. Но оказывается, что решетка топологий не допускает разбиения на этажи.
Ответы: D
A
(n) = D
L
(n) = n + 1, D
+
T
(n) = 2n + 2, D
B
(n) = 2
n
+ Теорема Поста о выразимости для функций алгебры логики (АИ. Засорин, А. Б. Скопенков
В этом разделе латинскими буквами обозначаются элементы множества. Введем обозначения =
(
1, при a = 0,
0, при a = логическое не ∨ b =
(
1, при a = 1 или b = 1,
0, в противном случае
(логическое или & b =
(
1, при a = 1 ив противном случае
(логическое и ⊕ b =
(
1, при a = b,
0, в противном случае
(сумма по модулю 2, или XOR).
1. а) a ∨ b = б) (a ∨ b) & c = (a&c) ∨ (b & c).
2. Выразите а) x & y через x и ∨; б) x ⊕ y через x, & и Если неясно, что значит выразить, то см. ниже определение суперпозиции. В процессе выражения одних функций через другие в функцию можно подставлять вместо некоторых переменных одну и туже (те. отождествлять переменные).
Условимся не писать &, например, записывать (x & y & z) ∨ (a & как xyz ∨ ab.
3. Докажите, что через x и & можно выразить:
а) x ∨ б) x ⊕ в) x|y, где 1|1 := 0 и x|y := 1, если хотя бы одно из x, y равно нулю;
г) x ↿ y, где 0 ↿ 0 := 1 и x ↿ y := 0, если хотя бы одно из x, y равно единице;
д) x 6 y, где (x 6 y) := 1 тогда и только тогда, когда x 6 е) каждую функцию f : Z
2 2
→ двух переменных

Гл. 11. Многомерный куб. Выразите через &, ∨ и x функцию трех переменных f : Z
3 2
→ которая а) равна 1 на наборе (0, 1, 0) и равна 0 на остальных наборах;
б) равна 1 на наборах (0, 1, 0), (1, 1, 1) и равна 0 на остальных наборах в) произвольна. Докажите, что каждую функцию f : Z
n
2
→ можно выразить через аи б) & ив и 1, где 1(x) := г) |.
6. Докажите, что всякая функция f : Z
n
2
→ единственным образом представляется полиномом Жегалкина — суммой по модулю два мо- номов, те. неповторяющихся произведений переменных, причем в каждом мономе все переменные различны. При этом 1 считается мономом,
в котором нет множителей. Константу 0 по определению выражает пустой полином Жегалкина.
7. Можно ли выразить каждую функцию f : Z
n
2
→ через аи б) ∨ ив и гид и е) g(x, y, z) = xy ∨ xz ∨ yz и Пусть дано некоторое множество функций F = {f
α
(x
1
, . . . , x необязательно конечное. Определим понятие суперпозиции функций из F (или формулы над F ) индуктивно.
1) Сами функции f и все переменные x являются суперпозициями функций из F .
2) Если функции f (x
1
, . . . , x n
), g
1
(. . .), . . . , g n
(. . .) являются суперпозициями функций из F (необязательно различными, то и функция f (g
1
(. . .), . . . , g n
(. . .)) является суперпозицией функций из F Суперпозицию можно также определить графически, на языке схем. Если брать только f ∈ F (а непроизвольную суперпозицию f функций из F ), то получится эквивалентное определение. Отображения (функции) называются равными, если их значения совпадают при всех значениях переменных. Примеры равных отображений см. в задаче а) Сколько различных отображений f : Z
n
2
→ Переменная называется несущественной для отображения f : Z
n
2
→ Z
2
, если для любых x
2
, . . . , x n
∈ выполнено f (0, x
2
, . . . , x n
) =

Теорема Поста о выразимости для функций алгебры логики f (1, x
2
, . . . , x n
). Аналогично определяется несущественность переменной. Отображения Z
n
2
→ называются эквивалентными, если они становятся равными после переименования переменных,
добавления и изъятия несущественных переменных. Классы эквивалентности называются функциями алгебры логики. Далее функциями называются не функции-отображения, а функции алгебры логики.