Редактирование: Основы Кибернетики, 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.
+
Пусть етсь 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
+
Докво. 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;‘‘+ &rArr; &betta;‘ >= &betta;‘‘ &rArr; &betta;‘ &in; NK&betta;‘‘+
K&betta;‘+ <= K&bettal;‘‘+ &rArr; &betta;‘ >= &betta;‘‘ &rArr; &betta;‘ &in; NK&betta;‘‘+
-
f &mdash; монот ФАЛ. Тогда &alpha; &mdash; «нижняя» 1 f &hArr; &alpha; &in; Nf и &forall; &betta; <= &alpha;, &betta; != &alpha; &hArr; f(b) = 0 &rArr; Nf+ &mdash; множество всех нижних «1» монотонных ФАЛ f
+
f &mdash; монот ФАЛ. Тогда &alpha; &mdash; «нижняя» 1 f &hArr; &alpha; &in; Nf и &forall; &betta; <= &alpha;, &betta; != &alpha; &hArr; f(b) = 0 &rArr; Nf+ &mdash; множество всех нижних «1» монот ФАЛ f
4.2 Сокр ДНФ a монот ФАЛ f является единств тупик ДНФ и имеет вид a = V_&betta; &in; Nf+ K_&betta;^+, причём все наборы из Nf+ являются ядровыми точками f, и все max грани &mdash; ядр. гранями.
4.2 Сокр ДНФ a монот ФАЛ f является единств тупик ДНФ и имеет вид a = V_&betta; &in; Nf+ K_&betta;^+, причём все наборы из Nf+ являются ядровыми точками f, и все max грани &mdash; ядр. гранями.
Строка 136: Строка 136:
Пример: функция голосования. Сокр ДНФ H = x1x2 v x1x3 v x2x3
Пример: функция голосования. Сокр ДНФ H = x1x2 v x1x3 v x2x3
-
последнее семейство функций, которые мы рассмотрим: цепные или циклические функции. На единичном кубе их еж значения состоят из рёбер, которые организуют циклы.
+
последнее семейство ф-ций, к-рые мы рассмотрим: цепные или циклические функции. На ед кубе их еж значенияф сост из рёбер, к-рые орг циклы.
f &in; P2(n) &mdash; цепная (циклическая) ФАЛ длины t &hArr; Сокр ДНФ f представляет собой цепь (цикл) из t рёбер куба Bn.
f &in; P2(n) &mdash; цепная (циклическая) ФАЛ длины t &hArr; Сокр ДНФ 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}}

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Личные инструменты
Разделы