Новиков Ф.А. Дискретная математика для программистов (860615), страница 27

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 27)

При этом тип узла дерева N определён следующимобразом: N = record i: 0..1;l,r : 1 N end record.Алгоритм 3.5 Вычисление значения функции по сокращённому дереву решенийВход: указатель ТN на корень дерева решений; массив х : array [1 ..п] of 0..1значений переменных.Выход: 0..1 — значение булевой функции,for г from 1 to п doif T.l = nil & T.r = nil thenreturn T.i { листовой узел — возвращаем значение }elseif ж [г] thenТ: = T.r { 1 — переход вправо }3.6. Представление булевых функций в программах139elseТ : =Т.1 { 0 — переход влево }end ifend ifend forДерево решений можно сделать ещё компактнее, если отказаться от древовидности связей, то есть допускать несколько дуг, входящих в узел. В таком случае мыполучаем бинарную диаграмму решений.

Бинарная диаграмма решений получается из бинарного дерева решений тремя последовательными преобразованиями:1. Отождествляются листовые узлы, содержащие 0 и содержащие 1.Пример На рис. 3.3, а показано исходное полное дерево решений для функции д, а на рис. 3.3, б — результат первого преобразования.2. В диаграмме выделяются изоморфные поддиаграммы и заменяются единственным их экземпляром.Пример На рис. 3.3, б видно, что два поддерева, корнями которых являютсяузлы г, находящиеся в середине, изоморфны. На рис. 3.3, в показан результатвторого преобразования.3. Исключаются узлы, обе исходящие дуги которых ведут в один узел.Пример На рис.

3.3, в видно, что крайние узлы г излишни — значениефункции от значения г не зависит. Они удаляются, а входящие в них дугипродолжаются до тех узлов, в которые вели дуги из узлов г. На рис. 3.3, гпоказан результат третьего преобразования, который является построеннойдиаграммой решений.Интерпретация бинарной диаграммы решений (вычислеиие значения функции)производится в точности так же, как и для дерева решений, то есть по алгоритму 3.5.Результат преобразования дерева решений в диаграмму решений существеннозависит от того, в каком порядке рассматриваются переменные при построенииисходного полного дерева решений.Пример На рис.

3.4 показаны последовательность преобразований и окончательная диаграмма решений для функции д в том случае, когда переменныерассматриваются в следующем порядке: у, х, z. Мы видим, что диаграмма нарис. 3.4, г компактнее диаграммы на рис. 3.3, г и вычисление значения функциид требует всего двух операций. Фактически, диаграмма на рис. 3.4 показывает,что функция д может быть реализована следующим условным выражением:if у thenelse -*х end if.140Глава 3. Булевы функцииОТСТУПЛЕНИЕПоследний разобранный пример свидетельствует, что иногда можно построить такое специальное представление функции, которое позволяет хранить меньше информации и приэтом производить вычисления быстрее, чем это в принципе возможно при использованииуниверсальных математических методов представления функций с помощью графиков(массивов) и формул (выражений).

Советуем читателям обдумать этот факт.КомментарииПрекрасным руководством по булевым функциям являются книги [11] и [10],в которых можно найти обширный дополнительный материал, в частности, опущенные за недостатком места более изощрённые алгоритмы построения, упрощения и минимизации дизъюнктивных нормальных форм. Все алгоритмы этойглавы являются программистским фольклором, обработанным автором. Краткое описание бинарных деревьев решений и много другого полезного материаламожно найти в книге [12].Упражнения3.1.

Доказать, что число булевых функций от п переменных, среди которыхк фиктивных, равно 2 2 " .3.2. Проверить равносильности из подраздела 3.2.2 путем построения таблицистинности.3.3. Какие функции являются двойственными для функций +, =, |, j?3.4. Построить СДНФ для функций xi \ х2, х\ | х2, х\ —> х2, х\ + х2.3.5. Доказать, что если / £ Т0, то / £ Т* V ( / £ Тх к f £ Т^).3.6. Построить СДНФ, сокращённую дизъюнктивную нормальную форму, минимальную дизъюнктивную форму, сокращённое дерево решений и бинарнуюдиаграмму решений для функции, заданной формулой (х —• у) —> 2.Упражнения141Рис.

3.3. Построение бинарной диаграммы решенийРис. 3.4. Бинарная диаграмма решений при другом порядке переменныхГлава 4ЛогическиеисчисленияС древнейших времён человечеству известна логика, или искусство правильнорассуждать. Вообще говоря, способность к рассуждеииям — это именно искусство.

Имея какие-то утверждения (посылки), истинность которых проверена,скажем, на опыте, логик путем умозрительных построений приходит к другомуутверждению (заключению), которое также оказывается истинным (в некоторых случаях). Опыт древних (чисто наблюдательный) был систематизированАристотелем1. Он рассмотрел конкретные виды рассуждений, которые назвалсиллогизмами. А именно, Аристотель рассмотрел так называемые категорическиеутверждения четырех видов (Л, В — категории)'.1)2)3)4)все А обладают свойством В (все А суть В);некоторые А обладают свойством В (некоторые А суть В);все А не обладают свойством В (все А суть пе В);некоторые А не обладают свойством В (некоторые А суть не В)и зафиксировал все случаи, когда из посылок такого вида выводятся заключенияодного из этих же видов.Примеры1.

