2.2: Розрахунки Мінтермс та MATLAB
Концепції та процедури в цьому підрозділі відіграють значну роль у багатьох аспектах аналізу ймовірнісних тем та у використанні MATLAB протягом цієї роботи.
Мінтермальні вектори і MATLAB
Систематична формулювання в попередньому модулі Мінтермс показує, що кожна булева комбінація, як об'єднання мінтермів, може бути позначена вектором коефіцієнтів нуль-один. Коефіцієнт один вi -му положенні (нумерація від нуля) вказує на включення мінтермаMi в союз. Ми ретельно сформулюємо цю схему нижче і покажемо, як логічні операції MATLAB можуть бути використані при налаштуванні та вирішенні проблеми.
Припустимо,E це логічна комбінаціяA,B,C. Потім, до мінтермінного розширення,
E=⋁JEMi
деMi -i й мінтерм іJE - сукупність індексів для тих,Mi що входять вE. Наприклад, розглянемо
E=A(B∪Cc)∪Ac(B∪Cc)c=M1⋁M4⋁M6⋁M7=M(1,4,6,7)
F=AcBc∪AC=M0⋁M1⋁M5⋁M7=M(0,1,5,7)
Ми можемо позначити кожен набір зразком нулів і одиниць (e0,e1,⋅⋅⋅,e7). Ті вказують, які мінтерми присутні в наборі. У викрійці для наборуE, мінтермMi входить вE iffei=1. Це, по суті, ще одне розташування мінтермальної карти. У такому вигляді візерунок зручно розглядати як мінтерм-вектор, який може бути представлений матрицею рядків або рядковим вектором [e0,e1,⋅⋅⋅,e7]. Ми вважаємо зручним використовувати один і той же символ для назви події і для мінтермального вектора або матриці, що представляє її. Таким чином, для наведених вище прикладів,
E∼[0 1 0 0 1 1] іF∼ [1 1 0 0 0 1]
Повинно бути очевидним, що ця формалізація може бути розширена на множини, породжені будь-яким скінченним класом.
Мінтермальні вектори для логічних комбінацій
ЯкщоE іF є комбінаціямиn генеруючих установок, то кожна представлена унікальним мінтерм-вектором довжини2n. У лікуванні в модулі Мінтермс ми визначаємо мінтерм-вектор за допомогою мінтермальної карти. Ми хочемо розробити систематичний спосіб визначення цих векторів.
В якості першого кроку ми припускаємо, що у нас є мінтермальні вектори дляEF і хочемо отримати мінтермальний вектор булевих комбінацій цих.
- Мінтерм розширення дляE∪F має всі мінтерми в будь-якому наборі. Це означає,j що елемент вектора forE∪F - це максимумj th елементів для двох векторів.
- Мінтерм розширення дляE∩F має тільки ті мінтерми в обох множині. Це означає,j що елемент вектора forE∩F є мінімумом зj th елементів для двох векторів.
- Мінтермальне розширення дляEc має лише ті мінтерми, які не є розширенням дляE. Це означає, що вектор forEc має нулі та одиниці поміняні. jЕлемент дорівнюєEc одиниці, якщо відповідний елементE дорівнює нулю.
Проілюструємо для випадку двох комбінаційE і трьохF генераторних установок, розглянутих вище
E=A(B∪Cc)∪Ac(B∪Cc)c∪Ac(B∪Cc)c∼[0 1 0 0 1 1] іF=AcBc∪AC∼ [1 1 0 0 0 1]
Тоді
E∪F∼[1 1 0 0 1 1],E∩F∼ [0 1 0 0 0 0 1], іEc∼ [1 0 1 1 0 1 0]
Логічні операції MATLAB
Логічні операції MATLAB на матрицях нуль-один забезпечують зручний спосіб обробки логічних комбінацій мінтермальних векторів, представлених у вигляді матриць. Для двох матриць нуль-одинE,F і того ж розміру
- E|Fматриця, отримана шляхом взяття максимального елемента в кожному місці.
- E&Fматриця, отримана шляхом взяття мінімального елемента в кожному місці.
- Ecматриця, отримана шляхом зміни одиниці і нуля в кожному місці вE.
Таким чином, якщоE,F є мінтермальними векторами для множин з однаковою назвою, тоE|F це мінтермальний вектор forE∪F,E&F є мінтермальним вектором forE∩F, іE=1−E є мінтермальним вектором дляEc.
Це говорить про загальний підхід до визначення мінтермальних векторів для булевих комбінацій.
Почніть з мінтерм-векторів для генеруючих наборів.
Використовуйте логічні операції MATLAB для отримання вектора minterm для будь-якої логічної комбінації.
Припустимо, наприклад, клас генеруючих установок є{A,B,C}. Тоді вектори mintermA forB, іC, відповідно, є
A=[0 0 0 1 1 1]B= [0 0 1 1] [0 1 0 1]C= [0 1 0 1 0 1]
ЯкщоE=AB∪Cc, то логічнаE=(A&B) | C комбінація матриць даєE= [1 0 1 0 1 0 1 1].
Реалізація MATLAB
Ключовим кроком у щойно описаній процедурі є отримання мінтермальних векторів для генеруючих елементів{A,B,C}. У нас є m-функція для забезпечення таких фундаментальних векторів. Наприклад, щоб створити другий мінтерм-вектор для сімейства (тобто, мінтерм-вектор дляB), базовий шаблон нуль-один тиражується двічі, щоб дати
0 0 1 1 0 0 1 1
Функція minterm (n, k) генерує k -й мінтермальний вектор для класу n генеруючих множин.
мінтерми для класу {a, b, c}.
>> A = minterm(3,1) A = 0 0 0 0 1 1 1 1 >> B = minterm(3,2) B = 0 0 1 1 0 0 1 1 >> C = minterm(3,3) C = 0 1 0 1 0 1 0 1
шаблони minterm для булевих комбінацій
F=AB∪BcCG=A∪AcC
F = (A&B)|(~B&C) F = 0 1 0 0 0 1 1 1 >> G = A|(~A&C) G = 0 1 0 1 1 1 1 1 >> JF = find(F)-1 % Use of find to determine index set for F JF = 1 5 6 7 % Shows F = M(1, 5, 6, 7)
Ці основні мінтермальні патерни корисні не тільки для логічних комбінацій подій, але і для багатьох аспектів аналізу тих випадкових величин, які приймають лише кінцеву кількість значень.
Масиви нульового числа в MATLAB
Наведена вище обробка приховує той факт, що прямокутний масив нулів і одиниць може мати два абсолютно різних значення і функції в MATLAB.
Числова матриця (або вектор), підпорядкована звичайним операціям над матрицями..
Логічний масив, елементи якого об'єднані а. логічними операторами для отримання нових логічних масивів; б. операції масиву (поелементні) для отримання числових матриць; c. Масиви операцій з числовими матрицями для отримання числових результатів.
Деякі прості приклади проілюструють основні властивості.
>>> A = minterm(3,1); >> B = minterm(3,2); >> C = minterm(3,3); >> F = (A&B)|(~B&C) F = 0 1 0 0 0 1 1 1 >> G = A|(~A&C) G = 0 1 0 1 1 1 1 1 >> islogical(A) % Test for logical array ans = 0 >> islogical(F) ans = 1 >> m = max(A,B) % A matrix operation m = 0 0 1 1 1 1 1 1 >> islogical(m) ans = 0 >> m1 = A|B % A logical operation m1 = 0 0 1 1 1 1 1 1 >> islogical(m1) ans = 1 >> a = logical(A) % Converts 0-1 matrix into logical array a = 0 0 0 0 1 1 1 1 >> b = logical(B) >> m2 = a|b m2 = 0 0 1 1 1 1 1 1 >> p = dot(A,B) % Equivalently, p = A*B' p = 2 >> p1 = total(A.*b) p1 = 2 >> p3 = total(A.*B) p3 = 2 >> p4 = a*b' % Cannot use matrix operations on logical arrays ??? Error using ==> mtimes % MATLAB error signal Logical inputs must be scalar.
Часто бажано мати таблицю генеруючих мінтермальних векторів. Використання функції minterm у простому «циклі for» дає наступну m-функцію.
Функція mintable (n) генерує таблицю мінтермальних векторів дляn генеруючих множин.
mintable для трьох змінних
>> M3 = mintable(3) M3 = 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1
Як застосування mintable розглянемо проблему визначенняk ймовірностіn подій. Якщо{Ai:1≤i≤n} є якимось кінцевим класом подій, то подія, що самеk ці події відбуваються на суді, можна охарактеризувати просто з точки зору мінтермального розширення. ПодіяAkn, яка точноk відбувається, дається
Akn=the disjoint union of those minterms with exactly k positions uncomplemented
У матриці це мінтерми, відповідні стовпцям з точноk одиницями. Подія BkNbKn, якаk або більше відбувається, задається
Bkn=⋁nr=kArn
Якщо у нас є мінтермальні ймовірності, легко вибрати відповідні мінтерми та поєднати ймовірності. Наступний приклад у випадку трьох змінних ілюструє процедуру.
опитування програмного забезпечення (продовження)
У проблемі обстеження програмного забезпечення мінімальні ймовірності є
pm=[0 0.05 0.10 0.05 0.20 0.10 0.10]
деA= подія має текстовий процесор,B= подія має розкид аркуша,C= подія має програму бази даних. Бажано, щоб отримати ймовірність, яку має окремий обранийk з них,k=0,1,2,3.
Рішення
Формуємо mintable для трьох змінних. Кількість «успіхів», що відповідає кожному мінтерму, підраховуємо за допомогою функції MATLAB sum, яка дає суму кожного стовпця. У цьому випадку було б легко визначити кожне окреме значення та додати ймовірності на мінтермах, які дають це значення. Для більш складних випадків ми маємо m-функцію під назвою csort (для сортування та консолідації) для виконання цієї операції.
>> pm = 0.01*[0 5 10 5 20 10 40 10]; >> M = mintable(3) M = 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 >> T = sum(M) % Column sums give number T = 0 1 1 2 1 2 2 3 % of successes on each >> [k,pk] = csort(T,pm); % minterm, determines % distinct values in T and >> disp([k;pk]') % consolidates probabilities 0 0 1.0000 0.3500 2.0000 0.5500 3.0000 0.1000
Для трьох змінних досить легко визначити різні комбінації «на око» і скласти комбінації. Однак для більшої кількості змінних це може стати нудним. Підхід набагато корисніший у випадку з Незалежними подіями, через простоту визначення мінтермальних ймовірностей.
Процедури Мінвеца
Використання тильди∼ для позначення доповнення події часто незручно. Прийнято вказувати доповнення того чи іншого заходуE поEc. У MATLAB ми не можемо вказати верхній індекс, тому вказуємо доповненняEc замість∼E. Для полегшення написання комбінацій у нас є сімейство процедур minvec (minvec3, minvec4,..., minvec10) для прискорення вираження логічних комбінаційn=3,4,5,⋅⋅⋅,10 множин. Вони генерують та називають вектор minterm для кожного генеруючого набору та його доповнення.
булеві комбінації з використанням minvec3
Ми хочемо створити матрицю, рядки якої є векторами minterm дляΩ=A∪Ac,A,AB,ABC,C, іAcCc, відповідно.
>> minvec3 % Call for the setup procedure Variables are A, B, C, Ac, Bc, Cc They may be renamed, if desired >> V = [A|Ac; A; A&B; A&B&C; C; Ac&Cc]; % Logical combinations (one per % row) yield logical vectors >> disp(V) 1 1 1 1 1 1 1 1 % Mixed logical and 0 0 0 0 1 1 1 1 % numerical vectors 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0 0 0 0 0
Мінтермальні ймовірності та логічне поєднання
Якщо у нас є ймовірність кожного мінтерма, згенерованого скінченним класом, ми можемо визначити ймовірність будь-якої булевої комбінації членів класу. Коли ми знаємо мінтермальне розширення або, еквівалентно, мінтермальний вектор, ми просто вибираємо ймовірності, що відповідають мінтермам в розширенні, і додаємо їх. У наступному прикладі ми робимо це «вручну», а потім покажемо, як це зробити за допомогою MATLAB.
РозглянемоE=A(B∪Cc)∪Ac(B∪Cc)c іF=AcBc∪AC приклад вище, і припустимо, що відповідні мінтермальні ймовірності є
p0=0.21,p1=0.06,p2=0.29,p3=0.11,p4=0.09,p5=0.03,p6=0.14,p7=0.07
Використання minterm карти показуєE=M(1,4,6,7) іF=M(0,1,5,7). так що
P(E)=p1+p4+p6+p7=p(1,4,6,7)=0.36іP(F)=p(0,1,5,7)=0.37
З цим легко впоратися в MATLAB.
- Використовуйте minvec3 для встановлення генеруючих мінтерм-векторів.
- Використовувати логічні матричні операції
E=(A&(B|Cc))|(Ac&((B|Cc))) таF=(Ac&Bc)|(A&C)
отримати (логічні) мінтерм-вектори дляE таF - Якщоpm матриця мінтермальних ймовірностей, виконайте алгебраїчний точковий добуток або скалярний добуток матриці pmpm та мінтерм-вектора для комбінації. Це може бути викликано командами MATLAB PE = E*pm 'і PF = F*pm'.
Нижче наведено стенограму операцій MATLAB.
>> minvec3 % Call for the setup procedure Variables are A, B, C, Ac, Bc, Cc They may be renamed, if desired. >> E = (A&(B|Cc))|(Ac&~(B|Cc)); >> F = (Ac&Bc)|(A&C); >> pm = 0.01*[21 6 29 11 9 3 14 7]; >> PE = E*pm' % Picks out and adds the minterm probabilities PE = 0.3600 >> PF = F*pm' PF = 0.3700
вирішення проблеми обстеження програмного забезпечення
Встановлено матричні рівняння з використанням MATLAB та розв'язуємо для мінтермальних ймовірностей. З них ми можемо вирішити бажані «цільові» ймовірності.
>> minvec3 Variables are A, B, C, Ac, Bc, Cc They may be renamed, if desired. Data vector combinations are: >> DV = [A|Ac; A; B; C; A&B&C; Ac&Bc; (A&B)|(A&C)|(B&C); (A&Bc&C) - 2*(Ac&B&C)] DV = 1 1 1 1 1 1 1 1 % Data mixed numerical 0 0 0 0 1 1 1 1 % and logical vectors 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 -2 0 1 0 0 >> DP = [1 0.8 0.65 0.3 0.1 0.05 0.65 0]; % Corresponding data probabilities >> pm = DV\DP' % Solution for minterm probabilities pm = -0.0000 % Roundoff -3.5 x 10-17 0.0500 0.1000 0.0500 0.2000 0.1000 0.4000 0.1000 >> TV = [(A&B&Cc)|(A&Bc&C)|(Ac&B&C); Ac&Bc&C] % Target combinations TV = 0 0 0 1 0 1 1 0 % Target vectors 0 1 0 0 0 0 0 0 >> PV = TV*pm % Solution for target probabilities PV = 0.5500 % Target probabilities 0.0500
альтернативний підхід
Попередня процедура спочатку отримала всі мінтермальні ймовірності, потім використовувала їх для визначення ймовірностей для цільових комбінацій. Наступна процедура не вимагає обчислення мінімальних ймовірностей. Іноді даних недостатньо для обчислення всіх мінімальних ймовірностей, але є достатніми для визначення цільових ймовірностей.
Припустимо, що мінтерм-вектори даних лінійно незалежні, а цільові мінтерм-вектори лінійно залежать від векторів даних (тобто цільові вектори можуть бути виражені у вигляді лінійних комбінацій векторів даних). Тепер кожна цільова ймовірність - це однакова лінійна комбінація ймовірностей даних. Для визначення лінійних комбінацій вирішуємо матричне рівняння
TV=CT∗DV which has the MATLAB solution CT=TV/DV
Тоді матрицяtp цільових ймовірностей задається за допомогоюtp=CT∗DP′. Продовжуючи наведені вище процедури MATLAB, ми маємо:
>> CT = TV/DV;
>> tp = CT*DP'
tp = 0.5500 0.0500
Процедура мінкальц
Процедура mincalc виконує розрахунки, як і в попередніх прикладах. Уточнення полягають у визначенні узгодженості та обчислюваності різних індивідуальних мінтермальних ймовірностей та цільових потенцій. Перевірка послідовності в основному для негативних мінтермальних ймовірностей. Випробування обчислюваності - це тести на лінійну незалежність шляхом обчислення рангів різних матриць. Процедура вибирає обчислювані мінтермальні ймовірності та обчислювані цільові ймовірності та обчислює їх.
Щоб використовувати процедуру, проблема повинна бути сформульована належним чином і точно таким чином:
Використовуйте програму MATLAB minvecq, щоб встановити мінтермальні вектори для кожної з q базових подій.
Дані складаються з булевих комбінацій основних подій та відповідних ймовірностей цих комбінацій. Вони організовані в дві матриці:
- Матриця векторів данихDV має дані Boolean combinations— по одному на кожному рядку. MATLAB переводить кожен рядок у мінтермальний вектор для відповідної логічної комбінації. Перший запис (у першому рядку) - A | Ac (forA⋁Ac), який є цілим пробілом. Його мінтермальний вектор складається з ряду одиниць.
- Матриця ймовірностей данихDP являє собою рядкову матрицю ймовірностей даних. Перший запис один, ймовірність всього простору.
Мета полягає у визначенні ймовірності різних цільових булевих комбінацій. Вони поміщаються в матрицю цільового вектораTV, по одному на кожному рядку. MATLAB створює мінтерм-вектор для кожної відповідної цільової логічної комбінації.
Обчислювальна записка. У mincalc необхідно перетворити масиви DV і TV, що складаються з шаблонів нуль-один, в матриці нуль-один. Це досягається для DV операцією. і аналогічно для телевізора. Як оригінальна, так і перетворена матриці мають однаковий візерунок нуль-один, але MATLAB інтерпретує їх по-різному.
Звичайний випадок
Припустимо, що вектори мінтерму даних лінійно незалежні, а цільові вектори лінійно залежать від мінтермальних векторів даних. Тоді кожен цільовий мінтерм-вектор можна виразити у вигляді лінійної комбінації даних мінтерм-векторів. Таким чином, існує матрицяCT така, щоTV=CT∗DV. MATLAB вирішує цеCT=TV/DV командою Цілеві ймовірності - це ті ж лінійні комбінації ймовірностей даних. Вони отримані за допомогою операції MATLABtp=DP∗CT′.
Застережні нотатки
Програма mincalc залежить від положення в MATLAB для розв'язання рівнянь, коли доступні менше повних даних (на основі декомпозиції сингулярних значень). Є кілька ситуацій, які слід розглядати як особливі випадки. Зазвичай рекомендується перевірити результати вручну, щоб визначити, чи відповідають вони даними. Перевірка вручну, як правило, набагато простіше, ніж отримання рішення без сторонньої допомоги, так що використання MATLAB є вигідним навіть у сумнівних випадках.
Нульова проблема. Якщо загальна ймовірність групи мінтермів дорівнює нулю, то з цього випливає, що ймовірність кожного мінтерма в групі дорівнює нулю. Однак якщо mincalc не має достатньої кількості інформації для обчислення окремих мінтермальних ймовірностей у випадку, якщо вони не дорівнюють нулю, він не підхопить в нульовому випадку той факт, що окремі мінтермальні ймовірності дорівнюють нулю. Він просто вважає ці мінтермальні ймовірності не обчислюваними.
Лінійна залежність. У разі лінійної залежності операція, викликана командою CT = TV/DV, може бути не в змозі вирішити рівняння. Матриця може бути одниною, або вона може бути не в змозі вирішити, яке з надлишкових рівнянь даних використовувати. Якщо це дасть рішення, результат слід перевірити за допомогою мінтермальної карти.
Перевірка консистенції. Оскільки перевірка узгодженості проводиться для негативних мінтермінів, якщо немає достатньої кількості даних для обчислення мінтермальних ймовірностей, простий перевірки на консистенцію немає. Іноді ймовірність цільового вектора, включеного в інший вектор, насправді перевищить те, що має бути більшою ймовірністю. Без значної перевірки може бути важко визначити консистенцію.
У кількох незвичних випадках команда CT = TV/DV не працює належним чином, навіть якщо дані повинні бути адекватними для проблеми під рукою. Мабуть процес наближення не сходиться.
MATLAB Рішення для прикладів з використанням mincalc
програмне забезпечення опитування
% file mcalc01 Data for software survey minvec3; DV = [A|Ac; A; B; C; A&B&C; Ac&Bc; (A&B)|(A&C)|(B&C); (A&Bc&C) - 2*(Ac&B&C)]; DP = [1 0.8 0.65 0.3 0.1 0.05 0.65 0]; TV = [(A&B&Cc)|(A&Bc&C)|(Ac&B&C); Ac&Bc&C]; disp('Call for mincalc') >> mcalc01 % Call for data Call for mincalc % Prompt supplied in the data file >> mincalc Data vectors are linearly independent Computable target probabilities 1.0000 0.5500 2.0000 0.0500 The number of minterms is 8 The number of available minterms is 8 Available minterm probabilities are in vector pma To view available minterm probabilities, call for PMA >> disp(PMA) % Optional call for minterm probabilities 0 0 1.0000 0.0500 2.0000 0.1000 3.0000 0.0500 4.0000 0.2000 5.0000 0.1000 6.0000 0.4000 7.0000 0.1000
комп'ютерне опитування
% file mcalc02.m Data for computer survey minvec3 DV = [A|Ac; A; B; C; A&B&C; A&C; (A&B)|(A&C)|(B&C); ... 2*(B&C) - (A&C)]; DP = 0.001*[1000 565 515 151 51 124 212 0]; TV = [A|B|C; Ac&Bc&C]; disp('Call for mincalc') >> mcalc02 Call for mincalc >> mincalc Data vectors are linearly independent Computable target probabilities 1.0000 0.9680 2.0000 0.0160 The number of minterms is 8 The number of available minterms is 8 Available minterm probabilities are in vector pma To view available minterm probabilities, call for PMA >> disp(PMA) 0 0.0320 1.0000 0.0160 2.0000 0.3760 3.0000 0.0110 4.0000 0.3640 5.0000 0.0730 6.0000 0.0770 7.0000 0.0510
% file mcalc03.m Data for opinion survey minvec4 DV = [A|Ac; A; B; C; D; A&(B|Cc)&Dc; A|((B&C)|Dc) ; Ac&B&Cc&D; ... A&B&C&D; A&Bc&C; Ac&Bc&Cc&D; Ac&B&C; Ac&Bc&Dc; A&Cc; A&C&Dc; A&B&Cc&Dc]; DP = 0.001*[1000 200 500 300 700 55 520 200 15 30 195 120 120 ... 140 25 20]; TV = [Ac&((B&Cc)|(Bc&C)); A|(B&Cc)]; disp('Call for mincalc') >> mincalc03 Call for mincalc >> mincalc Data vectors are linearly independent Computable target probabilities 1.0000 0.4000 2.0000 0.4800 The number of minterms is 16 The number of available minterms is 16 Available minterm probabilities are in vector pma To view available minterm probabilities, call for PMA >> disp(minmap(pma)) % Display arranged as on minterm map 0.0850 0.0800 0.0200 0.0200 0.1950 0.2000 0.0500 0.0500 0.0350 0.0350 0.0100 0.0150 0.0850 0.0850 0.0200 0.0150
Процедура мінкалкт
Корисна модифікація, яку ми називаємо mincalct, обчислює наявні цільові ймовірності, не перевіряючи та обчислюючи мінімальні ймовірності. Ця процедура передбачає файл даних, подібний до файлу даних для mincalc, за винятком того, що він не потребує цільової матриціTV, оскільки він запитує введення цільової логічної комбінації. Процедура mincalct може бути використана після того, як mincalc виконав свої операції для обчислення ймовірностей для додаткових цільових комбінацій.
(продовження) Додаткова цільова дата для опитування думки
Припустимо, mincalc був застосований до даних для опитування думок і що його бажано визначитиP(AD∪BDc). Не варто перераховувати всі інші величини. Ми можемо просто використовувати процедуру mincalct і ввести потрібну булеву комбінацію в підказці.
>> mincalct Enter matrix of target Boolean combinations (A&D)|(B&Dc) Computable target probabilities 1.0000 0.2850
Повторні виклики maclct можуть бути використані для обчислення інших цільових ймовірностей.