2Дискретка / Метода / 3. Математическая логика

III. МАТЕМАТИЧЕСКАЯ ЛОГИКА

ГЛАВА 1. ПЕРЕКЛЮЧАТЕЛЬНЫЕ ФУНКЦИИ

1.1. Основные определения

Переключательными (логическими) функциями называют функции, об-

ласть значений которых есть подмножество двухэлементного множества {0,1},

а область определения – {0,1}n , где n – число переменных. Очень часто значе-

ние «0» обозначают как «Л» – «ложь», а значение «1» – как «И» – «истина». Каждая комбинация значений переменных называется набором (набором пере- менных). Множество наборов переменных образует область определения логи- ческой функции. Число всех возможных различающихся наборов значений n переменных переключательной функции f(x1, x2, x3, …, xn) равно 2n (равно чис- лу всех возможных двоичных векторов длины n). Иногда множество наборов переменных интерпретируют как вершины n-мерного куба. Наборы и соответ- ствующие им значения функции составляют таблицу истинности функции, в левой части которой выписаны все возможные наборы значений аргументов функции, а в правой части соответствующие этим наборам значения функций.

Количество различных переключательных функций n аргументов 2(2n ) (Равно числу возможных расстановок нулей и единиц в столбце с 2n строками).

Логическую функцию можно задать двумя способами:

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

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

(эквивалентными).

Пример 20. Рассмотрим три способа задания функции f(a, b, c)

Таблицей истинности:

a b c	f
0 0 0	0	Набором значений
0 0 1	0	(сокращенной таблицей истинности):
0 1 0	0	f(a, b, c)=(00000111)=(0000 0111).
0 1 1	0
1 0 0	0
1 0 1	1	Формулой:
1 1 0	1	f(a, b, c)= a (b c).
1 1 1	1

Примечание: Отметим, что наличие пробела между значениями при таб- личном задании функции (или пустой строки в таблице истинности) сущест- венно облегчает восприятие текста. Поэтому в дальнейшем договоримся отде- лять подчеркиванием в таблице истинности (или пробелом в наборе значений) по 4 строки (значения).

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

Переключательные функции двух аргументов

№	x:	0011	Обозначения								Названия функции
	y:	0101	функции
0		0000	const 0								Константа 0
1		0001	x y, xy								Конъюнкция, функция ‘и’
2		0010	x←y, x								Запрет ‘y’
									y
3		0011	x								Повтор ‘x’
4		0100	x→y,						y		Запрет ‘x’
							x
5		0101	y								Повтор ‘y’
6		0110	x y								Сумма по модулю 2, исключающее ‘или’
7		0111	x y								Дизъюнкция, соединительное ‘или’
8		1000	x↓y								Стрелка Пирса
9		1001	x~y, x y								Эквивалентность
10		1010				, ←y					Отрицание y, функция ‘не’
				y
11		1011	x y, x y								Обратная импликация
12		1100			, ←x						Отрицание x, функция ‘не’
				x
13		1101	x y, x y								Прямая импликация
14		1110	x/y								Штрих Шеффера
15		1111	const 1								Константа 1

Пусть формула F зависит от списка переменных <X1, X2, ..., Xk>.

Формула F называется тавтологией (тождественно-истинной формулой

– ТИФ), если при любых значения переменных списка <X1, X2, ..., Xk> соответ- ствующая ей функция принимает значение 1.

Формула F называется выполнимой (условно-истинной формулой – УИФ),

если при некоторой значениях переменных списка <X1, X2, ..., Xk> соответст- вующая ей функция принимает значение 1.

Формула F называется тождественно-ложной формулой – ТЛФ, если при любых значениях переменных списка <X1, X2, ..., Xk> соответствующая ей функция принимает значение 0.

Формула F называется опровержимой (условно-ложной формулой) , если при некоторых значениях переменных списка <X1, X2, ..., Xk> соответствующая ей функция принимает значение 0.

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

1.Правило подстановки формулы F вместо переменной x: все вхождения переменной x в исходное соотношение должны быть одновременно заменены формулой F.

2.Правило замены подформул: если какая-либо формула F, описывающая функцию f, содержит F1 в качестве подформулы, то замена F1 на эквивалент- ную F2 не изменит функцию f.

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

1.2. Основные теоремы (эквивалентные соотношения) переключательных функций:

1.

a)

x / y

= xy ,

b)

xy

= x / y ,

2.

a)

= x y ,

b)

= x y ,

x y

x y

= x y ,

b)

= x ↓ y ,

3.

a)

x ↓ y

x y

4.

a) y → x = x ← y ,

b) y x = x y ,

5.

a)

= x ← y ,

b)

= x y ,

x y

x ← y

6.

a) x y =

y ,

b)

= x

,

x

x y

y

7.

y x = x y xy ,

8.

x ( y z ) = xy xz ,

9.

x y =

10.

x y = xy

,

11.

x / x =

,

xy x y ,

x

y

x

12. a) x x = 0 ,

b)

x 1 =

,

c)

x 0 = x ,

x

13. a) 1 = 0 ,

b)

0 =1,

c)

x = x .

Старшинство операций (операции даны по убыванию приоритетов)

	¬	/	↓	→					~
				←

ГЛАВА 2. БУЛЕВА АЛГЕБРА

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

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

Наиболее хорошо изученной является система булевых функций { ,,←} .

Формулы, содержащие кроме переменных (и скобок) только знаки функций { ,,←} , называются булевыми.

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

ется булевой алгеброй логических функций.

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

2.1. Основные эквивалентные соотношения в булевой алгебре

Аксиомы отрицания:

1

= 0

0 = 1

x = x

Аксиомы конъюнкции и дизъюнкции

Аксиомы конъюнкции:

Аксиомы дизъюнкции:

x y = y x

x y=y x

коммутативность

x ( y z ) = ( x y) z

x (y z)=(x y)z

ассоциативность

x x = x

x x=x

идемпотентность

x ( y z ) = x y x z

x y z = ( x y) ( x z )

дистрибутивность

x ( x y) = x

x x y = x

поглощение

x 1 = x

x1=1

аксиомы 0 и 1

x 0 = 0

x0=x

=

=

законы де Моргана

x y

x

y

x y

x

y

аксиома «исключенного

аксиома «противоречия»:

третьего»: x

= 1

x

= 0

x

x

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

4Для доказательства этой теоремы достаточно предложить любой способ построения булевой формулы. Пусть логическая функция задана некоторой формулой F (не являющейся булевой), тогда с помощью эквивалентных преоб- разований (используя эквивалентные соотношения 1-13) нужно заменить все логические операции на булевы операции.3

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

Пример 21. Используя эквивалентные преобразования получить булеву фор- мулу для функции f ( x, y, z, p) = y p x / z ← y x y p z .

4 f ( x, y, z, p) = y p x / z ← y x y p z ≡

(

(

))

(

)

(

)

≡

(

y

p

x / z

y

x y

p z

≡

(

)

(

)

)

≡

y

p

( x / z )

y

x y

( p z )

≡(

≡(

x y

(

p z

y

(

x / z

))

(

p

y

)

(

)

(

))

(

)

)

(

y

p

x / z

y

x y

p z

y

(

p z

y

p

(

x / z

))

y

≡

x

)

(

y

x y ( p z ) y ( p z ) )

( p ( xz )) y

x y( p z ) y ( p z ) y ( p ( xz ))

≡

y .

3

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

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

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

Например, x1x3 x2 – элементарное произведение, x1x2 x3 x1 – не является элементарным произведением.

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

Пример 22. Получить ДНФ для функции

f ( x, y, z, p) = y p x / z ← y x y p z .

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

( y

( p ( xz )) y x y ( p z ) y ( p z ) )

x y( p z ) y ( p z )

y

( p

( xz )) y

≡ (

( p (

)) x y ( p z ) yp yz )

y

x

z

x

y ( p z ) y p yz

y ( p

( xz )) y

≡ ( y px p z

)

x y p z yp

yz

(

)

x

y p z y p yz y

p

(xz )

≡

≡ (

y px pz x y p z yp yz )

(

xy p z x y p x yz

y p yxz ) ≡

≡( yx y p z pxyz pzx p zy ) (xy p z ) ≡

≡yx y p z pxyz pzx pzy xy p z . 3

≡

≡

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

		x, α = 1				Очевидно, что xα =	1, x = α
Обозначим xα =					.			.
		x,			α = 0		0, x ≠ α
Конституентой единицы (K1) данного набора (α1, α2,..., αn) называется
конъюнкция всех переменных, образующих этот набор
K1	( x , x ,..., x				) = xα1 xα2	...xαn ,
(α1 ,α2 ,...,αn )	1 2			n	1 2	n

т.е. если переменная в наборе принимает значение 1, то в конъюнкцию она бе- рется без отрицания, если же в наборе значение переменной 0, то она записыва- ется с отрицанием.

На произвольном фиксированном наборе x1=β1, x2=β2, ... , xn=βn имеем для конституенты единицы данного набора

K1

(β

,β

,...,β

) = βα1βα2

...βαn

1,

если β1

= α1

,…,βn = αn

n

=

(α1 ,α2 ,...,αn )

1

2

1 2

n

0,

если β1

≠ α1

,…, или βn ≠ αn

Очевидно,

что если

(α ,α

2

,...,α

n

)≠(β ,β

,...,β

n

) , то K

1

(β ,β

,...,β

n

) = 0

1

1

2

(α1 ,α2 ,...,αn )

1 2

(так как, если хотя бы один элемент конъюнкции равен 0, то и вся конъюнкция равна 0). Следовательно, верна следующая лемма:

Лемма 1. Конституента единицы равна 1 только на одном наборе.

Конституентой нуля (K0) данного набора (α1, α2,..., αn) называется дизъюнкция всех переменных, образующих этот набор

K(0α1 ,α2 ,...,αn ) ( x1, x2 ,..., xn ) = x1α1 x2α2 ... xnαn

т.е. если переменная в наборе принимает значение 0, то в дизъюнкцию она бе- рется без отрицания, если же в наборе значение переменной 1, то она записыва- ется с отрицанием.

На произвольном фиксированном наборе x1=β1, x2=β2, ... , xn=βn имеем для конституенты нуля данного набора

K 0

(β ,β

,...,β

) = βα1

βα2

... βαn

0,

если β1 = α1,…,βn

= αn

,

n

=

(α1 ,α2 ,...,αn )

1

2

1

2

n

1,

если β1 ≠ α1,…,

или βn ≠ αn

Очевидно,

что

если

(α ,α

2

,...,α

n

)≠(β ,β

,...,β

n

) , то K 0

(

β ,β

2

,...,β

n

) =1

1

1 2

(α1 ,α2 ,...,αn )

1

(так как, если хотя бы один элемент дизъюнкции равен 1, то и вся дизъюнкция равна 1). Следовательно, верна следующая лемма:

Лемма 2. Конституента нуля равна 0 только на «своем» наборе.

СДНФ есть дизъюнкция конституент единицы тех наборов, где функция

равна единице: fСДНФ ( x1, x2 ,..., xn ) = f (α1 ,α2 ,...,αn )=1 K(1α1 ,α2 ,...,αn ) .

Лемма 3. Всякая переключательная функция, не равная тождественно 0, пред- ставима и притом однозначно в совершенной дизъюнктивной нормальной фор- ме (СДНФ).

СКНФ есть конъюнкция конституент нуля тех наборов, где функция равна

нулю: fСКНФ ( x1, x2 ,..., xn ) = f (α1 ,α2 ,...,αn )=0 K(0α1 ,α2 ,...,αn ) .

Лемма 4. Всякая переключательная функция, не равная тождественно 1, пред- ставима и притом однозначно в совершенной конъюнктивной нормальной форме (СКНФ).

Формулы, получаемые перестановкой конъюнкт и дизъюнкт, считаются одной и той же СДНФ (СКНФ) (ввиду коммутативности дизъюнкции и конъ- юнкции).

Пример 23. Построить таблицу истинности для функции f, заданной формулой f ( x, y, z, p) = y p x / z ¬ y x y p z . По таблице истинности выпи-

сать СДНФ и СКНФ.

	4Порядок операций:	f ( x, y, z, p)≡		(			)
					y
			y ( p ( x/ z ))						x y ( p z ) .

	I	II	III	IV	V	VI	VII	VIII	f
x y z p	x / z	p I	← y	III II	y IV	p z	y VI	x VII	V VIII								K1																										K 0
0 0 0 0	1	0	1	1	1	0	0	1	1
											x						y							z								p
0 0 0 1	1	1	1	1	1	1	1	0	0																													x y z
																																																					p
0 0 1 0	1	0	1	1	1	1	1	0	0																													x y												p
																																																z
0 0 1 1	1	1	1	1	1	1	1	0	0																													x y
																																																z						p
0 1 0 0	1	0	0	0	0	0	1	0	1				y
											x												z								p
0 1 0 1	1	1	0	1	1	1	0	1	1				y														p
											x												z
0 1 1 0	1	0	0	0	0	1	0	1	0																													x													p
																																									y							z
0 1 1 1	1	1	0	1	1	1	0	1	1					y z p
											x
1 0 0 0	1	0	1	1	1	0	0	1	1		x
															y							z								p
1 0 0 1	1	1	1	1	1	1	1	1	1		x															p
															y							z
1 0 1 0	1	0	1	1	1	1	1	1	1		x								z
																y													p
1 0 1 1	0	0	1	1	1	1	1	1	1		x								z p
																y
