ДМ_Конспект

Формулы, представляющие одну и ту же функцию, называются

эквивалентными или равносильными.

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

Пример.

Равносильные

функции

(x y) z (x y) z

или

((x x) y) ( y x) x y .

Пример.

x y

Важнейшие примеры равносильных функций: x равносильно x ;

равносильно

y x ; (x y) z

равносильно

x ( y z) ; x y равносильно

y x ;

(x y) z

равносильно

x ( y z) ;

x x равносильно x ;

x x

равносильно x ; x (x y) равносильно x .

Чтобы

выяснить, являются ли данные формулы эквивалентными

(равносильными), существует, по крайней мере, два метода:

стандартный метод (построение таблицы функции);

метод эквивалентных преобразований формул.

6.6 Принцип двойственности

Одним из способов получения тождеств в булевой алгебре является способ, основанный на принципе двойственности.

Определение.

Функция

f * (x , x

, ..., x

)

называется

двойственной

к функции

1

2

n

f (x , x

, ..., x

) , если f

* (x , x , ..., x ) f (x ,

x , ..., x ) .

1 2

n

1

2

n

1

2

n

Для любой функции двойственная ей функция определяется однозначно.

Отношение двойственности симметрично.

Определение.

Функция,

двойственная

сама

себе,

т.е.

f f * ,

называется

самодвойственной.

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

Пример.

а) (x y) z двойственна x y z .

71

б) x y (x y z) двойственна x y (x y z) .

Таблица двойственности функции получается из таблицы для функции f (x1 , x2 , ..., xn ) инвертированием (т.е. заменой 0 на 1 и 1 на 0) значений

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

Пример.

Найдем функцию f * (x, y) , двойственную заданной f (x, y) , при помощи таблицы истинности. Результат представим в табл. 6.5.

Таблица 6.5 Таблица

истинности

f (x, y) и

двойственной функции

f * (x, y)

x

y

f (x, y)

f * (x, y)

0

0

f (0,0) 1

f (1,1) 0

0

1

f (0,1) 0

f (1,0) 0

1

0

f (1,0) 1

1

f (0,1)

1

1

f (1,1) 1

0

f (0,0)

Рассмотрим таблицу истинности самодвойственной функции (табл. 6.6).

Таблица 6.6 Самодвойственная функция, представленная таблицей истинности

x	y	f (x, y) f * (x, y)
0	0
		f (0, 0) f (1, 1)
0	1
		f (0, 1) f (1, 0)
1	0
		f (1, 0) f (0, 1)
1	1
		f (1, 1) f (0, 0)

Определение.

Принцип двойственности указывает правило получения двойственных формул в булевой алгебре: «Для того чтобы получить двойственную формулу булевой алгебры, необходимо заменить в ней все конъюнкции на дизъюнкции, дизъюнкции на конъюнкции, 0 на 1, 1 на 0 и использовать скобки, где необходимо, чтобы порядок выполнения операций остался прежним».

Пример.

Найти функцию, двойственную функции f x y z 0.

Используя правило получения двойственных функций, получим двойственную функцию f * (x y z 0)* x ( y z) 1.

Определение.

72

Если функции равны, то и двойственные им функции также равны, т.е.,

если f1 f2 , то f1* f2* .

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

6.7 Булевы алгебры. Законы и тождества булевой алгебры

Определение.

Алгебраическая структура (B, , , ) , где B {0, 1} и операция есть конъюнкция f1 (x1, x2 ) , есть дизъюнкция f7 (x1, x2 ) (таблица 3.4), « » есть отрицание f2 (x) (таблица 3.2), называется двухэлементной булевой алгеброй.

Определение.
Алгеброй			логики	называется		двухэлементная булева алгебра
(B, , ,		, , ~),	где носитель		алгебры	B {0, 1}, и в которой множество
операций		дополнено		двумя	бинарными операциями: импликацией

( f13(x1, x2 )) и эквивалентностью ~ ( f9 (x1, x2 )) (см. таблицу 3.4).

На основе определения основных операций (отрицание, дизъюнкция, конъюнкция) нетрудно убедиться в справедливости следующих законов (свойств) булевой алгебры.

Рассмотрим основные законы (свойства) булевой алгебры.

Закон коммутативности (переместительный закон) x1 x2 x2 x1 ;

x1 x2 x2 x1 .

Пример.

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

Таблица 6.7 Таблица истинности для доказательства коммутативности

операции дизъюнкции
	x1	x2	x1 x2	x2 x1
	0	0	0	0
	0	1	1	1
	1	0	1	1
1		1	1	1

Столбцы x1 x2 и x2 x1 в таблицах истинности содержат одинаковые

значения, что доказывает коммутативность операции дизъюнкции.

