1_Algebra_logiki
.pdf
Нормальные формы Cовершенные ДНФ и КНФ
Разложение Шеннона и
Cовершенная дизъюнктивная нормальная форма
1 декомпозиция Шеннона (разложение по одной переменной)
f(x1; :::; xi 1; xi; xi+1; :::; xn) =xi f(x1; : : : ; xi 1; 1; xi+1; :::; xn)_ xi f(x1; : : : ; xi 1; 0; xi+1; :::; xn)
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
17 / 50 |
Нормальные формы Cовершенные ДНФ и КНФ
Разложение Шеннона и
Cовершенная дизъюнктивная нормальная форма
1 декомпозиция Шеннона (разложение по одной переменной)
f(x1; :::; xi 1; xi; xi+1; :::; xn) =xi f(x1; : : : ; xi 1; 1; xi+1; :::; xn)_ xi f(x1; : : : ; xi 1; 0; xi+1; :::; xn)
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
17 / 50 |
Нормальные формы Cовершенные ДНФ и КНФ
Разложение Шеннона и
Cовершенная дизъюнктивная нормальная форма
1 декомпозиция Шеннона (разложение по одной переменной)
f(x1; :::; xi 1; xi; xi+1; :::; xn) =xi f(x1; : : : ; xi 1; 1; xi+1; :::; xn)_ xi f(x1; : : : ; xi 1; 0; xi+1; :::; xn)
2 Cовершенная дизъюнктивная нормальная форма (разложение по всем переменным)
|
( 1_ n |
xnn f( 1; : : : ; n) |
f(x1; : : : ; xn) = |
x11 |
;:::; )
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
17 / 50 |
Нормальные формы Cовершенные ДНФ и КНФ
Разложение Шеннона и
Cовершенная дизъюнктивная нормальная форма
1 декомпозиция Шеннона (разложение по одной переменной)
f(x1; :::; xi 1; xi; xi+1; :::; xn) =xi f(x1; : : : ; xi 1; 1; xi+1; :::; xn)_ xi f(x1; : : : ; xi 1; 0; xi+1; :::; xn)
2 Cовершенная дизъюнктивная нормальная форма (разложение по всем переменным)
|
( 1_ n |
xnn f( 1; : : : ; n) |
f(x1; : : : ; xn) = |
x11 |
;:::; )
Åñëè f( 1; : : : ; n) = 0
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
17 / 50 |
Нормальные формы Cовершенные ДНФ и КНФ
Разложение Шеннона и
Cовершенная дизъюнктивная нормальная форма
1 декомпозиция Шеннона (разложение по одной переменной)
f(x1; :::; xi 1; xi; xi+1; :::; xn) =xi f(x1; : : : ; xi 1; 1; xi+1; :::; xn)_ xi f(x1; : : : ; xi 1; 0; xi+1; :::; xn)
2 Cовершенная дизъюнктивная нормальная форма (разложение по всем переменным)
( 1_ n |
x11 xnn f( 1; : : : ; n) |
|
f(x1; : : : ; xn) = |
||
;:::; ) |
|
|
1 |
n |
f( 1; : : : ; n) = 0, |
Åñëè f( 1; : : : ; n) = 0 , òî x1 |
xn |
|
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
17 / 50 |
Нормальные формы Cовершенные ДНФ и КНФ
Разложение Шеннона и
Cовершенная дизъюнктивная нормальная форма
1 декомпозиция Шеннона (разложение по одной переменной)
f(x1; :::; xi 1; xi; xi+1; :::; xn) =xi f(x1; : : : ; xi 1; 1; xi+1; :::; xn)_
|
xi f(x1; : : : ; xi 1; 0; xi+1; :::; xn) |
|||||
2 Cовершенная дизъюнктивная нормальная форма (разложение |
||||||
по всем переменным) |
|
|
|
|
|
|
( 1_ n |
|
x11 xnn f( 1; : : : ; n) |
||||
f(x1; : : : ; xn) = |
|
|
||||
;:::; ) |
|
|
|
|
||
|
1 |
|
n |
f( 1; : : : ; n) = 0, ) |
||
Åñëè f( 1; : : : ; n) = 0 , òî x1 |
|
xn |
||||
|
|
|
|
W n |
1 |
n |
f(x1; : : : ; xn) = |
f( 1 |
x1 |
xn |
|||
|
( 1 |
;:::; n) |
||||
;:::; )=1
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
17 / 50 |
Нормальные формы Cовершенные ДНФ и КНФ
Разложение Шеннона и
Cовершенная дизъюнктивная нормальная форма
1 декомпозиция Шеннона (разложение по одной переменной)
f(x1; :::; xi 1; xi; xi+1; :::; xn) =xi f(x1; : : : ; xi 1; 1; xi+1; :::; xn)_
|
xi f(x1; : : : ; xi 1; 0; xi+1; :::; xn) |
|||||
2 Cовершенная дизъюнктивная нормальная форма (разложение |
||||||
по всем переменным) |
|
|
|
|
|
|
( 1_ n |
|
x11 xnn f( 1; : : : ; n) |
||||
f(x1; : : : ; xn) = |
|
|
||||
;:::; ) |
|
|
|
|
||
|
1 |
|
n |
f( 1; : : : ; n) = 0, ) |
||
Åñëè f( 1; : : : ; n) = 0 , òî x1 |
|
xn |
||||
|
|
|
|
W n |
1 |
n |
f(x1; : : : ; xn) = |
f( 1 |
x1 |
xn |
|||
|
( 1 |
;:::; n) |
||||
;:::; )=1
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
17 / 50 |
Нормальные формы Cовершенные ДНФ и КНФ
Разложение булевой функции по подмножеству переменных
Теорема
Любая булева функция может быть представлена формулой над множеством элементарных функций _; ^; x.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
18 / 50 |
Нормальные формы Cовершенные ДНФ и КНФ
Разложение булевой функции по подмножеству переменных
Теорема
Любая булева функция может быть представлена формулой над множеством элементарных функций _; ^; x.
Доказательство.
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
18 / 50 |
Нормальные формы Cовершенные ДНФ и КНФ
Разложение булевой функции по подмножеству переменных
Теорема
Любая булева функция может быть представлена формулой над множеством элементарных функций _; ^; x.
Доказательство.
1 Пусть f(x1; : : : ; xn) = 0
2 Пусть f(x1; : : : ; xn) 6= 0
Николаева Екатерина Александровна (ТГУ) |
Алгебра логики |
18 / 50 |