Дискретная математика. Кулаков Ю.В - 32 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

Используя метод Петрика, составим мультипликативную-аддитивную фор-
му, преобразуем ее в аддитивно-мультипликативную и получим все покрытия столбцов строками этой
таблицы:
(g ∨ k ∨ m ∨ n ∨ p ∨ r) (a ∨ c ∨ d ∨ g ∨ m ∨ p) (b ∨ c ∨ e ∨ g ∨ n ∨ p)&
&(a ∨ b ∨ c ∨ d ∨ e ∨ g ∨ k ∨ n ∨ p ∨ r) (c ∨ d ∨ g ∨ k ∨ m ∨ n ∨ p) =
= (g ∨ ak ∨ kc ∨ kd ∨ m ∨ an ∨ cn ∨ dn ∨ p ∨ ar ∨ cr ∨ rd)&
&(b ∨ c ∨ e ∨ g ∨ n ∨ p) (c ∨ d ∨ g ∨ k ∨ m ∨ n ∨ p) =
= (g ∨ ak ∨ kc ∨ kd ∨ m ∨ an ∨ cn ∨ dn ∨ p ∨ ar ∨ cr ∨ rd)&
&(c ∨ g ∨ n ∨ p ∨ bd ∨ bk ∨ bm ∨ ed ∨ ek ∨ em) =
= g ∨ p ∨ abk ∨ kc ∨ an ∨ cn ∨ dn ∨ ake ∨ kbd ∨ ked ∨
∨ mc ∨ mn ∨ bm ∨ me ∨ cr ∨ rbd ∨ red =
= g ∨ p ∨ kc ∨ an ∨ cn ∨ dn ∨ mc ∨ mn ∨ bm ∨ me ∨
∨ cr ∨ abk ∨ ake ∨ kbd ∨ ked ∨ rbd ∨ red.
Каждое из полученных покрытий π
i
порождает базис B
i
:
π
1
= {g} ↔ B
1
= { o } – базис Вебба;
π
2
= {p} ↔ B
2
= {|} – базис Шеффера;
π
3
= {k, c} ↔ B
3
= { a , ∼};
π
4
= {a, n} ↔ B
4
= {→, 0} – импликативный базис;
π
5
= {c, n} ↔ B
5
= {→,
↵
};
π
6
= {d, n} ↔ B
6
= {→, ⊕};
π
7
= {m, c} ↔ B
7
= { a , } – коимпликативный базис;
π
8
= {m, n} ↔ B
8
= {→, } – импликативный базис;
π
9
= {b, m} ↔ B
9
= {&, } – конъюнктивный базис Буля;
π
10
= {m, e} ↔ B
10
= {∨, } – дизъюнктивный базис Буля;
π
11
= {c, r} ↔ B
11
= { a , 1} – коимпликативный базис;
π
12
= {a, b, k} ↔ B
12
= {∼, &, 0};
π
13
= {a, k, e} ↔ B
13
= {∼, ∨, 0};
π
14
= {k, b, d} ↔ B
14
= {⊕, &, ∼};
π
15
= {k, e, d} ↔ B
15
= {⊕, ∨, ∼};
π
16
= {r, b, d} ↔ B
16
= {⊕, &, 1} – базис Жегалкина;
π
17
= {r, e, d} ↔ B
17
= {⊕, ∨, 1}.
Получено семнадцать базисов, в каждом из которых нельзя вычеркнуть ни
одну функцию без потери полноты в двузначной логике.
Каждой булевой функции, представленной в системе функций {∨, &, }, соот-
ветствует эквивалентное представление в любом из полученных базисов.
Техническая реализация булевых функций, вошедших в базисы, может быть
основана на использовании различных физических явлений. Так, например, магнитные явления исполь-
зуются для реализации импликации и коимпликации, явления в полупроводниках – для реализации
функций Шеффера и Вебба.
Задачи и упражнения
1 Установить, сохраняет ли константы 0 и 1, является ли линейной, самодвойственной и монотон-
ной булева функция:
а) f (x
1
, x
2
, x
3
) = x
1
∨
3
x ;
г) f (x
1
, x
2
, x
3
) = x
1
∨ x
3
;
б) f (x
1
, x
2
, x
3
) = x
2
∨ x
1
x
3
;
д) f (x
1
, x
2
, x
3
) =
3
x ;
в) f (x
1
, x
2
, x
3
) =
32
xx ;
е) f (x
1
, x
2
, x
3
) = x
1
x
2
∨
3
2
3
1
xxxx ∨ .
2 Определить, является ли полной система S булевых функций трех переменных и образует ли она
базис в двузначной логике:
а) S = {x
1
, x
1
x
2
∨
3
x , x
2
∨ x
3
}; г) S = { x
1
x
2
∨
1
x ,
3
2
3
1
xxxx ∨ };

Страницы