Алгоритм построения схемы без рисков по днф.

Пусть задана функция nпеременных

1. Выбирается номер переменной i=1

2. Представляется искомая функция как сумма трех блоков

f(x¹) = A v B (x_i) v C(x¹_i)

3. Для x_iопределяем пары наборовδ₁δ_2,на которых функция равна 1 и которая отличается только значениемx_i.

4. Для каждой полученной пары δ₁δ₂ определяем значения на выходах группы конъюнкцииA

Если A(δ₁) =A(δ₂) = 1, то риск отсутствует, еслиA= 0, то для пары образуем конъюнкцию, которая сохраняет значение 1 на обоих наборахδ₁иδ₂и не зависит отx_i.

5. Увеличиваем iна 1 и конец, еслиIбольшеn, иначе возвращаемся в пункт2.

Пример:

Есть функция трех переменных.φⁱ(x₁,x₂,x₃) = ⌐x₁⌐x₃vx₂x₃

i= 1 – риска нет

i= 2 – риска нет

i = 3

B = x₂x₃

C = ⌐x₁x₃

A = 0

B = 1 C = 0

B = 0 C = 1

Следовательно δ₁= 011, δ₁= 010

Следовательно A= ⌐x₁x₂, тогда окончательно φ(x₁,x₂,x₃) = ⌐x₁⌐x₃vx₂x₃v⌐x₁x₂

Существует два способа для определения конъюнкций, исключающих явление риска:

1. С помощью операции обобщенного склеивания

если часть функции y¹=RX_ivS⌐X_i=RSvRX_ivS⌐X_i

в примереR=x₂,S= ⌐x₁

2. С помощью карт Карно

В карте Карно симметричные клетки отличаются только одним разрядом x_i , следовательно если в симметричной клетке 1 , а она входит в разное покрытие, то возможен риск и эти 1 надо объединить введя дополнительное покрытие.

КНФ

Схему аналогично представлена виде A,B,Cблоков, причем в группеAx_iне входит в группуBиCвходит в прямом и инверсном виде. Риск возможен только если с выхода группы на двух комбинациях получается на двух комбинациях 1. В этом случае 0 на выходе обеспечивается на комбинацииδ₁группыB, а на комбинацииδ₂группы С или наоборот.

если τ_B> τ_Cто получаем:

если τ_B<= τ_Cто получаем:

Идея построения схемы без риска – по КНФ, формирование на выходе группы 0 на комбинациях δ₁иδ₂