Довести один із законів де моргану. Нечіткі і випадкові множини

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

Для довільних множин А, В і С справедливі наступні тотожності (табл. 3.1):

Таблиця 3.1

Закони алгебри множин стосовно операцій перетину () та об'єднання () підпорядковані принципу двоїстості: якщо в будь-якому законі всі знаки перетину замінити знаками об'єднання, а всі знаки об'єднання – знаками перетину, знак універсуму (U) замінити знаком порожнього множини (Ø), а знак порожнього – знаком універсуму, то отримаємо знову вірну тотожність. Наприклад (з цього принципу), слід і т. п.

3.1. Перевірка істинності тотожності за допомогою діаграм Ейлера-Венна

Усі закони алгебри множин можна наочно уявити та довести, використовуючи діаграми Ейлера-Венна. Для цього необхідно:

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

Накреслити іншу діаграму і зробити те саме для правої частини рівності.

Ця тотожність істинна тоді і тільки тоді, коли на обох діаграмах заштрихована та сама область.

Зауваження 3.1.Два кола, що перетинаються, ділять все універсальне безліч на чотири області (див. рис.3.1)

Зауваження 3.2.Три кола, що перетинаються, ділять все універсальне безліч на вісім областей (див. рис.3.2):

Зауваження 3.2.При записі умов різних прикладів часто використовуються позначення:

 - з … слідує…;

 - тоді і лише тоді, коли… .

Завдання 3.1 . Спростити вирази алгебри множин:

Рішення.

Завдання 3 .2 . Довести тотожність:

(АВ)\В = А\В;

А(ВС) = А\(А\В)(А\С).

Рішення.

Завдання 3.3 . Довести наступні співвідношення двома способами: за допомогою діаграм та за допомогою визначення рівності множин.

Рішення.

2. Доказ за допомогою визначення рівності множин.

За визначенням, множини Х і Y рівні, якщо одночасно виконані співвідношення: XY та YX.

Спочатку покажемо, що
. Нехай х- довільний елемент множини
, тобто х
. Це означає, що хU та х
. Звідси випливає, що хА або хВ. Якщо хА, то тоді хĀ, а значить,
. Якщо ж хВ, то
, а значить,
. Таким чином, будь-який елемент множини.
. є також елементом множини
Тобто

Тепер доведемо протилежне, тобто, що
. Нехай
. Якщо хĀ, то хU та хА, отже, хАВ. Звідси слідує що
. Якщо ж
, то хU та хВ. Значить, хАВ, тобто
. Звідси випливає, що кожен елемент множини
є також елементом множини
, тобто
.

Значить,
, що й потрібно було довести.

A(BC) = (AB)(AC);

1. Доказ за допомогою діаграми:

Нехай хА(ВС). Тоді хА та хВС. Якщо хВ, то хАВ, що не суперечить сказаному, а отже, х(АВ)(АС). Якщо ж хС, то хАС. Отже, х(AB)(AC). Отже, доведено, що A(BC) (AB)(AC.

Нехай тепер х (AB)(AC). Якщо хАВ, то хА та хВ. Звідси слідує що хА та хВС, тобто хА(ВС). Якщо ж хАС, то хА та хС. Звідси випливає, що хА та хВС, тобто хА(ВС). Таким чином, (AB)(AC) A(BC). Отже, A(BC) = (AB)(AC). Що й потрібно було довести.

За доказом достатності ми отримали, що АВ=. Очевидно, що С тому співвідношення доведено. За доказом було розглянуто найзагальніший випадок. Однак тут можливі деякі варіанти при побудові діаграм. Наприклад, випадок рівності АВ=С або
, випадок порожніх множини і так далі. Вочевидь, що це можливі варіанти враховувати буває важко. Тому вважається, що доказ співвідношень за допомогою діаграм не завжди коректний.

2. Доказ за допомогою визначення рівності множин.

Необхідність. Нехай АВС та елемент хА. Покажемо, що в цьому випадку елемент множини А буде також елементом множини
.

Розглянемо два випадки: хВ або
.

Якщо хВ, то хАВС, тобто хС, і, як наслідок цього,
.

Якщо ж
, то й
. Необхідність доведена.

Нехай тепер
і хАВ. Покажемо, що елемент хтакож буде елементом множини С.

Якщо хАВ, тоді хА та хВ. Оскільки
, значить хС. Достатність доведено.

1. Доказ за допомогою діаграми:

2. Доказ за допомогою визначення рівності множин.

Нехай АВ. Розглянемо елемент хВ (або
). Аналогічно: хА (або хĀ). Тобто всякий елемент множини є також елементом множини Ā. А це може бути у випадку, якщо
. Що й потрібно було довести.

Завдання 3.4. Виразити символічно вказані області та спростити отримані вирази.

Рішення.

Шукана область складається з двох ізольованих частин. Умовно назвемо їх верхньою та нижньою. Безліч, яку вони зображають, можна описати так:

М = ( x xA та хВ та хС або хС та хА та хВ).

З визначення операцій над множинами отримаємо:

М = ((АВ)\С)(С\А\В).

Запишемо цей вислів за допомогою основних операцій – доповнення, об'єднання та перетину:

Спростити це вирази не можна, оскільки маємо по одному входження кожного символу. Це і найпростіший вид цієї формули.

Дану область можна розглядати як об'єднання множин А\В\С та АВС. За визначенням M = ( x xA та xВ та хС або хА та хВ та хС). Спростимо:

Завдання для самостійного вирішення.

1. Спростити:

2. Довести за допомогою діаграм, законів алгебри множин та визначення рівності множин:

(АВ)\В = А\В;

А(ВС) = А\(А\В)(А\С);

АВ = АВ  А=В;

А\В =   АВ = А.

3. З'ясувати, чи існує безліч Х, яка задовольняє за будь-якої А рівності:

АХ = А; (відповідь );

Теорема поглинаннязаписується у двох формах - диз'юнктивної та

кон'юнктивної, відповідно:

А + АВ = А (16)

А(А+В)=А (17)

Доведемо першу теорему. Винесемо за дужки букву А:

А + АВ = А (1 + В)

Відповідно до теореми (3) 1 + В = 1, отже

А(1 + В) = А1 = А

Щоб довести другу теорему, розкриємо дужки:

А(А + В) = А А + АВ = А + АВ

Вийшов вираз, щойно доведений.

Розглянемо кілька прикладів застосування теореми поглинання при

спрощення булевих формул.

Теорема склеюваннятакож має дві форми - диз'юнктивну та

кон'юнктивну:

Доведемо першу теорему:

оскільки згідно з теоремами (5) і (4)



Для доказу другої теореми розкриємо дужки:



Відповідно до теореми (6) отже:

По теоремі поглинання (16) А+АВ = А

Теорема поглинання, як і теорема склеювання, застосовується при спрощенні

булевих формул, наприклад:



Теорема де Морганапов'язує всі три основні операції булевої алгебри

Диз'юнкцію, кон'юнкцію та інверсію:

Перша теорема читається так: інверсія кон'юнкції є диз'юнкцією

інверсії. Друга: інверсія диз'юнкції є кон'юнкцією інверсій. Довести теореми Моргана можна за допомогою таблиць істинності для лівої та правої частин.

Теорема де Моргана застосовна і до більшої кількості змінних:

Лекція 5

Інвертування складних виразів

Теорема де Моргана застосовна не лише до окремих кон'юнкцій

або диз'юнкцій, але й до складніших виразів.

Знайдемо інверсію виразу АВ + CD , представленого у вигляді диз'юнкції кон'юнкцій. Інвертування вважатимемо закінченим, якщо знаки заперечення стоять лише над змінними. Введемо позначення: АВ = Х;

CD = Y,тоді

Знайдемо і підставимо у вираз (22):



Таким чином:

Розглянемо вираз, поданий у кон'юнктивній формі:

(А + В) (З + D)

Знайдемо його інверсію у вигляді



Введемо позначення: А + В = X; З + D = Y,тоді

Знайдемо і підставимо їх у вираз

Таким чином:

При інвертуванні складних виразів можна скористатися наступним правилом. Щоб знайти інверсію, необхідно знаки кон'юнкції замінити знаками диз'юнкції, а знаки диз'юнкції – знаками кон'юнкції та поставити інверсії над кожною змінною:

Поняття булевої функції

Узагальному випадку функція (лат. functio - виконання, відповідність,

відображення) - це деяке правило (закон), згідно з яким кожному елементу множини X, являє собою область значень незалежного змінного х, ставиться у відповідність певний елемент множини F,

під яким розуміється область значень залежного змінного f . У разі булевих функцій X = F = (0,1). Правилом, за допомогою якого задається функція, може бути будь-яка булева формула, наприклад:



Символом f тут позначено функцію, яка є, як і аргументи А, В, С,двійковою змінною.

Аргументи - це незалежні змінні, вони можуть набувати будь-яких значень - або 0, або 1. Функція ж f - Залежна змінна. Її значення повністю визначається значеннями змінних та логічними зв'язками між ними.

Головна особливість функції: щоб визначити її значення, у випадку необхідно знати значення всіх аргументів, яких вона залежить. Наприклад, наведена вище функція залежить від трьох аргументів А, У, З.Якщо прийняти А = 1, то отримаємо



тобто вийшло нове вираження, не рівне ні нулю, ні

одиниці. Нехай тепер У= 1. Тоді



т. е. й у разі невідомо, чому дорівнює функція, нулю чи одиниці.

Приймемо, нарешті, З= 0. Тоді отримаємо: f = 0. Таким чином, якщо у вихідному виразі прийняти А = 1, У= 1, З = 0, то функція набуде нульового значення: f = 0.

Розглянемо поняття набору значень змінних .

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

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

Наприклад, якщо

то згідно з латинським алфавітом першим є аргумент Р, другим -

Q,третім - X, четвертим – У. Тоді за набором значень аргументів легко

Визначити значення функції. Нехай, наприклад, дано набір 1001. Відповідно до нього

записи тобто на наборі 1001 задана функція дорівнює одиниці.

Ще раз зазначимо, що набір значень аргументів – це сукупність

нулів та одиниць. Двійкові числа також є наборами нулів та одиниць.

Звідси виникає питання - чи не можна набори розглядати як двійкові.

числа? Можна, і в багатьох випадках це дуже зручно, особливо якщо двійкове

число перевести до десяткової системи. Наприклад, якщо

А = 0, В = 1, С = 1, D = 0,

0 * 2 3 +1 * 2 2 +1 * 2 1 +0 * 2 0 = 4+2 = 6

тобто заданий набір має номер 6 у десятковій системі.

Якщо за десятковим номером потрібно знайти значення аргументів, то

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

Нехай, наприклад, потрібно знайти значення аргументів А, В, С, D, Е, Fза набором з номером 23. Перекладаємо число 23 у двійкову систему методом

поділу на два:

В результаті одержуємо 23 10 = 10 111 2 . Це число п'ятизначне, а всього

аргументів шість, отже, зліва необхідно записати один нуль:

23 10 = 010 111 2 . Звідси знаходимо:

А=0, В=1, С=0, D=1, Е=1, F=1.

Скільки всього існує наборів, якщо відоме число п аргументів? Очевидно, стільки ж, скільки існує n-розрядних двійкових чисел, тобто 2 n

Лекція 6

Завдання булевої функції

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

На прикладі функції



з'ясуємо, як побудувати нею таблицю відповідності.

Функція залежить від трьох аргументів А, У, З. Отже, у таблиці

передбачаємо три колонки для аргументів A, B, C та одну колонку для значень функції f. Ліворуч від колонки А корисно розмістити ще одну колонку. У ній записуватимемо десяткові числа, які відповідають наборам, якщо їх розглядати як трирозрядні двійкові номери. Ця десяткова

колонка вводиться для зручності роботи з таблицею, тому, в принципі,

нею можна знехтувати.



Заповнюємо таблицю. У рядку з номером ТОВ записано:

А = В = С = 0.

Визначимо значення функції на цьому наборі:

У колонці f записуємо нуль у рядку з набором 000.

Наступний набір: 001; е. А = В = 0, С = 1. Знаходимо значення функції

на цьому наборі:

На наборі 001 функція дорівнює 1, отже, у колонці f у рядку з

номером 001 записуємо одиницю.

Аналогічно обчислюємо значення функцій на всіх інших наборах і

заповнюємо всю таблицю.

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

Надалі вважається, що всі нечіткі множини, що розглядаються, є підмножинами однієї і тієї ж множини Y.

П2-1. Закони де Моргана для нечітких множин

Як відомо, законами ж Моргана називаються наступні тотожності алгебри множин

Теорема 1.Для нечітких множин справедливі тотожності

(3)

Доказ теореми 1 полягає у безпосередній перевірці справедливості співвідношень (2) і (3) шляхом обчислення значень функцій належності нечітких множин, що беруть участь у цих співвідношеннях, на основі визначень, даних у розділі 8.

Тотожності (2) і (3) назвемо законами де Моргана для нечітких множин. На відміну від класичного випадку співвідношень (1), вони складаються з чотирьох тотожностей, одна пара яких відноситься до операцій об'єднання та перетину, а друга - до операцій твору та суми. Як і співвідношення (1) в алгебрі множин, закони де Моргана в алгебрі нечітких множин дозволяють перетворювати вирази та формули, до складу яких входять операції заперечення.

П2-2. Дистрибутивний закон для нечітких множин

Деякі властивості операцій над множинами не виконані для нечітких множин. Так, за винятком випадку, коли А- "чітка" множина (тобто функція приналежності приймає тільки значення 0 і 1).

Чи вірний дистрибутивний закон для нечітких множин? У літературі іноді розпливчасто стверджується, що "не завжди". Внесемо повну ясність.

Теорема 2.Для будь-яких нечітких множин А, В і С

У той же час рівність

справедливо тоді і тільки тоді, коли за всіх

Доведення. Фіксуємо довільний елемент. Для скорочення запису позначимо Для доказу тотожності (4) необхідно показати, що

Розглянемо різні впорядкування трьох чисел a, b, c.Нехай спочатку тоді ліва частина співвідношення (6) є правою тобто. рівність (6) справедлива.

Нехай тоді у співвідношенні (6) зліва стоїть праворуч тобто. співвідношення (6) знову є рівністю.

Якщо то у співвідношенні (6) зліва стоїть праворуч тобто. обидві частини знову збігаються.

Три інші впорядкування чисел a, b, cрозбирати немає необхідності, оскільки у співвідношення (6) числа bі cвходять симетрично. Тотожність (4) доведено.

Друге твердження теореми 2 випливає з того, що відповідно до визначення операцій над нечіткими множинами (див. розділ 8)

Ці два вирази збігаються тоді й тільки тоді, коли, коли щось потрібно було довести.

Визначення 1.Носієм нечіткої множини А називається сукупність усіх точок , для яких

Наслідок теореми 2.Якщо носії нечітких множин і З збігаються з У, то рівність (5) має місце тоді й тільки тоді, коли А - "чітка" (тобто звичайна, класична, не нечітка) безліч.

Доведення.За умовою при всіх . Тоді з теореми 2 випливає, що тобто. або , що означає, що А- Чітка безліч.

П2-3. Нечіткі множини як проекції випадкових множин

З початку появи сучасної теорії нечіткості в 1960-і роки почалося обговорення її взаємин з теорією ймовірностей. Справа в тому, що функція приналежності нечіткої множини нагадує розподіл ймовірностей. Відмінність лише тому, що сума ймовірностей за всіма можливими значеннями випадкової величини (або інтеграл, якщо безліч можливих значень незліченна) завжди дорівнює 1, а сума Sзначень функції власності (у безперервному випадку - інтеграл від функції власності) може бути будь-яким невід'ємним числом. Виникає спокуса пронормувати функцію власності, тобто. розділити всі її значення на S(при S 0), щоб звести її до розподілу ймовірностей (або щільності ймовірності). Однак фахівці з нечіткості справедливо заперечують проти такого "примітивного" відомості", оскільки воно проводиться окремо для кожної розмитості (нечіткої множини), і визначення звичайних операцій над нечіткими множинами з ним узгодити не можна. Останнє твердження означає наступне. Нехай зазначеним чином перетворені функції належності нечітких множин Аі У. Як у своїй перетворюються функції власності ? Встановити це неможливо у принципі.Останнє твердження стає цілком зрозумілим після розгляду декількох прикладів пар нечітких множин з одними і тими ж сумами значень функцій належності, але різними результатами теоретико-множинних операцій над ними, причому і суми значень відповідних функцій приналежності для цих результатів теоретико-множинних операцій, наприклад, перетинів множин, також різні.

У роботах з нечітких множин досить часто стверджується, що теорія нечіткості є самостійним розділом прикладної математики і не має відношення до теорії ймовірностей (див., Наприклад, огляд літератури в монографіях). Автори, які порівнювали теорію нечіткості та теорію ймовірностей, зазвичай підкреслювали різницю між цими областями теоретичних та прикладних досліджень. Зазвичай порівнюють аксіоматику та порівнюють області додатків. Треба відразу відзначити, що аргументи при другому типі порівнянь не мають доказової сили, оскільки з приводу меж застосування навіть такої наукової галузі, що давно виділилася, як імовірнісно-статистичні методи, є різні думки. Нагадаємо, що підсумок міркувань одного з найбільш відомих французьких математиків Анрі Лебега з приводу меж застосування арифметики такий: "Арифметика застосовна тоді, коли вона застосовна" (див. його монографію).

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

Можна зрозуміти бажання ентузіастів нового напряму наголосити на принциповій новизні свого наукового апарату. Проте важливо встановити зв'язку нового підходу з раніше відомими.

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

Визначення 2.Нехай - випадкове підмножина кінцевої множини У. Нечітка множина, визначена на У, називається проекцією А і позначається Proj A, якщо

(7)

при всіх

Очевидно, кожній випадковій множині Аможна поставити у відповідність за допомогою формули (7) нечітка множина У = Proj A.Виявляється, вірне і протилежне.

Теорема 3. Для будь-якої нечіткої підмножини У кінцевої множини існує випадкова підмножина А множини У така, що В = Proj A.

Доведення.Достатньо задати розподіл випадкової множини А. Нехай У 1- носій У(Див. визначення 1 вище). Без обмеження спільності вважатимуться, що при деякому mта елементи У 1занумеровані в такому порядку, що

Введемо безліч

Для всіх інших підмножин Хбезлічі Упокладемо Р(А=Х)=0. Оскільки елемент y tвходить до множини Y(1), Y(2),…, Y(t)і не входить у безлічі Y(t+1),…, Y(m),то з наведених вище формул випливає, що Якщо те, очевидно, Теорема 3 доведено.

Розподіл випадкової множини з незалежними елементами, як випливає з розгляду глави 8, повністю визначається його проекцією. Для кінцевої випадкової множини загального вигляду це не так. Для уточнення сказаного знадобиться така теорема.

Теорема 4. Для випадкової підмножини А множини У з кінцевої числа елементів набори чисел і виражаються один через інший.

Доведення.Другий набір виражається через перший наступним чином:



Елементи першого набору виразити через другий можна за допомогою формули включень та виключень із формальної логіки, відповідно до якої

У цій формулі у першій сумі упробігає всі елементи множини Y\X,у другій сумі змінні підсумовування у 1і у 2не збігаються і також пробігають це безліч, тощо. Посилання на формулу включень та виключень завершує доказ теореми 4.

Відповідно до теореми 4 випадкове безліч А можна характеризувати не тільки розподілом, а й набором чисел У цьому наборі інших зв'язків типу рівностей немає. У цей набір входять числа, отже, фіксація проекції випадкової множини еквівалентна фіксації k = Card(Y)параметрів з (2 k -1)параметрів, що задають розподіл випадкової множини Ау загальному випадку.

Буде корисна така теорема.

Теорема 5. Якщо Proj A = B, то

Для доказу достатньо скористатися тотожністю з теорії випадкових множин формулою для ймовірності накриття з глави 8, визначенням заперечення нечіткої множини і тим, що сума всіх P(A=X) дорівнює 1.

П2-4. Перетину та твори нечітких і випадкових множин

З'ясуємо, як операції над випадковими множинами співвідносяться з операціями їх проекціями. З огляду на законів де Моргана (теорема 1) і теореми 5 досить розглянути операцію перетину випадкових множин.

Теорема 6. Якщо випадкові підмножини А 1 і А 2 кінцевої множиниУ незалежні, то нечітка безліч є твором нечітких множин Proj A 1 та Proj A 2 .

Доведення.Треба показати, що для будь-кого

За формулою для ймовірності накриття точки випадковою множиною (глава 8)

Як відомо, розподіл перетину випадкових множин можна виразити через їх спільний розподіл таким чином:

Зі співвідношень (9) і (10) випливає, що ймовірність накриття для перетину випадкових множин можна представити у вигляді подвійної суми

Зауважимо тепер, що праву частину формули (11) можна переписати так:

(12)

Дійсно, формула (11) відрізняється від формули (12) лише тим, що в ній згруповані члени, в яких перетин змінних підсумовування набуває постійного значення. Скориставшись визначенням незалежності випадкових множин і правилом перемноження сум, отримуємо, що з (11) та (12) випливає рівність

Для завершення доказу теореми 6 достатньо ще раз послатися на формулу для ймовірності накриття точки випадковим множиною (глава 8).

Визначення 3. Носієм випадкової множини З називається сукупність всіх тих елементів для яких

Теорема 7.Рівність

вірно тоді і тільки тоді, коли перетин носіїв випадкових множин і порожньо.

Доведення.Необхідно з'ясувати умови, за яких

Тоді рівність (13) зводиться до умови

Зрозуміло, що співвідношення (14) виконано тоді і лише тоді, коли р 2 р 3=0 за всіх тобто. не існує жодного елемента такого, що одночасно і , а це еквівалентно порожнечі перетину носіїв випадкових множин і . Теорему 7 доведено.

П2-5. Зведення послідовності операцій над нечіткими множинами

до послідовності операцій над випадковими множинами

Вище отримані деякі зв'язки між нечіткими та випадковими множинами. Варто зазначити, що вивчення цих зв'язків у роботі (ця робота виконана в 1974 р. та доповідана на семінарі "Багатомірний статистичний аналіз та ймовірнісне моделювання реальних процесів" 18 грудня 1974 р. - див.) почалося з введення випадкових множин з метою розвитку та узагальнення апарату нечітких множин Л. Заде. Справа в тому, що математичний апарат нечітких множин не дозволяє належним чином враховувати різні варіанти залежності між поняттями (об'єктами), що моделюються з його допомогою, не є досить гнучким. Так, для опису "загальної частини" двох нечітких множин є лише дві операції - твір та перетин. Якщо застосовується перша з них, то фактично передбачається, що множини поводяться як проекції незалежних випадкових множин (див. вище теорему 6). Операція перетину також накладає певні обмеження на вигляд залежності між множинами (див. вище теорему 7), причому в цьому випадку знайдені навіть необхідні і достатні умови. Бажано мати ширші можливості для моделювання залежності між множинами (поняттями, об'єктами). Використання математичного апарату випадкових множин надає такі можливості.

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

Визначення 4.Імовірнісний простір { W, G, P)назвемо ділимим, якщо для будь-якої вимірної множини Х G і будь-якої позитивної кількості, меншого Р(Х), можна вказати вимірну множину таку, що

приклад.Нехай - одиничний куб кінцевого лінійного простору, Gє сигма-алгебра борелівських множин, а P- Міра Лебега. Тоді { W, G, P)- поділений імовірнісний простір.

Таким чином, поділений імовірнісний простір - це не екзотика. Звичайний куб є прикладом такого простору.

Доказ сформульованого в прикладі твердження проводиться стандартними математичними прийомами, заснованими на тому, що вимірна множина можна як завгодно точно наблизити відкритими множинами, останні представляються у вигляді суми не більше ніж лічильного числа відкритих куль, а для куль поділення перевіряється безпосередньо (від кулі Х тіло об'єму відокремлюється відповідною площиною).

Теорема 8.Нехай дано випадкове безліч А на поділеному імовірнісному просторі (W, G, P) зі значеннями у множині всіх підмножин множини У з кінцевого числа елементів, і нечітка множина D на У. Тоді існують випадкові множини, З 2, З 3, З 4 на тому ж ймовірнісному просторі такі, що

де B = Proj A.

Доведення.Через справедливість законів де Моргана для нечітких (див. теорему 1 вище) і для випадкових множин, а також теореми 5 вище (про заперечення) достатньо довести існування випадкових множин З 1і З 2 .

Розглянемо розподіл ймовірностей у безлічі всіх підмножин множини У, що відповідає випадковій множині Зтакому, що Proj C = D(Він існує в силу теореми 3). Побудуємо випадкове безліч З 2 Виключимо елемент тільки для тієї ж множини У такі, що

і, крім того, результати теоретико-множинних операцій пов'язані аналогічними співвідношеннями

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

Закони де Моргана – це логічні правила, встановлені шотландським математиком Огастесом де Морганом, які пов'язують пари логічних операцій з допомогою логічного заперечення.

Огастес де Морган зауважив, що у класичній логіці справедливі такі співвідношення:

not (A and B) = (not A) or (not B)

not (А or B) = (not A) and (not B)

У більш звичній для нас формі дані співвідношення можна записати в такому вигляді:



Закони де Моргана можна сформулювати так:

I закон де Моргана:Заперечення диз'юнкції двох простих висловлювань рівносильне кон'юнкції заперечень цих висловлювань.

II закон де Моргана:Заперечення кон'юнкції двох простих висловлювань рівносильне диз'юнкції заперечень цих висловлювань.

Розглянемо застосування законів де Моргана на конкретних прикладах.

приклад 1.Перетворити формулу те щоб не було заперечень складних висловлювань.

Скористаємося першим законом де Моргана, отримаємо:

до заперечення кон'юнкції простих висловлювань В і С застосуємо другий закон де Моргана, отримаємо:

,

таким чином:

.

У результаті отримали рівносильне висловлювання, у якому немає заперечень складових висловлювань, проте заперечення ставляться лише до простих висловлювань.

Перевірити справедливість рішення можна з допомогою таблиць істинності. Для цього складемо таблиці істинності для вихідного висловлювання:

і для висловлювання, отриманого внаслідок перетворень, виконаних за допомогою законів де Моргана:

.

Таблиця 1.

			В/\С	А/В/\С



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

Асоціативність

х 1 (х 2 х 3) = (х 1 х 2) х 3;

x 1 Ú (x 2 Ú x 3) = (x 1 Ú x 2) Ú x 3 .

Комутативність

х 1 х 2 = х 2 х 1

х 1 Ú х 2 = х 2 Ú х 1

Дистрибутивність кон'юнкції щодо диз'юнкції

x 1 (x 2 Ú x 3) = x 1 x 2 Ú x 1 x 3 .

Дистрибутивність диз'юнкції щодо кон'юнкції

х 1 Ú(х 2 × х 3) = (х 1 Úх 2) × (х 1 Úх 3). *

Ідемопотентність (тавтологія)

Подвійне заперечення

Властивості констант

x & 1 = x; (Закони універсальної множини)

x & 0 = 0; (Закони нульової множини)

Правила (закони) де Моргана





Закон протиріччя (додатковості)

Закон виключення третього (додатковості)

Докази всіх цих формул є тривіальними. Один із варіантів – побудова таблиць істинності лівої та правої частин та їх порівняння.

Правила склеювання

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

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

Правило поглинання

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

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

Правило розгортання

Це правило визначає дію зворотне склеювання.

Правило розгортання елементарного твору на логічну суму елементарних творів більшого рангу (у межі до r = n, тобто до конституента одиниці, як і буде розглянуто нижче) випливає із законів універсальної множини, розподільчого закону першого роду і виробляється в три етапи:

У елементарне твір рангу, що розгортається, r вводиться в якості співмножників n-r одиниць, де n- ранг конституенти одиниці;

Кожна одиниця замінюється логічною сумою деякою, що не є у вихідному елементарному творі змінної та її заперечення: x i v `x i = 1;

Проводиться розкриття всіх дужок на основі розподільчого закону першого роду, що призводить до розгортання вихідного елементарного добутку рангу r у логічну суму 2 n-r конституент одиниці.

Правило розгортання елементарного твору використовується для мінімізації функцій логіки алгебри (ФАЛ).

Правило розгортання елементарної суми рангу r до виконання елементарних сум рангу n (конституент нуля) дотримується їх законів нульової множини (6) та розподільчого закону другого роду (14) і проводиться у три етапи:

У суму рангу, що розгортається, r як доданок вводиться n-r нулів;

Кожен нуль представляється у вигляді логічного твору деякої, що не є у вихідній сумі змінної та її заперечення: x i·` x i = 0;

Вираз, що вийшов, перетворюється на основі розподільчого закону другого роду (14) таким чином, щоб вихідна сума рангу r розгорнулася в логічний добуток 2 n-r конституент нуля.

16. Поняття повної системи. Приклади повних систем (з підтвердженням)

Визначення.Безліч функцій алгебри логіки A називається повною системою (P2), якщо будь-яку функцію алгебри логіки можна виразити формулою над A.

Система функцій A = ( f 1 , f 1 ,..., f m), що є повною, називається базисом.

Мінімальним базисом називається такий базис, для якого видалення хоча б однієї функції f 1, що утворює цей базис, перетворює систему функцій (f 1, f 1, ..., f m)у неповну.

Теорема.Система A = (∨, &,) є повною.

Доведення. Якщо функція алгебри логіки f відмінна від тотожного нуля, то f виражається у вигляді досконалої диз'юнктивної нормальної форми, до якої входять лише диз'юнкція, кон'юнкція та заперечення. Якщо ж f ≡ 0, то f = x & x. Теорему доведено.

Лемма.Якщо система A – повна, і будь-яка функція системи A може бути виражена формулою над деякою іншою системою B, то B – також повна система.

Доведення. Розглянемо довільну функцію алгебри логіки f (x 1, …, x n) та дві системи функцій: A = (g 1, g 2, …) та B = (h 1, h 2, …). З огляду на те, що система A повна, функція f може бути виражена у вигляді формули над нею:

f (x 1 , …, x n) = ℑ

де g i = ℜ i

тобто функція f представляється у вигляді

f (x 1 , …, x n)=ℑ[ℜ1,ℜ2,...]

інакше кажучи, може бути представлена ​​формулою над B. Перебираючи таким чином всі функції логіки алгебри, отримаємо, що система B також повна. Лемма доведена.

Теорема.Наступні системи є повними P 2:

4) (&, ⊕, 1) база Жегалкіна.

Доведення.

1) Відомо (теорема 3), що система A = (&, V,) повна. Покажемо, що повна система B = (V, . Дійсно, із закону де Моргана (x& y) = (x ∨ y) отримуємо, що x & y = (x ∨ y) , тобто кон'юнкція виражається через диз'юнкцію та заперечення, і всі функції системи A виражаються формулами над системою B. Відповідно до леми система B повна.

2) Аналогічно пункту 1: (x ∨ y) = x & y ⇔ x ∨ y = (x & y) і з леми 2 випливає істинність затвердження пункту 2.

