В.П. Воронин - Дополнительные главы дискретной математики (1127085), страница 18

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 18)

Доказать, что в частично упорядоченном по делимости множестве натуральных чисел функцией Мебиуса являетсяn = 1,1,sµ (n) = (−1) , n = p1 · · · ps — свободно от квадратов,0,иначе.Использовано следующее обозначение: µ (m, n) = µ 1, mn ; µ (1, n) = µ (n).6. Доказать, что свойства 6a и 6b эквивалентны и для определения дистрибутивности достаточно любого одного изних.62ГЛАВА 2. КОНЕЧНОЗНАЧНЫЕ ЛОГИКИГлава 2Конечнозначные логики2.1Функции конечнозначной логикиОпределения и примеры. Множество U = {u1 , u2 , . . .

, u` , . . .} назовем алфавитом переменных. Элементы этогомножества называются соответственно переменными. При этом считается, что переменные с различными индексамиразличны (то есть могут принимать различные значения независимо друг от друга).Определяется множество Ek = {0, 1, . . .

, k − 1} и рассматриваются функции вида f : Ekn → Ek . Функция от n различных переменных обозначается f (ui1 , . . . , uin ), при этом считается, что j 6= s ⇒ ui j 6= uis . Такие функции называютсяфункциями k-значной логики. В дальнейшем используются следующие метаобозначения: f (x, y, .

. . , z) — при этомсчитается, что различным буквам соответствуют различные переменные, f (x1 , . . . , xn ) — при этом аналогично считается, что буквам с различными индексами соответствуют различные переменные и f (x̃n ), что является альтернативнымобозначением второго обозначения.Множество всех функций k-значной логики обозначается Pk . Множество всех функций k- значной логики, завиn hni hniсящих от n переменных обозначается Pk .

Очевидно, Pk = kk . В дальнейшем левая часть предыдущего равенствабудет записываться в несколько ином виде: |Pk |hni . Доказывается это равенство при помощи табличного заданияфункции k-значной логики: x100kn. ..k−1...............xn−100...k−1xn01...k−1f (x1 , . . . , xn−1 , xn )← любое значение← любое значение...← любое значениеУпорядочив лексикографически в левой части таблицы все наборы длины n из Ek , легко видеть, что всего их kn . Далее,каждому из наборов ставится в соответствие произвольное значение также из Ek . Это, в свою очередь можно сделатьnkk различными способами.Изучение функций k-значной логики существенно затрудняется тем, что с возрастанием числа переменных их количество растет заметно быстрее, чем, скажем, число функций алгебры логики. Так, например, число функций трехзначной логики двух переменных равно 39 , что больше, чем 19000, в то время, как число функций алгебры логики тогоже числа переменных равно 16.

Возникает вопрос о задании функции k-значной логики. Векторное задание, котороеочень удобно для функции алгебры логики, представляется неприемлемым, так как длина вектора быстро растет. Дляфункций одного переменного наиболее часто используется представление в виде подстановки:0 1 ... k −1S (x) =.a0 a1 . . . ak−1Напомним, что элементы нижней строчки в подстановке могут повторяться.

Если же все элементы нижней строчкиразличны, то подстановка превращается в перестановку. Для функций двух переменных используется задание в видедвумерной таблицы:HHy1...k−1x H 0..0...1....· · · · · · f (i, j)k−1Следующие функции называются элементарными функциями k-значной логики:• Константы 0, 1, . .

. , k − 1 не имеют существенных переменных. Формально константу 0 можно задать в видеподстановки0 1 ... k −10 (x) =.0 0 ...0632.1. ФУНКЦИИ КОНЕЧНОЗНАЧНОЙ ЛОГИКИ• Функции, существенно зависящие от одной переменной: Обобщение отрицания алгебры логики — отрицаниеПоста0 1 ... k −2 k −1x== x + 1 (mod k).1 2 ... k −10Оно обладает простыми свойствами: x = x + 2 (mod k), и вообще для любого натурального l отрицание Поста,примененное l раз к x, дает x + l (mod k).

Обратим внимание, что сложение двух различных переменных такимобразом не определяется, так как мы определили лишь сложение с константой.• Другим обобщением отрицания в P2 является отрицание Лукасевича (в некоторых источниках — Лукашевича). Оно определяется как012... k −1∼x== (k − 1) − x.k −1 k −2 k −3 ...0Для отрицания Лукасевича справедливо правило снятия двойного отрицания, как и у отрицания в P2 : ∼ (∼ x) = x012... k −1• Функция −x =, обладающая тем свойством, что если ее добавить к x, то по0 k −1 k −2 ...1лучится константа 0.Векторное задание этой функцииимеет вид −x = 0 k − 1 .

. . 1 . С другой стороны:x = 0 1 ... k −1 ,∼ x = k −1 k −2 ... 1 ,(∼ x) = 0 k − 1 . . . 1 ,то есть x = −(∼ x).• Семейство функций, являющихся также обобщениями отрицания(k − 1 x = i,Ji (x) =0 6 i 6 k−10x 6= i,и(1 x = i,ji (x) =0 x=6 i,0 6 i 6 k − 1.• Разностью переменной x и константы i назовем функцию x − i = x + (k − i), иначе говоря, (k − i) раз примененноеотрицание Поста.• Обобщение двухместной дизъюнкции — максимум: max (x, y). Эта функция, очевидно, коммутативна, а такжеассоциативна: max (x, max (y, z)) = max (max (x, y) , z), что позволяется ввести по индукции n-местный максимум:max (x1 , .

. . , xn−1 , xn ) = max (max (x1 , . . . , xn−1 ) , xn ).• Обобщение двухместной конъюнкции: min (x, y). Минимум обладает такими же свойствами, что и максимум. Вчастности, определяется min (x1 , . . . , xn ). Для минимума и максимума справедливы обобщения правил де Моргана:∼ max (∼ x, ∼ y) = min (x, y) , ∼ min (∼ x, ∼ y) = max (x, y) .(2.1)• Сложение по модулю k: x + y (mod k).

Эта операция коммутативна и ассоциативна. Можно ввести разность: x +y+y+...+y = x−y|{z}k−1• Еще одним обобщением конъюнкции может служить произведение по модулю k: x · y (mod k).• Усеченная разность(x − y x > y,x−̇y =0x < y.Таблица усеченной разности при k = 3 имеет следующий вид:yHx H012001210012000Очевидно, что из усеченной разности легко получить минимум: min (x, y) = x−̇ (x−̇y). Действительно, если x < y,то выражение в скобке равно нулю и вся формула реализует функцию x. Если же x > y, то выражение в скобкереализует x − y, что заведомо меньше x, то есть вся формула реализует x − (x − y) ≡ y.64ГЛАВА 2. КОНЕЧНОЗНАЧНЫЕ ЛОГИКИ• Импликация x ⊃ y =∼ (x−̇y), которую можно записать также(k − 1 − x + y x > y,x⊃y=k−1x < y.Реализация функций формулами.

Понятия формулы и ее глубины, а также функции, сопоставляющейся формуленад множеством функций определяются аналогично P2 .Определение 2.1.1. Пусть A — некоторое множество функций из Pk .1. Для любой функции f ∈ A справедливо: f является формулой глубины 1 над A .2. Если F1 , . . . , Fn — формулы над A или символы переменных из U и f (exn ) ∈ A , причем наибольшая глубина формулы среди F1 , . . .

, Fn равна k, то f (F1 , . . . , Fn ) — также формула над A , глубина которой равна k + 1.3. Те и только те объекты называются формулами над A , которые могут быть определены согласно пунктам 1 и 2данного определения.Дадим определение реализации функций формулой.Определение 2.1.2. Пусть A — некоторое множество функций из Pk .1.

Если функция f ∈ A , то формуле f сопоставляется функция f ∈ A , иными словами, формула f реализует функцию f : f → f ∈ A .2. Если F1 → f1 , . . . , Fn → fn и f ∈ A , то формуле f (F1 , . . . , Fn ) сопоставляется функция f ( f1 , . . . , fn ), иными словами,f ( f1 , . . . , fn ) реализуется формулой f (F1 , . . . , Fn ).3. Функции сопоставляются всем формулам, описанным в пунктах 1 и 2, и только им.Первая и вторая формы.Система функций{0, 1, . .

. , k − 1, J0 (x) , . . . , Jk−1 (x) , min (x, y) , max (x, y)}называется системой Россера-Туркетта.Теорема 2.1. Система Россера-Туркетта полна в Pk . Док-во. Обозначим систему Россера-Туркетта символом A . Так как 0 ∈ A , будем рассматривать функции f (exn ) 6≡0. В этом случае справедливо представлениеf (exn ) =max(α1 ,...,αn )∈Eknf (α1 ,...,αn )6=0(min (Jα1 (x1 ) , . . . , Jαn (xn ) , f (α1 , . . . , αn ))) .(2.2)e n ∈ Ekn все минимумы обратятся в ноль, за исключением одного, который и приДействительно, на любом наборе αмет значение, равное значению функции на этом наборе. Максимум из нулей и одного значения функции равен этомусамому значению.Реализация функции над системой Россера-Туркетта называется первой формой этой функции.

Так, например,первая форма усеченной разности при k = 3 имеет следующий вид:max (min (J1 (x) , J0 (y) , 1) , min (J2 (x) , J0 (y) , 2) , min (J2 (x) , J1 (y) , 1))Отметим, что система функций{0, 1, . . . , k − 1, J0 (x) , . . . , Jk−1 (x) , x + y, min (x, y)}также полна в Pk . Это следует из того, что доказательство теоремы 2.1 не изменится, если заменить в 2.2 максимум насумму по модулю k:f (exn ) =∑ min (Jα1 (x1 ) , . . . , Jαn (xn ) , f (α1 , . . .

, αn )) (mod k).(α1 ,...,αn )∈Eknf (α1 ,...,αn )6=0В этом случае суммироваться будут все нули и одно значение функции, что, очевидно, то же самое.Рассмотрим теперь систему{0, 1, . . . , k − 1, j0 (x) , . . . , jk−1 (x) , x + y, x · y}и докажем ее полноту:(2.3)652.1. ФУНКЦИИ КОНЕЧНОЗНАЧНОЙ ЛОГИКИТеорема 2.2. Система 2.3 полна в Pk . Док-во. Обозначим систему 2.3 символом B. Так как 0 ∈ B, будем рассматривать функции f (exn ) 6≡ 0. В этом случаесправедливо представлениеf (exn ) =∑(α1 ,...,αn )∈Eknf (α1 ,...,αn )6=0f (α1 , . . . , αn ) · jα1 (x1 ) · · · jαn (xn )(mod k).(2.4)Действительно, на любом наборе (α1 , .

. . , αn ), если ∃i : xi 6= αi , то все слагаемое обратится в ноль. Если же все xi = αi ,что встретится не более одного раза, то все слагаемое станет равным значению функции. Таким образом, правая частьсуммы 2.4 на фиксированном наборе равна просто значению функции на этом же наборе.Представление 2.4 функции k-значной логики принято называть ее второй формой. Так, при k = 3 вторая формаусеченной разности имеет вид:j1 (x) · j0 (y) + 2 · j2 (x) · j0 (y) + j2 (x) · j1 (y) .Операция замыкания, свойства замыкания, замкнутые классы. Пусть A — некоторое множество функций из Pk .Множество [A ] всех функций, реализуемых формулами над A , называется замыканием множества A .

Для операциизамыкания очевидны следующие тривиальные тождества:1. экстенсивность: A ⊆ [A ],2. монотонность (изотонность): A ⊆ B ⇒ [A ] ⊆ [B] и3. идемпотентность: [A ] = [[A ]].Если множество A совпадает со своим замыканием: (A = [A ]), то A называется замкнутым классом.Пусть A , B ⊆ Pk . Тогда если B = [B] , A ⊆ B и [A ] = B, то говорят, что система функций A — полная в системеB. Аналогично, если A — минимальная (по удалению) полная система в B, то A называется базисом.Очевидно, что замкнутые классы существуют. Тривиальными примерами замкнутых классов являются все Pk и пустое множество: [Pk ] = Pk , [∅] = ∅.

Характеристики

Список файлов книги