Arvi the Hacker (Арви Хэкер) (arvi) wrote,
Arvi the Hacker (Арви Хэкер)
arvi

Category:

Трёхзначная логика.

( продолжение )

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

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

© Евг.Евтушенко

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

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

5. Двуместные операции.


   Операции с двумя переменными называются двуместными («бинарными»). Если учитывать третье состояние, а в трёхзначной логике оно учитывается, то всего существует 19683 двуместных операций. Десятки тысяч операций сложно разобрать в одной таблице, как мы поступили с унарными операциями в третьем параграфе. Чтобы учесть их все, нужны математические методы, выходящие за рамки этого обзора.
   Поэтому о двуместных операциях куда меньше информации в Сети. Основной материал этого постинга взят из второй главы («k-значная логика») книжки С.В. Яблонского «Введение в дискретную математику», по которой нам и преподавали матлогику на мехмате МГУ. Его применение к трёхзначной логике учитывает ту информацию о советской машине «Сетунь», которую мне передал slobin из школы акад. Брусенцова, разработчика этой машины.
   Хэкерство не сводится к науке, т.к. подводит к дзэнскому просветлению, а не исходит из католической схоластики. Но изучение компьютерных наук, как мы видим, способно помочь на пути хэкера.
   Интерпретация трёхзначной логики, помогающая освоить её побыстрее, отражает непростое время «цифровой оккупации» страны, в которой мы все живём. За эпиграф отдельное спасибо magenta_13.

5.1. Конъюнкция и дизъюнкция.


   Программисты зарубежных двоичных машин должны помнить простенькие логические операции И, ИЛИ (AND, OR). Математики их называют конъюнкцией x&y (в некоторых работах Брусенцова встречается запись x∧y, как дань уважения Лукашевичу) и дизъюнкцией x∨y соответственно. В трёхзначной логике (если использовать префиксную нотацию) их проще запомнить, как операции min(x,y) и max(x,y). Любая трёхзначная функция (сколько угодно аргументов) может быть довольно легко записана с помощью этих двух операций и операций выбора (S+, S, S-) из прошлого постинга.
   Вот карты Карно («таблицы Пифагора») для этих двух операций. Они коммутативны, поэтому можете искать x и y хоть по горизонтали, хоть по вертикали («переместительный закон»). Результат будет на пересечении:

x&y=
=min(x,y)
-0+
----
0-00
+-0+


x∨y=
=max(x,y)
-0+
--0+
000+
++++


   Если вы научили машину делать отрицание Лукашевича (~x=NOT x), то одна из этих функций избыточна, ведь ~min(x,y)=max(~x,~y). Теперь разберём смысл, интерпретацию этих двух важнейших операций трёхзначной логики. Сразу заметим, что если на входе нет „третьего состоянья“, то эти две функции неотличимы от соответствующих функций профессора Буля.

5.1.1. Логическое И (конъюнкция).


   Операцию A&B=min(A,B) часто называют логическим И (Logical AND). Почему? Представим, что ваш проект зависит от нескольких других. В простейшем случае, от каждого из двух других проектов. Всё получится, если Вася сделает обещанное и у Маши тоже всё получится.
   Пусть A обозначает "у Васи всё получилось", B это "у Маши всё получилось", а C это "у Васи и Маши всё получилось". Оказывается, что C=A&B. Эту формулу легко доказать, ведь состояний всего три и перебрать все можно довольно быстро:
  • Случай, когда и Вася, и Маша справились (оба „+“) понятен. Общий проект получился, результат "логического И" тоже „истина“ („+“). Это единственный случай, когда вы можете твёрдо заявить об успехе.
  • Случай, когда кто-нибудь из них не справился („-“) тоже понятен. Независимо от усердства другого, общий проект тоже не удался („-“).
  • Если среди проектов есть незавершённые („третье состоянье“), но явных провалов нет, тогда статус общего проекта тоже неизвестен („0“).


5.1.2. Логическое ИЛИ (дизъюнкция).


   Вторая операция A∨B=max(A,B) называется логическим ИЛИ (Logical OR). Предположим, что для успеха нашего проекта (C) достаточен успех лишь одного из других. При этом не важно, кто именно добьётся своего — Вася (A) или Маша (B).
   В этом случае C=A∨B. Разберём возможные случаи:
  • Кто-то добился успеха (A=„+“ или B=„+“). Тогда, независимо от статуса другого проекта, мы тоже выиграли (C=„+“).
  • Оба проиграли (A=„-“ и B=„-“ одновременно). Это единственный случай, когда удача не на нашей стороне (C=„-“).
  • Явных успехов нет ни у кого (A≠„+“ и B≠„+“), но на кого-то ещё осталась надежда (A=„0“ или B=„0“). В этом случае наш проект ещё не окончен (C=„0“).


