19032001 (1109976)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

19 марта 2001 г.

Итак, продолжим доказательство утверждения. Через функцию мы обозначаем ту существенную функцию, которая принадлежит нашей системе. Было выяснено, что существует квадрат (в последнем столбце стоят значения на соответствующих наборах), такой что на нем некоторое значение принимает ровно один раз (это означает, что ), и была рассмотрена функция . Пусть , , , и . Нарисовав таблицу на наборах из и , можно убедиться в том, что она ведет себя, как дизъюнкция для двух переменных:

.

Обозначим ее через . Напомним, что у нас есть, поскольку принимает только два значения.

,

таким образом получена функция, которая ведет себя, как конъюнкция, на наборах из и .

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

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

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

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

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

Определение. Функция называется функцией Шеффера, если система, состоящая только из этой функции, полная.

Критерий. - функция Шеффера порождает все функции от одной переменной, принимающие значение.

Доказательство критерия.

Тривиально. Т.к. эта функция порождает вообще все функции.

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

Утверждение. Система полная - простое число.

Имеет место быть аналогичное утверждение в случае, когда – степень простого числа, ибо тогда можно рассмотреть поле Галуа из элементов (существование такого поля доказывается в курсе алгебры) и операции сложения и умножения в нем, которые вместе с константами будут образовывать полную систему – там все функции полиномиальны.

Доказательство. Сначала докажем малую теорему Ферма.

Лемма. Если – простое число, а , то .

Доказательство леммы. Рассмотрим все ненулевые остатки от деления на . Умножим каждый из них на . Утверждается, что снова получаются все ненулевые остатки. Действительно, если , то , откуда уже следует , поскольку . Но мы знаем, что , и единственная возможность для - это . Следовательно, все произведения разные, их всего , равно как и различных остатков. Поэтому их множества совпадают. Если теперь перемножить все ненулевые остатки, с одной стороны, получим , а с другой, . Значит, , и, если учесть, что , получим, что .

. Пусть . Из равенств , если , следует, что , а подставив вместо в , получим , откуда . Наконец .

Доказательство будет закончено на следующей лекции.

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

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

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов лекций