12032001 (1109973)

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

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

12 марта 2001 г.

Определение. – существенная функция, если

1) число переменных, от которых она существенно зависит,

2) принимает значений.

Утверждение. Пусть содержит все функции от одной переменной. Тогда полна содержит существенную функцию.

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

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

Будет доказано для случая Слупецкого.

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

Докажем для случая Яблонского, а значит и для случая Слупецкого.

Нам понадобится

Лемма о трех наборах. Пусть

1) существенно зависит от переменных (например, от и какой-нибудь еще)

2) принимает значения.

Тогда существуют три набора , и , такие что , т.е. значения функции на этих наборах различны.

Заметим, что наборы выбраны так, что в матрице, три строки которой суть наши наборы, в каждом столбце не более двух разных элементов:

Еще следует отметить, что при таких условиях набор не может совпадать с набором , поскольку тогда было бы , но . Это значит, что для некоторого .

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

Поскольку существенно зависит от первой переменной, то существуют и , такие что . Рассмотрим наборы . на этих наборах принимает хотя бы 2 значения.

Тут различаются две возможности. Если она на них принимает ровно 2 значения, то третье она принимает на каком-то , а значит, можно рассмотреть , для которого заведомо из-за выбора , и тогда найдется , такое что на наборе принимает оставшееся значение из тех двух, которые она принимает на наборах . Три набора , , удовлетворяют условиям леммы.

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

Определение. Квадрат – это четыре набора

, причем , .

Лемма о квадрате. Пусть существенно зависит от переменных, принимает значения. Тогда существует квадрат, на котором эта функция некоторое значение принимает ровно один раз.

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

Очевидно, удовлетворяет условиям леммы о трех наборах. Пусть , , - такие наборы, что первые три те, существование которых следует из леммы о трех наборах, а четвертый построен по ним очевидным образом. Пусть на первых трех принимает разные значения , а на четвертом , возможно, совпадающее с некоторым из первых трех. Беда с этими четырьмя наборами в том, что они – не квадрат. Но можно постепенно переходить от одного квадрата к другому, шагая только по квадратам, и тогда окажется, что мы обязательно пройдемся по квадрату, удовлетворяющему условиям леммы. Отправным квадратом послужит следующий:

,

стремиться мы будет к квадрату:

,

на каждом шаге проделывая замену:

,

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

,

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

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

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

Итак, рассмотрим еще раз наборы, образующие квадрат, на котором какое-то значение, скажем, , принимается ровно один раз:

, ,

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

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

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

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

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

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

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

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