Редактирование: Основы Кибернетики, 01 лекция (от 09 февраля)
Материал из eSyr's wiki.
Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
| Текущая версия | Ваш текст | ||
| Строка 16: | Строка 16: | ||
Что такое функция алгебры логики, как мы их будем задавать. Рассмотрим представления и разложения других функций. | Что такое функция алгебры логики, как мы их будем задавать. Рассмотрим представления и разложения других функций. | ||
| - | Функцция от н переменных -отображение единичного | + | Функцция от н переменных -отображение единичного н-мерного куба в одномерный куб: |
ФАЛ f(x1...xn): Bn -f-> B | ФАЛ f(x1...xn): Bn -f-> B | ||
| - | Чаще всего будем задавать | + | Чаще всего будем задавать ВАЛ таблицей (линейной таблицей T(f)): |
x1 | x1 | ||
... | ... | ||
| Строка 92: | Строка 92: | ||
P2(n) – все ФАЛ от н переменных | P2(n) – все ФАЛ от н переменных | ||
|P2(n)| = 2^2^n | |P2(n)| = 2^2^n | ||
| - | Все | + | Все ф-ции от 1 перем: |
x1 | x1 | ||
x1 | x1 | ||
| Строка 108: | Строка 108: | ||
0 | 0 | ||
1 | 1 | ||
| - | + | Ф-ции от 2 перем: | |
x1 | x1 | ||
x2 | x2 | ||
| Строка 155: | Строка 155: | ||
0 | 0 | ||
0 | 0 | ||
| - | Существенно зависят от 2 | + | Существенно зависят от 2 перем 10 функций |
//приведена функция голосования - H | //приведена функция голосования - H | ||
| - | Другие варианты табличного задания: характеристическое множество. Обозн множество всех | + | Другие варианты табличного задания: характеристическое множество. Обозн множество всех 3тех наборов, на котороых функция равна единица (либо его дополнение – множество тех наборов, на которых функция равна 0) |
Nf = {alpha in Bn: f(alpha)=1} | Nf = {alpha in Bn: f(alpha)=1} | ||
NH = {(011), (101), (110), (111)} | NH = {(011), (101), (110), (111)} | ||
| Строка 169: | Строка 169: | ||
Чаще функции будем задавать формулами. | Чаще функции будем задавать формулами. | ||
| - | Из функций конъюнкции, отрицания, дизъюнкции и | + | Из функций конъюнкции, отрицания, дизъюнкции и др. можно строить формулы. Причём эти функции обладают алгебр свойствами: коммутативность, ассоциативность, дистрибутивность. |
о – коммутативная операция тогда и только тогда, когда х1 о х2 = х2 о х1, о in {&, v, +, ~} | о – коммутативная операция тогда и только тогда, когда х1 о х2 = х2 о х1, о in {&, v, +, ~} | ||
| Строка 208: | Строка 208: | ||
Совершенная КНФ <=> ранг каждой (любой) дизъюнкции Ij = n. | Совершенная КНФ <=> ранг каждой (любой) дизъюнкции Ij = n. | ||
| - | + | Предст функции – предст в виде объед. точек. | |
f(x1...xn) = V σ=&sigma1...σn in Nt xσ11 ... xσnn - совершенная ДНФ | f(x1...xn) = V σ=&sigma1...σn in Nt xσ11 ... xσnn - совершенная ДНФ | ||
| Строка 254: | Строка 254: | ||
1 | 1 | ||
0 | 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) | |
Сокращённая ДНФ и способы её построения | Сокращённая ДНФ и способы её построения | ||
| Строка 295: | Строка 295: | ||
a = K1 v .... v Kt – нетривиальная ДНФ <=> любой 1 <= i != j <=t Kki не принадлежит Nkj | a = K1 v .... v Kt – нетривиальная ДНФ <=> любой 1 <= i != j <=t Kki не принадлежит Nkj | ||
| - | Утверждение 2.1. Пусть a‘ - сокращённая ДНФ f‘, a‘‘ - сокращённая ДНФ f‘‘ и пусть неприводимая ДНФ a получается в результате раскрытия скобок и приведения подобных в a‘a‘‘ => a – сокр ДНФ f=f‘f‘‘ | + | Утверждение 2.1.Пусть a‘ - сокращённая ДНФ f‘, a‘‘ - сокращённая ДНФ f‘‘ и пусть неприводимая ДНФ a получается в результате раскрытия скобок и приведения подобных в a‘a‘‘ => a – сокр ДНФ f=f‘f‘‘ |
| - | Следствие. b = I1 & ... & Is – КНФ ФАЛ f и a – неприводимая ДНФ, | + | Следствие. b = I1 & ... & Is – КНФ ФАЛ f и a – неприводимая ДНФ, получ из b в результате раскрыттия скобок и приведенич подобных => a – сокр ДНФ |
| - | + | Док-во. Тождества приведения подобных: | |
x&~x = x&0 = 0, x v 0 = x | x&~x = x&0 = 0, x v 0 = x | ||
x1 v x1x2 = x1 – тождество поглощения | x1 v x1x2 = x1 – тождество поглощения | ||
| Строка 305: | Строка 305: | ||
K <= K‘ <=> K = K‘K‘‘ K v K‘ = K‘ v K‘K‘‘ = K‘‘ | K <= K‘ <=> K = K‘K‘‘ K v K‘ = K‘ v K‘K‘‘ = K‘‘ | ||
| - | 1. Достаточно доказать, что все простые импликанты f получатся при раскрытии скобок в нашем произведении a‘a‘‘.=> a – сокращённая ДНФ | + | 1.Достаточно доказать, что все простые импликанты f получатся при раскрытии скобок в нашем произведении a‘a‘‘.=> a – сокращённая ДНФ |
| - | 2. Пусть K – простая импликанта f=f‘f‘‘ => K – импликанта f‘, f‘‘. => существет простая импликанта K‘ ФАЛ f‘, существет простая импликанта K‘‘ ФАЛ f‘‘ | K‘ >=K, K‘‘ >= K | + | 2.Пусть K – простая импликанта f=f‘f‘‘ => K – импликанта f‘, f‘‘. => существет простая импликанта K‘ ФАЛ f‘, существет простая импликанта K‘‘ ФАЛ f‘‘ | K‘ >=K, K‘‘ >= K |
a‘ = K‘ v ... = f‘ | a‘ = K‘ v ... = f‘ | ||
a‘‘ = K‘‘ v ... = f‘‘ | a‘‘ = K‘‘ v ... = f‘‘ | ||
K‘K‘‘ v ... = K v ... = f | K‘K‘‘ v ... = K v ... = f | ||
| - | раз K‘ больше K, то чтобы перейти от K к K‘, нужно вычеркнуть какие-нибудь буквы в коньюнкции K. | + | раз K‘ больше K, то чтобы перейти от K к K‘, нужно вычеркнуть какие-нибудь буквы в коньюнкции K. |
Если K‘K‘‘ = 1, то K‘K‘‘ v... = f = 1 => K‘K‘‘ - импликанта f, состоит из тех же букв, что и K, а это простая импликация. Отсюда K = K‘K‘‘ так как если бы какая-то буква K не содержалась бы в K‘K‘‘, то K не была бы простой импликантой. ч. т. д. | Если K‘K‘‘ = 1, то K‘K‘‘ v... = f = 1 => K‘K‘‘ - импликанта f, состоит из тех же букв, что и K, а это простая импликация. Отсюда K = K‘K‘‘ так как если бы какая-то буква K не содержалась бы в K‘K‘‘, то K не была бы простой импликантой. ч. т. д. | ||
| Строка 324: | Строка 324: | ||
Следствие. a‘ - ДНФ f и a – неприводимая ДНФ, которая получается из a‘ всевозможными расширениями и последующим приведением подобных. Тогда a – сокращённая ДНФ. | Следствие. a‘ - ДНФ f и a – неприводимая ДНФ, которая получается из a‘ всевозможными расширениями и последующим приведением подобных. Тогда a – сокращённая ДНФ. | ||
| - | + | Док-во. Любую простую импликанту можно получить из любой ДНФ путём расширения. Если мы получим все простые импликанты таким способом, тогда все непростые импликанты поглотим. | |
| - | 1. Достаточно доказать, чот любая неприводимая ДНФ a, не имеющая строгих расширений, действительно является строгой ДНФ. a содержит все простые импликанты. Пусть a (x1...xn) реализует f, пусть K – простая импликанта f, которая не вошла в a. | + | 1.Достаточно доказать, чот любая неприводимая ДНФ a, не имеющая строгих расширений, действительно является строгой ДНФ. a содержит все простые импликанты. Пусть a (x1...xn) реализует f, пусть K – простая импликанта f, которая не вошла в a. |
K – множество тех ЭК от x1...xn, ЭК является импликантой f, но не является импликантой ни одной элементарной конъюнкцией из ДНФ a. // нет ЭК ранга n | K – множество тех ЭК от x1...xn, ЭК является импликантой f, но не является импликантой ни одной элементарной конъюнкцией из ДНФ a. // нет ЭК ранга n | ||
| Строка 334: | Строка 334: | ||
=> существует переменная xi, которая не входит в k | => существует переменная xi, которая не входит в k | ||
| - | k&~xi не | + | k&~xi не принаждлежит К => K‘ принадлежит a : K‘ >= ~xi&k и K‘ !>= k => K‘=~xi&k‘ и k‘>=k |
| - | k&xi не | + | k&xi не принаждлежит К => K‘‘ принадлежит a : K‘‘ >= xi&k и K‘‘ !>= k => K‘=~xi&k‘‘ и k‘‘>=k |
применяя tOE получим, K‘ v K‘‘ v k‘k‘‘ >= k – должна входить в K ?! | применяя tOE получим, K‘ v K‘‘ v k‘k‘‘ >= k – должна входить в K ?! | ||
