Булевы функции
Решение задачЗадание 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,у), являющейся суперпозицией функций fn и fk, если f1=(1001 0111), f2 =(0110 1011), f3=(1110 О11О), f4=(0111 0011),f5= (1100 0111), f6 =(1001 0100),f7= (1011 0101), f8= (1000 010), f9 = (1010 0110), f10 = (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,у) = f2(у,у,f1(x,у,x)) . Сначала запишем таблицу функций f1 и f2 (табл. 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)=f2(y,y,f1(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
|
Переменная 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
- Написать таблицу булевой функции f(x,y,z), заданной формулой.
- Найти фиктивные переменные данной функции.
- Преобразовать данную формулу в эквивалентную ей, но не содержащую фиктивных переменных.
Таблица 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
|
Так как 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