Лекции по "Развитию операционных систем"

Лекция 5.

 

п.5.  Булевы функции.

 

5.2.  Существенная и фиктивная переменная.

 

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

Определение 5.2.  Функция из P2 зависит существенно от аргумента xi, если существуют такие значения a1, …, ai-1, ai+1 ,…, an переменных x1, …, xi-1, xi+1, …, xn, что

.

В этом случае переменная xi называется существенной, в противном случае называется несущественной (фиктивной) переменной.

 

Пример 5.1.  Пусть булевы функции f1(x1, x2) и f2(x1, x2) заданы таблицей истинности:

.

Для этих функций переменная x1 – существенная, а переменная x2 – фиктивная.

,

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

Определение 5.3.  Функции f1 и f2 называются равными, если функцию f2 можно получить из f1 путем введения и (или) удаления фиктивных переменных.

 

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

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

п.6.  Реализация функций формулами.

 

6.1.  Формулы. Реализация функций формулами.

 

Как известно, в математическом анализе из «элементарных» функций можно составить формулы. Так и из «элементарных» булевых функций можно строить формулы.

Пусть X – некоторый фиксированный алфавит переменных, s={ } - множество функциональных символов (базис) и F - множество булевых функций, соответствующих функциональным символам s, т.е. являющиеся подмножеством множества функций P2.

Определение 6.1.  Формулой над s называется всякое (и только такое) выражение вида:

1)  x – любая переменная из множества X;

2)  , где A, B – это формулы над s.

 

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

 

Пример 6.1.  Пусть F - множество «элементарных» функций.

1)  ;

2)  ;

3)  .

Выражения являются формулами над s, а выражение формулой не является.

,

Для формул над множеством функциональных символов (логических связок) s принимаются некоторые соглашения:

1) внешние скобки у  формул опускаются;

2) формула (AÙB) записывается в виде (A×B) или (AB);

3) считается, что связка Ø сильнее любой двуместной связки из множества s;

4) связка Ù считается сильнее, чем любая другая двуместная связка из множества s.

 

Сопоставим теперь каждой формуле G некоторую функцию fG. Понятие булевой функции fG, реализуемой формулой G, вводится рекурсивно следующим образом:

1)  Формуле G=x, где xÎX, сопоставляется функция ;

2)  если G равна одной из формул , где A, B – это формулы над s, то fG равно соответствующей элементарной булевой функции . Если , то значение ее на произвольном наборе , совпадает со значением на этом наборе для соответствующей ей элементарной булевой функции.

Таким образом, зная таблицы истинности элементарных функций (функций базиса), можно вычислить и таблицу истинности функции fG, которую реализует формула G.

Пример 6.2.  Пусть f (x1, x2) – функция, которой соответствует формула .

Эта формула состоит из трех подформул: , , . В таблице истинности приводятся соответствующие им функции.

.

Последний столбец определяет функцию f (x1, x2). Очевидно, что f (x1, x2)=x1Úx2.

,

 

6.2.  Эквивалентность формул.

 

Поскольку функция рассматривается с точностью до фиктивных переменных, мы считаем, что формула A реализует и любую функцию, равную f. Если функция , реализуемая формулой , имеет несущественную переменную xi, то при n>1 переменную xi можно удалить, заменив функцию f равной ей функцией , а формулу A – формулой , получающейся из A в результате отождествления переменной xi с любой из оставшихся переменных. Очевидно, что является формулой над s и реализует функцию .

Определение 6.2.  Формулы G1 и G2 над s называются эквивалентными, если они реализуют равные булевы функции и .

 

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

1.  - коммутативность связки o, где o - общее обозначение для связок Ù, Ú, Å, «, ½, ¯.

2.  - ассоциативность связки o, где o - общее обозначение для связок Ù, Ú, Å, «.

3.  а)  - дистрибутивность конъюнкции относительно дизъюнкции;

   б)  - дистрибутивность дизъюнкции относительно конъюнкции;

   в)  - дистрибутивность конъюнкции относительно сложения по mod 2.

4.  правила де Моргана:

   а)  ;              б)  .

5.  правила поглощения:

   а)  ;           б)  .

6.  а)  ;

   б)  ;

   в)  ;

   г)  ;

   д)  .

7.  а)  ;

   б)  ;

   в)  .

8.  а)  ;      б)  .

 

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

 

Очевидно, что если A¢ – подформула формулы A и если заменить любое из ее вхождений на эквивалентную формулу B¢, то формула A перейдет в формулу B, которая будет эквивалентная A.

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

Пример 6.3.  Используя основные тождества, установить эквивалентность формул

 и

.

Решение.  =(Раскрытие стрелки Пирса, импликации, штриха Шеффера)=

=

=

=(использование  двойного отрицания, законы де  Моргана, раскрытие эквиваленции  и убираем лишние скобки)=

=

=

=

=

=

=

=(используем правила  поглощения)=

=

=(используем правила поглощения)=

=

.

Преобразуем формулу B, используя соответствующие эквивалентности:

=

=( раскрытие стрелки Пирса, импликации)=

=

=

=(законы де Моргана, раскрытие  стрелки Пирса, двойное отрицание)=

=

=

=(используем правила поглощения)=

=

.

Тем самым доказываем эквивалентность формул A и B.

,

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

Пример 6.4.  Некий любитель приключений отправился в кругосветное путешествие на яхте, оснащенной бортовым компьютером. Его предупредили, что чаще всего выходят из строя три узла компьютера – a, b, c, и дали необходимые детали для замены. Выяснить, какой именно узел надо заменить, он может по сигнальным лампочкам на контрольной панели. Лампочек тоже ровно три: x, y и z.

Инструкция по выявлению неисправных узлов такова:

   1.  если неисправен хотя  бы один из узлов компьютера, то горит, по крайней мере, одна  из лампочек x, y, z;

   2.  если неисправен узел a, но исправен узел с, то загорится лампочка y;

   3.  если неисправен узел с, но исправен узел b, загорается лампочка y, но не загорается лампочка x;

   4.  если неисправен узел b, но исправен узел с, то загораются лампочки x и y, или не загорается лампочка x;

   5.  если горит лампочка x и при этом неисправен узел а, либо все три узла a, b, c исправны, то горит и лампочка y.

В пути компьютер сломался. На контрольной панели загорелась лампочка x. Тщательно изучив инструкцию, путешественник починил компьютер. Какие узлы заменил путешественник?

Решение.  Введем логические переменные, которые будут определять простые высказывания:

a – узел a исправный;             – узел a не исправный;

b – узел b исправный; ;           – узел b не исправный;

c – узел c исправный. ;           – узел c не исправный.

 

x – загорелась лампочка x;        – не загорелась лампочка x;

y – загорелась лампочка y;        – не загорелась лампочка y;

z – загорелась лампочка z;        – не загорелась лампочка z;

 

Используя условие задачи, составляем формулу, которая реализует следующую функцию:

.

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

 

=

=

=

=(правила поглощения)=

=

.

Из последнего равенства можно сделать вывод: узел a исправный, b – нет и c – нет.

,

 

6.3.  Переключательные схемы.

 

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

Определение 6.3. Переключательная схема – это схематическое изображение некоторого устройства, состоящего из переключателей и соединяющих их проводников, а также из входов и выходов, на которые подается и с которых принимается электрический сигнал.

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

 

 

 

 

Каждый переключатель имеет только два состояния: замкнутое и разомкнутое. Будем считать, что два переключателя и связаны таким образом, что когда замкнут, то разомкнут и наоборот.

Сопоставим переключателю переменную , которая принимает значение 1 в случае, когда переключатель замкнут, и значение 0 в случае, когда переключатель разомкнут. Переключателю соответствует переменная , которая принимает значение 1 в случае, когда переключатель замкнут, и значение 0 в обратном случае. Тогда сеть на рис. 1 пропускает ток, если и , то есть, если функция . Сеть на рис. 2 пропускает ток, если или , то есть, если функция .

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

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

Пример 6.5. По данной функции проводимости

построить переключательную схему с помощью трёх переключателей , , . Определить, при каких положениях переключателей ток в сети отсутствует.

Решение. Формуле соответствует переключательная схема вида:

 

 

 

 

 

 

Формуле соответствует переключательная схема:

 

 

 

 

 

 

Из рисунков следует, что данной функции соответствует схема

 

 

 

 

 

 

 

 

 

 

 

 

 

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