Home  »  Общая математика   »   5630.Учебная работа .Тема:Эквиваленты функций

5630.Учебная работа .Тема:Эквиваленты функций

1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...
Контрольные рефераты

Тема:Эквиваленты функций»,»

Контрольная работа

Эквиваленты функций

Используя таблицу истинности, установить эквивалентность функций в формуле:

Решение:

Обозначим:

Составим таблицу истинности для правой и левой части функции:

0001110111010101110001111101011000010101010101011110011100111010101111000101010101111101010101001100010111000111010101111100001101001000

Ответ: Как видно из таблицы, значения правой и левой части равенства действительно совпадают, значит, функции в данной формуле эквивалентны.

Определить к каким классам (константы нуля, константы единицы, самодвойственных функций, монотонных функций, линейных функций, симметрических функций) относится функция следующего вида:

Обозначим:

Решение:

  1. Составим таблицу истинности:

0001001110011100010000110011010011000011101110000110010011100100

  1. Т. к. f(0,0,0) ¹ 0, значит, данная функция не относится к классу константы 0.
  2. Т. к. f (1,1,1) = 0, значит, данная функция относится к классу не сохраняющих константу 1.
  3. Т. к. f(0,1,1) < f (0,1,0) и f(1,0,0) = f(0,1,1), значит, данная функция не относится к классу монотонных функций.
  4. Т. к., например, f(0,0,0) ¹ f(1,1,1) или f(0,0,1) ¹ f(1,1,0), то данная функция относится к классу самодвойственных функций.
  5. Т. к. не выполняется условие f(0,1,1) = f(1,0,1) = f(1,1,0) (значения соответственно равны 0,0,1), то данная функция не относится к классу симметрических функций.
  6. Проверим принадлежность функции к классу линейных функций.

Для этого запишем ее в таком виде:

Найдем коэффициенты Ci :

f (0,0,0) = 1 (из таблицы истинности)

, т.о., С0 = 1.

f(1,0,0 )= 0 (из таблицы истинности)

, т.о., С1 = 1.

f(0,1,0) = 1 (из таблицы истинности)

, т.о., С2 = 0.

f(0,0,1) = 0 (из таблицы истинности)

,т.о., С3 = 1.

Тогда f1(x1,x2,x3) = 1.

Сравним значения функций f и f1 по таблице истинности:

0001110001010110010111011101010110111101

Т. к. значения функций различны для одинаковых наборов, то данная функция не относится к классу линейных функций.

Ответ: данная функция относится к классу константы 1.

Необходимо для данной ФАЛ f(x1,x2,x3,x4) найти ее ДСНФ, КСНФ, ПСНФ, ЭСНФ, ИСНФ, принимающей значение 1 на следующих наборах:

4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15.

Решение:

  1. Составим таблицу истинности:

№000000100010200100300110401001501011601101701111810001910011101010111101111211001131101114111001511111

  1. Для получения ДСНФ, ПСНФ используем термы для 1 значений функции:

  1. Для получения КСНФ, ЭСНФ используем термы для 0 значений функции:

Используя метод неопределенных коэффициентов, необходимо найти МДНФ функции f(x1,x2,x3), принимающей значение 1 на наборах:

0, 3, 4, 7.

Решение:

1.Составим таблицу истинности:

№0000110010201003011141001510106110071111

2.

К10 \/ К20 \/ К30 \/ К1200 \/ К1300 \/ К2300 \/ К123000 = 1

К10 \/ К20 \/ К31 \/ К1200 \/ К1301 \/ К2301 \/ К123001 = 0

К10 \/ К21 \/ К30 \/ К1201 \/ К1300 \/ К2310 \/ К123010 = 0

К10 \/ К21 \/ К31 \/ К1201 \/ К1301 \/ К2311 \/ К123011 = 1

К11 \/ К20 \/ К30 \/ К1210 \/ К1310 \/ К2300 \/ К123100 = 1

К11 \/ К20 \/ К31 \/ К1210 \/ К1311 \/ К2301 \/ К123101 = 0

К11 \/ К21 \/ К30 \/ К1211 \/ К1310 \/ К2310 \/ К123110 = 0

К11 \/ К21 \/ К31 \/ К1211 \/ К1311 \/ К2311 \/ К123111 = 1

  1. Приравняем 0 все коэффициенты при 0 значениях функции:

К10 = К20 = К31 = К1200 = К1301 = К2301 = К123001 = 0

К10 = К21 = К30 = К1201 = К1300 = К2310 = К123010 = 0

К11 = К20 = К31 = К1210 = К1311 = К2301 = К123101 = 0

К11 = К21 = К30 = К1211 = К1310 = К2310 = К123110 = 0

  1. Вычеркнем 0 коэффициенты из коэффициентов при 1 значениях функции:

К2300 \/ К123000 = 1

К2311 \/ К123011 = 1

К2300 \/ К123100 = 1

К2311 \/ К123111 = 1

  1. Найдем минимальное покрытие: К2300 и К2311 ,т. е.

f1(x1,x2,x3) =

6. Проверка:

№000011100100201000301111410011510100611000711111

Т.к. f =f1, то преобразования выполнены верно.

Ответ: f1(x1,x2,x3) = .

Используя метод Квайна, необходимо найти МДНФ функции f(x1,x2,x3,x4), принимающей значение 1 на наборах: 3, 4, 5, 6, 13, 14, 15.

Решение:

1. Составим таблицу истинности:

№000000100010200100300111401001501011601101701110810000910010101010011101101211000131101114111011511111

  1. Выпишем термы для 1 значений функции и склеим все возможные:

1. 3. 4. 5. 6. 7.

  1. Составим таблицу и найдем минимальное покрытие:

1234567++++++++++++

В данном случае следующие импликанты являются существенными:

  1. Проверка:

№0000000100010020010003001111401001150101116011011701110081000009100100101010001110110012110000131101111411101115111111

Т. к. f1 = f, то преобразования выполнено верно.

Ответ:

Используя метод Квайна Мак Класки , необходимо найти МДНФ функции f(x1,x2,x3,x4), принимающей значение 1 на наборах: 2, 6, 7, 10 ,12 ,13 14, 15.

Решение:

  1. Составим таблицу истинности:

№000000100010200101300110401000501010601101701111810000910010101010111101101211001131101114111011511111

  1. Составим группы по количеству единиц и выполним необходимые преобразования:

№20010по 1 единице60110101010по 2 единицы12110070111131101по 3 единицы141110151111по 4 единицы

1. 2. 3. 4. 5. 6. 7. 8. 9. 10.(2,6) = 0_10 (2,10) = _010 (6,7) = 011_ (6,14) = _110 (10,14) = 1_10 (12,13) = 110_ (12,14) = 11_0 (7,15) = _111 (13,15) = 11_1 (14,15) = 111_

  1. Составим таблицу и найдем минимальное покрытие:

001001100111101011001101111011110_10++_010++011_++_110++1_10++110_++11_0++_111++11_1++111_++

Импликанты , , и являются существенными. Т. о., получаем:

.

  1. Проверка:

№0000000100010020010113001100401000050101006011011701111181000009100100101010111110110012110011131101111411101115111111

Т.к. f1 = f, то преобразования выполнено верно.

Ответ:

Используя метод диаграмм Вейча, необходимо найти МДНФ функции f(x1,x2,x3,x4), принимающей значение 1 на наборах: 0, 2, 4, 8, 12, 14, 15.

Решение:

1. Составим таблицу истинности:

№00000110001020010130011040100150101060110070111081000191001010101001101101211001131101014111011511111

  1. Для булевой функции 4х переменных диаграмма Вейча имеет вид:

00000010=00_000000100=0_0011001110=11_011001000=1_0011111110=111_

Получаем:

  1. Проверка:

№000001110001002001011300110040100115010100601100070111008100011910010010101000110110012110011131101001411101115111111

Т. к. f1 = f, то преобразования выполнено верно.

Ответ:

константа эквивалентность дизъюнктивная форма функция

Список использованной литературы

1.Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. М.: Наука,1977.

.Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика. М.: Наука. Физматлит, 2000.

.Информатика: Энциклопедический словарь для начинающих /Сост. Д.А. Поспелов. М.: Педагогика Пресс, 1994.

.Кузнецов О.П., АдельсонВельский Г.М. Дискретная математика для инженера. М.: Энергоатомиздат,1988.

.Лихтарникова Л.М.,Сукачева Т.Г. Математическая логика / Курс лекций. СПб. : Издательство «Лань», 1998.

.Логинов Б.М. Лекции и упражнения по курсу «Введение в дискретную математику». Калуга: МГТУ им.Н.Э. Баумана, 1998.

.Нефедов В.Н., Осипова В.А. Курс дискретной математики: Учеб. пособие.М.: Издво МАИ,1992.

.Савельев А.П. Прикладная теория цифровых автоматов. М.: Наука,1985.

.Фудзисава Т., Касами Т. Математика для радиоинженеров: Теория дискретных структур: Пер. с япон. М.: Радио и связь,1984.

.Муха Ю.П., Авдеюк О.А., Скворцов М.Г. Математическая логика. Конспект лекций по теоретической информатике: Учеб. пособие/ ВолгГТУ. Волгоград, 2001.

/ Муха Ю.П., Авдеюк О.А. Математическая логика и теория алгоритмов. Конспект лекций: Учеб. пособие/ ВолгГТУ. Волгоград, 2005.

Нет похожих работ.

➤