Рефераты - Афоризмы - Словари
Русские, белорусские и английские сочинения
Русские и белорусские изложения
 

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

Работа из раздела: «Математика»

/

14

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

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

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

Решение:

Обозначим:

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

0

0

0

1

1

1

0

1

1

1

0

1

0

1

0

1

1

1

0

0

0

1

1

1

1

1

0

1

0

1

1

0

0

0

0

1

0

1

0

1

0

1

0

1

0

1

0

1

1

1

1

0

0

1

1

1

0

0

1

1

1

0

1

0

1

0

1

1

1

1

0

0

0

1

0

1

0

1

0

1

0

1

1

1

1

1

0

1

0

1

0

1

0

1

0

0

1

1

0

0

0

1

0

1

1

1

0

0

0

1

1

1

0

1

0

1

0

1

1

1

1

1

0

0

0

0

1

1

0

1

0

0

1

0

0

0

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

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

Обозначим:

Решение:

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

0

0

0

1

0

0

1

1

1

0

0

1

1

1

0

0

0

1

0

0

0

0

1

1

0

0

1

1

0

1

0

0

1

1

0

0

0

0

1

1

1

0

1

1

1

0

0

0

0

1

1

0

0

1

0

0

1

1

1

0

0

1

0

0

Т. к. f(0,0,0) 0, значит, данная функция не относится к классу константы 0.

Т. к. f (1,1,1) = 0, значит, данная функция относится к классу не сохраняющих константу 1.

Т. к. f(0,1,1) < f (0,1,0) и f(1,0,0) = f(0,1,1), значит, данная функция не относится к классу монотонных функций.

Т. к., например, f(0,0,0) f(1,1,1) или f(0,0,1) f(1,1,0), то данная функция относится к классу самодвойственных функций.

Т. к. не выполняется условие f(0,1,1) = f(1,0,1) = f(1,1,0) (значения соответственно равны 0,0,1), то данная функция не относится к классу симметрических функций.

Проверим принадлежность функции к классу линейных функций.

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

Найдем коэффициенты 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 по таблице истинности:

0

0

0

1

1

1

0

0

0

1

0

1

0

1

1

0

0

1

0

1

1

1

0

1

1

1

0

1

0

1

0

1

1

0

1

1

1

1

0

1

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

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

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

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

Решение:

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

0

0

0

0

0

0

1

0

0

0

1

0

2

0

0

1

0

0

3

0

0

1

1

0

4

0

1

0

0

1

5

0

1

0

1

1

6

0

1

1

0

1

7

0

1

1

1

1

8

1

0

0

0

1

9

1

0

0

1

1

10

1

0

1

0

1

11

1

0

1

1

1

12

1

1

0

0

1

13

1

1

0

1

1

14

1

1

1

0

0

15

1

1

1

1

1

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

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

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

0, 3, 4, 7.

Решение:

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

0

0

0

0

1

1

0

0

1

0

2

0

1

0

0

3

0

1

1

1

4

1

0

0

1

5

1

0

1

0

6

1

1

0

0

7

1

1

1

1

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

Приравняем 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

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

К2300 / К123000 = 1

К2311 / К123011 = 1

К2300 / К123100 = 1

К2311 / К123111 = 1

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

f1(x1,x2,x3) =

6. Проверка:

0

0

0

0

1

1

1

0

0

1

0

0

2

0

1

0

0

0

3

0

1

1

1

1

4

1

0

0

1

1

5

1

0

1

0

0

6

1

1

0

0

0

7

1

1

1

1

1

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

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

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

Решение:

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

0

0

0

0

0

0

1

0

0

0

1

0

2

0

0

1

0

0

3

0

0

1

1

1

4

0

1

0

0

1

5

0

1

0

1

1

6

0

1

1

0

1

7

0

1

1

1

0

8

1

0

0

0

0

9

1

0

0

1

0

10

1

0

1

0

0

11

1

0

1

1

0

12

1

1

0

0

0

13

1

1

0

1

1

14

1

1

1

0

1

15

1

1

1

1

1

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

1.

3.

4.

5.

6.

7.

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

1

2

3

4

5

6

7

+

+

+

+

+

+

+

+

+

+

+

+

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

Проверка:

0

0

0

0

0

0

0

1

0

0

0

1

0

0

2

0

0

1

0

0

0

3

0

0

1

1

1

1

4

0

1

0

0

1

1

5

0

1

0

1

1

1

6

0

1

1

0

1

1

7

0

1

1

1

0

0

8

1

0

0

0

0

0

9

1

0

0

1

0

0

10

1

0

1

0

0

0

11

1

0

1

1

0

0

12

1

1

0

0

0

0

13

1

1

0

1

1

1

14

1

1

1

0

1

1

15

1

1

1

1

1

1

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

Ответ:

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

Решение:

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

0

0

0

0

0

0

1

0

0

0

1

0

2

0

0

1

0

1

3

0

0

1

1

0

4

0

1

0

0

0

5

0

1

0

1

0

6

0

1

1

0

1

7

0

1

1

1

1

8

1

0

0

0

0

9

1

0

0

1

0

10

1

0

1

0

1

11

1

0

1

1

0

12

1

1

0

0

1

13

1

1

0

1

1

14

1

1

1

0

1

15

1

1

1

1

1

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

2

0

0

1

0

по 1 единице

6

0

1

1

0

10

1

0

1

0

по 2 единицы

12

1

1

0

0

7

0

1

1

1

13

1

1

0

1

по 3 единицы

14

1

1

1

0

15

1

1

1

1

по 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_

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

0010

0110

0111

1010

1100

1101

1110

1111

0_10

+

+

_010

+

+

011_

+

+

_110

+

+

1_10

+

+

110_

+

+

11_0

+

+

_111

+

+

11_1

+

+

111_

+

+

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

.

Проверка:

0

0

0

0

0

0

0

1

0

0

0

1

0

0

2

0

0

1

0

1

1

3

0

0

1

1

0

0

4

0

1

0

0

0

0

5

0

1

0

1

0

0

6

0

1

1

0

1

1

7

0

1

1

1

1

1

8

1

0

0

0

0

0

9

1

0

0

1

0

0

10

1

0

1

0

1

1

11

1

0

1

1

0

0

12

1

1

0

0

1

1

13

1

1

0

1

1

1

14

1

1

1

0

1

1

15

1

1

1

1

1

1

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

Ответ:

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

Решение:

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

0

0

0

0

0

1

1

0

0

0

1

0

2

0

0

1

0

1

3

0

0

1

1

0

4

0

1

0

0

1

5

0

1

0

1

0

6

0

1

1

0

0

7

0

1

1

1

0

8

1

0

0

0

1

9

1

0

0

1

0

10

1

0

1

0

0

1

1

0

1

1

0

12

1

1

0

0

1

13

1

1

0

1

0

14

1

1

1

0

1

15

1

1

1

1

1

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

0000

0010

=

00_0

0000

0100

=

0_00

1100

1110

=

11_0

1100

1000

=

1_00

1111

1110

=

111_

Получаем:

Проверка:

0

0

0

0

0

1

1

1

0

0

0

1

0

0

2

0

0

1

0

1

1

3

0

0

1

1

0

0

4

0

1

0

0

1

1

5

0

1

0

1

0

0

6

0

1

1

0

0

0

7

0

1

1

1

0

0

8

1

0

0

0

1

1

9

1

0

0

1

0

0

10

1

0

1

0

0

0

1

1

0

1

1

0

0

12

1

1

0

0

1

1

13

1

1

0

1

0

0

14

1

1

1

0

1

1

15

1

1

1

1

1

1

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

Ответ:

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

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

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

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

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

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

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

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

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

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

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

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

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

ref.by 2006—2019
contextus@mail.ru