Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Алгоритм Квайна построения сокращенной ДНФ.

Читайте также:
  1. III. Произвести анализ риска путем построения дерева событий.
  2. Аксиоматический способ построения теории
  3. Алгоритм RSA
  4. Алгоритм виконання часткового технологічного процесу
  5. Алгоритм выборки сообщений из очереди потока
  6. Алгоритм выполнения манипуляции
  7. Алгоритм выполнения манипуляции
  8. Алгоритм выполнения манипуляции
  9. Алгоритм вычисления выражений в обратной польской записи
  10. Алгоритм Дейкстры

1. Получить СДНФ функции f.

2. Провести все операции неполного склеивания.

3. Провести все операции поглощения.

Пример 1. Построим сокращенную ДНФ для функции, приведенной в таблице 3.1.

Таблица 3.1

x y z t 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
f 1 1 1 1 0 1 0 0 1 0 1 0 1 1 1 1

 

1. Строим СДНФ функции f:

. Пронумеруем дизъюнктивные члены в полученной СДНФ в порядке от 1 до 11.

2. Проводим все операции неполного склеивания.

Первый этап склеивания в таблице 3.2.

После первого этапа склеиваний (и возможных поглощений) получаем, что

Пронумеруем дизъюнктивные члены в полученной ДНФ в порядке их следования от 1 до 15.

Второй этап склеиваний в таблице 3.3.

После второго этапа склеиваний и последующих поглощений получаем, что Это и будет сокращенной ДНФ для функции f, ибо дальнейшие склеивания невозможны.

Таблица 3.2

Слагаемые Склеивание по Результат
1,2 T
1,3 Z
1,6 X
2,4 Z
2,5 Y
3,4 T
3,7 X
5,9 X
6,7 Z
6,8 Y
7,10 Y
8,9 T
8,10 Z
9,11 Z xyt
10,11 T xyz

 

Таблица 3.3


Дата добавления: 2014-11-13; просмотров: 14; Нарушение авторских прав


<== предыдущая лекция | следующая лекция ==>
Минимизация нормальных форм | Алгоритм построения сокращенной ДНФ с помощью КНФ
lektsii.com - Лекции.Ком - 2014-2019 год. (0.008 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты