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

Анотація наукової статті з математики, автор наукової роботи - Екгауз Є.Я., Цилова Є.Г.


LOGICALTRANSFORMATIONS ON THE CUBE

The article demonstrates the possibility of using the properties of logical operations, laws of logic and construction of logical expressions not with the help of the theoretic-multiple model of Euler's circles, but on the basis of a three-dimensional model of a logical cube. The possibilities and benefits of this interpretation are illustrated. Here's a list of tasks that you can do on the model.


Область наук:
  • Математика
  • Рік видавництва: 2019
    Журнал: Вісник Уральського інституту економіки, управління і права
    Наукова стаття на тему 'ЛОГІЧНІ ПЕРЕТВОРЕННЯ НА КУБІ'

    Текст наукової роботи на тему «ЛОГІЧНІ ПЕРЕТВОРЕННЯ НА КУБІ»

    ?УДК 51

    Екгауз Є.Я., Цилова Є.Г. ЛОГІЧНІ ПЕРЕТВОРЕННЯ НА КУБІ

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

    Ключові слова: логічні операції, логічні закони, логічні вирази, кола Ейлера, логічний куб, диз'юнктивні нормальні форми, вчинені диз'юнктивні нормальні форми.

    * * *

    Ekgauz Е. Уо., Tsylova Е. G.

    LOGICAL TRANSFORMATIONS ON THE CUBE

    The article demonstrates the possibility of using the properties of logical operations, laws of logic and construction of logical expressions not with the help of the theoretic-multiple model of Euler's circles, but on the basis of a three-dimensional model of a logical cube. The possibilities and benefits of this interpretation are illustrated. Here's a list of tasks that you can do on the model.

    Keywords: logical operations, logical laws, logical expressions, Euler circles, logical cube, disjunctive normal forms, perfect disjunctive normal forms.

    Існування геометричній інтерпретації для алгебраїчних і, зокрема, логічних конструкцій дозволяє представити їх наочно і глибше відчути сенс взаємозв'язків їх елементів. Операції над логічними елементами мають прямий аналог в алгебрі множин. так кон'юнкція відповідає перетину множин, диз'юнкція - їх об'єднання, а логічне заперечення - доповнення до універсальної множини. Таким чином, для інтерпретації логічних виразів вдало можуть бути використані кола Ейлера [1]. Однак в силу аморфності цих діаграм (пов'язаної з характером поняття безлічі) така інтерпретація втрачає наочність в разі спроби її застосування до алгебри логіки, так як вона не відображає внутрішню структуру логічних операцій.

    Досвід викладання курсу «Логіки» показав, що більш наочною в цьому випадку є інтерпретація логічних виразів за допомогою моделі «логічного куба» [2].

    Мал. 1. Модель «логічного куба»

    ft ft

    ft

    На ньому зручно працювати з формулами, які залежать від трьох (зокрема не більше ніж трьох) змінних і приведеними до виду діз'юнктівних нормальних форм (ДНФ) [3]. У цьому випадку члени диз'юнкцій можуть бути інтерпретовані як вершини, ребра і грані куба.

    Інтерпретація здійснюється наступним чином. Змінні і їх заперечення інтерпретуються як імена граней куба. Для визначеності приймемо, що змінні А, В, С позначають, відповідно, праву, передню і верхню межі куба, тоді гранях, протилежним цим трьом сторонам, природно привласнити імена А, В, С відповідно (див. Малюнок 1). Ребра куба при цьому будемо вважати кон'юнкції прилеглих граней, а його вершини кон'юнкції граней, що сходяться в цих вершинах.

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

    Можна поглянути на модель «логічного куба» і з іншого, теоретико-множинної, сторони.

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

    Неважко переконатися, що логічному нулю відповідає порожня множина вершин (0), а логічній одиниці - універсальна множина вершин (I), тобто весь куб. Крім того, операція кон'юнкції відповідає операції перетину множин (X л Y ^ X п У), операція діз'юн-

    кції операції об'єднання множин (X V Y ^ X і Y), а операція логічного заперечення - доповнення безлічі до універсальної множини (X ^ I / X).

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

    Для роботи з моделлю «логічного куба» необхідно в першу чергу навчитися «зображати» на моделі логічні формули. Для цього необхідно перетворити вихідну формулу до вигляду еквівалентної їй ДНФ, тобто спочатку за допомогою тотожності XоУ = (XлY) v | XлYj позбутися еквіваленцій і за допомогою тотожності X ^ У = XV У позбутися імплікацій, а потім за допомогою законів де Моргана [4; 5] XV У = X л У і X л У = XV У і закону зняття подвійного заперечення X = X домогтися того, щоб під знаком логічного заперечення знаходилися тільки окремі змінні. Якщо ж (або після того, як) формула приведена до виду еквівалентної їй ДНФ, вона представляється у вигляді диз'юнкції відповідних елементів куба (граней для одноелементні членів ДНФ, ребер для двоелементний членів ДНФ і окремих вершин для трьохелементної членів ДНФ).

    Модель "логічного куба" дозволяє наочно переконатися в справедливості всіх законів алгебри логіки, зокрема законів поглинання [6], найбільш важко розуміються і засвоюються.

    При описаної інтерпретації стають очевидними закони поглинання: А V (А л В) = А і А л (А V В) = А. Дійсно, так як А п В е А, В е А і В, то співвідношення А і (А ПВ) = А і А п (А і В) = А є приватними слу-

    ВІСНИК УРАЛЬСКОГО ІНСТИТУТУ ЕКОНОМІКИ, УПРАВЛІННЯ ТА ПРАВА • №4 2019

    87

    чаями відомого властивості вкладених множин: якщо безліч X вкладено в безліч У (X з Y), то X і У = У, X п У = X .

    Закони поглинання А ^ А л В ^ = А V В і А л ^ А V В | = А л В також мають наочне геометричне тлумачення, так як вірні співвідношення Аі ((I / А) п В) = А і В і А п ((I / А) і В) = А п В. У першому співвідношенні до другого члену диз'юнкції «додані» дві вершини, що належать ребру АВ, але так як вони належать і межі А першому члену диз'юнкції, то в вихідну диз'юнкцію нові вершини не додаються. У другому співвідношенні з другого члена кон'юнкції видалені вершини, що належать грані ребру АВ, але так як вони не належать грані, першому члену кон'юнкції, то вихідна кон'юнкція вершин не втрачає.

    Розглянемо тепер більш складні закони поглинання, які засновані на міркуваннях симетрії.

    Нехай в тричленної ДНФ симетрія порушена тільки по одній із змінних (наприклад, ВС V АВ V АС). Істотна особливість такої ДНФ полягає в тому, що ребра куба, які є членами цієї диз'юнкції, утворюють триланкову ламану. Якщо замінити ланки цього ламаної диз'юнкцій відповідних вершин куба, то одна з вершин середньої ланки АВ буде входити в ребро ВС, а інша - в ребро АС. Таким чином, середня ланка ламаної поглинається двома крайніми ланками, і, значить, трехзвенная ламана еквівалентна диз'юнкції її крайніх ланок. Отже, якщо в тричленної ДНФ симетрія порушена тільки по одній із змінних, то поглинається середня ланка цієї ламаної, тобто пропадає той член диз'юнкції, який не містить змінну, по якій _нарушена_ симетрія: ВС V АВ V АС = ВС V АС .

    Якщо ж в тричленної ДНФ симетрія порушена двічі (наприклад, ABv АС V ВС),

    то цієї ДНФ відповідає сукупність трьох ребер куба, два з яких (в нашому випадку АС та ВС) утворюють двухзвенную ламану, а третє (АВ) схрещується з кожним з перших двох. Якщо замінити ланки двухзвенной ламаної диз'юнкцій відповідних вершин куба, то ми отримаємо три з чотирьох вершин грані С, а четверту відсутню вершину «дасть» ребро. Таким чином, тричленна ДНФ, в якій симетрія порушена за двома змінним, еквівалентна мінімальної диз'юнкції, одним з членів якої є змінна, по якій симетрія не порушена (С), а іншим той член диз'юнкції, який не містить цю змінну (АВ). Цей член відповідає ребру куба, перпендикулярному площині грані С: АВ V АС V ВС = С V АВ.

    Залишаються нерозглянутими ще два випадки, коли в тричленної ДНФ, що залежить від трьох змінних, симетрія порушена за всіма трьома змінним (наприклад, АВ V ВС V АС), і коли симетрія взагалі не порушена (наприклад, АВ V АС V ВС). У першій ситуації такий ДНФ відповідає сукупність трьох взаємно перехресних ребер куба, а в другій ситуації такий ДНФ відповідає сукупність трьох ребер куба, що виходять із загальної вершини. В обох цих випадках розглядаються ДНФ є мінімальними і ніякі подальші їх спрощення неможливі.

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

    Диз'юнкція всіх восьми вершин куба

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

    Цікаво подивитися, як на моделі «логічного куба» функціонують закони де Моргана: А V В = А л В і А л В = А V В.

    Формулі А V В відповідає безліч I / (А і В) вершин куба, тобто безліч вершин куба, які не належать ні межі А, ні межі В. Таких вершин дві, і вони обидві належать протилежного ребру АВ. Звідси випливає, що А V В = А л В.

    Аналогічно, формулою А л В відповідає безліч I / (А п В) вершин куба, тобто безліч вершин куба, які не належать ребру АВ. Таких вершин шість, і вони заповнюють собою протилежні цьому ребру межі А і В. Таким чином, А л В = А V В.

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

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

    Цікава зв'язок між геометрією куба (як багатогранника) і комбінаторикою ДНФ, що лягла в основу моделі «логічного куба».

    Кожен Трьохелементний член ДНФ встановлює в таблиці істинності рівно одну одиницю і «закриває» рівно один рядок таблиці.

    Число можливих трьохелементної членів ДНФ (як і число рядків в трьохелементної таб-

    Г 3 ^

    особі істинності) одно

    v 3 у

    • 2 - 8. Вони зі-

    зауважують 8 вершин куба.

    Розглянемо двоелементний члени ДНФ. Кожен такий член встановлює в таблиці істинності рівно дві одиниці і «закриває» рівно два рядки таблиці.

    Число можливих двоелементний чле-

    вони

    нов ДНФ одно

    v 2 у

    • 22 - - • 4 -12

    2

    відповідають 12 ребрах куба.

    Розглянемо, нарешті, одноелементні члени ДНФ, тобто безпосередньо змінні і їх заперечення. Кожен такий член встановлює в таблиці істинності рівно чотири одиниці і «закриває», таким чином, рівно чотири рядки таблиці.

    Число можливих одноелементні чле-

    ^ 1

    • 21 = 3 • 2 = 6

    нов ДНФ одно

    v1 у

    (3 пере-

    сних і 3 їх заперечення). Вони відповідають 6 граней куба.

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

    ВІСНИК УРАЛЬСКОГО ІНСТИТУТУ ЕКОНОМІКИ, УПРАВЛІННЯ ТА ПРАВА • №>4 2019

    89

    БІБЛІОГРАФІЧНИЙ СПИСОК

    1. Некрасов В.П. Основи дискретної математики: Навчальний посібник. Єкатеринбург: Изд-во УІЕУіП, 2011. 93 с.

    2. Мадер В.В. Школяру про алгебри логіки: книга для позакласного читання учнів 10-11 класів середньої школи: Хрестоматія. М.: Просвещение, 1993. 126 с. (Світ знань).

    3. Підручник з дискретної математики ДНФ, СДНФ, КНФ, СКНФ [Електронний ресурс]. Режим доступу: http://www.mini-soft.ru/document/diskretnaya-matematika-3.

    4. Безліч [Електронний ресурс]. Режим доступу: http://math.siomax.ru/Sets.html.

    5. Спрощення логічних формул [Електронний ресурс]. Режим доступу: https://de.ifmo.ru/ bk_netra / page.php? Dir = 4&tutindex = 19&index = 18&layer = 1.

    6. Бєліков Д.А., Камінська О.В. 2.1. Логічні закони / Інформатика. Основи алгебри висловлювань: Навчально-методичний комплекс. Томськ, 2007 [Електронний ресурс]. Режим доступу: https://ido.tsu.ru/schools/physmat/data/res/informatika3/text/2_1 .html.

    REFERENCES

    1. Nekrasov V.P. Osnovy diskretnoj matematiki. Uchebnoe posobie. Ekaterinburg: Izd-vo UIEUiP, 2011. 93 s.

    2. Mader V. V. SHkol'niku ob algebre logiki: kniga dlya vneklassnogo chteniya uchashchihsya 10-11 klassov srednej shkoly: hrestomatiya. M .: Prosveshchenie, 1993. 126 s. (Mir znanij).

    3. Uchebnik po diskretnoj matematike DNF, SDNF, KNF, SKNF [Elektronnyj resurs]. Rezhim dostupa: http://www.mini-soft.ru/document/diskretnaya-matematika-3.

    4. Mnozhestva [Elektronnyj resurs]. Rezhim dostupa: http://math.siomax.ru/Sets.html.

    5. Uproshchenie logicheskih formul [Elektronnyj resurs] Rezhim dostupa: https://de.ifmo.ru/bk_netra/ page.php? Dir = 4&tutindex = 19&index = 18&layer = 1.

    6. Belikov D.A., Kaminskaya E.V. 2.1. Logicheskie zakony / Informatika. Osnovy algebry vyskazyvanij. Uchebno-metodicheskij kompleks. - Tomsk, 2007 [Elektronnyj resurs]. Rezhim dostupa: https://ido.tsu.ru/schools/physmat/data/res/informatika3/text/2_1.html.

    ВІДОМОСТІ ПРО АВТОРІВ

    ЕКГАУЗ Євгенія Яківна, викладач, ГАПО СТ «Каменська-Уральський технікум торгівлі та сервісу», м Каменськ-Уральський.

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

    ЦИЛОВА Олена Григорівна, кандидат фізико-математичних наук, доцент кафедри Вищої математики, Пермський національно-дослідний політехнічний університет, м Перм.

    E-mail: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

    Дата надходження статті: 5.12.2019

    рецензент:

    кандидат фізико-математичних наук

    Кротова О.Л.


    Ключові слова: ЛОГІЧНИХ ОПЕРАЦІЇ / ЛОГІЧНІ ЗАКОНИ / ЛОГІЧНІ ВИРАЗУ / кіл Ейлера / Логічний КУБ / Диз'юнктивна нормальна форма / Досконала диз'юнктивна нормальна форма / LOGICALOPERATIONS / LOGICAL LAWS / LOGICALEXPRESSIONS / EULER CIRCLES / LOGICALCUBE / DISJUNCTIVE NORMAL FORMS / PERFECT DISJUNCTIVE NORMAL FORMS

    Завантажити оригінал статті:

    Завантажити