1 (С.А. Ложкин - Лекции по основам кибернетики (2017)), страница 2
Описание файла
Файл "1" внутри архива находится в папке "С.А. Ложкин - Лекции по основам кибернетики (2017)". PDF-файл из архива "С.А. Ложкин - Лекции по основам кибернетики (2017)", который расположен в категории "". Всё это находится в предмете "основы кибернетики" из 6 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 2 страницы из PDF
Функцию f ,определенную на множестве An и принимающую значенияиз множества D (множества A), будем называть n-местной,или, иначе, n-арной функцией из множества A во множество D (соответственно над множеством A) от переменныхx и будем представлять ее в виде2f = f (x) , f : An −→ D(соответственно f : An −→ A) .При этом в случае D = B = {0, 1} функция f считаетсяотношением над множеством A, а запись f (a) (f (a)), гдеa = (a1 , . . . , an ) ∈ An , означает, что компоненты набора aнаходятся (соответственно не находятся) в отношении f , тоесть f (a) = 1 (соответственно f (a) = 0).Для бинарных отношений, то есть отношений от двухпеременных, обычным образом определяются свойства рефлексивности, транзитивности, симметричности и антисимметричности. Отношение, обладающее свойствами рефлексивности, симметричности и транзитивности, будем, как обычно, называть отношением эквивалентности.
Напомним, что1Через dαe (bαc) обозначается ближайшее к α сверху (соответственно снизу) целое число2Функцию f от переменных x1 , x2 будем, как обычно, представлятьв виде (x1 f x2 ).Введение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Введениеалфавит переменных над множеством 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 над множеством Б, которая реали-Введение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ВведениеПредставление функций алгебры логики спомощью дизъюнктивных нормальных форм(ДНФ) и его «геометрическая» интерпретация. Совершенная ДНФ, критерий единственности ДНФМножество 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-го слоя обычно располагаются на одном и том же горизонтальном уровне надВведение15B3`@@c` N2 c`@c`N3 (011)@ (101)@@ (010) @ N4c` N6 @c`` (001)N@5 c@@@`(111)(110)N1(100)(1111)`@@Γ(1222) ```@`@@ @ @@ @`@`` @` `@`@@ @ @@@ Γ(0221)`@`@`c@`Γ(0200)Γ(0010)@ x x1xx13I 2 6@ 4@`B4(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 , .