Минимизация ФАЛ

Информация - Математика и статистика

Другие материалы по предмету Математика и статистика

ставлено ни одного терма и.т.д.

Метод Квайна-Мак-Класки может быть применим при минимизации этого базиса, при этом кроме эффективных значений функции, где включаются некоторые 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>