12802

ИЗУЧЕНИЕ СЛОЖНЫХ ЛОГИЧЕСКИХ ВЫСКАЗЫВАНИЙ

Лабораторная работа

Информатика, кибернетика и программирование

Лабораторная работа № 3 ИЗУЧЕНИЕ СЛОЖНЫХ ЛОГИЧЕСКИХ ВЫСКАЗЫВАНИЙ Цель работы: Изучить основы алгебры логики и составления сложных логических выражений. Краткие теоретические сведения Как и фундаментальные операции И ИЛИ и НЕ более сложные функции также мо...

Русский

2013-05-03

409.5 KB

5 чел.

Лабораторная работа № 3

«ИЗУЧЕНИЕ СЛОЖНЫХ ЛОГИЧЕСКИХ ВЫСКАЗЫВАНИЙ»

Цель работы: Изучить основы алгебры логики и составления сложных логических выражений.

Краткие теоретические сведения

Как и фундаментальные операции И, ИЛИ и НЕ, более сложные функции также можно представить с помощью таблиц истинности.

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

Так, например, для функции  – это таблица 1.

Таблица 1 – Таблица истинности функции

А

В

С

АВ+С

0

0

0

0

0

0

1

1

0

1

0

0

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

1

1

1

1

1

Можно видеть, что  принимает значение 1 в пяти случаях (в таблице выделено жирным шрифтом). Следовательно, функция  может быть записана как

,

где каждый член соответствует одной из записей таблицы истинности. Если в результате вычисления член оказывается равным 1, то и все выражение примет значение 1.

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

Карта Карно состоит из двухмерного массива клеток. Каждая клетка соответствует одному минтерму. Минтермы соседних клеток – все равно, по горизонтали или по вертикали – содержат одинаковые переменные. Только в одном минтерме переменная стоит в прямой форме, а в другом – в инверсной. Клетка обозначается 1 для тех минтермов, которые присутствуют в минимизируемой функции. Минимизация производиться объединением прилежащих клеток, отмеченных 1, в группу, содержащую общий член-произведение, при этом исключается переменная, которая присутствовала в минтермах в разных формах (согласно тождеству , где  – член в виде произведения переменных, а  – переменная, общая для нескольких заданных членов выражения). Причем, если два минтерма в результате объединения дают более простое произведение, то это вовсе не означает, что группа не может быть затем объединена с соседними группами того же размера.

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

Рисунок 1 – Карта Карно для трех переменных

Так как соседние клетки карты отличаются только одной переменной, то по верхнему краю карты нумерация будет следующей: 00, 01, 11, 10 (эта последовательность по существу представляет собой так называемый код Грэя). Обозначения карты по вертикали строятся таким же образом. В данном случае вертикаль обозначается только одной цифрой, соответствующей третьей переменной функции. Таким образом, каждая клетка идентифицируется в соответствии с обозначениями по вертикали и горизонтали. Верхняя левая клетка, например, будет обозначаться как 000, что соответствует минтерму .

Примечание 1. Код Грэя может содержать любое число разрядов. Существует простое правило для формирования состояний кода Грэя: начинать надо из нулевого состояния, а потом для получения каждого следующего выбрать самый младший разряд, изменение которого приводит к образованию нового состояния, и взять его инверсное значение.

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

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

При этом следует руководствоваться рядом правил:

  1.  Все единицы (при записи функции в дизъюнктивной форме) и все нули (при записи в конъюнктивной форме) должны быть замкнутыми в прямоугольные контуры. Единичные контуры могут объединять несколько единиц, но не должны содержать внутри себя нулей. Нулевые контуры могут объединять несколько нулей, но не должны содержать внутри себя единиц. Одноименные контуры могут накладываться один на другой, т.е. одна и та же единица (или ноль) может входить в несколько единичных (нулевых) контуров.
  2.  Площадь любого контура должна быть симметричной относительно границ переменных, пересеченных данным контуром. Другими словами, число клеток в контуре равняется , где  – 0, 1, 2, 3, 4, …, т.е. число клеток выражается числами 1, 2, 4, 8, 16,…
  3.  Во избежание получения лишних контуров их построение следует начинать из тех единиц или нулей, которые могут войти в один контур. Лишними называются контуры, все клетки которых вошли уже в другие контуры.
  4.  В контуры можно объединять только соседние клетки, которые содержат единицы или нули. Соблюдение этого правила в особенности необходимо проверять при числе переменных, большем четырех, когда соседние клетки могут быть расположены не рядом, и потому контуры могут испытывать видимый разрыв.
  5.  Каждой единичной клетке отвечает конъюнкция входных переменных, которые определяют данную клетку. Каждой нулевой клетке отвечает дизъюнкция инверсий входных переменных, что определяют данную клетку.
  6.  В контуре, который объединяет две клетки, одна из переменных изменяет свое значение, поэтому выражение контура из двух клеток не зависти от этой переменной, а представляется всеми другими переменными. Это правило относится и к контурам, которые охватывают число клеток более двух, и имеет такую формулировку: выражения, которые отвечают контурам, не содержат тех переменных, чьи границы пересекаются площадью, ограниченной данным контуром.
  7.  Выражение логической функции может быть записано по соответствующей ей карте Карно в дизъюнктивной или конъюнктивной форме. Дизъюнктивная форма составляется в виде дизъюнкции конъюнкций, которые отвечают единичным контурам, выделенным на карте для определения функции; конъюнктивная – в виде конъюнкции дизъюнкций, которые отвечают нулевым контурам.
  8.  Для контуров, которые охватывают разное количество клеток, получаются выражения разной сложности. Поэтому для данной логической функции можно записать по ее карте Карно несколько алгебраических выражений, которые отличаются по сложности. Наиболее сложное выражение отвечает случаю, когда каждой клетке отвечает свой контур. Это выражение представляет собой СДНФ или СКНФ.
  9.  Для получения по карте Карно минимального выражения логической функции следует руководствоваться.

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

