Первая страница
Наша команда
Контакты
О нас

    Головна сторінка



Булеві функції та перетворення Булеві змінні І функції

Скачати 360.33 Kb.

Булеві функції та перетворення Булеві змінні І функції




Скачати 360.33 Kb.
Дата конвертації09.04.2017
Розмір360.33 Kb.


Булеві функції та перетворення

1.1. Булеві змінні і функції

Двійкові інтерпретації, істотні та фіктивні змінні

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

Інтерпретатор мови програмування (interpreter) - програма чи технічні засоби, необхідні для виконання інших програм, вид транслятора, який здійснює пооператорну (покомандну, построкову) обробку, перетворення у машинні коди та виконання програми або запиту (на відміну від компілятора, який транслює у машинні коди всю програму без її виконання).
Двійкова система числення - це позиційна система числення, база якої дорівнює двом та використовує для запису чисел тільки два символи: зазвичай 0 (нуль) та 1 (одиницю). Числа, представлені в цій системі часто називають двійковими або бінарними числами.
Таким чином, всі операції, які виконує комп'ютер, проводяться на множині {0,1}. Ці перетворення зручно формально зображати за до­помогою апарата двійкової логіки, який був розроблений Джорджем Булем у середині XIX століття. Ця алгебраїчна структура є алгеброю і називається булевою. Булева алгебра використовується при розв'язанні різних задач обробки інформації, при роботі з базами даних, в логічному програмуванні, при проектуванні інтелектуальних систем, для конструювання та аналізу роботи комп'ютерів та інших електронних пристроїв. У цій главі розглянуто основні вла­стивості булевих функцій з аргументами з множини {0, 1} і способи зображення булевих функцій у вигляді виразів булевої алгебри.
Конструюва́ння - процес створення конструктором проекту певного об'єкта техніки, що полягає у визначенні форми, розмірів, взаємного розташування й параметрів частин й елементів конструкції об'єкта, його складових (агрегатів, систем, вузлів тощо), способу їхнього з'єднання, вибору матеріалів окремих елементів та розробки конструкторської документації.
Проектува́ння - процес створення проекту, прототипу, прообразу майбутнього об'єкта, стану та способів його виготовлення. У проектуванні застосовують системний підхід, який полягає у встановлені структури системи, типу зв'язків, визначені атрибутів, аналізуванні впливів зовнішнього середовища.
Інтелектуал - людина розумової праці[Джерело?]. «Інтелектуалом» також називають[Хто?] освічену, начитану людину з високо розвиненим інтелектом[Джерело?].
Ло́гіка (грец. λογιχη від грец. logos - слово, значення, думка, мова) - наука про закони і різновиди мислення, способи пізнання та умови істинності знань і суджень.
Алгебра логіки (Булева логіка, двійкова логіка, двійкова алгебра) - розділ математичної логіки, що вивчає систему логічних операцій над висловлюваннями. Найчастіше передбачається, що висловлювання можуть бути тільки істинними або помилковими, тобто використовується так звана бінарна або двійкова логіка, на відміну від, наприклад, тризначної логіки.
Обробка інформації́ - вся сукупність операцій (збирання, введення, записування, перетворення, зчитування, зберігання, знищення, реєстрація), що здійснюються за допомогою технічних і програмних засобів, включаючи обмін по каналах передачі даних [6.
Алгебраїчна система (алгебраїчна структура) - в математиці це непорожня множина з заданим на ній набором операцій та відношень, що задовільняють деякій системі аксіом.
Логі́чне програмува́ння - парадигма програмування, а також розділ дискретної математики, що вивчає методи і можливості цієї парадигми, засновані на виведенні нових фактів з даних фактів згідно із заданими логічними правилами.
Електро́ніка (від грец. Ηλεκτρόνιο - електрон) - наука про взаємодію електронів з електромагнітними полями і про методи створення електронних приладів і пристроїв, в яких ця взаємодія використовується для перетворення електромагнітної енергії, в основному для передачі, обробки і зберігання інформації.
Бу́лева фу́нкція (функція алгебри логіки, логічна функція) - в дискретній математиці відображення Bn → B, де B = - булева множина.
Булева функція може мати велику кількість змінних і знаків операцій, у той час, як може існувати інше, еквівалентне зображення даної функції, що має меншу кіль­кість змінних і операцій.
Кількість - в Арістотелівській логіці друга з 10 категорій (класів, розрядів, які спрощують процес розумового визначення будь-якої речі), побічна обставина матеріальних речей , за допомогою якої вони поширюються в просторі, вимірюються якоюсь математичною нормою і здатні бути поділеними на окремі частини.
У главах розділу описано методи одержання виразів з мінімальною кількістю змінних і знаків операцій.

Розглянемо двохелементну множину В, елементи якої бу­демо позначати через 0 і 1: В = {0, 1}.

Визначення

Змінні, які можуть приймати значення тільки з множини В, називаються логічними або булевими змінними. Самі значення 0 і 1 булевих змінних називаються булевими константами.

В мовах програмування для роботи з такими змінними, як правило, вводиться спеціальний логічний (булевський) тип (наприклад, у мовах Рascal i Java — boolean, у С — bool).

Константа (лат. constans - стала величина, інша назва - стала) - величина, що не змінює свого значення протягом певного процесу (на відміну від змінної, значення якої може змінюватись). Прикладами констант є число пі, коефіцієнти многочленів, температура під час ізотермічного процесу.
Мо́ва програмува́ння (англ. Programming language) - це штучна мова, створена для передачі команд машинам, зокрема комп'ютерам. Мови програмування використовуються для створення програм, котрі контролюють поведінку машин, та запису алгоритмів.
Змінна цього типу приймає два значення: true і false.

Визначення

Функція виду у = f(x1,x2,...,xn), аргументи х, і значення у якої належать множині В, називається n-місною буле-вою функцією. Такі функції також називають логічними або перемикальними функціями.



Визначення

Кортеж (х1, х2,…, хn) конкретних значень булевих змінних називається двійковим словом (п-словом) або булевим на­бором довжини п. Для булевої функції y=1,х2,…хn) конкретне (індивідуальне) значення булевого набору 1,х2,…хn) називається також інтерпретацією булевої функції f. Множина всіх двійкових слів, що позначає­ться через Вn, називається п-виміриим булевим кубом і містить 2n елементів-слів: n | = 2n.

