Файл: sem6.doc

Семинар 6. Общие принципы вычислений

6.1 Основные понятия алгебры логики

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

Алгебралогикивозниклавсередине19векавработахДж.БуляибыларазвитаЧ.Пирсом

(C.S. Peirs),П.С.Порецким,Б.Расселом(B.Russel),Д.Гильбертом(D.Hilbert)идр.

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

Истина _≡ И _≡ True _≡ T _≡ 1. (6.1)

Для обозначения ложности высказывания вводятся следующие тождественные символы

Ложь _≡ Л _≡ False _≡ F _≡ 0. (6.2)

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

"и"(конъюнкция) _≡ & _≡∧≡ AND _≡∩"или"(дизъюнкция) _≡∨≡ OR"если...то"(импликация)_≡→"эквивалентность" _≡∼

"отрицание" _≡ черта над высказыванием _≡¬≡ NOT

⎫⎬

(6.3)

Связкиичастицы"не"рассматриваютсявалгебрелогикикакоперациинадвеличинами,принимающиедвазначения0и1,авысказыванияспроизвольнымивысказываниямиисвязкамиобразуютформулы.Приэтомвысказывания,образующиеформулу,рассматриваютсявкачествепеременных,асвязкивкачествефункций.ФормулыAиBназываютсяравными(A=B),еслиониреализуютравныефункции.

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

a

b

NOT a

a ∧ b

a ∨ b

a → b

a ∼ b

0

0

1

0

0

1

1

0

1

1

0

1

1

0

1

0

0

0

1

0

0

1

1

0

1

1

1

1

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

– закон коммутативности

a _∨ b = b _∨ a; a _∧ b = b _∧ a; (6.4)

– закон ассоциативности

(a _∧ b) _∧ c = a _∧ (b _∧ c);(a_∨ b) _∨ c = a _∨ (b _∨ c);(6.5)

– закон поглощения

a _∧ (a _∨ b)=a;a_∨ (a _∧ b)=a;(6.6)

– закон дистрибутивности

a _∧ (b _∨ c)=(a_∧ b) _∨ (a _∧ z);a_∨ (b _∧ c)=(a_∨ b) _∧ (a _∨ c);(6.7)

– закон противоречия

a _∧ a = 0; (6.8)

– закон исключения третьего

a _∨ a = 1; (6.9)

a _→ b = a _∨ b; a _∼ b =(a _∧ b) _∨ (a _∧ b) (6.10)

Множество всех формул, в построении которых учавствуют переменные высказывания, символы _∧, _∨, _→, _∼, _¬, константы 0 и 1 называются языком над данными символами. Равенство (6.4)–(6.10) означают, что для всякой формулы в языке над _∧, _∨, _→, _∼, _¬, 0, 1 найдется равная ей формула в языке над _∧, _∨,,0,1.

¬

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

Вязыкенад _∧, _∨, _→, _∼, 0, 1, _⊕,где _⊕ – используетсядляобозначениясложенияпомодулю 2 устанавливаются следующие соотношения:

a _∨ b = ((a _∧ b)+a)+b(6.11)a_→ b = a _∧ b; a _∼ b=(a+b)+1;(6.12)a+b=(a_∧ b) _∨ (a _∧ b);1=a_∨ a. (6.13)

6.2 Классические универсальные машины и логические гейты

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

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

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

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

Нарисункеуказано,чтобитaпроходитчерезгейтNOT,которыйпереворачиваетбит,превращая1в0и0в1.ЛиниидоипослегейтаNOTслужатдляпереносабитакгейтуиудалениеегопослепреобразования.Данныелинии(провода)могутпредставлятькакпереносбитаизоднойточкипространствавдругую,такиразвитиесостояниябитавовремени.ГейтNOTимеетодинвходнойбитиодинбитнавыходе.Фактически,выходнойбитвычисляетфункциюf(a)=1_⊕ a.

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

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

a

b

c

0

0

0

;

c ≡ a ∧ b = a · b

0 1

1 0

0 0

1

1

1

				б. OR-гейт

a

b

c

0

0

0

;

c ≡ a ∨ b = a + b − a · b

0 1

1 0

1 1

1

1

1

в. XOR-гейт (исключающее или _≡ "или", но не оба)

ab

00

; c _≡ aXORb=a(1₋ b)+b(1₋ a) 01

10 11

г. NAND-гейт _≡ (NOT AND-гейт)

ab

00 ; c =1 ₋ ab 01

·

10 11 д. NOR-гейт _≡ (NOT OR-гейт)

ab

00

; c = (1 ₋ a)(1₋ b) 01 10 11

0 1 1 0

c

1 1 1 0

c

1 0 0 0