3) х | y=(x&y), x | x = x; x & y = (x | y) = (x | y) | (x | y) та згідно лемі 2 система повна.

4) x = x ⊕1 і згідно з лемою 2 система повна.

Теорему доведено.

17. Алгебра Жегалкіна. Властивості операцій та повнота

Безліч булевих функцій, заданих у базисі Жегалкіна S4=(⊕,&,1) називається алгеброю Жегалкіна.

Основні характеристики.

1. комутативність

h1⊕h2=h2⊕h1 h1&h2=h2&h1

2. асоціативність

h1⊕(h2⊕h3)=(h1⊕h2)⊕h3 h1&(h2&h3)=(h1&h2)&h3

3. дистрибутивність

h1&(h2⊕h3)=(h1&h2)⊕(h1&h3)

4. властивості констант

5. h⊕h=0 h&h=h
Твердження. Через операції алгебри Жегалкіна можна виразити всі інші булеві функції:

x→y=1⊕x⊕xy

x↓y=1⊕x⊕y⊕xy

18. Поліном Жегалкіна. Способи побудови. приклад.

Поліномом Жегалкіна (поліномом за модулем 2) від nзмінних x 1 , x 2 ... x n називається вираз виду:

c 0 ⊕c 1 x 1 ⊕c 2 x 2 ⊕ ... ⊕c n x n ⊕c 12 x 1 x 2 ⊕ ... ⊕c 12 ... n x 1 x 2 ... x n ,