Дійсно, для п = 1 є всього 21 = 2 слова — (0) і (1), а за ра­хунок збільшення довжини слова на один символ кількість слів збільшується в два рази, оскільки додатковий символ може приймати два значення — 0 або 1. Для наочності зобра­зимо в одному рядку набори булевих змінних зростаючої дов­жини, у другому рядку — кількості різних наборів відповідної довжини:

(x1),(x1,x2),(x1,x2,x3),…,(x1,x2,…,xn);

2,2*2,2*2*2=2

Покажемо, що кількість всіх можливих булевих функцій y=f(х1, х2,…, хn) дорівнює 22n. Зауважимо, що у позначеннях булева функція є відображення f: ВnВ, В = {0, 1}. Позна­чимо n-слово одним символом u= 1, х2,…, хn) і пронумеруємо всі різні слова: {и} = {u1, u2,…, up}, де р=2n Дві булеві функції f1(u) i f2(u) співпадають, якщо

f1(ui)= f2(ui) для всіх иі , і = 1, 2,…,2n. Оскільки f(u) може мати два значення (0 або 1), то число різних функцій f(u) дорівнює кількості різних булевих слів (наборів) довжини р, тобто числу 2Р = 22n.

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



Визначення

Змінна xi у функції у = f(x1,…xi-1,0,xi 1,…,xn) назива­ється неістотною (або фіктивною), якщо



f(x1,…xi-1,0,xi 1,…,xn) = f(x1,…xi-1,1,xi 1,…,xn)

при будь-яких значеннях решти змінних, тобто якщо зміна значення xi, у будь-якому наборі значень x1,…,xn не змінює значення функції.

В цьому випадку функція f(x1,…,xn) фактично залежить від n-1 змінної, тобто зображує функцію g(x1,…xi-1,xi 1,…,xn). Стверджують, що функція g одержана з функції f видаленням фіктивної змінної, а функція f одержана з g введенням фіктив­ної змінної, причому ці функції за визначенням рівні.

1.2. Способи задання булевих функцій

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

Булеві функції можуть бути задані такими спосо­бами:

1.За допомогою таблиці істинності (значеннями на кожній з інтерпретацій).

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


  1. Порядковим номером, який має ця функція.

  2. Аналітично (у вигляді формули).