Любоевычислениеможетбытьзаписановтерминахбулевскоговыражения,илюбоебулевскоевыражениеможетбытьпостроеноизфиксированногонаборалогическихгейтов.Такойнабор(например,AND,ORилиNOT)называетсяуниверсальным.Вдействительностиможнообойтисьтолькодвумягейтами,такимикакANDиNOT,илиORиNOT,илиANDиXOR.Устройство,котороеможетисполнитьпроизвольныекомбинациилогическихгейтовизуниверсальногонабора,являетсяуниверсальнымкомпьютером.

Хотяприведенныевышегейтыдостаточныдляматематическогоаппаратаалгебрылогики,онинедостаточныдляреализациипрактическойвычислительноймашины.ВреальномустройстветребуютсяещедвагейтаFANOUT(разворачивание)иERASE(стирание).

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

		В некоторых приложениях используется, помимо того, гейт EXCHANGE

a 0 0 1 1

b

0 1 0 1

50

a�

b�

0

0

1

0

0

1

1

1

Для примера рассмотрим цепь, которая суммирует два целых числа, имеющих длину nбит. Базовым элементом в этой цепи является "ячейка" сети известная как полусумматор (half-adder _≡ HA). На вход полусумматора подаются два бита x и y, а на выходе получается сумма битов x _⊕ y по модулю 2 и перенос (carry) бита в состоянии 1, если x и y оба 1, или 0 во всех остальных случаях.

Схема сети полусумматора имеет вид:

	Таблица истинности полусумматора:

x

y

0

0

0

1

1

0

1

1

перенос
0
0
0
1

^x _⊕ ^y

0 1 1 0

двоичное число

00 01 01 10

Перенос бита позволяет перейти на следующий разряд, если складывается 1+1=0. Каскад из 2-х полусумматоров (HA) образует полный сумматор (full-adder _≡ FA)

Полныйсумматоримееттрибитанавходе,гдеx,y–данныедлясложения,c–переносбитаспредыдущегоэтапавычисленийидвабитанавыходе.Одинвыходнойбитявляетсясуммойпомодулю2x_⊕ y _⊕ cвсехтрехвходящихбитов,авторойвыходнойбитc�–естьпереносбита,которыйравен1,еслидваилибольшевходныхбитаравны1,иравен0впротивномслучае.

											Таблица истинности полного сумматора: Каскадполныхсумматоров,позволяющийпостроитьцепьдлясложениядвух2-хбитовыхцелых(x1x0)+(y1y0)

x

y

c

x

y

c

x

y

c

перенос

x ⊕ y ⊕ c

число

0 0 1 1

0 1 0 1

0 0 0 0

0 0 0 1

0 1 1 0

0 0 0 0

0 0 0 1

0 0 0 0

0 1 1 0

0 0 0 1

0 1 1 0

00 01 01 10

0 0 1 1

0 1 0 1

1 1 1 1

0 0 0 1

0 1 1 0

1 1 1 1

0 0 0 1

0 1 1 0

1 0 0 1

0 1 1 1

1 0 0 1

01 10 10 11

x1

x0

y1

y0

x1

x0

y1

y0

c

x0

y0

x + y

10-тичное число

0

0

0

0

0

0

0

0

0

0

0

000

0

0

1

0

0

0

0

0

1

0

0

1

001

1

1

0

0

0

1

0

0

0

0

1

0

010

2

1

1

0

0

1

0

0

1

0

1

1

011

3

0

0

0

1

0

0

0

1

0

0

1

001

1

0

1

0

1

0

1

0

0

0

1

0

010

2

1

0

0

1

1

0

0

1

0

1

1

011

3

1

1

0

1

1

1

0

0

1

0

0

100

4

0

0

1

0

0

0

1

0

0

1

0

010

2

0

1

1

0

0

0

1

1

0

1

1

011

3

1

0

1

0

1

0

1

0

1

0

0

100

4

1

1

1

0

1

0

1

1

1

0

1

101

5

0

0

1

1

0

0

1

1

0

1

1

011

3

0

1

1

1

0

1

1

0

1

0

0

100

4

1

0

1

1

1

0

1

1

1

0

1

101

5

1

1

1

1

1

1

1

0

1

1

0

110

6

Каскадполныхсумматоровпозволяетпостроитьцепьдлясложениядвухn-битовыхцелых.Примердляn=3приведеннарисункениже.

Здесьдватрехбитовыхцелыхчислапредставленыввидеx=x2x1x0иy=y2y1y0.Аналогичноможетбытьпостроенацепьвычисленияпроизвольнойфункции.

В классическом компьютере NOT и NAND-гейты осуществляются транзисторами, например, как показано на рис. 6.1.

рис. 6.1.

