Лекции Русакова (1021002), страница 19

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 19)

Теоремадоказана.Определение.Правая часть равенства (3) называется совершенной дизъюнктивнойнормальной формой (кратко СДНФ) функции f(x1, x2,…, xn).Замечание.СДНФ существует только для тех булевых функций, которые неявляются константами, равными нулю.Определение.178Правая часть равенства (4) называется совершенной конъюнктивнойнормальной формой (СКНФ) функции f(x1, x2,…, xn).Замечание.СКНФ существует только для тех булевых функций, которые неявляются константами, равными единице.Определение.Конъюнкция всех аргументов функции (с отрицанием и без отрицания)называется полной и обозначается буквой K с соответствующим индексом.Индексом в обозначении служит номер набора или двоичное число, а такжесоответствующееемудесятичное,полученноепризаменекаждойпеременной xi символом 1, а переменной  xi – символом 0.Определение.Дизъюнкция всех аргументов функции (с отрицанием и без отрицания)называетсяполнойиобозначается(влитературе)буквойDссоответствующим индексом.

Индексом служит инверсионный номер набораили двоичное число, а также соответствующее ему десятичное, полученноепри замене каждой переменной xi символом 0, а переменной  xi – символом1.Примеры.1. x1x2 – номер набора –112 = 310, полная конъюнкция обозначается K3.2.

x1 x2 x3 – номернабора – 0102 = 210,обозначается K2.179полнаяконъюнкция3. x1∨ x2 – номер инверсионного набора – 002 – 010, полная дизъюнкцияобозначается D0.4. x1 ∨ x2 ∨ x3 – номер инверсионного набора – 1012 – 510, полнаядизъюнкция обозначается D5.Определение.Полная конъюнкция, принимающая значение 1 только на одном набореаргументов, соответствующем её индексу, и значение 0 на всех остальныхнаборах,называетсятакжеконституэнтой(образующей)илихарактеристической функцией единицы.Определение.Полная дизъюнкция, принимающая значение 0 только на одном набореаргументов, соответствующем её индексу, и значение 1 на всех остальныхнаборах,называетсятакжеконституэнтой(образующей)илихарактеристической функцией нуля.Замечание.Значение булевой функции для конкретных значений аргументовудобно обозначить символом α с индексом в виде десятичного числа,соответствующего двоичному набору аргумента, например,f(1,1) = α3,f(1,0,1) = α5.Примеры.С учётом введённых определений булеву функцию f(x1, x2) можнозаписать {с учетом разложения в СДНФ или СКНФ} в следующем виде:3f ( x1 , x2 ) =x1 x2 f (1,1) ∨ x1 x2 f (1,0) ∨ x1x2 f (0,1) ∨ x1 x2 f (0,0) =∨ K iα i ;i =0180f ( x1 , x2 ) = ( x1 ∨ x2 ∨ f (0,0))( x1 ∨ x2 ∨ f (0,1)) ∨ ( x1 ∨ x2 ∨ f (1,0)) ⋅3= &( Di ∨ α i )( x1 ∨ x2 ∨ f (1,1))i =0.Замечание.Приведенный пример показывает, каким образом можно перейти оттабличногопредставлениябулевойфункциикеёаналитическомупредставлению.

При табличном представлении функции задаются еёзначения αi для каждого набора аргументов, определяемого индексом i. Таккак в силу определения операции конъюнкции имеем 0⋅Ki = 0 и 1⋅Ki = Ki, тодля представления функции в виде СДНФ нужно выписать дизъюнкцию всехтех конституэнт единицы Ki, для которых αi = 1. Учитывая также, что0∨Di=Di и 1∨Di=1, СКНФ получается как конъюнкция всех тех конституэнтнуля Di, для которых значение функции αi равно 0.5.03.

Законы двойственности.Определение.Учитывая определённую симметрию операций ∧ и ∨ в аксиоматикеалгебры Буля логических высказываний и операций, операции ∧ и ∨называются двойственными.Определение.Формулыи*называются двойственными, если одна получаетсяиз другой заменой каждой операции на двойственную.Примеры.1811. ( X ∨ Y ) & Z двойственна X & Y ∨ Z .2. X ∨ Y & ( X ∨ Y & Z ) двойственна X & Y ∨ X & Y ∨ Z .3.

X & Y ∨ Y & Z ∨ U & V двойственна ( X ∨ Y ) & (Y ∨ Z ) & (U ∨ V ) .Замечание.Как для операций, так и для формул отношение двойственностивзаимно, то есть если*двойственна, то и, наоборот,двойственна*.Лемма.Если формулы(X1, X2,…, Xn) и(X1, X2,…, Xn) двойственны,*аX1, X2,…, Xn – все входящие в них элементарные высказывания, то(X1, X2,…, Xn) равносильна* ( X 1 , X 2 ,..., X n ).Доказательство:Доказательство непосредственно следует из законов де Моргана.Следствие из леммы.Частным случаем леммы являются следующие соотношения:X 1 ∨ X 2 ∨ ... ∨ X n = X 1 ∧ X 2 ∧ ... ∧ X n ;(5)X 1 ∧ X 2 ∧ ... ∧ X n = X 1 ∨ X 2 ∨ ... ∨ X n .(6)Они являются обобщением законов де Моргана и называются законамиКлода Шеннона.Задание.Доказать законы Клода Шеннона и лемму.182Теорема (закон двойственности).иЕслиравносильны, то и двойственные им формулыи**также равносильны.Доказательство:(X1, X2,…, Xn) иПустьа(X1, X2,…, Xn) – равносильные формулы,X1, X2,…, Xn – входящие в них элементарные высказывания.

Тогда, в силулеммы,( X 1 , X 2 ,..., X n ) , а(X1, X2,…, Xn) равносильна**(X1, X2,…, Xn)( X 1 , X 2 ,..., X n ) .равносильнаИз равносильности формулследует равносильность формул(X1, X2,…, Xn) и( X 1 , X 2 ,..., X n ) и(X1, X2,…, Xn)( X 1 , X 2 ,..., X n ) , так(X1, X2,…, Xn) икак в силу определения равносильности(X1, X2,…, Xn)принимают одинаковые значения при любых значениях переменныхX1, X2,…, Xn,а,следовательно, и при значенияхСледовательно, формулы( X 1 , X 2 ,..., X n )формуле( X 1 , X 2 ,..., X n ) , а формула( X 1 , X 2 ,..., X n )итакже(X1, X2,…, Xn) равносильнаравносильны, далее, в силу леммы формулаформулеX 1 , X 2 ,..., X n .*(X1, X2,…, Xn) равносильна*( X 1 , X 2 ,..., X n ) .

Следовательно, формулы(X1, X2,…, Xn) и*(X1, X2,…, Xn) равносильны между собой, что и требовалось доказать.*Замечание.1. Если, применяя к формуледистрибутивные преобразования наосновании первого дистрибутивного закона мы получим формулу183, топереход от двойственной формулы*к двойственной формуле*осуществляется дистрибутивными преобразованиями на основании второгодистрибутивного закона.2.

