Целью курса является изучение основ специальных разделов современной дискретной математики, широко используемых при разработке цифровых систем различного профиля. Знание основ дискретной математики является необходимым в практической деятельности инженера. Базой для преподавания этих дисциплин наряду с классическими методами анализа непрерывных физических моделей стали алгебраические, логические и комбинаторные методы исследования различных моделей дискретной математики.
Основными задачами курса являются:
создание у студентов теоретической подготовки, достаточной для освоения дисциплин по специальности, а также для чтения специальной технической литературы;
формирование у студентов научного мировоззрения, достаточного в частности для усвоения основных математических моделей и методов их исследования;
выработка у студентов приемов и навыков решения конкретных задач в различных разделах дискретной математики, с упором на возможность использования этих задач в качестве модельных для исследования цифровых систем;
ознакомление студентов с использованием современных алгоритмических и вычислительных средств для решения задач дискретной математики большой размерности.
Студент должен знать и уметь:
· основные дискретные модели и структуры;
· определять возможности применения теоретических положений и методов математического анализа для постановки и решения практических задач методами дискретной математики;
· применять основополагающие оптимизационные методы решения.
Место дисциплины в учебном процессе
Дисциплина относится к циклу общих математических и естественно-научных дисциплин. Курс Дискретной математики базируется на разделах, изучаемых в дисциплинах "Высшая математика", "Логика", "Информатика".
Основные положения дисциплины должны быть использованы в дальнейшем при изучении следующих дисциплин: «Теория вероятностей и математическая статистика», «Математическая логика и теория алгоритмов», «Методы оптимизации», «Организация ЭВМ и систем», «Сети ЭВМ и телекоммуникации», «Теория систем и системный анализ», «Теория принятия решений».
Для студентов заочной формы обучения основной в учебной деятельности является самостоятельная работа с литературными и прочими информационными источниками.
Средством контроля знаний студентов-заочников является контрольная работа, в которой студент должен показать усвоенные им теоретические знания и определенные практические навыки.
Внимательно изучив разделы рекомендуемой основной литературы, письменно ответьте на поставленные вопросы вашего варианта. Номер варианта выбирается по последней цифре зачетки (студенческого билета). Контрольная работа предусматривает выполнение студентом 12 задач. Первая тема посвящена изучению материала разделов «Теория множеств и отношения». Вторая тема составлена из задач математической логики и построения логических схем.
Структура контрольной работы:
· Титульный лист (наименование учебной дисциплины, специальность, курс, шифр группы, фамилия, имя, отчество автора и т.д.).
· Основная часть, состоящая из двух тем «Теория множеств и отношения» и «Математическая логика».
· Список использованной литературы.
Контрольная работа оформляется по всем правилам оформления печатных работ, то есть на листах формата А4. Допускается оформление рукописно в отдельной тетради (12-18листов) страницы должны быть пронумерованы, рисунки и таблицы подписаны и т.д. Законченная и правильно оформленная работа предъявляется на рецензию с обязательной регистрацией в деканате факультета Информационных технологий ВСЭИ. Контрольная работа сдается до первого дня сессии или в первый день сессии в деканат.
Задания для контрольной работы
Номер варианта выбирается по последней цифре зачетки (студенческого билета).
Тема 1. « Теория множеств и отношения»
Знак инверсии обозначается чертой над символом или скобкой Ø перед символом.
1. Выполнить над множествами следующие операции и дать графическую интерпретацию.
· `A È (C D B) для варианта множеств а).
· B \ Ø (A Ç C) для варианта множеств b).
· C Ç ØB \ A для варианта множеств c).
2. Выяснить выполняется ли соотношение (графически):
( `A È B ) Ç A = A È B.
3. Найдите произведение множеств A ´ B, B ´ C и A2 и их мощности для варианта множеств c).
4. Найдите проекцию множеств A ´ B´ C на 2, 3 составляющие, то есть Пр2,3 A ´ B´ C для варианта множеств a).
5. Дано множество M={m: m =x+y, x ' A, y ' C} для варианта множеств а). и отношение R={(a, b): a, b ' M, a+b < 11}
· Записать отношение в явном виде и найти обратное отношение R-1,
· представить R линейно-координатным способом,
· выяснить какими свойствами обладает данное отношение,
6. На одной из кафедр университета работают 13 человек, причем каждый из них знает хотя бы один иностранный язык. 10 чел. знают английский, 7 чел. – немецкий, 6 чел. – французский, 5 чел. знают и английский, и немецкий, 4 – английский и французский, 3 - немецкий и французский. Сколько человек знают все три языка? Сколько человек знают два языка? Сколько человек знают только английский?
7. Сколькими способами можно составить трехцветный полосатый флаг, если имеется материал 5 различных цветов? Та же самая задача, если одна из полос должна быть красной?
1. Выполнить над множествами следующие операции и дать графическую интерпретацию.
· `A È C Ç B для варианта множеств а).
· B D A Ç C для варианта множеств b).
· C \ B Ç `A для варианта множеств c).
2. Выяснить выполняется ли соотношение (графически):
A\(C È B)=(A\B)\C.
3. Найдите произведение множеств A ´ C, B ´ A и C2 и их мощности для варианта множеств c).
4. Найдите проекцию множеств A ´ C´ B на 2, 3 составляющие, то есть Пр2,3 A ´ C´ B для варианта множеств a).
5. Дано множество M={m: m =x+y, x ' A, y ' B} для варианта множеств а). и отношение R={(a, b): a, b ' M, a+b - нечетное}
· Записать отношение в явном виде и найти обратное отношение R-1,
· представить R линейным способом,
· выяснить какими свойствами обладает данное отношение,
6. Известно, что из 100 студентов живописью увлекаются 28 чел., спортом – 42 чел., музыкой – 30 чел., живописью и спортом – 10 чел., живописью и музыкой - 8 чел., спортом и музыкой – 5. живописью, спортом и музыкой – 3 чел. Определить a). сколько человек увлекается только спортом, b). сколько человек ничем не увлекается, c). сколько человек увлекается хотя бы живописью и музыкой ?
7. Сколькими способами можно выбрать из полной колоды карт (содержащей 52 карты) по одной карте каждой масти так, чтобы карты красных мастей и карты чёрных мастей образовывали пары( например, девятки пик и треф и валеты бубен и червей)?
1. Выполнить над множествами следующие операции и дать графическую интерпретацию.
a. `B Ç (C D A) для варианта множеств а).
b. ØB È (A \ C) для варианта множеств b).
c. C È `B Ç A для варианта множеств c).
2. Выяснить выполняется ли соотношение (графически):
A\B ÈC = A ÇB \ C Ç`B
3. Найдите произведение множеств C ´ B, A ´ C и B2 и их мощности для варианта множеств c).
4. Найдите проекцию множеств C ´ A´ B на 2, 3 составляющие, то есть Пр2,3 C ´ A´ B для варианта множеств a).
5. Дано множество M={m: m =x+y, x ' B, y ' C} для варианта множеств а). и отношение R={(a, b): a, b ' M, I a-b I < 9}
· Записать отношение в явном виде, найти обратное отношение R-1 ,
· представить R координатным способом,
· выяснить какими свойствами обладает данное отношение,
6. В отделе НИИ работает несколько человек, причем каждый из них знает хотя бы один иностранный язык. 10 чел. знают английский, 9 чел. – немецкий, 7 чел. – французский, 4 чел. знают и английский, и немецкий, 2 – английский и французский, 2 - немецкий и французский, а один человек знает все три языка. Определить a). сколько человек работает в отделе? b). сколько человек знают ровно два языка? c). сколько человек знают только английский?
7. Рота состоит из 3 офицеров, 6 сержантов и 60 рядовых. Сколькими способами можно выделить из них отряд, состоящий из одного офицера, 2 сержантов и 20 рядовых? Та же задача, если в отряд должен войти командир роты и старший из сержантов.
1. Выполнить над множествами следующие операции и дать графическую интерпретацию.
· `C È B \ A Ç B для варианта множеств а).
· (C D A) \C для варианта множеств b).
· A \ B Ç `C для варианта множеств c).
2. Выяснить выполняется ли соотношение (графически):
A Ç (B \ C) = (AÇ B) \ (A Ç C).
3. Найдите произведение множеств A ´ C, C ´ B и C2 и их мощности для варианта множеств c).
4. Найдите проекцию множеств A ´ C´ B на 2, 3 составляющие, то есть Пр2,3 A ´ C´ B для варианта множеств a).
5. Дано множество M={m: m =x+y, x ' B, y ' C} для варианта множеств а). и отношение R={(a, b): a, b ' M, a+b - четное}
· Записать отношение в явном виде и найти обратное отношение R-1 ,
· представить R графовым способом,
· выяснить какими свойствами обладает данное отношение,
6. На загородную прогулку поехало 92 человека. Бутерброды с колбасой взяли 47 чел., с сыром – 38 чел., с ветчиной – 42 чел., и с сыром и с колбасой – 28 чел., с колбасой и ветчиной – 31 чел., с сыром и ветчиной - 26 чел. Все три вида бутербродов 25 чел., а несколько человек вместо бутербродов захватили с собой пирожки. a). сколько человек взяли с собой пирожки? b). сколько человек взяли с собой только бутерброды с колбасой? c). сколько человек взяли с собой только бутерброды с сыром?
7. В некотором государстве не было двух жителей с одинаковым набором зубов. Какова может быть наибольшая численность населения государства (наибольшее число зубов равно 32)?
1. Выполнить над множествами следующие операции и дать графическую интерпретацию.
d. `A È (C D B) для варианта множеств а).
e. B \ Ø (A Ç C) для варианта множеств b).
f. `C Ç B \ A для варианта множеств c).
2. Выяснить выполняется ли соотношение (графически):
( `A È B ) Ç A = A È B.
3. Найдите произведение множеств A ´ B, B ´ C и A2 и их мощности для варианта множеств c).
4. Найдите проекцию множеств A ´ B´ C на 2, 3 составляющие, то есть Пр2,3 A ´ B´ C для варианта множеств a).
5. Дано множество M={m: m =x+y, x ' A, y ' C} для варианта множеств а). и отношение R={(a, b): a, b ' M, a+b < 11}
· Записать отношение в явном виде, найти обратное отношение R-1
· представить R линейно- координатным способом,
· выяснить какими свойствами обладает данное отношение,
6. На одной из кафедр университета работают 13 человек, причем каждый из них знает хотя бы один иностранный язык. 10 чел. знают английский, 7 чел. – немецкий, 6 чел. – французский, 5 чел. знают и английский, и немецкий, 4 – английский и французский, 3 - немецкий и французский. Сколько человек знают все три языка? Сколько человек знают ровно два языка? Сколько человек знают только французский?
7. Сколькими способами можно составить трехцветный полосатый флаг, если имеется материал 5 различных цветов, причем полосы могут быть и вертикальные и горизонтальные? Та же самая задача, если одна из полос должна быть красной?
1. Выполнить над множествами следующие операции и дать графическую интерпретацию.
· `A È C Ç B для варианта множеств а).
· B D A Ç C для варианта множеств b).
· C \ `B Ç A для варианта множеств c).
2. Выяснить выполняется ли соотношение (графически):
A\(C È B)=(A\B)\C.
3. Найдите произведение множеств A ´ C, B ´ A и C2 и их мощности для варианта множеств c).
4. Найдите проекцию множеств A ´ C´ B на 2, 3 составляющие, то есть Пр2,3 A ´ C´ B для варианта множеств a).
5. Дано множество M={m: m =x+y, x ' A, y ' B} для варианта множеств а). и отношение R={(a, b): a, b ' M, a+b - нечетное}
· Записать отношение в явном виде, найти обратное отношение R-1 .
· представить R линейным способом,
· выяснить какими свойствами обладает данное отношение,
6. Известно, что из 100 студентов живописью увлекаются 28 чел., спортом –42 чел., музыкой – 30 чел., живописью и спортом – 10 чел., живописью и музыкой - 8 чел., спортом и музыкой – 5. живописью, спортом и музыкой –3 чел. Определить a). сколько человек увлекается только музыкой, b). сколько человек ничем не увлекается, c). сколько человек увлекается хотя бы живописью и музыкой ?
7. Надо послать 7 срочных писем. Сколькими способами это можно сделать, если для передачи писем можно послать 3 курьеров и каждое письмо можно дать любому из 3 курьеров?
1. Выполнить над множествами следующие операции и дать графическую интерпретацию.
a. `B Ç (C D A) для варианта множеств а).
b. B È Ø (A \ C) для варианта множеств b).
c. `C È B Ç A для варианта множеств c).
2. Выяснить выполняется ли соотношение (графически):
A\B ÈC = A ÇB \ C Ç`B
3. Найдите произведение множеств C ´ B, A ´ C и B2 и их мощности для варианта множеств c).
4. Найдите проекцию множеств C ´ A´ B на 2, 3 составляющие, то есть Пр2,3 C ´ A´ B для варианта множеств a).
5. Дано множество M={m: m =x+y, x ' B, y ' C} для варианта множеств а). и отношение R={(a, b): a, b ' M, I a-b I < 9}
· Записать отношение в явном виде, найти обратное отношение R-1
· представить R координатным способом,
· выяснить какими свойствами обладает данное отношение,
6. В отделе НИИ работает несколько человек, причем каждый из них знает хотя бы один иностранный язык. 10 чел. знают английский, 9 чел. – немецкий, 7 чел. – французский, 4 чел. знают и английский, и немецкий, 2 – английский и французский, 2 - немецкий и французский, а один человек знает все три языка. Сколько человек работает в отделе? Сколько человек знают ровно два языка? Сколько человек знают только немецкий?
7. Рота состоит из 5 офицеров, 8 сержантов и 80 рядовых. Сколькими способами можно выделить из них отряд, состоящий из одного офицера, 2 сержантов и 20 рядовых? Та же задача, если в отряд должен войти командир роты и старший из сержантов.
1. Выполнить над множествами следующие операции и дать графическую интерпретацию.
· `C È B \ A Ç B для варианта множеств а).
· (C D A) \C для варианта множеств b).
· A \ B Ç `C для варианта множеств c).
2. Выяснить выполняется ли соотношение (графически):
A Ç (B \ C) = (AÇ B) \ (A Ç C).
3. Найдите произведение множеств A ´ C, C ´ B и C2 и их мощности для варианта множеств c).
4. Найдите проекцию множеств A ´ C´ B на 2, 3 составляющие, то есть Пр2,3 A ´ C´ B для варианта множеств a).
5. Дано множество M={m: m =x+y, x ' B, y ' C} для варианта множеств а). и отношение R={(a, b): a, b ' M, a+b - четное}
· Записать отношение в явном виде, найти обратное отношение R-1
· представить R графовым способом,
· выяснить какими свойствами обладает данное отношение,
6. На загородную прогулку поехало 90 человека. Бутерброды с колбасой взяли 47 чел., с сыром – 38 чел., с ветчиной – 42 чел., и с сыром и с колбасой – 28 чел., с колбасой и ветчиной – 28 чел., с сыром и ветчиной - 24 чел. Все три вида бутербродов 20 чел., а несколько человек вместо бутербродов захватили с собой пирожки. a). Сколько человек взяли с собой пирожки? b). Сколько человек взяли с собой только бутерброды с колбасой? c). Сколько человек взяли с собой только бутерброды с сыром?
7. Из студенческой группы надо избрать делегацию, состоящую из 5 человек на конференцию. Сколькими способами это можно сделать, если в группе 20 человек?
1. Выполнить над множествами следующие операции и дать графическую интерпретацию.
d. `A È (C D B) для варианта множеств а).
e. ØB \ (A Ç C) для варианта множеств b).
f. C Ç B \ ØA для варианта множеств c).
2. Выяснить выполняется ли соотношение (графически):
( `A È B ) Ç A = A Ç B.
3. Найдите произведение множеств A ´ B, B ´ C и A2 и их мощности для варианта множеств c).
4. Найдите проекцию множеств A ´ B´ C на 2, 3 составляющие, то есть Пр2,3 A ´ B´ C для варианта множеств a).
5. Дано множество M={m: m =x+y, x ' A, y ' C} для варианта множеств а). и отношение R={(a, b): a, b ' M, a+b < 11}
· Записать отношение в явном виде и найти обратное отношение R-1,
· представить R линейно- координатным способом,
· выяснить какими свойствами обладает данное отношение,
6. На одной из кафедр университета работают 13 человек, причем каждый из них знает хотя бы один иностранный язык. 10 чел. знают английский, 7 чел. – немецкий, 6 чел. – французский, 5 чел. знают и английский, и немецкий, 4 – английский и французский, 3 - немецкий и французский. Сколько человек знают все три языка? Сколько человек знают ровно два языка? Сколько человек знают только французский?
7. На школьном вечере присутствуют 12 девушек и 9 юношей. Сколькими способами можно выбрать из них 4 пары для танца?
1. Выполнить над множествами следующие операции и дать графическую интерпретацию.
· `A È C Ç B для варианта множеств а).
· B D A Ç C для варианта множеств b).
· C \ B Ç `A для варианта множеств c).
2. Выяснить выполняется ли соотношение (графически):
A\(C È B)=(A\B) ÇC.
3. Найдите произведение множеств A ´ C, B ´ A и C2 и их мощности для варианта множеств c).
4. Найдите проекцию множеств A ´ C´ B на 2, 3 составляющие, то есть Пр2,3 A ´ C´ B для варианта множеств a).
5. Дано множество M={m: m =x+y, x ' A, y ' B} для варианта множеств а). и отношение R={(a, b): a, b ' M, a+b - нечетное}
· Записать отношение в явном виде и найти обратное отношение R-1,
· представить R линейным способом,
· выяснить какими свойствами обладает данное отношение,
6. Известно, что из 100 студентов живописью увлекаются 28 чел., спортом –42 чел., музыкой – 30 чел., живописью и спортом – 10 чел., живописью и музыкой - 8 чел., спортом и музыкой – 5. живописью, спортом и музыкой –3 чел. Определить a). сколько человек увлекается только спортом, b). сколько человек ничем не увлекается, c). сколько человек увлекается хотя бы спортом или музыкой ?
7. Сколько словарей надо издать, чтобы можно было непосредственно выполнять переводы с любого из 5 языков: русского, английского, французского, немецкого, итальянского, на любой другой из этих 5 языков?
Тема 2 «Математическая логика и схемы»
Вариант № 1
1. Упростить выражение
y(a,b,c)= (aÚ bc)ac Ú bÅc
2. Построить алгебраическими преобразованиями СДНФ
f(x1,x2,x3,)=x1x2Ú (x1®x2)x3Ú x2x3
3. Построить алгебраическими преобразованиями СКНФ
f(x,y,z)=x(yzÚ xz)Ú xyz.
4. Минимизировать функции по картам Карно и найти сложность по Квайну:
а) Найти мин. сумму б). Найти мин произведение
-
-
-
-
5. Для данного выражения выполнить преобразование в базис операции штрих Шеффера. Дать схемную реализацию в базисе (И-НЕ).
y(a,b,c) = (abÚ c)(abÚ abc)Ú (aÚ bc)
Вариант № 2
1. Упростить выражение
y(a,b,c ) = (aÚ bc)ac Ú b®c
2. Построить алгебраическими преобразованиями СДНФ
f(x,y,z) = (xyÚ xyz)xÅy
3. Построить алгебраическими преобразованиями СКНФ
в) f(x,y,z)=x(yzÚ xz)Ú xyz.
4. Минимизировать функции по картам Карно и найти сложность по Квайну:
а) Найти мин. сумму б). Найти мин произведение
-
-
-
-
5. Для данного выражения выполнить преобразование в базис операции стрелка Пирса. Дать схемную реализацию в базисе (ИЛИ-НЕ).
f(a,b,c,d)= `ab Ú bcÚ `cd
Вариант № 3
1. Упростить выражение
f(x,y,z) = (xyÚ y)® x
2. Построить алгебраическими преобразованиями СДНФ
f(a,b,c,d)=(abÚ c)abÚ cdÚ abc
3. Построить алгебраическими преобразованиями СКНФ
f(x,y,z) = xyÅ yz
4. Минимизировать функции по картам Карно и найти сложность по Квайну:
а) Найти мин. сумму б). Найти мин произведение
-
-
-
-
-
5. Для данного выражения выполнить преобразование в базис операции штрих Шеффера. Дать схемную реализацию в базисе (И-НЕ).
y(a,b,c) = (abÚ c) (abÚ abc)
Вариант № 4
1. Упростить выражение
f = x1®( x2 Ú x1x2x3Ú x2x3Ú x1x3)
2. Построить алгебраическими преобразованиями СДНФ
y=abcÚ a(bcÚ bc)
3. Построить алгебраическими преобразованиями СКНФ
в) f(x,y,z)=x(yzÚ xz)Ú xyz.
4. Минимизировать функции по картам Карно и найти сложность по Квайну:
а) Найти мин. сумму б). Найти мин произведение
-
-
-
-
-
-
5. Для данного выражения выполнить преобразование в базис операции стрелка Пирса. Дать схемную реализацию в базисе (ИЛИ-НЕ).
f(x,y,z) = (xyÚ z)Å (xÚ y) (xÚ z)
Вариант № 5
1. Упростить выражение
y(a,b,c)= (aÚ bc)ac Ú bÅc
2. Построить алгебраическими преобразованиями СДНФ
f(x1,x2,x3,)=x1x2Ú (x1®x2)x3Ú x4x3
3. Построить алгебраическими преобразованиями СКНФ
f(x,y,z)=x(yzÚ xz)Ú xyz.
4. Минимизировать функции по картам Карно и найти сложность по Квайну:
а) Найти мин. сумму б). Найти мин произведение
-
-
-
-
5. Для данного выражения выполнить преобразование в базис операции штрих Шеффера. Дать схемную реализацию в базисе (И-НЕ).
y(a,b,c) = (abÚ c)(abÚ abc)Ú (aÚ bc)
Вариант № 6
1. Упростить выражение
y(a,b,c ) = (aÚ bc)ac Ú b®c
2. Построить алгебраическими преобразованиями СДНФ
f(x,y,z) = (xyÚ xyz)xÅy
3. Построить алгебраическими преобразованиями СКНФ
в) f(x,y,z)=x(yzÚ xz)Ú xyz.
4. Минимизировать функции по картам Карно и найти сложность по Квайну:
а) Найти мин. сумму б). Найти мин произведение
-
-
-
-
-
5. Для данного выражения выполнить преобразование в базис операции стрелка Пирса. Дать схемную реализацию в базисе (ИЛИ-НЕ).
f(a,b,c,d)= `ab Ú b`cÚ cd(`cÚ cd)
Вариант № 7
1. Упростить выражение
f(x,y,z) = (xyÚ y)® x
2. Построить алгебраическими преобразованиями СДНФ
f(a,b,c,d)=(abÚ c)abÚ cdÚ abc
3. Построить алгебраическими преобразованиями СКНФ
f(x,y,z) = xyÅ yz
4. Минимизировать функции по картам Карно и найти сложность по Квайну:
а) Найти мин. сумму б). Найти мин произведение
-
-
-
-
-
5. Для данного выражения выполнить преобразование в базис операции штрих Шеффера. Дать схемную реализацию в базисе (И-НЕ).
y(a,b,c) = (abÚ c) (abÚ bc)
Вариант № 8
1. Упростить выражение
f = x1® x2 Ú x1x2x3Ú x2x3Ú x1x3
2. Построить алгебраическими преобразованиями СДНФ
y=abcÚ a(bcÚ bc)
3. Построить алгебраическими преобразованиями СКНФ
в) f(x,y,z)=x(yzÚ xz)Ú xyz.
4. Минимизировать функции по картам Карно и найти сложность по Квайну:
а) Найти мин. сумму б). Найти мин произведение
-
-
-
-
-
5. Для данного выражения выполнить преобразование в базис операции стрелка Пирса. Дать схемную реализацию в базисе (ИЛИ-НЕ).
f(x,y,z) = (xyÚ z)Å (xÚ y) `(xÚ z)
Вариант № 9
1. Упростить выражение
y(a,b,c)= (abÚ bc)ac Ú bÅc
2. Построить алгебраическими преобразованиями СДНФ
f(x1,x2,x3,)=x1x2Ú (x1®x2)x3Ú x4x3
3. Построить алгебраическими преобразованиями СКНФ
f(x,y,z)=x(yzÚ xz)Ú xy.
4. Минимизировать функции по картам Карно и найти сложность по Квайну:
а) Найти мин. сумму б). Найти мин произведение
-
-
-
-
-
5. Для данного выражения выполнить преобразование в базис операции штрих Шеффера. Дать схемную реализацию в базисе (И-НЕ).
y(a,b,c) = (abÚ c)(abÚ abc)
Вариант № 10
1. Упростить выражение
y(a,b,c ) = (aÚ bc)c Ú (b®c)
2. Построить алгебраическими преобразованиями СДНФ
f(x,y,z) = (xyÚ xyz) (xÅy)
3. Построить алгебраическими преобразованиями СКНФ
в) f(x,y,z)=x(zÚ x)Ú xyz.
4. Минимизировать функции по картам Карно и найти сложность по Квайну:
а) Найти мин. сумму б). Найти мин произведение
-
-
-
-
-
5. Для данного выражения выполнить преобразование в базис операции стрелка Пирса. Дать схемную реализацию в базисе (ИЛИ-НЕ).
f(x1,x2,x3,)=x1x2Ú (x1®x2)x3Ú x2x3
f(x,y,z)=x(yzÚ xz)Ú xyz.
f(x,y,z) = (xyÚ y)® x
f(a,b,c,d)=(abÚ c)abÚ cdÚ abc
f(x,y,z) = xyÅ yz
y(a,b,c) = (abÚ c) (abÚ abc)
f(x,y,z) = (xyÚ z)Å (xÚ y) (xÚ z)
3. Построить алгебраическими преобразованиями СКНФ
f(x,y,z)=x(yzÚ xz)Ú xyz.
y(a,b,c) = (abÚ c)(abÚ abc)Ú (aÚ bc)
f(a,b,c,d)=(abÚ c)abÚ cdÚ abc
f = x1® x2 Ú x1x2x3Ú x2x3Ú x1x3
3. Построить алгебраическими преобразованиями СКНФ
f(x,y,z) = (xyÚ z)Å (xÚ y) `(xÚ z)
