Принцип двойственности

Функция f*(x₁,…,x_n)= называется двойственной к функции f. Из определения следует, что f**=(f*)*=f, т.е. функция f двойственна к f* и наоборот.

Пример 5. (0)*=1, (xÚy)*=x&y, (x)*=x, (Øx)*= Øx.

Лемма 2.Пусть F(x₁,…,x_n)=f(f₁(x₁,…,x_n),…, f_m(x₁,…,x_n)), тогда F*(x₁,…,x_n)=f*(f₁* (x₁,…,x_n),…, f_m* (x₁,…,x_n))

Из этой леммы следует принцип дойственности:

Если формула A=S[f₁,…,f_k] реализует функцию f(x₁,…,x_n), то S[f₁*,…,f_k*] реализует функцию f*(x₁,…,x_n).

Двойственная к A формула обозначается A*=S[f₁*,…,f_K*]. Таким образом, в силу принципа двойственности формула, двойственная к данной, получается заменой в исходной формуле всех функций на двойственные с сохранением ее строения, т.е. порядок выполнения операций остается прежним.

Пример 6. Найдем (xyÚyzÚzx)*. В силу принципа двойственности, т.к. & двойственна Ú, и наоборот, имеем (xyÚyzÚzx)*=(xÚy)(yÚz)(zÚx)=(yÚxz)(zÚx)=xyÚyzÚzx.

В силу принципа двойственности из эквивалентности формул A₁ и A₂ следует эквивалентность двойственных формул A₁* и A₂*.

Задачи

9.Используя непосредственно определение двойственности, выяснить, является ли функция g двойственной к функции f:

9.1. , ;

9.2. , ;

9.3. , ;

9.4. , ;

9.5. , ;

9.6. , ;

9.7. , ;

9.8. , ;

9.9. , ;

9.10. , .

10.Используя принцип двойственности, построить формулу, реализующую функцию, двойственную к функции f, и убедиться, что она эквивалентна формуле A:

10.1. , A= ;

10.2. , A= ;

10.3. , A= ;

10.4. , A= ;

10.5. , A= ;

10.6. , A= ;

10.7. , A= ;

10.8. , A= ;

10.9. , A= ;

10.10. , A= .