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

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

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

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

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

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

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

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

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

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

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

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

,

таким чином:

.

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

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

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

.

Таблиця 1.

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

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

Для довільних множин А, В і С справедливі наступні тотожності (табл. 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. З'ясувати, чи існує безліч Х, яка задовольняє за будь-якої А рівності:

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

Формули та закони логіки

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

НЕ запам'ятати, НЕ роздрукувати, а саме ще раз осмислити та власноруч переписати на папір – щоб вони були перед очима:

- Таблиця НЕ;
- Таблиця І;
- Таблиця АБО;
- Імплікаційна таблиця;
- Таблиця еквіваленції.

Це дуже важливо. В принципі, їх було б зручно занумерувати "Таблиця 1", "Таблиця 2" і т.д., але я неодноразово підкреслював вада такого підходу – як кажуть, в одному джерелі таблиця виявиться першою, а в іншому – сто першою. Тому використовуватимемо «натуральні» назви. Продовжуємо:

Насправді, з поняттям логічної формули ви вже знайомі. Наведу стандартне, але досить дотепне визначення: формуламиалгебри висловлювань називаються:

1) будь-які елементарні (прості) висловлювання;

2) якщо і – формули, то формулами також є вирази виду
.

Жодних інших формул немає.

Зокрема формулою є будь-яка логічна операція, наприклад, логічне множення . Зверніть увагу на другий пункт - він дозволяє рекурсивнимчином «створити» скільки завгодно довгу формулу. Оскільки - Формули, то - теж формула; оскільки і – формули, то - Теж формула і т.д. Будь-яке елементарне висловлювання (Знову ж згідно з визначенням)може входити до формули неодноразово.

Формулою неє, наприклад, запис - і тут простежується очевидна аналогія з «сміттям алгебри» , з якого не зрозуміло - чи потрібно числа складати або множити.

Логічну формулу можна розглядати як логічну функцію. Запишемо у функціональному вигляді ту саму кон'юнкцію:


Елементарні висловлювання й у разі грають роль аргументів (незалежних змінних), які у класичної логіці можуть набувати 2 значення: істинаабо брехня. Далі для зручності я іноді називатиму прості висловлювання змінними.

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

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

Треба сказати, що «вихід» тут вийшов «в один крок», але загалом логічна формула є складнішою. І в таких «непростих випадках» потрібно дотримуватися порядок виконання логічних операцій:

- Насамперед виконується заперечення;
– у другу чергу – кон'юнкція;
- Потім - диз'юнкція;
- Потім імплікація;
- І, нарешті, нижчий пріоритет має еквівалентність.

Приміром, запис передбачає, що треба здійснити логічне множення , та був – логічне складання: . Прямо як у «звичайній» алгебрі – «спочатку множимо, та був складаємо».

Порядок дій можна змінити звичним способом – дужками:
– тут насамперед виконується диз'юнкція і лише потім «сильніша» операція.

Напевно, всі розуміють, але на всякого пожежника: і це дві різніформули! (як у формальному, так і змістовному плані)

Складемо таблицю істинності для формули. До цієї формули входять два елементарні висловлювання і «на вході» нам потрібно перерахувати всі можливі комбінації одиниць та нулів. Щоб уникнути плутанини та різночитань, домовимося перераховувати комбінації. суворо у такому порядку (який я, власне, де-факто використовую із самого початку):

У формулу входять дві логічні операції, і відповідно до їхнього пріоритету, в першу чергу потрібно виконати запереченнявисловлювання. Ну що ж, заперечуємо стовпець «пе» – одиниці перетворюємо на нулі, а нулі – на одиниці:

На другому кроці дивимося на стовпці та й застосовуємо до них операцію АБО. Трохи забігаючи наперед, скажу, що диз'юнкція перестановна (і – це одне й те саме), І тому стовпці можна аналізувати у звичному порядку - зліва направо. При виконанні логічного додавання зручно використовувати наступне прикладне міркування: «Якщо два нулі – ставимо нуль, якщо хоча б одна одиниця – одиницю»:

Таблиця істинності побудована. А тепер згадаємо стару-добру імплікацію:

…уважно-уважно… дивимося на підсумкові колонки…. В алгебрі висловлювань такі формули називаються рівносильнимиабо тотожними:

(три горизонтальні рисочки – це значок тотожності)

У 1-й частині уроку я обіцяв висловити імплікацію через базові логічні операції, і виконання обіцянки не забарилося! Бажаючі можуть вкласти в імплікацію змістовний зміст (наприклад, «Якщо дощ, то на вулиці сиро»)і самостійно проаналізувати рівносильне твердження.

