Карты карно для 5 переменных. Правила минимизации с использованием карт карно

Лекции по теории автоматов. Логические основы цифровых автоматов

Сохрани ссылку в одной из сетей:

3. Отыскание минимального покрытия.

Оставляем минимальное число первичныхимпликант, которые в совокупностипокрывают все столбцы. Такие импликантыназовем существенными, а остальныенесущественными или лишними.

Поскольку второй столбец покрываетсяединственным образом, то выделеннаяимпликанта (последняя в списке), заведомоявляется существенной; столбцы, которыеона покрывает, можно вычеркнуть, аимпликанту запомнить. Подобным образом
на различных шагах поиска определяютсяи другие существенные импликанты, выборкоторых обязателен.

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

1. Удаление поглощенныхстрок.

2. Удаление поглощающих столбцов.

3. Выбор заведомо существенной, как было разъяснено выше, строки (в нашем методе – соответствующей первичной импликанты).

Эти трипункта могут повторяться сколько угоднораз в любой последовательности. Нижеприведен пример поглощенной строки.

* * *

* * поглощенная строка

Поглощенная строка содержитподмножество отметок “*”, имеющихсяв некоторой другой (поглощающей)строке. Поглощенная строка может бытьудалена по очевидным причинам. Приобнаружении пары столбцов, один изкоторых является поглощающим, а другой– поглощенным, удалить следует первыйиз них.

* *

*

* *

поглощающий

столбец

В нашем случае останутся три существенныеимпликанты:

МДНФ: f(x1, x2,x3, x4)=. Характеристики найденной формы:

Ca= 8, Cb= 11.

Отметим, что при возрастании “размеразадачи” (числа переменных и числа
0-кубов) указанные выше пункты алгоритмана отдельных шагах его работы могутоказаться неприменимыми. В этом случае,если отыскивается точное решение,возникает необходимость перебора подереву решений, поэтому данная задачав общей постановке является трудноразрешимой.

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

2.2.2. Карты Карно

Карты Карно (КК) можно рассматриватькак развертки геометрических кубов наплоскости. Карта Карно, предназначеннаядля задания и минимизации функций n переменных, имеет 2n клеток. Каждая клетка соответствуетнабору переменных. В тех клетках, которыесоответствуют значениям функции, равным1, записываются единицы, а в остальных– нули (или вместо нулей оставляютсяпустые клетки).

Разметка карт.Разметкапредназначена для установления взаимнооднозначного соответствия между наборамиЛФ и клетками. Начнем с n= 2:

или

Соседние наборыразличаются только одной координатой

n = 3: n= 4 (даны два варианта возможной разметки):

Примерзаполнения карты и минимизациидля n = 3.

.ƒ(x1, x2,x3)

Исходная функция: f = (Са = 12, Сb= 16). Соседние клетки, заполненныеединицами, можно объединить в контур,используя 2к соседних клеток.Каждому контуру будет соответствоватьконъюнктивный терм ДНФ. Результатминимизации: f = (Са = 7, Сb= 10).

Правила минимизации

1. Две соседние единичные клетки исходной карты (два 0-куба) образуют 1-куб. Клетки на границах также являются соседними. При этом независимая координата, обозначавшаяся ранее символом “X”, при аналитической записи исчезает из терма.

2. Четыре соседние единичные клетки могут объединяться в контур, образуя
   2-куб, при этом исчезают две переменные. Каждая клетка в объединении имеет две соседние клетки.

3. Восемь соседних единичных клеток могут объединяться в контур, образуя
   3-куб. Каждая клетка в объединении имеет три соседние клетки.

4. Шестнадцать соседних единичных клеток могут объединяться в контур, образуя 4-куб, и т. д.

5. Каждому контуру, включающему 2к клеток, в аналитической записи соответствует конъюнктивный терм минимизированной ДНФ, содержащий n – k переменных; отрицания над переменными расставляются согласно разметке карты; полученные термы в формуле соединяются знаком “”.

Объединение клеток отражает фактсклеивания соответствующих термов прианалитической записи.

Цель использованиякарт Карно для получения минимальнойДНФ состоит в следующем: покрыть всеединицы карты как можно меньшим числомкак можно более крупных контуров.

Вобщем случае возможны разные вариантыпокрытия; не самое удачное покрытиеимеет следствием получение правильной,но не оптимальной (по цене покрытия)формулы.

Приведем пример оптимального покрытиякарты при n = 4:

МДНФ включаеттри терма, один из которых содержит двепеременные, а два остальных – по три переменных.

ПолучениеМКНФ

Получение МКНФ по карте Карно можетосновываться на предварительномполучении МДНФ для инверсной функции;взятие еще одного отрицания с применениемправил де Моргана приведет к записиКНФ: .

Получение МКНФ непосредственнопо карте

Используем карту с проставленныминулями, находим контуры и, подразумеваяинверсную разметку карты, сразу записываемМКНФ.

Инверсную разметку можно непосредственнонанести на карту:

f = (х1 х2х3)(х1х3) (х2х3) – МКНФ.

Карты Карно для n> 4

Карты Карно для n >4 менее наглядны и требуют большеговнимания при поиске контуров. Клетки,зеркально отраженные относительноцентральных осей, также являютсясоседними. Ниже показаны карты и ихразметка для n = 5 и n = 6. Клетки, отмеченныесимволом “*”, – соседние и могутвключаться в общий контур.

n =5: n= 6:

Разметка карт может осуществлятьсяпо-разному: допустимы переименованияпеременных и инверсная разметка. Однаков любом случае для любой переменной иее отрицания отводятся по половинекарты.

2.3. Теорема Шеннона о разложениилогической функции

Любую ЛФ от n переменныхможно первоначально представить в виде:

. (3)

Для доказательства достаточно положитьпоочередно в равенстве (3) значение x1 равным 1 и 0.

(4)

Всего в правой части (4) может быть 2n слагаемых. В более краткой записивыражение (4) имеет вид:

, (5)

где li– элемент множества{0, 1} , приэтом .

Удалив из (5) слагаемые, на которых f принимает значение “0”,получим СДНФ:

. (6)

В (6) суммирование ведется только понаборам, на которых f= 1.

Аналогично, из принципа двойственностиполучим СКНФ:

(7)

В (7) в произведение включаются тольконаборы, на которых f= 0.

Доказательство существования совершенныхформ (6) и (7) и составляет содержаниетеоремы Шеннона.

Источник: https://works.doklad.ru/view/b7xicMHgYxE/3.html

Карта Карно

Введение
• 1 Принципы минимизации
• 2 Описание
• 3 Примеры
  • 3.1 Пример 1
  • 3.2 Пример Карты Карно на пять переменных
  • 3.3 Пример большой Карты Карно на восемь переменных

Рис. 1 Пример Карты Карно

Карта Карно́ — графический способ минимизации переключательных (булевых) функций, обеспечивающий относительную простоту работы с большими выражениями и устранение потенциальных гонок.

Представляет собой операции попарного неполного склеивания и элементарного поглощения. Карты Карно рассматриваются как перестроенная соответствующим образом таблица истинности функции.

Карты Карно можно рассматривать как определенную плоскую развертку n-мерного булева куба.

Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы.

В карту Карно булевы переменные передаются из таблицы истинности и упорядочиваются с помощью кода Грея, в котором каждое следующее число отличается от предыдущего только одним разрядом.

1. Принципы минимизации

Основным методом минимизации логических функций, представленных в виде СДНФ или СКНФ, является операция попарного неполного склеивания и элементарного поглощения.

Операция попарного склеивания осуществляется между двумя термами (членами), содержащими одинаковые переменные, вхождения которых (прямые и инверсные) совпадают для всех переменных, кроме одной.

В этом случае все переменные, кроме одной, можно вынести за скобки, а оставшиеся в скобках прямое и инверсное вхождение одной переменной подвергнуть склейке. Например:

Аналогично для КНФ:

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

Как известно, булевы функции N переменных, представленные в виде СДНФ или СКНФ, могут иметь в своём составе 2N различных термов. Все эти члены составляют некоторую структуру, топологически эквивалентную N–мерному кубу, причём любые два терма, соединённые ребром, пригодны для склейки и поглощения.

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

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

