Редактирование: Основы Кибернетики, 02 лекция (от 16 февраля)
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 11: | Строка 11: | ||
* ДНФ ΣT = k1 V k2 V k3 V k4 V k5 ≠ a | * ДНФ ΣT = k1 V k2 V k3 V k4 V k5 ≠ a | ||
- | Пусть | + | Пусть етсь f(x1 ... xn), α ∈ Nf ⇒ Пα(f) — множество проходящих граней f, проходящих через a — пучок f через точку a. |
Определение. α ∈ Nf — регулярная точка функции f ⇔ ∃ &betta; ∈ Nf: П&betta;(f) ∈ Пα(f), &betta; не является регулярной. | Определение. α ∈ Nf — регулярная точка функции f ⇔ ∃ &betta; ∈ Nf: П&betta;(f) ∈ Пα(f), &betta; не является регулярной. | ||
Строка 19: | Строка 19: | ||
α0 — регулярная точка g‘ | α0 — регулярная точка g‘ | ||
- | Любая ядровая точка не | + | Любая ядровая точка не явл регулярной. |
α3, α7, α0, α4, α5, α1, α6, α2 — регулярнгые вg‘ | α3, α7, α0, α4, α5, α1, α6, α2 — регулярнгые вg‘ | ||
Строка 27: | Строка 27: | ||
6, 7 состоят только из регулярных точек. Поэтому они являются реглярными гранями. | 6, 7 состоят только из регулярных точек. Поэтому они являются реглярными гранями. | ||
- | Грань регулярна ⇔ все её | + | Грань регулярна ⇔ все её отчки регулярны. |
- | Сумма тупиковых соответствует всем | + | Сумма тупиковых соответствует всем нерег граням. |
Утверждение 3.2. Простая импликанта K ФАЛ f входит в ДНФ ΣT ⇔ соответствующая ей NK не является регулярной. | Утверждение 3.2. Простая импликанта K ФАЛ f входит в ДНФ ΣT ⇔ соответствующая ей NK не является регулярной. | ||
Строка 35: | Строка 35: | ||
Это позволяет строить ДНФ ΣT, не находя все тупиковые ДНФ, а только проверяя все грани на регулярность. | Это позволяет строить ДНФ ΣT, не находя все тупиковые ДНФ, а только проверяя все грани на регулярность. | ||
- | + | Докво. 1) Nk — регулярная грань ⇒ K ∉ ДНФ ΣT | |
Пусть NK = {α1, ..., αs} ⇒ ∀ αi ∃ &betta;i: П&betta;(f) ∈ П αi(f); &betta;i нерегулярная ⇒ &betta;i ∉ NK | Пусть NK = {α1, ..., αs} ⇒ ∀ αi ∃ &betta;i: П&betta;(f) ∈ П αi(f); &betta;i нерегулярная ⇒ &betta;i ∉ NK | ||
Строка 60: | Строка 60: | ||
Только K накрывает α Kj не принадлежит пучку альфа, поэтому она альфа не покрывает. Поэтому при переходе к K‘ мы K потерять не можем. | Только K накрывает α Kj не принадлежит пучку альфа, поэтому она альфа не покрывает. Поэтому при переходе к K‘ мы K потерять не можем. | ||
- | ч.т.д. - первая теорема Журавлёва | + | ч. т. д. - первая теорема Журавлёва |
== Локальность просмотренных методов, алгоритмов, приёмов построения суммы тупиковых ДНФ и тупиковых ДНФ == | == Локальность просмотренных методов, алгоритмов, приёмов построения суммы тупиковых ДНФ и тупиковых ДНФ == | ||
Строка 78: | Строка 78: | ||
ΣM — объединение всех минимальных ДНФ | ΣM — объединение всех минимальных ДНФ | ||
- | Для них | + | Для них окр-ти второго порядка уже недостаточно. |
= 4. Особенности ДНФ для ФАЛ из некоторых классов (линейные ФАЛ, монотонные ФАЛ и др.). Теореме Журавлёва о ДНФ ΣM (2-я теор Журавлёва) = | = 4. Особенности ДНФ для ФАЛ из некоторых классов (линейные ФАЛ, монотонные ФАЛ и др.). Теореме Журавлёва о ДНФ ΣM (2-я теор Журавлёва) = | ||
Строка 125: | Строка 125: | ||
K&betta;‘+ <= K&bettal;‘‘+ ⇒ &betta;‘ >= &betta;‘‘ ⇒ &betta;‘ ∈ NK&betta;‘‘+ | K&betta;‘+ <= K&bettal;‘‘+ ⇒ &betta;‘ >= &betta;‘‘ ⇒ &betta;‘ ∈ NK&betta;‘‘+ | ||
- | f — монот ФАЛ. Тогда α — «нижняя» 1 f ⇔ α ∈ Nf и ∀ &betta; <= α, &betta; != α ⇔ f(b) = 0 ⇒ Nf+ — множество всех нижних «1» | + | f — монот ФАЛ. Тогда α — «нижняя» 1 f ⇔ α ∈ Nf и ∀ &betta; <= α, &betta; != α ⇔ f(b) = 0 ⇒ Nf+ — множество всех нижних «1» монот ФАЛ f |
4.2 Сокр ДНФ a монот ФАЛ f является единств тупик ДНФ и имеет вид a = V_&betta; ∈ Nf+ K_&betta;^+, причём все наборы из Nf+ являются ядровыми точками f, и все max грани — ядр. гранями. | 4.2 Сокр ДНФ a монот ФАЛ f является единств тупик ДНФ и имеет вид a = V_&betta; ∈ Nf+ K_&betta;^+, причём все наборы из Nf+ являются ядровыми точками f, и все max грани — ядр. гранями. | ||
Строка 136: | Строка 136: | ||
Пример: функция голосования. Сокр ДНФ H = x1x2 v x1x3 v x2x3 | Пример: функция голосования. Сокр ДНФ H = x1x2 v x1x3 v x2x3 | ||
- | последнее семейство | + | последнее семейство ф-ций, к-рые мы рассмотрим: цепные или циклические функции. На ед кубе их еж значенияф сост из рёбер, к-рые орг циклы. |
f ∈ P2(n) — цепная (циклическая) ФАЛ длины t ⇔ Сокр ДНФ f представляет собой цепь (цикл) из t рёбер куба Bn. | f ∈ P2(n) — цепная (циклическая) ФАЛ длины t ⇔ Сокр ДНФ f представляет собой цепь (цикл) из t рёбер куба Bn. | ||
Строка 162: | Строка 162: | ||
(100..0), (1100.0), ... (1...1)(01...1)...(0...01) | (100..0), (1100.0), ... (1...1)(01...1)...(0...01) | ||
- | Задачи для самостоятельного решения. Принести в 617. Кто-то из | + | Задачи для самостоятельного решения. Принести в 617. Кто-то из преподов должен зафиксировать дату и время и оставить в папке для лектора. Тот, кто первый решит, освобождается от задачи на ДНФ. |
- | 1. Построить функцию с | + | 1.Построить функцию с мин числом булевских переменных, длина сокр днф которой превосходит длину соврешенной днф этой же функции. |
- | 2. Построить функцию с | + | 2.Построить функцию с мин числом булевских переменных, ни одна кратчайшая ДНФ не является минимальной ДНФ и ни одна минимальная не явл кратчайщей. |
{{Основы Кибернетики}} | {{Основы Кибернетики}} | ||
+ | {{Lection-stub}} |