 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Лемма 1 для доказательства теоремы о конечности дерева достижимости сети Петри
Лемма 1. Во всяком корневом ориентированном бесконечном дереве, в котором каждая вершина имеет конечное число непосредственно последующих вершин, существует бесконечный путь, исходящий из корня.
Доказательство.
Начнем с корня х 0. Поскольку эта вершина имеет конечное число непосредственно последующих вершин, то найдется одна или более вершин, непосредственно следующих за х 0 и являющаяся корнем бесконечного поддерева. Пусть это будет
вершина x 1. Повторяя рассуждения, получим х 2 и т.д. Получим х 0, х 1,x 2, x 3,... – бесконечный путь, исходящий из корня.
Лемма 2 для доказательства теоремы о конечности дерева достижимости сети Петри.
Определение. Расширенным множеством натуральных чисел будем называть множество натуральных чисел, дополненное символом ω.
Лемма 2. Всякая бесконечная последовательность из расширенного множества натуральных чисел содержит бесконечную неубывающую под последовательность.
Доказательство. Возможны два случая:
Если какой-либо элемент последовательности х0 встречается бесконечно часто, то последовательность х 0, x 0, x 0,... является бесконечной неубывающей подпоследовательностью. Пусть любой элемент последовательности встречается конечное число раз и х 0 – произвольный элемент последовательности, отличный от ω. Очевидно, что в последовательности имеется не более чем х 0 различных элементов, меньших чем х 0. Каждый из указанных элементов встречается конечное число раз. Тогда общее число элементов, меньших х0, конечно, а последовательность бесконечна.
Следовательно, в последовательности существует элемент x 1,отличный от ω, такой, что x 1 ≥ x 0.
Аналогично должен существовать в последовательности элемент x 2 ≥ x 1 и т.д.
Получаем бесконечную неубывающую последовательность
x 0 ≤х 1 ≤x 2 ≤x 3 ≤..., что и требовалось доказать.
Лемма 3 для доказательства теоремы о конечности дерева достижимости сети Петри.
Лемма 3. Всякая бесконечная последовательность n-мерных векторов над расширенным множеством натуральных чисел содержит бесконечную неубывающую подпоследовательность.
Доказательство. Доказываем индукцией по n, где n – размерность векторного пространства.
1. Случай n =1 это лемма 2.
2. Допустим, что лемма верна для размерности n, докажем ее справедливость для n+1.
Сопоставим каждому (n +1) - мерному вектору из последовательности n-мерный вектор, полученный удалением последней координаты. По предположению индукции, из полученной последовательности n-мерных векторов можно извлечь
неубывающую подпоследовательность. Добавим теперь к элементам этой подпоследовательности (n+1)-ю координату из исходной последовательности. Выбрав из полученной последовательности (n+1) - х координат неубывающую последовательность в соответствии с леммой 2, получим «подподпоследо-вательность» исходной последовательности с нужными свойствами.
Поиск по сайту: