3, Содержащая одну подформулу глубины 2 и две подформулы

глубины 1. Если f1 обозначает дизъюнкцию, f2- конъюнкцию, а f3 -

сложение по mod2, то приведенная формула примет более

привычный вид:

((x3∨ x1)⊕(x1&(x1⊕ x2))) (3.1)

Все формулы, построенные описанным способом, т.е.

содержащие только символы переменных, скобки и знаки функций

из множества S называются формулами над S.

Всякая формула, выражающая функцию f, как суперпозицию

других функций, задает правило ее вычисления: для вычисления

формулы необходимо вычислить значения всех ее подформул.

Вычислим, например, формулу (3.1) на наборе x1=1, x2=1, x3=0.

Используя таблицу 2.3 получим x3∨x1=1; x1⊕x2=0,

x1&(x1⊕x2)=x1&0=0; ((x3∨x1)⊕(x1&(x1⊕x2)))=1⊕0=1.

Таким образом, формула каждому набору значений аргументов

ставит в соответствие значение функции и, поэтому, может

служить наряду с таблицей способом задания и вычисления

функции. По формуле, вычисляя ее на всех 2n наборах, можно

восстановить таблицу функции. О формуле, задающей функцию,

говорят, что она реализует или представляет эту функцию.

В отличие от табличного задания представление данной

функции формулой не единственно. Например, функцию f14

«штрих Шеффера» из таблицы 2.3 можно выразить формулами

f14(x1,x2)= x1 ∨ x2

f14(x1,x2)= x1 x2 (3.2)

а функцию f8 «стрелка Пирса» - формулами

f8(x1,x2)= x1 ⋅ x2

f8(x1,x2)= x1 ∨ x2 (3.3)

Формулы, представляющие одну и ту же функцию, называются

эквивалентными или равносильными. Эквивалентность формул

обозначается знаком равенства:

x1 ∨ x2 = x1 ⋅ x2 , x1 ⋅ x2 = x1 ∨ x2

Для того, чтобы выяснить, эквивалентны формулы или нет,

можно по каждой формуле восстановить таблицу функции, а затем

эти таблицы сравнить.

Существует и другой метод определения эквивалентности

формул, называемый методом эквивалентных преобразований. Его

мы рассмотрим позднее.

Булева алгебра.

Алгебра (P2,∨,&,⎤ ), основным множеством которой является

все множество логических функций, а операциями - дизъюнкция,

конъюнкция и отрицание, называется булевой алгеброй

логических функций. Операции булевой алгебры также часто

называют булевыми операциями.

Свойства булевых операций.

1. Ассоциативность:

( x1 ⋅ ( x2 ⋅ x3 ) ) = ( ( x1 ⋅ x2 ) ⋅ x3 ) ,

( x1 ∨ ( x2 ∨ x3 ) ) = ( ( x1 ∨ x2 ) ∨ x3 ) . (3.4)

2. Коммутативность:

x2 ⋅ x1 = x1 ⋅ x2 ,

x2 ∨ x1 = x1 ∨ x2 . (3.5)

3. Дистрибутивность конъюнкции относительно дизъюнкции:

( x1 ⋅ ( x2 ∨ x3 ) ) = ( x1 ⋅ x2 ) ∨ ( x2 ⋅ x3 ) (3.6)

4. Дистрибутивность дизъюнкции относительно конъюнкции:

( x1 ∨ ( x2 ⋅ x3 ) ) = ( x1 ∨ x2 ) ⋅ ( x2 ∨ x3 ) (3.6)

5. Идемпотентность:

x⋅x = x

(x∨x)=x (3.7)

6. Двойное отрицание:

x=x (3.8)

7. Свойства констант:

x ⋅1 = x , x ⋅ 0 = 0 , x ∨ 1 = 1 , x ∨ 0 = x , 0 = 1 , 1 = 0 . (3.9)

8. Закон де Моргана:

( x1 ⋅ x2 ) = ( x1 ∨ x2 ) ,

( x1 ∨ x2 ) = ( x1 ⋅ x2 ) (3.10)

9. Закон противоречия:

x⋅x = 0 (3.11)

10. Закон «исключения третьего»

x ∨ x =1 (3.12)

Соотношения (3.4) - (3.12) можно проверить стандартным

методом, т.е. вычислением обеих частей равенств на всех наборах

значений переменных.

Очевидно, что результат вычислений не зависит от того,

являются ли эти переменные независимыми или получены, в свою

очередь, в результате каких-то вычислений. Поэтому равенства

(3.4) - (3.12) остаются справедливыми при подстановке вместо

переменных любых логических функций и любых формул,

представляющих эти функции. Т.е. справедливо правило

подстановки: при подстановке формулы F вместо переменной x

все вхождения переменной x в исходное соотношение должны

быть одновременно заменены формулой F.

4. Принцип двойственности. Совершенная

дизъюнктивная нормальная форма (СДНФ).

Разложение булевых функций по переменным.

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

Определение: Функция f*(x1,…,xn) , равная f ( x1 ,..., xn ) ,

называется двойственной функцией к функции f(x1,…,xn).

Очевидно, что таблица для двойственной функции (при

фиксированном порядке наборов значений переменных)

получается из таблицы для функции f(x1,…,xn) инвертированием

(т.е. заменой 0 на 1 и 1 на 0) столбца функции и его

переворачиванием (таблицы 4.1 и 4.2).Таблица 4.1.

x f0 f1 f2 f3 f0* f1* f2* f3*

0 0 0 1 1 1 0 1 0

1 0 1 0 1 1 1 0 0

Таблица 4.2.

15

x1 x2 f0 f3 f0* f3*

0 0 0 0 0 0

0 1 0 1 1 0

1 0 0 1 1 0

1 1 1 1 1 1

Из таблиц видно, что

функция 0 двойственна функции 1,

функция 1 двойственна функции 0,

функция x двойственна функции x,

функция x двойственна функции x ,

функция x1 ⋅ x2 двойственна функции x1 ∨ x2 ,

функция x1 ∨ x2 двойственна функции x1 ⋅ x2 .

Функция, двойственная самой себе, является

самодвойственной. Т.о. х и x являются самодвойственными

функциями.

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

( f * )* = ( f ( x1 ,…, x n )) * = f ( x1 ,…, x n ) = f ( x1 ,…, x n ) ,

т.е. исходная функция f является двойственной к f*.

Пусть функция ϕ(x1,…,xn) реализуется формулой F.

Спрашивается, какой вид имеет формула F*, реализующая

функцию ϕ*(x1,…,xn).

Обозначим через x1,…,xn все различные символы переменных,

встречающиеся в множествах ( x11 ,..., x1n1 ),..., ( xm1 ,..., xmn m ) .

Теорема 4.1. Если

ϕ ( x1 ,..., xn ) = f ( f 1 ( x11 ,..., x1n1 ),..., f m ( xm1 ,..., xmnm )) , то

ϕ * ( x1 ,..., xn ) = f * ( f 1* ( x11 ,..., x1n1 ),..., f m ( xm1 ,..., xmn m )) .

*

Доказательство.

16

ϕ * ( x1 ,…, xn ) = ϕ ( x1 ,…, xn ) =

= f ( f1 ( x11 ,…, x1n1 ),…, f m ( xm1 ,…, xmnm )) =

= f ( f1 ( x11 ,…, x1n1 ),..., f m ( xm1 ,…, xmnm )) =

f ( f1* ( x11 ,..., x1n1 ),..., f m ( xm1 ,..., xmnm )) =

*

f * ( f1* ( x11 ,..., x1n1 ),..., f m ( xm1 ,..., xmnm ))).

*

Из теоремы вытекает

Принцип двойственности. Если формула F=F(f1,…,fm) реализует

функцию ϕ(x1,…,xn), то формула F*=F(f1*,…,fm*) полученная из F

заменой функций f1,…,fm на f1*,…,fm*, реализует функцию

ϕ*(x1,…,xn).

Формулу F* будем называть формулой, двойственной к F.

Для формул над (0,1,∨,&,) принцип двойственности может быть

сформулирован так: для получения формулы F*, двойственной к

формуле F, нужно в формуле F всюду заменить 0 на 1, 1 на 0, & на

∨, ∨ на &.

Пример 4.1.

Пусть F1(f1)=f1(х1,x2)=x1&x2.

Тогда F1*(f1)=F1(f1*)=f1*(x1,x2)=x1∨ x2.

Пусть

F2 ( f1 , f 2 , f 3 ) = f 2 ( f 1 ( x1 , x2 ), f 1 ( f 3 ( x1 ), f 3 ( x2 ))) = x1 x2 ∨ x1 x2 .

Здесь f1 – конъюнкция, f2 – дизъюнкция, f3 – отрицание.

Тогда

F2* ( f1 , f 2 , f 3 ) = F2 ( f1* , f 2* , f 3* ) =

= f 2* ( f1* ( x1 , x2 ), f 1* ( f 3* ( x1 ), f 3* ( x2 ))) = ( x1 ∨ x2 ) & ( x1 ∨ x2 )

Из принципа двойственности вытекает, что если

F(f1,…,fm) =Φ(g1,…,gn), то F*(f1,…,fm) = Φ*(g1,…,gn)

Пример 4.2.