Минимальнаясвободнаяэнергия,котораярасходуетсянаточтобыработалидеальныйкомпьютерзависитотнабораичислапримитивныхэлементов.Например,нагейтеNAND,выходящаялинияc�принимаетодноиздвухзначенийиприэтомэнтропияизменяетсянаln2единицы.Теоретическийминимумколичестватеплоты,котороерассеиваетсявпространствонаодномэлементарномшагесоставляетkTln2(здесьk–постояннаяБольцмана,T–абсолютнаятемпература).Фактическивреальныхвычислительныхустройствахпроисходитдиссипацияэнергиипорядка_∼ 10¹⁰ kT . Физически это связано с тем, что для изменения потенциала (напряжения) проводника он сначала заземляется через сопротивление, а затем через сопротивление заряжается.

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

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

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

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

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

¹R. Landaner. IBM. J.Res. Develop. 3, p.183 (1961)
²R.W. Keyes. IBM. J.Res. Develop. 32, 24 (1988)

6.3 Обратимые логические гейты

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

При построении логических цепей с обратимыми логическими элементами можно использовать три обратимых гейта ³: NOT, CNOT, CCNOT, определение которых имеет следующий вид:

а. NOT-гейт. Стандартный NOT-гейт, очевидно не теряет информации и является обратимым. Обращение достигается повторным действием NOT-гейта.

			б. CNOT-гейт (CNOT ≡ CONTROLLED NOT ≡ контролируемое "не"). Данный гейт определяется следующей диаграммой и таблицей истинности

a

b

a�

b�

0

0

0

0

0

1

0

1

1

0

1

1

1

1

1

0

ГейтCNOTимеетдвевходящиелинииaиb(двавходныхбита)идвевыходящиелинии(дверезультирующихбита).Битa�всегдатотже,чтоиa,асоответствующаялинияназываетсяконтролирующей(иликонтрольной)линией.Есликонтролирующаялинияактивирована(a=1),тогдавыходнойбитb�естьNOTотb.Впротивномслучае(a=0)b�=b:

NOT b, если a =1

b� = (6.14)

b, если a =0.

					Используя определение гейта CNOT видно, что:

– действие данного гейта обращается простым повторением

– величина b� является симметричной функцией a и b и является гейтом XOR (исключающее или) a или b, но не оба. Данная операция является операцией суммирования a и b по модулю 2, что символически можно записать в виде

a

b

a�

b�

a��

b��

0

0

0

0

0

0

0

1

0

1

0

1

1

0

1

1

1

0

1

1

1

0

1

1

54

XOR:(x,y)_→ (x,x_⊕ y).(6.15)

Соответственно символическое обозначение гейта CNOT допустимо писать в виде:

CNOT:(a,b)_→ (a,a_⊕ b) _≡ (a,XOR:(a,b)).(6.16)

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

СоответственногейтCNOTсохраняетлиниюa=a�,чтоиустраняетнеопределенностьгейтаXOR.

– гейтCNOTобеспечиваетгейтFANOUT,таккакприb=0,aкопируетсяналиниюb�.

FANOUT

; или FANOUT _≡ CNOT:(a,0).(6.17)

≡

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

– гейтCNOTобеспечиваетгейтEXCHANGE(илиSWAP)

в. Гейт CCNOT (CONTROLLED CONTROLLED NOT) (контролируемое

≡ ≡

контролируемое "не"). Данный гейт определяется следующей диаграммой и таблицей истинности:

abc a� b� c�

000

000001

001010

010011

011100

100101

101110

111111

110 ГейтCCNOT–содержиттрилинииизкоторыхдвелинииaиbявляютсяконтрольнымииостаютсянеизменныминавыходе,авыходтретьейлинииc�=NOTc,еслиобеконтрольныелинииактивированы(a=b=1),впротивномслучаеc�=c.

Из определения гейта CCNOT следует, что

– еслинавходетретьейлинииc=0,тоc�=1толькоприусловииa=1иb=1,впротивномслучаеa=0илиb=0илиa=b=0навыходетретьейлинииполучимc�=0.Такимобразомвэтомслучае(c=0)гейтопределяет(функцию)гейтAND,чтосимволическиможнозаписатьследующимобразом:

CCNOT:(a,b,0)(a,b,AND(a,b)).(6.18)

→

Трикомбинациивходныхбитов(a,b),аименно(0,0),(0,1),(1,0),приводяткодномувыходномубитулогическойфункцииAND(a,b)=0.Следовательнодляустранениянеоднозначноститребуетсяпомнитьобавходныхбитаилииметьдвеконтролируемыелинии.

Сохранение этих битов на линиях a, b на выходе позволяет обратить действие гейта.

– повторноевыполнениеоперацииCCNOTобращаетрезультатпервойоперацииCCNOT

								рис. 6.6.

a

b

c

a�

b�

c�

a��

b��

c��

0

0

0

0

0

0

0

0

0

0

0

1

0

0

1

0

0

1

0

1

0

0

1

0

0

1

0

0

1

1

0

1

