Булевы функции

Задание 2.1.1

Построить таблицу данной булевой функции f(x,y,z)

Таблица 2.1.1

№	f(x,y,z)
1	x+y∧z ->x ∨ z
2	(x|y)->z ∧ y+x
3	(x->y)+z ∨ x
4	x ∨ y + z < - > y
5	x∨ y -> z + y
6	x ∨ y -> z ∨ y
7	(x↓y) ∨ x-> z
8	(x∧y ->z)∨x + y
9	(x|y)∧z→y∨x
10	(x→y∧z)+x
11	x ∨ y ∧ z→x∧y
12	(x+y)+(z∨x)
13	x∨y+z→y
14	(x↓y)+z∨x
15	(x∨y→z)+y
16	x↔y+z∨y)
17	x∨y∧z+y
18	(x+y)∧z∨x
19	(x→y)+(z∨y)
20	(x|y)∧z&or y
21	(x→y)+z↔y
22	(x↓y)↔z+y
23	(x∨y)+z→y
24	x∧y+z→x
25	(x+(y↓z)+y)
26	x→y ∨ y +z
27	(x|y)+(y→z∧x
28	x→y ∧(x∨y+z)
29	y+z↔z∧x∨x
30	x∧ y→z ↔ y+z

Пример решения задания 2.1.1

Построить таблицу булевой функции, заданной формулой

f(x,y,z) = x→y∧z∨-х

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

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

Итак, мы нашли, что исходная формула задаёт булеву функцию f(x,y,z), имеющую вектор значений (1111 0001).

Задание 2.1.2

Написать таблицу функции h(x,у), являющейся суперпозицией функций f_n и f_k, если f₁=(1001 0111), f₂ =(0110 1011), f₃=(1110 О11О), f₄=(0111 0011),f₅= (1100 0111), f₆ =(1001 0100),f₇= (1011 0101), f₈= (1000 010), f₉ = (1010 0110), f₁₀ = (0101 1000).

№	n	k	h(x,y)
1	1	2	fn(x,fk(x,x,y),y)
2	2	1	fn(x,fk(y,x,y),x)
3	1	2	fn(y,fk(x,y,x),x)
4	3	5	fn(x,fk(y,x,y),y)
5	3	2	fn(y,fk(x,y,x),x)
6	4	3	fn(x,fk(y,y,x),y)
7	2	3	fn(y,fk(x,y,y),y)
8	5	2	fn(y,x,fk(x,x,y))
9	5	4	fn(fk(x,y,y),x,y)
10	3	2	fn(x,x,fk(x,y,y))
11	4	3	fn(x,y,fk(y,x,y))
12	2	4	fn(x,fk(x,y,y),y)
13	5	7	fn(x,y,fk(y,x,x))
14	9	8	fn(y,y,fk(x,y,x))
15	7	5	fn(x,y,fk(x,y,y))
16	8	7	fn(x,x,fk(y,x,y))
17	7	8	fn(y,fk(x,y,x),y)
18	5	9	fn(x,fk(y,x,x),y)
19	5	10	fn(y,fk(x,y,x),x)
20	10	9	fn(x,fk(x,x,y),y)
21	10	5	fn(fk(x,x,y),y,x)
22	7	9	fn(fk(y,y,x),x,y)
23	8	7	fn(fk(x,y,y),y,x)
24	7	8	fn(fk(x,y,x),x,y)
25	6	7	fn(fk(y,y,x),y,x)
26	9	2	fn(x,fk(y,y,x),y)
27	2	10	fn(x,fk(y,x,x),y)
28	3	9	fn(fk(y,y,x),x,x)
29	10	7	fn(,yx,fk(x,y,x))
30	8	3	fn(x,fk(y,y,x),y)

Пример решения задания 2.1.2

Написать таблицу функции h(x,у) = f₂(у,у,f₁(x,у,x)) . Сначала запишем таблицу функций f₁ и f₂ (табл. 2.1.2а).

Таблица 2.1.2а

xyz	f1	f2
000	1	0
001	0	1
010	0	1
011	1	0
100	0	1
101	1	0
110	1	1
111	1	1

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

В заключительном столбеце, задающим функцию h, выделим столбец.

h(x,y)=f₂(y,y,f₁(x,y,x))

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

Итак h(x,y)=(1111).

Задание 2.1.3

Для данной функции f(x,y,z)

1. Выяснить, какие ее переменные являются существенными, а какие - фиктивными.

2. Выразить f(x,y,z) формулой, содержащей только существееные переменные.

Таблица 2.1.3

№	f(x,y,z)
1	1011 1011
2	0011 1100
3	0101 1111
4	1000 1000
5	1010 0000
6	1100 1111
7	0010 0010
8	1100 0011
9	0000 1010
10	1001 1001
11	0101 0000
12	1100 1100
13	0100 0100
14	1111 0011
15	0000 0101
16	0000 0011
17	0011 0000
18	1101 1101
19	1111 0101
20	0111 0111
21	1010 0101
22	0011 0011
23	1011 1011
24	1111 1100
25	0110 0110
26	1010 1111
27	1010 1010
28	1110 1110
29	0001 0001
30	0011 1111

Пример решения задания 2.1.3

Для данной функции f(x,y,z)=(0101 1010)

1. Выяснить, какие её переменные являются существенными, а какие — фиктивными.

2. Выразить f(x,y,z) формулой, содерэюащей только существенные переменные.

Таблица 2.1.3а

x	y	z	f
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1

x	y	z	f
1	0	0	1
1	0	1	0
1	1	0	0
0	1	1	1

1. Переменная х является существенной для данной бф, так как, например, наборы (0,0,0) и (1,0,0) являются соседними по переменной х и f(0,0,0) ≠ f(1,0,0). Переменная z является существенной для данной бф, так как, например, наборы (0,0,0) и (0,0,1) являются соседними по переменной z и f(0,0,0) ≠ f(0,0,1).

Таблица 2.1.3 x z f 0 0 0 0 1 1 1 0 1 1 1 0

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

f(0,0,0) = f(0,1,0), f(1,0,0) = f(1,1,0), f(0,0,1) = f(0,1,1), f(1,0,1) = f(1,1,1).

2. Выпишем таблицу функции /, как функцию только от существенных переменных.

Видим, что функция f(x, z) = x + z.

Задание 2.1.4

1. Написать таблицу булевой функции f(x,y,z), заданной формулой.
2. Найти фиктивные переменные данной функции.
3. Преобразовать данную формулу в эквивалентную ей, но не содержащую фиктивных переменных.

Таблица 2.1.4

Выполним задание 2.1.4 для функции

1. При отыскании таблицы значений для таблица 2.1.4а данной функции (табл. 2.1.4а) заметим, что из определения дизъюнкции и конъюнкции следует, что для построения таблицы функции, имеющей вид дизъюнкции нескольких выражений, нужно найти единичные наборы для каждого из этих выражений, тогда объединение множеств единичных наборов и даст множество единичных наборов исходной функции. 2. Рассмотрим пары наборов, соседних по переменной х, и значения функции на этих наборах: f(0,0,0) = f(1,0,0) = 0; f(0,0,1) = f(1,0,1) = 1; f(0,1,0) = f(1,1,0) = 1; f(0,1,1) = f(1,1,1) = 1. Значит, х — фиктивная переменная.

Таблица 2.1.4a xyz f 000 0 001 1 010 1 011 1 100 0 101 1 110 1 111 1

Так как f(0,0,0) ≠ f(0,0,1), значит, z — существенная переменная.
Неравенство f(0,0,0) ≠ f(0,1,0) показывает, что y — также существенная переменная.

3. Преобразуем формулу к виду, не содержащему фиктивной переменной.

f (x,y,z) = X → у ∧ Z ∨ ¬ X

= xy ∨ yz ∨ yz ∨ xyz = xy ∨ (y ∨ y)z ∨ xyz = xy ∨ l · z ∨ xyz=
= xy ∨ z ∨ xyz = xy ∨ z ∨ xy=z ∨ xy ∨ xy=z ∨ (x ∨ x)y =
= zvl · y = zv у.

Итак,

f (x,y,z)=z∨y