Переход откназывается преобразованием, двойственным**преобразованию, переводящемув.Теорема. (Формулы разложения Клода Шеннона.)Для любой булевой функции f(x1, x2,…, xn) имеют место следующиеразложения по переменным x1, x2,…, xk {1≤ k ≤ n}:1.∨f(x1, x2,…, xn) =( a1 ,a2 ,...,an )x1a1 x2a2 ...akxk f (a1 ,..., ak , xk +1 ,..., xn ),(7)где 1) 1≤ k ≤ n;2) дизъюнкция берётся по всем наборам (a1, a2,…, ak), {ai∈{0,1}},i = 1, k .Это разложение называется дизъюнктивным разложением булевойфункции f(x1, x2,…, xn) по переменным x1, x2,…, xk {1≤ k ≤ n}.f ( x1 , x2 ,..., xn ) =∧( a1 ,a2 ,...,an )( x1a1 ∨ x2a2 ∨ ... ∨ xkak ∨ f (a1 , a2 ,..., ak , xk +1 ,..., xn )),(8)где 1) 1≤ k ≤ n;2) конъюнкция берётся по всем наборам (a1, a2,…, ak), {ai∈{0,1}},i = 1, kЭто разложение называется конъюнктивным разложением булевойфункции f(x1, x2,…, xn) по переменным x1, x2,…, xk , {1≤ k ≤ n}.Оба соотношения (7) и (8) также называются формулами разложенияКлода Шеннона.184Доказательство:При k = 1 формулы (7) и (8) имеют следующий вид:=f ( x1 , x2 ,..., xn ) x1 f (1, x2 ,..., xn ) ∨ x1 f (0, x2 ,..., xn ) ;(9)( x1 ∨ f (1, x2 ,..., xn ))( x1 ∨ f (0, x2 ,..., xn )) .f ( x1 , x2 ,..., xn ) =(10)Докажем формулу (9).При x1 = 1 имеем:f (1, x2 ,..., xn ) =1 ⋅ f (1, x2 ,..., xn ) ∨ 0 ⋅ f (0, x2 ,..., xn )0– равенство очевидно.При x1 = 0 имеем:f (0, x2 ,..., xn ) = 0 ⋅ f (1, x2 ,..., xn ) ∨ 1 ⋅ f (0, x2 ,..., xn )0– равенство очевидно.Таким, образом доказана справедливость соотношения (9).

Подобнымобразом можно разложить функцию по другой переменной, напримерпо x2. Тогда для формулы (9) это разложение имеет вид:f ( x1 , x2 ,..., xn ) =x1 x2 f (1,1,..., xn ) ∨ x1 x2 f (1,0,..., xn ) ∨∨ x1 x2 f (0,1,..., xn ) ∨ x1 x2 f (0,0,..., xn ) .(11)Подставляя, где записано разложение по x1, значение x2=1 и затем x2=0,легко убедится в справедливости и соотношения (11). Если продолжитьпроцесс разложения по остальным переменным (до k включительно(1≤ k ≤ n)), то получим соотношение (7). Аналогично доказывается формула(8).

Теорема доказана.Замечания.1. При k = n дизъюнктивное разложение булевой функции {формула(7)} имеет вид:f ( x1 , x2 ,..., xn )= x1 x2 ⋅ ... ⋅ xn−1 xn f (1,1,...,1,1) ∨∨ x1 x2 ⋅ ... ⋅ xn−1 xn f (1,1,...,1,0) ∨185………………………………..(12)∨ x1 x2 ⋅ ... ⋅ xn−1 xn f (1,0,...,0,0) ∨∨ x1 x2 ⋅ ... ⋅ xn−1 xn f (0,0,...,0,0) ,а конъюнктивное разложение {формула (8)} имеет вид:f ( x1 , x2 ,..., xn ) = ( x1 ∨ x2 ∨ ... ∨ xn−1 ∨ xn ∨ f (1,1,...,1,1)) ⋅⋅( x1 ∨ x2 ∨ ... ∨ xn−1 ∨ xn ∨ f (1,1,...,1,0)) ⋅……………………………………….(13)⋅( x1 ∨ x2 ∨ ... ∨ xn−1 ∨ xn ∨ f (1,0,...,0,0)) ⋅⋅( x1 ∨ x2 ∨ ...

∨ xn−1 ∨ xn ∨ f (0,0,...,0,0)) .2. Из полученных соотношений видно, что дизъюнктивное разложениебулевой функции при k = n { см. формулу (12)} есть не что иное, каксовершенная дизъюнктивная нормальная форма {см. формулу (3)}, аконъюнктивное разложение булевой функции при k = n {см. формулу (13)}есть совершенная конъюнктивная нормальная форма {см. формулу (4)}.Таким образом, СДНФ и СКНФ являются частными случаями равенств (7) и(8), являющихся соответственно дизъюнктивным иконъюнктивнымразложениями булевой функции f(x1, x2,…, xn) по переменным x1, x2,…, xk ,{1≤ k ≤ n}.5.04.

Характеристики

Список файлов лекций