Постановка задачи. Основной задачей, для решения которой предназначена экспертная система CIOS, является построение и оптимизация таблиц истинности заданных логических схем

Основной задачей, для решения которой предназначена экспертная система CIOS, является построение и оптимизация таблиц истинности заданных логических схем. Логической схемой будем называть объединение некоторых примитивных логических элементов. Полный список и описание логи­ческих элементов, используемых в данном примере, приведены в табл. 14.1.

Таблица 14.1. Примитивные логические элементы

Логический элемент	Описание
SOURCE	Источник— элемент, представляющий собой вход логической схемы. Имеет один выход и не имеет входов. Считается, что первоначальный сигнал появляется в этом элементе и сразу передается следующему логическому элементу
LED	Индикатор — элемент, моделирующий выход логической схемы. Является противоположностью источнику, имеет один вход и не имеет выходов. Считается, что при получении сигнала индикатор просто отображает его
SPLITTER	Разделитель. Данный элемент предназначен для деления сигнала. Имеет один вход и два логических выхода. Полученный сигнал без изменения передается на оба выхода разделителя
NOT	Логическое НЕ. Имеет один вход и один выход. Меняет полученный сигнал на противоположный
AND	Логическое И. Имеет два входа и один выход. Возвращает 1, если оба полученных сигнала равны 1. В противном случае возвращает 0
OR	Логическое ИЛИ. Имеет два входа и один выход. Возвращает 1, если хотя бы один из полученных сигналов равен 1. В противном случае возвращает 0
NAND	Отрицание логического И. Имеет два входа и один выход. Возвращает 0, если оба полученных сигнала равны 1. В противном случае возвращает 1
XOR	Исключающее ИЛИ. Имеет два входа и один выход. Возвращает 1, если полученные сигналы не равны. В противном случае возвращает 0

При составлении логической схемы из примитивных элементов обязательными являются следующие правила:

Ø выход каждого логического элемента связан с одним и только одним входом другого элемента;

Ø вход каждого логического элемента связан с одним и только одним выходом другого элемента;

Ø исходные сигналы подаются на источники логической схемы, не имеющие входов;

Ø исходный сигнал перемещается по логической схеме, за условную единицу времени — такт;

Ø по завершении такта обработанный сигнал оказывается на логических индикаторах схемы.

Таблицей истинности называется таблица, содержащая всевозможные наборы сигналов, принимаемые источниками логической схемы, и обработан­ный результат, полученный на индикаторах схемы для каждого набора. Например, для простейшей логической схемы, приведенной на рис. 14.1, таблица истинности представлена в табл. 14.2.

Рис. 14.1. Простейшая логическая схема

Таблица 14.2. Пример простейшей таблицы истинности

SOURCE-1	SOURCE-2	LED-1

Количество столбцов таблицы истинности очевидно равно числу источни­ков и индикаторов схемы. Количество строк — числу 2, возведенному в степень числа источников, т. е. при одном источнике 2¹ = 2, при двух 2² = 4, при трех 2³ = 8 и т. д. Таким образом, таблица истинности может принимать весьма внушительные размеры. Уже при 6-ти источниках коли­чество строк в ней равняется 64.

Очевидно, что возможны ситуации, когда изменение значения одного из входов не влияет на результат при постоянных значениях остальных входах. В этом случае таблицу можно оптимизировать, объединив такие строчки и заменив значение невлияющего на результат входа на символ *. В представ­ленном выше примере можно объединить первую и вторую строку таблицы, т. к. при любом значении, подаваемом на источник SOURCE-2 в случае, если на источник SOURCE-1 подается 0, результат будет равен 0. Таким образом, оптимизированная таблица примет вид, приведенный в табл. 14.3.

Таблица 14.2. Оптимизированная таблица истинности

SOURCE-1	SOURCE-2	LED-1
	*

В данном примере преимущества оптимизированных таблиц истинности не очень заметно. Однако при составлении таких таблиц для достаточно больших логических схем преимущества очевидны. Эффект, полученный от оп­тимизации таблицы истинности, сильно зависит от конкретной анализируемой логической схемы.

Следует отметить, что оптимизация таблиц истинности неоднозначна. Но конечный результат (количество строк в итоговой таблице) всегда одинаков. Наш простой пример можно было оптимизировать так, как представлено в табл. 14.4.

Таблица 14.4. Еще один пример оптимизированной таблицы истинности

SOURCE-1	SOURCE-2	LED-1
*

Для разработки и тестирования экспертной системы CIOS будем использовать логические схемы, приведенные на рис. 14.2—14.4. Сокращения даны в табл. 14.5.

Таблица 14.5. Сокращения названий логических элементов

Название логического элемента	Используемое сокращение
SOURCE	S
LED	L
SPLITTER	P
NOT	N
AND	A
OR	O
NAND	D
XOR	X

Рис. 14.2. Схема 1

Рис. 14.3. Схема 2

Рис. 14.4. Схема 3