Редактирование: Основы Кибернетики, 01 лекция (от 09 февраля)

Материал из eSyr's wiki.

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

Предыдущая лекция | [[Основы Кибернетики, лекция 02 (от 16 февраля)|Следующая лекция]]

= Единичный n-мерный куб. Функция алгебры логики (ФАЛ). Дизъюнктивная нормальная форма (ДНФ), Конъюктивная нормальная форма (КНФ), связанные с ними представления и разложения =

Пусть есть конечное множество A. Чаще всего мы будем рассматривать декартово произведение или декартову степень данного множества <math>a(1 + e^2 / 2)</math> <math>A^n = A \times A \times \ldots \times A = {a = (a_1, \ldots a_n), a_i \in A}</math>

== Примеры граней и способов их задания (записи) ==
N = B3;31 = Г(2,2,1) – грань размерности 2
N1 = B3;1,31,0 = Г(1,2,0) – грань размерности 1
N2 = B3;2,31,0 = Г(2,1,0)
N‘ = B3;1,2,30,0,0 = Г(0,0,0)
//нарисовать картинки с кубиками

С этими гранями связано понятие  КНФ и ДНФ.

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

Функцция от н переменных  -отображение единичного n-мерного куба в одномерный куб:
ФАЛ f(x1...xn): Bn -f-> B
Чаще всего будем задавать ФАЛ таблицей (линейной таблицей T(f)):
x1
...
xn
f
0

0
alpha0
0

1
alpha1

1
alpha2n-1
alphaf = (alpha0 ... alpha2n-1) – столбец значений ФАЛ
Прямоугольная таблица:

xk+1
0
1

0
0

xn / xk
0
0

1
0

0
alpha0

alpha2n-k-1

alpha2n-1
P2(n) – все ФАЛ от н переменных
|P2(n)| = 2^2^n
Все функции от 1 переменной:
x1
x1
~x1
0
1
0
0
1
0
1
1
1
0
0
1
Функции от 2 переменных:
x1
x2
&
v
+
~
->
|
|
V
0
0
0
0
0
1
1
1
1
0
1
0
1
1
0
1
1
0
1
0
0
1
1
0
0
1
0
1
1
1
1
0
1
1
0
0
Существенно зависят от 2 переменных 10 функций.

//приведена функция голосования - H

Другие варианты табличного задания: характеристическое множество. Обозн множество всех тех наборов, на которых функция равна единице (либо его дополнение – множество тех наборов, на которых функция равна 0)
Nf = {alpha in Bn: f(alpha)=1}
NH = {(011), (101), (110), (111)}

delta in Bn
xidelta(xi1 ... xin) – характеристическая функция множества наборов delta
Nxi(delta) = delta

Чаще функции будем задавать формулами.

Из функций конъюнкции, отрицания, дизъюнкции и других можно строить формулы. Причём эти функции обладают алгебраическими свойствами: коммутативность, ассоциативность, дистрибутивность.

о – коммутативная операция тогда и только тогда, когда х1 о х2 =  х2 о х1, о in {&, v, +, ~}
ассоциативность: (x1 o x2) o x3 = x1 o (x2 o x3), o in {&, v, +, ~}
дистрибутивность: о []: x1 o (x2 [] x3) = (x1 o x2) [] (x1 o x3) – операция о дистрибутивна по отношению к операции [] это верно для (&, v), (v, &), (&, +)

Сила операций: отрицание, конъюнкция, остальные.

Тождества приведения подобных:
отождествление двух переменных либо подстановка весто них константы:
x & x = x v x = x & 1 = x v 0 = x
x & ~x = x & 0 = 0
x v 1= x v ~x = 1
x +1 = ~x
x + ~x = 1

Понятие дизъюнктивной (конъюнктивной) нормальной формы и представление функций с помощью этих форму

x, ~x – буква
x0 = ~x, x1 = x

Элементарная конъюнкция (ЭК): конъюнкция букв различных булдевских переменных, K = x&sigma;1i1&hellip;x&sigma;rir
1 <= i1 < i2 < &hellip; ir <= n

Элементарная дизъюнкция I = x&sigma;1i1 v &hellip; v x&sigma;rir

x&sigma; = 1 <=> x = &sigma;
x&sigma; = 0 <=> x = ~&sigma;

Nk = Bn;i1&hellip;ir&sigma;1&hellip;&sigma;r
~NI = Bn;i1&hellip;ir~&sigma;1&hellip;~&sigma;r

Дизьюнкция ЭК – ДНФ, Конъюнкция ЭД – КНФ
K1 v ... v Kt – ДНФ
I1 & ... & Is – КНФ

Совершенная ДНФ <=> ранг каждой (любой) конъюнкции Ki = n.
Совершенная КНФ <=> ранг каждой (любой) конъюнкции Ij = n.

Представление функции – представление в виде объединённых точек.

f(x1...xn) = V &sigma;=&sigma1...&sigma;n in Nt  x&sigma;11 ... x&sigma;nn  - совершенная ДНФ
f(x1...xn) = & &sigma;=&sigma1...&sigma;n in Nt  x~&sigma;11 v ... v x~&sigma;nn  - совершенная КНФ

Разложение функции по части переменных: берём только часть переменных, и по этим переменных разлагаем функцию.
f(x1...xq, xq+1 ... xn) = V &sigma;‘ = (&sigma;1 ... &sigma;q) x&sigma;11 ... x&sigma;qq f(&sigma;‘, x‘‘)
      x‘             x‘‘

Что такое совершенная ДНФ:
x1
x2
x3
g
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
1
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
0
Совершенная ДНФ: ~x1~x2x3 v ~x1x2~x3 v ~x1x2x2 v x1~x2~x3 V x1~x2x3 v x1x2~x3 – объект 6 граней размерности 0
Совершенная КНФ:  (x1 v x2 v x3)(~x1 v ~x2 v ~x3)

Сокращённая ДНФ и способы её построения

Ng = N1 объединение N2 объединение N3 
g = K1 v K2 v K3

K1 = x1~x3 NK1 = N1
K3 = ~x1x2 NK3 = N3
K5 = ~x2x3 NK5 = N5

g =  x1~x3 v ~x1x2 v ~x2x3

f = a = K1 v ... v Kt
Nf = NK1 объединение NK2 ... объединение NKt
f = d = I1 & ... & Is
~Nf = ~NI1 объединение ... объединение ~Nis

K‘ : NK‘ >= Nk <+< K‘ получается из K удалением буква
Nk <= Nf
Nk – максимальная грань, если любое её расширение выводит за Nf
Сокр ДНФ f <=> Тл1 ююю Тле – все максимальные грани ФАЛ f

Nk <= Nf – К-импликанта f

(k -> f) == 1 K <= f

Nk - максимальная грань, тогда K – простая импликанта f

У функции g 6 граней N1..N6, которые являются максимальными, и 6 простых импликантов
a = K1    v K2   v   K3   v K4  v  K5  v   K6
    x1~x3 x2~x3 ~x1x2 ~x1x3  ~x2x3  x1~x2
Геометрия помогает при небольшом количестве переменных. Нужно иметь надёжный аппарат для построения сокращённых ДНФ.

