Функции алгебры логики

71. Дано m предметов одного сорта и n другого. Найти число выборок, составленных из r элементов одного сорта и s другого.

Ответ: Cmr Cns .

72. Сколькими способами число n можно представить в виде суммы k натуральных слагаемых

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

C k 1

Ответ: n 1 .

73.Бросаются 10 одинаковых игральных костей. Сколькими способами они могут упасть так, что :

1)ни на одной кости не выпадет 6 очков;

2)хотя бы на одной кости выпадет 6 очков;

3)ровно на 3-х костях выпадет 6 очков;

4)ровно на 3-х костях выпадет 6 очков, на 2-х других выпадет 5 очков.

Ответ : 510, 610-510, 24 58, 630 46

74. Считая, что телефонные номера состоят из 7 цифр, причем могут начинаться и с 0 тоже, найти число

телефонных номеров, таких что:

1)4 последние цифры одинаковы и не встречаются среди первых 3-х (первые 3 цифры различны.);

2)все цифры различны ;

3)номер начинается с цифры 5;

4)номер содержит три цифры 5, две цифры 1 и две цифры 2.

Ответ : 5040, 103!! , 106, 210.

75.10 человек, среди которых Иванов и Петров, размещаются в гостинице

вдвух 3-х местных и в одном 4-х местном номерах. Сколькими способами они могут быть размещены ? Сколькими способами их можно разместить, если Иванов и Петров помещены в 4-х местный номер ?

Ответ: 4200, 560.

76.52 карты раздаются 4-м игрокам, каждому по 13 карт. Сколькими способами их можно раздать, если

1)каждый игрок получит туза;

2)один из игроков получит все 13 карт единой масти ;

3)все тузы попадут к одному из игроков;

4)2 определенных игрока не получат ни одного туза.

4! 48!

16 39!

4 48!

48! 2300

Ответ:

,

,

,

.

(12!)4

(13!)3

(13!)3 9!

(13!)3 11!

77. Регистр калькулятора содержит 8 разрядов. Сколько будет 8-ми значных

чисел, если

21

1)регистр содержит ровно 2 одинаковые цифры ;

2)регистр содержит ровно 2 пары одинаковых цифр;

3)регистр содержит ровно 3 одинаковые цифры;

4)регистр содержит не более 3-х различных цифр.

Ответ: 143 10!, 10! 352 , 73 10!, 10 (1 9 27 36 37 ) .

78.Сколькими способами можно выстроить 9 человек:

1)в колонну по одному;

2)в колонну по 3, если в каждой шеренге люди выстраиваются по росту и нет людей одинакового роста?

Ответ: 9!, C93 C63 .

79.Из n букв, среди которых a встречается α раз, буква b встречается β раз,

аостальные буквы попарно различны, составляются слова. Сколько среди них будет различных r-буквенных слов, содержащих h раз букву a и k раз букву b?

Ответ: Chr Ckr h Cn ( r h k ).

80. Имеется колода из 4n (n 5) карт, которая содержит карты 4-х мастей по n карт каждой масти,

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

1)5 последовательных карт одной масти;

2)4 карты из 5-ти с одинаковыми номерами;

3)3 карты с одним номером и 2 карты с другим;

4)5 карт одной масти;

5)5 последовательно занумерованных карт;

6)3 карты из 5-ти с одним и тем же номером;

7)не более 2-х карт каждой масти.

Ответ: 4(n–4), 4n(n–1), 12n(n–1), C5n , 45(n–4), 4nC42n 4 , 12 Cn2 2 n 4Cn2 n3 .

81. Сколькими способами можно расставить n нулей и k единиц так, чтобы между любыми 2-мя единицами находилось не менее m нулей?

Ответ: Ck .

n k( m 1 ) 1

2.ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ

2.1.Элементарные функции алгебры логики

22

Обозначения:			E ={0,1}; Е n =				E E ... E		2	–	прямое	произведение n
				2		2	2	2
сомножителей; (x	1	,..,x		) E , | E | – мощность E , |E |=2, тогда |Е n								|=2n.
			n	2	2			2	2		2
Определение 1. Функцией алгебры логики называется закон,
осуществляющий отображение Е n							E , причем отображение всюду определено
					2		2
и функционально.
Так как множество Е n					конечно, то задать отображение Е n								E , означает
				2								2	2
задать множество наборов из Е 2n						и для каждого набора указать его образ в Е 2.

Пример 1. Пусть n=2, тогда Е 22 ={(0 0),(0 1),(1 0),(1 1)}, отображение Е 22

E2 задано, например, так: (0 0) 0 ; (0 1) 1; (1 0) 1 ; (1 1) 1

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

