Множества. Комбинаторика. Отношения (стр. 6 )

.

Наборы начинаются заполняться с нулевого набора 00…0, далее идет 00..01, т. е. по правилу двоичного сложения (0+0=0, 0+1=1, 1+0=1, 1+1=0).

Пример:

1) Пусть дана булева функция f(x, y), т. е. зависящая от двух переменных. Тогда таблица истинности будет содержать 4 строки (22).

X	Y	F(X, Y)
0	0	F(0, 0)
0	1	F(0, 1)
1	0	F(1, 0)
1	1	F(1, 1)

2) Пусть дана булева функция, зависящая от трех переменных F(x, y, z). Тогда таблица истинности данной функции содержит 8 строк (23).

X	Y	Z	F(X, Y, Z)
0	0	0	F(0, 0, 0)
0	0	1	F(0, 0, 1)
0	1	0	F(0, 1, 0)
0	1	1	F(0, 1, 1)
1	0	0	F(1, 0, 0)
1	0	1	F(1, 0, 1)
1	1	0	F(1, 1, 0)
1	1	1	F(1, 1, 1)

Упражнения

1) Какой номер у набора значений переменных булевой функции (11101)?

2) Номером какого набора значений переменных булевой функции от пяти переменных является число 18?

Ответ 1) 57, 2) (10010)

Единый способ записи наборов значений переменных дает возможность записывать функции лишь в виде столбца ее значений. Например, x&y = (0001), xÚy = (0111), h = (00010111). Нульместные функции 0 и 1 называются соответственно тождественным нулем и тождественной единицей. Функция f(x) = x называется тождественной функцией. Функция f(x) = Øx называется отрицанием x. Все одноместные функции можно свести в таблицу:

X	0(x)	1(x)	f(x) = x	f(x) = Øx
0	0	1	0	1
1	0	1	1	0

Выпишем все двуместные булевы функции

x	y	0(x, y)	x&y	xÞy	yÞx	xÅy	xÚy	x¯y	xóy	Øy	yÞx	Øx	xÞy	x½y	1(x, y)
0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	0	0	1	0	1	0	1	0	1	0	1

Конъюнкция x и y обозначается также xy, x×y, min (x, y) и читается “x и y”. Дизъюнкция xÚy читается “x или y”. Функция xÅy называется суммой по модулю 2 или альтернативной дизъюнкцией и читается “x плюс y по модулю 2”. Эквивалентность x ó y часто обозначается также x«y, x~y, xºy. Импликация в некоторых книгах обозначается также x®y, x É y и часто читается “x имплицирует y”. Функция x½y называется штрихом Шеффера. Функция х¯у называется стрелкой Пирса, функцией Пирса. Все эти функции называют элементарными. Символы Ø,&,Ú,Å,Þ,Û,½,¯ называют логическими связками.

Две функции называются равными, если они принимают одинаковые значения на одних и тех же наборах значений переменных. Говорят, что f(x1,…,xn) существенно зависит от переменной x1, если существует такой набор значений переменных x2 = a2,…, xn = an, что f(0, a2,…, an) ¹ f(0, a2,…, an). Переменные, от которых функция зависит существенно, называются существенными, остальные фиктивными. Отождествляем функции, из которых добавлением фиктивных переменных можно получить одну и ту же функцию.

ТЕОРЕМА. Число всех различных n–местных булевых функций равно

Доказательство. Число наборов значений n переменных равно . В случае стандартной нумерации наборов значений переменных n–местной булевой функции ставится во взаимооднозначное соответствие двоичный вектор длины . Таких векторов . Так как соответствие взаимооднозначное, то и всех булевых функций тоже столько. <

Упражнения

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

2) Найдите число всех различных n–местных функций k-значной логики (k ³ 2).

Приведем пример, в котором появляются булевы функции.

1) Составным элементом нервной системы является нейрон. Это устройство предназначено для того, чтобы не пропускать слабые возбуждения и передавать достаточно регулярные и сильные.

Одна из моделей нейрона. Нейрон N имеет n входов, по которым в некоторый момент времени t могут поступать или не поступать возбуждения. Если в момент t более h входов возбуждены, на выход нейрона поступает возбуждение, в противном случае оно не поступает. Обозначим входы нейрона x1,…,xn. Будем говорить, что вход xi принимает значение 0 в момент t, если он не возбужден в этот момент, и значение 1, если xi возбужден в момент t. Состояние выхода Ah(x1,…,xn) однозначно определяется соотношением входов и числом h. Будем считать Ah(x1,…,xn) = 1, если среди значений x1,…,xn более h равняется 1; Ah(x1,…,xn) = 0, если среди значений x1,…,xn не более h равняется 1

Пример. Для A1(x1, x2, x3) имеем таблицу истинности.

х1	х2	х3	А1
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

2.1.3. Формулы алгебры логики

Алфавитом называется любое непустое множество. Элементы этого множества называются символами алфавита. Словом в алфавите G называется произвольная конечная (возможно пустая) последовательность символов из G. Фиксируем некоторый конечный или счетный алфавит переменных X ={x1,x2,…}.

Формула алгебры логики определяется следующим образом (индуктивное определение):

1)  Переменная есть формула.

2)  Если А и В – формулы, то (ØА), (АÚВ), (А&В), (АÞВ), (АÅВ), (АÛВ), (А½В), (А¯В) – тоже формулы.

3)  Других формул нет.

Подформулой формулы А называется любое подслово слова А, которое само является формулой. Для сокращения записи формул обычно принимаются следующие соглашения:

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

б) формула ØА записывается в виде ,

в) формула А&В записывается в виде АВ,

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

д) связка & считается сильнее любой другой двуместной связки.

В соответствии с этим договоримся, что логические операции выполняются в следующем порядке:

1)  конъюнкция,

2)  дизъюнкция,

3)  импликация и эквиваленция в порядке их записи,

4)  если часть формулы заключена в скобки, то сначала производится действие в скобках,

5)  если над частью формулы стоит знак отрицания, то он заменяет собой скобки, в которые заключена эта часть формулы.

Функция jА, реализуемая формулой А, вводится следующим образом:

1)  Формуле А = х сопоставляется тождественная функция j(х) = х.

2)  Если А = ØВ, то jА = ØjВ; если А = В°С, то jА = jВ°jС, где ° = &, Ú, Þ, Û, Å, ½, ¯.