|
|
Зависимости между логическими операциями ⇐ ПредыдущаяСтр 4 из 4 Операции не являются независимыми; одни из них могут быть выражены через другие. СМожно доказать с помощью таблиц истинности можно доказать следующие равносильности: 1. A®B= Ā ØAÚB 2. A«B=(A®B)Ù(B®A)=(Ā ØAÚB)Ù(AÚØB)=(AÙB)Ú(Ā ØAÙØB) 3. ØØA=A закон двойного отрицания. 4. AÙB=BÙA коммутативный закон для конъюнкции 5. AÚB=BÚA коммутативный закон для дизъюнкции 6. (AÙB)ÙC=AÙ(BÙC) ассоциативный закон для конъюнкции 7. (AÚB)ÚC=AÚ(BÚC) ассоциативный закон для дизъюнкции 8. AÙ(BÚC)=(AÙB)Ú(AÙC) дистрибутивные законы 9. AÚ (BÙC)=(AÚB)Ù(AÚC) 10. AÙA=A закон идемпотенции для конъюнкции 11. AÚA=A закон идемпотенции. для дизъюнкции 12. Ø(AÙB)=ØAÚØB законы де Моргана 13. Ø(AÚB)=ØAÙØB 14. AÙ1=A закон единицы для конъюнкции 15. AÙ0=0 закон нуля для конъюнкции 16. AÚ1=1 закон единицы для дизъюнкции 17. AÚ0=A закон нуля для дизъюнкции 18. AÚ(AÙA)=A законы поглощения 19. AÙ(AÚA)=A 20. AÚØA=1 закон исключения третьего 21. AÙØA=0 закон противоречия 22. AÙ(ØAÚB)=AÙB 23. AÚ(ØAÙB)=AÚB Глупости Одну и ту же зависимость между логическими переменными можно выразить различными формулами. Поэтому важно иметь возможность приводить формулы к некоторому стандартному виду. Существует несколько стандартных форм, к которым приводятся логические выражения с помощью эквивалентных преобразований (формулы 1-23). Первая из них – дизъюнктивная нормальная форма (ДНФ), имеет вид A1ÚA2Ú…ÚAn, где каждое из составляющих есть конъюнкция простых высказываний и их отрицаний, например B=(ØA1ÙA2ÙA3)Ú(A4ÙA5) Вторая – конъюнктивная нормальная форма (КНФ), имеет вид A1ÙA2Ù…ÙAn, где каждое из составляющих есть дизъюнкция простых высказываний и их отрицаний, например B=(ØA1ÚA2ÚØA3)Ù(A4ÙA5)ÙA6
Табличное и алгебраическое задание булевских функций Задать булевскую функцию можно, в виде аналитического выражения или определяя ее значения для всех возможных наборов значений аргументов. Каждый аргумент может иметь два значения 0 и 1, следовательно, n аргументов могут принимать 2n различных наборов. Пусть, например булевская функция имеет три аргумента X1,X2,X3. Общее число наборов 23=8, зададим таблицу истинности функции, указав для каждого набора аргументов значение функции (в нашем случае зададим произвольное F).
Для составления аналитической (алгебраической) формы F по результатам таблицы сделаем следующее: -. вВ комбинациях, где функция F =принимает значение 1, единицу в аргументе заменим именем функции, а нуль именем с отрицанием, (т.е. комбинации аргументов 0 0 1 поставим в соответствие выражение -, все элементы (конституенты единицы) соединим знаками дизъюнкции., Ддля рассматриваемого примера, получим F(X1,X2,X3) = (ØX1ÙØX2ÙX3)Ú(ØX1ÙX2ÙX3)Ú(X1ÙØX2ÙX3) Ú(X1ÙX2ÙX3)
Как нетрудно заметитьпроверить, построенная функция (1) удовлетворяет всем строкам заданной таблицые истинности. Функция представляет дизъюнктивную нормальную форму. Кроме того, заметим, что в каждую группу дизъюнкций входят все аргументы функции. Такая ДНФ называется совершенной, а каждая группа дизъюнкций называется коституентой единицы. Аналогично, для комбинаций, где функция принимает значение нуля можно построить алгебраическую форму
F(X1,X2,X3) = (X1ÚX2ÚX3)Ù(X1ÚØX2ÚX3)Ù(ØX1ÚX2ÚX3) Ù(ØX1ÚØX2ÚX3) (2), кКоторая также удовлетворяет заданной таблице истинности и представляет собой конъюнктивную нормальную форму, в данном случае совершенную. Каждая конъюнкция называется конституентой нуля. Приведенный пример показывает, что любая булевская функция заданная таблично может быть представлена КНФ или ДНФ, и, обобщая, можно сказать, что вообще любая булевская функция представляется в КНФ или ДНФ.
В следующей главе будет показано, как основываясь на булевой алгебре, создаются цифровые устройства. 1.6.2. Элементы теории множеств Множеством называется любое объединение определенных вполне различимых объектов; их может и не быть вообще. Можно говорить о множестве точек на отрезке [0,1], множестве студентов в группе, множестве снежных дней в июле на экваторе, т.е. множество образуют любые объекты, объединенные по любому признаку. Объекты, составляющие множество, называются элементами множества. Множество, не имеющее ни одного элемента, называется пустым, оно обозначается Æ. Множество, состоящее из конечного числа элементов, называется конечным, в противном случае – бесконечным. Задать множество можно перечислением его элементов. Например, множество образованное из n элементов a1,a2,…,an, обозначается A={ a1,a2,…,an }; пишется aÎA (говорится «элемент a принадлежит множеству A»), если a является элементом множества А, в противном случае aÏA. Задать множество можно также, указав общее свойство для всех его и только его элементов. Например, множество точек равноудаленных от концов отрезка. Два множества считаются равными, если состоят из одних и тех же элементов; записывается этот факт A=B. Множество А1 называется подмножеством А (записывается А1ÌА), если все элементы множества А1 являются элементами А. Для множеств определены следующие операции: объединения, пересечения, дополнения. Объединением множеств А и В (записывается AÈB) называется множество состоящее из элементов как одного так и второго множества. Например, A и B – множества точек принадлежащих некоторым двум кругам, имеющим общие точки, тогда объединением AÈB будет фигура, состоящая из общих точек. Пересечением множеств А и В (записывается AÇB) называется множество, состоящее из элементов, принадлежащих как одному так и второму множеству одновременно. Дополнением множества А до В называется множество, состоящее из элементов множества В, не принадлежащих А. Дополнение обозначается Ā=В-А.
1.6.3. Элементы теории графов Основные понятия
u= (ei,ej)= (ej,ei), то ребро называется неориентированным или просто ребром, если же порядок имеет значение, то ребро u= (ei,ej) называется ориентированным ребром или дугой. Вершина ei - называется началом дуги, ej – конец дуги. Граф, содержащий хотя бы одну дугу, называется ориентированным графом или орграфом. Граф G(E,U) называется конечным, если множество E вершин конечно. Граф G(E,U), у которого любые две вершины соединены ребром, называется полным. Если хотя бы две вершины соединены несколькими ребрами, то такой граф называется мультиграфом. Две вершины ei,ejÎE называются смежными, если они соединены ребром. Число ребер, инцидентных данной вершине ei, называется локальной степенью этой вершины r(ei). Число ребер r графа G(E,U) определяется выражением
Рассмотрим граф, изображенный на рисунке 1.8.
Ориентированный граф рис. 1.8.
Множество вершин графа состоит из пяти элементов E={1,2,3,4,5}, а множество ребер U={(1,2),(1,4),(1,5),(2,3),(3,4),(5,3)}. Ребро (5,3) – является ориентированным ребром или дугой. Число ребер в графе определяется по значению локальных степеней для каждой вершины: r(1)=3; r(2)=2; r(3)=3; r(4)=2; r(5)=2; r=(3+2+3+2+2)/2=6 Важным в теории графов является понятие части графа G(E,U), который обозначается G¢(E¢,U¢)ÍG(E,U) Множества вершин и ребер части графа являются подмножествами вершин и ребер исходного графа E¢ÍE U¢ÍU Многие задачи на графах состоят в определении частей графа с заданными свойствами. Часть графа G¢(E¢,U¢)ÍG(E,U) называется подграфом графа G(E,U), если E¢ÍE, а подмножество U¢ÍU образовано только ребрами инцидентными вершинам множества E¢. Часть графа G¢(E¢,U¢)ÍG(E,U) называется суграфом графа G(E,U), если E¢ÍE, а подмножество U¢ÍU образовано ребрами инцидентными вершинам множества E¢. В графе, изображенном выше, можно выделить подграф G¢(E¢,U¢), где E¢={1,2,3}, множество ребер U¢={(1,2),(2,3)} и суграф G¢(E¢,U¢), у которого E¢={1,2}, U¢={(1,2),(1,4),(1,5),(2,3)}. Полным графом называется граф G(E,U), у которого каждая вершина eiÎE соединена ребрами с остальными вершинами. Например,
Рис. 1.9. Полный граф
Связанность графов Маршрутом графа G называется последовательность ребер S=(u1,u2,…un), в которой каждые два соседних ребра имеют общую вершину, т.е. u1=(e1,e2); u2=(e2,e3); …un=(en,en+1); Не исключено, что одно и то же ребро может встречаться несколько раз на одном маршруте. Две вершины ei и ej называются связанными, если существует маршрут из ei в ej. Компонентой связности графа называется подмножество его вершин с инцидентными им ребрами, такое, что любая вершина связана с любой другой вершиной маршрута. Например, из графа на рисунке 1.10. можно выделить следующие две компоненты связанности, показанные сплошной линией.
Рис 1.10. Компоненты связанности графа
Простой цепью или простым путем называется маршрут, в котором ни одно ребро не повторяется дважды. Элементарной цепью или элементарным путем называется маршрут, в котором ни одна вершина не повторяется дважды. Циклом в графе называется маршрут, у которого начальная вершина совпадает с конечной. Например, следующий граф имеет цикл S=(1,2,3,5,4,1). Рис.1.11.
Рис 1.11. Цикл в графе Цикл, проходящий по всем ребрам графа только один раз, называется Эйлеровым циклом. В теории графов доказывается теорема, определяющая, содержит ли граф эйлеров цикл. Оказывается, конечный граф содержит эйлеров цикл тогда и только тогда, когда он связан, и все его локальные степени вершин четные. Важной прикладной задачей теории графов является задача поиска в графе цикла, проходящего через каждую вершину только один раз. Такие циклы называются гамильтоновыми циклами. Весьма важным является связанный граф, не имеющий циклов, он называется деревом. В дереве любые две вершины связаны единственным путем. Вершина называется концевой, если ей инцидентно не более одного ребра; одна из концевых вершин может быть выбрана в качестве корня. Задание графа Граф может задаваться в виде рисунка, аналитически, в виде матрицы. Выше приводилось задание графа в виде рисунка. Аналитическое задание состоит в задании элементов множества вершин и E={e1,e2,…en} и множества ребер U={u1,u2,…um}. Для выполнения различного рода формальных преобразований над графами удобно использовать их матричные задания. Матрица A размерностью n´n, называется матрицей смежности графа G(E,U), если ее элементы образованы по правилу: элемент матрицы aij=m, если вершины ei и ej соединены m ребрами, и aij=0, если эти вершины не связаны ребрами. Матрица смежности имеет число строк и столбцов равное количеству вершин графа. Матрица A размерностью n´m, называется матрицей инциндентности графа G(E,U), если ее элементы образованы по правилу: элемент матрицы bij=1, если вершина ei инцидентна ребру uj, и bij=0 в противном случае. Так как каждое ребро инцидентно двум вершинам, то в каждой строке этой матрицы ровно два ненулевых элемента. Построим матрицы смежности и инцидентности для графа, изображенного на рисунке 1.12.
Рис 1.12. Матрицы смежности будет состоять из пяти строк и пяти столбцов.
Матрица инцидентности будет состоять из пяти строк и шести столбцов
Синтез цифровых схем. Задачей этого параграфа будет указание возможности обработки (преобразования) информации с помощью электронных устройств.
Z1= Z1(X1,X2,…Xn) Z2= Z2(X1,X2,…Xn) (1) … Zm=Zm(X1,X2,…Xn)
т.е. если существует двоичный код X1,X2,…Xn и каждому конкретному из 2n набору можно поставить в соответствие двоичный код Z1,Z2,…Zm всего 2m, то существует табличное или аналитическое представление для каждого значения Zi в зависимости от X1,X2,…Xn
где X1X2X3 – двоичные разряды первого слагаемого, Y1Y2Y3 – второго, Z1Z2Z3 – результата.
Z2=Z2(X2,Y2, X3,Y3) результат во 2-м зависит от двух предыдущих разрядов слагаемых Z1=Z1(X1,Y1, X2,Y2, X3,Y3) результат в 3-м зависит от всех предыдущих разрядов
Каждую из функций системы (1) можно представить в КНФ или ДНФ. Если создать электронные устройства: - способное моделировать двоичный сигнал в виде электрического тока; - конъюнкцию и дизъюнкцию сигналов, представленных в виде тока, то комбинируя эти устройства можно создать электронные схемы обрабатывающие информацию. Если же добавить еще устройство хранящее информацию, и в него записать данные и рецепты (алгоритмы) обработки этих данных, то станет возможна работа автомата по программе.
1.7.1. Устройства обработки данных. Как уже говорилось, легче строить электронные устройства с двумя устойчивыми состояниями, чем с 10, поэтому для построения цифровых устройств была выбрана двоичная система счисления. Следовательно, всякая информация, подлежащая обработке на цифровых электронных устройствах, должна быть представлена в двоичном коде. Моделировать двоичный сигнал в виде электрического тока можно подавая на некотором участке электрической цепи токовые импульсы разного напряжения рис 1.10. Например, логическую единицу связать с токовым импульсом, ноль с бестоковым, длительность импульсов задает тактовый генератор (ТГ). Очевидно, чем выше тактовая частота, тем быстрее работает устройство.
Обработка двоичных данных в виде электрических импульсов осуществляется электронными устройствами реализующими логические операции И, ИЛИ, НЕ. Схемы устройств не сложные, но мы их не приводим. На рис 1.11 показаны условные обозначения схем выполняющих логические операций и их временные диаграммы.
Такой функционально полной по отношению к КНФ и ДНФ системой элементов может быть реализована любая булева функция, в частности каждая из функций системы (2), а значит и любая обработка двоичных данных. ПРИМЕР. Рассмотрим синтез цифрового устройства, реализующего функцию
Устройство, реализующее данную функцию имеет, вид:
  
   
  
        
     
 
  
     
   
      В этой схеме имеются три входных сигнала. Элементы 1 и 2 обеспечивают отрицание (инверсию) сигналов X1,X2. соответствующие конъюнкции производят элементы 3,4,5,6 затем дизъюнкцию всех сигналов делает элемент 7, на выходе которого сигнал соответствует заданной булевской функции.
1.7.2. Построение элементов памяти цифровых устройств. Рассмотренные схемы работают при наличии входных сигналов, после их снятия исчезает сигнал на выходе, поэтому они могут быть полезны в различных схемах преобразующих двоичные данные, но не решают проблему временного хранения данных. Для хранения входных, промежуточных и выходных данных необходимы элементы, которые запоминали бы и сохраняли бы двоичный код после снятия напряжения с некоторых участков цепи, т.е. некоторый кратковременный импульс тока переводил бы элемент из одного устойчивого состояния в другое. Такие элементы называются элементами памяти.
1 и 2 называются входами 3 и 4 выходами. Вход 1 (S) предназначен для записи в триггер единичного значения переменной, вход 2 (R) записывает нулевое значение переменной или обнуляет триггер. На выходах 3 и 4 всегда присутствуют разные значения сигнала, если выходе 3 сигнал равен единицы, то выходе 4 он равен нулю и наоборот. Записать в триггер единицу – значит подать на вход S единицу в этом случае на выходе 3 (единичном) будет выставлен единичный сигнал. Ноль в триггер записывается подачей единицы на вход R, тогда на единичном выходе (3) будет сигнал нуль. Триггер служит основой для построения функциональных узлов, способных хранить двоичные коды, осуществлять передачу и запись, а так же выполнять с ними некоторые специальные операции. Такие функциональные узлы называются регистрами. Регистр представляет собой набор триггеров, число которых определяет разрядность регистра. Разрядность регистра кратна восьми битам: 8-, 16-, 32-, 64- разрядные регистры. Кроме этого в состав регистра входят схемы управления его работой. На рис. 1.14 приведена схема регистра хранения. Регистр содержит n триггеров, образующих n разрядов. Перед записью информации регистр обнуляется подачей единичного сигнала на вход "Сброс". Запись информации в регистр производится синхронно подачей единичного сигнала "Запись". Этот сигнал открывает входные вентили (схемы "логическое И") и на тех входах х1… хn, где присутствует единичный сигнал, произойдёт запись единицы. Чтение информации из регистра так же производится синхронно, подачей сигнала "Чтение" на выходные вентили. Обычно регистры содержат дополнительные схемы, позволяющие организовать такие операции как сдвиг информации (регистры сдвига) и подсчёт поступающих единичных сигналов (регистры счётчики).
  ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...  Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...  Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...  ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
это называется коституентой единицы ØX1ÙØX2ÙX3);
(1)
, где n – количество вершин в графе.
Любое преобразование данных в двоичной форме описывается системой логических функций
Z3=Z3(X3,Y3) результат в (младшем разряде) зависит от младших разрядов слагаемых
Элементы памяти могут быть построены на основе логических элементов И, ИЛИ, НЕ. Элемент памяти, который хранит значение одной булевой переменной называется триггером. Условное обозначение триггера на схемах имеет вид: