26022001 (1109978)

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

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

26 февраля 2001 г.

Введем правило сравнения двух наборов. Будем говорить, что , если . При этом мы считаем, что , , , . Теперь мы можем упорядочить все наборы: .

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

Примеры:

1) функции монотонны (это видно из таблицы),

2) функции не монотонны.

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

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

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

Мы получили, что если , то .

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

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

если содержится в каком-либо из этих множеств, например, , то , т.е. система не полная.

Т.к. , то . Аналогично , где все принадлежат системе (некоторые из них могут и совпадать).

1) получение констант. Возьмем функцию , т.е. , рассмотрим , тогда . Если , то это константа 1, а функция - константа 0. Если , то это отрицание, и тогда, по лемме о несамодвойственной функции, при помощи отрицания можно получить обе константы, т.е. . Мы получили обе константы.

2) получение отрицания. По лемме о немонотонной функции, при помощи констант можно получить отрицание, т.е. .

3) получение конъюнкции. По лемме о нелинейной функции, при помощи констант и отрицания можно получить конъюнкция, т.е. .

Мы получили, что содержит в себе полную систему, следовательно система полная.

Следствие. Из любой полной системы можно выделить полную подсистему, состоящую из пяти функций.

Доказательство. Достаточно взять функции .

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

Покажем, что это число в общем случае уменьшить нельзя. Рассмотрим систему , напишем таблицу, в которой укажем, каким из классов они принадлежат (будем ставить , если принадлежит и -, если не принадлежит):

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

Лемма. Для любых двух классов (из пяти нами рассмотренных ранее) существует функция принадлежащая одному и не принадлежащая другому.

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

, где функция - это

Очевидно, что - самодвойственная функция, она нелинейная, т.к., подставив вместо константу , мы получим конъюнкцию – нелинейную функцию.

Теорема. Пусть - замкнутый класс и , тогда содержится в одном из пяти классов .

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

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

1) ,

2) ,

3) имеем .

Теорема. В множестве всех функций алгебры логики существует равно пять предполных классов: .

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

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

В алгебре логики имеется счетное количество замкнутых классов.

ФУНКЦИИ -ЗНАЧНОЙ ЛОГИКИ

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

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

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

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

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

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

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

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