записывая эту функцию в виде таблицы:

x1	x2	f(x1,x2)
0	0	0
0	1	1
1	0	1
1	1	1

Здесь x1 и x2 обозначают названия столбцов, а f – символ, обозначающий отображение. Следует обратить внимание, что функции f(x1,x2) и f(y1,y2) задают одно и то же отображение, и их таблицы отличаются только названиями столбцов.

Определение 2. Таблица, задающая функцию f(x1,x2,...,xn), называется таблицей истинности для этой функции.

Рассмотрим функции одной переменной. Их будет всего 4, они задаются следующими таблицами истинности:

x f0(x)

00

10

функция называется константой 0, записывается f0(x) 0;

x f1(x)

00

11

функция называется тождественной, записывается f1(x)= x;

23

x	f2(x)
0	1
1	0

функция называется «не x» и записывается f2 (x)= x ;

x	f3(x)
0	1
1	1

функция записывается f3(x) 1 и называется константой 1. Если стандартным расположением переменной x считать 0 в первой строке и 1 во второй, то

функции f0, f1, f2, f3 определяются однозначно наборами значений: f0=(0,0), f1=(0,1), f2=(1,0) и f3=(1,1). Наборы значений функций составляют множество E2 Е2,

поэтому количество функций одной переменной равно |E2 E2|=4. Для удобства функции пронумерованы так, что двоичный код номера совпадает с набором значений функции.

Рассмотрим функции двух переменных f(x1,x2). Функции двух переменных определены на множестве Е 22 ={(0 0),(0 1),(1 0),(1 1)}, эти наборы переменных из

Е 22 можно тоже рассматривать как двоичные коды чисел 0,1,2,3, именно такой порядок расположения наборов (x1,x2) будем считать стандартным. Тогда функции

f(x1,x2) определяются однозначно наборами значений ( 1, 2,									3,	4), где каждое
E ,		поэтому (	,	,	,	) Е 4		. Следовательно, число		функций двух
i	2	1		2	3	4	2

переменных равно 24=16, занумеруем их числами от 0 до 15 так, чтобы двоичный код номера совпадал с набором значений функции.

x1 x2	f0	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	f11	f12	f13	f14	f15
0 0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0 1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1 0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1 1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

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

24

1)f1(x1,x2) = (x1&x2), читается «конъюнкция х1 и х2», иногда вместо знака

&употребляют знак или вообще его опускают, пишут (х1х2). (х1 х2) совпадает с обычным произведением х1х2 и совпадает с min(x1,x2). Эту операцию называют также логическим умножением.

2)	f6(x1,x2) = (x1 x2) – сложение х1 и х2 по модулю два, иногда пишут
(х1+х2)mod2.

3)f7(x1,x2) = (x1 x2), читается «х1 дизъюнкция х2», она совпадает с max(x1,x2), ее называют логическим сложением.

4)f8(x1,x2) = (x1 x2), читается «х1 стрелка Пирса х2» и совпадает с отрицанием дизъюнкции, другие названия: функция Вебба, функция Даггера.

5)f9(x1,x2) = (x1 x2), читается «х1 эквивалентно х2».

6)f13(x1,x2) =( x1 x2), читается «х1 импликация х2», иногда обозначается (х1 х2), т. е. х1 влечет х2 .

7)f14(x1,x2) = (x1|x2), читается «х1 штрих Шеффера х2», она является отрицанием конъюнкции.

Cимволы , участвующие в обозначениях элементарных

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

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

соответствует «лжи» , а 1 – «истине», а функции алгебры логики называются еще и блевыми функциями.

	Рассмотрим		функции		f(x ...x	), где	(x ...x	) Е n		, тогда число наборов
					1 n		1 n		2
(x	...x	),где функция f(x ...x		)	должна быть задана,				равно |Е n		|=2n. Обозначим
1	n		1 n							2

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

число функций, зависящих от n переменных. Очевидно, Р2(n)=22 n.

С ростом n число Р2(n) быстро растет: P2(1)=4, P2(2)=16, P2(3)=256,

P2(4)=65536 . При больших n табличный способ задания функций становится неприемлемым, используется формульное задание функций. Но прежде чем ввести понятие формулы, дадим определение существенной переменной.

Определение 3. Функция f(x1,...,xi–1,xi,xi+1,...,xn) существенно зависит от хi,

если существуют такие значения 1, ... i–1, i+1, ... n переменных x1, ...xi–1, xi+1, ...xn, что f( 1, ... i–1 i+1 . n) f( 1... i–1 i+1 . n) . Тогда переменная хi называется

25

существенной переменной. В противном случае хi называется фиктивной переменной.

Пример 2.

Рассмотрим несколько функций двух переменных

x1	x2	(x1 x2)	f3	f15
0	0	0	0	1
0	1	0	0	1
1	0	0	1	1
1	1	1	1	1

Покажем, что (х1 x2) существенно зависит от х1. Рассмотрим наборы (0,1) и (1,1), здесь 2=1, f(0, 2)=0 и не равно f(1, 2)=1. Покажем, что х2 тоже существенная переменная. Рассмотрим наборы (1,0) и (1,1). Здесь 1=1, f(1,0)=0 и

не равно f(1,1)=1. Для функции f3(x1,x2) покажем , что х2 – иктивная переменная,

т.е. надо показать, что не существует наборов ( 1,0) и ( 1,1) таких, что f3( 1,0) f3( 1,1). Пусть 1=0, т.е. рассмотрим наборы (0,0) и (0,1), f(0,0)=f(0,1)=0.

Пусть 1=1, но f(1,0)=f(1,1)=1.

Для функции f15 и x1 и x2 являются фиктивными переменными. x1 –

фиктивная переменная, если не существует наборов (0, 2) и (1, 2), таких, что f(0, 2) f(1, 2). Если 2=0, то f(0,0)=f(1,0)=1. Пусть 2=1, тогда f(0,1)=f(1,1)=1.

Пусть хi является фиктивной переменной для функции f(x1, ..., xi, ..., xn). Тогда ее можно удалить из таблицы истинности, вычеркнув все строки вида: ( 1, ... i–1, 1, i+1, ... n) или, наоборот, все строки вида: ( 1,

..., i–1, 0, i+1, ... n) и столбец для переменной хi. При этом получим таблицу для некоторой функции g(x1, ..., xi–1, xi+1, ...xn). Будем говорить, что функция g(x1, ...xi–1, xi+1, ...xn) получена из функции f(x1, ..., xi, ...xn) путем удаления фиктивной переменной хi или f получена из g путем введения фиктивной переменной хi.

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

Пример 3.

x1	x2	f3
0	0	0
0	1	0
1	0	1
1	1	1

Вычеркнули строки типа ( ,1), т.е. (0,1) и (1,1) и столбец для х2.

26

Получили f3(x1 x2) = g(x1) = x1.

Пример 4.

x1	x2	g
0	0	0
0	1	0
1	0	0
1	1	1

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

введением фиктивной переменной х3:

x1	x2	x3	f
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	0

К наборам (х1,х2) мы добавим х3=0, получим наборы вида: ( 1, 2,0), на этих наборах функцию f положим равной g( , ), затем добавим наборы вида ( , ,1), функцию f( , ,1) положим равной g( , ).

Особую роль играют константы 0 и 1, которые не имеют существенных переменных и которые можно рассматривать как функции от пустого множества переменных.

2.2. Формульное задание функций алгебры логики

Дадим индуктивное определение формулы над множеством. Это определение несколько сложное по форме, но будет полезно в дальнейшем. С

индуктивным определением мы встречались в математическом анализе при определении n-го дифференциала dnf(x) : было введено понятие первого дифференциала df(x), а затем n-й дифференциал определялся как первый дифференциал от d(n–1)f(x).

27

Определение 1. Пусть М P2, тогда:

1)каждая функция f(x1, ..., xn) называется формулой над ;

2)пусть g(x1, ..., xm) G1, ..., Gm – либо переменные, либо формулы над

. Тогда выражение g(G1...Gn) – формула над .

Формулы будем обозначать заглавными буквами: N[f1, ..., fs], имея в виду функции, участвовавшие в построении формулы, или N(х1, ..., xk) имея в виду переменные, вошедшие в формулу. Gi – формулы, участвовавшие в построении g(G1, ..., Gn), называются подформулами.

Пример 1. Пусть N={(x1 x2),(x1 x2),( x )}, тогда ((х1 х2) х3) – формула над

.

Сопоставим каждой формуле N(x1, ..., xn) функцию f(x1, ..., xn) P2.

Сопоставление будем производить в соответствии с индуктивным определением формулы.

1)Пусть N(x1, ..., xn)=f(x1, ..., xn), тогда формуле N(x1, ..., xn) сопоставим функцию f(x1, ..., xn).

2)Пусть N(x1, ..., xn)=g(G1, ..., Gm), где каждое Gi – либо формула над M, либо переменная, тогда по индуктивному предположению каждому Gi сопоставлена либо функция fi P2 , либо переменная хi , которую можно считать тождественной

функцией.			Таким образом,		каждой		формуле Gi	сопоставлена функция
fi( xi	,...,xi	),	причем:{ xi	,...,xi		} {x1,	..., xn}, т.к.	в формуле N(x1, ..., xn)
1	k		1	k