Сов КНФ g = (~x1 v ~x2 v ~x3)(x1 v x2 v x3) = ~x1x2 v `x1x3 v x1~x2 v ~x2x3 v x1~x3 v x2~x3
x1~x1 = 0
0 v x1 = x1

a = K1 v .... v Kt – нетривиальная ДНФ <=> любой 1 <= i != j <=t Kki не принадлежит Nkj

Утверждение 2.1. Пусть a‘ - сокращённая ДНФ f‘, a‘‘ - сокращённая ДНФ f‘‘ и пусть неприводимая ДНФ a получается в результате раскрытия скобок и приведения подобных в a‘a‘‘ => a – сокр ДНФ f=f‘f‘‘

Следствие. b = I1 & ... & Is – КНФ ФАЛ f и a – неприводимая ДНФ, полученная из b в результате раскрытия скобок и приведения подобных => a – сокращенная ДНФ

Доказательство. Тождества приведения подобных:
x&~x = x&0 = 0, x v 0 = x
x1 v x1x2 = x1 – тождество поглощения

K <= K‘ <=> K = K‘K‘‘ K v K‘ = K‘ v K‘K‘‘ = K‘‘

1. Достаточно доказать, что все простые импликанты f получатся при раскрытии скобок в нашем произведении a‘a‘‘.=> a – сокращённая ДНФ
2. Пусть K – простая импликанта f=f‘f‘‘ => K – импликанта f‘, f‘‘. => существет простая импликанта K‘ ФАЛ f‘, существет простая импликанта K‘‘ ФАЛ f‘‘ | K‘ >=K, K‘‘ >= K
a‘ = K‘ v ... = f‘
a‘‘ = K‘‘ v ... = f‘‘
        K‘K‘‘ v ... = K v ... = f
раз K‘ больше K, то чтобы перейти от K к K‘, нужно вычеркнуть какие-нибудь буквы в коньюнкции K.

Если K‘K‘‘ = 1, то K‘K‘‘ v... = f = 1 => K‘K‘‘ -  импликанта f, состоит из тех же букв, что и K, а это простая импликация. Отсюда K = K‘K‘‘ так как если бы какая-то буква K не содержалась бы в K‘K‘‘, то K не была бы простой импликантой. ч. т. д.

tП: x1 v x1x2 = x1
tOE: ~x11x2 v x1x3 = ~x1x2 v x1x3 v x2x3
~x1K2 v xK3 = ~x1K2 v x1K3 v K2K3

a |=tOE=>> a‘  - строгое расширение ДНФ a тогда и только тогда, когда в ДНФ a‘ есть ЭК, которые не содержатся ни в одной из элементарных конъюнкций a, то есть нельзя получить из ДНФ a‘ a только поглощениями.

Утверждение 2.2. ДНФ a сокращённая тогда и только тогда, когда она неприводимая и не имеет строгих расширений.

Следствие. a‘ - ДНФ f и a – неприводимая ДНФ, которая получается из a‘ всевозможными расширениями и последующим приведением подобных. Тогда a – сокращённая ДНФ.

Доказательство. Любую простую импликанту можно получить из любой ДНФ путём расширения. Если мы получим все простые импликанты таким способом, тогда все непростые импликанты поглотим.
1. Достаточно доказать, чот любая неприводимая ДНФ a, не имеющая строгих расширений, действительно является строгой ДНФ. a содержит все простые импликанты. Пусть a (x1...xn) реализует f, пусть K – простая импликанта f, которая не вошла в a.
K – множество тех ЭК от x1...xn, ЭК является импликантой f, но не является импликантой ни одной элементарной конъюнкцией из ДНФ a. // нет ЭК ранга n

K принадлежит K => K != пустое

k – ЭК из K, имеющая максимальный ранг. rank(k) < n

=> существует переменная xi, которая не входит в k

k&~xi не принадлежит К => K‘ принадлежит a : K‘ >= ~xi&k и K‘ !>= k => K‘=~xi&k‘ и k‘>=k
k&xi не принадлежит К => K‘‘ принадлежит a : K‘‘ >= xi&k и K‘‘ !>= k => K‘=~xi&k‘‘ и k‘‘>=k
применяя tOE получим, K‘ v K‘‘ v k‘k‘‘ >= k – должна входить в K ?!

|=tП=>> a‘‘ - неприводимая ДНФ
a !=  a‘‘

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Описание изменений:

Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

Получено с http://esyr.org/wiki/%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D1%8B_%D0%9A%D0%B8%D0%B1%D0%B5%D1%80%D0%BD%D0%B5%D1%82%D0%B8%D0%BA%D0%B8%2C_01_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_09_%D1%84%D0%B5%D0%B2%D1%80%D0%B0%D0%BB%D1%8F%29

Редактирование: Основы Кибернетики, 01 лекция (от 09 февраля)

Материал из eSyr's wiki.

Просмотры

Личные инструменты

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты

@@ Строка 206: / Строка 206: @@
 Совершенная ДНФ <=> ранг каждой (любой) конъюнкции Ki = n.
-Совершенная КНФ <=> ранг каждой (любой) дизъюнкции Ij = n.
+Совершенная КНФ <=> ранг каждой (любой) конъюнкции Ij = n.
 Представление функции – представление в виде объединённых точек.