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

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

Перейти к: навигация, поиск

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

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

Текущая версия Ваш текст
Строка 1: Строка 1:
-
Предыдущая лекция | [[Основы Кибернетики, лекция 02 (от 16 февраля)|Следующая лекция]]
+
== From Ebaums Inc to MurkLoar. ==
-
 
+
We at EbaumsWorld consider you as disgrace of human race.
-
= Единичный n-мерный куб. Функция алгебры логики (ФАЛ). Дизъюнктивная нормальная форма (ДНФ), Конъюктивная нормальная форма (КНФ), связанные с ними представления и разложения =
+
Your faggotry level exceeded any imaginable levels, and therefore we have to inform you that your pitiful resourse should be annihilated.
-
 
+
Dig yourself a grave - you will need it.
-
Пусть есть конечное множество 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
+
-
 
+
-
1
+
-
alpha2n-1
+
-
alphaf = (alpha0 ... alpha2n-1) – столбец значений ФАЛ
+
-
Прямоугольная таблица:
+
-
 
+
-
 
+
-
xk+1
+
-
0
+
-
1
+
-
 
+
-
1
+
-
 
+
-
 
+
-
 
+
-
0
+
-
0
+
-
 
+
-
1
+
-
 
+
-
 
+
-
 
+
-
 
+
-
 
+
-
 
+
-
 
+
-
x1
+
-
 
+
-
xn / xk
+
-
0
+
-
0
+
-
 
+
-
1
+
-
0
+
-
 
+
-
0
+
-
alpha0
+
-
 
+
-
 
+
-
alpha2n-k-1
+
-
 
+
-
 
+
-
 
+
-
 
+
-
 
+
-
 
+
-
 
+
-
1
+
-
 
+
-
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<sup>&sigma;<sub>1</sub></sup><sub>i<sub>1</sub></sub>&hellip;x<sup>&sigma;<sub>r</sub></sup><sub>i<sub>r</sub></sub>
+
-
1 <= i1 < i2 < &hellip; ir <= n
+
-
 
+
-
Элементарная дизъюнкция I = x<sup>&sigma;<sub>1</sub></sup><sub>i<sub>1</sub></sub> v &hellip; v x<sup>&sigma;<sub>r</sub></sup><sub>i<sub>r</sub></sub>
+
-
 
+
-
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
Личные инструменты
Разделы