Логическое устройство компьютера

МОУ ВПО «Воронежский институт экономики и социального управления»

Реферат

по теме:

«Логические операции и логическое устройство компьютера»

Подготовил: Глущенко Алексей Анатольевич ГМУ 1 Проверил: Лихачёва Татьяна Генадьевна

12 декабря 2010 г.

Введение

Алгебра логики (булева алгебра) - это раздел математики, возникший в XIX веке благодаря усилиям английского математика Дж. Буля. Поначалу булева алгебра не имела никакого практического значения. Однако уже в XX веке ее положения нашли применение в описании функционирования и разработке различных электронных схем. Законы и аппарат алгебры логики стал использоваться при проектировании различных частей компьютеров (память, процессор). Хотя это не единственная сфера применения данной науки.

Что же собой представляет алгебра логики? Во-первых, она изучает методы установления истинности или ложности сложных логических высказываний с помощью алгебраических методов. Во-вторых, булева алгебра делает это таким образом, что сложное логическое высказывание описывается функцией, результатом вычисления которой может быть либо истина, либо ложь (1, либо 0). При этом аргументы функции (простые высказывания) также могут иметь только два значения: 0, либо 1.

Буль (англ. GeorgeBoole; 2 ноября 1815, Линкольн -- 8 декабря 1864, Баллинтемпл, графство Корк, Ирландия) --английский математик и логик. Профессор математики Королевского колледжа Корка (ныне Университетский колледж Корк) с 1849. Один из предтеч математической логики.

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

Публикация первой статьи («Теория математических преобразований», 1839) привела к дружбе между Булем и Д. Ф. Грегори(редактором «Кембриджского математического журнала», где статья была опубликована), продолжавшейся до самой смерти последнего в 1844 г. В этот журнал и наследовавший ему «Кембриджский и дублинский математический журнал» Буль представил двадцать две статьи.