Сформулюємо загальне визначення: дві формули називаються рівносильними (тотожними)якщо вони приймають однакові значення при будь-якому наборі значень, що входять до цих формул змінних (елементарних висловлювань). Також кажуть, що «Формули рівносильні, якщо збігаються їх таблиці істинності»але мені не дуже подобається ця фраза.

Завдання 1

Скласти таблицю істинності для формули і переконатися у справедливості знайомого вам тотожності.

Ще раз повторимо порядок розв'язання задачі:

1) Так як у формулу входять дві змінні, то всього буде 4 можливі набори нулів та одиниць. Записуємо їх в обумовленому порядку.

2) Імплікації «слабші» за кон'юнкцію, але вони розташовуються в дужках. Заповнюємо стовпець, при цьому зручно використовувати таке прикладне міркування: «якщо з одиниці слідує нуль, то ставимо нуль, у всіх інших випадках – одиницю». Далі заповнюємо стовпець для імплікації, і при цьому, увага!- Стовпці і слід аналізувати «праворуч наліво»!

3) І на завершальному етапі заповнюємо підсумковий стовпець. А тут зручно міркувати так: "якщо в стовпцях і дві одиниці, то ставимо одиницю, у всіх інших випадках - нуль".

І, нарешті, звіряємось із таблицею істинності еквіваленції .

Основні рівносильності алгебри висловлювань

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

Комутативність кон'юнкції та комутативність диз'юнкції

Комутативність- Це перестановність:


Знайомі з 1-го класу правила: «Від перестановки множників (доданків) твір (сума) не змінюється». Але при всій здається елементарності цієї властивості, справедливо воно далеко не завжди, зокрема, некомутативним є множення матриць (У загальному випадку їх переставляти не можна), а векторний добуток векторів– антикоммутативно (перестановка векторів спричиняє зміну знака).

І, крім того, тут знову хочу підкреслити формалізм математичної логіки. Так, наприклад, фрази «Студент склав іспит і випив»і «Студент випив та склав іспит»різні з змістовної точки зору, але невиразні з позицій формальної істинності. …Таких студентів знає кожен із нас, і з етичних міркувань ми не озвучуватимемо конкретних імен =)

Асоціативність логічного множення та додавання

Або якщо «по-шкільному» – поєднана властивість:


Дистрибутивні властивості

Зверніть увагу, що у другому випадку некоректно говорити про «розкриття дужок», у сенсі тут «фікція» – їх можна забрати взагалі: , т.к. множення – це сильніша операція.

І знову ж таки – ці, здавалося б, «банальні» властивості виконуються далеко не у всіх алгебраїчних системах, і, більше того, вимагають доказів (про які ми дуже скоро поговоримо). До речі, другий дистрибутивний закон несправедливий навіть у нашій «звичайній» алгебрі. І справді:

Закон ідемопотентності

Що робити, латину.


Прямо якийсь принцип здорової психіки: "я і я - це я", "я чи я - це теж я" =)

І відразу кілька схожих тотожностей:


…мда, щось я навіть підзавіс… так і доктором філософії завтра можна прокинутися =)

Закон подвійного заперечення

Ну а тут уже напрошується приклад із російською мовою – всі чудово знають, що дві частки «не» означають «так». А для того, щоб посилити емоційне забарвлення заперечення нерідко використовують три «не»:
– навіть із крихітним доказом вийшло!

Закони поглинання

- «А чи був хлопчик?» =)

У правому тотожності дужки можна опустити.

Закони де Моргана

Припустимо, що суворий викладач (ім'я якого вам також відомо:))ставить іспит, якщо – Студент відповів на 1-е запитання і – Студент відповів на друге запитання. Тоді висловлювання про те, що Студент неЗдав екзамен, буде рівносильно твердженню – Студент невідповів на 1-е запитання абона 2-е питання.

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

Доведемо тотожність. Оскільки в нього входить єдине висловлювання, то «на вході» можливо лише два варіанти: одиниця або нуль. Далі приписуємо одиничний стовпець і застосовуємо до них правило І:

В результаті «на виході» отримано формулу, істинність якої збігається з істинністю висловлювання. Рівносильність доведена.

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

Тепер переконаємось, наприклад, у справедливості закону де Моргана.

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

Далі складемо таблицю істинності для правої частини. Тут теж все прозоро – насамперед проводимо «сильніші» заперечення, потім застосовуємо до стовпців правило І:

Результати збіглися, таким чином, тотожність доведена.

Будь-яку рівносильність можна подати у вигляді тотожно істинної формули. Це означає що ПРИ БУДЬ-ЯКОМУ вихідному наборі нулів і одиниць"на виході" виходить строго одиниця. І цьому є дуже просте пояснення: оскільки таблиці істинності і збігаються, то, зрозуміло, вони еквівалентні.

Або, якщо компактніше:

Завдання 2

Довести такі рівносильності:

б)