1 1 0 0	1	0	0	0	0	0	1	1	0																																					z p
											x y														p													x					y
1 1 0 1	1	1	0	1	1	1	0	1	1
																					z																															p
1 1 1 0	1	0	0	0	0	1	0	1	0
																																						x				y							z
1 1 1 1	0	0	0	0	0	1	0	1	0
																																						x				y							z						p

fСДНФ = x y z p x y z p x y z p x y z p x y z p x y z p x y z p x y z p x y z p , fСКНФ = (x y z p) (x y z p) (x y z p) (x y z p) (x y z p)

(x y z p) (x y z p).3

2.2. Минимизация булевых функций

Импликантой f2(x1, x2,..., xn) данной функции f1(x1, x2,..., xn) называется функция со следующими свойствами:

( ) 0, на наборах, где f ( x , x ,..., x ) = 0

f x , x ,..., x = 1 1 2 ( n )

2 1 2 n 0 или 1, на наборах, где f1 x1, x2 ,..., xn = 1

Лемма 5. Функция g является импликантой функции f тогда и только тогда, ко- гда переключательная функция g f равна const1.

Лемма 6. Если функция g – импликанта функции f и g = a b, где a и b – произ- вольные функции, то a и b также являются импликантами функции f.

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

Лемма 7. Конституенты единицы тех наборов, на которых данная функция равна единице, есть импликанты данной функции.

Лемма 8. Любая собственная часть конституенты единицы фиксированного набора сохраняет единицу на этом фиксированном наборе.

Сокращенная дизъюнктивная нормальная форма (Сокр. ДНФ) есть дизъ-

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

Теорема 2. Всякая переключательная (логическая) функция представима, при- чём однозначно, в виде некоторой сокращенной дизъюнктивной нормальной формы.

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

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

Пример 24. Получить тупиковую форму для функции: f (x, y, z, p) = yx y p z pxyz pzx pzy xy p z .

4Согласно лемме 5, функции p xyz , xy p z , y p z , pzx , p zy , yx являются импликантами функции f. Проверим, являются ли эти импликанты простыми. Для этого надо построить таблицы истинности для всех собственных частей этих импликант (импликанта является простой, если никакая ее собственная часть импликантой не является).

Очевидно, что никакая часть не импликанты не может быть импликантой. Поэтому, если при проверке на простоту импликанты длины n оказалось, что все ее собственные части длины n–1 оказались не импликантами, то не имеет смысла проверять ее собственные части длинны n–2, …,1.

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

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

																																												xy z p
								xyzp																			xyp																																										xy z и x z p
x,y,z,p	f																	yzp									xp				yp
		xyz					xyp					xzp											xy												xy z							xy p								x z p								y z p								xy			y z				x z				x p			z p
0 0 0 0	1																																																	1																							1				1			1
0 0 0 1																												1																																													1
0 0 1 0																																										1																																			1
0 0 1 1													1															1
0 1 0 0	1																					1													1															1								1							1				1				1				1			1
0 1 0 1	1						1															1					1					1			1																														1								1
0 1 1 0		1																						1																		1																								1				1							1
0 1 1 1	1	1					1					1					1					1					1					1																																	1
1 0 0 0	1																																																																															1
1 0 0 1	1
1 0 1 0	1
1 0 1 1	1
1 1 0 0																																																										1												1										1
1 1 0 1	1																															1																																					1
1 1 1 0
1 1 1 1																		1														1
Импликанта? («+» – да)			–				+							–				–						–				–				–			+								–							+									–							–				–			–				–				–
				x y														y z p																		xz p																							y z p
x,y,z,p	f		x						y				y z					y p						z p							x		z			xp								z p												y z				yp								z p
0 0 0 0	1							1				1						1							1
0 0 0 1									1				1																															1																									1
0 0 1 0									1									1
0 0 1 1									1
0 1 0 0	1																								1																															1
0 1 0 1	1																																									1														1					1								1
0 1 1 0
0 1 1 1	1																																																												1
1 0 0 0	1	1						1				1						1							1							1
1 0 0 1	1	1						1				1																				1				1						1																											1
1 0 1 0	1	1						1										1
1 0 1 1	1	1						1																												1
1 1 0 0		1																							1							1																								1
1 1 0 1	1	1																														1				1						1														1					1								1
1 1 1 0		1
1 1 1 1		1																																		1																									1
Импликанта? («+» – да)			–						–					–						–							–					–					–									–										–						–							–

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

f ( x, y, z, p) = xyp xy z x z p y p z p zx pzy yx

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