Как видно из рисунка, для трёхмерного случая возможны более сложные конфигурации термов. Например, четыре терма, принадлежащие одной грани куба, объединяются в один терм с поглощением двух переменных:

В общем случае можно сказать, что 2K термов, принадлежащие одной K–мерной грани гиперкуба, склеиваются в один терм, при этом поглощаются K переменных.

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

Таким образом появляется возможность представлять булевы функции с числом переменных больше двух в виде плоской таблицы.

Аналогичным образом можно работать с функциями четырёх, пяти и более переменных. Примеры таблиц для N=4 и N=5 приведены на рисунке.

Для этих таблиц следует помнить, что соседними являются клетки, находящиеся в соответственных клетках крайних столбцов и соответственных клетках верхней и нижней строки.

Для таблиц 5 и более переменных нужно учитывать также, что квадраты 4х4 виртуально находятся друг над другом в третьем измерении, поэтому соответственные клетки двух соседних квадратов 4х4 являются сосоедними, и соответствующие им термы можно склеивать.

2. Описание

Карта Карно может быть составлена для любого количества переменных, однако удобно работать при количестве переменных не более пяти. По сути Карта Карно — это таблица истинности составленная в 2-х мерном виде.

Благодаря использованию кода Грея в ней верхняя строка является соседней с нижней, а правый столбец соседний с левым, т.о. вся Карта Карно сворачивается в фигуру тор (бублик). На пересечении строки и столбца проставляется соответствующее значение из таблицы истинности.

После того как Карта заполнена, можно приступать к минимизации.

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

1. объединяем смежных клеток, содержащих единицы, в область так, чтобы одна область содержала 2n (n целое число = 0…) клеток(помним про то, что крайние строки и столбцы являются соседними между собой), в области не должно находиться клеток, содержащих нули;
2. область должна располагаться симметрично оси(ей) (оси располагаются через каждые четыре клетки);
3. не смежные области, расположенные симметрично оси(ей), могут объединяться в одну;
4. область должна быть как можно больше, а количество областей как можно меньше;
5. области могут пересекаться;
6. возможно несколько вариантов накрытия.

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

Для КНФ всё то же самое, только рассматриваем клетки с нулями, не меняющиеся переменные в пределах одной области объединяем в дизъюнкции (инверсии проставляем над единичными переменными), а дизъюнкции областей объединяем в конъюнкцию. На этом минимизация считается законченной. Так для Карты Карно на рис.1 выражение в формате ДНФ будет иметь вид: В формате КНФ:

Так же из ДНФ в КНФ и обратно можно перейти использовав Законы де Моргана.

3.1. Пример 1

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

Для краткости обозначим родственников Коли через буквы:мама — х1папа — х2дедушка — х3бабушка — х4Условимся обозначать согласие родственников единицей, не согласие нулём.

Возможность пойти погулять обозначим буквой f, Коля идёт гулять — f = 1, Коля гулять не идёт — f = 0.Составим таблицу истинности:

Перерисуем таблицу истинности в 2-х мерный вид:
Переставим в ней строки и столбцы в соответствии с кодом Грея. Получили Карту Карно:

Заполним её значениями из таблицы истинности:
Минимизируем в соответствии с правилами:

1. 1. Все области содержат 2n клеток;
2. 2. Так как Карта Карно на четыре переменные оси располагаются на границах Карты и их не видно (подробнее смотри пример Карты на 5 переменных);
3. 3. Так как Карта Карно на четыре переменные все области симметрично осей — смежные между собой (подробнее смотри пример Карты на 5 переменных);
4. 4. Области S3, S4, S5, S6 максимально большие;
5. 5. Все области пересекаются (не обязательное условие);
6. 6. В данном случае рациональный вариант только один.

Теперь по полученной минимальной ДНФ можно построить логическую схему:

Из за отсутствия в наличии шести-входового элемента ИЛИ, реализующего функцию дизъюнкции, пришлось каскадировать пяти- и двух-входовые элементы(D7, D8). Составим мин. КНФ:

3.2. Пример Карты Карно на пять переменных

Имеем такую таблицу истинности:

Карта Карно будет выглядеть следующим образом (для лучшего визуального восприятия в Карту нули не записываем):
Неправильно (на примере ДНФ):

