Геометричне подання функцій алгебри логіки

Н ехай Eⁿ – множина всіх можливих наборів (x₁, x₂, …, x_n): Eⁿ = {(x₁, x₂, …, x_n)}, де x_i = 0  1.

Цю множину можна розглядати як множину всіх вершин одиничного куба розмірності n. Так функцію двох змінних можна інтерпретувати за допомогою квадрата, заданого в системі координат Ox₁x₂. Вершини квадрата відповідають комбінаціям змінних – геометричне подання функції двох змінних. Отже, дві вершини, які належать одному і тому самому ребру, називаються сусідніми, причому вони „склеюються” за змінною, що змінюється вздовж цього ребра: x₁x₂  x₂ = x₂(x₁  ) = x₂.

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

Б улева функція відображається на n-вимірному кубі вилученням вершин, що відповідають векторам (x₁, x₂, …, x_n), на яких функція y = f(x₁, x₂, …, x_n) набуває значення 1.

Спрощення булевих функцій

Булеві функції використовують для спрощення так званих релейно-контактних і вертикальних схем. У випадку релейно-контактних схем кожній змінній x (відповідно ) булевої функції f(x₁, ..., x_n) ставлять у відповідність перемикач, який пропускає струм тоді й лише тоді, коли x = 1 ( = 0). Операція  (диз’юнкція) інтерпретується як паралельне з’єднання перемикачів, а операція  (кон’юнкція) – як послідовне з’єднання. Запис f(a₁, ..., a_n ) = 1 інтерпретується як „струм проходить через схему”, коли стани перемикачів відповідають набору значень (a₁, ..., a_n)  {0, 1}ⁿ, а f(a₁, ..., a_n) = 0 інтерпретується як „струм не проходить через схему” при цьому наборі значень станів пе­ре­микачів. З ДНФ і КНФ випливає, що для кожної булевої функції f мож­на побудувати електричний ланцюг – паралельно-послідовне з’єднання перемикачів, який пропускає струм тоді й лише тоді, коли f = 1.

Два електричні ланцюги вважають еквівалентними, якщо вони одночасно пропускають або не пропускають струм при однакових станах відповідних перемикачів. З двох еквівалентних ланцюгів простішим вважається той, який складається з меншої кількості перемикачів. Наприклад, f(x, y, z) = ((x  y)  z)  (  z) відповідає ланцюг із 5 перемикачів. Але f(x, y, z) = xz  yz  z = z(x  )  yz = z(1  y) = z. Тому один з еквівалентних ланцюгів складається з єдиного перемикача z.

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

1 ) вентиль з двома входами і одним виходом: на виході одер­жу­є­мо 1 (наявність напруги), якщо хоча б на один з двох входів подається 1;

2



) вентиль з двома входами і одним виходом: на виході одер­жу­є­мо 1, якщо на обидва входи подається 1;

3 ) вентиль з одним входом і одним виходом: на виході одер­жу­є­мо 1, якщо на вході 0 і на виході одержуємо 0, якщо на вході 1.

При конструюванні вентильних схем виникає проблема їхньої мінімізації, яка полягає в знаходженні булевої функції такого виду, який би мав „простий вигляд”. Вважаємо, що всі булеві функції, з якими ми працюємо, мають ДНФ, тобто мають вигляд f = , де f_i = , де  {0, 1}, x¹ = x, x⁰ = .

Функції f_i називаються мономами. Кожне входження змінної у вираз для функції f назвемо літералом.

Означення 1. ДНФ f назвемо мінімальною за літералами, якщо кожна еквівалентна їй ДНФ g не містить меншої кількості літералів. ДНФ називається мінімальною за мономами, якщо кожна еквівалентна їй ДНФ g не містить меншої кількості мономів або такої ж кількості мономів, але з меншою кількістю літералів.

Означення 2. Скажемо, що вираз g має наслідком вираз f, якщо не існує такого набору значень змінних, для якого g набуває значення 1, а f набуває значення 0. Кожний моном, який має наслідком f, називається імплікантом для f. Простим імплікантом називається імплікант, який перестає ним бути після вилучення будь-якого літерала.

Отже, прості імпліканти є найкоротшими серед імплікантоів.

Твердження 1. Нехай f = – ДНФ. Тоді кожний моном f_i є імплікантом для f.

Доведення. Якщо при заданому наборі значень змінних f_i набуває значення 1, то й f набуває значення 1.

Твердження 2. Кожна булева функція f дорівнює сумі всіх своїх простих імплікант.

Доведення. З ДНФ f випливає, що f дорівнює сумі імплікантів, і для кожного набору змінних, для якого f = 1, знайдеться деякий імплікант, який теж дорівнює 1.

Приклад. f(x, y) = xy  x  y  f(x, y) = Мономи xy, x та y не є простими імплікантами. Справді xy  x = x(y  ) = x.

Означення 3. ДНФ g функції f називається ненадлишковою, якщо:

1. кожний моном, який входить в g, є простим імплікантом функції f;

2. після вилучення будь-якого монома з g одержують f g.

Твердження 3. Кожна ДНФ g, яка є мінімальною за літерала й мономами, є ненадлишковою.

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

Щоб знайти ненадлишкове мінімальне зображення булевої функції f, потрібно:

1. знайти множину всіх простих імплікантів функції f;

2. знайти ненадлишкові об’єднання простих імплікантів;

3. вибрати серед цих об’єднань мінімальні.