Теоретическая часть
Методы, используемые при поиске и сортировке
Оценки времени исполнения
Приложение на Delphi, в котором представлена работа некоторых методов сортировки и поиска
Пример выполнения
Вопросы для самопроверки
Представление множеств и отношений в программах
Алгоритмы генерации множеств
Then
Варианты заданий
Теоретическая часть
Примеры выполнения
Вариантв заданий
Перевод даты рождения в двоичную систему
Вопросы для самопроверки
Вопросы для самопроверки
Процедура основного обработчика
Вопросы для самопроверки
Практическая часть
Дешифраторы
Навигация
Вопросы для самопроверки
Основы дискретной математики
179431
знак
27
таблиц
82
изображения
5.3 Вопросы для самопроверки
1) Какие формы представления логических функций Вы знаете?
2) В каких случаях, на Ваш взгляд, какие формы представления логических функций являются наиболее предпочтительными?
3) Изобразите общую схему таблицы истинности функции 4‑х переменных.
4) Каков приоритет выполнения логических операций?
5) Какие логические функции есть в алгоритмическом языке Object Pascal?
6) Дайте определение логической функции многих переменных.
7) Приведите пример тождественно ложной логической функции. Можно ли для этой функции построить СДНФ?
8) Приведите пример тождественно истинной логической функции. Можно ли для этой функции построить СКНФ?
9) На основании каких замен можно построить арифметическую модель логической функции?
10) Перечислите законы алгебры логики.
11) Какие следствия из законов алгебры логики Вы знаете?
12) Назовите учёных, которые считаются основателями алгебры логики.
Практическая работа № 6. Изучение методов минимизации логических функций
Цель работы: применение изученных методов минимизации логических функций для решения конкретных задач.
6.1 Краткие теоретические сведения
Общая задача минимизации логических функций сводится к построению в базисе Буля функции, содержащей минимально возможное число двоичных переменных. Исходное выражение логической функции может быть представлено формулой в любом базисе. Поэтому на первом этапе осуществляется переход к нормальной форме формулы булевой функции, как правило, совершенной дизъюнктивной нормальной форме.
F 0={×;Ú; – ;Å;«;®;½;¯} – сигнатура алгебры логики;
F 1={×;Ú;–} – базис Буля;
F 2={×;–} – базис конъюнктивный;
F 3={Ú;–} – базис дизъюнктивный;
F 4={×;Å; 1} – базис Жегалкина;
F 5={¯} – базис Вебба;
F 6={½} – базис Шеффера;
F 7={®;–} – базис импликативный и т. д.
В таблицах 6.1–4 приведены формулы в некоторых базисах и для некоторых значений функции f (x1, x2).
Таблица 6.1 – Формулы, описывающие функции в базисах F0 и F5
| fi | Формулы в базисах F 0 и F 5 |
| f1 | (x1×x2)=(x1¯x2)¯(x1¯x2) |
| f6 | (x1Åx2)=[(x1¯x1)¯(x2¯x2)]¯(x1¯x2) |
| f7 | (x1Úx2)=(x1¯x2)¯(x1¯x2) |
| f9 | (x1«x2)=[x1¯(x2¯x2)]¯[x2¯(x1¯x1)] |
| f13 | (x1®x2)=[x2¯(x1¯x1)]¯[x2¯(x1¯x1)] |
| f14 | (x1÷x2)=[(x1¯x1)¯(x2¯x2)]¯ [(x1¯x1)¯(x2¯x2)] |
Таблица 6.2 – Формулы, описывающие функции в базисах F0 и F2
| Fi | Формулы в базисах F 0 и F2 |
| f6 | (x1Åx2)=ù(`x1×`x2)×ù(x1×x2) |
| f7 | (x1Úx2)=ù(`x1×`x2) |
| f8 | (x1¯x2)=(`x1×`x2) |
| f9 | (x1«x2)=ù(x1×`x2)×ù(`x1×x2) |
| f13 | (x1®x2)=ù(x1×`x2) |
| f14 | (x1÷x2)=ù(x1×x2) |
Таблица 6.3 – Формулы, описывающие функции в базисах F0 и F3
| Fi | Формулы в базисах F 0 и F3 |
| f6 | (x1×x2)=ù(`x1Ú`x2) |
| f7 | (x1Åx2)=ù(`x1Úx2)Úù(x1Ú`x2) |
| f8 | (x1¯x2)=ù(x1Úx2) |
| f9 | (x1«x2)=(x1Úx2)Úù(`x1Ú`x2) |
| f13 | (x1®x2)=(`x1Úx2) |
| f14 | (x1½x2)=(`x1Ú`x2) |
Таблица 6.4 – Формулы, описывающие функции в базисах F0 и F6
| Fi | Формулы в базисах F 0 и F 6 |
| f1 | (x1×x2)=(x1½x2)½(x1½x2) |
| f6 | (x1Åx2)=[x1½(x2½x2)]½[x2½ (x1½x1)] |
| f7 | (x1Úx2)=(x1½x2)½(x1½x2) |
| f8 | (x1¯x2)=[(x1½x1)½(x2½x2)½ (x2½x2)] |
| f9 | (x1«x2)=[(x1½x1)½(x2½x2)]½ (x1½x2)] |
| f13 | (x1®x2)=(x1½(x2½x2). |
6.2 Практическая часть
6.2.1 Задание к работе
1. Минимизировать функции с помощью карт Карно или таблицы Куайна.
2. Используя средства Excel и Delphi, построить таблицы истинности заданных логических функций.
3. Сделать выводы.
6.2.2 Примеры выполнения
Пример 1.
Задание:
1. Минимизировать функции с помощью таблицы Куайна.
2. Используя программные средства Delphi, построить таблицы истинности заданных логических функций.
1 Минимизация с помощью таблицы Куайна:
Пусть функция F представлена в виде СДНФ
F1СДНФ = 
Таблица 6.5 – таблица Куайна
| х1x2x3 | 001 | 101 | 110 | 111 |
| 0 0 1 1 – 1 1 1 – | 1 | 1 | 1 | 1 |
Упростим F1СДНФ, получим:
F1МДНФ =
Как мы видим, результат, полученный по таблице Куайна, совпадает с F1МДНФ.
Рисунок 6.1 – Графический интерфейс
Похожие работы
... Е и множество и мы рассматриваем все его подмножества, то множество Е называется униварсельным. Пример: Если за Е взять множество книг то его подмножества: художественные книги, книги по математике, физики, физики … Если универсальное множество состоит из n элементов, то число подмножеств = 2n. Если , состоящее из элементов E, не принадлежащих А, называется дополненным. Множество можно задать: ...
в и формальных систем является центральной в дисциплине. В настоящие время от нее возникли ответвления, например, разработка алгоритмических языков программирования.Одной из важнейших проблем в дискретной математики является проблема сложности вычислений.Теория сложности вычислений помогает оценить расход времени и памяти при решении задач на ЭВМ. Теория сложности позволяет выделить объективно ...
... которой были разработаны в последней четверти 19 века Георгом Кантором. Цель контрольной работы – ознакомится с основными понятиями и методами решения по дискретной математике, уметь применить полученные знания при решении практического задания. Задание 1 Представить с помощью кругов Эйлера множественное выражение . Используя законы и свойства алгебры множеств, упростить заданное ...
элементы теории нечетких множеств можно применять для решения экономических задач в условиях неопределённости. 1. применение Логических функций 1.1 Применение методов дискретной математики в экономике При исследовании, анализе и решении управленческих проблем, моделировании объектов исследования и анализа широко используются методы формализированного представления, являющегося предметом ...
0 комментариев