• — Область S1 — накрыта правильно;
• — Область S2 — нарушает п.1;
• — Область S3 — нарушает п.2;
• -Области S4 и S6 — не выполняют п.3, это не является ошибкой — выражение получится больше чем если бы S4 и S6 представляли собой одну область;
• — Область S5 — нарушает п.1 по кол-ву клеток и по недопустимости нахождения нулей в области.

Правильно, но не оптимально:

Эта карта Карно минимизирована неоптимально, так как можно объединить единицы, входящие в члены S3 и S5.

Минимизировав эту Карту получаем следующую ДНФ:

Оптимально:

Составим минимальную КНФ:

Другой вариант той же самой Карты Карно:

Ничего не меняется только в строках записано три переменных, а в столбцах две.

3.3. Пример большой Карты Карно на восемь переменных

Предположим, по имеющейся таблице истинности составлена такая Карта Карно:
Найдём минимальную ДНФ:

Минимальная КНФ:
скачать
Данный реферат составлен на основе статьи из русской Википедии. Синхронизация выполнена 18.07.11 16:15:08
Похожие рефераты: Карно, Карно Лазар, Лазар Карно, Карно-йоки, Карно Фред, Фред Карно, Теоремы Карно, Цикл Карно, Карно (город).

Категории: Логика, Булева алгебра.

Текст доступен по лицензии Creative Commons Attribution-ShareA.

Источник: http://wreferat.baza-referat.ru/%D0%9A%D0%B0%D1%80%D1%82%D0%B0%20%D0%9A%D0%B0%D1%80%D0%BD%D0%BE

Презентация на тему: МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОД МИНИМИЗИРУЮЩИХ КАРТ: КАРТЫ КАРНО ЛЕКЦИЯ 16

1МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОД МИНИМИЗИРУЮЩИХ КАРТ: КАРТЫ КАРНО ЛЕКЦИЯ 16 В.И. ХАХАНОВФакультет компьютерной инженерии и управления, кафедра АПВТ, ХНУРЭДИСКРЕТНАЯ МАТЕМАТИКАБУЛЕВА АЛГЕБРА

2

Слайд 2: Цель лекции – изучить метод карт Карно для минимизации булевых функций, описывающих комбинационные подсхемы цифровых проектов

2Цель лекции – изучить метод карт Карно для минимизации булевых функций, описывающих комбинационные подсхемы цифровых проектовКарты Карно двух, трех, четырех переменныхСвойства карт КарноУпрощенный стандарт карт КарноР-подкубы. ПокрытияПравила минимизацииВыводыТема: Минимизация булевых функций. Метод карт Карно

3

Слайд 3

3ЛитератураСавельев А.Я. Прикладная теория цифровых автоматов. М.: Высш. шк., 1987. 222-240 с.Хаханов В. І., Хаханова І.В., Кулак Е.М., Чумаченко С.В. Методичні вказівки до практичних занять з курсу “Дискретна математика”. Харків, ХНУРЕ. 2001. С.35-43.Дискретная математика: Гипертекстов ые учебные материалы (электронный учебник) / В.И.

Хаханов, С.В. Чумаченко. 2004. http/…/10.13.20.100/nserv/library/education/Чумаченко/Дискретная математика/Дистанционный_учебник/index.htm.Арифметические и логические основы цифровых автоматов. Гипертекстовые учебные материалы (электрон. учебник) / А.С. Шкиль. 2004. http/…/10.13.20.100/nserv/library/education/Шкиль/ ЛМ/Лк_лб/st_text/index.htm.

4

Слайд 4

4Базовые понятия:Булева переменнаяБулева функцияДвоичная система счисленияЧисловое представление ФАЛКубическое представление ФАЛСДНФ и СКНФЗаконы склеивания и поглощенияТерминыКлючевые слова:МинимизацияСоседние клеткир-подкубОдномерныйр-подкубДвумерныйр-подкубМинимальное покрытие

5

Слайд 5

5Представление ФАЛ на картах КарноКарта Карно является графическим способом представления булевых функций от нескольких переменныхТаблицы истинности функции от 2, 3, 4-х переменных могут быть перестроены в карты КарноПример: карта Карно для двух переменных№ набораx 1x 2f( x 1, x 2 )000101210311x 1 x 2013200 01 11 10

