по переменной xi

t {х2, Xi) = Х2 [xi-f (0,0) 7 / (0,1)1 V X2 Ixrf (1,0) V i-f (1,1)1 = = «21-/(0,0) 721-(0,1) Vx-axi-f (1,0) VJC2;i-/(1,1) = = 2 f (0.0)4 x°x]-f (0,1) Vxlx°.f(\,0) V xl afj(1,i) =

где V = (jCj, JC), V; = (62, Si), i = EiBi, Ki{v) = X2x\ - минтермы двух переменных Хц и А!,. Так как f(vi) ~ai=0 или 1 (значение

функции в точке V,), то f (v) = V aiKiiv).

Такая форма представления функции двух переменных называется СДНФ. Разложение функции п переменных будет представлять собой дизъюнкцию 2" членов вила xy...xP...xf{en, -ep...,ei) = =f(Vi)Ki{v)=atKi{v):

(1.37)

2"-l

(v)= v atKi (V).

Выражение (1 37) представляет собой СДНФ функции п переменных.

Так как значения функции at -О или 1, то acKi(v)=0, если Oi=0, и aj./(,(v)=/iCi(v), если ai=l. Поэтому СДНФ функции можно представить в виде

/(v)= У KiAv),

(1.38)

где is - номера тех точек, в которых функция f{v) равна 1, т.е. /(Vi,)=ai, =1.

В качестве примера рассмотрим функцию f(v) трех переменных: хз, «2 и ДС,, заданную таблицей истинности (табл. 1.4), Из

Таблица 1.4

табл. 1.4 следует, что ао=аз = а4=аб = 0, а,=02=05=07=1, поэтому на осиоваиии (1.38) /(v)=/(,(v)V(2(v)V/(5(v)vk7(v) = = KiX2Xi\/x3XiXi\/XiX2Xi\/XiX2Xx. Это и есть СДНФ функции f(v). Совершенная дизъюнктивная нормальная форма полностью неопре-

2"-1

деленной функции имеет вид ft (v) = V ciKi(v), где Ci - неопреде-

ленные значения функции.

Совершенная конъюнктивная нормальная форма (СКНФ). Такую форму функции п переменных flv) можно получпть на основании двойственной теоремы разложения (1.25). Однако СКНФ можно получить и более простым способом, записав СДНФ инверсии функции /(v). Инверсия функции в каждой точке Vj должна иметь инверсные значения ж по отношению к значениям а, самой функции, т. е. )(vi) если f{v,} -а{.

На основании (1,37) запишем СДНФ инверсной функции

2"-1

f(v)= V aiKiiv). 1=0

Из данного соотношения на основании закона двойсгвенносги следует

2"-1 2"-1

/(v) = V at Ki (V) = П К,- (v) = П у 7(7)].

(=0 t=0 i=0

Из определения макстермов следует, что

2"-1

f(v)= П [ai\/Mi{v)]. (1.39)

Данная форма представлеимя функции п переменных называется СКНФ.

Так как значение функции а; = 0 или 1, то ai\/Mi=Mi(v), если ai=0, и a,\/Mi{\) = 1, если а,= 1. Поэтому СКНФ можно представить п виде

f(v) = nMi (V), (1.40)

где is - номера тех точек, в которых функция f(v)=0, т.е. /(v; ) = =а;=0.

В качестве примера рассмотрим функцию трех переменных, заданную табл. 1.4. Так как только значения функции ао=аз = а4 = = 06 = 0, то н а основании ( 1.40) f(v) =мо-мз-м4-мв= (jcsv-aV \/Xi) {x3\/x2\/xi) (xi\/x2\/xi) (x3\/X2\/xi). Это и есть СКНФ функции

Совершенные нормальные формы в базисах И-НЕ и ИЛИ-НЕ.

Совокупность элементарных функций, с помощью которых можно записать любую функцию f(v), называется функционально полной системой функций или базисом. Из выражений (1.38) и (1.40) следует, что для представления любой функции f(v) в СДНФ и СКНФ достаточно использовать только функции (операции) И, ИЛИ и НЕ

2-376 17

(операция НЕ «еобкояима для получения первичных термов хр, входящих в минтермы и макстермы), т.е. совокупность этих функций является базисом.

Преобразуем СДНФ функции (1.37) с помощью закона двойного отрицания и закона двойственности

2"-1

/(v)= V aiKi(v)= П aiKi(v). (1.41)

j=0 (=0

Данная форма представления функций называется совершенной нормальной формой (СНФ) в базисе И - НЕ, так как она требует использования только функций (операций) И - НЕ.

Преобразуем теперь СКНФ функции (1.39) с помощью закона двойного отрицания и закона двойственности

21-1 2" 1

/(v)= П \aiVMi(v)]= V at У Mi {). (1.42)

1=0 1=0

Данная форма представления функций называется СНФ в базисе ИЛИ - НЕ, так как оиа требует использования только функций (операций) ИЛИ-НЕ.

На основании (1.41) и (1.42) из СДНФ и СКНФ функции, заданной табл. 1.4, можно получить СНФ этой функции в базисах

И-Ж и ИЛИ -НЕ !{у)=хзХ2Х1-ХзХ2Х1-ХзХгХ1-ХзХ2Х1; f{v) =

Xiyxyxiyxyxyxylciyxiyxiyxsyxiyxi.

Решение систем логических уравнений. Пусть задана система логических уравнений с одним неизвестным у

h{>,y)8j{,y), (1-43)

где v==(jc„..... Xt), j-l...k. Необходимо решить ее относительно

у, т.е. найти такие значения y-f(v), которые обращают в тождества все уравнения системы (1.43).

Из равносильных соотношений 6/= W<==>V® W=0 следует, что /з(У. у) Ф Sii, У)=0. Тогда на основании равносильных соотио-шеиий С/=0, W=0<=>U\/W=0 получим k

V lfj(,y) ®gj(,y)]=0. (1.44)

Решение системы логических уравнений (1.43) свелось к решению одного логического уравнения (1.44). Разложив левую часть

этого уравнения по г/, получим iVy>l2=0. гд€г)1=\/ [fj(v,0)Q

®g;(v,0)]; Ф2= V[/7(v, l)©g/(v, 1)1.

Тогда: ф2=0, i)i=G=*-i/=ft(v) -произвольная -(полностью неопределенная) функция; ф2=0, i)i = l=*-i/= 1; %=1, i=0=>-(/=0; ф2=!, ф = 1=*-1=0 - решение ие существует, а значит, можпо положить у=с=Ф (О или 1). Из этого следует, что y=h (v)&i)2i)iVl•i2iiV0X

ХМ1\/Сф2ф1.