Шестнадцать его статей были опубликованы в «Философском журнале» (Philosophical Magazine), шесть мемуаров -- в «Философских трудах» (Philosophical Transactions), ряд других -- в «Трудах Королевского общества Эдинбурга и Королевской Ирландской академии» (TransactionsoftheRoyalSocietyofEdinburghandoftheRoyalIrishAcademy), в «Вестнике С.-Петербургской академии» (Bulletindel'AcadйmiedeSt-Pйtersbourg, под псевдонимом G.Boldt, Vol. IV. pp. 198-215) и в журнале Крелля (Journalfьrdiereineundangewandte Mathematik).

Этот список дополняет публикация 1848 года в «Журнале механика» (Mechanic's Magazine) о математических основах логики.

Всего Булем было опубликовано порядка пятидесяти статей в различных изданиях и несколько монографий.

Математическая логика

Буль был, вероятно, первым после Джона Валлиса математиком, обратившимся к логической проблематике. Идеи применения символического метода к логике впервые высказаны им в статье «Математический анализ логики» (1847). Не удовлетворённый полученными в ней результатами, Буль высказывал пожелание, чтобы о его взглядах судили по обширному трактату «Исследование законов мышления, на которых основываются математические теории логики и вероятностей» (1854). Буль не считал логику разделом математики, но находил глубокую аналогию между символическим методом алгебры и символическим методом представления логических форм и силлогизмов. Единицей Буль обозначал универсум мыслимых объектов, буквенными символами -- выборки из него, связанные с обычными прилагательными и существительными (так, если x="рогатые", а y="овцы", последовательный выбор x и y из единицы даст класс рогатых овец). Буль показал, что символика такого рода подчиняется тем же законам, что и алгебраическая, из чего следовало, что их можно складывать, вычитать, умножать и даже делить. В такой символике высказывания могут быть сведены к форме уравнений, а заключение из двух посылок силлогизма -- получено путём исключения среднего термина по обычным алгебраическим правилам. Ещё более оригинальной и примечательной была часть его системы, представленной в «Законах мышления…», образующая общий символический метод логического вывода. Буль показал, как из любого числа высказываний, включающих любое число терминов, вывести любое заключение, следующее из этих высказываний, путём чисто символических манипуляций. Вторая часть «Законов мышления…» содержит аналогичную попытку обнаружить общий метод в исчислении вероятностей, позволяющий из заданных вероятностей совокупности событий определить вероятность любого другого события, логически связанного с ними. Профессор Огирко, Игорь на основе теории Буля создал теорию относительности в логике.

Математический анализ

На математические темы Булем в течение жизни были созданы два систематических трактата: «Трактат о дифференциальных уравнениях» (1859; второе издание не завершено, материалы к нему опубликованы посмертно в 1865) и задуманный как его продолжение «Трактат о конечных разностях» (1860).Эти труды внесли важный вклад в соответствующие разделы математики и в то же время продемонстрировали глубокое понимание Булем философии своего предмета.

Другие труды

Хотя за исключением математических и логических работ Буль публиковался мало, его труды обнаруживают широкое и глубокое знакомство с литературой. Его любимым поэтом был Данте, причём «Рай» нравился ему больше, чем «Ад».

Постоянными предметами изучения были для Буля метафизика Аристотеля, этика Спинозы, философские труды Цицерона и множество подобных работ. Размышления о научных, философских и религиозных вопросах содержатся в четырёх речах -- «Гений сэра Исаака Ньютона», «Достойное пользование досугом», «Притязания науки» и «Социальный аспект интеллектуальной культуры» -- произнесённых и опубликованных им в разное время.

Наши рассуждения слагаются из высказываний. К примеру, в умозаключение «Некоторые птицы летают; значит, некоторые летающие -- птицы» входят два разных высказывания.

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

Высказывание -- грамматически правильное предложение, взятое вместе с выражаемым им смыслом (содержанием) и являющееся истинным или ложным.

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

Высказывание считается истинным, если даваемое им описание соответствует реальной ситуации, и ложным, если не соответствует ей. «Истина» и «ложь» называются истинностными значениями высказывания.

Из отдельных высказываний разными способами можно строить новые высказывания. Так, из высказываний «Дует ветер» и «Идет дождь» можно образовать более сложные высказывания «Дует ветер и идет дождь», «Либо дует ветер, либо идет дождь», «Если идет дождь, дует ветер» и т. п. Выражения «и», «либо, либо», «если, то» и т. п., служащие для образования сложных высказываний, называются логическими связками.

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

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

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

1. Логические операции и таблицы истинности

F = A & B.

A	B	F
1	1	1
1	0	0
0	1	0
0	0	0

Логическое умножение КОНЪЮНКЦИЯ - это новое сложное выражение будет истинным только тогда, когда истинны оба исходных простых выражения. Конъюнкция определяет соединение двух логических выражений с помощью союза И.

F = A + B

A	B	F
1	1	1
1	0	1
0	1	1
0	0	0

Логическое сложение - ДИЗЪЮНКЦИЯ - это новое сложное выражение будет истинным тогда и только тогда, когда истинно хотя бы одно из исходных (простых) выражений. Дизъюнкция определяет соединение двух логических выражений с помощью союза ИЛИ

A	неА
1	1
1	0

Логическое отрицание : ИНВЕРСИЯ - если исходное выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное выражение ложно, то результат отрицания будет истинным/ Данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО

A	B	F
1	1	1
1	0	0
0	1	1
0	0	1

Логическое следование: ИМПЛИКАЦИЯ - связывает два простых логических выражения, из которых первое является условием (А), а второе (В)- следствием из этого условия. Результатом ИМПЛИКАЦИИ является ЛОЖЬ только тогда, когда условие А истинно, а следствие В ложно. Обозначается символом "следовательно" и выражается словами ЕСЛИ … , ТО …

A	B	F
1	1	1
1	0	0
0	1	0
0	0	1

Логическая равнозначность: ЭКВИВАЛЕНТНОСТЬ - определяет результат сравнения двух простых логических выражений А и В. Результатом ЭКВИВАЛЕНТНОСТИ является новое логическое выражение, которое будет истинным тогда и только тогда, когда оба исходных выражения одновременно истинны или ложны. Обозначается символом "эквивалентности"

Отрицание -- логическая связка, с помощью которой из данного высказывания получается новое высказывание, такое, что если исходное высказывание истинно, его отрицание является ложным, и наоборот.Отрицательное высказывание состоит из исходного высказывания и отрицания, выражаемого обычно словами «не», «неверно, что». Отрицательное высказывание является, таким образом, сложным высказыванием: оно включает в качестве своей части отличное от него высказывание. Например, отрицанием высказывания «10 -- четное число» является высказывание «10 не есть четное число» (или:«Неверно, что 10 есть четное число»).

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

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

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

· каждое высказывание (как простое, так и сложное) имеет одно и только одно из двух значений истинности: оно является либо истинным, либо ложным;

· истинностное значение сложного высказывания зависит только от истинностных значений входящих в него высказываний и способа их логической связи между собой.

Эти предположения кажутся простыми. Приняв их, нужно, однако, отбросить идею, что, наряду с истинными и ложными высказываниями, могут существовать также высказывания неопределенные с точки зрения своего истинностного значения (такие, как, скажем, «Через пять лет в это время будет идти дождь с громом» и т. п.). Нужно отказаться также от того, что истинностное значение сложного высказывания зависит также от «связи по смыслу» соединяемых высказываний.

В обычном языке два высказывания соединяются союзом «и», когда они связаны между собой по содержанию, или смыслу. Характер этой связи не вполне ясен, но понятно, что мы не рассматривали бы конъюнкцию «Он шел в пальто и я шел в университет» как выражение, имеющее смысл и способное быть истинным, или ложным. Хотя высказывания «2 -- простое число» и «Москва -- большой город» истинны, мы не склонны считать истинной также их конъюнкцию «2 -- простое число и Москва -- большой город», поскольку составляющие ее высказывания не связаны между собою по смыслу.

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

Соединяя два высказывания с помощью слова «или», мы получаем дизъюнкцию этих высказываний. Высказывания, образующие дизъюнкцию, называются членами дизъюнкции.

Слово «или» в повседневном языке имеет два разных смысла. Иногда оно означает «одно или другое или оба», а иногда «одно или другое, но не оба вместе». Высказывание «В этом сезоне я хочу пойти на «Пиковую даму» или на «Аиду» допускает возможность двукратного посещения оперы. В высказывании же «Он учится в Московском или в Ленинградском университете» подразумевается, что упоминаемый человек учится только в одном из этих университетов.

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

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

В логике и математике слово «или» всегда употребляется в неисключающем значении.

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

Центральная задача логики -- отделение правильных схем рассуждения от неправильных и систематизация первых. Логическая правильность определяется логической формой. Для ее выявления нужно отвлечься от содержательных частей рассуждения (собственных символов) и сосредоточить внимание на несобственных символах, представляющих эту форму в чистом виде. Отсюда интерес формальной логики к таким, обычно не привлекающим внимания словам, как «и», «или», «если, то» и т. п.

2. Условное высказывание, импликация, эквивалентность

Условное высказывание -- сложное высказывание, формулируемое обычно с помощью связки «если ..., то ...» и устанавливающее, что одно событие, состояние и т. п. является в том или ином смысле основанием или условием для другого. Например: «Если есть огонь, то есть дым», «Если число делится на 9, оно делится на 3» и т. п.

Условное высказывание слагается из двух более простых высказываний. То из них, которому предпослано слово «если», называется основанием, или антецедентом (предыдущим); высказывание, идущее после слова «то», называется следствием, или консеквентом (последующим).

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

В терминах условного высказывания обычно определяются понятия достаточного и необходимого условия: антецедент (основание) есть достаточное условие для консеквента (следствия), а консеквент -- необходимое условие для антецедента. Например, истинность условного высказывания «Если выбор рационален, то выбирается лучшая из имеющихся альтернатив» означает, что рациональность -- достаточное основание для избрания лучшей из имеющихся возможностей, и что выбор такой возможности есть необходимое условие его рациональности.

Типичной функцией условного высказывания является обоснование одного высказывания ссылкой на другое высказывание. К примеру, то, что серебро электропроводно, можно обосновать ссылкой на то, что оно металл: «Если серебро -- металл, оно электропроводно».

Выражаемую условным высказыванием связь обосновывающего и обосновываемого (основания и следствия) трудно охарактеризовать в общем виде и только иногда природа ее относительно ясна. Эта связь может быть, в частности, связью логического следования, имеющей место между посылками и заключением правильного умозаключения («Если все живые многоклеточные существа смертны, а медуза является таким существом, то она смертна»). Связь может представлять собой закон природы («Если тело подвергнуть трению, оно начнет нагреваться») или причинную связь («Если Луна в новолуние находится в узле своей орбиты, наступает солнечное затмение»). Рассматриваемая связь может иметь также характер социальной закономерности, правила, традиции и т. п. («Если меняется общество, меняется также человек», «Если совет разумен, он должен быть выполнен»).

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

И в обычном языке, и в языке науки условное высказывание, кроме функции обоснования, может выполнять также целый ряд других задач. Оно может формулировать условие, не связанное с каким-либо подразумеваемым общим законом или правилом («Если захочу, разрежу свой плащ»), фиксировать какую-то последовательность («Если прошлое лето было сухим, то в этом году оно дождливое»), выражать в своеобразной форме неверие («Если вы решите эту задачу, я докажу великую теорему Ферма»), противопоставление («Если в огороде растет бузина, то в Киеве живет дядька») и т. п. Многочисленность и разнородность функций условного высказывания существенно затрудняет его анализ.

Употребление условного высказывания связано с определенными психологическими факторами. Так, обычно мы формулируем такое высказывание, только если не знаем с определенностью, истинны или нет его антецедент и консеквент. В противном случае его употребление кажется неестественным («Если вата -- металл, она электропроводна»).

Условное высказывание находит очень широкое применение во всех сферах рассуждения. В логике оно представляется, как правило, посредством импликативного высказывания, или импликации. При этом логика проясняет, систематизирует и упрощает употребление «если ..., то ...», освобождает его от влияния психологических факторов.

Логика отвлекается, в частности, от того, что характерная для условного высказывания связь основания и следствия в зависимости от контекста может выражаться не только с помощью «если ..., то ...», но и с помощью других языковых средств. К примеру: «Так как вода жидкость, она передает давление во все стороны равномерно», «Хотя пластилин и не металл, он пластичен», «Если бы дерево было металлом, оно было бы электропроводно» и т. п. Эти и подобные им высказывания представляются в языке логики посредством импликации, хотя употребление в них «если ..., то ...» было бы не совсем естественным.

Утверждая импликацию, мы утверждаем, что не может случиться, чтобы ее основание (антецедент) было истинным, а следствие (консеквент) -- ложным.

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

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

и ее основание, и ее следствие истинны;

основание ложно, а следствие истинно;

и основание, и следствие ложны.

Только в четвертом случае, когда основание истинно, а следствие ложно, вся импликация ложна.

Импликацией, в частности, не предполагается, что высказывания А и В как-то связаны между собой по содержанию. В случае истинности В высказывание «если А, то В» истинно независимо от того, является А истинным или ложным и связано оно по смыслу с В или нет. Истинными считаются, например, высказывания: «Если на Солнце есть жизнь, то дважды два равно четыре», «Если Волга -- озеро, то Токио -- большой город» и т. п. Условное высказывание истинно также тогда, когда А ложно, и при этом опять-таки безразлично, истинно В или нет и связано оно по содержанию с А или нет. К истинным относятся, к примеру, высказывания: «Если Солнце -- куб, то Земля -- треугольник», «Если дважды два равно пять, то Токио маленький город» и т. п. В обычном рассуждении все эти высказывания вряд ли будут рассматриваться как имеющие смысл и еще в меньшей степени как истинные.

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

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

С импликацией тесно связана эквивалентность, называемая иногда «двойной импликацией».

Эквивалентность -- сложное высказывание «А, если и только если В», образованное из высказываний А и В и разлагающееся на две импликации: «если А, то В» и «если В, то А». Например: «Треугольник является равносторонним, если и только если он является равноугольным». Термином «эквивалентность» обозначается и связка «..., если и только если ...», с помощью которой из двух высказываний образуется данное сложное высказывание. Вместо «..., если и только если ...» для этой цели могут использоваться «... в том и только том случае, когда ...», «... тогда и только тогда, когда ...» и т. п.

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

Обозначим эквивалентность символом «-», формула А «-» В может быть прочитана как: «А, если и только если В».

С использованием введенной логической символики связь эквивалентности и импликации можно представить так:

«А«-»В» означает (А -»В) Л (В-»А)

Например: высказывание «Ромб является квадратом, если и только если все углы ромба прямые» означает «Если ромб есть квадрат, то все углы ромба прямые, и если все углы ромба прямые, го ромб есть квадрат».

Эквивалентность является отношением типа равенства. Как и всякое такое отношение, эквивалентность высказываний является рефлексивной (всякое высказывание эквивалентно самому себе), симметричной (если одно высказывание эквивалентно другому, то второе эквивалентно первому) и транзитивной (если одно высказывание эквивалентно другому, а другое -- третьему, то первое высказывание эквивалентно третьему).

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

Таблица 1.

Название	Символ	Толкование
Отрицание	~	«не»
Конъюнкция	Л	«… и …»
Дизъюнкция в неисключающем смысле	V	«… или …»
Дизъюнкция в исключающем смысле	V	«либо…, либо …»
Импликация	-»	«если …, то …»
Эквивалентность	«-»	«…, если и только если …»

Следующие примеры показывают употребление данных связок.

Таблица 1.

А	~ А	А-»А	Av~A	А л ~А	~ (А л ~ А)
и	л	и	и	л	и
л	и	и	и	л	и

Таблица 1.

А	В	A-»B	(А-»В)лА	((A-»B) Л А)-*В
и	и	и	и	и
и	л	л	л	и
л	и	и	л	и
л	л	и	л	и

Эти таблицы показывают, что формулы (А-»А), (А V ~ А), ~(АЛ~А), ((А-»В) Л А)-»В и ((А-»В) Л~В)-»~ А принимают значение истинно при любых значениях входящих в них переменных. Такие формулы называются общезначимыми, или тождественно истинными, или тавтологиями. Более подробно об общезначимых формулах, представляющих законы логики, говорится в главе, посвященной этим законам. В алгебре логики имеется ряд законов, позволяющих производить равносильные преобразования логических выражений. Приведем соотношения, отражающие эти законы.

1. Закон двойного отрицания:

А = .

Двойное отрицание исключает отрицание.

2. Переместительный (коммутативный) закон:

-- для логического сложения:

A V B = B V A

-- для логического умножения:

A&B = B&A.

Результат операции над высказываниями не зависит от того, в каком порядке берутся эти высказывания.

В обычной алгебре 2 + 3 = 3 + 2, 2 ґ 3 = 3 ґ 2.

3. Сочетательный (ассоциативный) закон:

-- для логического сложения:

(A Ъ B) Ъ C = A Ъ (BЪ C);

-- для логического умножения:

(A&B)&C = A&(B&C).

При одинаковых знаках скобки можно ставить произвольно или вообще опускать.

В обычной алгебре:

(2 + 3) + 4 = 2 + (3 + 4) = 2 + 3 + 4, 5 ґ (6 ґ 7) = 5 ґ (6 ґ 7) = 5 ґ 6 ґ 7.

4. Распределительный (дистрибутивный) закон:

-- для логического сложения:

(A Ъ B)&C = (A&C) Ъ (B&C);

-- для логического умножения:

(A&B) Ъ C = (A Ъ C)&(B Ъ C).

Определяет правило выноса общего высказывания за скобку.

В обычной алгебре:

(2 + 3) ґ 4 = 2 ґ 4 + 3 ґ4.

5. Закон общей инверсии (законы де Моргана):

-- для логического сложения

=  &  ;

-- для логического умножения:

=  Ъ 

6. Закон идемпотентности

-- для логического сложения:

A Ъ A = A;

-- для логического умножения:

A&A = A.

Закон означает отсутствие показателей степени.

7. Законы исключения констант:

-- для логического сложения:

A Ъ 1 = 1, A Ъ 0 = A;

-- для логического умножения:

A&1 = A, A&0 = 0.

8. Закон противоречия:

A&  = 0.

Невозможно, чтобы противоречащие высказывания были одновременно истинными.

9. Закон исключения третьего:

A Ъ  = 1.

10. Закон поглощения:

-- для логического сложения:

A Ъ (A&B) = A;

-- для логического умножения:

A&(A Ъ B) = A.

11. Закон исключения (склеивания):

-- для логического сложения:

(A&B) Ъ (  &B) = B;

-- для логического умножения:

(A Ъ B)&(  Ъ B) = B.

12. Закон контрапозиции (правило перевертывания):

(A Ы B) = (BЫ A).¬(А>В) = А&¬В¬А&(АЪВ)= ¬А&ВАЪ¬А&В=АЪВ

Логический элемент компьютера -- это часть электронной логичеcкой схемы, которая реализует элементарную логическую функцию.

Логическими элементами компьютеров являются электронные схемы И, ИЛИ, НЕ, И--НЕ, ИЛИ--НЕ и другие (называемые такжевентилями), а также триггер.

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

Чтобы представить два логических состояния -- “1” и “0” в вентилях, соответствующие им входные и выходные сигналы имеют один из двух установленных уровней напряжения. Например, +5 вольт и 0 вольт.

Высокий уровень обычно соответствует значению “истина” (“1”), а низкий -- значению “ложь” (“0”).

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

Работу логических элементов описывают с помощью таблиц истинности.

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

С х е м а И

Схема И реализует конъюнкцию двух или более логических значений. Условное обозначение на структурных схемах схемы И с двумя входами представлено на рис. 5.1.



Рис. 5.1

Таблица истинности схемы И

x	y	x . y
0	0	0
0	1	0
1	0	0
1	1	1

Единица на выходе схемы И будет тогда и только тогда, когда на всех входах будут единицы. Когда хотя бы на одном входе будет ноль, на выходе также будет ноль.

Связь между выходом z этой схемы и входами x и y описывается соотношением: z = x ^. y (читается как "x и y"). Операция конъюнкции на структурных схемах обозначается знаком "&" (читается как "амперсэнд"), являющимся сокращенной записью английского слова and.

С х е м а ИЛИ

Схема ИЛИ реализует дизъюнкцию двух или более логических значений. Когда хотя бы на одном входе схемы ИЛИ будет единица, на её выходе также будет единица.

Условное обозначение на структурных схемах схемы ИЛИ с двумя входами представлено на рис. 5.2. Знак "1" на схеме -- от устаревшего обозначения дизъюнкции как ">=1" (т.е. значение дизъюнкции равно единице, если сумма значений операндов больше или равна 1). Связь между выходом z этой схемы и входами x и y описывается соотношением: z = x v y (читается как "x или y").

Рис. 5.2

Таблица истинности схемы ИЛИ

x	y	x v y
0	0	0
0	1	1
1	0	1
1	1	1

С х е м а НЕ

Схема НЕ (инвертор) реализует операцию отрицания. Связь между входом x этой схемы и выходом z можно записать соотношением z =, где  читается как "не x" или "инверсия х".

Если на входе схемы 0, то на выходе 1. Когда на входе 1, на выходе 0. Условное обозначение на структурных схемах инвертора -- на рисунке 5.3

Рис. 5.3

Таблица истинности схемы НЕ

x
0	1
1	0

С х е м а И--НЕ

Схема И--НЕ состоит из элемента И и инвертора и осуществляет отрицание результата схемы И. Связь между выходом z и входами x и yсхемы записывают следующим образом: , где читается как "инверсия x и y". Условное обозначение на структурных схемах схемы И--НЕ с двумя входами представлено на рисунке 5.4.

Рис. 5.4

Таблица истинности схемы И--НЕ

x	y
0	0	1
0	1	1
1	0	1
1	1	0

С х е м а ИЛИ--НЕ

Схема ИЛИ--НЕ состоит из элемента ИЛИ и инвертора и осуществляет отрицание результата схемы ИЛИ. Связь между выходом z и входами x и y схемы записывают следующим образом: , где , читается как "инверсия x или y ". Условное обозначение на структурных схемах схемы ИЛИ--НЕ с двумя входами представлено на рис. 5.5.

Рис. 5.5

Таблица истинности схемы ИЛИ--НЕ

x	y
0	0	1
0	1	0
1	0	0
1	1	0

Что такое триггер?

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

Термин триггер происходит от английского слова trigger -- защёлка, спусковой крючок. Для обозначения этой схемы в английском языке чаще употребляется термин flip-flop, что в переводе означает "хлопанье". Это звукоподражательное название электронной схемы указывает на её способность почти мгновенно переходить ("перебрасываться") из одного электрического состояния в другое и наоборот.

Самый распространённый тип триггера -- так называемый RS-триггер (S и R, соответственно, от английских set -- установка, и reset -- сброс). Условное обозначение триггера -- на рис. 5.6.

Он имеет два симметричных входа S и R и два симметричных выхода Q и, причем выходной сигнал Q является логическим отрицанием сигнала .

На каждый из двух входов S и R могут подаваться входные сигналы в виде кратковременных импульсов .

Наличие импульса на входе будем считать единицей, а его отсутствие -- нулем.

На рис. 5.7 показана реализация триггера с помощью вентилей ИЛИ--НЕ и соответствующая таблица истинности.

S	R	Q
0	0	запрещено
0	1	1	0
1	0	0	1
1	1	хранение бита

Проанализируем возможные комбинации значений входов R и S триггера, используя его схему и таблицу истинности схемы ИЛИ--НЕ (табл. 5.5).

1. Если на входы триггера подать S="1", R="0", то (независимо от состояния) на выходе Q верхнего вентиля появится "0". После этого на входах нижнего вентиля окажется R="0", Q="0" и выход станет равным "1".

2. Точно так же при подаче "0" на вход S и "1" на вход R на выходе появится "0", а на Q -- "1".

3. Если на входы R и S подана логическая "1", то состояние Q и не меняется.

4. Подача на оба входа R и S логического "0" может привести к неоднозначному результату, поэтому эта комбинация входных сигналов запрещена.

Поскольку один триггер может запомнить только один разряд двоичного кода, то для запоминания байта нужно 8 триггеров, для запоминания килобайта, соответственно, 8 х 2¹⁰ = 8192 триггеров. Современные микросхемы памяти содержат миллионы триггеров.

Сумматор логический операционный узел, выполняющий арифметическое сложение кодов двух чисел. При арифметическом сложении выполняются и другие дополнительные операции: учет знаков чисел, выравнивание порядков слагаемых и тому подобное. Указанные операции выполняются в арифметическо-логических устройствах (АЛУ) или процессорных элементах, ядром которых являются сумматоры.

Сумматоры классифицируют по различным признакам.

В зависимости от системы счисления различают:

· двоичные;

· двоично-десятичные (в общем случае двоично-кодированные);

· десятичные;

· прочие (например, амплитудные).

По количеству одновременно обрабатываемых разрядов складываемых чисел:

· одноразрядные,

· многоразрядные.

По числу входов и выходов одноразрядных двоичных сумматоров:

· четвертьсумматоры (элементы "сумма по модулю 2"; элементы "исключающее ИЛИ"), характеризующиеся наличием двух входов, на которые подаются два одноразрядных числа, и одним выходом, на котором реализуется их арифметическая сумма;

· полусумматоры, характеризующиеся наличием двух входов, на которые подаются одноименные разряды двух чисел, и двух выходов: на одном реализуется арифметическая сумма в данном разряде, а на другом перенос в следующий (более старший разряд);

· полные одноразрядные двоичные сумматоры, характеризующиеся наличием трех входов, на которые подаются одноименные разряды двух складываемых чисел и перенос из предыдущего (более младшего) разряда, и двумя выходами: на одном реализуется арифметическая сумма в данном разряде, а на другом перенос в следующий (более старший разряд).

По способу представления и обработки складываемых чисел многоразрядные сумматоры подразделяются на:

· последовательные, в которых обработка чисел ведется поочередно, разряд за разрядом на одном и том же оборудовании;

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

Параллельный сумматор в простейшем случае представляет собой n одноразрядных сумматоров, последовательно (от младших разрядов к старшим) соединенных цепями переноса. Однако такая схема сумматора характеризуется сравнительно невысоким быстродействием, так как формирование сигналов суммы и переноса в каждом i-ом разряде производится лишь после того, как поступит сигнал переноса с (i-1)-го разряда. Таким образом, быстродействие сумматора определяется временем распространения сигнала по цепи переноса. Уменьшение этого времени основная задача при построении параллельных сумматоров.

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

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

· с последовательным переносом;

· с параллельным переносом;

· с групповой структурой;

· со специальной организацией цепей переноса.

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

· сумматоры со сквозным переносом, в которых между входом и выходом переноса одноразрядного сумматора оказывается наименьшее число логических уровней [1];

· сумматоры с двухпроводной передачей сигналов переноса [1, 2];

· сумматоры с условным переносом (вариант сумматора с групповой структурой, позволяющий уменьшить время суммирования в 2 раза при увеличении оборудования в 1,5 раза) [3];

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

Сумматоры, которые имеют постоянное время, отводимое для суммирования, независимое от значений слагаемых, называют синхронными.

По способу выполнения операции сложения и возможности сохранения результата сложения можно выделить три основных вида сумматоров:

· комбинационный, выполняющий микрооперацию "S = A плюс B", в котором результат выдается по мере его образования (это комбинационная схема в общепринятом смысле слова);

· сумматор с сохранением результата "S = A плюс B";

· накапливающий, выполняющий микрооперацию "S = S плюс B".

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

Важнейшими параметрами сумматоров являются:

· разрядность;

· статические параметры: Uвх, Uвх, Iвх и так далее, то есть обычные параметры интегральных схем;

· динамические параметры. Сумматоры характеризуются четырьмя задержками распространения:

· от подачи входного переноса до установления всех выходов суммы при постоянном уровне на всех входах слагаемых;

· от одновременной подачи всех слагаемых до установления всех выходов суммы при постоянном уровне на входе переноса;

· от подачи входного переноса до установления выходного переноса при постоянном уровне на входах слагаемых;

· от подачи всех слагаемых до установления выходного переноса при постоянном уровне на входах слагаемых.

Четвертьсумматор

Простейшим двоичным суммирующим элементом является четвертьсумматор. Происхождение названия этого элемента следует из того, что он имеет в два раза меньше выходов и в два раза меньше строк в таблице истинности по сравнению с полным двоичным одноразрядным сумматором. Наиболее известны для данной схемы названия: элемент "сумма по модулю 2" и элемент "исключающее ИЛИ". Схема (рис. 1) имеет два входа а и b для двух слагаемых и один выход S для суммы. Работу ее отражает таблица истинности 1 (табл. 1), а соответствующее уравнение имеет вид

Уравнение



	(1)

Рис. 1	Таблица 1

Данный элемент выпускается в виде интегральных схем (ИС) типа ЛП5 (серии 133, 155, 530, 531, 533, 555, 1531, 1533); ЛП12 (555); ЛП107 (100, 500, 1500); ЛП2 (561, 564); ЛП14 (1561) и т. п.

Реализуем четвертьсумматор в базисах И-НЕ, ИЛИ-НЕ и с использованием только одного инвертора, для чего преобразуем уравнение (1):

	(2)
	(3)
	(4)

Схемы, полученные по уравнениям (2)(4), приведены на рис. 2.

Рис. 2

Полусумматор

Полусумматор (рис. 3) имеет два входа a и b для двух слагаемых и два выхода: S сумма, P перенос. Обозначением полусумматора служат буквы HS (halfsumполусумма). Работу его отражает таблица истинности 2 (табл. 2), а соответствующие уравнения имеют вид:

	(5)

Рис. 3	Таблица 2

Из уравнений (5) следует, что для реализации полусумматора требуется один элемент "исключающее ИЛИ" и один двухвходовый вентиль И (рис. 3б).

3. Полный одноразрядный двоичный сумматор

Он (рис. 4) имеет три входа: a, b для двух слагаемых и p для переноса из предыдущего (более младшего) разряда и два выхода: S сумма, P перенос в следующий (более старший) разряд. Обозначением полного двоичного сумматора служат буквы SM. Работу его отражает таблица истинности 3 (табл. 3).



Рис. 4	Таблица 3 № наб. a b p P S 0 0 0 0 0 0 1 0 0 1 0 1 2 0 1 0 0 1 3 0 1 1 1 0 4 1 0 0 0 1 5 1 0 1 1 0 6 1 1 0 1 0 7 1 1 1 1 1

Отметим два момента. Первый: в табл. 2 и 3 выходные сигналы P и S не случайно расположены именно в такой последовательности. Это подчеркивает, что PS рассматривается как двухразрядное двоичное число, например, 1 + 1 = 2₁₀ = 10₂ , то есть P = 1, а S = 0 или 1 + 1 + 1 = 3₁₀ = 11₂, то есть P = 1, а S = 1. Второй: выходные сигналы P и S полного двоичного сумматора относятся к классу самодвойственных функций алгебры логики. Самодвойственными называют функции, инвертирующие свое значение при инвертировании всех переменных, от которых они зависят. Обратите внимание, что P и S для четвертьсумматора и полусумматора не являются самодвойственными функциями! Преимущества, вытекающие из этого свойства полного двоичного сумматора, будут рассмотрены при анализе возможностей ИС типа 155ИМ1.

Уравнения, описывающие работу полного двоичного сумматора, представленные в совершенной дизъюнктивной нормальной форме (СДНФ), имеют вид:

Уравнение для переноса может быть минимизировано:

P = ab + ap + bp. (7)

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

Например, преобразуем уравнения (6) следующим образом:

	(8)

Из выражений (8) следует, что полный двоичный сумматор может быть реализован на двух полусумматорах и одном двухвходовом элементе ИЛИ. Соответствующая схема приведена на рис. 5.

Рис. 5

Из выражения (8) для S также следует:

S = a Е b Е p. (9)

Примечание. Так как операция Е в выражении (9) коммутативна (переменные можно менять местами), то следует, что три входа полного двоичного сумматора абсолютно равноправны и на любой из них можно подавать любую входную переменную. Это полезно помнить, разводя печатные платы, на которых установлены ИС сумматоров.

К настоящему времени разработано большое число схем сумматоров. Доказано (нашим отечественным ученым Вайнштейном), что при использовании только одного инвертора нельзя реализовать полный двоичный сумматор со сложностью P_кв < 16, а при двух инверторах P_кв < 14, где P_кв вес по Квайну, используемый как оценка сложности любых комбинационных схем. Pкв это общее число всех входов всех логических элементов схемы без учета инверторов.

Рис. 6

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

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

Таблица 4

№ наб.	a	b	p	P	S
10	1	0	1	0	x
11	1	0	1	1	0
12	1	1	0	0	x
13	1	1	0	1	0
14	1	1	1	0	x
15	1	1	1	1	1

Из карты Карно для функции S (рис. 6) следует:

S = abp + Pa + Pb + Pp = = abp + P(a + b + p). (10)

Второй метод основан на применении диаграмм Венна. На рис. 7а показана диаграмма Венна для трех переменных а, b, p; области, ограниченные окружностями, соответствуют переменным а, b, p, а области, обозначенные цифрами от 0 до 7 соответствующим конъюнкциям (например, 5 = abp). Область, заштрихованная на рис. 7б, очевидно, соответствует функции P = ab + ap + bp. Функция S представлена заштрихованной областью на рис. 7в. Ее можно представить суммой произведения функции a + b + p (рис. 7г) на функцию ab + ap + bp (рис. 7д) и функции abp (рис. 7е). Очевидно, что в этом случае получается выражение для S, аналогичное уравнению (10).



Рис. 7

Схема сумматора, реализованного по уравнениям (7) и (10), приведена на рис. 8а. В данной схеме используются многовходовые логические элементы Ии ИЛИ. Если использовать только двухвходовые элементы, то получаются схемы, приведенные на рис. 8б,в.