1

0

1

1

1

0

0

1

0

0

1

0

0

1

0

1

1

0

1

1

0

1

1

1

0

1

1

1

1

1

0

1

1

1

1

1

0

1

1

1

Из определения CCNOT-гейта (или Тоффоли-гейта) видно, что выход этого гейта может быть разложен в различные гейты

^c _⊕ ^a _∧ ^{b =}

⎧⎨

a _∧ b,дляc=0(AND-гейт)a_⊕ c,дляb=1(XOR-гейт)_(6.19)

c,дляa=b=1(NOT-гейт)a,дляb=1,c=0(FANOUT-гейт)

Тоестьданныйгейтявляетсяуниверсальным,посколькуонвыполняетAND,XOR,NOTиFANOUT,взависимостиоттого,чтоимеетсянавходе.

Комбинируя обратимые логические элементы можно составить любую логическую схему и построить универсальный компьютер. Например, используя последовательность CCNOT и CNOT можно составить полусумматор (HA) рис. 6.7.

рис. 6.7.

Полныйсумматор(FA),которыйиспользуетпереносc(отпредыдущегосуммирования)искладываетегосдвумябитами(линиями)aиb,акрометого,содержитдополнительнуюdсравнымнулюбитомнавхадеможнопостроитьнаосновечетырехгейтов(рис.6.8.)

рис. 6.8.

Помимо полной суммы трех битов a _⊕ b _⊕ cпомодулю2ипереносабитавполномсумматоре(рис.6.8.)присутствуютещедвасообщенияналинияхaиb.Приэтомaa,

→

b _→ s� = a _⊕ b–промежуточнаясумма.Этообстоятельствоявляетсятипичнымдляорганизациилогикивычисленийнаобратимыхгейтах.Каквидно,навыходеполучаетсянетолькото,чтотребовалосьполучить(Sumипереносбита),ноиопределенноеколичествопромежуточнойинформации,которуюпринятоназывать"мусором".Наличиемусоравтакихцепяхявляетсяпроблемой,таккакразрастаниецепейдомиллионовгейтовозначаетнеобходимостьхраненияогромногоколичестваненужнойинформацииинеэффективноеиспользованиетехнологическихэлементовкомпьютера.Поэтомуприорганизациипроцессавычислениянаобратимыхэлементахнеобходимоещерешатьзадачуборьбысмусором.Вконкретномслучае,представленномнарис.6.8.,мусорможетбытьсведенвточностиктому,чтоимеетсянавыходе,есликблокуFAдобавитьдополнительноCNOTнадвеверхниелинии.

Действительно, если a =0, то s� = a _⊕ b = b и в соответствии с определением гейта CNOT (т.к. линия a не активизирована) b^�� = b. Во втором возможном случае a =1, s� =1 _⊕ b. При этом:

1, если b =0

s� = (6.20)

0, если b =1.

В силу того, что линия a =1 (активизирована), результат действия гейта CNOT на линии b _≡ s� будет равен:

_{b�� =} NOTs�=0,еслиb=0_{= b. (6.21)}

NOTs�=1,еслиb=1

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

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

Ранее (формула (6.17) и обратимость гейта CNOT) было показано, что гейт FANOUT является обратимым. Очевидно, что гейт FANOUT не разрушает информацию, поэтому возможна его обратимость.

ТеперьрассмотримоперациюERASE,которая,каккажется,требуетсядляпериодической"очистки"(обнуления)памятикомпьютера.Интересно,чтоодинтипстиранияможетбытьосуществленобратимымобразом.Действительно,еслиестьпродублированнаякопиянекоторогобита,томожностеретьдобавочнуюкопию(иликопию)путемоперацииобратнойFANOUT-гейту.

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

Действительно,вычислениепроизвольнойфункцииf(a)можетбытьвоспроизведеновзаимнооднозначнымсоответствиемсееагрументомврезультатесохранениякопиивходныхданныхa:

f:a(a,f(a))(6.22)

→

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

f:a(a,j(a),f(a)),(6.23)

→

гдеj(a)–большоечислодополнительныхмусорныхбитов.

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

Напервомшагевычисляетсяfиприэтомполучаютсямусорныебитыj(a)иискомыйрезультат (6.23).

НавторомшагеприменяетсяFANOUT-гейтдлядублированиявыходногорезультата

f(a)вfc(a)

FANOUT:(a,j(a),f(a))→(a,j(a),f(a),fc(a)).

(6.24)

3. На третьем этапе выполняется операция обратная вычислению функции f

f−1:(a,j(a),f(a),f(a))→(a,fc(a)).

(6.25)

Обратнаяоперацияудаляеткакмусорныебиты,такибитыпервоначальновычисленноговыходногорезультатаf(a),нетрогаяприэтомкопиювыходногорезультатаfc(a).

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

.