ОК_Часть_1_2015 (С.А. Ложкин - Лекции по основам кибернетики (2015)), страница 2

. . , an ) ∈ An , означает, что компоненты набора aнаходятся (соответственно не находятся) в отношении f , тоесть f (a) = 1 (соответственно f (a) = 0).Для бинарных отношений, то есть отношений от двухпеременных, обычным образом определяются свойства рефлексивности, транзитивности, симметричности и антисимметричности. Отношение, обладающее свойствами рефлексивности, симметричности и транзитивности, будем, как обычно, называть отношением эквивалентности. Напомним, что1Через dαe (bαc) обозначается ближайшее к α сверху (соответственно снизу) целое число2Функцию f от переменных x1 , x2 будем, как обычно, представлятьв виде (x1 f x2 ).§1.

Основные понятия11отношение эквивалентности τ , заданное на множестве A,порождает разбиение этого множества на классы τ -эквивалентности — максимальные по включению подмножествамножества A, состоящие из попарно τ -эквивалентных элементов. Примером отношения эквивалентности является отношение перестановочности на множестве An , в которомслова α0 и α00 находятся тогда и только тогда, когда α00 можно получить из α0 в результате перестановки букв.

Заметим,что классами эквивалентности по этому отношению являются сочетания с повторениями.Отношение, обладающее свойствами рефлексивности, транзитивности и антисимметричности, будем, как обычно, называть отношением частичного порядка. Если τ — отношение частичного порядка на множестве A, то пару (A, τ )будем называть частично упорядоченным множеством. Втом случае, когда в частично упорядоченном множестве (A, τ )любые два элемента a0 и a00 из A сравнимы, то есть либоa0 τ a00 , либо a00 τ a0 , пару (A, τ ) будем считать линейно упорядоченным множеством.

Предполагается, что все элементы конечного линейно упорядоченного множества (A, τ ), где|A| = t, пронумерованы числами отрезка [0, t) так, что длялюбых a0 и a00 из A номер a0 не больше, чем номер a00 тогдаи только тогда, когда a0 τ a00 .Под дискретной функцией понимают, обычно, отображение одного конечного множества в другое. Так, функция над отрезком [0, k), где k > 2, называется функциейk-значной логики (при k = 2 — алгебры логики), а множество всех таких функций обозначается через Pk . Дискретные функции, как правило, могут быть описаны таблицами.Так, бинарная функция f (x1 , x2 ) из конечного линейно упорядоченного множества A = {a1 , .

. . , am } в конечное множество D может быть задана матрицей M, M ∈ Dm,m , гдеM hi, ji = f (ai , aj ) при всех i, j из отрезка [1, m], и обратно.Пусть X = {x1 , x2 , . . . , xn , . . . } — счетный упорядоченный12Глава 1. Дизъюнктивные нормальные формыалфавит переменных над множеством A и пусть PA = PA (X)— множество всех функций над A от переменных из X. Переменная xi , i ∈ [1, n], называется несущественной переменной функции f (x1 , .

. . , xn ) из PA , если f (α) = f (β) длялюбых отличающихся только по xi наборов α и β из An . Впротивном случае переменная xi называется существеннойпеременной функции f . Считается, что функция f существенно (несущественно) зависит от переменной xi , если xi —существенная (соответственно несущественная) переменнаяфункции f .

Несущественная переменная не влияет на значение функции, поэтому, как обычно, равенство функций будем рассматривать с точностью до добавления или изъятиянесущественных переменных. При этом две функции считаются равными, если они имеют одни и те же существенныепеременные и одинаковым образом отображают декартовустепень A, связанную с их существенными переменными, вA. Будем говорить, что f — существенная функция, еслиона существенно зависит от всех своих переменных.Предполагается, что у нас имеется счетный алфавит функциональных символов (ФС) для обозначения функций из PAи что в PA выделено «базисное» множество Б.

Дадим индуктивное определение формулы над Б и реализуемой ею функции, которое, в отличие от [28], неявно предполагает наличиев Б функции, тождественно равной переменной. Заметим,что с содержательной точки зрения формула представляетсобой слово, построенное из ФС «базисных» функций, символов переменных и «разделителей», которое задает последовательность выполнения операций суперпозиции.Любая переменная xj из X считается формулой глубины0 над множеством Б, которая реализует функцию xj .

Если ϕ (x1 , . . . , xk ) ∈ Б и для каждого i, i ∈ [1, k], определенаформула Fi глубины qi над множеством Б, которая реали-§1. Основные понятия13зует функцию fi из PA , то запись F видаF = ϕ (F1 , . . . , Fk )(1.6)является формулой глубины q = max {q1 , . . . , qk } + 1 над Б,которая реализует функцию f вида f = ϕ (f1 , .

. . , fk ). Всезаписи, полученные в результате указанного индуктивногопостроения, и только они считаются формулами над множеством Б. При этом формулы, полученные в процессеиндуктивного построения формулы F, называются ее подформулами, а те подформулы F1 , . . . , Fk , из которых на последнем шаге индуктивного построения строится формулаF вида (1.6), считаются ее главными подформулами.

Подсложностью (рангом) формулы F понимается число вхождений в нее ФС (соответственно символов переменных), которое обозначается через L (F) (соответственно R (F)).Формулы F0 и F00 , реализующие равные функции f 0 иf 00 , называются равными или, иначе, эквивалентными. Приэтом равенство вида t : F0 = F00 считается тождеством.Обычным образом вводятся тождества, характеризующиесвойства коммутативности, ассоциативности и дистрибутивности бинарных функций из PA .Множество всех функций, реализуемых формулами надБ, называется замыканием множества Б.

При этом множество Б считается полным, если его замыкание совпадает сPA . В дальнейшем любое конечное полное в PA базисноемножество Б будем называть базисом. При этом, в отличиеот [28], в Б могут присутствовать ФАЛ, при удалении которых оставшееся множество продолжает быть полным.14§2Глава 1. Дизъюнктивные нормальные формыПредставление функций алгебры логики спомощью дизъюнктивных нормальных форм(ДНФ) и его «геометрическая» интерпретация. Совершенная ДНФ, критерий единственности ДНФМножество B n , где B = {0, 1} и n ∈ N, то есть множество наборов длины n из 0 и 1, обычно называют единичным кубомили гиперкубом размерности n.

Отношение перестановочности разбивает куб B n на классы эквивалентности (сочетания) B0n , B1n , . . . , Bnn , где Bin , i ∈ [0, n], — так называемыйi-й слой куба B n , то есть множество наборов с i единицами,nnи, очевидно, |Bi | = i .На множестве B n введем отношение лексикографического линейного порядка, которое задается взаимно однозначным отображением (нумерацией) ν : B n → [0, 2n ) таким, чтоν (α1 , .

. . , αn ) =nXαi 2n−i .i=1Заметим, что двоичная запись числа ν (α) , α ∈ B n , дополненная слева нулями до набора длины n, совпадает сα. Аналогичным образом вводится лексикографический порядок на множестве ([0, k))n при k > 2. Множество наборов,являющееся образом отрезка [a, b], где [a, b] ⊆ [0, 2n ), приотображении ν −1 , называется отрезком куба B n .Для наборов α, β из B n через ρ (α, β) обозначается такназываемое расстояние Хэмминга между ними, то есть число тех разрядов, в которых они отличаются друг от друга.При этом наборы, находящиеся на расстоянии n, называются противоположными, а наборы, отличающиеся только водном (i-м) разряде, считаются соседними (соответственнососедними по i-й переменной).

При геометрическом изображении куба B n на плоскости вершины i-го слоя обычно располагаются на одном и том же горизонтальном уровне над§2. Представление ФАЛ с помощью ДНФB3N1(100)(1111)`@@Γ(1222) ```@`@@ @ @@ @`@`` @` `@`@@ @ @@@ Γ(0221)`@`@`c@`Γ(0200)Γ(0010)@ x x1xx13I 2 6@ 4@`B4`@@c` N2 c`@c`N3 (011)@ (101)@@ (010) @ N4c` N6 @c`` (001)N@5 c@@@`(111)(110)15(000)(0000)a)b)Рис. 2.1: B 3 и B 4 , примеры гранейвершинами (i − 1)-го слоя, i = 1, .

. . , n, а соседние вершинысоединяются отрезками прямых (см. рис. 2.1). Множествонаборов куба B n , находящихся на расстоянии t (не больше,чем t) от набора α, называется сферой (соответственно шаром) радиуса t с центром α. Заметим, что i-й слой куба B nявляется сферой радиуса i с центром в наборе e0 = (0, . . . , 0)eи сферой радиуса (n − i) с центром в наборе 1 = (1, . . . , 1).На множестве B n обычным образом введем отношениечастичного порядка 6 такое, чтоα = (α1 , .

. . , αn ) 6 β = (β1 , . . . , βn )тогда и только тогда, когда αi 6 βi при всех i ∈ [1, n]. Приэтом считается, что α < β, если α 6 β и α 6= β, а наборыα, β из B n , для которых α 6 β или β 6 α (α β и β α),называются сравнимыми (соответственно несравнимыми).Для набора γ = (γ1 , . . . , γn ) длины n над множеством[0, 2] через Γγ обозначим множество всех тех наборов α == (α1 , . . . , αn ) куба B n , для которых αi = γi при всех i ∈16Глава 1. Дизъюнктивные нормальные формыx1010 x1 x1 10 1 0 10 0 1 1a)x1 x20 00 11 01 1&0001∨ ⊕ ∼ → | ↓0 0 1 1 1 11 1 0 1 1 01 1 0 0 1 01 0 1 1 0 0b)αef(00)(11)(01)(10)(0001)(0111)(0110)(1001)(1101)(1110)(1000)название функции f— ”0” (константа нуль)— ”1” (константа единица)— тождественная функция— отрицание— конъюнкция (умножение)— дизъюнкция— сумма по модулю 2— эквивалентность— импликация— штрих Шеффера— стрелка Пирсаc)Рис.

2.2: P2 (1) и «основные» ФАЛ из P2 (2)§2. Представление ФАЛ с помощью ДНФ17[1, n] таких, что γi 6= 2. Множество Γγ называется граньюкуба B n , число (n − r), равное числу ”2” в наборе γ, считается размерностью этой грани, а число r — ее рангом. Заметим, что указанная грань Γγ представляет собой подкубразмерности (n − r) куба B n и состоит из 2n−r наборов, отличающихся друг от друга только в тех разрядах, в которыхрасположены символы ”2” набора γ.