1. дм функции алгебры логики. Реализация функций формулами. Канонические нормальные формы представления функций

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 xy xy x~y xy x|y xy 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=k1k2…km, где элем. кон. (в элем. кон. все перемен. различны. r - ранг конъюнкции). ^ Минимальная ДНФ – ДНФ, содержащая наименьшее число вхождений переменных. Кратчайшая ДНФ – ДНФ, содержащая наим. число элем. кон. Полином Жегалкина — полином над Z2, то есть полином с коэффициентами вида 0 и 1, где в качестве произведения берется конъюнкция, а в качестве сложения исключающее или. ^ 2. ДМ Замыкание систем функций алгебры логики. Основные замкнутые классы. E2={0,1}; f(x1,…,xn)-ф-ия алгебра логики, если переменные x1,…, xn определены на E2 и зн ия ф-ии f на любом наборе переменных принадлежат E2 f(A1…An) – формула, если A1…An – формулы либо переменные Пусть MP2. Замыканием мн-ва M наз-ся мн-во всех булевых ф ий, представимых в виде ф-лы над M. Обозн [M]. Пр.: M=P2  [M]=P2; M={1, x1x2}  [M]={f: f=c0c1x1…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 xy xy x~y xy x|y xy T0 + - + - + + - - + - - T1 - + - - + + + + - - - S - - + + - - - - - - - M + + + - + + - - - - - L + + + + - - - + + - - ^ 3. ДМ Полнота систем функций алгебры логики. Критерий функциональной полноты. E2={0,1}; f(x1,…,xn)-ф-ия алгебра логики, если переменные x1,…, xn определены на E2 и зн ия ф-ии f на любом наборе переменных принадлежат E2 f(A1…An) – формула, если A1…An – формулы либо переменные Пусть P={f1f2…} – система ф-ий изP2. Система ф-ий P функционально полна в P2, если fP2 м.б. представлена в виде формулы над P. Примеры полных в P2 систем ф-ий: P2, {,,}, {,}, {,}, {0,1, xy, xy}, {|}, {,} [ Т Т] о функциональной полноте: пусть P={f1f2…}-произв. сист. ф­­ ий из P2. Для того, чтобы сист. ф-ий была функционально полной в P2 н. и д., чтобы она целиком не принадлежала ни одному из замкнутых классов T0, T1, S, L, M. Пр.: {xy, x} T0 T1 S L M x - - + + - xy + + - - + => полна Пр.: {xy, xy} T0 T S L M xy + + xy - + => не полна ^ 4. ДМ Проблема построения минимальных ДНФ и подходы к ее решению. ДНФ –дизъюнкция элементарных конъюнкций, т.е.D=k1k2…km, где элем. кон. (в элем. кон. все перемен. различны. r - ранг конъюнкции). ^ Минимальная ДНФ – ДНФ, содержащая наименьшее число вхождений переменных. Кратчайшая ДНФ – ДНФ, содержащая наим. число элем. кон. Тривиальный алгоритм построения минимальной и кратчайшей ДНФ ф-ии f(x1…xn): построить все возможные ДНФ, используя x1…xn и x1…xn, упорядочить их от простых к сложным, и, начиная с простых, проверять, реализует ли ДНФ ф-ию f. Число разл-х ДНФ, построенных на n-переменных= ^ Геометр. интерпретация задачи: имеем единичный n-мерный куб. Bn- мн-во его Вршин. (1..n). Любой ф-ии f можно поставить в соотв. мн-во NfBn– подмн-во вершин куба: Nf={(1..n): f(1..n)=1} Пусть k– произв. элементарная конъ. ранга r. Мн-во NkBn наз­­ ся интервалом ранга r, если оно соотв. конъ k: , зн-ия остальных переменных – произвольные. Пр1.:  Nk={(101)}; Пр2.: k=y  N={(010)(011)(110)(111)} Пусть f задана в виде ДНФ: f= k1k2…km. Т.о. с каждой ДНФ ф-ии f связано некоторое покрытие мн-ва Nf интервалами . Справедливо и обратное: каждое покрытие мн ва Nf интервалами определяет некоторую ДНФ, реал-ую данную ф-ию. Пусть rj – ранг коньюнкции kj. - число вхождений переменных во всей ДНФ. Построение ДНФ сводится к построению покрытия Nf интервалами , при котором вел на r минимальна. Построение кратчайшей ДНФ сводится к отысканию покрытия с минимальным числом интервалов. Пр.: ^ 5. ДМ Детерминированные и ограниченно детерминированные функции. Способы задания ограниченно-детерминированных функций. 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)) ^ Пр2: Ф(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-ф-ия. ^ 6. ДМ Проблематика теории кодирования. Алфавитное кодирование. Проблема однозначности кодирования. Префиксные коды. сообщение[кодер]код сообщ.[канал связи]код сообщ.[декодер]сообщ. на выходе Проблемы: однозначность кодирования, оптимизация кодирования, обнаружение и исправление ошибок Пусть a={a1,a2,…,an}-исх. алф., A= , l(A) – длина слова, S(A)-мн во всех слов в алф. A, S(A)S(A)-мн во всех возм-х сообщ. на входе; b={b1,b2,…,bq}-алфавит, В- слово в нем. Пусть задано отобр. F: AS(A) BS(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=BB. Тогда B - префикс, B - суффикс. Схема кодирования  обладает св-вом префикса, если I,j (ij) 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. Т Алфавитное кодирование со схемой  явл-ся неодн м т.тогда, когда граф Г() содержит ориентированный цикл, проходящий через вершину . ^ 7. ДМ Коды с минимальной избыточностью(Коды Хафмана). сообщение[кодер]код сообщ.[канал связи]код сообщ.[декодер]сообщ. на выходе Пусть a={a1,a2,…,an}-исх. алф., A= , l(A) – длина слова, S(A)-мн во всех слов в алф. A, S(A)S(A)-мн во всех возм-х сообщ. на входе. Пусть b={b1,b2,…,bq}-алфавит, В- слово в нем. Пусть задано отобр. F: AS(A) BS(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 ^ 8. ДМ Помехоустойчивое кодирование. Коды Хемминга. сообщение[кодер]код сообщ.[канал связи]код сообщ.[декодер]сообщ. на выходе Пусть a={a1,a2,…,an}-исх. алф., A= , l(A) – длина слова, S(A)-мн во всех слов в алф. A, S(A)S(A)-мн во всех возм-х сообщ. на входе. Пусть b={b1,b2,…,bq}-алфавит, В- слово в нем. Пусть задано отобр. F: AS(A) BS(B). Слово B – код сообщения A. Процесс перехода от A к B – кодирование. Отобр. F- некоторый алгоритм. Предполагаем, что канал связи при передаче сообщения длины N может делать только одну ошибку. Как отловить эту ошибку? отправить вместо одного три сообщения, добавлять к сообщению бит четности. Можно добавить несколько контрольных разрядов, которые позволят узнать, где ошибка: 1-ый позв. определить, есть ли ошибка, 2-ой – есть ли ошибка во второй половине общения, 3-ий разряд отвечает за 2-ю и 4-ю четверти и т.д. ^ Построение самокорректирующихся кодов (коды Хемминга): пусть имеется число v (1 v  l). Пусть имеется его двоичная запись v=kk 1…1. Эти числа разобьем на группы. В первую включим числа с номерами 1, 3, 5, 7…, во вторую 2, 3, 6, 7, 10, 11… т.е. номера, во втором разряде двоичного представления которых стоит 1, в третью 4,5,6,7,13,14,15,20… и т.д. Те разряды в коде , номера которых явл-ся степенями числа 2, будем использовать как контрольные, остальные разряды – информационные: 1=3579… 2=36710… 4=56712… Т.о. можно для каждого сообщения A получить код B. Пусть получили код 1, 2,…, l. Необходимо обнаружить и исправить ошибку. Двоичная запись номера испорченного разряда: s=sksk-1…s1, где s1=125… s2=2367… s3=456712… Пр. Пусть пришел код 1100110. Необходимо найти и исправить ошибку. s1=0 s2=1  есть ошибка s3=1 s=110=6 – ошибка в 6-ом разряде.

Похожие:

	1. дм функции алгебры логики. Реализация функций формулами. Канонические нормальные формы представления функций Ф-ия алгебра логики, если переменные x1,…, xn определены на E2 и зн ия ф-ии f на любом наборе переменных принадлежат E2		Формулы тройных углов Обратные тригонометрические функции Некоторые значения тригонометрических функций Определите знаки тригонометрических функций в зависимости от того, в какой четверти находится аргумент
	1. мл формулы логики предикатов. Общезначимые, выполимые формулы. Основные эквивалентности логики предикатов. Нормальные формы. Логическое следование Мл формулы логики предикатов. Общезначимые, выполимые формулы. Основные эквивалентности логики предикатов. Нормальные формы. Логическое...		Элементы алгебры логики Для описания логики функционирования аппаратных и программных средств компьютера используется алгебра логики или булева алгебра
	2 Функции управленческого учета Понимание сущности управленческого учёта позволяет выявить зависимость функций, выполняемых этим видом учёта, от функций управления....		Лекции 32часа. Отчетность зачет. Литература Основные элементы логических функции алгебры логики (или-or,и-and, и- не -and-not, и- или -не-and-or-not)
	Схемная реализация сложных логических функций Триггеры на логических элементах. Rs-триггер. Принцип работы. Схемная реализация. Таблица истинности. Временная диаграмма		Лекция 2 Биоэнергетические функции митохондрий Нарушение функций митохондрий при тканевой гипоксии Нарушение биоэнергетических функций митохондрий одно из наиболее ранних проявлений повреждения клеток. Нарушение биоэнергетических функций митохондрий одно из наиболее ранних проявлений повреждения клеток
	Правила вычисления предела числового ряда и функции Понятие производной и ее геометрический и экономический смысл Техника дифференцирования простых функций Суть метода выделения полного квадрата при интегрировании дробно-рациональной функции		Вопросы к экзамену по дисциплине «Дискретная математика» для специальностей Функционально полные системы функций. Критерий функционально полноты системы функций (теорема Поста-Яблонского)
	Вопросы к экзамену по математике Непрерывность функции. Свойства непрерывных функций. Классификация точек разрыва