67606
Разложение булевых функций по переменным
Лекция
Математика и математический анализ
Это представление называется разложением функции по m переменным x1xm. Разложение по одной переменной 1 Разложение по всем n переменным 2 При Опр. Это разложение называется совершенной дизъюнктивной нормальной формой представления функции fx1xn.
Русский
2014-09-12
174.5 KB
8 чел.
Лекция №15
Разложение булевых функций по переменным.
Возникают вопросы:
1) всякая ли функция может быть записана с помощью формулы?
2) как это сделать?
Совершенная дизъюнктивная нормальная форма.
Обозначим, где равен либо 0, либо 1. Тогда
.
Поскольку
,
то x=1 x=.
Теорема о разложении функции по переменным || Каждую функцию Булевой алгебры при любом можно представить в следующей форме:
,
где дизъюнкция берется по всем наборам значений переменных . ||
опр || Это представление называется разложением функции по m переменным x1,…xm.||
Доказательство.
- Рассмотрим произвольный набор значений . Левая часть равенства имеет вид . Правая часть
(в сумме только одно произведение отлично от нуля: то в котором )
.
Теорема доказана.
Разложение по одной переменной
1)
Разложение по всем n переменным
2)
При
Опр. Это разложение называется совершенной дизъюнктивной нормальной формой представления функции f(x1,…,xn).
Теорема || Каждая функция алгебры логики может быть выражена в виде формулы, содержащей только отрицание, конъюнкцию и дизъюнкцию. ||
Доказательство ||
1) Если , то
2) Если , то
Примеры
1)
|
x1 |
x2 |
f |
|
0 |
0 |
1 |
|
0 |
1 |
1 |
|
1 |
0 |
0 |
|
1 |
1 |
1 |
(это СДНФ; теперь преобразуем)
2) Следующий пример. Дана таблица
|
x1 |
x2 |
x3 |
f |
|
0 |
0 |
0 |
1 |
|
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
0 |
|
0 |
1 |
1 |
0 |
|
1 |
0 |
0 |
0 |
|
1 |
0 |
1 |
1 |
|
1 |
1 |
0 |
0 |
|
1 |
1 |
1 |
1 |
3)
|
x1 |
x2 |
x3 |
x4 |
f |
|
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
1 |
1 |
|
0 |
0 |
1 |
0 |
0 |
|
0 |
0 |
1 |
1 |
0 |
|
0 |
1 |
0 |
0 |
1 |
|
0 |
1 |
0 |
1 |
0 |
|
0 |
1 |
1 |
0 |
0 |
|
0 |
1 |
1 |
1 |
0 |
|
1 |
0 |
0 |
0 |
1 |
|
1 |
0 |
0 |
1 |
1 |
|
1 |
0 |
1 |
0 |
0 |
|
1 |
0 |
1 |
1 |
0 |
|
1 |
1 |
0 |
0 |
0 |
|
1 |
1 |
0 |
1 |
0 |
|
1 |
1 |
1 |
0 |
1 |
|
1 |
1 |
1 |
1 |
0 |
4) Аналитический способ
5)
Пусть . Согласно теореме двойственности
Это разложение называется совершенной конъюнктивной нормальной формой.
Примеры
1)
2)
|
x1 |
x2 |
f |
|
0 |
0 |
0 |
|
0 |
1 |
1 |
|
1 |
0 |
1 |
|
1 |
1 |
0 |
3)
|
x1 |
x2 |
x3 |
f |
|
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
1 |
|
0 |
1 |
0 |
1 |
|
0 |
1 |
1 |
1 |
|
1 |
0 |
0 |
1 |
|
1 |
0 |
1 |
0 |
|
1 |
1 |
0 |
1 |
|
1 |
1 |
1 |
1 |
4)
|
x1 |
x2 |
x3 |
x4 |
|
|
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
1 |
1 |
|
0 |
0 |
1 |
0 |
0 |
|
0 |
0 |
1 |
1 |
0 |
|
0 |
1 |
0 |
0 |
1 |
|
0 |
1 |
0 |
1 |
0 |
|
0 |
1 |
1 |
0 |
0 |
|
0 |
1 |
1 |
1 |
0 |
|
1 |
0 |
0 |
0 |
1 |
|
1 |
0 |
0 |
1 |
1 |
|
1 |
0 |
1 |
0 |
0 |
|
1 |
0 |
1 |
1 |
0 |
|
1 |
1 |
0 |
0 |
0 |
|
1 |
1 |
0 |
1 |
0 |
|
1 |
1 |
1 |
0 |
1 |
|
1 |
1 |
1 |
1 |
0 |
5)
А также другие работы, которые могут Вас заинтересовать | |||
| 77978. | Возможности Delphi для ввода и отображения дат и времен. Таймер | 193.5 KB | |
| Таймер Компонент Delphi Timer очень простой компонент который не виден на экране но тем не менее Delphi Timer выполняет очень важные функции в программе. Delphi Timer позволяет вводить необходимые задержки между выполнением тех или иных действий. Компонент Timer имеет всего четыре свойства и одно событие и работать с компонентом Delphi Timer очень просто. Свойство Назначение Enbled Включение-выключение таймера Intervl Интервал срабатывания в миллисекундах Nme Имя компонента в программе Tg Произвольный числовой параметр Помещаем... | |||
| 77979. | Графические файлы в Delphi | 63 KB | |
| У ряда объектов из библиотеки библиотеки визуальных компонент есть свойство Cnvs канва которое предоставляет простой путь для рисования на них. Cnvs является в свою очередь объектом объединяющим в себе поле для рисования карандаш Pen кисть Brush и шрифт Font. Cnvs обладает также рядом графических методов: Drw TextOut rc Rectngle и др. Используя Cnvs вы можете воспроизводить на форме любые графические объекты картинки многоугольники текст и т. | |||
| 77980. | Итерационные циклы | 47 KB | |
| Для организации итерационных циклов используются операторы цикла с предусловием цикл ПОКА и цикла с постусловием цикл ДО. Эти операторы не задают закон изменения параметра цикла поэтому необходимо перед циклом задавать начальное значение параметра с помощью оператора присваивания а внутри цикла изменять текущее значение этого параметра. Циклы с предусловием используются тогда когда выполнение цикла связано с некоторым логическим условием. Оператор цикла с предусловием имеет две части: условие выполнения цикла и тело цикла. | |||
| 77981. | Кнопки. Диалоговые окна | 67.5 KB | |
| Виды кнопок Кнопки TButton широко используются для управления программами представляет сабой командную кнопку на странице Stndrd. Определяет цвет стиль размер шрифта прилож Cncel: Boolen; Если имеет значение True событие OnClick кнопки возникает при нажатии клавиши Esc Defult: Boolen; Если имеет значение True событие OnClick кнопки возникает при нажатии клавиши Enter События OnClick Возникает при нажатии на кнопке В отличие от большинства других видимых компонентов кнопка TButton является компонентом самой Windows и... | |||
| 77982. | Комбинированные типы | 31.5 KB | |
| В отличии от массивов записи могут объединять значения различных типов и поэтому являются наиболее гибким механихмом построения данных. Запись состоит из фиксированного числа компонентов называемых полями записи. Что бы можно было ссылаться на тот или иной компонент записи поля именуются. Структура объявления типа записи такова: имя типа =RECORD список полей END Здесь: имя типа правильный идентификатор; RECORDEND зарезервированные словазапись конец; список полей этот список представляет собой последовательность разделов записи... | |||
| 77983. | Компоненты для создания приложений БД | 183 KB | |
| Для использования компонента TDBText нужно: указать в свойстве property DtSource: TDtSource; имя соответствующего компонента TDtSource связанного с НД; указать в параметре property DtField: String; имя поля. Поэтому для TDBEdit необходимо указывать свойства property DtSource: TDtSource; имя компонента DtSource определяющего НД; property DtField: string; имя редактируемого поля; property RedOnly: Boolen; если содержит True значение поля доступно только для чтения если Flse значение поля можно изменять. Свойство property Text:... | |||
| 77984. | Компоненты переключатели | 57.5 KB | |
| TCheckBox независимый переключатель. Независимый переключатель TCheckBox используется для того чтобы пользователь мог указать свое решение типа Да Нет или Да Нет Не совсем в последнем случае в окошке компонента устанавливается флаг выбора но само окошко закрашивается серым цветом. В составе диалогового окна может быть несколько компонентов TCheckBox. Свойства и методы компоненты TCheckBox. | |||
| 77985. | Конструкторы и деструкторы | 28.5 KB | |
| Конструкторы — это специальные методы, создающие и инициализирующие объект. Объект создается выделением для него области в динамически распределя емой памяти. Объявление конструктора выглядит так же, как объявление процедуры, но предваряется ключевым словом constructor. В качестве имени конструктора обычно задают имя Create. | |||
| 77986. | Массивы, одномерные массивы | 46 KB | |
| Каждый элемент массива имеет уникальный номер индекс с помощью которого к элементу массива можно обращаться как к переменной. Имя массива идентификатор составляют тем же правилам что и для переменных. Количество индексов определяет размерность массива. Математическим эквивалентом одномерного массива является вектор. | |||
