Полная версия

Главная arrow Математика, химия, физика arrow Дискретная математика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

Функционально полные системы логических функций

Рассмотрим понятия полноты, или функциональной полноты, для системы логических функций.

Возьмем системы булевых функций F= {fx,f2, Система

функций /"называется полной, если любая логическая функция может быть представлена как суперпозиция системы функций F.

Рассмотрим примеры полных систем.

7n

Очевидно, что система Р2 = {f,f2, / т = 2 }, содержащая

все jV-мерные булевы функции, полна.

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

Для определения, является ли исследуемая система полной, может быть использовано два подхода. Один из них основывается на теореме о полноте, а второй — на критерии Поста—Яблонского [1—3].

Теорема 3.4. Теорема о полноте

Если даны две системы логических функций Fx и F2, и Fx полна, то система F2 полна тогда и только тогда, когда каждая функция системы Fx представима через функции F2.

Данная теорема дает возможность доказать полноту следующих систем булевых функций.

1. Штрих Шеффера {|}.

Выведем представление полной системы функций алгебры Буля { л, ->) через штрих Шеффера. Для этого воспользуемся дизъюнктивной формой а | Ь = а + Ь:

а = а+ а= аа

а + Ь = а | Ь = (а а) (Ь Ь);

а ? Ь = а + Ь = (а Ь) = (а Ь) (а Ь).

2. Элемент Вебба {°}.

Представим функции алгебры Буля через элемент Вебба с учетом его ДНФ:

а о Ь = а ? Ь а = а а = а° а; а ? Ь = а о Ь - {а о а) о (Ь о Ь)

а + Ь = а ? Ь = (а ° Ь) = (а ° Ь) ° (а ° Ь).

3. Импликативная система {—>,0}.

Представим функции алгебры Буля через импликативную систему с учетом ДНФ импликации:

а —» Ь = а + Ь; а=а + 0 = а—>0; й + 6 = й—>6 = (я—> 0)—>6;

а ? Ь = а + Ъ - (а —> 6) = —>(/>—> 0)) —> 0.

4. Алгебра Жегалкина {©, 1, •}.

Выведем представление полной системы функций — алгебры Буля — через алгебру Жегалкина. Для этого воспользуемся дизъюнктивной формой:

а®Ь = а- Ь+ а-Ь а = 0 + а = 0 - а + - а = я©1;

а + Ь - а ? Ь = ((а © 1) • © 1)) © 1.

Неудобство использования теоремы о полноте заключается в том, что мы никак не можем интерпретировать отрицательный результат. Если мы не смогли найти выражение функций через 7^, то в чем причина: в нашем неумении или принципиальной невозможности таких действий?

Более конструктивным является критерий Поста—Яблонского. Применение этого подхода к исследованию системы функций на полноту требует введения пяти замкнутых классов функций К0, Аф 5, Л/ и Ь. Замкнутым каждый класс называется потому, что любая суперпозиция (подстановка) функций данного класса дает новую функцию, которая также принадлежит этому классу.

Классом К0 (сохраняющих константу 0) булевых функций/^хх2, ..., х„) называется множество функций, для которых выполняется условие, что при нулевых значениях переменных функции принимают значение 0:

/<0,0,...,0) = 0.

К классу К0 принадлежат такие функции, как константа 0, логическое сложение а + Ь, логическое умножение аЬ, сложение Жегал-кина а © Ь, функции сохранения первой а и второй Ь переменных.

Классом К (сохраняющих константу 1) булевых функций/{{, х2, ..., хп) называется множество функций, для которых выполняется условие, что при единичных значениях переменных функции принимают значение 1:

№, 1,..., 1) = 1.

К классу К] принадлежат такие функции, как константа 1, логическое сложение а + Ь, логическое умножение аЬ, эквивалентность а <=> Ь, функции сохранения первой а и второй Ь переменных.

Классом 8 (самодвойственных) булевых функций/,{х{, х2, ..., хп) называется множество функций, для которых выполняется условие, что/* = У-, т.е. на всех противоположных наборах значения функции противоположны:

_/;(*,,х2, ...,хп) = /1х2, ...,хп).

К классу 5 принадлежат такие функции, как отрицание а, функции сохранения первой а и второй Ь переменных.

Классом М (монотонных) булевых функций/,(хь х2, ..., хп) называется множество функций, для которых выполняется условие, что на всех наборах 0| и а2 при а( > а2 значение функции/(<Д|) >/(а2).

Основная сложность при исследовании данного свойства состоит

в сравнении наборов. Не все наборы а, = (а], о2, ..., о|() и ст2 = (<*1% С72, сравнимы, а только те, у которых о) > а,2, / = 1, п. Например, наборы 100 и 000 сравнимы: 100 > 000, а 010 и 001 — нет.

К классу М принадлежат такие функции, как константы 0 и 1, логическое сложение а + Ь, логическое умножение аЬ, функции сохранения первой а и второй Ь переменных.

Классом Ь (линейных) булевых функций/(хь х2,..., хп) называется множество функций, которые представимы полиномом Жегалкина первой степени:

Х2, ..., Х„) = С0 © С{ © с22 © ... © спп.

К классу Ь принадлежат такие функции, как константы 0 и 1, эквивалентность а ~ Ь, сложение Жегалкина а © Ь, отрицание, функции сохранения первой а и второй Ь переменных.

Теорема 3.5. Критерий Поста—Яблонского

Для того чтобы система логических функций Б была функционально полна, необходимо и достаточно, чтобы она по совокупности не содержалась ни в одном из замкнутых классов К{), Кх, 5, Ми Ь.

Базисом или базисным набором логических функций называется такая полная система функций В, что удаление из В хотя бы одной логической функции нарушает свойство полноты В.

Как очевидно из данного определения, любой базис является полной системой, но не каждая полная система образует базис. Например, привычный набор функций алгебры Буля {+, •, -}, обладающий функциональной полнотой, не является базисом в строгом смысле этого слова, так как из него может быть получено два новых базиса: конъюнктивный {•, -} и дизъюнктивный{+, -}.

Для доказательства построим таблицу принадлежности классов (табл. 3.14).

Таблица 3.14

Таблица Яблонского

Классы

*0

К

5

м

Н

+

+

+

{+}

+

+

+

{-}

+

+

К +»-}

Рассмотрим несколько примеров.

Задача 3.10. С помощью критерия Поста—Яблонского исследовать систему {-, •, 0} на полноту.

Решение.

Построим таблицу истинности предложенных функций и по ней проведем исследование (табл. 3.15).

Таблица 3.15

Таблица истинности для задачи 3.10

а

ь

а~Ь

аЬ

0

0

0

і

0

0

0

1

0

0

0

1

0

0

0

0

1

1

1

1

0

Из таблицы истинности очевидно, что {•, 0} с К0 и {-} <х К0, а{-,~}сА:| и{0}ссА:1.

Все три функции из системы {-, •, 0} не являются самодвойственными, так как для них можно указать нарушение этого свойства. Например 0 ~ 0 = 1, а на противоположном наборе 1-1 = 1 функция имеет то же значение. Для функции {•} противоположные наборы 01 и 10 дают одинаковые значения. Для константы 0 обе пары противоположных наборов дают одинаковые значения.

Свойство монотонности соблюдается для функций {•, 0}, но не для {-}, так как наборы 00 и 01 связаны соотношением 00 < 01, но ~(0, 0) > ~(0, 1).

Проверим линейность исследуемых функций.

Предположим, что 0(а, Ь) линейна, тогда она должна быть представима в виде

0(я, Ь) = с0 © с] ? а © с2 ? Ь.

Найдем неизвестные коэффициенты разложения, зная таблицу истинности функции:

  • 0(0, 0) = с0 0 с, • 0 0 с2 • 0 = с0 = 0;
  • 0(0, 1) = с0 © сх • 0 © с2 • 1 = с0 © с2 = 0 © с2 = с2 = 0;
  • 0( 1, 0) = с0 © с{ • 1 © с2 • 0 = с0 © с, = 0 © с, = С| = 0.

Проверим правильность найденных коэффициентов: 0(1, 1) = = с0 © с, • 1 © с2 • 1 = 0 © 0 © 0 = 0, что совпадает со значением в таблице истинности. Наше предположение о линейности функции {0} подтвердилось.

Следовательно, функция {0} с I.

Продолжим исследование. Предположим:

~(а, Ь) = с0® с, ? а® с2- Ь

~(0, 0) = с0 © С • 0 0 с2 • 0 = Со © 0 © 0 = Со = 11 ~(0, 1) = Со © С| • 0 © с2 ? 1 = 1 © 0 © с2 = 1 © с2 = 0, следовательно, с2= 1;

~(1, 0) = Со © С| • 1 © с2 ? 0 = 1 © 0 © С| = 1 © С| = О, следовательно, с1 = 1.

Проверим правильность найденных коэффициентов:

~(1, 1) = с0Фс1- 1 © с2 • 1 = 1 Ф 1 Ф 1 = 1,

что совпадает со значением в таблице истинности. Наше предположение о линейности {-} подтвердилось.

Следовательно, функция {-} с Рассмотрим функцию {•}. Предположим, что:

  • ? (а, Ь) = с0 ® с| • а © с2 • Ь
  • • (0, 0) = с0 © С! • 0 © с2 • 0 = с0 © 0 © 0 = с0 = 0;
  • • (0, 1) = с0 © с, • 0 © с2 • 1 = 0 © 0 © с2 = 0 © с2 = 0, следовательно, с2 = 0;
  • • (1,0) = с0 © с, • 1 © с2 • 0 = 0 © 0 © с, = 0 © с, = 0, следовательно, = 0.

Проверим правильность найденных коэффициентов:

~(1, 1) = Со©С| - 0©с2-0 = 0©0©0 = 0,

что не совпадает со значением в таблице истинности. Наше предположение о линейности {•} не подтвердилось. Следовательно, функция

Построим таблицу принадлежности классам А^0, К{, М и Ь (табл. 3.16).

Таблица 3.16

Таблица Яблонского для задачи 3.10

Классы

*0

?

М

I

0

+

+

+

+

+

+

+

+

Ь •, 0}

В соответствии с критерием Поста—Яблонского система {-, •, 0} не содержится целиком ни в одном из пяти классов К0, К, Ми I, следовательно, она полна.

Задача 3.11. С помощью критерия Поста—Яблонского исследовать систему {—», ©} на полноту.

Решение.

Построим таблицу принадлежности рассматриваемых функций {—>, ©} классам К0, Аф 5, Ми I (табл. 3.17).

Таблица 3.17

Таблица Яблонского для задачи 3.11

Классы

*0

К

м

L

—>

+

©

+

+

{^,©1

В соответствии с критерием Поста—Яблонского система {—>, ©} не содержится целиком ни в одном из пяти классов К0, Кх, М и Ь, следовательно, она полна.

Задача 3.12. С помощью критерия Поста—Яблонского исследовать систему {—>, 1} на полноту.

Решение.

Построим таблицу принадлежности рассматриваемых функций {—», 1} классам К0, 5, М и А (табл. 3.18).

Таблица 3.18

Таблица Яблонского для задачи 3.12

Классы

*0

М

L

—>

+

1

+

+

+

{—?S В-

+

В соответствии с критерием Поста—Яблонского система {—>, 1} содержится целиком в классе К], следовательно, она не полна.

Рассмотрим несколько задач на синтез логических функций с заданными свойствами. Обратите внимание, что каждая задача в рассматриваемых случаях имеет более чем одно правильное решение!

Задача 3.13. Задать самодвойственную логическую функцию от трех переменных F(x, у, z)-

Решение.

Задать логическую функцию означает построить ее таблицу истинности.

При построении воспользуемся определением, что на противоположных наборах самодвойственная функция имеет противоположное значения (табл. 3.19).

Таблица 3. 19

Таблица истинности самодвойственной логической функции

х у z

р(х, у, z)

0 0 0

1

0 0 1

0

0 1 0

0

0 1 1

0

1 0 0

1

1 0 1

1

1 1 0

1

1 1 1

0

Зададим функцию на наборе 000, например, равной 1. Тогда на противоположном наборе 111 она должна иметь значение 0.

На наборах 001, 010 и 011 зададим функцию как ложную. Тогда на противоположных наборах 110, 101 и 110 функция должна быть истинной.

Обратите внимание, что мы задали только одну самодвойственную функцию из нескольких возможных!

Задача 3.14. Задать монотонную логическую функцию от трех переменных F(x, у, z)-

Решение.

Зададим логическую функцию в виде таблицы истинности. При построении воспользуемся определением, что с увеличением набора значение самой функции не должно уменьшаться (табл. 3.20).

Обратите внимание, что не все наборы из трех переменных сравнимы между собой (рис. 3.1), т.е. между ними задан частичный порядок

Два набора можно сравнивать, только если они обладают соседними двоичными кодами, различающимися только в одном разряде. Например, набор 000 меньше чем 001, 010 или 100. Но наборы 101, 011 и 110 несравнимы между собой.

Зададим функцию на наборах 000, 001 и 010 равной 0, а на наборе 100 равной 1. Тогда на наборах 101, ИОи 111, больших чем 100, она должна иметь также значение 1.

При этом на наборе 011 функция может иметь любое значение, при этом она все равно будет монотонной!

X у Z

F(x, у, z)

0 0 0

0

0 0 1

0

0 1 0

0

0 1 1

0

1 0 0

1

1 0 1

1

1 1 0

1

1 1 1

1

111

011

101

по

-

х

х

t

001

010

100

000

Рис. 3.1. Сравнение между двоичными наборами

Обратите внимание, что мы задали только одну монотонную функцию из нескольких возможных!

Задача 3.15. Задать линейную логическую функцию от трех переменных F(x, у, z)-

Решение.

Зададим логическую функцию в виде таблицы истинности. При построении воспользуемся определением, что для линейной функции должен существовать линейный полином Жегалкина, т.е. должно существовать разложение

F(x, у, z) = С0 © СХХ ® с2у ® C3Z.

Зададим, например, с0 = 1, с, = с2 = 0, с3 = 1.

Тогда, вычисляя значение линейной функции на каждом наборе по этому полиному, получим таблицу истинности (табл. 3.21).

В соответствии с заданными коэффициентами в полиноме Жегалкина наша функция зависит только от переменной г. На тех наборах, где z= 1, функция равна 0. В противном случае, когда z = 0, функция равна 1.

X у Z

F(x, у, z)

0 0 0

1

0 0 1

0

0 1 0

1

0 1 1

0

1 0 0

1

1 0 1

0

1 1 0

1

1 1 1

0

Обратите внимание, что мы задали только одну линейную функцию из множества возможных!

Задача 3.16. Задать полную логическую функцию от трех переменных F(x, у, z).

Решение.

Зададим логическую функцию в виде таблицы истинности. При построении воспользуемся критерием Поста—Яблонского, что эта функция не должна принадлежать ни одному из классов К0, К, S, М и L.

В соответствии с критерием на наборе 000 функция должна быть равна 1, а на наборе 111 равна 0. При этом функция теряет свойство монотонности.

Наша функция не должна быть и самодвойственной, тогда зададим на ее наборах 001 и 110 равной 0.

На остальных четырех наборах зададим функцию таким образом, чтобы для нее не существовал линейный полином Жегалкина. Для этого внесем противоречие в коэффициенты.

По заданным четырем наборам можно утверждать, что, для того чтобы полином существовал, необходимо, чтобы с0 = 1, с3 = 1, а с, не был равен с2.

Положим Cj = с2 = 0 и вычислим функцию на наборах 010, 100, 011 и 101 (табл. 3.22).

Обратите внимание, что мы задали только одну функцию, обладающую функциональной полнотой, из множества возможных!

Задача 3.17. Задать самодвойственную логическую функцию от трех переменных F(x, у, z), сохраняющую 0, но не сохраняющую 1.

X у 1

Т(х, у, 1)

0 0 0

1

0 0 1

0

0 1 0

1

0 1 1

0

1 0 0

1

1 0 1

0

1 1 0

0

1 1 1

0

Решение.

Если функция самодвойственная, то/, 0, 0) ^ /Д1, 1, 1). Но если

функция сохраняет 0 и не сохраняет 1, то Р(0, 0, 0) = 0 и Р(, 1, 1) = 0,

т.е. на этих наборах значения функции равны.

Следовательно, возникает противоречие и логической функции,

удовлетворяющей ограничениям данной задачи, не существует.

 
<<   СОДЕРЖАНИЕ   >>