Де і в якому віку виготовлена судина ? 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Де і в якому віку виготовлена судина ?



За допомогою Булевої змінної введемо позначення:

- Це судина грецьках1; - Виготовлена в 5 століттіх5

- Це судина фінікійськах2; - Виготовлена в 3 століттіх3

- Це судина н е грецька; - Виготовленa в 4 століттіх4

У цих позначеннях вислови хлоп'ят кодуються логічними функціями таким чином

Альоша:

Боря:

Гриша:

Крім того, ясно, що судина може бути виготовлений тільки в одному із століть і лише в одній з країн. Ці умови дозволяють ввести додаткові логічні функції:


Форм. 6

 

Отримані таким чином логічні функції представлені в досконалій диз'юнктивній нормальній формі. Якщо надати всілякі значення наборам змінних, від яких залежать вказані функції, то можна отримати таблиці

Припустимо, що всі fi = 1, тоді отримаємо наступну систему рівнянь Булевої алгебри


Форм. 7

Система (7 представляє математичну модель шуканого завдання. Один із способів рішення (7) полягає в підборі тих одиничних термів логічних функцій набори змінних яких задовольняють системі (7), а значення змінних з цих наборів не противоречат один одному.

Для знаходження всіх одиничних термів системи (7) необхідно провести обчислення таблиць функцій f1, f2, f3, f4, f5. Це можна зробити за допомогою програми Microsoft Excel. Для цього:

1. Заповните клітинки з A1 по B4 таблиці, перебравши всі варіанти значень логічних змінних х1 і х5;

2. Побудуйте таблицю істинності для функції f1, скориставшись функціями НЕ, І, АБО, які знаходяться в майстрові функцій fx у категорії ЛОГІЧНІ.

Для цього:

• активізуйте клітинку С2;

• скористайтеся функцією НЕ (рис. 8);

• автозаповненням занесіть отримані результати в клітинки з С2 по С5 (рис. 9


Рис. 8

 


Рис. 9

 

Аналогічним чином добудуємо таблицю істинності для функції f1, використовуючи функції І, АБО. В результаті набудемо значень для х1 і х5, зображені на рис. 10.


Рис. 10

 

Будуючи таблиці для функцій f2 – f5 і, проводячи аналогічні дії із змінними, отримаємо наступні таблиці (рис. 11):


Рис. 11

 

У таблицях 1 – 5 одиничні набори визначаються тими наборами змінних, при яких логічні функції мають одиничні значення. Для вирішення поставленого завдання необхідно вибрати п'ять одиничних термів, значення змінних в яких не суперечливі.

Як такі набори змінних візьмемо наступні:


Форм. 8

З цих наборів змінних виходить, що рішення має вигляд:


Форм. 9

Несуперечність рішення (9) треба розуміти так: значення х1 = 0 має місце в наборах змінних для функцій f5, f1, f3 аналогічно х5 = 1 має місце для f1, f4 і так далі

Для перевірки рішення (9) підставимо його в систему (7) і переконаємося в тому, що після цього рівняння системи (7) перетворюються на тотожність.


Рис. 12

 

Для відтворення рішення (9) в словесній формі необхідно пригадати вислови, які кодувалися символами Хi. З прийнятого кодування виходить, що х2 = 1 означає, що судина – фінікійський, а х5 = 1судина виготовлена в 5-м столітті.

 

Завдання 2. У школі відбулася надзвичайна подія: у класі хтось з учнів розбив вікно. Вчителем були опитані чотири ученика— Льоня, Діма, Толя і Миша. Кожен з учнів зробив по три заяви (див. таблиці 1 – 4). Вчитель засумнівався в одній з трьох заяв кожного з опитаних учнів. Останнє означає, що у кожного одна з трьох заяв невірно. З аналізу всіх заяв необхідне узнать— хто розбив вікно.

Для отримання обчислюваного логічного алгоритму рішення даної задачі необхідно формалізувати її умову, тобто свідченням всіх учнів надати форму математичних співвідношень, що складаються з символів, що позначають поняття, і знаків логічних операцій, що виконуються над вказаними символами.

З цією метою припустимо, що кожне з тверджень Льоні є події , які можуть відбутися або не відбутися. Вірогідність того, що кожна з перелічених подій мала місце, позначимо відповідно Вірогідності того, що події не мали місця, позначимо через При цьому припускається, що подія протилежна події і т.д., стосовно подій, що залишилися.

Подія A полягає в тому, що з трьох свідчень Льоні одне не вірне, називається складною подією. Воно складається як комбінація простих подій таким чином:


Форм. 10

У цьому виразі операція суми подій замінена операцією диз’юнкції, а операція добутку — конъюнкцией. Вірогідність складної події А позначимо через Р(А). У теорії вірогідності значення вірогідності можуть приймати весь спектр числовых значений от нуля до единицы.

Стосовно цієї задачі будемо вважати, що вірогідність Р приймає тільки значення: нуль або одиниця. Це дозволяє ототожнювати вірогідність Р с Булевой переменной х, тобто ввести позначення:


Форм. 11

У цьому випадку х = 1 означає істинність даної події, а х = 0 — хибність. Аналогічно f1 = 1 говорить об істинності складної події A, а f1 = 0 — про ii хибність.

Тепер, згідно теоремам об вірогідність суми і твору декількох подій, вірогідність f1 складної події A визначається таким чином:


Форм. 12

 

Проводячи аналогічні міркування для свідчень решти учнів, і використовуючи позначення таблиць 2 – 4, заяви Діми, Толі і Миші представимо у формі наступних математичних співвідношень:


Форм. 13

 


Форм. 14

 


Форм. 15

 

Всі ці логічні формули однотипні і представляють досконалу диз'юнктивну нормальну форму (ДДНФ) однієї і тієї ж логічної функції f(abc).


Форм. 16

 

Додаючи набору (abc) різні комбінації з нулів і одиниць, підставляючи їх в (16) і проводячи обчислення за допомогою таблиць операцій кон'юнкції і диз'юнкції, отримуємо таблицю 10 логічній функції f.

 

У таблиці 10 через j позначений десятковий код набору змінних, що представляє безліч трьох розрядних двійкових чисел.

Одиничні значення логічної функції f називаються одиничними термами. Для них введемо нове позначення

Одиничні терми можна обчислювати за допомогою операцій кон'юнкції і заперечення по наступних формулах:


Форм. 17

 

Для отримання явного виду кон’юнктивних термів логічних функцій необхідно обчислити таблиці цих функцій за допомогою програми Microsoft Excel. Для цього:

У вікні Microsoft Excel заповните клітинки з А12 по С49 таблиці, перебравши всі варіанти значень логічних змінних хj уj, zj та sj;

Побудуйте таблицю істинності для функцій Fij, скориставшись функціями НЕ, І, АБО, які знаходяться в майстрові функцій fx у категорії ЛОГІЧНІ.

Зрештою отримуємо таблицю, показану на рис. 14.


Рис. 14

 

З таблиці, зображеної на рис. 14, формуємо таблицю 11, що складається з кон’юнктивних термів функцій і відповідних їм наборів змінних.

 

Тут стосовно функції fi кон'юнктивний терм позначений через так, що верхній індекс i відповідає номеру логічної функції.

Якщо ніхто з учнів не відмовився від своїх висловів, то значення всіх логічних функцій треба покласти рівними одиниці, після чого співвідношення (4) – (7) приймуть вид наступної системи рівнянь алгебри для визначення дванадцяти невідомих, які представляються свідченнями учнів в позначеннях таблиць 6 – 9:


Форм. 18

 

Тут для позначення кон'юнктивних термів, що входять в використаний символ

Співвідношення (18) представляють математичну модель свідчень учнів і їх слід називати системою рівнянь Булевої алгебри, оскільки вони визначені на безлічі М ={0;1} з використанням трьох логічних операцій – диз'юнкції, кон'юнкції і заперечення.

У цій системі число невідомих перевищує число рівнянь. Проте, оскільки вираз 10 = 1, те вирішення системи (10) визначатиметься такими чотирма термами: F1j, F2j, F3j, F4j, (j=3, 5, 6), набори змінних, яких після підстановки в (10) і проведення логічних обчислень перетворять рівняння (18) на тотожність. При цьому терми FIJ обчислюються за формулою (17) з урахуванням позначення змінних згідно таблиці 11.

Серед комбінацій з вказаних чотирьох термів можуть опинитися такі, значення наборів змінних яких можуть привести до суперечливих свідчень учнів. Наприклад, розглянемо терми

Набори змінних, відповідні вказаним термам, визначаються по таблиці 11. У таблиці 12 приведені значення змінних, знайдені з отриманих наборів змінних, а також свідчення учнів, відповідні даним значенням змінних.

 

Щоб показати, що значення змінних з таблиці 12 суть вирішення системи (18) необхідне для цих значень обчислити по (17) рядки і підставити їх в тотожність.

Тут же в таблиці 12 даються вислови хлопчиків, відповідні розглянутому рішенню. З них виходить, що всі учні винні. Останнє противоречит умові завдання.

Таке рішення задачі надалі називатимемо суперечливим

Розглянемо інше рішення: F13=1, F26=1, F35=1, F46=1. Значення змінних і свідчення учнів, відповідні цьому рішенню, приведені в таблиці 13.

 

Несуперечливі свідчення цієї таблиці говорять про те, що Льоня винен і він розбив вікно.

Рішення, що приводить до логічно несуперечливого результату, назвемо несуперечливим.

Виникає питання: Як з безлічі рішень вибрати одне – несуперечливе?

Повернемося до первинних заяв учнів (таблиці 6 – 9) і звернемо увагу на те, що з чотирьох заяв – x1, y1, z1, s1 одне не вірне.

По аналогії з міркуваннями, що приводять до формул (10) і (12, вказану особливість чотирьох заяв можна виразити так:


Форм. 19

 

Тепер значення змінних з таблиці 13 підставимо в праву частину формули (19) і проведемо обчислення f за допомогою програми Microsoft Excel. Для цього:

• У клітинках А52 – D52 запишіть значення змінних x1, y1, z1 і s1 з таблиці 13.

• Далі, за допомогою функцій НЕ, І, АБО знайдемо значення функції f.

• В даному випадку отримаємо: f = f max = 1.

Аналогічно обчислимо f по (19) з використанням значень змінних з таблиці 12; тоді матимемо: f = fmin = 0 (рис. 15).


Рис. 15

 

Таким чином, несуперечливе рішення приводить до максимальних значень логічної функції (19). Останнє може означати, що логічна функція (19) представляється критерієм відбору несуперечливого вирішення системи (18) з безлічі рішень. По аналогії з економічними завданнями лінійного і нелінійного програмування, логічну функцію (19) слід назвати цільовою функцією.

Тепер алгоритм рішення даної задачі (18) – (19 зводиться до наступного: перебираємо всілякі комбінації з чотирьох термів F1j, F2j, F3j, F4j, потім стосовно кожної вибраної комбінації по таблиці 11 визначаємо значення змінних, по яких обчислюємо цільову функцію (19).

Той варіант з чотирьох одиничних термів, який визначить максимальне значення цільової функції (19), слід визнати як несуперечливе рішення.

Очевидно, що такий алгоритм вимагає великого об'єму логічних обчислень. Так, наприклад, в даному завданні, число комбінацій з чотирьох термів визначатиметься числом поєднань з дванадцяти термів по чотири, тобто



Поделиться:


Последнее изменение этой страницы: 2017-02-22; просмотров: 260; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 54.160.133.33 (0.049 с.)