Из равенства x1 x2 = ( x1 ∨ x2 ) вытекает равенство x1 ∨ x2 = x1 x2 .

Принцип двойственности позволяет почти в два раза сокращать

усилия на вывод равенств при рассмотрении свойств булевых

функций.

Совершенная дизъюнктивная нормальная форма (СДНФ).

Введем обозначения xo= x , x1=x. Пусть δ∈{0,1}. Тогда

⎧ x, δ = 1

xδ = ⎨

⎩ x , δ = 0.

Очевидно, что xδ=1 ⇔ x=δ.

δ δ δ

Определение. Выражение вида x1 1 x2 2 ...xn n называется

элементарной конъюнкцией.

Членами конъюнкции являются либо сами переменные x1,…,xn,

либо их отрицания.

Пример 4.3.

x1 x2 , x3 x4 , x1 x2 x4 x5 .

Определение. Элементарная конъюнкция, в которую включены

все переменные, называется основной элементарной конъюнкцией.

Пример 4.4.

n = 5; x1 x2 x3 x4 x5 , x1 x2 x3 x4 x5 .

Лемма 4.1.

δ δ δ ⎧1, если δ 1 = x1 ,...δ n = xn ,

x1 1 x2 2 ... xn n = ⎨

⎩0, если δ i ≠ xi хотя бы для одного i.

Доказательство

Пусть δ1=x1,…, δn=xn. Тогда

δ δ x x

x1 1 xn n = x1 1 xn n = 1 1 = 1.

Пусть δ k ≠ xk , для некоторого k: 1 ≤ k ≤ n . Тогда

δ δ δ

x1 1 xk k xn n = x1x1 xkx k xn n = 1 1 ⋅ 0 ⋅ 1 1 = 0.

x

Определение. Формула Φ = k1 ∨ k 2 ∨ ... ∨ k m , где ki-

элементарные конъюнкции, называется дизъюнктивной

нормальной формой (ДНФ). Если все ki являются основными

элементарными конъюнкциями, то ДНФ называется совершенной

(СДНФ).

Пример 4.5.

n = 3; x1 x2 ∨ x1 x3 ∨ x2 x3 − ДНФ,

x1 x2 x3 ∨ x1 x2 x3 − СДНФ.

Разложение булевых функций по переменным.

Теорема 4.2. (о разложении функций по переменным). Каждую

функцию алгебры логики f(x1,…,xn) при любом m,1≤m≤n, можно

представить в следующей форме:

δ δ

f ( x1 ,..., xm , xm + 1 ,..., xn ) = ∨ x1 1 xmm f (δ 1 ,...,δ m , xm + 1 ,..., xn ) ,

δ 1 ,..,δ m

(4.1)

где дизъюнкция берется по всем возможным наборам

значений переменных x1,…,xm.

Это представление называется разложением функции по m

переменным x1,…,xm.

Доказательство. Теорема доказывается подстановкой в обе

части равенства (4.1) произвольного набора ( α1 ,...,α m , α m + 1 ,...,α n )

всех n переменных.

Левая часть (4.1) дает f(α1,…,αn).

Правая -

δ δ

∨ α 1 1 α mm f (δ 1 ,..., δ m ,α m +1 ,...α n ) =

δ 1 ,...,δ m

α α

= α 1 1 α mm f (α 1 ,...,α m ,α m +1 ,...,α n ) = f (α 1 ,...,α n )

В качестве следствия получим два специальных случая

разложения.

Следствие 4.1. Разложение по k-ой переменной

f ( x1 ,..., xk −1 , xk , xk + 1 ,..., xn ) =

= xk f ( x1 ,..., xk −1 ,1k , xk + 1 ,..., xn ) ∨ xk f ( x1 ,..., xk −1 ,0, xk + 1 ,..., xn )

Следствие 4.2. Разложение по всем n переменным

δ δ

f ( x1 ,..., xn ) = ∨ x1 1 xn n f (δ 1 ,..., δ n ). Но f (δ 1 ,..., δ n ) = 0

δ 1 ,...,δ n

либо f (δ 1 ,…, δ n ) = 1. Cледовательно, при f ( x1 ,..., xn ) ≡ 0 оно

/

может быть преобразовано к виду

δ δ δ δ

∨ x1 1 xn n f (δ 1 ,..., δ n ) = ∨ x1 1 xn n , т.е.

δ 1 ,...,δ n δ 1 ,...,δ n

f (δ 1 ,...,δ n ) = 1

δ δ

f ( x1 ,..., xn ) = ∨ x1 1 xn n - СДНФ.

δ 1 ,...,δ n

f (δ 1 ,...,δ n ) = 1

Отсюда вытекает порядок построения СДНФ по функции,

заданной таблицей.