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

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

19 февраля 2001 г.

Определение. Система функций называется полной, если любая функцию алгебры логики выражается формулой над .

Пример. В конце прошлой лекции мы доказали, что является полной системой.

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

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

Теорема. Из любой полной системы можно выделить конечную полную подсистему.

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

Используя достаточное условие полноты, построим еще несколько полных систем:

1) система - полная. Действительно то, что конъюнкция и отрицание выражается формулой над этой системой – очевидно. Т.к. , то и дизъюнкция выражается формулой над этой системой, следовательно эта система полная;

2) система - полная. Аналогично, т.к. ;

3) система - полная. Действительно, конъюнкция выражается формулой над этой системой, отрицание тоже. Т.к. система - полная, то и эта система полная;

4) система (штрих Шеффера) – полная. Выразим отрицание и конъюнкцию через штрих Шеффера: и . Следовательно штрих Шеффера является полной системой (состоящей из одной функции!). Существует еще одна функция, образующая полную систему, - это - стрелка Пирса (доказательство аналогичное).

Мы получили, что следующие системы являются полными:

.

ПОЛИНОМ ЖЕГАЛКИНА

Рассмотрим конъюнкции нескольких переменных , где все - разные, также мы будем рассматривать конъюнкции длины 1, т.е. сами переменные и константу 1.

Определение. Сумма по модулю два таких попарно различных конъюнкций, т.е. называется полиномом Жегалкина. Пустой полином Жегалкина по определению выражает нулевую функцию.

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

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

1) представимость. Т.к. - полная система, то любая функция представима формулой над . Представим ее в виде полинома Жегалкина:

а) если какая-нибудь сумма умножается на что-нибудь, то применим дистрибутивный закон, т.е. , так, раскрыв все скобки, можно добиться нужного нам вида (суммы произведений) - ;

б) ликвидация повторяющихся переменных. Т.к. , то, если в каком-либо произведении встречаются повторяющиеся переменные, то мы можем лишние убрать и оставить только один экземпляр;

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

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

В итоге мы получим полином Жегалкина, т.е. любая функция представима в виде полинома Жегалкина.

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

Рассмотрим специальные полиномы Жегалкина, состоящие из произведений длины не выше 1, т.е. функции вида , и может быть еще и . Функции, представимые полиномом Жегалкина такого вида, называются линейными.

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

Примеры.

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

2) если же , то замыкание - это просто множество всех линейных функций. Т.е., если - множество всех линейных функций, то .

Напишем некоторые свойства операции замыкания:

1) ;

2) если , то ;

3) ;

4) ;

5) если - полная система, то .

Определение. Множество называется замкнутым, если .

Пример. Множество является замкнутым. Это множество к тому же не тривиально, т.е. не пусто и не совпадает с .

Лемма о нелинейной функции. Из любой нелинейной функции, подставляя вместо некоторых переменных константы, и может быть отрицание переменных, и может быть навешивая отрицание на результат, можно получить конъюнкцию двух переменных.

Доказательство. Пусть , тогда в ее полиноме Жегалкина есть произведение длины большей 1 (нелинейные произведения). Возьмем самое короткое из них, переставим его на первое место , . Каждое другое нелинейное произведение содержит хотя бы одну переменную, отличную от . Вместо всех переменных, кроме подставим ноль, тогда все остальные нелинейные конъюнкции обратятся в ноль и останется , где - это линейная функция от переменных . Оставим первые две переменные, а вместо остальных (если они есть) подставим 1, получим . Сделаем следующую подстановку: вместо (это будет либо , либо ), и прибавим ко всей функции , т.е. либо ничего не изменим, либо навесим отрицание на результат. В итоге получится следующая функция:

Следствие. Если , то .

Приведем также еще несколько замкнутых классов функций:

1) Класс функций, т.ч. . Очевидно что это множество не тривиально, т.е. не пусто и не совпадает с , докажем, что оно замкнуто. Очевидно, что сами переменные принадлежат этому множеству, т.к. если , то . Поэтому нам достаточно доказать, что если и , то и . Т.к. ,то

. Следовательно класс функций замкнут;

2) Класс функций, т.ч. . Этот класс также не тривиален и замкнут.

Пусть дана произвольная функция , функция называется двойственной функцией к .

Примеры:

Как видно из примеров, иногда бывает, что , такие функции называются самодвойственными. Множество всех самодвойственных функций обозначается . Очевидно, что множество не тривиально, докажем, что оно замкнуто:

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

, т.к. .

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

Лемма о несамодвойственной функции. Пусть , тогда, подставляя в нее вместо переменной переменную или ее отрицание , можно получить константу.

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

Следствие. Если , то замыкание содержит в себе обе константы.

Доказательство. Одну какую-то константу оно содержит по предыдущей лемме, но т.к. у нас есть операция отрицания, то мы можем получить и вторую константу.

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

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

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

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

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

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