Минимизация ФАЛ - (реферат)
p>Если доопределять *=0 или *=1 то получим минимальный вариант: 3)Пример показывает, что доопределение функции существенно влияет на конечный результат минимизации. При доопределенииможно руководствоваться правилом: МДНФ не полностью определенных функций получается как дизъюнкция наиболее коротких по числу букв импликант функциина всех наборах и функциях, которые в совокупности покрывают все импликативные СНФ, ина всех наборах, где функция не определена.
Пример: найти минимальную форму для
Составим таблицу истинности:
0
0
0
0
1
0
0
0
1
*
0
0
1
0
*
0
0
1
1
0
0
1
0
0
*
0
1
0
1
0
0
1
1
0
1
0
1
1
1
*
1
0
0
0
*
1
0
0
1
1
1
0
1
0
0
1
0
1
1
*
1
1
0
0
0
1
1
0
1
*
1
1
1
0
1
1
1
1
1
*
1) доопрделим *=1 и получим минимальный вид функции
Доопрделим *=0
Оптимальное доопрделение функций соответствующее минимальному покрытию может быть найдено по методу Квайна.
V
V
V
V
V
V
В результате получится минимальный вид функции вида: ее таблица единичных значений тогда будет: Временные булевы функции. (1. 7)
Определение: Временная булева функция – логическая функция вида , принимающая значение единицы при , где s – дискретное целочисленное значение, называемое автоматическим временем. Утверждение: число различных временных булевых функций равно . Доказательство: если функция времени принимает n значений и на каждом интервале времени t соответствует единичных наборов, то всего получится наборов, значит число временных булевых функций равно . Любая временная булева функция может быть представлена в виде Где - конъюнктивный или дизъюнктивный терм, а равно 0 или 1 в зависимости от времени t. Форма представления временных булевых функций позволяет применить все метды минимизации.
Пример:
0
0
0
0
0
1
0
0
1
0
0
1
1
1
0
0
0
0
1
0
0
1
1
1
1
0
1
1
1
1
1
0
0
0
2
0
0
1
2
0
1
0
2
1
1
1
2
1
Временные булевы функции применяются для описания работы схем с памятью. Определение: Производной первого порядка от булевой функции по переменной называется выражение: Где первая - единичная остаточная функция, а вторая- нулевая остаточная функция. Пример:
после минимизации получим:
производная первого порядка по переменной определяет условие, при котором эта функция изменяет свое значение при перемене значенияс 0 на 1.
Для данной функции получим схему:
--
Смешанные производные k-го порядка.
Определение: смешанной производной k-го порядка называется выражение вида:
При этом порядок фиксированной переменной не имеет значения. Производная k-го порядкаопределяет условия, при которых эта функция изменяет свое значение при одновременном изменении значений.
Согласно Бохману, производная k-го порядка вычисляется по формуле: Пример: определить условия переключения выходного канала функции при переключении каждого канала, первого и второго канала, всех каналов одновременно.
1)
Понятие производной от булевых функций используется для синтеза логических схем, а также в теории надежности.
Приложение алгебры логики. (1. 8)
1) Для решения логических задач, - суть в том, что имея конкретные условия логической задачи стараются записать их в виде ФАЛ, которые затем минимизируют. Простейший вид формуды, как правило, приводят к ответу на задачу. Задача:
По подозрению в преступлению задержаны: Браун, Джон и Смит. Один – старик, другой – чиновник, третий –мошенник). Все они дали показания, причем: старик всегда говорил правду, мошенник всегда лгал, а чиновник иногда лгал, а иногда говорил правду. Показания: Браун – Я совершил это, Джон не виноват.
Джон – Браун не виноват, это сделал Смит.
Смит – я не виноват, виновен Браун.
На основании этого условия определить, кто из них совершил преступление, и кто старик, кто мошенник и кто чиновник.
Обозначим буквами: Б- виноват Браун
Д – виноват Джон
С – виноват Смит
Тогда показания запишутся в виде:
Тогда запишем функцию:
Запишем ее таблицу истинности и вычеркнем некоторые не подходящие наборы (2 преступника одновременно и. т. д. )
Б
Д
С
L
1
0
0
0
0
0
0
0
2
0
0
1
0
1
0
1
3
0
1
0
0
0
0
0
4
0
1
1
0
1
0
1
5
1
0
0
1
0
1
1
6
1
0
1
1
0
0
1
7
1
1
0
0
0
1
1
8
1
1
1
0
0
0
0