Найдем тождество, двойственное данному тождеству, для чего заменим все функции на двойственные им (x1 x2 )* (x2 x1 )* , x1 x2 x2 x1 .

73

Закон ассоциативности (сочетательный закон) x1 (x2 x3 ) (x1 x2 ) x3 ;

x1 (x2 x3 ) (x1 x2 ) x3 .

Пример.

Доказать ассоциативность операции конъюнкции можно, используя таблицы истинности (табл. 6.8).

Таблица 6.8 Таблица истинности для доказательства ассоциативности операции конъюнкции

x1	x2	x3	x2 x3	x1 (x2 x3 )	(x1 x2 )	(x1 x2 ) x3
0	0	0	0	0	0	0
0	0	1	0	0	0	0
0	1	0	0	0	0	0
0	1	1	1	0	0	0
1	0	0	0	0	0	0
1	0	1	0	0	0	0
1	1	0	0	0	1	0
1	1	1	1	1	1	1

Столбцы, соответствующие левой и правой частям второго равенства, содержат одинаковые значения, что доказывает справедливость тождества x1 (x2 x3 ) (x1 x2 ) x3 .

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

Закон дистрибутивности (распределительный закон) x1 (x2 x3 ) (x1 x2 ) (x1 x3 ) ;

x1 (x2 x3 ) (x1 x2 ) (x1 x3 ) .

Пример.

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

Таблица 6.9 Дистрибутивность конъюнкции относительно дизъюнкции

x	x	2	x	3	x	2	x	x (x		2	x )	(x x	2	)	(x1 x3 )	(x x	2	) (x x )
1							3	1			3	1				1		1	3
0	0		0				0		0			0			0			0
0	0		1				1		0			0			0			0
0	1		0				1		0			0			0			0
0	1		1				1		0			0			0			0
1	0		0				0		0			0			0			0
1	0		1				1		1			0			1			1
1	1		0				1		1			1			0			1
1	1		1				1		1			1			1			1

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

74

x1 (x2	x3 ) (x1 x2 ) (x1 x3 ) . Двойственное тождество выражает
дистрибутивность дизъюнкции относительно конъюнкции.
Закон идемпотентности
x1	x1	x1;
x1	x1	x1.

Пример.

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

Таблица 6.10 Закон идемпотентности

x1	x1 x1	x1 x1
0	0	0
1	1	1

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

двойственными друг другу.

Закон исключенного третьего

x1 x1 1.

Пример.

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

Таблица 6.11 Закон исключенного третьего

x1					x
		x		x
		1		1	1
0		1			1
1		0			1

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

Закон противоречия

x1 x1 0 .

Пример.

Для доказательства закона противоречия используем таблицу истинности

(табл. 6.12).

Таблица 6.12 Закон противоречия

x1					x
		x		x
		1		1	1
0		1			0
1		0			0

Данный закон является двойственным к доказанному выше закону исключенного третьего.

75

Закон тождества (свойство констант) x1 0 x1; x1 1 1;

x1 1 x1 ; x1 0 0 .

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

Таблица 6.13 Таблицы истинности тождеств

x1	x1 0	x1 1	x1 1	x1 0
0	0	0	1	0
1	1	1	1	0

Закон поглощения (элиминации) x1 (x1 x2 ) x1 ;

x1 (x1 x2 ) x1 .

Пример.

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

x1 (x1 x2 ) (x1 0) (x1 x2 ) x1 (0 x2 ) x1 0 x1 ; x1 (x1 x2 ) (x1 1) (x1 x2 ) x1 (1 x2 ) x1 1 x1 .

Закон инволюции (двойного отрицания)

x1 x1 .

Пример.

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

Таблица 6.14 Закон двойного отрицания

x1		x
					x
		1
				1
0		1		0
1		0		1

Законы де Моргана x1 x2 x1 x2 ;

x1 x2 x1 x2 .

Пример.

Для доказательства закона де Моргана используем таблицу истинности

(табл. 6.15).

Таблица 6.15 Доказательство закона де Моргана

		x1 x2
x1	x2			x x	2			x			x	2			x1 x2
				1			1
0	0	0		1			1			1				1
0	1	1		0			1			0				0
						76

1	0	1	0	0	1	0
1	1	1	0	0	0	0

Второй закон де Моргана является двойственным первому и, значит, также является верным.

6.8 Контрольные вопросы и задания

1.Какие переменные называются булевыми или логическими переменными?

2.Какая функция называется логической (булевой, переключательной)?

3.Приведите примеры задания (использования) булевых переменных в языках программирования.

4.Как называется совокупность конкретных значений аргументов булевой функции?

5.Сколько элементов-слов содержит n -мерный булевый куб?

6.Что представляет собой область определения и область значений булевой функции?

7.Какая булева функция называется полностью определенной?

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

9.Перечислите способы задания булевых функций.

10.Что представляет собой таблица истинности (соответствия) булевой функции. Назовите правила еѐ построения.

11.Перечислите булевы функции от одной переменной.

12.Приведите примеры элементарных функций двух переменных.

13.Перечислите основные булевы функции от двух переменных.

14.Каким образом определяется номер булевой функции? Номер интерпретации?

15.Дайте определение формулы для задания булевой функции. Что такое суперпозиция булевых функций?

16.Какие знаки используются при образовании (построении) формул? Какой приоритет определен для операций алгебры логики?

17.Какая запись формул называется инфиксной? Приведите примеры.

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

19.Какие формулы называются равносильными или эквивалентными?

20.Перечислите основные методы определения равносильности формул.

21.Дайте определение двойственной функции.

22.Дайте определение самодвойственной функции.

23.Каким образом формируется таблица истинности двойственной

функции?

24.Сформулируйте принцип двойственности булевых функций.

77

25.Дайте определения двухэлементной булевой алгебры и алгебры

логики.

26.Перечислите основные законы булевой алгебры.

27.Каким способом можно доказать законы булевой алгебры.

28.Сформулируйте и запишите тождества для законов булевой алгебры.

ЛЕКЦИЯ 7. НОРМАЛЬНЫЕ ФОРМЫ БУЛЕВЫХ ФУНКЦИЙ

7.1 Нормальные формы булевых функций, основные понятия

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

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

(«или»), («не»).

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

Определение.

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

Пример.

Элементарными конъюнкциями для функции от одной переменной могут быть y , z ; для функции от двух переменных x y , x z ; для функции от трех переменных x y z , x z y , x y z и т.д.

Определение.

Дизъюнктивной нормальной формой (ДНФ) называется формула,

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

Пример.

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

формой. ДНФ функции f (x, y, z) может иметь вид f (x, y, z) x y z x z .

Определение.

Члены дизъюнктивной нормальной формы, представляющие собой элементарные конъюнкции k букв, называются минтермами k -го ранга.

Пример.

78

Элементарная конъюнкция xy является минтермом второго ранга; xy z минтермом третьего ранга; xy zt минтермом четвертого ранга и т.п.

Определение.

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

Пример. Конституента единицы обращается в единицу только при одном соответствующем ей наборе значений переменных, который получается, если все переменные принять равными единице, а их отрицания нулю, например, конституенте единицы xy zt соответствует набор (0101), а конституенте

единицы xy z набор (110).

7.2 Совершенные нормальные формы булевых функций

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

совершенной

нормальной

формой

функции

f .

Она

имеет

регламентированную логическую структуру и однозначно определяется по функции.

Определение.

Совершенной дизъюнктивной нормальной формой (СДНФ) функции f (x1, x2 ,...,xn ) , содержащей n различных переменных, называется

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

в) никакое слагаемое не содержит переменной вместе с еѐ отрицанием; г) в каждом слагаемом содержится в качестве множителя либо

переменная xi , либо еѐ отрицание, где i 1, 2, ..., n .

Условия а), б), в), г) являются необходимыми и достаточными для того, чтобы ДНФ была СДНФ.

Определение.

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

В каждом члене СДНФ представлены все переменные (либо в прямом, либо в инверсном виде).

Всякая булева функция f (x1 , x2 , ..., xn ) , которая не является тождественным нулем, имеет:

несколько ДНФ;

одну и только одну СДНФ (количество еѐ членов равно количеству единичных значений функции).

Определение.

79

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

Пример.

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

Определение.

Конъюнктивной нормальной формой (КНФ) называется формула,

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

Пример.

Конъюнктивная нормальная форма функции f (x, y, z) может иметь вид f (x, y, z) (x y z) (x z) .

Определение.

Члены конъюнктивной нормальной формы, представляющие собой элементарные конъюнкции k букв, называются макстермами k -го ранга.

Пример. Элементарная дизъюнкция			x y является макстермом второго
ранга; x y z макстермом третьего			ранга; x y z t макстермом

четвертого ранга.

Определение.

Конституентой нуля (макстермом n -го ранга) называют булеву функцию n аргументов, которая принимает значение, равное 0, только на одной интерпретации (наборе).

Пример.

Конституента нуля обращается в ноль только при одном соответствующем ей наборе значений переменных, который получается, если все переменные принять равными нулю, а их отрицания единице, например, конституенте нуля xy zt соответствует набор (1010), конституенте нуля xy z

набор (001), конституенте нуля xz набор (01).

Пример.

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

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

Номер		Интерпретация				Конституента						Конституента
интерпретации	x		y		z	единицы						нуля
0	0		0		0							x y z
							x y z
1	0		0		1
							x yz					x y z
2	0		1		0
							xy z					x y z
		80