Дизюнктивни нормални форми

Всяка булева функция може да се изрази чрез три операции: &, и ¬

Като прилагаме горните формули можем се избавим от всички операции, освен от споменатите три. Това може да доведе до необходимостта да се поставят скоби, за да се съхрани порядъка на операциите. Например:

Може да се наложи разкриване на скобите по правила, познати ни от училище:

както при числовите променливи:

По същото правило можем да разкрием скобите и когато операцията конюнкция е вътре, а дизюнкция – вън от скобите. Тази симетрия няма аналогия в алгебрата:

Разкриването на скобите, пред които стои отрицание става по тези формули:

За да получим дизюнктивната форма на коя да е булева формула, използваща само операциите &, , ¬ като се избавим от всички възможни скоби са достатъчни формулите (1), (3) и (4). За конюнктивната форма са необходими формулите (2), (3) и (4).

Сега можем да се върнем към примера (0):

Накрая константите TRUE и FALSE могат да се изразят във вида:

Полиномът на Жегалкин

Съществуват и други групи булеви операции, чрез които може да се изразят всички булеви функции. Такъв набор е , & и константата TRUE.

Този начин на представяне е предложен от Иван Иванович Жегалкин, руски и съветски математик (1869-1947). Един от основопожниците на математическата логика в Русия. Освен разглеждания полином, Жегалкин има важни трудове по пресмятане по модул 2, а също касаещи алгоритмичното решение на проблема с разрешимостта.

Полиномът на Жегалкин е булева формула, в която се използват само операции , & и константата TRUE при това без никакви скоби. По аналогия с обикновената алгебра променливите, свързани с операцията “&”, ще наричаме множители, а групите множители, свързани с операцията ““, ще наричаме събираеми.

Има няколко начина да се състави полином на Жегалкин.

Да предположим, че ни е дадена произволна булева формула. Първо трябва да се отървем от всички операции освен и & , с помощта на тези тавтологии:

Да се избавим от всички скоби с помощта на правилото:

После тази формула може да се съкрати като премахнем повторящите се елементи и излишните константи с помощта на законите на поглъщането:

От константата TRUE не можем да се избавим навсякъде, защото законът за поглъщане

добавя операцията “¬”, от която също искаме да се избавим.

И резултатът е полином на Жегалкин.

Примери:

С помощта на еквивалентни преобразувания

Да речем, че имаме функцията: f(x, y, z) = ¬x&y&z x&¬z Да преобразуваме замествайки отрицанието: f(x, y, z) = ((x TRUE)&y&z) (x&(z TRUE)) После операцията : f(x, y, z) = ((x TRUE)&y&z) (x&(z TRUE)) ((x TRUE)&y&z&x&(z TRUE)) Разкриваме скобите: f(x, y, z) = x&y&z TRUE&y&z x&z x&TRUE x&y&z&x&z TRUE&y&z&x&z x&y&z&x&TRUE TRUE&y&z&x&TRUE Прилагаме законите за поглъщането вътре в скобите: f(x, y, z) = x&y&z y&z x&z x y&x&z y&x&z y&z&x y&z&x Прилагаме законите за поглъщането за еднаквите скоби, отчитайки, че променливите, свързани с знак “&”, може да разменят местата си: f(x, y, z) = y&z x&z x x&y&z

Карти на Карно

Като пример да преобразуваме в полином на Жегалкин логическа функция от три променливи P (A, B, C), зададена в вид на карта на Карно. Етапите на преобразуване са показани на фигурата долу:

Илюстрация: wikipedia

• Разглеждаме всички клетки на картите на Карно по реда на количеството единици в кодовете им. За функция на три променливи, последователността на клетките е 000 – 100 – 010 – 001 – 110 – 101 – 011 – 111. На всяка клетка от картата на Карно съответства член от полинома на Жегалкин в зависимост от позициите на кода, в който стоят единиците. Например, на клетка 111 съответства член ABC, на клетка 101 — член AC, на клетка 010 — член B, на клетка 000 — член 1.

• Ако в разглежданата клетка е 0, преминаваме към следващата клетка.

• Ако в разглежданата клетка има 1, добавяме в полинома на Жегалкин съответстващия член, инвертираме в картата на Карно всички клетки, където този член е равен на 1 и преминаваме към следващата клетка. Например, ако разглеждайки клетка 110 в нея се оказва единица, то в полинома на Жегалкин добавяме член AB и инвертираме всички клетки на картата на Карно, където A=1 и B=1. Ако клетка 000 е равна на единица, то в полинома на Жегалкин се добавя член 1 и се инвертира цялата карта на Карно.

• Процесът на преобразуване може да се смята за завършен, когато, след поредната инверсия, всички клетки станат равни на нула

Метод на триъгълника

Методът на триъгълника позволява да се преобразува таблицата на истинносттаиистината в полином на Жегалкин чрез построяване на спомогателна триъгълна таблица в съответствие ствие със следните правила:

• Построява се пълна таблица на истинността, в която редовете са подредени с назрастването на двоичните кодове от 000…00 до 111…11.
• Построява се спомогателна триъгълна таблица, в която първата колона съвпада с колонката стойности на функцията в таблицата на истинността.
• Клетката във всяка следваща колона се получава чрез сумиране по модул 2 на две клетки от предишната колона – стоящата същия ред и реда позиция по-долу.
• Колоните на спомогателната таблица се номерират с двоични кодове в същия ред както редовете на таблицата на истинността.
• На всеки двоичен код съответства един от членовете на полинома на Жегалкин в зависимост от позицията на кода, в които стоят единиците. Например, на клетка 111 съответства член ABC, на клетка 101 – член на AC, на клетка 010 – член B, клетка 000 – член 1 и т.н.
• Ако на най-горния ред на някоя колоната има 1, то съответния член присътства в полинома на Жегалкин.

На схемата долу е показан пример за преобразуване на таблица на истинността в полином на Жегалкин за функция от три променливи P(A,B,C):

Илюстрация: wikipedia

Програмно преобразуване

По-долу е показана функция на C#, преобразуваща таблицата на истинността в полином на Жегалкин. Входен параметър на процедурата е текстов низ, в който е закодирана таблицата на истинността (въвеждат се списъци от стойностите на редовете на таблицата на истинността, например, ‘10101001 ‘). Функцията връща полином на Жегалкин във вид на текстов низ, където променливите са обозначени с латински букви A, B, C, D…. в реда, в който са в таблицата на истинността, знакът на операцията конюнкция се пропуска, а операция изключващото или се показан с +. Функцията използва алгоритъма на триъгълника.

static string toZhegalkin(string s)
        {
            if (s.Length == 0)
                return string.Empty;
            int N = 1, M = 0;
            string buffer = "";
            if (s[0] == '1')
                buffer += s[0];
            for (int i = 1; i < 16; i++)
            {
                if (N >= s.Length)
                    break;
                else
                    N = N << 1;
                M++;
            }
            bool[] A = new bool[N];
            for (int i = 0; i < N; i++)
                A[i] = (s[i] == '1') ? true : false;
            for (int i = 1; i <= N - 1; i++)
            {
                for (int j = 0; j < N - 1; j++)
                    A[j] ^= A[j + 1];
                if (A[0])
                {
                    buffer += '+';
                    for (int j = N, k = M; j > 0; j /= 2, k--)
                    {
                        if ((i & j) > 0)
                        {
                            buffer += (char)(64 - k + M);
                        }
                    }
                }
            }
            return buffer.ToString();
        }

Източник:
Мартин Гарднер „Математически развлечения“, том 2, гл.29
Философия Традиционализма, Лекция 9. Смерть как язык, А.Г.Дугин
Методы структурной психосоматики. – СПб.: Издательский дом «ЮВЕНТА»; М: Институт общегуманитарных исследований, 2001. – Минченков А. В., Елпидифоров II. Б. (doc)
Булева алгебра
Учебник по булева алгебра, Мирослав Войнаровский(C) 2002
Дискретна математика, Учебник, А.В. Косточка, Ф.И. Соловьева, Новосибирски държавен университет, Катедра “Теоретична кибернетика(pdf)
С физикой — от счетов к современным компьютерам, Владимир Клиньшов
Август Де Морган — основоположник логической теории отношений – intencia.ru
О технике вычислений предложений в символической логике, И. И. Жегалкин (pdf)
Полином Жегалкина – Материал из Википедии
Лекция Логически функции, доц. д-р Вл.Шкуртов