Предположим, нужно минимизировать заданную функцию

.

Карта Карно этой функции изображена на рисунке 2.

Рисунок 2 – Представление функции  с помощью карты Карно для трех переменных

В выражении пять членов, поэтому на карте пять клеток с вписанными единицами. Две из них прилегают друг к другу, следовательно, эти два члена можно сгруппировать (см. рисунок 3).

Рисунок 3 – Карта Карно функции  с объединением двух членов

Группируясь,  и  дают просто , а  и  – . Еще одна клетка карты с  не соседствует ни с какой другой клеткой с  и не может быть объединена в группу. Группы показаны на рисунке линиями, обведенными вокруг соответствующих клеток. Переменную, которую можно убрать, легко определить, глядя на обозначения клеток. В одной клетке группы такой переменной соответствует , а в соседней – . Итак, минимизированное выражение имеет вид:

.

Если в двух полученных уже сокращенных членах снова будет отличаться только одна переменная, то их можно объединить еще раз и сократить вторую переменную. Однако это проще сделать сразу при использовании карт Карно, формируя как можно большие группы таким же образом, как это делалось в случае двух прилежащих клеток. Если группа из двух клеток позволяет сократить одну переменную, то в случае группы их четырех клеток можно убрать две переменные, а из восьми – три. Так, например, для функции  карта Карно в этом случае будет выглядеть следующим образом (см. рисунок 4).

Рисунок 4 – Карта Карно функции  с объединением большой группы

В этом случае  минимизированное выражение имеет вид:

Описание лабораторной установки

Лабораторная установка представляет собой учебный стенд для изучения работы логических элементов. На лицевой панели установки нанесены изображения основных логических элементов.

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

В левой части лицевой панели находятся 5 переключателей, по 4 гнезда в каждом. Они предназначены для подачи высокого или низкого уровня на входы микросхем.

ВНИМАНИЕ! Если необходимо подать на какой-либо вход микросхемы низкий уровень, то обязательно подайте на него низкий уровень от какого-либо переключателя. Если вход останется не присоединенным к низкому уровню, то (по умолчанию) будет считаться, что на нем находиться высокий уровень. Схема будет работать некорректно, что приведет к ложному результату.

В левом верхнем углу лицевой панели данной лабораторной установки имеется кнопка для кратковременной проверки собранной вами схемы.

Для включения лабораторной установки используется тумблер «Сеть».

Порядок выполнения работы

  1.  Ознакомиться с методическими указаниями к лабораторной работе.
  2.  В соответствии с заданием преподавателя составить карту Карно для функции .
  3.  По полученной карте Карно составить и минимизировать логическое выражение, описывающее функцию .
  4.  Разработать схему, реализующую полученную функцию .
  5.  Собрать разработанную схему на лабораторном стенде.
  6.  Составить отчет по данной лабораторной работе.

Содержание отчета

Отчет должен включать:

  1.  Задание на разработку схемы.
  2.  Карту Карно заданной функции.
  3.  Минимизацию логического выражения, описывающего заданную функцию.
  4.  Схему, реализующую минимизированное логическое выражение.
  5.  Краткое описание работы схемы.
  6.  Вывод.

Контрольные вопросы и задания

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


 

А также другие работы, которые могут Вас заинтересовать

26472. Анатомическая терминология. Плоскости и направления, принятые в анатомии 28.5 KB
  латеральное направление наружу медиальное направление вовнутрь Сегментальная поперечная вертикальная проходящая поперёк тела и делящая его на переднюю и заднюю половины. краниальное направление к голове cranium череп каудальное направление к хвосту cauda хвост Фронтальная горизонтальная делит тело на верхнюю и нижнюю половины. дорсальное направление вверх dorsum спина вентральное направление вниз ventor живот На голове: дорсальное направление...
26473. Биоморфологические закономерности строения и развития организмов 27 KB
  Биоморфологические закономерности строения и развития организмов Организм целостная живая система для которого прежде всего характерны целостность и дискретность. Общие принципы строения тела животного: биполярность билатеральность сегментарность закон трубкообразного строения большинство непарных органов расположены вдоль главной оси тела Основные законы биологического развития: Закон исторического филогенетического развития Шмальгаузен: в процессе развития постоянно происходит дифференцировка разделение функций клеток и тканей...
26474. Железы кожного покрова 45 KB
  На коже вымени: между бёдрами молочное зеркало planum lactiferum или надвыменная область regio supramammaria Под кожей поверхностная фасция вымени беловатая пластинка из плотн. ткани соединительнотканная собственная оболочка долей вымени соединённая прослойками ткани внутри долей вымени стромой stroma gl. mammaria между правой и левой половинами подвешивающая связка вымени lig. suspensorium mammarium на месте связки снизу вымени серединный жёлоб sulcus intermammarius.
26475. Классификация костей 23.5 KB
  Классификация костей Оs longum длинные дугообразные рёбра трубчатые плечевая бедренная общий план строения: биэпифизарные дистальный эпифиз проксимальный эпифиз между эпифизами тело кости диафиз. Зона роста кости в длину проксимальный и дистальный метафиз между эпифизом и диафизом. Os longum короткие равны по длине высоте ширине состоят из компактного и губчатого вещества кости запястья и заплюсны основная функция амортизация Os planum плоские или пластинчатые Имеют обширные...
26476. Кость как орган и её остеогенез 33.5 KB
  соли в кости меняется: Молодость: 1:1 Зрелость: 1:2 Старость: 1:7 кости твёрдые хрупкие С поверхности кость покрыта надкостницей periosteum: Наружный фиброзный слой защитная функция из плотной соединительной ткани содержит много коллагеновых волокон. продольно по отношению к главной оси кости. Костные перегородки остеоны расположены плотно что придаёт кости прочность сравнимую с прочностью гранита. Особо толстый слй компакты там где велики нагрузки кости на излом.
26477. Морфофункциональная характеристика волоса 35.5 KB
  Морфофункциональная характеристика волоса Волосы pili производные эпидермиса тонкие эластичные ороговевающие нити из ороговевшего или ороговевающего эпителия. волосы покрывают почти всё тело Фции: защита терморегуляторная орган осязания Волос состоит из: волосяная нить: стержень scapus pili видимая часть корень radix pili находится в толще кожного покрова корень переходит в луковицу волоса. волосяная сумка чехол в сумку открываются протоки сальных желёз Утолщение корня...
26478. Морфофункциональная характеристика кожного покрова 36.5 KB
  3 составляющих: кожа cutis слизистая оболочка tunica mycosa выстилает изнутри органы пищеварения дыхания размножения мочевыделения производные кожного покрова: железы потовые сальные молочные волосы перья чешуя мякиши роговые образования рога копыта когти СUTIS: epidermis располагается с поверхности представлен многослойным плоским ороговевающим эпителием dermis собственно кожа дерма соединительная ткань subcutis подкожный слой соединительная ткань epidermis 2060мкм эктодермальное происхождение...
26479. Морфофункциональная характеристика мякиша 32 KB
  Морфофункциональная характеристика мякиша МЯКИШИ torus упругие утолщения кожного покрова которые служат для опоры конечности о землю и обеспечивает амортизацию обладают большой чувствительностью осязание имеют хорошо развитый подкожный слой липоциты эласт. волокна располагаются на автоподиях Лошадь запястье пальмарно заплюсна плантарно каштаны пясть плюсна шоры пальцевый мякиш стрелка внутри копыта Собака на грудной запястные пястные пальцевые на тазовой плюсневые пальцевые Свинья КРС...
26480. СПЛАНХНОЛОГИЯ 24.5 KB
  Внутренние органы оъединяют в 3 аппарата: пищеварительный: система органов пищеварения пищеварительный канал пищеварительные железы вспомогательный аппарат жевательные мышцы челюсти зубы мышцы брюшного пресса и т. дыхательный: система органов дыхания дыхательные пути носовая полость глотка гортань трахея органы дыхания лёгкие вспомогательный аппарат органы дыхыхательной распираторики грудная клетка диафрагма мышцы брюшного пресса мочеполовой: почки мочевыводящие...