WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 3 | 4 ||

На практике тождественность формул доказывается аналитически путем приведения их к ДНФ с помощью правил булевой алгебры, суперпозиции (т.е. замены одних формул другими равносильными формулами согласно таблицам булевых функций одной и двух переменных (табл. 1 и 2)), эквивалентных преобразований и минимизации формул (1–22).

Пример. Рассмотрим функцию предыдущего примера. Из табл. видно, что она содержит одну конституенту 0 вида: x y z, т. е.

функцию можно представить следующей формулой f (x, y, z) = x y z.

Докажем аналитически тождественность двух формул представления функции:

f (x, y, z) = (x y) y z = (x y) ( yz yz) = x y ( yz yz) = = x y (( y z)( y z )) = x y ( yy zy yz zz ) = = x y yz yz = x y(1 z ) yz = x y yz = x y(1 z) yz = = x y yz yz = x y z( y y) = x y z.

1 2 3 4 5 6 7 Конститу- Конституx y z f31 (x, y, z) енты 1 енты 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 Для функции, заданной своим номером fN (x1, x2, …, xn), значения для каждого набора в таблице истинности однозначно определяются двоичным кодом номера N согласно алгоритму, описанному выше (с.

32). По значениям функции определяются конституенты 1 и конституенты 0, а по ним создаются СДНФ и СКНФ функции в соответствии с алгоритмом, представленным в примере на с.18. Для дальнейшего упрощения рекомендуется выбирать форму с меньшим числом конституент, но, как показывает практика, формулы ДНФ упрощаются быстрее.

Используя соотношения (1–22), исходную форму приводят к одной из тупиковых ДНФ, которая может оказаться минимальной ДНФ.

Пример. Для функции f31 (x, y, z) построить таблицу истинности, получить ее СДНФ и СКНФ, упростить одну из форм до формулы тупиковой ДНФ и проверить, что ее значения на всех наборах соответствуют значениям исходной функции.

Двоичный код числа 31 имеет вид: 1 1 1 1 1 0 0 0 (старший разряд), что отражено в таблице истинности функции (столбец 4):

Из конституент 1 можно получить СДНФ функции:

f31(x, y, z) = xyz xyz xyz xyz xyz, а из конституент 0 получим СКНФ функции:

f31(x, y, z) = (x y z) (x y z ) (x y z).

Для упрощения выберем СДНФ функции:

f31(x, y, z) = xyz xyz xyz xyz xyz = = yz xz xz xy = yz x xy = x yz.

Дадим пояснения по шагам упрощения булевых формул. На первом шаге, используя свойство идемпотентности (3), добавим 4-й и 5-й члены, а затем по правилу (19) склеим последовательно 1-й, 3-й и 4-й члены с 5-м, а также 2-й с 4-м. На втором шаге (из четырех членов) склеиваются 2-й и 3-й. На третьем шаге (из трех членов) 2-й член поглощает 3-й.

В результате упрощения получается тупиковая ДНФ из двух членов, которая является минимальной ДНФ для данной функции. Для проверВарианты булевых функций Таблица № вар. f (x, y, z) fN (x, y, z) 0 f95 (x, y, z) 1 f249 (x, y, z) 2 f63 (x, y, z) 3 f125 (x, y, z) 4 f59 (x, y, z) 5 f62 (x, y, z) 6 f111 (x, y, z) 7 f94 (x, y, z) 8 f89 (x, y, z) 9 f68 (x, y, z) ки последней формулы вычислены значения ее компонентов и формулы в целом (столбцы 7 и 8). Значения столбцов 4 и 8 совпадают, следовательно, упрощенная ДНФ представляет исходную функцию.

Работа с булевыми функциями В соответствии с вариантом задания, приведенным в табл. 7, выполнить следующие пункты задания.

1. Для булевой функции f (x, y, z), представленной формулой в столбце 2, построить таблицу истинности, вычислить десятичный номер функции.

Содержание Предисловие............................................................................................ 1. Цели и задачи курса............................................................................ Объем дисциплины..................................................................... 2. Содержание курса дисциплины....................................................... Раздел 1. Множества и их спецификации...................................... Раздел 2. Отношения на множествах............................................... Раздел 3. Основные понятия теории графов.................................. Раздел 4. Основные понятия неориентированного графа............ Раздел 5. Основные понятия для ориентированного графа......... Раздел 6. Булевы (переключательные) функции (БФ)................... 3. Контрольное задание........................................................................ Основные понятия теории множеств....................................... Перечисление элементов........................................................... Описание характеристического предиката.............................. Определение множества с помощью порождающих процедур Основные понятия теории множеств....................................... Обработка ориентированного графа........................................ Обработка ориентированного графа........................................ Работа с булевыми функциями................................................. Работа с булевыми функциями................................................. Библиографический список..............................................................

Pages:     | 1 |   ...   | 3 | 4 ||










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.