перечислены все переменные, участвовавшие в построении формулы. Можно считать, что все функции fi зависят от переменных (x1, ..., xn), причем какие-то переменные могут быть фиктивными. Тогда N(x1, ..., xn) = g(G1, ..., Gm) = g( f1(x1, ..., xn), ..., fm(x1,..,xn)). Сопоставим этой формуле функцию h(x1, ..., xn) следующим образом: пусть ( 1, ..., n) – произвольный набор переменных (x1, ..., xn).

Вычислим значение каждой функции fi на этом наборе, пусть f( 1, ..., n)= i, затем найдем значение функции g(x1, ..., xm) на наборе ( 1, ..., m) и положим h( 1, ..., n) = g( 1, ..., m) = g(f1( 1, ..., n), ..., fm( 1, ..., n)). Так как каждое fi(x1, ..., xn) есть функция, то на любом наборе ( 1, ..., n) она определяется однозначно, g(x1, ..., xm)

– тоже функция, следовательно, на наборе ( 1, ..., n) она определяется

28

однозначно, где h(x1, ..., xn) есть функция, определенная на любом наборе ( 1, ...,

n).

Множество всех формул над M обозначим через <M>.

Определение 2. Две формулы N и D из <M> называются равными N=D

или эквивалентными N D , если функции, реализуемые ими, равны.

Пример 2. Доказать эквивалентность формул:

( x1 &(х2 x3))~(								x1 ( x2		x3 )&( x3		x2 ) ) .
		x1		x2	x3		x2 x3			&	x2 x3		x3 x2		&	x1
	0			0	0		0			0	1		1		1	1	0
	0			0	1		1			1	1		0		0	0	1
	0			1	0		1			1	0		1		0	0	1
	0			1	1		0			0	1		1		1	1	0
	1			0	0		0			0	1		0		1	1	0
	1			0	1		1			0	1		0		0	1	0
	1			1	0		1			0	0		1		0	1	0
	1			1	1		0			0	1		1		1	1	0

Упрощение записи формул:

1)внешние скобки можно отпускать;

2)приоритет применения связок возрастает в следующем порядке: ~, , ,&;

3)связка – над одной переменной сильнее всех связок;

4)если связка – стоит над формулой, то сначала выполняется формула, затем отрицание;

5)если нет скобок, то операции и выполняются в последнюю очередь.

29

Теорема о замене подформул на эквивалентные

Пусть N <M> и имеет вид: N(x1, ..., xn) = g(G1, ...Gi, ...,Gm). Пусть подформула Gi~Gi , тогда формула N(x1, ..., xn) = g(G1, ...,Gi,...,Gm) эквивалентна формуле N (x1, ..., xn) = g(G1 , ..., Gi , ...,G m).

Доказательство. Формулы N и N эквивалентны, если реализуют одну и

ту же функцию. Согласно построению функции, реализующей формулу имеем:
N(x1, ..., xn) = g(f1(x1, ..., xn ), ..., fi(x1, ..., xn), ..., fm(x1, ..., xn)),
N (x1, ..., xn)= g(f1 (x1, ..., xn ), ..., fi (x1, ..., xn), ..., fm (x1, ..., xn)).
По условию Gi~Gi , следовательно на наборе 1, ..., n) имеем fi 1, ..., n) =	=

fi 1, ..., n) следовательно, на любом наборе 1, ..., n)значения функции g(f1,

...,fi, ...,fm) и g(f1 , ...,fi , ...,fm ) совпадают. Получим N~N .

Некоторые свойства элементарных функций

1.Идемпотентность & и : х&x=x , x x=x.

2.Коммутативность &, , ,|,~, .

3.Ассоциативность &, , ,~, поэтому в формулах вида xyz можно не ставить никаких скобок.

4.Дистрибутивность:

а) & по отношению к :	x&(y z)=xy xz ,
б) по отношению к &:	x(y&z)=(x y)&(x z) ,

в) & по отношению к : x(y z)=xy xz .

5.

Инволюция :

x =х .

= x & y и xy = x y .

6.

Правило де Моргана:

x y

7.

Законы действия с 0 и 1:

x 0=x , x 1=1 , x x =1 ,

x&0=0 , x&1=x , x&

x

=0 , x 1=

x

, x 0=x.

8. Самодистрибутивность импликации: x (y z)=(x y) (x z).

Равенство всех этих формул доказывается по определению, т.е. по

равенству функций, которые они реализуют.

Проверим				для		примера	самодистрибутивность импликации :
x (y z)=(x y) (x z).
	x	y	z		y z	x (y z)	x y	x z

30