1. ДМ Функции алгебры логики. Реализация функций формулами. Канонические нормальные формы представления функций. E2={0,1}; f(x1,…,xn)-ф-ия алгебра логики, если переменные x1,…, xn определены на E2 и зн ия ф-ии f на любом наборе переменных принадлежат E2 Способы задания ф-ий: табличный, в виде формул. Число булевых ф-ий от n переменных = 2n Ф-ия f(x1…xi…xn) существенно зависит от xi, если a1…an такой, что f(a1…ai 10ai+1…an)≠f(a1…ai-11ai+1…an). Иначе переменная называется фиктивной.S ^ называются равными, если одну можно получить из другой путем удаления и добавления фиктивных переменных (или они принимают на всех возможных наборах одинаковые значения) ^ : x | y | ¬x | x&y | xy | xy | x~y | xy | x|y | xy | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | f(A1…An) – формула, если A1…An – формулы либо переменные Каждая формула реализует некоторую ф-ию(можно сделать табличку). Ф-лы эквивалентны, если реализуемые ими ф-ии равны. | Любую булеву ф-ию м. представить в виде f(x1...xn)= -^ Как построить СДНФ: СДНФ содержит столько слагаемых, сколько 1 в таблице. Каждое слагаемое содержит все перменные. Переменные входят с отрицаниями или без в зависимости от значения переменной. Пример: x | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | y | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | z | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | f(x,y,z) | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
|

| ДНФ –дизъюнкция элементарных конъюнкций, т.е.D=k1k2…km, где элем. кон. (в элем. кон. все перемен. различны. r - ранг конъюнкции). ^ – ДНФ, содержащая наименьшее число вхождений переменных. Кратчайшая ДНФ – ДНФ, содержащая наим. число элем. кон. Полином Жегалкина — полином над Z2, то есть полином с коэффициентами вида 0 и 1, где в качестве произведения берется конъюнкция, а в качестве сложения исключающее или. | ^ E2={0,1}; f(x1,…,xn)-ф-ия алгебра логики, если переменные x1,…, xn определены на E2 и зн ия ф-ии f на любом наборе переменных принадлежат E2 f(A1…An) – формула, если A1…An – формулы либо переменные Пусть MP2. Замыканием мн-ва M наз-ся мн-во всех булевых ф ий, представимых в виде ф-лы над M. Обозн [M]. Пр.: M=P2 [M]=P2; M={1, x1x2} [M]={f: f=c0c1x1…cnxn} Класс M – замкнутый, если M=[M]. Пр.: P2-замкнутый класс ^ T0={f: f(0…0)=0} – класс ф-ий, сохраняющих константу 0; T1 – класс ф-ий, сохр-х константу 1; S -класс самодвойственных ф-ий (на противоположенных наборах принимают противоположные значения); M-класс монотонных ф-ий (,:< f()f()); L-класс линейных ф-ий
| 0 | 1 | x | ¬x | x&y | xy | xy | x~y | xy | x|y | xy | T0 | + | - | + | - | + | + | - | - | + | - | - | T1 | - | + | - | - | + | + | + | + | - | - | - | S | - | - | + | + | - | - | - | - | - | - | - | M | + | + | + | - | + | + | - | - | - | - | - | L | + | + | + | + | - | - | - | + | + | - | - |
| ^ E2={0,1}; f(x1,…,xn)-ф-ия алгебра логики, если переменные x1,…, xn определены на E2 и зн ия ф-ии f на любом наборе переменных принадлежат E2 f(A1…An) – формула, если A1…An – формулы либо переменные Пусть P={f1f2…} – система ф-ий изP2. Система ф-ий P функционально полна в P2, если fP2 м.б. представлена в виде формулы над P. Примеры полных в P2 систем ф-ий: P2, {,,}, {,}, {,}, {0,1, xy, xy}, {|}, {,} [ Т Т] о функциональной полноте: пусть P={f1f2…}-произв. сист. ф ий из P2. Для того, чтобы сист. ф-ий была функционально полной в P2 н. и д., чтобы она целиком не принадлежала ни одному из замкнутых классов T0, T1, S, L, M.
| Пр.: {xy, x}
|
| T0 | T1 | S | L | M | x | - | - | + | + | - | xy | + | + | - | - | + |
| => полна |
| Пр.: {xy, xy}
|
| T0 | T |
S | L | M | xy | + | + |
|
|
| xy | - | + |
|
|
|
| => не полна |
| ^ ДНФ –дизъюнкция элементарных конъюнкций, т.е.D=k1k2…km, где элем. кон. (в элем. кон. все перемен. различны. r - ранг конъюнкции). ^ – ДНФ, содержащая наименьшее число вхождений переменных. Кратчайшая ДНФ – ДНФ, содержащая наим. число элем. кон. Тривиальный алгоритм построения минимальной и кратчайшей ДНФ ф-ии f(x1…xn): построить все возможные ДНФ, используя x1…xn и x1…xn, упорядочить их от простых к сложным, и, начиная с простых, проверять, реализует ли ДНФ ф-ию f. Число разл-х ДНФ, построенных на n-переменных= ^ имеем единичный n-мерный куб. Bn- мн-во его Вршин. (1..n). Любой ф-ии f можно поставить в соотв. мн-во NfBn– подмн-во вершин куба: Nf={(1..n): f(1..n)=1} Пусть k– произв. элементарная конъ. ранга r. Мн-во NkBn наз ся интервалом ранга r, если оно соотв. конъ k:
, зн-ия остальных переменных – произвольные. | Пр1.: Nk={(101)}; Пр2.: k=y N={(010)(011)(110)(111)} Пусть f задана в виде ДНФ: f= k1k2…km. Т.о. с каждой ДНФ ф-ии f связано некоторое покрытие мн-ва Nf интервалами . Справедливо и обратное: каждое покрытие мн ва Nf интервалами определяет некоторую ДНФ, реал-ую данную ф-ию. П усть rj – ранг коньюнкции kj. - число вхождений переменных во всей ДНФ. Построение ДНФ сводится к построению покрытия Nf интервалами , при котором вел на r минимальна. Построение кратчайшей ДНФ сводится к отысканию покрытия с минимальным числом интервалов. Пр.:

| ^ Ek={0,1,…,k-1}, Ekc={=((1), (2),…): (i)Ek}. Pkc - мн-во ф-ий, опр-х на Ekc Пр1: E2={0,1}, f() = (0,0,…,0), если =(0,0,…,0) и f() = (1,1,…,1) иначе. Каждую функцию из Pkc можно трактовать как ф-ию их PNc (N=kn), но от одной переменной. Пусть f(x) PNc. Ф-ия f(x) наз-ся детерминированной (D-) ф-ей, если m, =((1), (2),…), =((1), (2),…) таких, что (1)= (1), (2)= (2) … (m)= (m) выполняется: (1)=(1), (2)=(2), …, (m)=(m) (т.е. (m) зависит только от (1)…(m)) ^ : Ф(x,y)=x+y – D-ф-ия; Пр1 – не D-ф-ия Задание D-ф-ий деревьями: Из каждой вершины исходит N ребер. Связанное мн-во ребер по одному из каждого яруса – ветвь. Каждая ветвь определяет набор значений аргументов D-ф-ии. Пр3: f(x,y)=x+y, k=2, n=2, N=4
|
 Пусть -вершина m-го яруса. Совокупность всех ветвей, исходящих из - поддерево исходного дерева с корнем в в вершине . Поддереву соответствует некоторая функция f(x). Два поддерева с корнями в вершинах 1 и 2 наз-ся эквивалентными, если  Эквивалентным вершинам можно приписать одно и тоже число. число классов эквивалентностей r в дереве наз-ся весом дерева (или весом функции) Используя эти понятия можно строить усеченные деревья, которые однозначным образом позволяют восстановить полное дерево. |
 D-ф-ия наз-ся огр-но детерминированной (OD-) ф-ей, если она имеет конечный вес. пр2 – OD-ф-ия.
| ^ сообщение[кодер]код сообщ.[канал связи]код сообщ.[декодер]сообщ. на выходе Проблемы: однозначность кодирования, оптимизация кодирования, обнаружение и исправление ошибок
Пусть a={a1,a2,…,an}-исх. алф., A= , l(A) – длина слова, S(A)-мн во всех слов в алф. A, S(A)S(A)-мн во всех возм-х сообщ. на входе; b={b1,b2,…,bq}-алфавит, В- слово в нем. Пусть задано отобр. F: AS(A) BS(B). Слово B – код сообщения A. Процесс перехода от A к B – кодирование. Отобр. F- некоторый алгоритм. ^ : задается схема кодирования , которая каждому символу алфавита a ставит в соответствие слово B из алфавита b: : | a1 – B1 | Слова B1…Br нас-ся элементарными кодами. Могут иметь произвольную конечную длину | a2 – B2 | … | ar – Br | Рассмотри проблему однозначности кодирования: Будем считать, чт S(a)=S(a). Пусть S(B)S(B) – образ мн-ва S(A) при кодировании. Если отображение S(A)S(B) взаимнооднозначно, то проблема декодирования решается однозначно. | Пр1: | : | a1 – b1 | -однозначна | a2 – b1b2 | Пусть слово B=BB. Тогда B - префикс, B - суффикс. Схема кодирования обладает св-вом префикса, если I,j (ij) Bi не является префиксом Bj. Т если схема кодирования обл-ет св-вом префикса, то кодирование будет взаимнооднозначным. Пр2: | : | a1 – b1b2 | -обдадает св-вом префикса однозначна | a2 – b1b1 | a3 – b3 | ^ : l(B)-длина слова B, li=l(Bi), -длина схемы кодирования Пусть Bi – элементарный код и имеется его разложение вида Bi=Bi1… Bi, где , - цепочки, отличные от элемент-х кодов, причем не оканчивается элем-м кодом, - не начинается им. Для любого Bi есть конечное число таких разложений. Обозначим через W максимум величины по всем возможным разложениям всех Bi.
Т. (Маркова) для любой схемы кодирования такое, что проблема однозначности кодирования сводится к проверке однозначности на некотором множестве SN(a)- мн-во всех слов в алфавите а, длина которых N. | Эта теорема позволяет построить чисто практический алгоритм распознавания однозначности: для каждого Bi рассм. все разложения. Построим мн-во D={, i}. Построим граф Г(), вершинами которогоявл-ся эл-ты мн-ва D так: если сущ-ет разложение Bi==Bi1… Bi, то соединим и ориентир м ребром, которое пометим цепочкой Bi1… Bi. Т Алфавитное кодирование со схемой явл-ся неодн м т.тогда, когда граф Г() содержит ориентированный цикл, проходящий через вершину .
| ^ сообщение[кодер]код сообщ.[канал связи]код сообщ.[декодер]сообщ. на выходе
Пусть a={a1,a2,…,an}-исх. алф., A= , l(A) – длина слова, S(A)-мн во всех слов в алф. A, S(A)S(A)-мн во всех возм-х сообщ. на входе. Пусть b={b1,b2,…,bq}-алфавит, В- слово в нем. Пусть задано отобр. F: AS(A) BS(B). Слово B – код сообщения A. Процесс перехода от A к B – кодирование. Отобр. F- некоторый алгоритм. ^ : задается схема кодирования , которая каждому символу алфавита a ставит в соответствие слово B из алфавита b: : | a1 – B1 | Слова B1…Br нас-ся элементарными кодами. Могут иметь произвольную конечную длину | a2 – B2 | … | ar – Br |
Пусть заданы некоторые вероятности p1…pr появления символов a1…ar в исходном сообщении. (их сумма = 1) Пусть li=l(Bi)- длина слова Bi. Тогда lср= pili – мат. ожидание длины элементарных кодов. Показывает во сколько раз в среднем длина сообщения больше длины исходного сообщения. Коды со схемой кодирования , у которых lср=l* (=min lср) называются кодами с минимальной избыточностью или кодами Хаффмана. | В силу нер ва Макмиллана и сл. из него. всегда сущ ют коды с минимальной избыточностью, обладающие св вом префикса. Алгоритм построения кодов Хаффмана: 1. по вел-нам r и q определить q0: q0=q-1, если остаток(r/(q-1))=0; q0=q, если остаток()=1; q0=остаток() в противном случае 2. список вероятностей p1…pr заменить на p1,…,pr-qo,p. Переупорядочить получившуюся последовательность. Повторяем этот шаг, пока число вероятностей больше чем q. 3. для оставшегося списка вероятностей строится однобуквенный код, который обладает св вом минимальной избыточности 4. проделываем шаг 2 в обратном порядке. Пр.
|
| ответ | дано |
|
|
|
|
| : | a1- | 1 | 0.22 |
| 0.22 |
| ┌ 0.44 | 0 | a2- | 2 | 0.20 |
| 0.20 |
| 0.22 | 1 | a3- | 00 | 0.14 |
| ┌ 0.14 |
| 0.20 | 2 | a4- | 01 | 0.11 |
| 0.14 | 0 | 0.14 | 3 | a5- | 02 | 0.10 |
| 0.11 | 1 |
|
| a6- | 03 | 0.09 |
| 0.10 | 2 |
|
| a7- | 30 | 0.08 | 0 | 0.09 | 3 |
|
| a8- | 31 | 0.06 | 1 |
|
|
|
| r=8, q=4, q0=2 | ^ сообщение[кодер]код сообщ.[канал связи]код сообщ.[декодер]сообщ. на выходе
Пусть a={a1,a2,…,an}-исх. алф., A= , l(A) – длина слова, S(A)-мн во всех слов в алф. A, S(A)S(A)-мн во всех возм-х сообщ. на входе. Пусть b={b1,b2,…,bq}-алфавит, В- слово в нем. Пусть задано отобр. F: AS(A) BS(B). Слово B – код сообщения A. Процесс перехода от A к B – кодирование. Отобр. F- некоторый алгоритм. Предполагаем, что канал связи при передаче сообщения длины N может делать только одну ошибку. Как отловить эту ошибку? отправить вместо одного три сообщения, добавлять к сообщению бит четности. Можно добавить несколько контрольных разрядов, которые позволят узнать, где ошибка: 1-ый позв. определить, есть ли ошибка, 2-ой – есть ли ошибка во второй половине общения, 3-ий разряд отвечает за 2-ю и 4-ю четверти и т.д. ^ : пусть имеется число v (1 v l). Пусть имеется его двоичная запись v=kk 1…1. Эти числа разобьем на группы. В первую включим числа с номерами 1, 3, 5, 7…, во вторую 2, 3, 6, 7, 10, | 11… т.е. номера, во втором разряде двоичного представления которых стоит 1, в третью 4,5,6,7,13,14,15,20… и т.д. Те разряды в коде , номера которых явл-ся степенями числа 2, будем использовать как контрольные, остальные разряды – информационные: 1=3579… 2=36710… 4=56712… Т.о. можно для каждого сообщения A получить код B. Пусть получили код 1, 2,…, l. Необходимо обнаружить и исправить ошибку. Двоичная запись номера испорченного разряда: s=sksk-1…s1, где s1=125… s2=2367… s3=456712… Пр. Пусть пришел код 1100110. Необходимо найти и исправить ошибку. s1=0 s2=1 есть ошибка s3=1 s=110=6 – ошибка в 6-ом разряде. |
|
| |