Розглянемо кожний із зазначених способів докладніше.

1.2.1. Таблиці істинності

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

В таблиці істинності кожній змінній та значенню самої функції відповідає по одному стовпчику, а кожній інтер­претації — по одному рядку. Кількість рядків у таблиці відповідає кількості різних інтерпретацій функції. Булеві функції φ(х), які залежать від однієї змінної, наведено в таб­лиці 1.1

Таблиця 1.1. Булеві функції однієї змінної


x

φ0

φ1

φ2

φ3

0

0

0

1

1

1

0

1

0

1

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

φ0 0 — функція константа 0,

φ1 = х — функція повторення аргументу,

φ2 =— функція інверсії або заперечення аргументу,

φ3 = 1 — функція константа 1.

Різні булеві функції двох змінних f(х, у) зображено в таб­лиці 1.2, їх кількість дорівнює = 16.



Таблиця 1.2. Булеві функції двох змінних

x

y

f0

f1

f2

f3

f4

f5

f6

f7

f8

f9

f10

f11

f12

f13

f14

f15

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

0

1

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

1

0

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

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

Матема́тика (грец. μάθημα - наука, знання, вивчення) - наука, яка первісно виникла як один з напрямків пошуку істини (у грецькій філософії) у сфері просторових відношень (землеміряння - геометрії) і обчислень (арифметики), для практичних потреб людини рахувати, обчислювати, вимірювати, досліджувати форми та рух фізичних тіл.
Позначення, назви і прочитання булевих функцій від двох змінних зображено в таблиці 1.3.



Таблиця 1.3. Позначення булевих функцій двох змінних

Функція

Позначення

Назва

Інші позначення

Прочитання

1

2

3

4

5

f0(x,y)

0

константа 0




будь-яке 0, константа 0

f1(x,y)

ху = ху

кон'юнкція (логічне «і»)

-, &, &&, *, АND, І, , min

x і у

f2(x,y)

х←у

заперечення імплікації

\

х і не у

f3(x,y)

x

повторення першого аргументу




як x

f4(x,y)

у←х

заперечення оберненої імплікації

\

не х і у

f5(x,y)

У

повторення другого аргументу




як у

f6(x,y)

ху

що виключає «або» (сума за модулем 2)

,<>, > <, !=,

XOR


х не як у

f7(x,y)

xу

диз'юнкція (логічне «або»)

ОR, АБО, , maх

х або у

f8(x,y)

ху

заперечення диз'юнкції (стрілка Пірса)

xу, х о у

не х і не у

f9(x,y)

х~у

еквівалентність

, Еqv, =

х як у

f10(x,y)



заперечення другого аргументу



не у

f11(х,у)

у —> X

обернена імплікація



х, якщо у або не у)

f12(х,у)



заперечення першого аргументу



не x

f13(х,у)

х у

імплікація

, =>, Imp

якщо х, то у (не х або у)

f14(х,у)

x|у

заперечення кон'юнкції (штрих Шеффера)

xy, х у

не x або не у

f15(х,у)

1

константа 1




будь-яке 1, константа 1

Позначення Not, Аnd, Оr, Хоr, Іmр, Еqv використо­вуються у мові програмування Ваsіс; позначення !, &, ! = використовуються у мові С; позначення використову­ються в системі Маthcad. Для стислості у прикладах та ви­кладеннях ми будемо опускати знак кон'юнкції і писати ху замість ху.



1.2.2. Номери булевих функцій та інтерпретацій

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

А́томний но́мер (протонне число,зарядове число, порядковий номер, Z) - властивість атома (нукліда, атомного ядра), яка вказує на загальну кількість протонів, що містяться в його ядрі, отже одночасно вказує на його заряд в одиницях елементарного заряду, а також на порядкове місце хімічного елемента в періодичній системі хімічних елементів.
Натура́льні чи́сла - числа, що виникають природним чином при лічбі. Це числа: 1, 2, 3, 4, … Множину натуральних чисел прийнято позначати знаком N . .}
Молодшим розрядом вважається самий нижчий рядок (значення функції на інтер­претації (1, 1,…, 1)), а старшим — самий верхній (значення функції на інтерпретації (0, 0,…, 0)). Вказаний порядковий номер функції, як двійковий, так і десятковий, повністю ви­значає булеву функцію.

Кожній інтерпретації булевої функції також привласнює­ться свій номер — значення двійкового коду, який зображує інтерпретація. Інтерпретації, що записана у верхньому рядку таблиці істинності, привласнюється номер 0, потім йде інтер­претація номер 1 тощо. В самому нижчому рядку розташована інтерпретація за номером 2n - 1, де пкількість змінних, від яких залежить булева функція.

1.2.3. Булеві алгебри: загальна, двохелементна і логічна

Введемо поняття булевої алгебри (А,,,, 0, 1) як дистрибутивної ґратки з доповненням, де , бінарні операції, унарна операція на множині-носії А, які володі­ють визначеними властивостями.

Біна́рна опера́ція (бінарний оператор) - це математичний об'єкт, що складається з двох величин і певної дії над ними.
В математиці унарна операція - операція тільки з одним операндом, інакше операція з єдиним входом, або функція від однієї змінної.
Аналізуючи алгебраїчну фор­му всіх цих властивостей (див. п. 3.
Ана́ліз (від грец. αναλυσις - «розклад») - розчленування предмету пізнання, абстрагування його окремих сторін чи аспектів. Метод дослідження, який вивчає предмет, уявно чи реально розчленовуючи його на складові елементи, як-от частини об'єкта, його ознаки, властивості, відношення, відтак розглядає кожен з виділених елементів окремо в межах єдиного цілого; протилежний метод - синтез.
5) і заміняючи позначення операцій ,,на •, , відповідно, ми виділяємо такий набір незалежних властивостей, які можна вважати аксіома­ми або незалежними законами булевої алгебри:



  1. Комутативність: а b = b а, а b = b а.

  2. Асоціативність: а (b с) = (a b) с,

а • (b • с) = b) • с.

3.Дистрибутивність: а (bс) = b) • (а с),



а (b с) = b) • с).

4.Закони для нуля, одиниці та заперечення:



а 0 = а, а = 1, а • 1 = 1, а = 0.

Всі інші відношення (деякі з них також називаються «за­конами» булевої алгебри) є наслідком зазначених вище.

Ді́лення (також діління́)- в математиці, бінарна операція, що обернена множенню.
Причи́нність, також причи́нно-наслідко́вий зв’язо́к, причи́новість, причи́ново-наслідко́вий зв’язо́к, кауза́льність - (неформально, нестрого розуміючи) зв’язок між подією А («причиною») й іншою подією Б («наслідком»), яка необхідно настає за першою чи витікає з неї.
Зок­рема, з 1-4 виходять:



  1. Закони ідемпотентності: а а = а а = а.
    Ідемпотентність (лат. idem - такий самий, лат. potens - сильний) - властивість унарних та бінарних операцій в алгебрі та логіці. Термін «ідемпотентність» означає властивість, яка проявляється в тому, що повторна її дія над будь-яким об'єктом уже не змінює результату.


  2. Інші властивості одиниці і нуля: а 1 = 1, а • 0 = 0.

  3. Закони поглинання: а • (а b) = а (а b) = а.

  4. Закон інволюції (подвійного заперечення): а = .

  5. Закони де Моргана (подвійності): = ;

= ;.

Таким чином, визначення булевої алгебри вигля­дає так (після «алгебраїчної розшифровки» понять, що беруть у ньому участь):



Визначення

Булева алгебра — це алгебраїчна структура (А, •, ,, 0, 1) з бінарними операціями •, : А2→А, унарною операцією «»; АА і виділеними елементами 0, 1 в носії А, які задовольняють властивості 1-4.

Позначення операцій , замість •, у спеціальних бу­левих алгебрах запозичене з логіки, в якій Дж.

Елеме́нт (лат. elementum - стихія, первинна речовина) - нерозкладний (у даній системі) компонент складних тіл, матеріальних систем, теоретичних побудов; будь-який об'єкт, пов'язаний певними відношеннями з іншими об'єктами в єдиний комплекс.
Запози́чення - елемент чужої мови (слово, морфема, синтаксична конструкція та ін.), який було перенесено з однієї мови до іншої в результаті мовних контактів, а також сам процес (запозича́ння) переходу елементів однієї мови до іншої.
Буль вперше виділив алгебраїчну структуру з властивостями 1-4. Носій цієї структури В = {0, 1} складається з двох елементів.



