Лидеры рейтинга

ID: 226425

Konstantin Shvetski

Мастер-Эксперт

942

Россия, Северодвинск


ID: 259041

Алексеев Владимир Николаевич

Мастер-Эксперт

510

Россия, пос. Теплоозёрск, ЕАО


ID: 401284

Михаил Александров

Академик

352

Россия, Санкт-Петербург


ID: 137394

Megaloman

Мастер-Эксперт

310

Беларусь, Гомель


ID: 400669

epimkin

Профессионал

190


ID: 400484

solowey

Профессор

70


ID: 401888

puporev

Профессор

52

Россия, Пермский край


8.1.6

02.01.2021

JS: 2.2.2
CSS: 4.2.0
jQuery: 3.5.1


 

Консультации и решение задач по алгебре, геометрии, анализу, дискретной математике.

Администратор раздела: Коцюрбенко Алексей Владимирович (Старший модератор)


Коцюрбенко Алексей Владимирович
Статус: Старший модератор
Рейтинг: 2134
Konstantin Shvetski
Статус: Мастер-Эксперт
Рейтинг: 942
Михаил Александров
Статус: Академик
Рейтинг: 352
 

Перейти к консультации №:
 

Консультация онлайн # 200090
Раздел: • Математика
Автор вопроса: xamatora29 (Посетитель)
Дата: 13.01.2021, 22:53
Поступило ответов: 1

Здравствуйте, уважаемые эксперты! Прошу вас ответить на следующий вопрос: Используя метод Квайна, необходимо найти МДНФ функции
f(x1,x2,x3,x4), принимающей значение 1 на наборах 2, 4, 6, 9, 10, 11, 12, 13. Буду очень благодарен за помощь!

Состояние: Консультация закрыта

Здравствуйте, xamatora29!

Составим таблицу истинности функции:

и запишем совершенную ДНФ (СДНФ):

Далее используем метод Квайна. На первом этапе преобразуем СДНФ в сокращённую ДНФ, воспользовавшись правилами склейки и поглощения:

где A - любая конъюнкция. Применим эти правила ко всем подходящим парам конъюнкций СДНФ (то есть отличающимся только по одной переменной):








Запишем получившуюся ДНФ :

Дальнейшие склеивания и поглощения невозможны, следовательно, получена сокращённая ДНФ (содержащая только простые импликанты).
На втором этапе преобразуем сокращённую ДНФ в минимальную ДНФ, убирая из неё все лишние простые импликанты. Это можно сделаеть с помощью импликантной матрицы Квайна, строки которой соответствуют простым импликантам (то есть компонентам сокращённой ДНФ), а столбцы - компонентам исходной СДНФ:

Отметим те клетки матрицы, для которых соответствующая простая импликанта поглощает соответствующую компоненту СДНФ. Далее отыщем все столбцы, содержащие одну отмеченную клетку. Соответствующие этим клеткам простые импликанты называются базисными и образуют ядро функции. Если ядро накрывает все столбцы импликантной матрицы, то оно и является минимальной ДНФ. В противном случае рассматриваем совокупности простых импликант, не входящих в ядро и накрывающих остальные столбцы импликантной матрицы, выбирая варианты с минимальным суммарным числом букв.
В составленной матрице столбцов, содержащих одну отмеченную клетку, нет, при этом каждая простая импликанта покрывают два из восьми столбцов (и содержит три буквы). Следовательно, чтобы покрыть все столбцы, МДНФ должна содержать четыре простых импликанты (возможно, больше). Возможны два варианта такой МДНФ:

и

содержащие одинаковое число букв.


Консультировал: Коцюрбенко Алексей Владимирович (Старший модератор)
Дата отправки: 18.01.2021, 19:32

Рейтинг ответа:

+1

[подробно]

Сообщение
модераторам

Отправлять сообщения
модераторам могут
только участники портала.
ВОЙТИ НА ПОРТАЛ »
регистрация »

Возможность оставлять сообщения в мини-форумах консультаций доступна только после входа в систему.
Воспользуйтесь кнопкой входа вверху страницы, если Вы зарегистрированы или пройдите простую процедуру регистрации на Портале.