Дискретная математика
Пример.
Конъюнкции,
то есть все
функции вида
,
тоже составляют
замкнутый
класс. Очевидно,
однако, что,
например, функцию,
которая на
наборе (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 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
|
0 1 – 1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
|
0 1 1 – |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
|
– 1 0 1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
|
1 1 0 – |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
|
1 1 – 0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
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 |
|
0 |
0 |
0 |
0 |
0 |
00 |
00 |
00 |
00 |
00 |
00 |
000 |
000 |
000 |
000 |
0000 |
0 |
|
1 |
1 |
0 |
0 |
0 |
10 |
10 |
10 |
00 |
00 |
00 |
100 |
100 |
100 |
000 |
1000 |
0 |
|
2 |
0 |
1 |
0 |
0 |
01 |
00 |
00 |
10 |
10 |
00 |
010 |
010 |
000 |
100 |
0100 |
1 |
|
3 |
1 |
1 |
0 |
0 |
11 |
10 |
10 |
10 |
10 |
00 |
110 |
110 |
100 |
100 |
1100 |
0 |
|
4 |
0 |
0 |
1 |
0 |
00 |
01 |
00 |
01 |
00 |
10 |
001 |
000 |
010 |
010 |
0010 |
0 |
|
5 |
1 |
0 |
1 |
0 |
10 |
11 |
10 |
01 |
00 |
10 |
101 |
100 |
110 |
010 |
1010 |
1 |
|
6 |
0 |
1 |
1 |
0 |
01 |
01 |
00 |
11 |
10 |
10 |
011 |
010 |
010 |
110 |
0110 |
1 |
|
7 |
1 |
1 |
1 |
0 |
11 |
11 |
10 |
11 |
10 |
10 |
111 |
110 |
110 |
110 |
1110 |
1 |
|
8 |
0 |
0 |
0 |
1 |
00 |
00 |
01 |
00 |
01 |
01 |
000 |
001 |
001 |
001 |
0001 |
0 |
|
9 |
1 |
0 |
0 |
1 |
10 |
10 |
11 |
00 |
01 |
01 |
100 |
101 |
101 |
001 |
1001 |
0 |
|
10 |
0 |
1 |
0 |
1 |
01 |
00 |
01 |
10 |
11 |
01 |
010 |
011 |
001 |
101 |
0101 |
1 |
|
11 |
1 |
1 |
0 |
1 |
11 |
10 |
11 |
10 |
11 |
01 |
110 |
111 |
101 |
101 |
1101 |
0 |
|
12 |
0 |
0 |
1 |
1 |
00 |
01 |
01 |
01 |
01 |
11 |
001 |
001 |
011 |
011 |
0011 |
1 |
|
13 |
1 |
0 |
1 |
1 |
10 |
11 |
11 |
01 |
01 |
11 |
101 |
101 |
111 |
011 |
1011 |
1 |
|
14 |
0 |
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 |
0 |
Итак, все коды на строках, заканчивающихся нулевыми значениями функции, исключаются автоматически. Если эти коды попадают на строки, заканчивающиеся единичным значением функции, то они также не учитываются. Остаются только те коды, которые расположены на строках с единичным значением функции (эти коды затемнены).
Далее
руководствуются
следующим
правилом. Для
того чтобы
функция приняла
значение, равное
единице, достаточно
того, чтобы
только какая-нибудь
одна импликанта
на строке приняла
единичное
значение. Прежде
всего, оставляем
минимальную
импликанту
,
которая перекрывает
единицы в строках
2, 6, 10 и 14. Затем,
естественно,
обращаемся
к 12 ой строке.
Здесь оставляем
единственный
на строке код
011, что отвечает
импликанте
.
Эта же импликанта
ответственна
за 13 ую строку,
оканчивающуюся
тоже единицей.
Осталось рассмотреть
5 ую и 7 ую строки.
Общей для них
является импликанта:
.
Таким образом,
тремя импликантами
мы перекрыли
все единичные
значения функции,
что совпадает
с результатом,
полученным
на основе таблиц
Куайна.
3. Существует графический способ склеивания, который получил название метод карты Карно (представлен в табл. 10). Выделяем смежные единицы, это и будут слагаемые нашей функции.
Таблица 10
|
x3x4 x1x2 |
00 |
01 |
11 |
10 |
|
00 |
0 |
0 |
1 |
1 |
|
01 |
1 |
0 |
0 |
0 |
|
11 |
1 |
0 |
0 |
0 |
|
10 |
0 |
0 |
0 |
0 |
– получили
два слагаемых
Хотя табл. 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* |
0 |
1* |
0 |
|
01 |
1* |
1 |
1 |
1* |
|
11 |
0 |
0 |
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 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 1 1 1 1 0
|
|
Сложность представления функции с помощью УБДР существенно зависит от порядка переменных. Так, например, УБДР для иного порядка переменных, чем на рис. 4, содержит четыре вершины, а не три (рис. 5). Интересной проблемой теоретической информатики является нахождение алгоритма, дающего оптимальный порядок переменных булевой функции с точки зрения представления этой функции упорядоченной БДР.

Рис. 5.
УБДР для функции
с порядком
переменных
[p,
q,
r]
3.11 Построение логических схем
При синтезе логических схем применяют элементы с одним и несколькими входами. Условия функционирования таких элементов определяются переключательными функциями одной или нескольких переменных.
Входные и выходные сигналы логических схем зависят от времени (одни из них в некоторый момент времени равны 1, в другие моменты времени 0). Логические функции, описывающие работу таких схем, называют переменными. Используют также схемы, для которых во все моменты времени сигналы равны либо 1, либо 0. Логические функции, описывающие работу этих схем, называют постоянными.
Существует только четыре различные переключательные функции одной переменной. Как видно из таблицы 14, только две функции не зависят от переменной А (в этих случаях переменная А фиктивна).
Таблица 14
|
Х |
А |
Условное обозначение |
Название функции |
|
0 1 |
|||
|
X0=f0 (A) X1=f1 (A) X2=f2 (A) X3=f3 (A) |
0 0 0 1 1 0 1 1 |
0 A
1 |
Константа 0 Переменная А Инверсия А Константа 1 |
Для функции двух переменных существует шестнадцать различных переключательных функций. Как видно из таблицы 5, только десять функций существенно зависят от переменных А и В.
На рис. 6, 7 приведены обозначения элементов, реализующих некоторые переключательные функции двух переменных.
Каждой элементарной логической операции можно поставить в соответствие элементарную логическую схему или вентиль. На входе и выходе вентиля мы имеем логические сигналы двух видов, что можно ассоциировать с логическим 0 или логической 1.
1. Элемент «И» 2. Элемент «ИЛИ» 3. Элемент «НЕ»

F=x1∙x2
F=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.
![]()
![]()

![]()

![]()

![]()
![]()
![]()
![]()
Рис. 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;
Function con (a, b: prep; var c: prep; параметры сохранения и т. д.): Boolean;
Function diz (a, b: prep; var c: prep; параметры сохранения и т. д.): Boolean;
Пример 4.
Отмоделировать функцию Yi:
![]()
Высказывание моделируется записью:
Function y1 (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);
If sohr 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)
Для автоматов с памятью характерно, что