6

Слайд 6

6Карта Карно для трех переменныхx 2 x 300 01 11 1001324576x 101№х 1х 2х 3f(x 1,x 2,x 3 )00001001201030114100510161107111

7

Слайд 7

7Карта Карно для четырех переменныхx 3 x 400 01 11 10013245761213151489111000011110x 1 x 2№х 1х 2х 3х 4f(x 1,x 2,x 3, х 4 )00000100012001030011401005010160110701118100091001101010111011121100131101141110151111

8

Слайд 8

8Представление ФАЛ на картах КарноДля представления функции на карте достаточно в те клетки, где функция равна единице, поместить единицыСчитается, что в остальных клетках содержатся нулиПримерыx 2 x 300 01 11 101111x 101x 1 x 21100 01 11 10

9

Слайд 9

9Свойства карт КарноКарты организованы таким образом, что соседние по строке или по столбцу клетки отличаются значением только одной переменнойЕсли две комбинации значений переменных отличаются только по одной координате, то клетки являются соседнимиВ карте Карно двух переменных клетки на противоположных концах карты тоже являются соседнимиЭто свойство сохраняется для карт Карно трех и четырех переменных: противоположные концы каждой строки или столбца являются соседними

10

Слайд 10

10Упрощенный стандарт карт Карноx 1x 1x 2x 2x 3x 3x 4x 1x 2Для упрощения строки и столбцы, где переменная х i равна 1, обозначают фигурной скобкой. При этом значение ноль эта переменная имеет в неотмеченных местах

11

Слайд 11

11Примеры представления функций на картах Карно с использованием упрощенного стандартаx 1111111x 11111x 2x 2x 3x 3x 4x 1x 2

12

Слайд 12

12Р-подкубы. Покрытия 1Р- клетки – клетки с единицамиДве соседние единицы образуют одномерный р-подкубОдномерный р-подкуб соответствует произведению, в котором всегда отсутствует один первичный термПеременная, отсутствующая в произведении, определяется по карте – она имеет различные значения для двух единиц соответствующего подкубаx 111x 211x 3x 4x 1x 2

13

Слайд 13

13Р-подкубы. Покрытия 2Четыре соседние единицы образуют двумерный р-подкубДвумерный р-подкуб соответствует произведению без двух первичных термовОпущены те переменные, которые не сохраняют постоянное значение на этом подкубе1111x 3x 4x 1x 21111x 3x 4x 1x 2

14

Слайд 14

1411111111x 3x 4x 1x 211111111x 3x 4x 1x 2Трехмерные р-подкубы содержат по 8 единицОдномерный р-подкуб соответствует ребру, имеющему две соседние вершиныДвумерный р-подкуб соответствует двумерному подкубу n -мерного кубаЧтобы представить функцию, следует покрыть все единицы карты р-подкубамиР-подкубы. Покрытия 3

15

Слайд 15

15Представления функций р-подкубами11111111x 3x 4x 1x 21111111x 3x 1x 2x 4

16

Слайд 17

17Правила минимизацииДве соседние клетки образуют 1-кубНесущественная координата для двух кубов обозначается символами X : 101  111=1Õ1Четыре клетки объединяются, образуя 2-куб :100  101  110  111=1ÕÕВ общем случае могут объединяться соседние клетки, число которых равно 2 k, где k =1,2,3… (2,4,8,16,32,…) с образованием k -кубов

18

Слайд 18

18Примеры минимизации по картам Карно 11111x 3x 4x 1x 21111x 3x 4x 1x 2

19

Слайд 19

19Примеры минимизации по картам Карно 21111x 3x 4x 1x 2Склеивание соседних ячеек дает:3 и 7 5 и 7 8 Итак, результирующая ДНФ имеет вид:

20

Слайд 20

20Примеры минимизации по картам Карно 311111111x 3x 4x 1x 2Не всегда выбранное покрытие оказывается минимальным. Например: требуется получить минимальную ДНФ для функции Y=1 на наборах {0,1,2,5,6,11,13,15}11111111x 3x 4x 1x 2Все возможные попарные склеивания НЕ дадут минимальную форму функции!

