Минимизация ФАЛ
Информация - Математика и статистика
Другие материалы по предмету Математика и статистика
ставлено ни одного терма и.т.д.
Метод Квайна-Мак-Класки может быть применим при минимизации этого базиса, при этом кроме эффективных значений функции, где включаются некоторые min-термы, где . Метод Квайна-Мак-Класки применим для минимизации базисов стрелки пирса и штриха Шеффера.
Не полностью определенные ФАЛ (1.6)
Определение: не полностью определенные ФАЛ от n переменных называется функции, заданные на множестве наборов меньше чем .
Если количество неопределенных наборов равно m то путем различных доопределений можно получить различных функций.
Пример: доопределить функцию
Где символ * означает "может быть".
Доопределим *=0
1)
Доопределим *=1
2)
Если доопределять *=0 или *=1 то получим минимальный вариант:
3)
Пример показывает, что доопределение функции существенно влияет на конечный результат минимизации. При доопределении можно руководствоваться правилом: МДНФ не полностью определенных функций получается как дизъюнкция наиболее коротких по числу букв импликант функции на всех наборах и функциях, которые в совокупности покрывают все импликативные СНФ, и на всех наборах, где функция не определена.
Пример: найти минимальную форму для
Составим таблицу истинности:
000010001*0010*001100100*01010011010111*1000*10011101001011*110001101*111011111*
1) доопрделим *=1 и получим минимальный вид функции
Доопрделим *=0
Оптимальное доопрделение функций соответствующее минимальному покрытию может быть найдено по методу Квайна.
VVVVVV
В результате получится минимальный вид функции вида: ее таблица единичных значений тогда будет:
Временные булевы функции.(1.7)
Определение: Временная булева функция логическая функция вида , принимающая значение единицы при , где s дискретное целочисленное значение, называемое автоматическим временем.
Утверждение: число различных временных булевых функций равно .
Доказательство: если функция времени принимает n значений и на каждом интервале времени t соответствует единичных наборов, то всего получится наборов, значит число временных булевых функций равно .
Любая временная булева функция может быть представлена в виде
Где - конъюнктивный или дизъюнктивный терм, а равно 0 или 1 в зависимости от времени t. Форма представления временных булевых функций позволяет применить все метды минимизации.
Пример:
000001001001110000100111101111100020012010211121
Временные булевы функции применяются для описания работы схем с памятью.
Определение: Производной первого порядка от булевой функции по переменной называется выражение:
Где первая - единичная остаточная функция, а вторая- нулевая остаточная функция.
Пример:
после минимизации получим:
производная первого порядка по переменной определяет условие, при котором эта функция изменяет свое значение при перемене значения с 0 на 1.
Для данной функции получим схему:
---
Смешанные производные k-го порядка.
Определение: смешанной производной k-го порядка называется выражение вида:
При этом порядок фиксированной переменной не имеет значения. Производная k-го порядка определяет условия, при которых эта функция изменяет свое значение при одновременном изменении значений .
Согласно Бохману, производная k-го порядка вычисляется по формуле:
Пример: определить условия переключения выходного канала функции при переключении каждого канала, первого и второго канала, всех каналов одновременно.
1)
Понятие производной от булевых функций используется для синтеза логических схем, а также в теории надежности.
Приложение алгебры логики. (1.8)
1) Для решения логических задач, - суть в том, что имея конкретные условия логической задачи стараются записать их в виде ФАЛ, которые затем минимизируют. Простейший вид формуды, как правило, приводят к ответу на задачу.
Задача:
По подозрению в преступлению задержаны: Браун, Джон и Смит. Один старик, другой чиновник, третий мошенник). Все они дали показания, причем: старик всегда говорил правду, мошенник всегда лгал, а чиновник иногда лгал, а иногда говорил правду.
Показания: Браун Я совершил это, Джон не виноват.
Джон Браун не виноват, это сделал Смит.
Смит я не виноват, виновен Браун.
На основании этого условия определить, кто из них совершил преступление, и кто старик, кто мошенник и кто чиновник.
Обозначим буквами: Б- виноват Браун
Д виноват Джон
С виноват Смит
Тогда показания запишутся в виде:
Тогда запишем функцию:
Запишем ее таблицу истинности и вычеркнем некоторые не подходящие наборы (2 преступника одновременно и.т.д.)
БДСL1000000020010101301000004011010151001011610110017110001181110000
Значит Браун чиновник, Джон старик, Смит мошенник, он же преступник.
2) Среди технических средств автоматизации (релейно-контактные системы).
Значительное место занимают РКС, используемые в вычислительной технике. РКС переключательные схемы. В 1910 г. физик Эрнфест указал на возможность применения алгебры логики при исследовании РКС. Его идея заключается в том, что каждой схеме можно сопоставить ФАЛ и наоборот. Это позволяет выявить возможности схемы, изучая соответствующую формулу, а упрощение схемы свести к упрощению ФАЛ анализ переключательной схемы.
Синтез переключательной схемы (до построения схемы можно описать ее работу с помощью логической ?/p>