Редактирование: Основы кибернетики, Теормин
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
ПРЕДУПРЕЖДЕНИЕ: Длина этой страницы составляет 61 килобайт. Страницы, размер которых приближается к 32 КБ или превышает это значение, могут неверно отображаться в некоторых браузерах. Пожалуйста, рассмотрите вариант разбиения страницы на меньшие части.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 33: | Строка 33: | ||
* ''t''<sup>ОС</sup>: ''x''<sub>1</sub> & ''x''<sub>2</sub> ∨ <span style="border-top:solid 1px">''x''</span><sub>1</sub> & ''x''<sub>3</sub> = ''x''<sub>1</sub> & ''x''<sub>2</sub> ∨ <span style="border-top:solid 1px">''x''</span><sub>1</sub> & ''x''<sub>3</sub> ∨ ''x''<sub>2</sub> & ''x''<sub>3</sub> | * ''t''<sup>ОС</sup>: ''x''<sub>1</sub> & ''x''<sub>2</sub> ∨ <span style="border-top:solid 1px">''x''</span><sub>1</sub> & ''x''<sub>3</sub> = ''x''<sub>1</sub> & ''x''<sub>2</sub> ∨ <span style="border-top:solid 1px">''x''</span><sub>1</sub> & ''x''<sub>3</sub> ∨ ''x''<sub>2</sub> & ''x''<sub>3</sub> | ||
- | |||
- | Расширение U' ДНФ U считается ''строгим'', если U' содержит ЭК, не являющуюся импликантой ни одной ЭК из U. | ||
=== Формулировка утверждения, связанного с построением сокращенной <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> из какой-либо <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> === | === Формулировка утверждения, связанного с построением сокращенной <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> из какой-либо <span title="дизъюнктивная нормальная форма" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ДНФ</span> === | ||
Строка 94: | Строка 92: | ||
=== Определение <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> покрытия матрицы и ее свойства, утверждение о КНФ для <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> покрытия === | === Определение <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> покрытия матрицы и ее свойства, утверждение о КНФ для <span title="функция алгебры логики" style="text-decoration:none; border-bottom:1px dotted #C0C0C0;">ФАЛ</span> покрытия === | ||
* Пусть N = {α<sub>1</sub>,...α<sub>s</sub>,} - конечное множество, а П = (N<sub>1</sub>,...,N<sub>p</sub>) - система его подмножеств, образующих покрытие множества N. Сопоставим паре (N,П) матрицу M ∈ B<sup>p,s</sup>, для которой M<nowiki><i,j></nowiki> = 1 ⇔ α<sub>j</sub> ∈ N<sub>i</sub>. Будем говорить, что i-я строка матрицы М ''покрывает'' ее j-й столбец, если M<nowiki><i,j></nowiki> = 1 и что система строк с номерами из I, I ⊆ [1,p], образует ''покрытие матрицы М'', если каждый ее столбец покрывается хотябы одной строкой с номером из I, то есть система подмножеств {N<sub>i</sub>}<sub>i ∈ I</sub> задает покрытие множества N. | * Пусть N = {α<sub>1</sub>,...α<sub>s</sub>,} - конечное множество, а П = (N<sub>1</sub>,...,N<sub>p</sub>) - система его подмножеств, образующих покрытие множества N. Сопоставим паре (N,П) матрицу M ∈ B<sup>p,s</sup>, для которой M<nowiki><i,j></nowiki> = 1 ⇔ α<sub>j</sub> ∈ N<sub>i</sub>. Будем говорить, что i-я строка матрицы М ''покрывает'' ее j-й столбец, если M<nowiki><i,j></nowiki> = 1 и что система строк с номерами из I, I ⊆ [1,p], образует ''покрытие матрицы М'', если каждый ее столбец покрывается хотябы одной строкой с номером из I, то есть система подмножеств {N<sub>i</sub>}<sub>i ∈ I</sub> задает покрытие множества N. | ||
- | * Пусть M ∈ B<sup>p,s</sup> - матрица без нулевых столбцов. Сопоставим i-й строке матрицы М БП y<sub>i</sub>, а каждому набору β ∈ B<sup>p</sup> значений этих переменных y = (y<sub>1</sub>,...,y<sub>p</sub>) - множество строк матрицы М с | + | * Пусть M ∈ B<sup>p,s</sup> - матрица без нулевых столбцов. Сопоставим i-й строке матрицы М БП y<sub>i</sub>, а каждому набору β ∈ B<sup>p</sup> значений этих переменных y = (y<sub>1</sub>,...,y<sub>p</sub>) - множество строк матрицы М с намерами из множества I = I(β) ⊆ [1,p], где i ∈ I(β) ⇔ β<nowiki><i></nowiki> = 1. ФАЛ F(y), для которой F(β) = 1 ⇔ система строк матрицы М с номерами из I(β) образует ее покрытие, будем называть ''функцией покрытия'' матрицы М. |
'''Свойства ФАЛ покрытия матрицы'''<br> | '''Свойства ФАЛ покрытия матрицы'''<br> | ||
* монотонность | * монотонность | ||
Строка 221: | Строка 219: | ||
=== !!! Определение эквивалентности КС Σ', Σ" и соответствующего тождества. Основное тождество ''t<sub>2</sub>'' (перестановка контактов в цепочке) и вспомогательное тождество ''t<sub>8</sub>'' ("расклейка" двух цепочек длины 2 с общим контактом); обобщенные тождества ''t<sub>2</sub><sup>(n)</sup>'' и ''t<sub>8</sub><sup>(n)</sup>'' === | === !!! Определение эквивалентности КС Σ', Σ" и соответствующего тождества. Основное тождество ''t<sub>2</sub>'' (перестановка контактов в цепочке) и вспомогательное тождество ''t<sub>8</sub>'' ("расклейка" двух цепочек длины 2 с общим контактом); обобщенные тождества ''t<sub>2</sub><sup>(n)</sup>'' и ''t<sub>8</sub><sup>(n)</sup>'' === | ||
- | + | (параграф 7 главы 2, в самом начале) | |
- | + | ||
- | + | ||
- | + | ||
=== !!! Определение суммарного цикломатического числа КС от БП ''x<sub>1</sub>'',...,''x<sub>n</sub>'' и формулировка утверждения о его изменениях при применении основных тождеств === | === !!! Определение суммарного цикломатического числа КС от БП ''x<sub>1</sub>'',...,''x<sub>n</sub>'' и формулировка утверждения о его изменениях при применении основных тождеств === | ||
(глава 2, стр 72) | (глава 2, стр 72) | ||
- | Множество всех связных компонент графа обозначается через c(G).Напомним, что | ||
- | |E(G)| − |V(G)| + |c(G)| > 0 | ||
- | и что левая часть неравенства называется цикломатическим числом графа G. | ||
=== Определение структуры CФЭ как графа специального вида и изоморфных СФЭ === | === Определение структуры CФЭ как графа специального вида и изоморфных СФЭ === |