Булевы функции и их форма

 

     Найдем  выражение для  и . Для упрощения записей обозначим , , соответственно через , , , а и - через и .

     Тогда  

      , . 

     Упростим  данные выражения 

       

       

     Таким образом 

     

       

     Отсюда  получаем схему одноразрядного двоичного  сумматора

 

       

     Задание к лабораторной работе №4 

     I. Составить контактные и логические  схемы для функций 

     1)

     2)

     3)

     4)

     5)

     6)

     7)

     8)

     9)

     10)  

 

     II. Упростить схемы 

     1)

       

     2)

       

     3)

       

     4)

       

     5)

     

 

     6)

       

     7)

       

     8)

       

     9)

       

     10)

     

 

     III. 1) Нужно, чтобы включение света  в комнате осуществлялось с  помощью трех различных переключателей  так, чтобы нажатие на любой  из них приводило к включению  света, если он перед этим  был включен, и к его выключению, если он включен. Постройте  простую цепь удовлетворяющую  этому условию.

     2) Пусть каждый из пяти членов  комитета голосует «за», нажимая  кнопку. Постройте простейшую цепь, через которую ток проходил  бы тогда и только тогда,  когда большинство членов комитета  голосует «за».

     3) Пусть каждый из пяти членов  комитета голосует «за», нажимая  кнопку. Постройте простейшую цепь, через которую ток проходил  бы тогда и только тогда,  когда большинство членов комитета  голосует «за», но только при  том дополнительном условии, что  за него голосует председатель  комитета.

     4) Построить контактные и логические  схемы, реализующие функции от  четырех аргументов, которая равна  I тогда и только тогда, когда  число аргументов, принимающих значение I, более трех или не более  одного.

     5) Построить контактные и логические  схемы, реализующие функцию от  трех аргументов, которая равна  I тогда и только тогда, когда  один или два аргумента равна  I.

     6) Построить контактные и логические  схемы, реализующие функцию от  трех переменных, которая равна  I тогда и только тогда, когда  один из аргументов принимает  значение I.

     7) Составьте электронную схему  дешифратора, переводящую двоичный  код в десятичные цифры.

     8) Составить схему-шифратор, переводящую  десятичные цифры в соответствующие  двоичные коды. 

     Контрольные вопросы 

     

1. Контактные  схемы.
2. Логические схемы.
3. Задача анализа и синтеза контактных схем.

 

 

     Лабораторная  работа №5. Полнота и замкнутость 

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

     Например, следующие системы  

      , , являются полными. 

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

     Всякая  система  булевых функций порождает некоторый замкнутый класс. Этот класс состоит из всех булевых функций, которые можно получить суперпозициями из . Такой класс называется замыканием и обозначается . Для замкнутого класса следует, что . Очевидно, что если - полная система, то .

     Рассмотрим  следующие классы булевых функций.

      - класс булевых функций, сохраняющих  константу 0, т.е. функций  , для которых .

      - класс булевых функций, сохраняющих  константу 1, т.е. функций  , для которых .

     Булева  функция  называется двойственной к функции , если  

      .

 

     Булева  функция  называется самодвойственной, если она совпадает с двойственной, т.е. .

      - класс всех самодвойственных  функций.

     Булевы  функции вида , где , равны нулю или единице, называются линейными.

      - класс всех линейных булевых  функций.

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

     Два набора и называются сравнимыми, если , .

     Запись  означает, что набор предшествует набору .

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

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

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

 

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

     Пример 1. Выяснить, является ли функция линейной.

     Найдем  полином Жегалкина для данной функции. 

      ,  

     

     

       

     Следовательно, данная функция линейна.

     Пример 2. Какие из указанных функций являются монотонными: 

     а)   б)  

     а) Упростим формулу  

      .

 

     Эта функция равна нулю на наборах (0,0,0), (0,1,0), (1,0,0). Все оставшиеся наборы, исключая (0,0,1) содержат не менее двух единиц, а значит, они могут быть только больше. Набор (0,0,1) (0,0,0), а с остальными двумя он несравним. Значит, рассматриваемая функция монотонна.

     б) Функция немонотонна, т.к. (0,0) (1,0), но .

     Пример 3. Является ли функция самодвойственной?

     Найдем  двойственную функцию к данной 

       

     Следовательно, данная функция самодвойственная.

     Пример 4. Выяснить, являются ли данные системы булевых функций полными 

     а)  б)  в)  

     а) . Ясно, что , . Так как , то . Найдем полином Жегалкина для . Следовательно, . Так как (0,0) (1,1), но , то .  

     Таблица Поста для системы  имеет вид.

 

     Итак, - полная система. 

     б)

 

     Функция самодвойственна, так как 

       

     Функция немонотонная, так как (0,0,1) (0,1,1), но 1=0+0+1>0+1+1=0.

     Система - полная система. 

     в)

 

     Функция самодвойственная, так как  

     

     Итак, система  целиком принадлежит классу . Следовательно, по теореме о полноте не является полной системой.

 

     Задания к лабораторной работе №5 

     I. Какие из указанных систем функций являются замкнутыми классами?

     1) Линейная функция;

     2) самодвойственные функции;

     3) монотонные функции;

     4) монотонно убывающие функции;

     5) функции, сохраняющие нуль;

     6) функции, сохраняющие единицу;

     7) функции, сохраняющие и нуль, и  единицу;

     8) функции, сохраняющие нуль, но  не сохраняющие единицу;

     9) функции от одной переменной;

     10) функции от двух переменных.

     II. Являются ли следующие функции  линейными? 

     1)

     2)  

     3)

     4)

     5)

     6)

     7)

     8)