Все люди смертны. Сократ — человек. Следовательно, Сократ смертен. Эторассуждение правильно, потому что подходит под один из образцов силлогизмов Аристотеля.2. Все дикари раскрашивают свои лица. Некоторые современные молодые людираскрашивают свои лица. Следовательно, некоторые современные молодыелюди — дикари.

Это рассуждение неправильно, хотя, видимо, все входящиев него утверждения истинны.Логика Аристотеля — это классическая логика, то есть паука, традиционно относящаяся к гуманитарному циклу и тем самым находящаяся вне рамок даннойкниги.1Аристотель (384-322 до н. э.).1434.1. Логические связкиПредметом этой главы являются некоторые элементы логики математической,которая соотносится с логикой классической примерно так, как язык Паскальсоотносится с английским языком.

Эта аналогия довольно точна и по степениформализованности, и по широте применимости в реальной жизни, и по значимости для практического программирования. План главы состоит в том, чтобы паоснове небольшого предварительного рассмотрения ввести понятие «формальной теории», или «исчисления», в наиболее общем виде, а затем конкретизировать это понятие примерами двух наиболее часто используемых исчислений:исчисления высказываний и исчисления предикатов.4.1. Логические связкиЦель данного раздела — неформально ввести специфическую «логическую» терминологию и указать на её связь с материалом предшествующих глав. В последующих разделах главы определения этого раздела уточняются и конкретизируются.4.1.1. ВысказыванияЭлементами логических рассуждений являются утверждения, которые либо истинны, либо ложны, по не то и другое вместе.

Такие утверждения называются(простыми) высказываниями. Простые высказывания обозначаются пропозициональными переменными. Пропозициональная переменная может принимать одноиз двух истинностных значений, обозначаемых символами «Т» и «F».ЗАМЕЧАНИЕИстинностные значения обозначают различными способами: латинскими буквами Т и F,как в этом учебнике, русскими буквами И и Л (от слов «Истина» и «Ложь»), цифрами1 и 0, специальными значками Т и 1. Каждый из способов обозначения истинностныхзначений имеет свои достоинства и недостатки. Пара символов Т и F выбрана нами,во-первых, для удобства чтения, во-вторых, эти символы пе используются в учебнике вдругом смысле, и, в-третьих, ради ассоциации с английскими словами «true» и «false», которые используются во многих языках программирования для обозначения истинностныхзначений.Из простых высказываний с помощью логических связок могут быть построенысоставные высказывания.

Обычно рассматривают следующие логические связки.НазваниеОтрицаниеКонъюнкцияДизъюнкцияИмпликацияПрочтениенеиилиесли...тоОбозначение-1&V144Глава 4. Логические исчисления4.1.2. ФормулыПравилыю построенные составные высказывания называются (пропозициональными) формулами. Формулы имеют следующий синтаксис:(формула):: =Т |F|(пропозициональная переменная) |(-"(формула)) |((формула) &; (формула)) |((формула) V (формула)) |((формула) —» (формула))ЗАМЕЧАНИЕДля описания синтаксиса языка мы используем один из стандартных приёмов: контекстносвободную порождающую грамматику в форме Бэкуса—Наура.

Здесь названия синтаксических конструкций заключаются в угловые скобки, метасимвол «:: =» означает «это»,метасимвол «|» означает «или», все остальные символы означают сами себя. Исчерпывающее изложение теории формальных грамматик применительно к программированиюможно найти в [1].Для упрощения записи вводится старшинство связок (->,V, —») и лишниескобки часто опускаются.Истинностное значение формулы определяется через истинностные значения еёсоставляющих в соответствии со следующей таблицей:АВ-*ААк ВА У ВА —> ВFFТТFТFТТТFFFттFFFТТТтFт4.1.3.

ИнтерпретацияПусть А(х 1,... ,хп) — пропозициональная формула, где xi,... ,хп — входящиев неё пропозициональные переменные. Конкретный набор истинностных значений, приписанных переменным х\,...,хп,называется интерпретацией формулы А. Формула может быть истинной (иметь значение Т) при одной интерпретации и ложной (иметь значение F) при другой интерпретации. Значениеформулы А в интерпретации I будем обозначать 1(A).

Формула, истинная принекоторой интерпретации, называется выполнимой. Формула, истинная при всехвозможных интерпретациях, называется общезначимой (или тавтологией). Формула, ложная при всех возможных интерпретациях, называется невыполнимой(или противоречием).ПримерыАУ->А — тавтология, А & -iA — противоречие, А —> ->А — выполнимая формула,она истинна при 1(A) — F.1454.1.

Характеристики

Список файлов книги