21

Слайд 21: Выводы

21ВыводыКарты Карно есть технологичная форма представления таблицы истинности для минимизации булевых функций от небольшого числа переменныхНа практике используются для минимизации аппаратурных затрат, реализующих функции возбуждения триггеров при синтезе цифровых автоматовИспользуются при анализе рисков сбоев, гонок и состязаний, возникающих в цифровых устройствах, соответствующих функциям, которые представлены картами Карно

22

Последний слайд презентации: МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ. МЕТОД МИНИМИЗИРУЮЩИХ КАРТ: КАРТЫ КАРНО ЛЕКЦИЯ 16: Тест-вопросы

22Тест-вопросыx 11111111x 11111111x 2x 2x 3x 3x 4x 1x 2Обозначить на картах Карно минимизирующие контурыУказать результаты склеиванияx 1111x 2АБВГ

Источник: https://slide-share.ru/minimizaciya-bulevikh-funkcij-metod-minimiziruyushchikh-kart-karti-karno-lekciya-16-132077

Минимизация ФАЛ с помощью карт Карно

Для задания ФАЛ в карте Карно надо проставить 1 в тех клетках, которые соответствуют разрешенным наборам. В карте на рис. 10 задана ФАЛ из табл. 5.

Рис. 10. Карта Карно

Минимизация ФАЛ по карте Карно заключается в объединении соседних клеток в прямоугольные контуры, причем соседними считаются и клетки, разделенные внешней границей карты.

Минимизация производится по следующим правилам.

Все единицы должны быть включены в прямоугольные контуры.

Во всех клетках контура должны стоять единицы.

Число клеток в контуре должно быть кратным степени числа 2: 1, 2, 4, 8, … .

Контуры могут накладываться друг на друга.

Контуры, все клетки которых уже вошли в другие контуры, являются лишними.

Для получения наиболее простой формулы надо выбирать контуры с максимальным числом клеток.

Каждому контуру соответствует конъюнкция, составленная из переменных, значения которых не изменяются во всех клетках контура.

Конъюнкции контуров объединяются знаками дизъюнкции.

Ниже представлена ФАЛ, соответствующая карте Карно на рис. 10:

Минимизируем функцию, представленную своими разрешёнными наборами, с использованием карт Карно (рис. 11):

.

Рис. 11. Минимизация по карте Карно

В итоге мы получаем следующую функцию:

ДСНФ и КСНФ

ДСНФ исходной функции:

КСНФ исходной функции:

Построение схемы в базисе {И, ИЛИ, НЕ}

Схема, реализующая функцию в базисе {И, ИЛИ, НЕ}, представлена на рис. 14.

Рис. 14. Реализация функции в базисе {И, ИЛИ, НЕ}

Построение схемы в базисе Шеффера {И-НЕ}

Схема, реализующая функцию в базисе Шеффера, представлена на рис. 15. Пунктиром показана возможность исключения двух элементов по закону двойного отрицания (12).

Рис. 15. Реализация функции в базисе Шеффера

Построение схемы в базисе Вебба {ИЛИ-НЕ}

Схема, реализующая функцию в базисе Вебба, представлена на рис. 16. Пунктиром показана возможность исключения двух элементов по закону двойного отрицания (12).

Рис. 16. Реализация функции в базисе Вебба

Запись исходной формулы в базисе И, НЕ

Воспользовавшись законами алгебры логики (подразд. 2.2), преобразуем исходную функцию к виду, содержащему только функции И, НЕ:

Запись исходной формулы в базисе ИЛИ, НЕ

Воспользовавшись законами алгебры логики (подразд. 2.2), преобразуем исходную функцию к виду, содержащему только функции ИЛИ, НЕ:

Page 3

При подготовке к выполнению задания рекомендуется использовать учебник Сапожникова Вл. В., Сапожникова В. В., Кравцова Ю. А. «Теория дискретных устройств железнодорожной автоматики, телемеханики и связи» (М. : УМК МПС России, 2001).

Источник: https://studwood.ru/2505775/logika/minimizatsiya_pomoschyu_kart_karno