де постійні C k можуть набувати значення 0 чи 1.

Якщо поліном Жегалкіна не містить творів окремих змінних, він називається лінійним (лінійна функція).

Наприклад, f=x⊕yz⊕xyz та f 1 =1⊕x⊕y⊕z - поліноми, причому друга є лінійною функцією.

Теорема. Кожна булева функція представляється у вигляді полінома Жегалкіна єдиним чином.

Наведемо основні методи побудови поліномів Жегалкіна від заданої функції.

1. Метод невизначених коефіцієнтів. Нехай P(x 1 ,x 2 ... x n) - Поліном Жегалкіна, що реалізує задану функцію f(x 1 ,x 2 ... x n). Запишемо його у вигляді

P=c 0 ⊕c 1 x 1 ⊕c 2 x 2 ⊕ ... ⊕c n x n ⊕c 12 x 1 x 2 ⊕ ... ⊕c 12 ... n x 1 x 2 ... x n

Знайдемо коефіцієнти Ck. Для цього послідовно надамо змінним x 1 x 2 ... x n значення з кожного рядка таблиці істинності. У результаті отримаємо систему з 2 n рівнянь із 2 n невідомими, що має єдине рішення. Вирішивши її, знаходимо коефіцієнти полінома P(X1, X2...Xn).