5.2. Алгебра логики.


   Как нам напомнил slobin, трёхзначная логика не является булевым кольцом. У неё свой математический аппарат. Его полезно изучить, ведь это поможет почувствовать трёхзначную логику и смелее в ней оперировать. Все эти законы и свойства легко доказать, перебрав все значения входящих в них переменных.
   Алгебраический подход заключается в том, чтобы определить над множеством {„-“, „0“, „+“} двуместные {&, ∨} и одноместные {', S, ~} операции с помощью законов, а оставшиеся свойства уже выводить из них алгебраически. При этом наборы законов (системы аксиом) могут быть разными. Главное, чтобы из каждого набора можно было вывести все оставшиеся (не включённые в набор) свойства в качестве следствий.

   1. Переместительный закон (законы коммутативности). Как я уже написал, операции a&b и a∨b коммутативны:
a&b = b&a
a∨b = b∨a


   2. Сочетательный закон (законы ассоциативности).
a&(b&c) = (a&b)&c
a∨(b∨c) = (a∨b)∨c


   3. Распределительный закон (законы дистрибутивности). Как и в булевской алгебре, каждая из двух операций &, ∨ дистрибутивна относительно другой (кстати, операция & имеет больший приоритет, чем операция ∨):
a&(b∨c) = a&b ∨ a&c
a ∨ b&c = (a∨b)&(a∨c)


   4. Идемпотентность конъюнкции и дизъюнкции означает, что:
a&a = a
a∨a = a


   5. Закон двойного (и тройного) отрицания. Отрицание Лукашевича ~a и циклическое отрицание a' подчиняются следующим законам:
~~a = a (инволютивность отрицания Лукашевича, то есть обратность самому себе)
a''' = a

   Здесь же можно привести определения двух «крайних» операций выбора. Эти тождества приводились в качестве свойств, когда мы определяли операции выбора с помощью таблиц истинности. Считаем, что циклическое отрицание a' обладает большим приоритетом, чем операции выбора:
S-a = Sa'
S+a = Sa''


   6. Свойства констант в общем-то традиционны:
a & „+“ = a
a & „-“ = „-“
a ∨ „+“ = „+“
a ∨ „-“ = a
~ „-“ = „+“
~ „+“ = „-“


   К ним добавлены свойства циклического отрицания констант, фактически его буквальное определение:
„-“ ' = „0“
„0“ ' = „+“
„+“ ' = „-“


   Также появились два новых свойства, связанных с неизменностью третьего состоянья при отрицании Лукашевича:
~ „0“ = „0“
~(a & „0“) = ~a ∨ „0“


   7. Законы де Моргана (законы дуальности) используют отрицание Лукашевича. Один из них я уже упомянул:
~(a&b) = ~a ∨ ~b
~(a∨b) = ~a & ~b


   8. Законы поглощения:
a & (a∨b) = a
a ∨ a&b = a


   9. Антиизотропность отрицания Лукашевича использует тот факт, что логические значения строго упорядочены („-“ < „0“ < „+“):
a≤b ⇒ ~a ≥ ~b

   Более того, если пользоваться операцией сравнения (см. ниже), то справедливо более сильное утверждение:
a mag b ⇔ ~b mag ~a

   Впрочем, из-за наличия меры (состоянья „0“) некоторые законы (например законы дополнительности конъюнкции и дизъюнкции) оказываются неверными. Их место занимают другие законы. Кстати, справедливость некоторых из этих законов ставилась под сомненье целыми математическими школами.

   10. Закон несовместности состояний пришёл на смену закону противоречия, который в трёхзначной логике неверен. Высказывание a & ~a не всегда ложно, не всегда „-“. Зато выполняются следующие тождества:
Sa & Sa'' = „-“
Sa' & Sa'' = „-“
Sa' & Sa = „-“


   Эти тождества означают, что a не может принять два состояния одновременно. Их можно записать с помощью операций S- и S+:
Sa & S+a = „-“
S-a & S+a = „-“
S-a & Sa = „-“


   11. Закон полноты состояний сменил неверный закон исключённого третьего. Действительно, высказывание a ∨ ~a не всегда истинно, не всегда „+“. Третье дано, поэтому следующее высказывание истинно (оно снова потребует поправки при увеличении числа состояний, например при переходе в четырёхзначную логику):
Sa' ∨ Sa ∨ Sa'' = „+“, или
S-a ∨ Sa ∨ S+a = „+“

   Иногда этот закон формулируют, как закон исключённого четвёртого:
a ∨ a' ∨ a'' = „+“

   12. Закон трёхчленного склеивания сменил неверный закон склеивания. В троичной логике a&b ∨ a&~b ≠ a и (a∨b) & (a∨~b) ≠ a, зато:
a&Sb' ∨ a&Sb ∨ a&Sb'' = a, или
a&S-b ∨ a&Sb ∨ a&S+b = a

   13. Закон обобщённого трёхчленного склеивания сменил неверный закон обобщённого склеивания (теоремы консенсуса). В троичной логике a&c ∨ b&~c ∨ a&b ≠ a&c ∨ b&~c и (a∨b) & (~a∨c) & (b∨c) ≠ (a∨b) & (~a∨c), зато:
a&Sd' ∨ b&Sd ∨ c&Sd'' ∨ a&b&c = a&Sd' ∨ b&Sd ∨ c&Sd'', или
a&S-d ∨ b&Sd ∨ c&S+d ∨ a&b&c = a&S-d ∨ b&Sd ∨ c&S+d

   14. Трёхчленный закон Блейка-Порецкого сменил неверный закон Блейка-Порецкого. Действительно, a ∨ ~a&b ≠ a∨b и a & (~a∨b) ≠ a&b, зато:
a ∨ Sa'&b ∨ Sa&b = a∨b, или
a ∨ S-a&b ∨ Sa&b = a∨b


5.3. Логическое умножение и сложение по модулю три.


   Удивительно, но в таблице команд машины «Сетунь» не было ни конъюнкции, ни дизъюнкции. Наряду с арифметическими операциями там была единственная «функция 20», поразрядное логическое умножение. Это обычное умножение, знакомое нам с детства:

x∧y=
=x∙y
-0+
-+0-
0000
+-0+

   Оно позволяет сохранить, обнулить или изменить знак тритов. Если к обнулённым тритам прибавить (арифметически) единички или минус единички, мы получим всё разнообразие, нужное программистам. Исходя из этого данная логическая операция и была выбрана Брусенцовым для аппаратной реализации в «Сетуни», ведь он экономил пространство команд.
   Сложение по модулю три напоминает двоичный XOR. Это обычное сложение, только без переноса: в случае переполнения разрядной сетки оно сохраняет лишь младший трит. Как и двоичный XOR, сложение по модулю три либо оставляет трит неизменным, либо изменяет его (производит операции INC/DEC, в зависимости от знака соответствующего трита).

x⊕y-0+
-+-0
0-0+
+0+-

   Эти две важные и полезные операции не найти у Яблонского. Вместо них русский учёный рассматривал аналогичные операции для троичной системы с базисом (0,1,2) — более сложной в аппаратной реализации, да и не нужной никому.

5.4. Функция Вебба, как надежда русской революции.


   Люди, всерьёз интересовавшиеся логикой профессора Буля, помнят штрих Шеффера и стрелку Пирса. Есть ли здесь подобные двуместные операции? Оказывается, есть. Двуместная операция, которую математики называют функцией Вебба (x|y=V3(x,y)=INC max(x,y)), позволяет реализовать все другие трёхзначные функции. Вы не ослышались, именно все. И одноместные (например INC x=V3(x,x)), и двуместные (например x∨y=INC INC V3(x,y)). Разумеется, её таблица истинности напоминает дизъюнкцию:

x|y-0+
-0+-
0++-
+---

   Вполне возможно, что именно логическим элементам, реализующим функцию Вебба, придётся сыграть роль троичных ЛА3'их (элементов И-НЕ). И от качества реализации этой функции, количества транзисторов будет зависеть эффективность будущих отечественных троичных процессоров.
   Впрочем, функция DEC max(x,y) (а возможно, что и INC min(x,y), DEC min(x,y)) ничем не хуже. Вопрос лишь в том, какую из них мы сможем реализовать наиболее эффективно.

6. Практические нужды.


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

6.1. Функции, важные для инженеров.


   Есть несколько функций, которые Брусенцов счёл полезными при проектировании троичных устройств. Во-первых, это одноместные арифметические функции отделения двоичных компонент α-, α° и α+, которые легко получаются из логических операций выбора:

αα-α°α+
-+00
00+0
+00+

   Во-вторых, это пороговое сложение x+y, которое в отличии от сложения по модулю 3 при переполнении выдаёт самое большое (или самое маленькое) значение, умещающееся в трите. Оно не является ассоциативным, но, по свидетельству Брусенцова, существенно проще в аппаратной реализации:

x+y-0+
---0
0-0+
+0++

   Стив Грабб с сайта www.trinary.cc предлагает ещё две одноместные функции, простые в реализации. Это пороговое увеличение (ShiftUp, ↗x) и пороговое уменьшение (ShiftDn, ↘x). Одноместные пороговые операции отличаются от операций модификации тем, что при переполнении трита он не изменяется, а «застывает» на самом большом или самом малом значении. Если INC x = x ⊕ „+“, а DEC x = x ⊕ „-“, то ↗x = x + „+“, а ↘x = x + „-“. Вот их таблицы истинности:

α↗α↘α
-0-
0+-
++0

   Стив Грабб предложил и реализовал ещё три двуместные функции. Во-первых, это исключающий максимум (Exclusive Max) x⇑y. Результат этой забавной функции равен максимуму двух операндов или „-“, если эти операнды совпадают:

x⇑y-0+
--0+
00-+
+++-

   Вторая функция почему-то называется среднее (Mean) x→y и подсчитывает количество среднего (то есть нулей) на входах. Если оба входа равны „0“, то на выходе „+“ (этот случай больше всего «нравится» функции). Если только один вход равен „0“, то и на выходе „0“. Если же на входах нет ни одного „0“, то на выходе „-“:

x→y-0+
--0-
00+0
+-0-

   Последняя из функций, предложенных Стивом Граббом называется сравнение (Magnitude) x≡y, она сравнивает величины двух аргументов. Значение этой функции „-“, если x<y, „0“ если x=y и „+“ если x>y (порядок аргументов важен — x по горизонтали, y по вертикали):

x≡y-0+
-0++
0-0+
+--0

6.2. Функции, важные для математиков.


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

   Пионером троичной логики был поляк Лукашевич. Наше логическое ИЛИ он обозначал x∧y и называл слабой конъюнкцией, а значком x&y обозначал совсем другую, сильную конъюнкцию, карта Карно которой приведена ниже. Справа приведена импликация Лукашевича x→лy (x по горизонтали), которая важна в модальной логике:

x&лy-0+
----
0--0
+-0+


x→лy-0+
-+0-
0++0
++++


   Свои операции конъюнкции и импликации предложил американец Клини. В его интерпретации третье состоянье означало «неопределено»:

x∧+y-0+
--0-
0000
+-0+


x→+y-0+
-+++
0000
+-0+


   В семействе импликаций также известны интуиционистская импликация Гейтинга (она же импликация Гёделя) x→гy, материальная импликация x→мy = x'∨y и функция следования Брусенцова x→y. Раскрытие смысла каждой из них уведёт повествование в сторону, но их карты Карно могут оказаться полезными:

x→гy-0+
-+--
0++0
++++


x→мy-0+
-+0-
0+00
++++


x→y-0+
-+0-
0000
+00+


   Также логикам важна операция тождества x≡y, которая истинна („+“) если сравниваемые триты равны и ложна („-“) во всех других случаях:

x≡y-0+
-+--
0-+-
+--+


7. Итоги.


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

xyx&yx∨yx∧yx⊕yx|y
----++0
-0-00-+
-+-+-0-
0--00-+
000000+
0+0+0+-
+--+-0-
+00+0+-
+++++--

8. Четвёртое измеренье состоянье.


   Разработчики давно поняли, что логика профессора Буля недостаточна для построения компьютера. Так компьютерная сеть «с общей шиной» (например Ethernet) требует объединения всех входов и выходов сетевых карт. Объединение входов понятно, все считывают с общего кабеля одну и ту же информацию. Но что такое объединение выходов? Если один компьютер захочет вывести „1“, а соседний „0“, то что получится на шине, что будут считывать входы?
   Многие современные схемы используют «третье состоянье» (которое скорее административное, чем логическое) и работают на стыке двоичной и троичной логик. Это состояние называется высокий импеданс («отключено»). В частности, в него переходят Интернет-сайты во время DoS-атак. :-)
   В случае общей шины все выходы должны уметь находиться в этом, третьем состоянии. И только один из них должен выводить на общую шину нолик или единичку, «ложь» или «истину». Аналогично, если мы хотим воспользоваться всеми преимуществами троичной связи, нам придётся прибегать к четвёртому состоянию «высокого импеданса».
   Впрочем, четырёхзначная логика легко сводится к двоичной. Просто операции производятся над двумя битиками сразу, а не над одним. Коренное отличие лишь в том, что четырёхзначные операции над битом способны влиять на «парный» бит. Впрочем, описываемое «четвёртое состояние» тоже будет нести не логическую, а «административную» функцию.

P.S. Ссылки для заинтересовавшихся:


( окончание следует )
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 44 comments