05032001 (1109969)

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

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

5 марта 2001 г.

В двухзначной алгебре логики имеет место следующее

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

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

Однако в -значной логике это утверждение неверно. Рассмотрим функцию, заданную следующей таблицей:

.

Эта функция обладает тем свойством, что и , если . Тогда имеем, что , потому что .

Интересными для рассмотрения функциями в -значной логике являются:

• константы

• тождественная функция

аналоги отрицания в :

аналоги функции в :

аналоги конъюнкции в :

• (далее: &)

аналог дизъюнкции в :

• (далее: )

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

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

Доказательство. В Имеет место аналог СДНФ:

.

Действительно, подставим в и проверим равенство

.

Если = , то = , т.к. - максимальному возможному значению. Если же , то найдется , т.ч. , тогда - наименьшему возможному значению, следовательно, , значит наша формула верна.

Следствие. Для любого k в существуют полные конечные системы.

Утверждение. Для любого k можно обойтись двумя функциям. Система полная.

Для доказательства нам потребуется

Лемма. Если полная и любая функция системы реализуется формулой над , то полная.

Доказательство этой леммы точно такое же, как и в случае .

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

Утверждение. Система полная. Функция называется функцией Вебба и является аналогом штриха Шеффера в .

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

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

Доказательство. Это следует из того, что существуют полные конечные системы.

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

1)

2)

3) для любой система полная.

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

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

Обозначим - количество предполных классов в . С. В. Яблонский показал, что при их ровно 18, при возрастании количество предполных классов растет очень быстро:

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

В заключение можно предложить алгоритм распознавания полноты. Пусть . Возьмем две переменные и построим последовательность индуктивно во следующему правилу:

1) пустое

2) , где – либо , либо , либо функция из .

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

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

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

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

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

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

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