Предыдущая страница реферата | 1  2  3  4  5  6  7 | Следующая страница реферата

2.1.2 Декартова степень произвольного множества.
Опр: [pic] - множество всевозможных упорядоченных наборов длины n , элементов множества А. [pic]

2.1.3 Определение булевой функции от n переменных.
Любое отображение [pic] - называется булевой функцией от n переменных, притом множество [pic]
[pic]

2.1.4 Примеры булевой функции.
1) [pic] логическая сумма (дизъюнкция).
2) [pic] логическое умножение (конъюнкция).
3) [pic] сложение по модулю два.
4) [pic] логическое следствие (импликация).
5) [pic] отрицание.

2.1.5 Основные булевы тождества.

1) [pic] (ассоциативность)

2) [pic] (коммутативность)

3) [pic] (свойство нуля)

4) [pic] (закон поглощения для 1)

5) [pic] (ассоциативность)

6) [pic] (коммутативность)

7) [pic] (свойство нуля по умножению)

8) [pic] (свойство нейтральности 1 по умножению)

9) [pic] (дистрибутивность)
10) [pic] (дистрибутивность 2)
11) [pic] (закон поглощения)
12) [pic] ( Законы
13) [pic] де Моргана)
14) [pic] (закон снятия двойного отрицания)
15) [pic] (tertium non datur – третьего не дано)
16) [pic] (ассоциативность)
17) [pic]
18) [pic]
19) [pic]
20) [pic]
21) [pic] (Свойства
22) [pic] идемпотентности)

2.2 Дизъюнктивные нормальные формы.

2.2.1 Основные определения.
[pic] - конечный алфавит из переменных.
Рассмотрим слово: [pic]
Экспоненциальные обозначения: [pic]
[pic] - элемент конъюнкции.
S – длина элемента конъюнкции.
ДНФ – дизъюнкция нескольких различных элементарных конъюнкций.
[pic]
Любая булева функция может быть представлена как ДНФ

2.2.2 Теорема о совершенной ДНФ.
Любая булева функция [pic] тождественно не равная 0 может быть разложена в ДНФ следующего вида:
[pic]

Опр: Носитель булевой функции [pic]
[pic].
Лемма: [pic]
1) [pic] это элементарно [pic]
2) [pic] возьмем набор [pic] а) [pic] б) [pic]
Доказательство: [pic], будем доказывать, что[pic].
1) Докажем, что [pic]. Возьмем [pic] он попадает в число суммируемых наборов и по нему будет проводиться сумирование.
[pic]
2) Докажем, что [pic]. Возьмем другой набор из [pic]
[pic]
Следовательно [pic]

2.2.3 Некоторые другие виды ДНФ.
Опр: [pic] - называется минимальной ДНФ, если она имеет [pic] - наименьшую возможную длину из всех ДНФ данной функции.

Опр: [pic] - называется тупиковой ДНФ, если из неё нельзя выбросить ни одного слагаемого с сохранением булевой функции.

(Легко понять, что любая минимальная ДНФ является тупиковой, а обратное не верно.)

Опр: К-мерной гранью называется такое подмножество [pic], которая является носителем некоторой элементарной конъюнкции длины: n-k.

Опр: Предположим дана функция [pic] и есть [pic]. Грань называется отмеченной, если она целиком содержится в носителе Т.

Опр: Максимальная грань – это такая грань, которая не содержится ни в какой грани более высокой размерности.

Предложение: Любую отмеченную грань можно вложить в максимальную грань.

Предложение: [pic]

Рекомендуем скачать другие рефераты по теме: вопросы и ответы, дипломная работа по юриспруденции.





Предыдущая страница реферата | 1  2  3  4  5  6  7 | Следующая страница реферата