Коротке рішення наприкінці уроку. Не лінуємося! Намагайтеся не просто скласти таблиці істинності, але ще й чіткосформулювати висновки. Як я нещодавно зазначав, зневага простими речами може обійтися дуже дорого!

Продовжуємо знайомитись із законами логіки!

Так, абсолютно правильно - ми з ними вже працюємо:

Істинапри , називається тотожно істинною формулоюабо законом логіки.

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

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

Фірмовий приклад протиріччя від давніх греків:
– жодне висловлювання може бути істинним і хибним одночасно.

Доказ тривіальний:

«На виході» отримані виключно нулі, отже формула дійсно тотожна хибна.

Однак і будь-яка суперечність – це також закон логіки, зокрема:

Не можна охопити таку велику тему в одній-єдиній статті, і тому я обмежуся лише кількома законами:

Закон виключеного третього

- У класичній логіці будь-яке висловлювання істинно чи хибно і третього не дано. «Бути чи не бути» – ось у чому питання.

Самостійно складіть табличку істинності і переконайтеся, що це тотожно істиннаформула.

Закон контрапозиції

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

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

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

І знову повернемося до наших змістовних прикладів: для висловлювань - Число ділиться на 4, - Число ділиться на 2справедливі прямаі протилежнатеореми, але помилкові зворотнаі протилежна зворотнійтеореми. Для «дорослої» формулювання теореми Піфагора істинні всі 4 «напрямки».

Закон силогізму

Теж класика жанру: «Усі дуби – дерева, всі дерева – рослини, отже, всі дуби – рослини».

Ну і тут знову хочеться відзначити формалізм математичної логіки: якщо наш суворий Викладач думає, що якийсь Студент – є дуб, то з формального погляду даний Студент, безумовно, рослина =) …хоча, якщо замислитись, то може бути і з неформальною теж = )

Складемо таблицю істинності для формули. Відповідно до пріоритету логічних операцій, дотримуємося наступного алгоритму:

1) виконуємо імплікації та . Взагалі кажучи, можна одразу виконати і 3-ю імплікацію, але з нею зручніше (і припустимо!)розібратися трохи згодом;

2) до стовпців застосовуємо правило І;

3) ось тепер виконуємо;

4) і на завершальному кроці застосовуємо імплікацію до стовпців та .

Не соромтеся контролювати процес вказівним та середнім пальцем:))


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

Завдання 3

З'ясувати, чи буде законом логіки наступна формула:


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

Перетворення логічних формул

Крім свого «логічного» призначення, рівносильності широко використовуються для перетворення та спрощення формул. Грубо кажучи, одну частину тотожності можна міняти іншу. Так, наприклад, якщо в логічній формулі вам зустрівся фрагмент , то за законом ідемпотентності замість нього можна (і потрібно) просто записати . Якщо ви бачите, то за законом поглинання спрощуйте запис до. І так далі.

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



, де - будь-які (скільки завгодно складні)формули

Перетворимо, наприклад, складну імплікацію (1-е тотожність):


Далі застосуємо до дужки «складний» закон де Моргана, при цьому, в силу пріоритету операцій, саме закон, де :


Дужки можна прибрати, т.к. всередині знаходиться «сильніша» кон'юнкція:


Ну, а з комутативністю взагалі все просто – навіть позначати нічого не потрібно… щось запал мені в душу закон силогізму:))


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


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

Як тренування впросимо формулу.

З чого почати? Насамперед, розібратися з порядком дій: тут заперечення застосоване до цілої дужки, яка «скріплена» з висловлюванням «трохи слабшою» кон'юнкцією. Фактично, маємо логічний твір двох множників: . З двох операцій, що залишилися, нижчим пріоритетом має імплікація, і тому вся формула має наступну структуру: .

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

(1) Використовуємо тотожність . А нашому випадку.

Потім зазвичай слідують «розбирання» з дужками. Спочатку все рішення, потім коментарі. Щоб не вийшло «олія масляна», використовуватиму значки «звичайної» рівності:


(2) До зовнішніх дужок застосовуємо закон де Моргана, де.

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

х 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
Зауважимо, що перевага алгебри Жегалкіна (порівняно з іншими алгебрами) полягає в арифметизації логіки, що дозволяє виконувати перетворення булевих функцій досить просто. Її недоліком у порівнянні з булевою алгеброю є громіздкість формул.




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