Дискр. мат._1 ПФ

ДИСКРЕТНАЯ МАТЕМАТИКА Контрольная работа № 2

Переключательные функции. Графы

Для заочников специальности 2204

Часть I. Переключательные функции

Переключательные или логические функции находят широкое применение при разработке современной вычислительной техники и ее применении. Они осуществляют однозначное отображение множества наборов , в которых переменные принимают значения из множества в множество . Чаще всего рассматривают переключательные функции для к=2. Множество в этом случае или просто состоит всего из двух элементов . Такие переключательные функции называют еще булевыми функциями, а переменные, принимающие значения из , — булевыми переменными.

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

Примеры логических функций.

Таблица функций одной переменной

	0 1	Обозначение (формула)	Название
	0 0	0	Константа 0
	0 1		Переменная х
	1 0		Отрицание
	1 1	1	Константа 1

Таблица функций от двух переменных

	0 0	0 1	1 0	1 1	Обозначение	Название
	0	0	0	0	0	Константа 0
	0	0	0	1		Конъюнкция
	0	0	1	0		Отрицание импликации
	0	0	1	1		Переменная х (y – фиктивная переменная)
	0	1	0	0		Отрицание обратной импликации
	0	1	0	1		Переменная y (х – фиктивная переменная)
	0	1	1	0		Сложение по модулю 2 (неравнозначность, исключённое или)
	0	1	1	1		Дизъюнкция
	1	0	0	0		Стрелка Пирса (отрицание дизъюнкции, конъюнкция отрицаний, функция Даггера)
	1	0	0	1		Эквиваленция (равнозначность)
	1	0	1	0		Отрицание y
	1	0	1	1		Обратная импликация
	1	1	0	0		Отрицание х
	1	1	0	1		Импликация
	1	1	1	0		Штрих Шеффера (дизъюнкция отрицаний, отрицание, конъюнкции)
	1	1	1	1	1	Константа 1

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

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

Пример. Пусть тогда

и т.д. — различные суперпозиции функций и .

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

Пример. Проверить, являются ли равносильными формулы и .

Решение. Составим таблицы истинности для этих формул, совместив их.

				Первая формула		Вторая формула
0 0	0	1	0	1	1	1
0 1	1	1	1	1	0	0
1 0	1	0	0	1	1	1
1 1	1	0	0	1	0	1

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

Аналогично рассмотренному примеру доказывается равносильность следующих формул:

( идемпотентность);

( коммутативность);

( ассоциативность);

( дистрибутивность);

( поглощение);

( действия с константами);

( действия с дополнением);

( инволютивность);

( законы де Моргана),

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

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

( склеивание)

или

( расщепление);

( обобщенное склеивание);

.

Любую булеву функцию можно задать с помощью формулы. Если не является тождественным нулем, то для нее существует единственная формула специального вида, называемая совершенной дизъюнктивной нормальной формой ( СДНФ ), которая строится следующим образом.

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

2. Каждому такому набору сопоставляется так называемая элементарная конъюнкция всех переменных , где

3. Берутся дизъюнкции всех построенных элементарных конъюнкций.

С помощью равносильных преобразований СДНФ можно привести к дизъюнкции элементарных конъюнкций, не обязательно содержащих все переменные. Получим дизъюнктивную нормальную форму ( ДНФ ). Можно построить разные ДНФ для одной и той же функции.

Пример. Для функции построить СДНФ и ДНФ.

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

в двоичной записи.

Для построения СДНФ выбираем те наборы значений переменных , на которых функция принимает значение 1. Таких наборов пять. Каждому из них соответствует конъюнкция, содержащая каждую переменную или её отрицание. Набору (0,0,0) соответствует ; отрицания ставятся над теми переменными, которые в данном наборе равны 0;

(0,1,1)  ;

(1,0,0)  ;

(1,0,1)  ;

(1,1,0) .

Поэтому .

Упростим эту формулу.

Если вторую элементарную конъюнкцию по идемпотентности повторить несколько раз, а затем применить склеивание, то получим другую ДНФ:

Аналогично, если не является тождественной единицей, то для нее существует единственная формула специального вида, называемая совершенной конъюнктивной нормальной формой ( СКНФ ), которая строится следующим образом.

1. Выбираются наборы значений переменных, на которых функция равна 0.

2. Каждому такому набору сопоставляется так называемая элементарная дизъюнкция всех переменных , где

3. Берутся конъюнкции всех построенных элементарных дизъюнкций.

С помощью равносильных преобразований СКНФ можно привести к конъюнкции элементарных дизъюнкций, не обязательно содержащих все переменные. Получим конъюнктивную нормальную форму ( КНФ ). Можно построить разные КНФ для одной и той же функции.

Пример. Для функции построить СКНФ.

Решение. Для построения СКНФ выбираем те наборы значений переменных , на которых функция принимает значение 0. Таких наборов три. Каждому из них соответствует дизъюнкция, содержащая каждую переменную или её отрицание. Набору (0,0,1)  ; отрицание ставится над теми переменными, которые в данном наборе равны 1;

(0,1,0)  ; (1,1,1)  .

Поэтому .

В

контакт разомкнут – переменная х = 0,

контакт замкнут – переменная х = 1.

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

Контакты, обозначенные одинаковыми буквами, замыкаются и размыкаются одновременно; при этом, если контакт замыкается, то контакт размыкается и наоборот.

К онъюнкция двух переменных x и y реализуется с помощью схемы

(последовательное соединение контактов),

а дизъюнкция

(параллельное соединение контактов).

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

Пример. Упростить контактную схему, используя равносильные преобразования.

Решение. Заданная контактная схема реализует булеву функцию

Следовательно, упрощённая схема имеет вид:

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

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

По карте Карно как по таблице истинности можно получить СДНФ и СКНФ. Каждый квадрат с единицей определяет элементарную конъюнкцию, содержащую каждую переменную или её отрицание. Если единицы стоят в соседних квадратах, то конъюнкции отличаются одной переменной, которую можно убрать за счёт склеивания.

Чтобы получить дизъюнктивную нормальную форму (ДНФ) по карте Карно заполненные клетки собирают в прямоугольники, состоящие из квадратов. Каждому такому прямоугольнику соответствует один член дизъюнктивной формы, содержащей только те переменные, которые на этом прямоугольнике не меняются, причем если какая-то переменная равна 0, то она входит в конъюнкцию с отрицанием. Минимальной форме соответствует минимальное число максимально возможных прямоугольников.

Аналогично, объединяя пустые квадраты в прямоугольники, получим члены КНФ, содержащие только те переменные, которые на этом прямоугольнике не меняются, причём если какая-то переменная равна 1, то она входит в дизъюнкцию с отрицанием.

Пример. Минимизировать с помощью карты Карно ДНФ и КНФ для функции .

Р

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

Для данной функции самые большие прямоугольники состоят из 4= квадратов (из 6 уже нельзя). Эти прямоугольники выделим с учётом соседства края таблицы. Таких прямоугольников три. То, что они пересекаются, роли не играет. И есть один прямоугольник, состоящий из двух квадратов, который нельзя увеличить. Поэтому минимальная дизъюнктивная форма для функции имеет вид:

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

Минимальная КНФ имеет вид:

И з рассмотренных примеров видно, что любую булеву функцию можно записать с помощью операций: ‘или’, ‘и’, ‘отрицание’. Но можно использовать и другие логические функции. Наш отечественный математик И.И. Жегалкин предложил использовать для записи произвольных булевых функций константу 1, конъюнкцию и сложение по модулю 2 — , определяемое таблицей истинности: