ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.04.2024
Просмотров: 62
Скачиваний: 1
А вот эта формула не является записанной
в С Д Н Ф :
АВС+АВС
В этой формуле в первом слагаемом нет высказы вания С, нет и его отрицания.
От всякой дизъюнктивной нормальной формы лег ко перейти к С Д Н Ф .
Рассмотрим на примере, как это делается. Пусть нам дана формула, не записанная в С Д Н Ф :
А+АВ
в
(В первом слагаемом |
нет ни |
В, ни В.) |
|
Поступаем так — первое |
слагаемое, в котором от |
||
сутствует буква |
В, |
умножаем на (В + В ) = 1, от |
|
этого значение X |
не изменится. |
ЭС=А(В+В)+АВ =АВ+АВ+АВ
Полученная формула уже записана в С Д Н Ф , ибо все слагаемые содержат все простые высказывания либо их отрицания.
Еще пример:
10 В. Касаткин |
145 |
ОС = АВС + АВ
Второе слагаемое, где нет ни С, ни С, умножаем на (С + С ) = 1.
Ж=АВС+АВ(С+С)=АВС+ АВС+АВС+ДВС
Итак, каждую формулу можно записать в С Д Н Ф . Минимизация любой формулы и начинается с того, что данную формулу записывают в С Д Н Ф .
Для каждого сложного высказывания, в соответ ствии с его формулой, можно построить геометриче скую модель.
Каждую формулу, в которой используются три простых высказывания, можно изобразить на трех мерном кубе. Куб помещают в начало пространст венной системы координат, оси называют теми же буквами, которыми обозначены простые высказыва ния данной формулы.
Дана формула:
ЭС=АВС+АВС+АВС+АВС
Вот как она изображается на кубе:
146
Еще один пример:
Ж=АВС+АВС + АВС
Как же используются для минимизации геометри ческие модели формул?
10* |
147 |
Пусть дана формула: X = А ВС + АВС. Геомет рическая ее модель такова:
т
ш
Отмечены две соседние вершины. Обращаем вни мание на то, что возможно склеивание по букве С. Тогда имеем X = АВ. Ребро с отмеченными верши
нами было параллельно С, |
и склеивание произошло |
по атой же букве. |
|
Каждому ребру можно |
приписать название. |
А
143
Пусть некая формула нанесена на куб — имеется три ребра с отмеченными вершинами:
Используем для записи формулы названия ребер:
0С=АВ+АС +ВС
Восстановим первоначальную формулу — формулу, которая заносилась на куб:
Х=АВС+ АВС+АВС+АВС
143
Еще пример:
Запишем формулу, используя названия ребер:
ЗС=АВ + АВ
Восстановим первоначальную формулу:
СС=АВС+АВС+АВС+АВС
Формулы, для записи которых использованы все без исключения ребра с отмеченными вершинами, называются с о к р а щ е н н ы м и .
159
Пример:
Имеются четыре отмеченные вершины и три ребра. Используя названия всех трех отмеченных ребер, получаем сокращенную форму данной на кубе фор
мулы:
0С = АВ + АВ +АС
Но для получения формулы можно воспользовать ся не тремя, а двумя названиями ребер. Эти ребра на чертеже отмечены черточками.
__ Тогда вместо суммы А ВС + А ВС мы напишем ВС, а вместо суммы А ВС + А ВС напишем А С :
Ж=ВС +АС
151
Если удается использовать не все названия ребер, но так, что все вершины оказываются «покрытыми ребрами», то приходят к одной из м и н и м а л ь н ы х форм записи формул. Минимальных „ форм может быть несколько. Рассмотрите пример:
А.
Ч В
Вершины данной модели покрываются тремя реб рами, но в нескольких вариантах. Каждая из полу чаемых записей есть одна из минимальных форм.
Интересен случай, когда отмеченными вершинами являются вершины одной грани:
{52
В данном случае имеем занесенную на куб фор' мулу:
ЭС=АВС+АВС+АВС+АВС
Если использовать названия ребер, покрывающих отмеченные вершины, то формула примет вид:
X —АВ +АВ
или зс=ВС+ВС
В каждой из полученных формул возможно склеи вание, и тогда формула будет иметь иной вид.
Действительно, все отмеченные вершины, обладают тем свойством, что они сдвинуты по направлению «В». Это дает основание приписать для данной грани название — «В ».
На следующем чертеже указаны все грани и их наименования:
153
Если окажется, что отмеченные вершины принад лежат одной грани, то можно сумму из четырех сла гаемых заменить одной буквой — названием грани.
Пример:
В
Отмечена грань «А ». К названию грани присоеди няем название ребра и получаем минимальную форму:
154
СС = А + ВС
ЗС= В +АС
А если сложное высказывание содержит не три простых высказывания, а четыре? Как поступают
вэтом случае?
Вэтом случае используется четырехмерный куб. Вот возможный вариант вычерчивания такого че
тырехмерного куба:
155
4 4
Четыре |
направления |
имеются здесь: три обычных |
|
(А , В |
и |
С ) и |
одно новое — направление |
«вовнутрь» — «Д ». |
|
||
Вот |
как можно записать координаты вершин, от |
||
меченных на чертеже: |
|
1-АВСД 2-АВСД з-АВСД
4-АВСД 5-АВСД 6-АВСД
В четырехмерном кубе имеются ребра, грани я подкубы. Как использовать то, что при нанесении формулы оказывается отмеченным ребро, или грань, или подкуб, догадайтесь сами.
Для примера мы приводим куб с нанесенной фор мулой и формулой, полученной после минимизации:
156
|
|
О Г Л А В Л Е Н И Е |
|
||
Г л а в а |
1, |
|
|
|
|
Как |
считают кибернетики. |
Приятные |
|||
сю рпризы двоичной системы. Умножать |
|||||
немного |
труднее . |
Вычитание |
требует |
||
больш е внимания. Делить помогает вы |
|||||
читание |
............................................ |
|
|
.... 9 |
|
Рассказ |
К и ................б ы |
............................ |
|
28 |
|
Г л а в а |
2. |
|
|
|
|
Алгебра |
высказываний. |
Предложения |
|||
мож но умножать. Как складывают вы |
|||||
сказывания. Отрицание. |
Ф орм улы слож |
||||
ных |
высказываний. |
Таблицы |
истины |
и лжи. Свойства логических операций. Отрицание сложных высказываний. О т
сложного к п р о с т о м у ........................ |
31 |
Рассказ К и б е р а ......................................... |
56 |
Г л а в а |
3. |
|
Обыкновенные задачи |
необыкновенной |
|
алгебры ..................................... |
59 |
|
Рассказ |
К и б ы .............................................. |
67 |
153
Г л а в а |
4. |
|
|
|
|
Логические |
элементы |
— клетки |
мозга |
||
«умных» машин. Таинственное «НЕ», Важ |
|||||
ное «И» и лю безное «ИЛИ». О т простого |
|||||
к сложному. |
Логика |
и |
автоматы . . . |
||
Рассказ |
Киби «о |
гадком |
у т е н к е » ................ |
102 |
|
Г л а в а |
5. |
|
|
|
|
Задачи для ум елы х |
............................. |
|
105 |
||
Рассказ |
К и б е р а ......................................... |
|
|
Ш |
|
Г л а в а |
6. |
|
|
|
|
Ответы и р е ш е н и я ............................... |
|
|
114 |
||
П р и л о ж е н и е .................................. |
|
|
143 |