Главная База знаний "Allbest" Математика Эквиваленты функций

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

Определение констант нуля и установление эквивалентности линейных функций при помощи таблицы истинности. Нахождение минимальной дизъюнктивной нормальной формы функции с помощью метода неопределенных коэффициентов. Преобразование функции методом Квайна.

Рубрика Математика
Вид контрольная работа
Язык русский
Дата добавления 05.07.2014
Размер файла 335,2 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

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.

Размещено на Allbest.ru


Подобные документы

  • Методы минимизации логических функций

    Определение МДНФ логической функции устройства различными методами (Квайна, Петрика, неопределенных коэффициентов и др.). Составление алгоритма метода минимизации функции и разработка его рабочих программ. Выполнение синтеза схемы логического устройства.

    курсовая работа [60,2 K], добавлен 21.11.2010

  • Функционально полные системы булевых функций

    Полнота и замкнутость системы булевых функций. Алгоритм построения таблицы истинности двойственной функции. Класс L линейных функций, сущность полинома Жегалкина. Распознавание монотонной функции по вектору ее значений. Доказательство теоремы Поста.

    учебное пособие [1,3 M], добавлен 20.08.2014

  • Нахождение пределов функций

    Нахождение производных функций, построение графика функции с помощью методов дифференциального исчисления, нахождение точки пересечения с осями координат. Исследование функции на возрастание и убывание, нахождение интегралов, установка их расходимости.

    контрольная работа [130,5 K], добавлен 09.04.2010

  • Код Прюфера

    Построение диаграммы псевдографа, матрицы инцидентности и матрицы соседства вершин. Восстановление дерева по вектору с помощью алгоритма Прюфера. Построение таблицы истинности для функции и совершенной конъюнктивной и дизъюнктивной нормальной форм.

    контрольная работа [181,9 K], добавлен 25.09.2013

  • Полином Жегалкина

    Изучение булевых функций. Алгоритм представления булевых функций в виде полинома Жегалкина. Система функций множества. Алгебраические преобразования, метод неопределенных коэффициентов. Таблица истинности для определенного количества переменных.

    курсовая работа [701,9 K], добавлен 27.04.2011

  • Преобразование графиков функции

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

    презентация [2,4 M], добавлен 16.11.2010

  • Взаимно обратные функции

    Понятие и основные свойства обратной функции. Нахождение функции, обратной данной. Область определения функции. Обратимость монотонной функции. Построение графиков функций и определение их свойств. Симметричность графиков функций относительно прямой у=х.

    презентация [98,6 K], добавлен 18.01.2015

  • Ряд Фурье

    Условия разложения функций для тригонометрического ряда. Определение коэффициентов разложения с помощью ортогональности систем тригонометрических функций. Понятие периодического продолжения функции, заданной на отрезке. Ряд Фурье функции у=f(x).

    презентация [30,4 K], добавлен 18.09.2013

  • Модели и методы принятия решений

    Нахождение экстремумов функций методом множителей Лагранжа. Выражение расширенной целевой функции. Схема алгоритма численного решения задачи методом штрафных функций в сочетании с методом безусловной минимизации. Построение линий ограничений.

    курсовая работа [259,9 K], добавлен 04.05.2011

  • Тригонометрическая и показательная форма комплексного числа

    Нахождение производных заданной функции. Частные производные первого и второго порядка. Вычисление неопределенных интегралов. Решение задачи комбинаторики. Расчет коэффициентов прямых материальных затрат с помощью межотраслевого балансового метода.

    контрольная работа [359,1 K], добавлен 15.04.2013

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.

© 2000 — 2023, ООО «Олбест» Все права защищены