Визначення

Алгебраїчна структура (В,,,), В = {0, 1}, де опе­рація є кон'юнкція f1(х, у), є диз'юнкція f7(х, у) (див. таблиці 4.2, 4.3), «» є заперечення або інверсія 2(х) (див. таблицю 4.1), називається двохелементною булевою алгеброю.

Виконання законів булевої алгебри 1-4 у структурі (В,,,), а також законів 5-9 виходить з визначення операцій кон'юн­кції, диз'юнкції та заперечення через таблиці істинності 1.1, 1.2 (див. п. 1.4).

Визначення

Алгеброю логіки називається двохелементна булева алгебра (В,,,, →, ), В = {0, 1}, в якій множи­ну операцій доповнено двома бінарними операціями: імплікацією (f13(х, у)) та еквівалентністю (f9(х, у)) (див. таблиці 1.2, 1.3).

1. 2.4. Булеві формули і пріоритет операцій

Булеві функції можуть бути задані аналітично, тобто фор­мулами.



Визначення

Формула — це вираз, що містить булеві функції та їхні суперпозиції.

Визначення

Суперпозицією називається спосіб одержання нових функцій шляхом підстановки значень одних функцій замість значень аргументів інших функцій. Точніше, суперпозицією булевої функції f0 і функцій f1, ..., fn називається функція f1 ,…, хm) =f0(g11,…, хт),…, gк1,…,хт)), де кожна з функцій gi1,…, хт) співпадає з однією з функцій f1, … fn, i {1, …, k}. При цьому деякі з функцій fi, а значить і gi можуть тотожно співпадати з однією із змінних xt, t {1, …, m}.

Визначення

Формули, що зображують одну й ту ж функцію, назива­ються еквівалентними або рівносильними.

Еквівалентність формул позначається знаком рівності.

Знак рівності (=) - це математичний символ, що використовується для позначення рівності. Він був винайдений в 1557 році Робертом Рекордом . У рівнянні, знак рівності поміщається між двома виразами, які мають те ж саме значення.
Один із способів встановити еквівалентність формул складається з такого: для кожної формули будується таблиця істинності, а потім одержані таблиці порівнюються, тобто фактично для кожного набору змінних перевіряється, чи дорівнюють на ньому значення функцій. Існують й інші способи перевірки еквівалентності формул, які буде розглянуто нижче.

1.2.5. Перехід від формули до таблиці істинності функції

Побудуємо таблицю істинності для функції, що задана такою формулою:



f(x,y,z,t) = x(z)t,

Функція залежить від чотирьох змінних і, отже, для неї є 24 = 16 iнтерпретацій. Для побудови таблиці істинності необ­хідно визначити значення функції на всіх інтерпретаціях:

f(0, 0, 0, 0) = 0 (0) 0 = 01(0) 0 =

= 01(01) 0 = 01(1) 0 = 01 0 = 1 0 =0;

f(0, 0, 0, 1) =0 (0) 1 = 01(0) 1 =

= 0 1(0 1) 1 = 0 1(1) 1 = 01 1 = 1 1 = 1;

f(0, 0, 1, 0) = 0 (1) 0 = 01(0) 0 =

= 0 1(1 1) 0 = 01(1) 0 = 01 0 = 1 0 = 0;

f(1, 1, 1, 1) = 1(1 ) 1 = 1 0(1) 1 =



= 10(10) 1 = 10(1) 1 =10 1 = 1 1 = 1.

Розмістимо в таблиці істинності інтерпретації в порядку збільшення відповідних їм двійкових номерів і запишемо одер­жане значення функції на кожній інтерпретації. Одержимо таблицю істинності функції f(x,y,z,t) = =x(z)t (таблиця 1.6).



Таблиця 1.6. Таблиця істинності f(x,y,z,t)

x

y

z

t

f(x,y,z,t)

0

0

0

0

0

0

0

0

1

1

0

0

1

0

0

0

0

1

1

1

0

1

0

0

1

0

1

0

1

1

0

1

1

0

1

0

1

1

1

1

1

0

0

0

1

1

0

0

1

1

1

0

1

0

1

1

0

1

1

1

1

1

0

0

1

1

1

0

1

1

1

1

1




0

1

1

1

1

1


Скачати 360.33 Kb.