Реферат: Минимизация функций алгебры логики
--PAGE_BREAK--Шаг 2.
<img width=«62» height=«26» src=«ref-1_293317052-260.coolpic» v:shapes="_x0000_i1075">
<img width=«62» height=«25» src=«ref-1_293317312-264.coolpic» v:shapes="_x0000_i1076">
<img width=«62» height=«26» src=«ref-1_293317576-260.coolpic» v:shapes="_x0000_i1077">
<img width=«61» height=«27» src=«ref-1_293313157-259.coolpic» v:shapes="_x0000_i1078">
<img width=«62» height=«26» src=«ref-1_293318095-255.coolpic» v:shapes="_x0000_i1079">
<img width=«62» height=«26» src=«ref-1_293318350-258.coolpic» v:shapes="_x0000_i1080">
<img width=«62» height=«25» src=«ref-1_293318608-260.coolpic» v:shapes="_x0000_i1081">
<img width=«62» height=«26» src=«ref-1_293318868-256.coolpic» v:shapes="_x0000_i1082">
<img width=«2» height=«204» src=«ref-1_293319124-167.coolpic» v:shapes="_x0000_s1041"><img width=«2» height=«204» src=«ref-1_293319291-168.coolpic» v:shapes="_x0000_s1042"><img width=«2» height=«204» src=«ref-1_293319124-167.coolpic» v:shapes="_x0000_s1043"><img width=«45» height=«27» src=«ref-1_293314449-238.coolpic» v:shapes="_x0000_i1083">
V
V
<img width=«48» height=«27» src=«ref-1_293314687-243.coolpic» v:shapes="_x0000_i1084">
V
V
<img width=«47» height=«25» src=«ref-1_293315411-241.coolpic» v:shapes="_x0000_i1085">
V
V
<img width=«48» height=«25» src=«ref-1_293315892-240.coolpic» v:shapes="_x0000_i1086">
V
V
<img width=«47» height=«27» src=«ref-1_293316132-239.coolpic» v:shapes="_x0000_i1087">
V
V
<img width=«588» height=«2» src=«ref-1_293320827-170.coolpic» v:shapes="_x0000_s1040"><img width=«36» height=«27» src=«ref-1_293316610-221.coolpic» v:shapes="_x0000_i1088">
V
V
V
V
Шаг 4 пропускаем.
Шаг 5.
Выбираем те min-термы, при записи которых, МДНФ функции минимальна.
Шаг 6.
<img width=«250» height=«33» src=«ref-1_293321218-488.coolpic» v:shapes="_x0000_i1089">
Недостаток метода Квайна – необходимость полного по парного сравнения всех min-термов на этапе нахождения первичных импликант.
Идея модификации метода Квайна – метод Квайна-Мак-Класки. (1.4)
1. Каждая конъюнкция в ДСНФ представляется своим двоичным набором.
2. Вся совокупность номеров наборов разбивается на группы в зависимости от числа единиц, имеющихся в номерах наборов (0-группа, 1-группа, 2-группа и.т.д.).
3. Сравниваются две группы, отличающиеся на одну единицу.
4. В результате сравнения в номере набора, имеющего большее число единиц на позиции, где обнаружится разница на одну единицу ставится прочерк.
5. В процессе преобразования возникают новые сочетания (n-группы).
6. Процесс преобразования длится до тех пор, пока возможна операция склеивания.
7. Элементы преобразованных групп являются первичными импликантами, которые вместе с номерами исходных наборов образуют таблицы разметок.
8. В остальном эти методы совпадают с единственным уточнением – если в результате таблицы разметок ни одна из строк не покрывает единицу столбца, то надо выбрать номер столбца набора из предыдущей группы преобразований.
Определение
:n-группа – это такой набор аргументовфункции, что число всех аргументов равных единице равно n, причем значении функции равно 1.
Пример:
<img width=«291» height=«37» src=«ref-1_293321706-525.coolpic» v:shapes="_x0000_i1090">
Составим таблицу истинности:
<img width=«17» height=«23» src=«ref-1_293301879-197.coolpic» v:shapes="_x0000_i1091">
<img width=«19» height=«23» src=«ref-1_293302076-200.coolpic» v:shapes="_x0000_i1092">
<img width=«19» height=«24» src=«ref-1_293302276-196.coolpic» v:shapes="_x0000_i1093">
<img width=«19» height=«23» src=«ref-1_293322824-201.coolpic» v:shapes="_x0000_i1094">
<img width=«16» height=«21» src=«ref-1_293310232-198.coolpic» v:shapes="_x0000_i1095">
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Запишем n-группы:
0-Группа:0000
1-Группа: 0001, 0010, 0100, 1000
2-Группа:0011, 0101, 0110, 1001
3-Группа:0111,1011
4-Группа: 1111
Теперь сравним группы с номерами n и n+1:
0-Группа: 000-, 00-0, 0-00, -000
1-Группа:00-1, 0-01, -001, 001-, 0-10, 010-,01-0, 100-
2-Группа:0-11, -011, 01-1, 011-, 10-1
3-Группа: -111, 1-11
Еще раз сравним(при этом прочерки должны быть на одинаковых позициях):
0-Группа: 00--, 0-0-, -00-
1-Группа:0--1, -0-1, 0-1-, 01—
2-Группа:--11
И еще раз сравним:
0-Группа: 0---
Запишем таблицу исходных min-термов, где функция равна 1:
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1011
1111
V
V
V
V
V
V
V
V
0---
Выделим минимальное число групп, покрывающих
Для проверки составим таблицу истинности
1000
1001
1011
1111
-00-
V
V
-0-1
V
V
-111
V
V
Метод минимизирующих карт (для ДСНФ и КСНФ). (1.5)
Одним из способов графического представления булевых функций от небольшого числа переменных являются карты Карно. Их разновидность – карты Вейча, которые строятся как развертки кубов на плоскости, при этом вершины куба представляются клетками карты, координаты которых совпадают с координатами соответствующих вершин куба.
Для ДСНФ единицы ставятся в клетке, соответствующей номеру набора, на котором значение функции равно единице, а ноль не ставится, а для КСНФ – наоборот.
Диаграмма для двух логических переменных (для ДСНФ):
<img width=«81» height=«73» src=«ref-1_293323223-345.coolpic» v:shapes="_x0000_i1096">
Для трех переменных:
<img width=«204» height=«99» src=«ref-1_293323568-657.coolpic» v:shapes="_x0000_i1097">
Карты Карно используются для ручной минимизации функций алгебры логики при небольшом количестве переменных. Правило минимизации:склеиванию подвергаются 2,4,8,16,<img width=«23» height=«25» src=«ref-1_293324225-218.coolpic» v:shapes="_x0000_i1098"> клеток и клетки, лежащие на границе карты.
При числе переменных 5 и больше отобразить графически функцию в виде единой плоской карты невозможно. Тогда строят комбинированные карты, состоящие из совокупности более простых карт. Процедура минимизации заключается тогда в том, что сначала находится минимальная форма 4-х мерных кубов (карт), а затем, расширяя понятие соседних клеток, отыскивают min-термы для совокупности карт. Причем соседними клетками являются клетки, совпадающие при совмещении карт поворотом вокруг общего ребра.
<img width=«19» height=«23» src=«ref-1_293302076-200.coolpic» v:shapes="_x0000_i1099">
<img width=«21» height=«25» src=«ref-1_293324643-205.coolpic» v:shapes="_x0000_i1100">
<img width=«17» height=«23» src=«ref-1_293301879-197.coolpic» v:shapes="_x0000_i1101">
<img width=«52» height=«25» src=«ref-1_293325045-243.coolpic» v:shapes="_x0000_i1102">
<img width=«49» height=«25» src=«ref-1_293325288-238.coolpic» v:shapes="_x0000_i1103">
<img width=«19» height=«25» src=«ref-1_293325526-202.coolpic» v:shapes="_x0000_i1104">
<img width=«52» height=«25» src=«ref-1_293325728-239.coolpic» v:shapes="_x0000_i1105">
<img width=«49» height=«23» src=«ref-1_293325967-234.coolpic» v:shapes="_x0000_i1106">
Пример: Минимизировать ФАЛ от двух переменных: <img width=«131» height=«33» src=«ref-1_293326201-362.coolpic» v:shapes="_x0000_i1107">
<img width=«31» height=«59» src=«ref-1_293326563-377.coolpic» v:shapes="_x0000_s1047"><img width=«213» height=«31» src=«ref-1_293326940-499.coolpic» v:shapes="_x0000_s1046">
<img width=«17» height=«23» src=«ref-1_293301879-197.coolpic» v:shapes="_x0000_i1108">
<img width=«19» height=«25» src=«ref-1_293325526-202.coolpic» v:shapes="_x0000_i1109">
<img width=«19» height=«23» src=«ref-1_293302076-200.coolpic» v:shapes="_x0000_i1110">
1
1
<img width=«21» height=«25» src=«ref-1_293324643-205.coolpic» v:shapes="_x0000_i1111">
1
продолжение
--PAGE_BREAK--
<img width=«77» height=«23» src=«ref-1_293328243-261.coolpic» v:shapes="_x0000_i1112">
Минимизировать функцию: <img width=«179» height=«33» src=«ref-1_293328504-409.coolpic» v:shapes="_x0000_i1113">
<img width=«50» height=«69» src=«ref-1_293328913-472.coolpic» v:shapes="_x0000_s1063">
<img width=«17» height=«23» src=«ref-1_293301879-197.coolpic» v:shapes="_x0000_i1114">
<img width=«17» height=«23» src=«ref-1_293301879-197.coolpic» v:shapes="_x0000_i1115">
<img width=«19» height=«25» src=«ref-1_293325526-202.coolpic» v:shapes="_x0000_i1116">
<img width=«19» height=«25» src=«ref-1_293325526-202.coolpic» v:shapes="_x0000_i1117">
<img width=«2» height=«31» src=«ref-1_293330183-153.coolpic» v:shapes="_x0000_s1065"><img width=«2» height=«31» src=«ref-1_293330183-153.coolpic» v:shapes="_x0000_s1064"><img width=«2» height=«31» src=«ref-1_293330183-153.coolpic» v:shapes="_x0000_s1062"><img width=«165» height=«31» src=«ref-1_293330642-507.coolpic» v:shapes="_x0000_s1059"><img width=«165» height=«31» src=«ref-1_293330642-507.coolpic» v:shapes="_x0000_s1058"><img width=«19» height=«23» src=«ref-1_293302076-200.coolpic» v:shapes="_x0000_i1118">
1
1
1
<img width=«21» height=«25» src=«ref-1_293324643-205.coolpic» v:shapes="_x0000_i1119">
1
<img width=«20» height=«27» src=«ref-1_293332061-202.coolpic» v:shapes="_x0000_i1120">
<img width=«19» height=«24» src=«ref-1_293302276-196.coolpic» v:shapes="_x0000_i1121">
<img width=«19» height=«24» src=«ref-1_293302276-196.coolpic» v:shapes="_x0000_i1122">
<img width=«20» height=«27» src=«ref-1_293332061-202.coolpic» v:shapes="_x0000_i1123">
<img width=«216» height=«27» src=«ref-1_293332857-411.coolpic» v:shapes="_x0000_i1124">
Минимизация логических функций, заданных в базисе <img width=«52» height=«25» src=«ref-1_293333268-252.coolpic» v:shapes="_x0000_i1125">.
Метод неопределенных коэфициентов применим для минимизации функций, заданных в различных базисах. Пусть функция <img width=«101» height=«24» src=«ref-1_293333520-307.coolpic» v:shapes="_x0000_i1126"> является ПСНФ, операция <img width=«17» height=«19» src=«ref-1_293333827-197.coolpic» v:shapes="_x0000_i1127">имеет особенности, отличающие ее от операции дизъюнкции.
1)<img width=«120» height=«19» src=«ref-1_293334024-259.coolpic» v:shapes="_x0000_i1128">
2)<img width=«112» height=«41» src=«ref-1_293334283-312.coolpic» v:shapes="_x0000_i1129">
3) <img width=«109» height=«41» src=«ref-1_293334595-322.coolpic» v:shapes="_x0000_i1130">
Минимизация при этом усложняется, так как ее основными критериями являются минимальные ранги каждого терма и их минимальное количество, при этом в ходе минимизации в базисе <img width=«52» height=«25» src=«ref-1_293333268-252.coolpic» v:shapes="_x0000_i1131"> нецелесообразно приравнивать к нулю все коэффициенты на наборах где <img width=«40» height=«21» src=«ref-1_293307702-223.coolpic» v:shapes="_x0000_i1132">, т.к. в наборах, где функция <img width=«37» height=«21» src=«ref-1_293335392-217.coolpic» v:shapes="_x0000_i1133">могут остаться термы высокого ранга. Поэтому особой разницы между выбором нулевого или единичного значения функции нет.
Количество коэффициентов, остающихся в нулевых строках должно быть четным, а в единичных – нечетным. Лучше всего рассматривать единичные строки и оставлять те коэффициенты минимального ранга, которые чаще всего повторяются в этих строках. В общем случае для получения минимальной формы выполняют следующие действия:
1) Подсчитывают, сколько раз в единичных строках встречаются термы первого ранга и оставляют из них те, которые встречаются максимальное число раз.
2) Находят нулевые строки, в которых встречаются оставленные в первом шаге термы и их не обнуляют.
3) Рассматривая нулевую строку, в которой остался одни единичные термы и находят в ней еще единичный терм, встречающийся максимальное число раз в единичных строках, в которых еще не было оставлено ни одного терма и.т.д.
Метод Квайна-Мак-Класки может быть применим при минимизации этого базиса, при этом кроме эффективных значений функции, где <img width=«37» height=«21» src=«ref-1_293335392-217.coolpic» v:shapes="_x0000_i1134">включаются некоторые min-термы, где <img width=«40» height=«21» src=«ref-1_293307702-223.coolpic» v:shapes="_x0000_i1135">. Метод Квайна-Мак-Класки применим для минимизации базисов стрелки пирса и штриха Шеффера.
Не полностью определенные ФАЛ (1.6)
Определение
:не полностью определенные ФАЛ от n переменных называется функции, заданные на множестве наборов меньше чем <img width=«23» height=«25» src=«ref-1_293324225-218.coolpic» v:shapes="_x0000_i1136">.
Если количество неопределенных наборов равно mто путем различных доопределений можно получить <img width=«25» height=«20» src=«ref-1_293336267-222.coolpic» v:shapes="_x0000_i1137"> различных функций.
Пример: доопределить функцию <img width=«216» height=«43» src=«ref-1_293336489-465.coolpic» v:shapes="_x0000_i1138">
Где символ * означает «может быть».
Доопределим *=0
1)<img width=«313» height=«27» src=«ref-1_293336954-512.coolpic» v:shapes="_x0000_i1139">
Доопределим *=1
2) <img width=«157» height=«27» src=«ref-1_293337466-366.coolpic» v:shapes="_x0000_i1140">
Если доопределять *=0 или *=1 то получим минимальный вариант:
3)<img width=«107» height=«25» src=«ref-1_293337832-304.coolpic» v:shapes="_x0000_i1141">
Пример показывает, что доопределение функции существенно влияет на конечный результат минимизации. При доопределении <img width=«36» height=«21» src=«ref-1_293338136-226.coolpic» v:shapes="_x0000_i1142"> можно руководствоваться правилом:МДНФ не полностью определенных функций получается как дизъюнкция наиболее коротких по числу букв импликант функции <img width=«111» height=«36» src=«ref-1_293338362-317.coolpic» v:shapes="_x0000_i1143"> на всех наборах и функциях, которые в совокупности покрывают все импликативные СНФ, и <img width=«112» height=«37» src=«ref-1_293338679-327.coolpic» v:shapes="_x0000_i1144">на всех наборах, где функция не определена.
Пример: найти минимальную форму для <img width=«383» height=«41» src=«ref-1_293339006-639.coolpic» v:shapes="_x0000_i1145">
Составим таблицу истинности:
<img width=«17» height=«23» src=«ref-1_293301879-197.coolpic» v:shapes="_x0000_i1146">
<img width=«19» height=«23» src=«ref-1_293302076-200.coolpic» v:shapes="_x0000_i1147">
<img width=«19» height=«24» src=«ref-1_293302276-196.coolpic» v:shapes="_x0000_i1148">
<img width=«19» height=«23» src=«ref-1_293322824-201.coolpic» v:shapes="_x0000_i1149">
<img width=«16» height=«21» src=«ref-1_293310232-198.coolpic» v:shapes="_x0000_i1150">
1
1
*
1
*
1
1
1
*
1
1
1
1
1
1
1
1
*
1
*
1
1
1
1
1
1
1
1
*
1
1
1
1
1
*
1
1
1
1
1
1
1
1
*
1)доопрделим *=1 и получим минимальный вид функции<img width=«16» height=«21» src=«ref-1_293310232-198.coolpic» v:shapes="_x0000_i1151">
<img width=«297» height=«27» src=«ref-1_293340835-505.coolpic» v:shapes="_x0000_i1152">
Доопрделим *=0
<img width=«421» height=«27» src=«ref-1_293341340-638.coolpic» v:shapes="_x0000_i1153">
Оптимальное доопрделение функций соответствующее минимальному покрытию может быть найдено по методу Квайна.
<img width=«67» height=«27» src=«ref-1_293341978-258.coolpic» v:shapes="_x0000_i1154">
<img width=«64» height=«27» src=«ref-1_293342236-260.coolpic» v:shapes="_x0000_i1155">
<img width=«65» height=«27» src=«ref-1_293342496-259.coolpic» v:shapes="_x0000_i1156">
<img width=«64» height=«27» src=«ref-1_293342755-256.coolpic» v:shapes="_x0000_i1157">
<img width=«33» height=«25» src=«ref-1_293343011-225.coolpic» v:shapes="_x0000_i1158">
V
<img width=«33» height=«27» src=«ref-1_293343236-224.coolpic» v:shapes="_x0000_i1159">
V
V
<img width=«33» height=«24» src=«ref-1_293343460-219.coolpic» v:shapes="_x0000_i1160">
V
V
<img width=«32» height=«23» src=«ref-1_293343679-216.coolpic» v:shapes="_x0000_i1161">
V
В результате получится минимальный вид функции вида: <img width=«108» height=«27» src=«ref-1_293343895-308.coolpic» v:shapes="_x0000_i1162">ее таблица единичных значений тогда будет: <img width=«155» height=«36» src=«ref-1_293344203-377.coolpic» v:shapes="_x0000_i1163">
Временные булевы функции. (1.7)
Определение
: Временная булева функция – логическая функция вида <img width=«132» height=«24» src=«ref-1_293344580-345.coolpic» v:shapes="_x0000_i1164">,принимающая значение единицы при <img width=«77» height=«19» src=«ref-1_293344925-258.coolpic» v:shapes="_x0000_i1165">, где s– дискретное целочисленное значение, называемое автоматическим временем.
Утверждение:число различных временных булевых функций равно <img width=«41» height=«29» src=«ref-1_293345183-246.coolpic» v:shapes="_x0000_i1166">.
Доказательство: если функция времени принимает n значений <img width=«93» height=«21» src=«ref-1_293345429-255.coolpic» v:shapes="_x0000_i1167"> и на каждом интервале времени tсоответствует <img width=«23» height=«20» src=«ref-1_293345684-218.coolpic» v:shapes="_x0000_i1168">единичных наборов, то всего получится <img width=«43» height=«21» src=«ref-1_293345902-233.coolpic» v:shapes="_x0000_i1169"> наборов, значит число временных булевых функций равно <img width=«41» height=«29» src=«ref-1_293345183-246.coolpic» v:shapes="_x0000_i1170">.
Любая временная булева функция может быть представлена в виде <img width=«335» height=«29» src=«ref-1_293346381-546.coolpic» v:shapes="_x0000_i1171">
Где <img width=«20» height=«27» src=«ref-1_293346927-213.coolpic» v:shapes="_x0000_i1172"> — конъюнктивный или дизъюнктивный терм, а <img width=«17» height=«27» src=«ref-1_293347140-204.coolpic» v:shapes="_x0000_i1173"> равно 0 или 1 в зависимости от времени t. Форма представления временных булевых функций позволяет применить все метды минимизации.
Пример:
<img width=«17» height=«23» src=«ref-1_293301879-197.coolpic» v:shapes="_x0000_i1174">
<img width=«19» height=«23» src=«ref-1_293302076-200.coolpic» v:shapes="_x0000_i1175">
<img width=«11» height=«16» src=«ref-1_293347741-188.coolpic» v:shapes="_x0000_i1176">
<img width=«80» height=«27» src=«ref-1_293347929-300.coolpic» v:shapes="_x0000_i1177">
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
2
1
2
1
1
1
2
1
<img width=«128» height=«27» src=«ref-1_293348229-344.coolpic» v:shapes="_x0000_i1178"> продолжение
--PAGE_BREAK--
<img width=«169» height=«25» src=«ref-1_293348573-395.coolpic» v:shapes="_x0000_i1179">
<img width=«172» height=«25» src=«ref-1_293348968-403.coolpic» v:shapes="_x0000_i1180">
<img width=«237» height=«27» src=«ref-1_293349371-461.coolpic» v:shapes="_x0000_i1181">
Временные булевы функции применяются для описания работы схем с памятью.
Определение
: Производной первого порядка от булевой функции <img width=«16» height=«21» src=«ref-1_293310232-198.coolpic» v:shapes="_x0000_i1182"> по переменной <img width=«19» height=«27» src=«ref-1_293350030-204.coolpic» v:shapes="_x0000_i1183">называется выражение: <img width=«388» height=«48» src=«ref-1_293350234-691.coolpic» v:shapes="_x0000_i1184">
Где первая <img width=«16» height=«21» src=«ref-1_293310232-198.coolpic» v:shapes="_x0000_i1185"> — единичная остаточная функция, а вторая- нулевая остаточная функция.
Пример:
<img width=«156» height=«37» src=«ref-1_293351123-388.coolpic» v:shapes="_x0000_i1186"> после минимизации получим:
<img width=«121» height=«27» src=«ref-1_293351511-323.coolpic» v:shapes="_x0000_i1187">
<img width=«501» height=«45» src=«ref-1_293351834-769.coolpic» v:shapes="_x0000_i1188">
производная первого порядка по <img width=«19» height=«27» src=«ref-1_293350030-204.coolpic» v:shapes="_x0000_i1189"> переменной определяет условие, при котором эта функция изменяет свое значение при перемене значения <img width=«19» height=«27» src=«ref-1_293350030-204.coolpic» v:shapes="_x0000_i1190">с 0 на 1.
Для данной функции получим схему:
<img width=«31» height=«108» src=«ref-1_293353011-236.coolpic» v:shapes="_x0000_s1067"><img width=«60» height=«19» src=«ref-1_293353247-236.coolpic» v:shapes="_x0000_i1191"> <img width=«17» height=«23» src=«ref-1_293301879-197.coolpic» v:shapes="_x0000_i1192">
<img width=«29» height=«19» src=«ref-1_293353680-200.coolpic» v:shapes="_x0000_i1193"> <img width=«19» height=«23» src=«ref-1_293302076-200.coolpic» v:shapes="_x0000_i1194"> ---<img width=«41» height=«19» src=«ref-1_293354080-219.coolpic» v:shapes="_x0000_i1195">
<img width=«29» height=«19» src=«ref-1_293353680-200.coolpic» v:shapes="_x0000_i1196"> <img width=«19» height=«24» src=«ref-1_293302276-196.coolpic» v:shapes="_x0000_i1197">
Смешанные производные k-го порядка.
Определение
: смешанной производной k-го порядка называется выражение вида:
<img width=«297» height=«60» src=«ref-1_293354695-821.coolpic» v:shapes="_x0000_i1198">
При этом порядок фиксированной переменной не имеет значения. Производная k-го порядка <img width=«123» height=«56» src=«ref-1_293355516-428.coolpic» v:shapes="_x0000_i1199"> определяет условия, при которых эта функция изменяет свое значение при одновременном изменении значений <img width=«57» height=«28» src=«ref-1_293355944-258.coolpic» v:shapes="_x0000_i1200">.
Согласно Бохману, производная k-го порядка вычисляется по формуле:
<img width=«680» height=«87» src=«ref-1_293356202-1671.coolpic» v:shapes="_x0000_i1201">Пример: определить условия переключения выходного канала функции <img width=«176» height=«27» src=«ref-1_293357873-390.coolpic» v:shapes="_x0000_i1202"> при переключении каждого канала, первого и второго канала, всех каналов одновременно.
1)<img width=«195» height=«45» src=«ref-1_293358263-464.coolpic» v:shapes="_x0000_i1203">
<img width=«209» height=«45» src=«ref-1_293358727-489.coolpic» v:shapes="_x0000_i1204">
<img width=«223» height=«45» src=«ref-1_293359216-509.coolpic» v:shapes="_x0000_i1205">
<img width=«313» height=«45» src=«ref-1_293359725-712.coolpic» v:shapes="_x0000_i1206">
<img width=«316» height=«45» src=«ref-1_293360437-721.coolpic» v:shapes="_x0000_i1207">
<img width=«241» height=«45» src=«ref-1_293361158-628.coolpic» v:shapes="_x0000_i1208">
<img width=«259» height=«48» src=«ref-1_293361786-688.coolpic» v:shapes="_x0000_i1209">
<img width=«611» height=«75» src=«ref-1_293362474-1232.coolpic» v:shapes="_x0000_i1210">
Понятие производной от булевых функций используется для синтеза логических схем, а также в теории надежности.
Приложение алгебры логики. (1.8)
1) Для решения логических задач, — суть в том, что имея конкретные условия логической задачи стараются записать их в виде ФАЛ, которые затем минимизируют. Простейший вид формуды, как правило, приводят к ответу на задачу.
Задача:
По подозрению в преступлению задержаны:Браун, Джон и Смит. Один – старик, другой – чиновник, третий – мошенник). Все они дали показания, причем:старик всегда говорил правду, мошенник всегда лгал, а чиновник иногда лгал, а иногда говорил правду.
Показания: Браун – Я совершил это, Джон не виноват.
Джон – Браун не виноват, это сделал Смит.
Смит – я не виноват, виновен Браун.
На основании этого условия определить, кто из них совершил преступление, и кто старик, кто мошенник и кто чиновник.
Обозначим буквами: Б- виноват Браун
Д – виноват Джон
С – виноват Смит
Тогда показания запишутся в виде: <img width=«136» height=«25» src=«ref-1_293363706-359.coolpic» v:shapes="_x0000_i1211">
Тогда запишем функцию: <img width=«216» height=«25» src=«ref-1_293364065-431.coolpic» v:shapes="_x0000_i1212">
Запишем ее таблицу истинности и вычеркнем некоторые не подходящие наборы (2 преступника одновременно и.т.д.)
Б
Д
С
<img width=«25» height=«25» src=«ref-1_293364496-209.coolpic» v:shapes="_x0000_i1213">
<img width=«24» height=«23» src=«ref-1_293364705-213.coolpic» v:shapes="_x0000_i1214">
<img width=«24» height=«23» src=«ref-1_293364918-212.coolpic» v:shapes="_x0000_i1215">
L
1
<img width=«31» height=«22» src=«ref-1_293365130-632.coolpic» v:shapes="_x0000_s1072">2
1
1
1
3
1
<img width=«69» height=«2» src=«ref-1_293365762-156.coolpic» v:shapes="_x0000_s1068">4
1
1
1
1
<img width=«69» height=«2» src=«ref-1_293365918-157.coolpic» v:shapes="_x0000_s1069">5
1
1
1
1
<img width=«69» height=«2» src=«ref-1_293365762-156.coolpic» v:shapes="_x0000_s1070">6
1
1
1
1
<img width=«69» height=«2» src=«ref-1_293365918-157.coolpic» v:shapes="_x0000_s1071">7
1
1
1
1
8
1
1
1
Значит Браун – чиновник, Джон – старик, Смит – мошенник, он же преступник.
2) Среди технических средств автоматизации (релейно-контактные системы).
Значительное место занимают РКС, используемые в вычислительной технике. РКС – переключательные схемы. В 1910 г. физик Эрнфест указал на возможность применения алгебры логики при исследовании РКС. Его идея заключается в том, что каждой схеме можно сопоставить ФАЛ и наоборот. Это позволяет выявить возможности схемы, изучая соответствующую формулу, а упрощение схемы свести к упрощению ФАЛ – анализ переключательной схемы.
Синтез переключательной схемы (до построения схемы можно описать ее работу с помощью логической функции).
Рассмотрим связь между переключательными схемами и ФАЛ. (1.8.1)
Определение
: переключательная схема – схемотехническое изображение устройства, состоящее из следующих элементов:
1) переключатель (может быть разомкнут или замкнут)
2) проводники
3) вход в схему и выход из нее
Примеры:
<img width=«41» height=«2» src=«ref-1_293366388-156.coolpic» v:shapes="_x0000_s1075"><img width=«41» height=«2» src=«ref-1_293366388-156.coolpic» v:shapes="_x0000_s1073">а) А В
<img width=«117» height=«61» src=«ref-1_293366700-348.coolpic» v:shapes="_x0000_s1077 _x0000_s1078 _x0000_s1080 _x0000_s1082 _x0000_s1083 _x0000_s1084">
<img width=«31» height=«2» src=«ref-1_293367048-155.coolpic» v:shapes="_x0000_s1085"> <img width=«31» height=«2» src=«ref-1_293367203-155.coolpic» v:shapes="_x0000_s1079"><img width=«31» height=«2» src=«ref-1_293367048-155.coolpic» v:shapes="_x0000_s1076">б) Дизъюнкция: А В
<img width=«31» height=«2» src=«ref-1_293367048-155.coolpic» v:shapes="_x0000_s1090"><img width=«21» height=«2» src=«ref-1_293367668-155.coolpic» v:shapes="_x0000_s1089"><img width=«40» height=«2» src=«ref-1_293367823-155.coolpic» v:shapes="_x0000_s1086">в) Импликация: А В
<img width=«40» height=«2» src=«ref-1_293367823-155.coolpic» v:shapes="_x0000_s1095"><img width=«21» height=«2» src=«ref-1_293367668-155.coolpic» v:shapes="_x0000_s1094"> <img width=«40» height=«2» src=«ref-1_293368288-153.coolpic» v:shapes="_x0000_s1091">г) Тождественно ложно:А В
<img width=«98» height=«52» src=«ref-1_293368441-316.coolpic» v:shapes="_x0000_s1097 _x0000_s1098 _x0000_s1101 _x0000_s1102 _x0000_s1104">
<img width=«40» height=«2» src=«ref-1_293368757-154.coolpic» v:shapes="_x0000_s1105"> <img width=«31» height=«2» src=«ref-1_293369104-153.coolpic» v:shapes="_x0000_s1096">д) Тождественно истинно: А В
<img width=«31» height=«2» src=«ref-1_293367048-155.coolpic» v:shapes="_x0000_s1099"> <img width=«31» height=«2» src=«ref-1_293369412-154.coolpic» v:shapes="_x0000_s1103">
Из схем а, б, в можно получить функцию алгебры логики.
<img width=«261» height=«167» src=«ref-1_293369566-1114.coolpic» v:shapes="_x0000_s1107 _x0000_s1108 _x0000_s1110 _x0000_s1116 _x0000_s1118 _x0000_s1119 _x0000_s1120 _x0000_s1121 _x0000_s1122 _x0000_s1124 _x0000_s1125 _x0000_s1127 _x0000_s1128 _x0000_s1133 _x0000_s1134 _x0000_s1135">
<img width=«31» height=«2» src=«ref-1_293370680-153.coolpic» v:shapes="_x0000_s1137"><img width=«31» height=«2» src=«ref-1_293370680-153.coolpic» v:shapes="_x0000_s1106">А Б
<img width=«108» height=«37» src=«ref-1_293370986-318.coolpic» v:shapes="_x0000_s1123 _x0000_s1126 _x0000_s1129"> <img width=«30» height=«2» src=«ref-1_293371304-153.coolpic» v:shapes="_x0000_s1111"> <img width=«31» height=«2» src=«ref-1_293367048-155.coolpic» v:shapes="_x0000_s1136"> <img width=«261» height=«38» src=«ref-1_293371612-524.coolpic» v:shapes="_x0000_s1109 _x0000_s1112 _x0000_s1113 _x0000_s1114 _x0000_s1130 _x0000_s1131 _x0000_s1132">
<img width=«175» height=«25» src=«ref-1_293372136-366.coolpic» v:shapes="_x0000_i1217">
После упрощения получим:
<img width=«242» height=«98» src=«ref-1_293372502-665.coolpic» v:shapes="_x0000_s1139 _x0000_s1141 _x0000_s1142 _x0000_s1144 _x0000_s1148 _x0000_s1149 _x0000_s1150 _x0000_s1151 _x0000_s1152 _x0000_s1153 _x0000_s1154 _x0000_s1155 _x0000_s1157">
<img width=«50» height=«2» src=«ref-1_293373167-154.coolpic» v:shapes="_x0000_s1158"><img width=«59» height=«2» src=«ref-1_293373321-153.coolpic» v:shapes="_x0000_s1156"><img width=«40» height=«2» src=«ref-1_293368288-153.coolpic» v:shapes="_x0000_s1147"> <img width=«31» height=«2» src=«ref-1_293369412-154.coolpic» v:shapes="_x0000_s1140"><img width=«40» height=«2» src=«ref-1_293373781-152.coolpic» v:shapes="_x0000_s1138">А B
<img width=«121» height=«21» src=«ref-1_293373933-320.coolpic» v:shapes="_x0000_i1218"> продолжение
--PAGE_BREAK--
Синтез логической схемы. (1.8.2)
В зависимости от выходного сигнала, все электрические схемы можно разбить на две группы:
1) 1-города – содержит комбинаторные схемы (выход зависит от входа)
2) 2-го рода – накапливающие схемы (элементы памяти, выход зависит от входа в данный момент времени и в предыдущий момент времени).
По количеству входов и выходов делятся на:
1) 1+1 – 1 вход и 1 выход
2) n+1 – nвходов и 1 выход
3) 1+n–1 вход и nвыходов
4) n+m – n входов и m выходов
Любая ЭВМ состоит из комбинации схем 1-го и 2-го порядков.
Определение
:логический оператор схемы – это элементарная логическая функция, с помощью которой описывается работа схемы в целом.
Анализ схемы производят в два этапа:
1)Из вспомогательной схемы удаляются все вспомогательные элементы, не влияющие на логику работы системы.
2) Через логические операторы выражают все элементы схемы, получая логическое уравнение, являющееся моделью функции, выполняемой схемой, затем ее упрощают и переходят к схематическому изображению.
Примеры:
Простейшие логические схемы:
<img width=«117» height=«35» src=«ref-1_293374253-289.coolpic» v:shapes="_x0000_s1159 _x0000_s1160 _x0000_s1161 _x0000_s1162"> <img width=«118» height=«35» src=«ref-1_293374542-318.coolpic» v:shapes="_x0000_s1163 _x0000_s1164 _x0000_s1165 _x0000_s1166">
<img width=«40» height=«2» src=«ref-1_293373781-152.coolpic» v:shapes="_x0000_s1172"> <img width=«12» height=«11» src=«ref-1_293375012-353.coolpic» v:shapes="_x0000_s1167"><img width=«40» height=«2» src=«ref-1_293373781-152.coolpic» v:shapes="_x0000_s1170"> <img width=«17» height=«23» src=«ref-1_293301879-197.coolpic» v:shapes="_x0000_i1219">
<img width=«90» height=«62» src=«ref-1_293375714-363.coolpic» v:shapes="_x0000_s1176 _x0000_s1179 _x0000_s1181 _x0000_s1183"> <img width=«12» height=«12» src=«ref-1_293376077-309.coolpic» v:shapes="_x0000_s1168"> <img width=«2» height=«55» src=«ref-1_293376386-159.coolpic» v:shapes="_x0000_s1173">
<img width=«70» height=«2» src=«ref-1_293376545-158.coolpic» v:shapes="_x0000_s1184"><img width=«12» height=«11» src=«ref-1_293376703-384.coolpic» v:shapes="_x0000_s1169"><img width=«22» height=«2» src=«ref-1_293377087-155.coolpic» v:shapes="_x0000_s1182"><img width=«2» height=«21» src=«ref-1_293377242-151.coolpic» v:shapes="_x0000_s1180"><img width=«40» height=«2» src=«ref-1_293368757-154.coolpic» v:shapes="_x0000_s1177"> <img width=«21» height=«2» src=«ref-1_293377547-153.coolpic» v:shapes="_x0000_s1174"> <img width=«19» height=«23» src=«ref-1_293302076-200.coolpic» v:shapes="_x0000_i1220"> <img width=«15» height=«17» src=«ref-1_293377900-197.coolpic» v:shapes="_x0000_i1221">
<img width=«245» height=«25» src=«ref-1_293378097-447.coolpic» v:shapes="_x0000_i1222">
После упрощения получим:
<img width=«88» height=«2» src=«ref-1_293378544-158.coolpic» v:shapes="_x0000_s1187"><img width=«12» height=«12» src=«ref-1_293378702-377.coolpic» v:shapes="_x0000_s1185"><img width=«17» height=«23» src=«ref-1_293301879-197.coolpic» v:shapes="_x0000_i1223">
<img width=«12» height=«12» src=«ref-1_293379276-383.coolpic» v:shapes="_x0000_s1193"><img width=«21» height=«2» src=«ref-1_293379659-151.coolpic» v:shapes="_x0000_s1192"> <img width=«15» height=«17» src=«ref-1_293377900-197.coolpic» v:shapes="_x0000_i1224">
<img width=«21» height=«2» src=«ref-1_293377547-153.coolpic» v:shapes="_x0000_s1190"><img width=«40» height=«2» src=«ref-1_293368757-154.coolpic» v:shapes="_x0000_s1188"><img width=«12» height=«12» src=«ref-1_293380314-325.coolpic» v:shapes="_x0000_s1186"><img width=«19» height=«23» src=«ref-1_293302076-200.coolpic» v:shapes="_x0000_i1225">
Синтез электронных схем (1.8.3)
Задачу синтеза электронных схем можно сформулировать следующим образом:при заданных входных переменных и известной выходной функции, спроектировать логическое устройство, которое реализует эту функцию. При этом могут быть наложены дополнительные ограничения либо в виде системы логических элементов, либо по количеству логических операторов и.т.д. Обычно, решая задачи анализа и синтеза, используют полные базисы функций. При этом, любую логическую функцию, входящую в базис, сопоставляют с некоторым физическим элементом, в результате логическую схему можно заменить принципиальной схемой, состоящей из физических элементов. Таким образом удается соединить математическую задачу синтеза логической схемы с инженерной задачей проектирования электронной схемы. При разработке электронной схемы за основные критерии принимают минимум аппаратуры, минимум типов применяемых элементов и максимум надежности. С точки зрения математической логики, задачи синтеза решаются при обеспечении минимального числа логических операторов, минимального количества типов логических операторов. В общем случае при синтезе электронной схемы соблюдается следующая последовательность:
1) сопоставление математического описания, адекватно отображающего процессы, происходящие в схеме (система логических уравнений).
2) анализ логических уравнений и получение минимальной формы для каждого из них в заданном базисе.
3) переход от логических уравнений к логической схеме, посредством применения логических операторов.
Электронные схемы с одним выходом.
Это наиболее простые схемы, основная сложность при синтезе этих схем – найти выражение для выходной функции в заданном базисе.
Пример:
<img width=«211» height=«27» src=«ref-1_293380839-429.coolpic» v:shapes="_x0000_i1229">
Типы логических элементов <img width=«72» height=«25» src=«ref-1_293381268-275.coolpic» v:shapes="_x0000_i1230">
Надо привести в базис импликации <img width=«41» height=«25» src=«ref-1_293381543-231.coolpic» v:shapes="_x0000_i1231">
Т.к. <img width=«167» height=«28» src=«ref-1_293381774-365.coolpic» v:shapes="_x0000_i1232">, то <img width=«397» height=«27» src=«ref-1_293382139-614.coolpic» v:shapes="_x0000_i1233">
Тогда получим схему:
<img width=«194» height=«61» src=«ref-1_293382753-385.coolpic» v:shapes="_x0000_s1200 _x0000_s1201 _x0000_s1202 _x0000_s1208 _x0000_s1209">
<img width=«40» height=«2» src=«ref-1_293368757-154.coolpic» v:shapes="_x0000_s1197"><img width=«12» height=«11» src=«ref-1_293383676-317.coolpic» v:shapes="_x0000_s1194"><img width=«17» height=«23» src=«ref-1_293301879-197.coolpic» v:shapes="_x0000_i1234">
<img width=«11» height=«12» src=«ref-1_293384190-370.coolpic» v:shapes="_x0000_s1214"><img width=«41» height=«2» src=«ref-1_293366388-156.coolpic» v:shapes="_x0000_s1213"><img width=«31» height=«2» src=«ref-1_293369412-154.coolpic» v:shapes="_x0000_s1211"> <img width=«85» height=«24» src=«ref-1_293384870-297.coolpic» v:shapes="_x0000_i1235">
<img width=«60» height=«2» src=«ref-1_293385167-155.coolpic» v:shapes="_x0000_s1210"> <img width=«69» height=«2» src=«ref-1_293385514-155.coolpic» v:shapes="_x0000_s1205"><img width=«40» height=«2» src=«ref-1_293367823-155.coolpic» v:shapes="_x0000_s1198"><img width=«12» height=«11» src=«ref-1_293385824-375.coolpic» v:shapes="_x0000_s1195"><img width=«19» height=«23» src=«ref-1_293302076-200.coolpic» v:shapes="_x0000_i1236">
<img width=«21» height=«40» src=«ref-1_293386399-187.coolpic» v:shapes="_x0000_s1204 _x0000_s1206">
<img width=«127» height=«2» src=«ref-1_293386586-159.coolpic» v:shapes="_x0000_s1203"><img width=«12» height=«11» src=«ref-1_293386745-373.coolpic» v:shapes="_x0000_s1196"><img width=«19» height=«24» src=«ref-1_293302276-196.coolpic» v:shapes="_x0000_i1237">
Задача синтеза, как правило, имеет различные решения в зависимости от выбора системы логических элементов. Однако, для любой заданной ФАЛ почти всегда можно синтезировать схему, соответствующую этой функции. Получение схемы с минимальным количеством логических связок требует нахождения минимальной формы для ФАЛ. Некоторые, более сложные схемы, имеющие несколько выходов, могут быть сведены в частном случае к набору схем с одним выходом, тогда синтез осуществляется путем декомпозиции для каждой выделенной схемы.
Пример: синтезировать схему одноразрядного двоичного сумматора методом декомпозиции в базисе <img width=«51» height=«25» src=«ref-1_293387314-236.coolpic» v:shapes="_x0000_i1238">
Составим таблицу истинности:
<img width=«19» height=«27» src=«ref-1_293387550-206.coolpic» v:shapes="_x0000_i1239">
<img width=«17» height=«27» src=«ref-1_293387756-210.coolpic» v:shapes="_x0000_i1240">
<img width=«37» height=«28» src=«ref-1_293387966-222.coolpic» v:shapes="_x0000_i1241">
<img width=«21» height=«29» src=«ref-1_293388188-208.coolpic» v:shapes="_x0000_i1242">
<img width=«23» height=«27» src=«ref-1_293388396-209.coolpic» v:shapes="_x0000_i1243">
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Где <img width=«39» height=«27» src=«ref-1_293388605-246.coolpic» v:shapes="_x0000_i1244"> — переменные, <img width=«21» height=«27» src=«ref-1_293388851-208.coolpic» v:shapes="_x0000_i1245">— сумма в <img width=«9» height=«17» src=«ref-1_293389059-185.coolpic» v:shapes="_x0000_i1246">-ом разряде, <img width=«37» height=«28» src=«ref-1_293387966-222.coolpic» v:shapes="_x0000_i1247"> — перенос из младшего разряда в старший, <img width=«23» height=«27» src=«ref-1_293388396-209.coolpic» v:shapes="_x0000_i1248"> — перенос из старшего разряда.
Составим ДСНФ: <img width=«353» height=«32» src=«ref-1_293389675-620.coolpic» v:shapes="_x0000_i1249">
<img width=«348» height=«32» src=«ref-1_293390295-597.coolpic» v:shapes="_x0000_i1250">
<img width=«19» height=«27» src=«ref-1_293387550-206.coolpic» v:shapes="_x0000_i1254">
<img width=«19» height=«27» src=«ref-1_293391098-206.coolpic» v:shapes="_x0000_i1255">
<img width=«20» height=«29» src=«ref-1_293391304-210.coolpic» v:shapes="_x0000_i1256">
<img width=«20» height=«29» src=«ref-1_293391304-210.coolpic» v:shapes="_x0000_i1257">
<img width=«17» height=«27» src=«ref-1_293387756-210.coolpic» v:shapes="_x0000_i1258">
1
1
<img width=«20» height=«32» src=«ref-1_293391934-212.coolpic» v:shapes="_x0000_i1259">
1
1
<img width=«35» height=«31» src=«ref-1_293392146-226.coolpic» v:shapes="_x0000_i1260">
<img width=«32» height=«28» src=«ref-1_293392372-217.coolpic» v:shapes="_x0000_i1261">
<img width=«32» height=«28» src=«ref-1_293392372-217.coolpic» v:shapes="_x0000_i1262">
<img width=«35» height=«31» src=«ref-1_293392146-226.coolpic» v:shapes="_x0000_i1263">
<img width=«82» height=«79» src=«ref-1_293393032-710.coolpic» v:shapes="_x0000_s1218">
<img width=«19» height=«27» src=«ref-1_293387550-206.coolpic» v:shapes="_x0000_i1264">
<img width=«19» height=«27» src=«ref-1_293391098-206.coolpic» v:shapes="_x0000_i1265">
<img width=«20» height=«29» src=«ref-1_293391304-210.coolpic» v:shapes="_x0000_i1266">
<img width=«20» height=«29» src=«ref-1_293391304-210.coolpic» v:shapes="_x0000_i1267">
<img width=«175» height=«22» src=«ref-1_293394574-367.coolpic» v:shapes="_x0000_s1217"><img width=«174» height=«22» src=«ref-1_293394941-359.coolpic» v:shapes="_x0000_s1216"><img width=«17» height=«27» src=«ref-1_293387756-210.coolpic» v:shapes="_x0000_i1268">
1
1
1
<img width=«20» height=«32» src=«ref-1_293391934-212.coolpic» v:shapes="_x0000_i1269">
1
<img width=«35» height=«31» src=«ref-1_293392146-226.coolpic» v:shapes="_x0000_i1270">
<img width=«32» height=«28» src=«ref-1_293392372-217.coolpic» v:shapes="_x0000_i1271">
<img width=«32» height=«28» src=«ref-1_293392372-217.coolpic» v:shapes="_x0000_i1272">
<img width=«35» height=«31» src=«ref-1_293392146-226.coolpic» v:shapes="_x0000_i1273">
Тогда<img width=«289» height=«31» src=«ref-1_293396608-584.coolpic» v:shapes="_x0000_i1274">
<img width=«168» height=«28» src=«ref-1_293397192-398.coolpic» v:shapes="_x0000_i1275">
<img width=«2» height=«21» src=«ref-1_293397590-153.coolpic» v:shapes="_x0000_s1261"><img width=«281» height=«2» src=«ref-1_293397743-168.coolpic» v:shapes="_x0000_s1225"> <img width=«59» height=«2» src=«ref-1_293373321-153.coolpic» v:shapes="_x0000_s1244"> продолжение
--PAGE_BREAK--
еще рефераты
Еще работы по математике