Построение совершенной дизъюнктивной нормальной формы
Синтез устройства, реализующего заданную таблицу истинности. Минимизация количества логических элементов. Различные представления логической функции и упрощения с помощью законов двоичной алгебры. Построение дизъюнктивной формы по таблице истинности.
| Рубрика | Математика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 12.04.2011 |
| Размер файла | 108,0 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Задание:
Выполнить синтез устройства, реализующего заданную таблицу истинности. Минимизировать количество логических элементов (число ИМС). Для этой цели использовать различные представления логической функции и упрощения с помощью законов двоичной алгебры.
Таблица истинности синтезируемого устройства:
|
a |
b |
c |
y |
|
|
0 |
0 |
0 |
1 |
|
|
0 |
0 |
1 |
0 |
|
|
0 |
1 |
0 |
1 |
|
|
0 |
1 |
1 |
1 |
|
|
1 |
0 |
0 |
0 |
|
|
1 |
0 |
1 |
0 |
|
|
1 |
1 |
0 |
0 |
|
|
1 |
1 |
1 |
1 |
Решение
1) Построение СДНФ.
Совершенная дизъюнктивная нормальная форма (СДНФ) - такая дизъюнкция конъюнкций, в которой:
1) Различны все члены конъюнкции ("множители");
2) Различны все члены каждой дизъюнкции ("слагаемые");
3) В каждой дизъюнкции нет одновременно переменной и ее отрицания;
4) Каждая дизъюнкция содержит все переменные, входящие в данную формулу или их отрицания.
Пример CДНФ: (¬XYZ)?(X¬YZ)?(¬XY¬Z)?(XY¬Z)
логический функция дизъюнктивный истинность
Построение СДНФ по таблице истинности:
1) Выбрать из таблицы истинности те строки, в которых значение формулы - "Истина" (1).
2) Для каждой выбранной строки составить конъюнкцию переменных или их отрицаний так, чтобы эта конъюнкция была истинной (для этого переменные, которые в соответствующей строке имеют значение "Ложь" (0) нужно взять с отрицанием, а переменные, имеющие значение "Истина" (1) - без отрицания).
3) Составить дизъюнкцию полученных конъюнкций.
Составим СДНФ
Минимизируем ее:
Построим полученную ДНФ:
Реализация логических функций с помощью стандартных элементов
Для ДНФ перейдем к базису И-НЕ:
Построим полученную функцию в базисе И-НЕ:
СКНФ:
1) Выбрать из таблицы истинности те строки, в которых значение формулы - "Ложь".
2) Для каждой выбранной строки составить дизъюнкцию переменных или их отрицаний так, чтобы эта дизъюнкция была ложной (для этого переменные, которые в соответствующей строке имеют значение "Истина" нужно взять с отрицанием, а переменные, имеющие значение "Ложь" - без отрицания).
3) Составить конъюнкцию полученных дизъюнкций.
1) Составим СКНФ
Упростим ее
Построим полученную функцию в КНФ:
Реализация логических функций с помощью стандартных элементов
Для КНФ перейдем к базису ИЛИ-НЕ:
Построим полученную функцию в базисе ИЛИ-НЕ
СПИСОК ЛИТЕРАТУРЫ
1) Бочаров В. А., Маркин В. И. Основы логики: Учебник. -- М.: ИНФРА-М, 2001. -- 296 с. -- ISBN 5-16-000496-3
2) Гетманова А. Д. Учебник по логике. -- М.: Владос, 1995. -- 303 с. -- ISBN 5-87065-009-7
3) Горский Д. П. Логика: Учебное пособие для педагогических училищ. -- Изд. 3-е. -- М.: Учпедгиз, 1961. -- 160 с.
4) Ивин А. А. Логика: Учебное пособие. -- Изд. 2-е. -- М.: Знание, 1998. -- (На портале «Философия в России»; на сайте Славы Янко)
5) Ивин А. А., Никифоров А. Л. Словарь по логике -- М.: Туманит, ВЛАДОС, 1997. -- 384 с -- ISBN 5-691-00099-3.
6) Ивлев Ю. В. Учебник логики: Семестровый курс: Учебник. -- М.: Дело, 2003. -- 208 с -- ISBN 5-7749-0317-6
7) Кондаков Н. И.: Логический словарь-справочник. -- М.: Наука, 1975. -- 720 с.
8) Челпанов Г. И. Учебник логики. -- М., 1994.
Размещено на Allbest.ru
Подобные документы
Построение диаграммы псевдографа, матрицы инцидентности и матрицы соседства вершин. Восстановление дерева по вектору с помощью алгоритма Прюфера. Построение таблицы истинности для функции и совершенной конъюнктивной и дизъюнктивной нормальной форм.
контрольная работа [181,9 K], добавлен 25.09.2013Определение констант нуля и установление эквивалентности линейных функций при помощи таблицы истинности. Нахождение минимальной дизъюнктивной нормальной формы функции с помощью метода неопределенных коэффициентов. Преобразование функции методом Квайна.
контрольная работа [335,2 K], добавлен 05.07.2014Представление булевой функции в виде дизъюнктивной нормальной формы. Выражение всех логических операции в формуле через конъюнкции, дизъюнкции и отрицания. Сокращение количества слагаемых, входящих в формулу и количества переменных, входящих в слагаемое.
контрольная работа [1,3 M], добавлен 06.05.2013Определение количества способов, которыми можно выбрать трех дежурных из группы в 20 человек. Построение таблицы истинности без предварительного упрощения функции по данному логическому выражению. Упрощение логических выражений с помощью карты Карно.
контрольная работа [81,1 K], добавлен 25.08.2013Синтез схемы, реализующей функцию, заданную кубическим комплексом в универсальном базисе логических элементов ИЛИ-НЕ. Нахождение минимального и построение факторизованного покрытий. Составление логической схемы и ее проверка контролирующим тестом.
курсовая работа [261,7 K], добавлен 16.06.2011Понятие алгебры логики, ее сущность и особенности, основные понятия и определения, предмет и методика изучения. Законы алгебры логики и следствия из них, методы построения формул по заданной таблице истинности. Формы представления булевых функций.
учебное пособие [702,6 K], добавлен 29.04.2009Алгоритм построения многочлена Жегалкина по совершенной дизъюнктивной нормальной форме. Диаграмма Эйлера-Венна, изображение универсального множества и подмножества. Проверка самодвойственности, монотонности и линейности логической функции двух переменных.
контрольная работа [227,5 K], добавлен 20.04.2015История возникновения булевой алгебры, разработка системы исчисления высказываний. Методы установления истинности или ложности сложных логических высказываний с помощью алгебраических методов. Дизъюнкция, конъюнкция и отрицание, таблицы истинности.
презентация [1,9 M], добавлен 22.02.2014Сущность двоичной, восьмеричной и шестнадцатиричной систем счисления, их отличительные черты и взаимосвязь. Пример алгоритмов перевода чисел из одной системы в другую. Составление таблицы истинности и логической схемы для заданных логических функций.
презентация [128,9 K], добавлен 12.01.2014Логический синтез устройства с использованием соотношений булевой алгебры. Составление таблицы истинности. Основные соотношения булевой алгебры. Логическая функция в смысловой, словесной, вербальной, табличной и аналитической математической формах.
лабораторная работа [83,6 K], добавлен 26.11.2011