2. Метод, заснований на перетворенні формул над безліччю зв'язок (&). Будують деяку формулу Fнад безліччю зв'язок (,&), що реалізує цю функцію f(X 1 ,X 2 ... X n). Потім замінюють усюди підформули виду A на A⊕1, розкривають дужки, користуючись дистрибутивним законом (див. властивість 3), а потім застосовують властивості 4 та 5.

приклад. Побудувати поліном Жегалкіна функції f(X,Y)=X→Y

Рішення.
1. (метод невизначених коефіцієнтів). Запишемо шуканий поліном у вигляді:

P=c 0 ⊕c 1 x⊕c 2 y⊕c 12 xy

Користуючись таблицею істинності імплікації, отримуємо, що

f(0,0)=P(0,0)=C 0 =1

f(0,1)=P(0,1)=C 0 ⊕C 2 =1

f(1,0)=P(1,0)=C 0 ⊕C 1 =0

f(1,1)=P(1,1)=C 0 ⊕C 1 ⊕C 2 ⊕C 12 =1

Звідки послідовно знаходимо, C 0 =1, C 1 =1, C 2 =0, C 12 =1

Отже: x→y=1⊕X⊕XY.

2. (Метод перетворення формул.). Маємо: x→y=xvy=(xy)=(x(y⊕1)) ⊕1=1⊕x⊕xy
Зауважимо, що перевага алгебри Жегалкіна (порівняно з іншими алгебрами) полягає в арифметизації логіки, що дозволяє виконувати перетворення булевих функцій досить просто. Її недоліком у порівнянні з булевою алгеброю є громіздкість формул.




Подібна інформація.