Реферат: Дискретная математика
/>Министерство образования и науки
Российской Федерации
Российский химико-технологическийуниверситет
им. Д.И. Менделеева
Новомосковский институт
Издательский центр
T.П. Тюрина, В.И. Емельянов
Дискретная математика
(часть 3)
Учебное пособие
Новомосковск 2004
Содержание
Часть 3. Элементы алгебры логики… 3
3.1 Введение в алгебру логики… 3
3.2 Основные функции алгебры логики… 5
3.3 Формулы алгебры логики… 9
Контрольныевопросы… 12
3.4 Законы алгебры логики и следствия из них… 12
Контрольныевопросы… 16
3.5 Логические функции многих переменных… 16
3.6 Построение формул алгебры логики по заданной таблицеистинности 18
Контрольныевопросы и упражнения… 26
3.7 Некоторые замкнутые классы (классы Поста). Понятие базиса… 26
Контрольныевопросы и упражнения… 34
3.8 Методы минимизации логических функций… 34
Контрольныевопросы… 39
3.9 Неполностью определенные логические функции… 40
3.10 Формы представления булевых функций… 41
3.10.1Семантические деревья… 42
3.10.2Бинарные диаграммы решений (БДР)… 45
3.11 Построение логических схем… 45
Контрольныевопросы… 45
3.12 Логические конечные автоматы… 46
3.12.1Процессы… 50
3.12.2Конечные автоматы… 52
Контрольныевопросы… 55
БИБЛИОГРАФИЧЕСКИЙСПИСОК… 60
/>/>/>/>/>Часть 3.Элементы алгебры логики/>/>/>/> 3.1 Введение в алгебру логики
Алгебрулогики иначе еще называют алгеброй высказываний, логикой высказываний. Алгебралогики начала формироваться в 19 веке в трудах английского математика Дж. Буля.
Прежде всего,благодаря труду английского логика Джорджа Буля «Математический анализ логики»,был достигнут подлинный прогресс науки, называемый математической логикой. Онперенёс на логику законы и правила математических действий, ввёл логическиеоперации, предложил способ записи высказываний в символической форме.
В трудахДжорджа Буля и О. де Моргана математическая логика представлена каксвоеобразная алгебра – алгебра логики (алгебра высказываний).
Алгебралогики (алгебра высказываний) – раздел математической логики, изучающийстроение (форму, структуру) сложных логических высказываний и способы установленияих истинности с помощью алгебраических методов.
Джордж Буль(1815–1864) родился в Линкольне (Англия). Сын сапожного мастера. Окончил тольконачальную школу и дальнейшие знания приобретал самоучкой. С 1849 г. Буль – профессор математики в Куинс – колледже в Корке (Ирландия), где преподавал доконца жизни. Буля почти в равной степени интересовали логика, математическийанализ, теория вероятностей, этика Б. Спинозы, философские работыАристотеля и Цицерона. Он считается несомненным создателем современнойсимволической (математической) логики.
Огастес деМорган (1806–1871) родился в Индии в семье полковника английских войск. Получилобразование в Кембриджском университете. Был профессором математики Лондонскогоуниверситета. Математику и логику де Морган назвал азами точного знания ивыражал сожаление, что математики не более заботятся о логике, чем логики оматематике. Сам он стремился сблизить обе науки, и его главной заслугой явилосьпостроение логики по образу и подобию математических наук. Независимо от Дж. Буляон открыл основные идеи алгебры логики.
«Логика Буля»основывается на отношении эквивалентности, при котором правая часть равенствавсегда содержит ровно столько же «истин», сколько и левая.
Высказывание– это имеющее смысл языковое выражение (повествовательное предложение),относительно которого в данной ситуации можно утверждать, что оно либо истинно,либо ложно, т. е. каждому высказыванию можно приписать истинное значение И(истина) или Л (ложь), но не то и другое одновременно.
Примеры:
1. НГТУ– крупнейший «вуз Новосибирска».
2. «Снегзелёный».
3. Р= «Чтобыподключиться к Интернету с домашнего компьютера, необходим модем исоответствующее ПО».
4. Крокодилылетают очень низко.
«А ты любишьинформатику?» – это предложение не является высказыванием.
Уравнение2+х=4 не является высказыванием. Однако, всякий раз, придавая переменной хопределенное числовое значение, будем получать высказывание. Используя частицу «не»,а также союзы «и», «или», связки «если …., то…», «тогда и только тогда, когда…»и т. п., можно из одних высказываний строить другие высказывания.
Изучениемвысказываний занимается Булева алгебра, в которой предполагается, что ужеимеется некоторый запас высказываний, для каждого из которых известно истиннооно или ложно. Такие высказывания называют элементарными высказываниями. Изэлементарных высказываний могут быть построены сложные с помощью операций алгебрылогики.
Знакилогических операций называют логическими связками (или просто связками).Логические связки могут быть одноместные (унарные), двухместные (бинарные),трехместные (тернарные) и т. д.
В алгебрелогики логические операции чаще всего описываются при помощи таблиц истинности,содержащих все наборы значений переменных и значения функции этих наборов.Алгебра логики не занимается обоснованием того, почему тому или иномуэлементарному высказыванию приписано значение истины или лжи. Этот вопрос решаетсяза пределами алгебры логики.
Например:сумма углов в треугольнике – 180 градусов. Алгебра логики отвлекается и отсмысловой содержательности высказывания. Она интересуется только одним свойствомсложных высказываний: быть истинным (True – 1) или ложным (False – 0).
/>/>/>/>3.2 Основные функции алгебры логикиОсновнойзадачей теории булевых функций является разработка систематического методапостроения сложных функций из более простых. Этот метод основан на изучениисвойств булевых функций.
Основнымисимволами алгебры высказываний являются:
а)пропозиционные переменные Р1, Р2, Р3, …;
б)одноместная связка – (ù) и двуместные связки Ù (и), Ú (или), ®, Þ, Û;
в) скобки ().
Переменная,значениями которой являются высказывания, называется пропозиционной переменной.
Пусть А, В-некоторыеэлементарные высказывания.
Определимновое высказывание Ā (т. е. не А), будем называть егоотрицанием (инверсия: />, Ā),представим таблицы значений функции отрицания:
А
Ā
1
1
Рассмотримнаборы истинных значений элементарных функций на наборах аргументов:
A B1
1
1
1
Таблица 1
№ Обозначение операции Другие обозначения Набор истинных значений Название логической опции и связки Как читается Арифметическая модель 12 АÚВА+В
Max (А, В)
1
1
1
Дизъюнкция, логическое сложение, «или» А или В A+B-A×B 23 АÙВА&В
А×В
Min (А, В)
1
Конъюнкция, логическое умножение «и» А и В A×B 34 А®ВАÊВ
АÞВ
1
1
1
Импликация, логическое следованиеЕсли А, то В
А влечет В
1‑A+ A×B 45 А~ВАºВ
А«В
АÛВ
1
1
Эквиваленция, эквивалентность А тогда и только тогда, когда В; А эквивалентно В1 – (A-B)2
56 АÅВА+В
АÚВ
АDВ
1
1
Сумма по модулю 2, сумма Жегалкина А плюс В; Либо А, либо В 67 А½В1
1
1
Штрих Шеффера, антиконъюнкция Неверно, что А и В; А штрих Шеффера В 78 А¯ВА°В
АÚВ
1
Стрелка Пирса, антидизъюнкция, функция Вебба, функция Даггера Ни А, ни В; А стрелка Пирса ВНесмотря нато, что булевых функций от любого заданного числа m двоичных переменныхконечное число, их слишком много, чтобы иметь запас преобразователей для любыхвстретившихся отображений. Рассмотрим сначала все возможные функции от однойдвоичной переменной. Их четыре, две из них – константы (0 и 1), одна – тождественнаяфункция и только одна – функция отрицания (функция НЕ) – являетсянетривиальной.
p/>p
1 1Очевидно, чточисло различных булевых функций от mпеременных равно 2 встепени />. При m = 2 это число 16, тоесть всего функций от двух переменных 16, однако наиболее практическиприменимых из них меньше.
Суперпозициядвоичных функций может быть записана как формула, которую называют логическойформулой.
Пример.
Логическаяформула /> задает функцию от трехпеременных как суперпозицию функций одной и двух переменных.
Дляуменьшения числа скобок вводятся приоритеты операций. Наиболее приоритетнафункция отрицания. Затем идет конъюнкция, после нее – дизъюнкция. Все другиефункции имеют равный приоритет, меньший, чем у дизъюнкции. Очевидно, чтоскобками можно установить желаемый порядок операций. Вышеприведенная формуламожет быть эквивалентно записана так: />.Отметим, что используют и другое распределение приоритетов, в частности,полагая импликацию менее приоритетной, чем все другие функции.
Логическаяформула дает возможность построить соответствующий функциональныйпреобразователь, если мы имеем «элементарные» или «базисные» преобразователи.Для реализации преобразователя f примера выше необходимо иметь элементы,реализующие отрицание, дизъюнкцию, конъюнкцию и сложение по модулю два (см. рис. 1).
На этомрисунке представлен пример синтаксической структуры формулы – графическоепредставление формулы.
/>
Рис. 1.Синтаксическая структура формулы />
Очевиднымобразом по формуле можно построить табличное представление функции f.
Таблица 2
p q r/>
/>
/>
/>
/>
/>
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1Суперпозициейнескольких простых булевых функций можно построить более сложную функцию, вчастности, булеву функцию от большего числа переменных. Поставим вопрос: можноли суперпозицией фиксированного набора функций представить любую булеву функциюот любого числа переменных? Удивительно, но ответ на этот вопрос положителен.
Штрих Шеффера является отрицанием конъюнкции, стрелка Пирса – отрицаниедизъюнкции, сумма Жегалкина – отрицание эквивалентности.
М. Жегалкин (1869–1947) – российский математик и логик, одиниз основоположников современной математической логики.
Чарльз Пирс (1839–1914) – американский логик, математик иестествоиспытатель. Основоположник семиотики, родоначальник прагматизма.
/>/>/>/>3.3 Формулы алгебры логикиИз логическихпеременных можно составлять различные конструкции, которые образуют формулыалгебры логики.
Пусть /> – некоторое множествологических переменных. По индукции определим понятие формулы алгебры логики:
1) любаялогическая переменная является формулой (атомарной);
2) если /> и /> – формулы, то выражения /> и другие, представленные втабл. 1, являются формулами;
3) никакихдругих формул, кроме построенных в пунктах 1 и 2, нет.
Если формула /> построена из логическихпеременных, лежащих в множестве {x1, x2,…, xn}, то будем писать />{x1, x2,…, xn}.
Таблицыистинности также называются интерпретациями логических операций и составляютсемантику формул (т. е. придание смысла формулам) в отличие от синтаксисаформул (т. е. формальных законов их построения, данных в определенииформулы).
На множестве /> вводится транзитивноеотношение < «быть более сильным» и отношение ~ «быть равносильным» по правилам,представленным на рис. 2. Для равносильных связок расстановка скобок выполняетсяслева направо.
/>
Рис. 2.Приоритетность логических операций
Все формулыалгебры логики можно разделить на 3 класса:
1) нейтральные,или выполнимые – принимающие как истинное, так и ложное значения;
2) тождественноистинные формулы (или тавтологии) – принимающие истинные значения при любых значенияхпеременных;
3) тождественноложные формулы – принимающие ложные значения при любых оценках переменных.
Существуетдва способа определения истинного значения формулы. Первый – с помощью таблицистинности, а второй – путём приведения формул к нормальной форме. Формулаимеет нормальную форму, если в ней отсутствуют знаки эквиваленции, импликации,двойного отрицания и др., при этом знаки отрицания находятся только при переменных.
Табличныйспособ определения истинного значения формул имеет ограниченное применение,поскольку при увеличении количества переменных приходится рассматривать слишкоммного вариантов (2N).
Равносильныминазываются два высказывания, у которых таблицы истинности совпадают.
Пример. Составимтаблицу истинности функции f=(A/>B)~(/>/>):
Таблица 3
A BA/>B
/>
/>
/>/>
(A/>B)~(/> />)
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
Полученноевысказывание истинно всегда. Такие высказывания называют тождественно истиннымии обозначаются J. По аналогии существуют и тождественно ложные высказывания L. Метод заполнениятаблицы истинности принят для не очень сложных высказываний. Если выражениесодержит N опций, то таблица становится громоздкой. Для этого используютсязаконы алгебры логики. Таблицу истинности можно составить с использованием программы.В большинстве языков высокого уровня имеются логические операции NOT, AND, OR, XOR, реализующие операции /> соответственно.
/>/>Контрольныевопросы
1. Дайтеопределение высказывания.
2.Перечислите основные символы алгебры высказываний.
3.Перечислите основные функции алгебры логики.
4. Чтоявляется основной задачей алгебры логики?
5. Что такоетаблицы истинности логических функций?
6. Составьтетаблицу истинности функций дизъюнкции и конъюнкции.
7. Составьтетаблицу истинности функций импликации и эквивалентности.
8. Составьтетаблицу истинности функций отрицания и сложения по модулю 2.
9. Составьтетаблицу истинности функций Штрих Шеффера и Стрелка Пирса.
10. Формулыалгебры логики. Приоритет логических операций. Какие отношения имеют место намножестве логических операций?
11. Что такоесинтаксическая структура формулы?
12. На какиеклассы делятся формулы алгебры логики?
/>/>/>/>3.4 Законы алгебры логики и следствия из нихПри решениимногих логических задач часто приходится упрощать формулы, полученные приформализации их условий. Упрощение формул в алгебре логики производится наоснове эквивалентных преобразований, опирающихся на основные логические законы.Законы алгебры логики – это тавтологии (или теоремы).
1. Законтождества:
А=А
2. Законнепротиворечия:
/>
/>
3. Законисключения третьего:
/>
4. Закондвойного отрицания:
/>
5. Законыистины и лжи (свойства констант):
/> />
/>
/>
/>
/>
6. Законыидемпотентности:
/>
/>
7.Коммутативные законы:
/>
/>
8.Ассоциативные законы:
/> – дизъюнкции
/> – конъюнкции
9.Дистрибутивные законы:
/> – 1‑ыйдистрибутивный закон
/> – 2‑ойдистрибутивный закон
10. Законыпоглощения:
/>
/>
11. Законы деМоргана:
/>
/>
12. Законимпликации:
/>
13. Законэквивалентности:
/>
/>
/>
14. Свойствасложения «по модулю два»:
/>
/>
Справедливостьэтих законов можно доказать с помощью таблиц истинности сложных логическихсвязей описываемых законов.
Следствияиз законовалгебры логики (часто используются при упрощении логических выражений).
1. Правилопоглощения. Данное правило является следствием из дистрибутивного закона. Ономожет быть записано в следующем виде:
/>.
2. Правилосвертки. Правило является следствием из второго дистрибутивного закона. Записьправила:
а) />;
б) />.
3. Правилорасширения. Правило записывается в следующем виде:
/>.
4. Правилосклеивания. Базируется на понятии соседних конъюнкций. Соседними называютсяконъюнкции, отличающиеся представлением одной переменной. Например, конъюнкции /> и />, /> и /> являются попарнососедними. В первой паре конъюнкции отличаются представлением х2,а во второй – представлением х1. По этим переменнымконъюнкции склеиваются.
Формулировкаправила: две соседние конъюнкции склеиваются с образованием одной конъюнкциименьшего ранга; исчезает та переменная, по которой конъюнкция склеивается.
/>, />.
/>/>Контрольныевопросы1.Перечислите основные законы алгебры логики. Как дозывается их справедливость?
2.Перечислите следствия из законов алгебры логики.
/>/>/>/>3.5 Логические функции многих переменныхВселогические операции, которые были рассмотрены в 3.2, распространяются и нафункции нескольких переменных. Теперь будем рассматривать функции F(x1, x2,…, xn), где xi – логические переменные,которые принимают значения нуля или единицы. Для описания логики функционированияаппаратных и программных средств компьютера используется алгебра логики, илибулева алгебра. Два элемента алгебры логики – ее константы – 0 (ложь) и 1 (истина).Во всех компьютерах используются сигналы двух видов. Сигналы можноинтерпретировать как двоичные числа, или логические переменные.
ЛогическойфункциейF от набора логическихпеременных х1,…, хn называется функция,которая может принимать только два значения: логический 0 и логическая 1.
Областьопределения логической функции конечна и зависит от количества возможныхнаборов аргументов. Если n – число аргументов, то количество возможных набороваргументов равно 2n.
Множествозначений функции F(x1,…, xn) – это множество {0,1}, т. е.F=0 либо 1.
Любаялогическая функция может быть задана с помощью таблицы истинности, в левойчасти которой записываются наборы аргументов, а в правой – соответствующиезначения функции.
x1
x2
…xn-1
xn
F(x1, x2,…, xn-1, xn)
… F (0,0,…, 0,0) … 1 F (0,0,…, 0,1) … 1 F (0,0,…, 1,0) … … … … … … 1 1 … 1 1 F (1,1,…, 1,1)Векторомзначений булевой функции F(x1,…, xn) называется упорядоченныйнабор всех значений функции F, при которых значения упорядочены полексикографическому порядку множества аргументов {0,1}n.
Посколькувсего имеется 2n наборов /> нулейи единиц (|{0,1}n|=2n), существует ровно /> булевых функций F(x1,…, xn) от n переменных:
/>.
При n=2 количество функцийравно 16, при n=3 – 256 и т. д. На рис. 3 представлены вупорядоченном виде наборы аргументов для ряда функций – отрицания 0, функций одного,двух и трёх аргументов.
/>
Рис. 3.Упорядоченные наборы аргументов
/>/>/>/>3.6 Построение формул алгебры логикипо заданной таблице истинности
Пусть F – двоичная функция от nпеременных. Предположим,что F не равна тождественно нулю. Пусть T1, T2,…, Tk – все точки ееопределения, в которых F=1. Можно доказать, что справедлива следующаяформула:
/>,
где />, j=1,2,…, k,
/>
Построитьфункцию F можно и по-другому. Если функция Fне равна тождественноединице и S1, S2,…, Sm – все точки области ееопределения, в которых F=0, то справедлива формула:
/>,
где />, j=1,2,…, m.
/>
Изприведенных формул видно, что любую двоичную функцию можно записать, используялишь операции ¬, />, />.
Основнаяконъюнкция – это конъюнкция основных высказываний переменных или их отрицаний.Например, />.
Основнаядизъюнкция – это дизъюнкция основных высказываний переменных или их отрицаний.Например, />.
Конъюнктивнойнормальной формой (КНФ) данной формулы называется формула, равносильная даннойи представленная в виде конъюнкции основных дизъюнкций. Например, (A+B) (A+C+B) (D+A).
Дизъюнктивнойнормальной формой (ДНФ) данной формулы называется формула, равносильная даннойи представленная в виде дизъюнкции основных конъюнкций. Например, AB+C+AC.
Теорема 1.Для того чтобы формула алгебры высказываний была тождественно истинной,необходимо и достаточно, чтобы ее КНФ содержала в каждой элементарнойдизъюнкции некоторое высказывание и его отрицание.
Теорема 2.Для того чтобы формула алгебры высказываний была тождественно ложной,необходимо и достаточно, чтобы ее ДНФ содержала в каждой элементарнойконъюнкции некоторое высказывание и его отрицание.
Совершенныедизъюнктивные, конъюнктивные и полиномиальные нормальные формы представленияпереключательных (логических) функций. Многообразие формул, посредством которых можетбыть выражена любая логическая функция, определяет многообразие форм логическихфункций, т. е. способов их записи путем применения к переменным и ихгруппам элементарных логических операций. Наиболее удобными для практического использованияоказываются совершенные нормальные формы представления сложных логическихфункций. В алгебре логики доказывают, что любая логическая функция F(A, B, C,…, N) может быть представленатолько одной совершенной дизъюнктивной нормальной формой (кроме константы нуль)или только одной совершенной конъюнктивной нормальной формой (кроме константыединица).
Пусть функцияX=F(A, B, C) задана таблицей 4.Запись функции Х в виде логической суммы (дизъюнкции) логическихпроизведений (конъюнкций) переменных, для которых значение функции Хравно 1, и является совершенной дизъюнктивной нормальной формой (СДНФ)представления логической функции.
Таблица 4
A B C X 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1СДНФлогической функции следует находить в такой последовательности:
1) составитьпроизведения переменных для строк таблицы истинности, в которых Х равна1. Если значение переменной (А, В или С) в строке равно 0, то впроизведении записывается отрицание этой переменной;
2) написатьсумму произведений, для которых функция Х равна 1. Полученная сумма иявляется СДНФ. В общем виде
/>, (1)
Это правилоназывают правилом записи переключательной функции по единицам. Согласно этомуправилу, данные табл. 4 описываются аналитическим выражением, связывающим всенаборы переменных, для которых Х=1, в виде:
/>. (2)
Запись функцииХ в виде логического произведения (конъюнкции) логических сумм(дизъюнкций) переменных, для которых функция Х равна 0, являетсясовершенной конъюнктивной нормальной формой (СКНФ) представления логическойфункции.
Для табл. 4аналитическое выражение в СДНФ, связывающее все наборы переменных, для которых Х=0,имеет вид:
/>. (3)
Дляпредставления логической функции Х в СКНФ произведем операцию отрицаниялевой и правой частей равенства (3)
/>
и наосновании законов двойного отрицания и инверсии
/>
/>. (4)
СКНФлогической функции, согласно (4), следует находить в такой последовательности:
1) составитьлогические суммы переменных для строк таблицы истинности, в которых функция Хравна 0. Если значение переменной (А, В или С) в строке равно1, то в сумме записывается отрицание этой переменной;
2) написатьлогическое произведение составленных логических сумм. Полученное произведение иявляется СКНФ. В общем виде:
/>, (5)
где Fi – сложные дизъюнкции.
Это правилотакже называют правилом построения переключательной функции по нулям.
Кроме представленияфункций в виде СДНФ и СКНФ используют и совершенную полиномиальную нормальнуюформу СПНФ. Вместо дизъюнкции может быть записана функция сложения по модулюдва (сумма Жегалкина):
/>, (6)
где Fi – сложные конъюнкции.
Существуетспециальная таблица, в которой все элементарные логические операции от двухаргументов представлены в двух совершенных нормальных формах.
Нормальныеформы представления переключательной функции иногда называют стандартными (табл.5).
Таблица 5
fA
0011
B
0101
Название функции Обозначение функции СДНФ СКНФf0
0000 Константа нуль Не имеет/>
f1
0001 Логическое произведение, конъюнкция/>
/>
/>
f2
0010 Функция запрета по В/>
/>
/>
f3
0011 Переменная А/>
/>
/>
f4
0100 Функция запрета по А/>
/>
/>
f5
0101 Переменная В/>
/>
/>
f6
0110 Сумма по мо дулю 2, логическая неравнозначность/>
/>
/>
f7
0111 Логическое сложение, дизъюнкция/>
/>
/>
f8
1000 Операция (стрелка) Пирса, операция Вебба/>
/>
/>
f9
1001 Эквивалентность, логическая равнозначность/>
/>
/>
f10
1010 Инверсия В/>
/>
/>
f11
1011 Импликация от В к А/>
/>
/>
f12
1100 Инверсия А/>
/>
/>
f13
1101 Импликация от А к В/>
/>
/>
f14
1110 Операция (штрих) Шеффера/>
/>
/>
f15
1111 Константа единица 1/>
Не имеетМногочленомЖегалкина называется многочлен, являющийся суммой константы 0 или 1 и различныходночленов, в которые все переменные входят не выше, чем в первой степени.
Теорема. Любая функция булевой алгебры может быть представлена, и притомединственным образом, с помощью полинома Жегалкина вида
J =/>.
Представим, например, в виде полинома выражение вида X1/>X2. Для этого проведем следующиерассуждения.
Пусть
X1/>X2= aX1X2+bX1+cX2+k,
где а, b, с, k – неопределенныекоэффициенты.
При X1= X2= 0 имеем k = 0. При Х1= 1, X2= 0 имеем b= 1. При Х1= 0, Х2=1 имеем с= 1. При X1=Х2= 1 имеем а + b+ с = 1, т. е. а= -1. Таким образом, получаем:
X1/>X2 = – X1X2+ X1+ X2.
СПНФобразуется путем замены в СДНФ: /> на + и /> на
1 /> х.
/>,
/>,
/>
В последнемслучае выражение для /> легко можноупростить, если раскрыть скобки и взаимно сократить все одинаковые слагаемые,входящие в формулу четное число раз:
/>.
Подобноеупрощение, которое называется минимизацией логической функции, можноосуществить и по отношению к СДНФ и СКНФ.
Таблица 6
/>
/>
/>
y 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1Применениезаконов алгебры логики позволяет найти более компактные аналитические выражениядля заданной функции у, т. е. минимальную дизъюнктивную нормальнуюформу />. Приведем соответствующиеформы представления функции у, заданной табл. 6:
/>,
и для СКНФ, т. е.минимальную КНФ:
/>.
После того,как найдены минимальные нормальные формы (МНФ), их рекомендуется проверить навсех наборах аргументов />.Переменные /> или /> часто называют термами.Именно полный набор из n термов образует конституенту. В процессе жеминимизации некоторые термы из конституент пропадут. Тогда оставшуюся частьдизъюнкта или конъюнкта называют импликантой.
Как мы толькочто убедились на примере, импликанты появляются в результате склейки смежныхконституент, различающихся одним термом.
/>/>Контрольныевопросы и упражнения/>1. Дайте определение логической функциимногих переменных.
2. Что такоевектор значений булевой функции? Приведите пример построения таблицы истинностилогической функции многих переменных.
3. Сколькосуществует булевых функций от n переменных?
4. Что такоеДНФ и КНФ?
5. Каковалгоритм построения СДНФ? Приведите пример построения СДНФ.
6. Каковалгоритм построения СКНФ? Приведите пример построения СКНФ.
7. СоставьтеСКНФ и СДНФ для функции />.
8. Приведитепример построения СПНФ.
/>/>3.7 Некоторые замкнутые классы (классы Поста).Понятие базисаСистемабулевых функций {f1, f2,…, fm} называется полной, еслилюбая булева функция может быть выражена через функции f1, f2,…, fm с помощью суперпозиций.
Пусть К0={f1(x1,…,xk1), f2(x1,…,xk2),…, fm(x1,…,xkm)} – конечная системабулевых функций. Функция fназывается элементарной суперпозицией(суперпозицией ранга 1) функций f1, f2,…, fm, если f может быть полученаодним из следующих способов:
а)переименованием некоторой переменной xj какой-нибудь функции fi;
б) подстановкойнекоторой функции /> вместокакой-либо переменной xj любой из функций />.
Суперпозицииранга 1 образуют класс функций К1. Класс функций,получающийся из функций класса Ks-1 суперпозицией ранга s‑1 с помощью элементарныхсуперпозиций, называется классом функций Ks суперпозиций ранга s. Суперпозициями функцийиз К0 называются функции, входящие в какой-то из классов Ks.
Согласновведенным определениям, можно говорить, что система булевых функций полна.Тогда любую булеву функцию можно представить в виде многочлена от своихпеременных.
В современномкомпьютере цифрами являются ноль и единица. Следовательно, команды, которыевыполняет процессор, суть булевы функции. Мы уже видели, что любая булевафункция реализуется через конъюнкцию, дизъюнкцию и отрицание. Следовательно,можно построить нужный процессор, имея в распоряжении элементы, реализующие />. Далее рассмотрим вопрос:существуют ли (и если существуют, то какие) другие системы булевых функций,обладающие тем свойством, что с их помощью можно выразить все другие функции.Рассмотрим некоторые замкнутые классы (классы Поста), их пять.
1.Класс функций, сохраняющих константу нуль (обозначается T0 или P0):
T:={f| f(0,0,…, 0)=0}.
Кэтому классу относятся, например, функции />; />; />; />.
2.Класс функций, сохраняющих константу единица (обозначается T1 или P1):
T1:={f| f(1,1,…, 1)=1}.
Кнему относятся все нечетные функции.
3.Класс самодвойственных функций (обозначается T* или S):
T*:={f| f*};
/>
Пример/> и />.
Функция/> называется двойственной по отношению кфункции />, если />. Двойственная функция получаетсяиз исходной при замене значений всех переменных, а также значений функции напротивоположные, т. е. в таблице истинности нужно заменить 0 на 1, 1 на 0.
Пример.Двойственной к функции /> являетсяфункция, соответствующая формуле />, т. е./> или />: />. Аналогично />, />.
Принципдвойственности:
Если/>,
то/>.
Такимобразом, функция, двойственная суперпозиции функций, есть соответствующаясуперпозиция двойственных функций.
Этотпринцип удобен при нахождении двойственных функций, представленных формулами,содержащими лишь конъюнкции, дизъюнкции и отрицание. В этом случае в исходнойформуле конъюнкции заменяются на дизъюнкции, а дизъюнкции – на конъюнкции.Таким образом, ДНФ соответствует КНФ, КНФ – ДНФ, СДНФ – СКНФ, СКНФ – СДНФ.
Пример./>,
если/>, то и />.
Функция/> называется самодвойственной,если />.
Пример.Покажем, что формула /> задаетсамодвойственную функцию.
Убедимся,что на всех противоположных наборах значений переменных /> и /> формула принимаетпротивоположные значения. Действительно, составим таблицу истинности:
/>
x y z 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1Получаем/>, />, />, />.
4.Класс монотонных функций (обозначается TM<sub/>или M):
/>, где />,/>, />, />.
5.Класс линейных функций (обозначается TL<sub/>или L):
/>.
Эквивалентностьявляется линейной функцией />.Стрелка Пирса – нет, />.
/>, />,/>,…, />,
т. е.
/>, />,…, />. (7)
Такимобразом, проверка линейности сводится к нахождению коэффициентов /> по формулам (7) исопоставлению таблиц истинности данной формулы /> иполученной формулы />.
Пример.Проверим, является ли линейной функция />.Имеем />, />, />. Таким образом, />. Сопоставляя таблицыистинности формул /> и />, убеждаемся, что они несовпадают. Вывод: функция /> нелинейна.
Линейностьфункции можно также определить с помощью следующей теоремы.
ТеоремаЖегалкина. Всякая булева функция /> представимаполиномом Жегалкина, т. е. в виде />, где в каждом наборе (i1,…, ik) все ij различны, а суммированиеведется по некоторому множеству таких несовпадающих наборов. Представление булевойфункции в виде полинома Жегалкина единственно с точностью до порядка слагаемых.
ПолиномЖегалкина называется нелинейным (линейным), если он (не) содержит произведенияпеременных.
Такимобразом, линейность булевой функции равносильна линейности соответствующегополинома Жегалкина.
Для полученияполинома Жегалкина булевой функции, находящейся в СДНФ, используются аксиомыбулевой алгебры, аксиомы булева кольца /> иравенства, выражающие операции /> черезоперации этого булева кольца: /> и т. д.
Пример.Определим линейность функции />.
Имеем
/>
Полученныйполином Жегалкина является нелинейным, и, следовательно, функция f также нелинейна.
Заметим, чтоесли в эквивалентности /> формулы/> являются различнымиконституентами единицы, то их произведение /> равно0, и тогда />. Следовательно, дляполучения полинома Жегалкина из СДНФ можно сразу заменить />.
Отметим, чтокаждый класс Поста замкнут относительно операций замены переменных исуперпозиции, т. е. с помощью этих операций из функций, принадлежащих данномуклассу, можно получить только функции из этого же класса.
Пример.Определим, к каким классам Поста относится булева функция />.
Так как f (0,0)=1, а f (1,1)=0, то /> и />. Поскольку />, то />. Так как f (0,0)>f (1,1), то />. Полином Жегалкина дляфункции /> имеет вид /> в силу равенства />. Поэтому данная функциянелинейна. Таким образом, можно составить следующую таблицу
Таблицафункций
Функция КлассыР0
Р1
S М L х | у Нет Нет Нет Нет НетТеоремаПоста. Система F булевых функций тогда и только тогда является полной, когда длякаждого из классов P, P1, S, M, L в системе F найдется функция, не принадлежащаяэтому классу.
В силутеоремы Поста функция х | у образует полную систему, т. е. спомощью штриха Шеффера можно получить любую булеву функцию. В частности, />.
Системабулевых функций называется базисом, если она полна, а удаление любойфункции из этой системы делает ее неполной.
Теорема.Каждый базис содержит, не более четырех булевых функций.
Доказательство.Предположим, что существует базис F, состоящий более чем из четырех функций. По теоремеПоста тогда получаем, что F состоит ровно из пяти функций, каждая из которыхне принадлежит ровно одному классу Поста. Пусть f – функция из F, не принадлежащая классуР0. Тогда, с одной стороны, f(0,0,…, 0)=1, а, с другой – из /> следует, что f(1,1,…, 1)=1. Это означает, что f не являетсясамодвойственной функцией, что противоречит предположению.
Пример. Следующиесистемы булевых функций являются базисами: />.
Таблица 7
Обоснование Базис/>;
следовательно, />
{И, НЕ} – конъюнктивный базис/>;
следовательно, />
{ИЛИ, НЕ} – дизъюнктивный базис/>;
{И, />, 1} – базис Жегалкина
/>;
следовательно, />; />
{|} – базис Шеффера/>;
следовательно, />; />
{/>} – базис Пирса
Пример.
Конъюнкции,то есть все функции вида />, тожесоставляют замкнутый класс. Очевидно, однако, что, например, функцию, котораяна наборе (0,0,…, 0) имеет значение 1, нельзя представить суперпозицией такихфункций. Таким образом, {И} не является базисом, следовательно, конъюнктивныйбазис {И, НЕ} является минимальным.
Рассмотримболее подробно базис Жегалкина.
АлгебраЖегалкина и линейные функции
АлгебраЖегалкина – это алгебра над множеством двух бинарных булевых функций (И, />) и нульарной функции 1.Легко проверить следующие соотношения в этой алгебре:
/>;
/>;
/>;
/>.
Если впроизвольной формуле, включающей только функции базиса Жегалкина, раскрытьскобки, то получим бесскобочную формулу, имеющую вид суммы (по модулю два)произведений, то есть некоторый полином. Он называется полиномом Жегалкина.
Широкий наборбазисов открывает большие возможности при решении задач минимизации схемустройств дискретного действия, поскольку из базисных схем с помощьюсуперпозиций можно составить схему, соответствующую любой булевой функции.
/>/>Контрольныевопросы и упражнения1. Дайтеопределение полной системе булевых функций.
2.Перечислите классы Поста.
3. Дайтеопределение двойственной функции. Приведите примеры.
4. Дайтеопределение самодвойственной функции. Приведите примеры.
5. Постройтеполином Жегалкина для функции «стрелка Пирса».
6.Сформулируйте теорему Поста.
7. Что такоебазис? Приведите примеры базисов.
/>/>/>/>3.8 Методы минимизации логических функцийНаиболееупотребляемая операция при минимизации функций – это операция склеивания.
AB+ĀB=B(A+ Ā)=B.
Рассмотримтри наиболее распространенных метода минимизации.
1. Пустьбудут заданы номера наборов четырех переменных, на которых логическая функцияпринимает единичное значение: f(2,5,6,7,10,12,13,14)=1.
Выразим этулогическую функцию в СДНФ (символ конъюнкции писать не будем):
f(0010,0101, 0110, 0111,1010, 1100, 1101, 1110) =
/>.
На первомэтапе минимизации исходную СДНФ можно упростить за счет использования законасклеивания, тогда получим:
/>.
Обращаемвнимание на то, что одну и ту же конституенту (импликанту) можно склеивать сдругими конституентами (импликантами) многократно, так как в логике Булядействует закон идемпотентности:
/>,
поэтому любуюконституенту можно размножить.
На второмэтапе воспользуемся таблицей Куайна (табл. 8), в соответствии с которой данныйметод минимизации получил свое наименование – метод Куайна. В таблице повертикали перечислены все полученные на первом этапе упрощения импликанты, а погоризонтали – исходные конституенты. Единица в табл. 8 стоит там, гдеимпликанта «накрывает» конституенту. Дело в том, что конституента всегда можетбыть заменена импликантой или даже отдельным термом по закону поглощения:
/>
Таблица 8
/>
0010 0101 0110 0111 1010 1100 1101 1110 – – 1 0 1 1 1 1 0 1 – 1 1 1 0 1 1 – 1 1 – 1 0 1 1 1 1 1 0 – 1 1 1 1 – 0 1 1Послезаполнения таблицы Куайна у нас получилось так, что почти в каждой графеоказалось по две единицы; между тем достаточно иметь одну единицу в графе. Поэтому,по возможности, нужно исключить избыточные единицы. Выбор единиц производитсяиз соображений минимальности числа термов (выбранные единицы затемнены). В итогеоказалось, что можно обойтись только тремя импликантами вместо шести:
/>.
С помощьютаблиц истинности легко проверить, что полученная в МНФ функция воспроизводитвсе значения исходной функции. Отметим, что в общем случае решений по критериюминимума термов может быть несколько.
2. Не менееэффективным способом минимизации логических функций является метод сочетанияиндексов. Для его изложения составим табл. 9, в графах которой записанывозможные сочетания индексов. В последней графе выписаны значения функции.Анализ таблицы начинается слева по столбцам. Принцип исключения i, j‑кода следующий. Напересечении i‑столбца, например, с сочетанием индексов 23, и j‑строки, например,3‑ей, находится код 10, что соответствует импликанте />. Следовательно, в этомстолбце везде, где встречается код 10, т. е. в строках 2, 3, 10 и 11, этикоды исключаются, поскольку значение функции в 3‑ей строке равно нулю.Теперь возьмем столбец с сочетанием индексов 124. Здесь во 2‑ой и 6‑ойстроках оставлены коды 010, а в 10‑ой и 14‑ой строках – код 011.Сделано это потому, что эти коды встречаются только на строках со значениемфункции, равным единице. Напротив, код 110 этого же столбца встречается как приединичных значениях функции, так и при нулевых.
Таблица 9
n 1 2 3 4 12 13 14 23 24 34 123 124 134 234 1234 y 00 00 00 00 00 00 000 000 000 000 0000 1 1 10 10 10 00 00 00 100 100 100 000 1000 2 1 01 00 00 10 10 00 010 010 000 100 0100 1 3 1 1 11 10 10 10 10 00 110 110 100 100 1100 4 1 00 01 00 01 00 10 001 000 010 010 0010 5 1 1 10 11 10 01 00 10 101 100 110 010 1010 1 6 1 1 01 01 00 11 10 10 011 010 010 110 0110 1 7 1 1 1 11 11 10 11 10 10 111 110 110 110 1110 1 8 1 00 00 01 00 01 01 000 001 001 001 0001 9 1 1 10 10 11 00 01 01 100 101 101 001 1001 10 1 1 01 00 01 10 11 01 010 011 001 101 0101 1 11 1 1 1 11 10 11 10 11 01 110 111 101 101 1101 12 1 1 00 01 01 01 01 11 001 001 011 011 0011 1 13 1 1 1 10 11 11 01 01 11 101 101 111 011 1011 1 14 1 1 1 01 01 01 11 11 11 011 011 011 111 0111 1 15 1 1 1 1 11 11 11 11 11 11 111 111 111 111 1111Итак, всекоды на строках, заканчивающихся нулевыми значениями функции, исключаютсяавтоматически. Если эти коды попадают на строки, заканчивающиеся единичнымзначением функции, то они также не учитываются. Остаются только те коды,которые расположены на строках с единичным значением функции (эти коды затемнены).
Далееруководствуются следующим правилом. Для того чтобы функция приняла значение,равное единице, достаточно того, чтобы только какая-нибудь одна импликанта настроке приняла единичное значение. Прежде всего, оставляем минимальнуюимпликанту />, которая перекрываетединицы в строках 2, 6, 10 и 14. Затем, естественно, обращаемся к 12‑ойстроке. Здесь оставляем единственный на строке код 011, что отвечает импликанте/>. Эта же импликантаответственна за 13‑ую строку, оканчивающуюся тоже единицей. Осталосьрассмотреть 5‑ую и 7‑ую строки. Общей для них является импликанта: />. Таким образом, тремяимпликантами мы перекрыли все единичные значения функции, что совпадает срезультатом, полученным на основе таблиц Куайна.
3.Существует графический способ склеивания, который получил название метод картыКарно (представлен в табл. 10). Выделяем смежные единицы, это и будут слагаемыенашей функции.
Таблица10
x3x4
x1x2
00 01 11 10 00 1 1 01 1 11 1 10/> – получили два слагаемых
Хотя табл. 9более громоздка, чем табл. 8, метод сочетания индексов не считается болеесложным, чем метод Куайна, если помнить, что до составления таблиц Куайнанеобходимо произвести многочисленные склейки конституент и импликант.Реализация на компьютере алгоритма метода сочетания индексов оказываетсясравнительно простой. И напротив, внешняя простота и наглядность третьегометода минимизации логических функций с помощью карт Карно оборачиваетсясложной программой при реализации алгоритма на компьютере.
Таблица 11
/>
/>
/>
/>
/>
1100 1110 0110 0100/>
/>
1101 1111 0111 0101/>
/>
1001 1011 0011 0001/>
/>
1000 1010 0010 0000/>
/>
/>
/>
/>
Таблица 12
/>/>/>
Карта Карнодля четырех переменных представлена в виде табл. 11. Каждая клетка картысоответствует конституенте. Заполненная карта представлена табл. 12 (функциявзята та же, что и в первых двух методах). Согласно закону склеивания, двесмежные конституенты с единичными значениями всегда можно объединить дляполучения соответствующей импликанты. Причем смежными считаются и те, которыележат на границах карты. Какие именно единицы требуется объединить дляполучения подходящей импликанты, легко определить визуально. Следует также помнить,что в соответствии с законом идемпотентности одна и та же единица табл. 12может склеиваться с двумя или тремя смежными единицами.
/>/> Контрольныевопросы1.Перечислите основные методы минимизации функций.
2. Расскажитео методе Куайна.
3. Расскажитео методе карт Карно.
/>/>/>/> 3.9 Неполностью определенные логические функцииРанеемы рассматривали ситуации, когда на множество аргументов или логическихпеременных x1, x2,…, xn не накладывались ограничения,или, что то же самое, функции были определены на всем наборе аргументов. Однакореально на практике функции либо не определены полностью, либо есть запрещенныекомбинации. Необходимо доопределить функцию таким образом, чтобы аналитическаяформа ее представления была минимальной, далее производят склейки (примерприведён в табл. 13).
Таблица13
x3x4
x1x2
00 01 11 10 00 0* 1* 01 1* 1 1 1* 11 1 0* 10 0* 0* 1* 0*/>.
*– эти значения доопределили сами, исходя того, чтобы выражение для функции F было минимальным.
/>/>/>/>3.10 Формы представления булевых функцийК настоящемувремени мы знакомы с двумя формами представления булевых функций: таблицаистинности и формула (аналитическая запись). Рассмотрим еще две формыпредставления таких функций.
/>/>/>/> 3.10.1Семантические деревьяСемантическоедерево – это двоичное дерево, корень которого помечен двоичной функцией от m переменных, из каждогоузла идут по два ребра, соответствующих двум значениям очередной переменной, а2m листьев помечены соответствующими значениями функции.
/>/>/>/>3.10.2 Бинарные диаграммы решений (БДР)
Бинарнаядиаграмма решений (Binary Decision Diagrams, BDD) – это граф, являющийсямодификацией семантического дерева. В БДР узлы с одним и тем же значениемфункции объединены. Если на каждом уровне БДР все вершины имеют одну и ту жеметку (одинаковые переменные), то такая БДР называется упорядоченной (в англоязычнойлитературе такое представление называется Ordinary Binary Decision Diagrams, или сокращенно OBDD). Будем называть такоепредставление УБДР. Вершины УБДР расположены по уровням, каждому уровню соответствуетодна переменная, которая помечает вершины, находящиеся на этом уровне. Изкаждой вершины выходят два ребра: одно соответствует нулевому значению соответствующейпеременной (будем его изображать штриховой линией), а другое – единичномузначению этой переменной (оно изображается сплошной линией).
На рис. 4показаны все четыре формы представления функции />.
Бинарныедиаграммы решений используются как компактная форма представления булевойфункции. Такое представление полезно во многих случаях, например, когда нужномногократно вычислять значения функции при различных наборах значений ееаргументов. Для того чтобы получить значение функции f, например, на языке С,вместо хранения громоздкой таблицы истинности можно вычислить оператор: f=q? (r? 0:1): (р? 0:1), который построен наосновании БДР (см. рис. 4). В этом примере использование УБДР позволяетвычислить значение булевой функции, выполнив всего две операции, в то время какпри ее вычислении по аналитическому представлению требуется не менее 5 операций.
Рис. 4.Четыре формы представления двоичной функции
f (p, q, r) Таблица истинности Семантическое дерево Бинарная диаграмма решений/>
/>
/>
/>
p q r f 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 <p/>/>
/>
Сложностьпредставления функции с помощью УБДР существенно зависит от порядка переменных.Так, например, УБДР для иного порядка переменных, чем на рис. 4, содержитчетыре вершины, а не три (рис. 5). Интересной проблемой теоретическойинформатики является нахождение алгоритма, дающего оптимальный порядок переменныхбулевой функции с точки зрения представления этой функции упорядоченной БДР.
/>
Рис. 5.УБДР для функции /> с порядкомпеременных [p, q, r]
/>/>/>/>3.11 Построение логических схемПри синтезелогических схем применяют элементы с одним и несколькими входами. Условияфункционирования таких элементов определяются переключательными функциями однойили нескольких переменных.
Входные ивыходные сигналы логических схем зависят от времени (одни из них в некоторыймомент времени равны 1, в другие моменты времени 0). Логические функции,описывающие работу таких схем, называют переменными. Используют такжесхемы, для которых во все моменты времени сигналы равны либо 1, либо 0.Логические функции, описывающие работу этих схем, называют постоянными.
Существуеттолько четыре различные переключательные функции одной переменной. Как видно изтаблицы 14, только две функции не зависят от переменной А (в этихслучаях переменная А фиктивна).
Таблица 14
Х А Условное обозначение Название функции 0 1X0=f0 (A)
X1=f1 (A)
X2=f2 (A)
X3=f3 (A)
0 0
0 1
1 0
1 1
A
/>
1
Константа 0
Переменная А
Инверсия А
Константа 1
Для функциидвух переменных существует шестнадцать различных переключательных функций. Каквидно из таблицы 5, только десять функций существенно зависят от переменных Аи В.
На рис. 6,7 приведены обозначения элементов, реализующих некоторые переключательныефункции двух переменных.
Каждойэлементарной логической операции можно поставить в соответствие элементарнуюлогическую схему или вентиль. На входе и выходе вентиля мы имеем логическиесигналы двух видов, что можно ассоциировать с логическим 0 или логической 1.
1. Элемент«И» 2. Элемент «ИЛИ» 3. Элемент «НЕ»
/>
F=x1∙x2F=x1/>x2 F=/>
Рис. 6. Символическое обозначениевентилей
а) б) в)
/>
/>/>/>г) д) е)
/>
Рис. 7.Условные обозначения переключательных функций двух переменных: а – элементШеффера; б – элемент Пирса; в-импликатор; г – запрет; д – равнозначность; е –сложение по модулю 2
В техническойлитературе используются обозначения элементов, несколько отличающихся друг отдруга.
Логическаясхема, которая полностью описывается булевыми выражениями или таблицамиистинности, называется комбинационной схемой.
Такимобразом, комбинационная схема – схема, в которой значения входных переменных втекущий момент времени полностью определяют значения выходных переменных.
Другой класссхем – последовательностные схемы. Это схемы с внутренней памятью. В нихзначения выходных переменных определяются не только значениями входных переменныхв текущий момент времени, но и их значениями в предыдущие моменты времени.
Будемрассматривать только комбинационные схемы.
До сих пор мырассматривали поведение логической схемы, таблицы истинности и булевы выражения,использованные для описания значений выходной переменной в зависимости отнабора значений входных переменных. Но булево выражение содержит сведения и оструктуре логической схемы.
Соединивлогические элементы в соответствии с булевыми выражениями, получим логическуюсхему, реализующую данное выражение.
Логическаясвязь выхода и входов этой схемы описывается исходным булевым выражением. Такимобразом, булево изображение – описание логической схемы.
/>/>Контрольныевопросы1.Перечислите все известные формы представления булевых функций.
2.Перечислите основные элементы, используемые при построении логических схем.
/>/>/>/>3.12 Логические конечные автоматы/>/>/>/> 3.12.1ПроцессыОписываяконкретные алгоритмы, мы отмечали, что вычисление по алгоритму можнорассматривать как некоторый процесс, который описывается множеством состояний,начальным состоянием и правилами перехода из состояния в состояние.
Рассмотримтри варианта таких правил и соответственно три в принципе различных процесса:
· процесс,в котором переходы выполняются под влиянием некоторых внешних воздействий. Этотпроцесс называется автоматом;
· процесс,в котором переходы выполняются под влиянием некоторого случайного механизма.Таких процессов можно придумать много, простейший из них, который будемрассматривать в дальнейшем, называется марковской цепью;
· процесс,в котором переходы выполняются по выбору некоего «одушевленного существа»,стремящегося выбрать такой набор или последовательность решений, которыеобеспечат ему максимальное значение некоторой функции от траектории процесса.Это управляемые процессы.
Разумеется,кроме таких чистых схем имеются и всякого рода смеси. Однако, чистые схемыинтересны тем, что по ним можно увидеть, на что в соответствующей конкретнойнауке обращается особое внимание, и как сильно традиции этой конкретной наукивлияют на изучение одного и того же математического объекта.
/>/>/>/> 3.12.2Конечные автоматыПусть заданы:
М – конечноенепустое множество, элементы которого называются состояниями автомата;
А – конечноенепустое множество внешних воздействий на автомат (входной алфавит автомата);
В-множествоответов автомата на внешние воздействия (выходной алфавит).
Автомат – этопроцесс, который рассматривается в дискретные моменты времени (такты работы) ив каждый момент времени получает внешние воздействия. В зависимости отвоздействия и текущего состояния процесса переходит в новое состояние и вырабатываетсвой ответ.
По сравнениюсо схемой из функциональных элементов конечный автомат является более точноймоделью дискретного преобразователя информации, однако, как и любая модель,понятие конечного автомата связано с рядом упрощающих предположений.
Во-первых,предполагается, что вход (выход) автомата в каждый момент времени можетнаходиться в одном из конечного числа различных состояний. Но у реальногопреобразователя входной сигнал x(t) представляет собойнепрерывную величину, и для описания такого преобразователя с помощью моделиконечного автомата нужно разделить диапазон изменения x(t) на конечное числоуровней и произвести квантование.
Во-вторых,предполагается, что время изменяется дискретно. Это означает, что состояниявхода и выхода устройства отмечаются только в определенные моменты времени,образующие дискретную последовательность
t1, t2,…, tn. Каждый момент времениоднозначно определяется его индексом, поэтому с целью упрощения будем считать,что время tпринимает значения 1, 2, 3,…, n. Промежуток (n, n+1) называется тактом.
Конечныйавтомат является математической моделью реальных дискретных устройств попереработке информации. Структура теории конечных автоматов определяется темизадачами, которые возникают при производстве и эксплуатации таких устройств.
Теория автоматов – раздел теоретической кибернетики, в котором изучаютсяматематические модели (называемые автоматами, машинами) реально существующих(механических, биологических и т. п.) или принципиально возможныхустройств, перерабатывающих дискретную информацию дискретными временнымитактами.
Теория автоматов возникла, главным образом, под влиянием запросов техникицифровых вычислительных и управляющих машин, а также внутренней потребноститеории алгоритмов и математической логики.
Понятие «автомата» заметно варьируется в зависимости от характераназванных устройств, от принятого уровня абстракции и целесообразной степениобщности (автоматы конечные, бесконечные, растущие, вероятностные, детерминированные,автономные и т. п.).
Автомат можно рассматривать как частный случай общего понятия управляющейсистемы. В теории автоматов широко применяется аппарат алгебры, математическойлогики, комбинаторного анализа (включая теорию графов) и теорию вероятностей.
Конечные и бесконечные автоматы характеризуются соответственноконечностью и бесконечностью объема памяти (число внутренних состояний).Конечными автоматами являются отдельные блоки компьютера и даже компьютер вцелом. Мозг тоже можно также рассматривать как конечный автомат. Бесконечныеавтоматы представляют собой естественную математическую идеализацию, вырастающуюиз представления об автомате с конечным, но необратимо большим числомсостояний.
Анализ автоматов – нахождение по заданному в том или ином виде автоматуотображения «вход-выход», осуществляемого этим автоматом; часто такоеотображение можно интерпретировать как вычисление предиката, и поскольку каждыйпредикат характеризуется своим множеством истинности, то задача анализаавтомата сводится к нахождению этого множества (говорят, что это множество распознаетсяавтоматом).
Для многих классов автоматов хорошо известны классы распознаваемых имимножеств. Например, машины Тьюринга распознают все рекурсивно перечислимыемножества, автоматы с магазинной памятью (недетерминированные) – контекстносвободные языки.
Далеко не всегда по заданным автомату и множеству удается определить,распознает ли автомат в точности это множество. В общем виде для произвольногокласса автоматов или даже для произвольного конкретного автомата эта проблема являетсяалгоритмически неразрешимой. Если наложить ограничения на способы заданияавтоматов и на способы задания множеств, то для многих случаев она становится разрешимой.Например, если регулярные события задавать регулярными выражениями, а конечныеавтоматы – матрицами переходов и выходов, то существует общий конструктивныйприем (алгоритм анализа конечных автоматов), позволяющий находить регулярныевыражения для событий, представляемых в произвольном конечном автомате.
Синтез автоматов – построение автоматов по заданномуповедению «вход-выход». Проблема синтеза наиболее подробно исследовалась дляконечных автоматов, поскольку к этому случаю сводятся многие практическиезадачи, связанные с проектированием разного рода управляющих и вычислительныхустройств.
Трудностисинтеза автоматов зависят в основном от того, как заданы условия функционированияавтомата. Чем выразительнее язык, применяемый для задания условийфункционирования аппарата (т. е., чем удобнее он для заказчика), темсложнее метод синтеза. Во многих случаях может оказаться, что единого методасинтеза не существует. Поэтому для ряда классов автоматов, в частности, дляконечных автоматов, разрабатываются специальные языки, с помощью которых удобнозадавать условия функционирования автоматов, для которых существуют методы синтеза(регулярные событияи выражения, логический язык для заданияавтоматов).
Минимизациячисла состояний автомата – по произвольному заданному конечному автоматусоздается автомат с наименьшим возможным числом состояний, обладающий тем жеповедением, что и исходный автомат. Решение этой задачи состоит в нахожденииэффективного алгоритма минимизации. Оно представляет интерес, как в абстрактнойтеории автоматов, так и в проектировании реальных автоматов.
Рассмотриммодели, которые представлены в виде некоторого черного ящика, на вход которогопоступают некоторые логические переменные x1, x2,…, xn. Объект их перерабатывает,и на выходе получаем некоторые логические функции y1, y2,…, yk.
/> /> /> /> /> /> /> /> /> /> /> /> /> <td/> />Рис. 8.Логический конечный автомат
Такие моделиназывают логически конечными автоматами. Существуют некоторые классы таких автоматов:
- автоматыбез памяти (комбинационные)
- автоматыс памятью (последовательностные).
/>/>/>3.12.2.1 Конечные автоматы без памяти (комбинационные)
Общая формула,описывающая этот вид автоматов:
/>, i = 1, 2, …, k.
/> – в векторной форме
Пример 1.
Примеромтаких автоматов является простая экспертная система профессиональнойпригодности, где входные значения – это ответы на n вопросов, а выходные – k выводов о том, может личеловек работать в данной области.
Пример 2.
Диагностиканеисправностей, заболеваний и т. д.
Пример 3.
Пустьфункционирование логического автомата описывается формулой:
/>.
На языке Pascal оператор присваивания,соответствующий этой формуле:
/>
Для болеесложной модели получается структура типа запись:
Type
Prep= record
Number:Integer;
Stroka:String;
Zn:Boolean;
End;
Далеемоделируется базис, который будет работать с этими высказываниями. Для каждойлогической операции пишем процедуру или функцию.
Function otr (a: prep; var b: prep; параметры сохранения и т. д.): Boolean;
Functioncon (a, b: prep; var c: prep; параметры сохранения и т. д.): Boolean;
Functiondiz (a, b: prep; var c: prep; параметры сохранения и т. д.): Boolean;
Пример 4.
Отмоделироватьфункцию Yi:
/>
Высказывание моделируется записью:
Functiony1 (x1, x2, x3, x4: prep; var rez:prep; sohr: Boolean; newnumber: Integer; t: String): Boolean;
Var
I:boolean; a, b, c, d, e,: prep;
Begin
I:=otr(x1, a, false, 0);
I:=otr(x2, b, false, 0);
I:=con (a, b, c, false, 0);
I:=con (c, x3, d, false, 0);
I:=otr(x3, a, false, 0);
I:=otr(x4, a, false, 0);
I:=con(x2, a, c, false, 0);
I:=con (c, b, e, false, 0);
I:=diz (d, e, rez, false, 0);
Ifsohr then begin
rez.number:=newnumber;
rez.stroka:=t;
end;
y1:=rez.znachenie;
end;
Отмоделироватьфункцию лучше программным путем, т. к. программу довольно простомодифицировать.
/>/>/>3.12.2.2 Конечные автоматы с памятью (последовательностные)
Для такихавтоматов характерно наличие вектора внутренних состояний z=(z1, z2,…, zm).
В такихавтоматах каждая логическая функция зависит от входных функций x и функций внутреннегосостояния z.
/>
Рис. 10.Конечный автомат с памятью
/>
/>. (8)
Для автоматовс памятью характерно, что они функционируют во времени, и в момент времени t0должно быть заданоначальное состояние z0. В момент времени t0/> определяетсявыражением (8). В момент времени t1=t0+t входной вектор можетпоменяться, в свою очередь может поменяться вектор состояний Y.
/>, (9)
где t –такт логического конечного автомата. Считается, что t много больше временирасчета на ЭВМ.
Пример.
Та же самаяэкспертная система определения профессиональной пригодности, но с условием, чтозначение о профессиональной пригодности зависит от ранее полученных ответов. Такиеэкспертные системы называют самообучающимися, т. к. сразу правильногоответа не дают. Частным случаем конечного автомата с памятью является автомат собратной связью по выходу. Для него вектор внутренних состояний в моментвремени t+tравен вектору выходных сообщений в момент времени t. Пример конечногоавтомата с памятью и обратной связью по выходу приведен на рис. 11.
/>
Рис. 11.Конечный автомат с памятью и обратной связью по выходу
Экспертнаясистема является примером конечного автомата с памятью с обратной связью повыходу. Программная модель такого автомата базируется на программной моделиавтомата без памяти, однако, помимо уже накопленного опыта добавляетсяпроцедура tact, а также начальные значения входных и выходных переменных.
Const
N=…;k=…;
Type
Vectorx = array [1..n] of boolean;
Vectory = array [1..k] of boolean;
Var
X:vector X;
Ypred,Y: vector Y;
Proceduretact (v: vector X; var Ypred, Y: vector Y);
Var
I:integer;
Begin
Y[1]:=y1(…);
Y[2]:=y2(…);
Y[3]:=y3(…);
Y[k]:=yk(…);
Fori:=1 to k do
Ypred[i]:=Y[i];
End;
End.
Состояниеконечного автомата называется установившимся, если с течением времени припостоянном значении входного вектора Х, вектор Y принимает постоянное значение.В этом случае процесс обучения конечного автомата заканчивается, и результатыего работы могут быть использованы. Однако существуют автоматы, состояние которыхне устанавливается с течением времени. Такие автоматы используются только всхемотехнике. Примером такого автомата является автомат триггерного типа. Логическаясхема триггера приведена на рис. 12.
/>
Рис. 12.Автомат триггерного типа
Другимчастным случаем является автономный конечный автомат, для которого векторвходных воздействий /> отсутствует. Длянего вектор выходных состояний является функцией от вектора внутреннихсостояний />. Для него />(с обратной связью повыходу), тогда />. Такие конечныеавтоматы называют также генераторами высказываний или генераторами логическойпоследовательности. Они могут использоваться для отладки и моделированиянекоторых ситуаций.
/>/> Контрольныевопросы1. Что такоелогический конечный автомат?
2.Представьте в виде рисунка логический конечный автомат.
3. Что такое тактконечного логического автомата?
4. Приведитепример конечного автомата без памяти.
5. Приведитепример конечного автомата с памятью.
6. Приведитепример конечного автомата с обратной связью по выходу.
/>/>/>/>/>Библиографическийсписок
1. Акимов В.А. Дискретнаяматематика: логика, группы, графы. М.: Лаборатория Базовых Знаний, 2003, 376 с.
2. Стол Роберт Р. Множества.Логика. Аксиоматические теории. Пер. с англ. Ю.А. Гастева И.Х. Шмаина.Под ред. Ю.А. Шихановича. М., «Просвещение», 1968, 232 с.
3. Ершов Ю.А., Полюнин Е.А. Математическаялогика: Учебное пособие для вузов. М.: Наука. Гл. ред. физ. – мат. лит., 1987,336 с.
4. Лавров И.А., Максимова Л.Л. Задачипо теории множеств, математической логике и теории алгоритмов. М.: Высшаяшкола, 2003, 256 с.
5. Р. ХаггартиДискретная математика для программистов Москва: Техносфера, 2003, 320 с.
6. Гончарова Г.А., Мочалин А.А. Элементыдискретной математики: Учебное пособие. – М.: ФОРУМ: ИНФРА-М, 2004, 128 с.
7. Судоплатов С.В., Овчинникова Е.В. Элементыдискретной математики: Учебник. – М.: ИНФРА – М; Новосибирск: НГТУ, 2003, 280 с.– (Серия «Высшее образование»)
8. Новиков Ф.А. Дискретнаяматематика для программистов. – СПб: Питер, 2001, 304 с.: ил.