Импликация — Гуманитарный портал

Импликация — это логическая операция, принятая в формализованных языках (см. Язык формализованный) для образования сложных высказываний (формул) из элементарных (простых) высказываний (см. Высказывание) и по смыслу равнозначная нестрогому условию «если…, то…», принятому в естественном языке (см. Язык). Импликация читается: «если A, то B», или «из A следует B»; записывается: A → B (здесь высказывание A называется посылкой высказывания A → B, а высказывание B — его заключением, для записи применяются также стрелки другой формы, но всегда указывающие на соотношение посылка → следствие), другое обозначение импликации: A ⊃ B; другое название импликации: логическое следование (см. Логическое следование), однако между ними есть различие — импликация как логическое выражение может принимать значения «истина» или «ложь», тогда как логическое следование A → B утверждает, что во всех случаях, когда значение A истинно, B также будет истинно. Понятие импликации сформировалось в процессе обособления языка логики и его последующей символизации (см. Логика символическая). Различные подходы к формализации логического следования привели, наряду с классической теорией импликации, к построению различных теорий строгой, сильной, аналитической, интенсиональной, релевантной и некоторых других видов импликации. В естественном языке импликация играет важную роль в рассуждениях и умозаключениях (см. Рассуждение, Умозаключение), так как [при учитывании смыслового содержания высказываний] предполагает причинную связь между посылкой и заключением, и её истинность зависит от смысла этих высказываний. Так, в русском языке распространены следующие выражения импликации: если A, то B; из A следует B; при A будет B; в случае A произойдёт B; B, так как A; B, потому что A; A — достаточное условие для B; B — необходимое условие для A. В математической логике обычно учитывается лишь истинность или ложность высказываний, а не смысловое содержание. Поэтому импликация обычно понимается в соответствии с истинностной таблицей: A B A → B И И И И Л Л Л И И Л Л И В классической логике (см. Логика), формальной логике (см. Логика формальная), языках формальных теорий (см. Формализация) и языках программирования импликация составляет одну из пяти наиболее распространённых логических связок, или логических операций (см. Логические операции), наряду с конъюнкцией (см. Конъюнкция), дизъюнкцией (см. Дизъюнкция), эквиваленцией (см. Эквиваленция) и отрицанием (см. Отрицание).

Высказывания — урок. Информатика, 8 класс.

Алгебра логики помогает нам понять внутреннее устройство компьютера. Ты уже знаешь, что компьютер обрабатывает информацию только в двоичном коде. Логика поможет тебе понять, как взаимодействуют между собой два состояния: \(0\) и \(1\). Процессор компьютера работает за счёт выполнения логических операций, но о них ты узнаешь позже.

Высказывание — это повествовательное предложение, о котором можно сказать, истинно оно или ложно.

Например: 7×8=56, 26>4, «Осенние месяцы: сентябрь, октябрь, ноябрь», «Графический планшет — это устройство ввода информации» — это всё истинные высказывания.

«Земля имеет форму квадрата», «Монитор — это устройство для ввода информации», 3>21, 15−6=10 — это ложные высказывания.

 

Высказываниями не могут быть восклицательные и побудительные предложения, определения, уравнения (т. к. там есть переменные), односложные утверждения — «Он хороший» (не для всех непонятный он может быть хорошим).

 

В алгебре логики высказывания обозначаются латинскими буквами.

 

Для алгебры логики содержание высказывания не играет никакой роли, главным здесь является, истинно это высказывание или ложно.

Если высказывание истинно, то оно равно \(1\). Если ложно, то \(0\).

Например, \(A\) \(=\) «Монитор — это устройство для вывода информации» можно записать как A=1.

 

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

 

Например:

\(A\) \(=\) «Маша поёт в ансамбле»;

\(B\) \(=\) «Маша танцует народные танцы».

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

\(A\) или \(B\) \(=\) «Маша поёт в ансамбле ИЛИ Маша танцует народные танцы»;

\(A\) и \(B\) \(=\) «Маша поёт в ансамбле И Маша танцует народные танцы».

 

Подумай! Какая разница между первым и вторым сложными высказываниями?

Логические операции — урок. Информатика, 8 класс.

В алгебре логики, как и в математике, есть свои обозначения для операций (действий).

 

Рассмотрим основные логические операции.

 

1. Логическое отрицание.

Отрицание (инверсия) — это логическая операция, которая делает ложное высказывание истинным, а истинное — ложным.

Обозначение: НЕ \(A\), not \(A\), ¬A, A¯.

 

Таблица истинности для инверсии.

 

\(A\)	A¯
\(0\)	\(1\)
\(1\)	\(0\)

 

2. Конъюнкция (логическое умножение).

Конъюнкция двух высказываний истинна тогда и только тогда, когда оба высказывания истинны.

Обозначение: И, and, &, \(×\), ∧.

 

Таблица истинности.

 

\(A\)	\(B\)	A∧B
\(0\)	\(0\)	\(0\)
\(0\)	\(1\)	\(0\)
\(1\)	\(0\)	\(0\)
\(1\)	\(1\)	\(1\)

 

3. Дизъюнкция (логическое сложение).

Дизъюнкция двух высказываний ложна тогда и только тогда, когда оба высказывания ложны.

Обозначение: ИЛИ, or, \(+\), ∨.

 

Таблица истинности.

 

\(A\)	\(B\)	A∨B
\(0\)	\(0\)	\(0\)
\(0\)	\(1\)	\(1\)
\(1\)	\(0\)	\(1\)
\(1\)	\(1\)	\(1\)

 

Приоритет выполнения логических операций:

1. действия в скобках;
2. инверсия;
3. конъюнкция;
4. дизъюнкция.

Математика и логика — Математическая составляющая

Математика и логика Поделиться    

Лев Дмитриевич Беклемишев

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

тривиума (грамматика, риторика, логика/диалектика) — базового уровня образования; математические же предметы (арифметика, геометрия, астрономия и музыка) составляли следующий, более продвинутый, уровень, называемый квадривиум. (От слова «тривиум» происходит одно из любимых математиками выражений «тривиально».) Предметы тривиума понимались как науки о том, как правильно, без ошибок, писать, говорить и, соответственно, рассуждать.

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

От Аристотеля к Булю. Основы учения о правильных рассуждениях заложил Аристотель. Он заметил, что корректные умозаключения следуют определённым элементарным схемам, называемым

силлогизмами, и перечислил ряд таких схем. (Классический пример силлогизма: «Все люди смертны. Сократ — человек. Следовательно, Сократ смертен».) Учение о силлогизмах в свою очередь опиралось на глубокий анализ понятий и их соединения в высказывания.

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

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

Аналогия между рассуждениями и вычислениями несколько глубже, чем кажется на первый взгляд. Возникновение логики как математической науки было связано с работами британских учёных Джорджа Буля и Августа де Моргана, которые обнаружили, что с логическими высказываниями можно оперировать как с алгебраическими выражениями. Например, если сложение читать как логическую связку «или», умножение как «и», а равенство как «равносильно», то для любых высказываний $a$, $b$ выполняются законы

$$ a+b=b+a,\quad a\cdot(b+c)=a\cdot b+a\cdot c, $$

как и многие другие привычные нам законы арифметики. Но, помимо этого, в алгебре высказываний выполняется и кое‐что непривычное, например всегда
$$ a+a=a\quad \hbox{и}\quad a+(b\cdot c)=(a+b)\cdot (a+c). $$

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

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

Математизация логики и аксиоматизация математики. Движущей причиной процесса математизации логики был назревший в самой математике на рубеже XIX—XX веков кризис оснований. С одной стороны, во второй половине XIX века в математике получил распространение удобный язык теории множеств, созданной Георгом Кантором. Математики стали уверенно использовать в своих рассуждениях конструкции с бесконечными множествами. Математика, вооружённая теорией множеств, шла от успеха к успеху.

С другой стороны, в самой теории множеств Кантора обнаружились парадоксы, которые указывали на то, что с этой теорией не всё в порядке на самом базовом уровне. Простейший парадокс такого рода, в фольклорном варианте известный как парадокс брадобрея, был придуман Бертраном Расселом: рассмотрим множество $R$ всех тех множеств, которые не содержат сами себя в качестве элемента. Тогда $R\in R$ если и только если $R\notin R$, противоречие.

Такое положение дел заставило многих выдающихся математиков и философов той эпохи (Пеано, Фреге, Рассел, Гильберт, Пуанкаре, Брауэр, Вейль и др.) задуматься об основаниях математики. Их волновали такие фундаментальные вопросы как:

• Что означает доказать математическую теорему? Какие средства при этом законно использовать?
• Что значит выразить то или иное математическое понятие или утверждение на том или ином языке?
• Когда мы говорим об истинности и о доказуемости какого‐либо математического утверждения, имеется ли в виду одно и то же?

Параллельно в математике стали укореняться новые стандарты строгости. Основные области математики — анализ, алгебра, геометрия — были поставлены на аксиоматическую основу. Великий математик Давид Гильберт (1862—1943) был ярким сторонником и пропагандистом аксиоматического метода. Под его влиянием была построена и общепринятая в наше время система аксиом теории множеств, свободная от очевидных парадоксов. Эту аксиоматику предложил в 1908 году Э. Цермело и в дальнейшем дополнили Дж. фон Нейман и А. Френкель. Но где же настоящая гарантия, что полученная система не содержит противоречия? Каким образом это можно установить?

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

Формальные языки. С современной точки зрения область интересов математической логики значительно шире, чем наука о правильных рассуждениях; её можно приблизительно описать, с оговорками и уточнениями, как построение и исследование формальных языков и систем математическими методами. Заметим, что если в этом определении отбросить слово «формальных», то вместо логики мы получим, по существу, математическую лингвистику — что указывает на определённое родство между этими двумя дисциплинами. Ключевое же отличие математической логики от логики в широком смысле слова — это именно использование математических методов, применяемых к точным формальным моделям.

Математическая логика по предмету сво-
ему есть логика, а по методу — математика.(П. С. Порецкий, 1884 год, Казань.)

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

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

Логика предикатов. Разработчики первых формальных языков и систем, как правило, не думали о том, что эти системы могут быть реально использованы в вычислительных устройствах. (Исключением, видимо, можно считать великого учёного Готфрида Вильгельма Лейбница (1646—1716), который почти за два века до Буля предвосхитил многие идеи математической логики, включая идею формализации языка математики, и даже построил механический арифмометр.)

Первые формальные языки и системы возникли как результат выделения фрагмента естественного языка, достаточного для передачи формулировок математических утверждений и их анализа. Процесс выработки основных категорий этого языка был продолжительным и шёл параллельно с выработкой некоторых ставших в наше время стандартными математических обозначений. (Одним из важных понятий, введённых в это время, стало понятие квантора, сформировавшееся в работах Г. Фреге и Ч. Пирса. Кванторы существования $\exists$ и всеобщности $\forall$ заменяют языковые конструкции «для некоторого» и «для всех». Первое из этих обозначений введено Дж. Пеано в 1897 году, второе — по аналогии — Г. Генценом в 1935 году, однако общеупотребительными эти обозначения стали лишь под влиянием Бурбаки во второй половине XX века.) Этот процесс в основном завершился в 1920‐х годах, когда в качестве стандартного класса языков, предназначенных для формализации и анализа математических утверждений, стал рассматриваться язык логики предикатов (первого порядка).

Предикатом на множестве $M$ мы называем высказывание, зависящее от $n$ параметров из этого множества (например, «натуральное число $x$ чётно», «точки $x$, $y$ и $z$ плоскости лежат на одной прямой»). Как только фиксированы значения параметров, предикат принимает логическое значение ложь или истина. Таким образом, с формальной точки зрения предикат представляет собой функцию от $n$ аргументов из множества $M$ в $\{0,1\}$.

Не вдаваясь в технические подробности, можно приблизительно описать высказывания логики предикатов как такие, которые можно сформулировать (предполагая заранее заданными обозначения некоторых базовых предикатов) с помощью конструкций $\land$ «и», $\lor$ «или», $\neg$ «не», $\to$ «влечёт» и уже упомянутых кванторов. Например, текст $\forall{x} \exists{y} (y>x \land P(y))$ выражает неограниченность множества простых чисел, если договориться, что переменные пробегают множество натуральных чисел, «$>$» означает «больше», а $P(y)$ выражает простоту числа $y$. Эти договорённости составляют часть того, что мы назвали семантикой языка логики предикатов.

Удивительный факт, подтверждаемый всей существующей математической практикой, состоит в том, что выразительных средств языка логики предикатов — на первый взгляд очень скромных — достаточно для формулировки любых известных математических результатов. При этом может быть использовано всего лишь одно базовое понятие — предикат принадлежности $x\in y$ «множество $x$ есть элемент множества $y$». (В картине мира аксиоматической теории множеств все объекты, обозначаемые переменными, являются множествами.)

Доказуемость и вычислимость. Выразить в данном языке то или иное осмысленное утверждение — совсем не то же самое, что суметь его доказать. Следующий уровень языка логики предикатов состоит в описании таких текстов, которые следует признать корректными доказательствами. Традиционно этот уровень называется в математической логике исчислением предикатов. Формальное доказательство (в формате, который принято называть гильбертовским, но который существовал и до работ Давида Гильберта) представляет собой конечную цепочку высказываний логики предикатов, каждое из которых либо является аксиомой, либо получается из предшествующих высказываний по одному из постулируемых правил. Минимальный стандартный набор таких правил содержит лишь два: правило, позволяющее из высказываний $A$ и $A\to B$ вывести $B$, и правило, позволяющее из высказывания $A$ вывести $\forall x A$. (Если высказывание $A$ содержит параметр $x$, то формальное доказательство $A$ обосновывает его истинность при всех возможных значениях параметра.)

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

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

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

Одним из первых, кто это понял, был Алан Тьюринг, давший точное определение и наиболее убедительный анализ понятия вычислимой функции в 1936 году. Другими учёными, которые наряду с Тьюрингом пришли к тем же идеям приблизительно в то же время, были Алонзо Чёрч и Эмиль Пост. Этими и другими исследователями в 1930‐х годах были созданы начала теории алгоритмов, которая стала основой понимания работы и построения вычислительных устройств в 40‐е и 50‐е годы. В частности, идея универсальной машины Тьюринга была в дальнейшем технически реализована в компьютерной архитектуре «по фон Нейману», в соответствии с которой программа хранится в памяти устройства и может быть модифицирована в ходе его работы. На основе этой идеи построены все операционные системы.

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

Если доказать существование того или иного алгоритма можно, предъявив его явно, то для того, чтобы утверждать, что такого алгоритма не существует, необходимо располагать точным математическим описанием того класса задач, которые допускают алгоритмическое решение. Ответ на этот вопрос потребовал разработки формальных языков описания алгоритмов ещё до появления компьютеров. Причём, поскольку цель такой разработки была более теоретическая, чем практическая, исследователи стремились к формулировке наиболее простых для описания и в то же время универсальных вычислительных моделей. Первыми такими моделями были рекурсивные функции Гёделя—Эрбрана, лямбда‐исчисление Чёрча и машины Тьюринга.

Гёдель, хотя и был первым, кто фактически сформулировал универсальный язык программирования, не считал, что найденное им (и французским логиком Эрбраном) понятие является универсальным в смысле способности запрограммировать любой алгоритм. Первым, кто высказал тезис об универсальности своей вычислительной модели, был Алонзо Чёрч. Он также предъявил доказательство невозможности решения Entscheidungsproblem в рамках этой модели. Исчисление Чёрча было очень простым по форме, но больше напоминало формальное логическое исчисление, чем реальную вычислительную машину. Машины Тьюринга в этом смысле были ближе к будущей реальности, и поверить в тезис Тьюринга о том, что любая задача, имеющая алгоритмическое решение, может быть решена на машине Тьюринга, было намного легче, чем в аналогичный тезис Чёрча (известно, что именно работа Тьюринга смогла убедить Гёделя в справедливости этого тезиса). Тьюринг также показал, что его машины эквивалентны лямбда‐исчислению в смысле вычислительных возможностей, что стало косвенным свидетельством справедливости тезиса Чёрча—Тьюринга, как его теперь принято называть.

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

Что касается лямбда‐исчисления, то оно долгое время пребывало на обочине математической логики, будучи вытеснено из теории алгоритмов более удобными и интуитивными моделями. Однако во второй половине XX века лямбда‐исчисление и системы на его основе нашли серьёзные практические применения. Лямбда‐исчисление Чёрча стало прообразом так называемых функциональных языков программирования (таких как современный язык Haskell), которые имеют ряд преимуществ по сравнению с традиционными императивными языками и в настоящее время очень активно развиваются.

Алгоритмически неразрешимые проблемы в математике. Вслед за Entscheidungsproblem с точки зрения теории алгоритмов были проанализированы и многие другие математические проблемы, поставленные как вопросы о построении того или иного алгоритма. Некоторые из таких трудных проблем, остававшихся открытыми десятилетиями, оказались алгоритмически неразрешимыми задачами.

Среди такого рода вопросов наиболее известна 10‐я проблема Гильберта о распознавании разрешимости диофантовых уравнений. Диофантово уравнение — это уравнение вида $P(x_1,…,x_n)=0$, где $P$ — многочлен с целыми коэффициентами от переменных $x_1$, …, $x_n$. Требуется узнать по заданному многочлену $P$, существуют ли целые числа $x_1$, …, $x_n$, удовлетворяющие такому уравнению.

Вопрос Гильберта о построении общего алгоритма, работающего для всех диофантовых уравнений, с самого начала выглядел безнадёжным. С появлением теории алгоритмов исследователи стали предпринимать усилия в попытке доказать неразрешимость этой задачи. Промежуточные результаты в этом направлении получили американские логики Дж. Робинсон, М. Дэвис и Х. Патнэм, на их основе окончательное решение задачи было получено лишь в 1970 году ленинградским математиком Ю. В. Матиясевичем.

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

Теоремы Гёделя и недоказуемые утверждения. Ещё одним открытием, сделанным гениальным австрийским логиком Куртом Гёделем в 1931 году, было явление непополняемости аксиоматических систем. Знаменитые теоремы Гёделя о неполноте не только оказали большое влияние на развитие математической логики и дали толчок к созданию теории алгоритмов, но и стали общекультурным явлением, затронувшим даже творчество писателей и художников. Гёдель был назван в числе ста наиболее влиятельных личностей XX века по версии журнала Тайм. Однако известность теорем Гёделя приводит и к тому, что часто они интерпретируются в слишком расширительном, метафорическом смысле.

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

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

Целые числа создал Господь Бог,
всё остальное — дело рук человеческих. (Леопольд Кронекер, 1886 год, Берлин.)

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

Гёдель показал, что при выполнении этих требований любая система аксиом либо противоречива, либо неполна. Более того, для любой непротиворечивой системы можно явно указать предложение, касающееся арифметики натуральных чисел, которое нельзя ни доказать, ни опровергнуть в данной системе (такие утверждения принято называть независимыми от данной системы аксиом). В частности, это означает, что систему аксиом формальной арифметики нельзя никаким непротиворечивым образом «пополнить»: всегда найдутся независимые от неё арифметические утверждения. Это составляет содержание так называемой первой теоремы Гёделя.

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

Теоремы Гёделя позволили построить первые примеры независимых утверждений для сильных систем аксиом, таких как арифметика или даже теория множеств. После работ Гёделя такие примеры были обнаружены среди открытых проблем в различных областях математики. Одной из самых знаменитых открытых проблем в математике была континуум‐гипотеза Кантора, в соответствии с которой всякое бесконечное подмножество множества вещественных чисел либо счётно (равномощно множеству натуральных чисел), либо континуально (равномощно множеству вещественных чисел). В 1938 году Гёдель сумел доказать, что эту гипотезу невозможно опровергнуть в теории множеств, а в 1961 году американский математик Пол Коэн установил её недоказуемость.

Недоказуемые утверждения теоретико‐множественной природы впоследствии были обнаружены в самых разных частях математики — в анализе, алгебре, топологии и др. Сравнительно недавно, в конце 1970‐х годов, были найдены первые простые примеры утверждений из области конечной комбинаторики, независимые от аксиом формальной арифметики и даже от более сильных аксиоматических систем. Принципиальная разница с примерами типа континуум-гипотезы состоит в том, что комбинаторные примеры относятся к конечным и совершенно элементарным объектам, и их можно легко объяснить школьнику. Исследования в направлении поиска естественных примеров независимых утверждений активно ведутся и в наши дни.

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

Область математики, которая испытала на себе сильное влияние логических методов — это абстрактная алгебра. Соответствующее направление математической логики — теория моделей — возникло в 1940‐х годах в работах А. И. Мальцева в России и А. Тарского и А. Робинсона в США с прицелом на приложения в алгебре. Первые такие приложения были найдены в 1941 году А. И. Мальцевым, который осмыслил доказанную им (а ранее в более слабой форме Гёделем) теорему о компактности для логики предикатов как общий метод получения локальных теорем в алгебре. Оказалось, что методы универсальной алгебры и методы теории моделей весьма близки и понимание взаимосвязей обогатило обе дисциплины. Некоторые конструкции, впервые найденные в математической логике, стали стандартными в алгебре и анализе, например так называемая конструкция ультрапроизведения, придуманная польским логиком Е. Лосем.

Одним из ярких достижений теории моделей 1960‐х годов стало создание нестандартного анализа Абрахамом Робинсоном. Он описал логическую конструкцию, которая позволила непротиворечиво рассматривать пополнение множества вещественных чисел бесконечно малыми и бесконечно большими числами. С помощью этой конструкции стало возможным дать объяснение исходной интуиции лейбницевских «бесконечно малых» и дать технически простое и интуитивное построение основных результатов математического анализа.n$ при $n>2$).

Методы теории доказательств — области математической логики, изучающей формальную доказуемость — также находят применения в «обычной» математике. Одним из успешных современных направлений является proof mining, извлечение конструктивных оценок из априори неконструктивных математических доказательств. Так называемые функциональные интерпретации, первоначально разработанные для анализа формальных систем, оказалось возможным применить и к конкретным содержательным математическим результатам (например, из области вещественного анализа, где интересен вопрос о скорости сходимости того или иного процесса к неподвижной точке и требуется явная оценка этой скорости). Результаты, полученные логическими методами, часто дают совершенно неочевидные усиления исходных теорем.

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

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

В 1960‐х годах американский учёный T. Кодд понял, что самый обычный язык логики предикатов очень удобен для обеих целей, поскольку позволяет эффективно осуществлять поиск по запросу. Эффективность обеспечивается с помощью аппарата реляционной алгебры — языка операций над отношениями, разработанного до этого в математической логике (в школе Альфреда Тарского) как алгебраический эквивалент языка логики предикатов. Идея Кодда о том, что запросы на языке реляционной алгебры допускают эффективный поиск, была первоначальным стимулом в разработке реляционных баз данных и общеупотребительных в настоящее время языков запросов, таких как SQL. С тех пор теория баз данных и логических языков успешно развиваются рука об руку.

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

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

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

Альтернативный подход, называемый theorem proving, состоит в том, чтобы сопоставить программе логическую формулу, выражающую её корректность, и искать формальное доказательство этой формулы — например, в исчислении предикатов. Этот подход на данный момент не так распространён на практике, как model checking, но продолжает развиваться. Успешность этого метода во многом зависит от эффективности работы пруверов — программ автоматического поиска формальных доказательств. Разработка такого рода систем активно ведётся в наши дни.

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

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

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

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

В последние годы функциональные языки занимают всё более важную нишу среди употребительных языков программирования и применяются в тех областях, где важно иметь надёжные программы, например, в банковской сфере. По существу, первым функциональным языком программирования было лямбда‐исчисление, придуманное Чёрчем как простейшая универсальная вычислительная модель. Идеи лямбда‐исчисления были затем воплощены в одном из первых действующих функциональных языков — языке LISP, а также во многих более современных языках вплоть до Ocaml и Haskell.

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

Формальные языки с типами (в отличие от бестиповых языков, в которых все переменные имеют один и тот же тип) впервые возникли в фундаментальном труде Б. Рассела и А. Уайтхеда «Основания математики», целью которого было построение математики на основе непротиворечивой системы аксиом теории множеств. В математике эта система, однако, не прижилась и была заменена более простой бестиповой теорией множеств Цермело—Френкеля с аксиомой выбора.

В 1950‐е годы в логике было обнаружено, что в достаточно развитых системах на базе лямбда‐исчисления с типами последние ведут себя в точности как логические высказывания (языка интуиционистской логики), а функциональные программы — как формальные доказательства этих высказываний. Это явление, описанное здесь, разумеется, очень приблизительно, получило название соответствия Карри—Говарда. Через несколько десятков лет оно послужило основой для создания функциональных языков, в которых возможно написание программ с одновременной верификацией их кода. Наиболее известными языками такого рода являются Coq и Agda, созданные для формализации математических доказательств. В частности, именно на языке Coq удалось построить формальное доказательство гипотезы четырёх красок и ряда других трудных математических результатов. Эти же языки начинают применяться и для задач верификации программ, описанных в предыдущем пункте.

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

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

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

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

Хотя сам Брауэр настаивал на неформальном характере своей философии математики — отсюда её название «интуиционизм» в противоположность гильбертовскому «формализму» — к началу 1930‐х годов возникла потребность в уточнении совокупности логических принципов, приемлемых с интуиционистской точки зрения. Решение этой задачи было дано учеником Брауэра А. Гейтингом, который сформулировал общепринятую в настоящее время интуиционистскую логику предикатов, опираясь на предшествовавшую работу А. Н. Колмогорова. Парадоксально, но в результате интуиционизм был также поставлен на прочную формальную основу.

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

С другой стороны, интуиционистская логика часто возникает в различных приложениях в компьютерных науках. Это не случайно, поскольку интуиционистская логика теснее связана с понятием вычисления, чем логика классическая. Одним из важнейших проявлений этой связи является уже упомянутое соответствие Карри—Говарда.

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

Модальная логика. Другим классом логик, обогащающих классическую новыми выразительными возможностями, являются так называемые модальные логики. Язык модальной логики, наряду с обычными связками, содержит новую одноместную логическую связку $ □\, $. Высказывание $□\, A$ в разных контекстах может пониматься совершенно по‐разному, что приводит к разным постулируемым принципам, т. е. разным модальным логикам. Стандартные логические связки, такие как импликация или отрицание, как правило, сохраняют в модальной логике классическую интерпретацию. (Разумеется, могут рассматриваться модальные логики и над другими логиками, например над интуиционистской, однако такие системы в целом сложнее и потому менее распространены.)

Исторически первым, идущим ещё от Аристотеля, прочтением формулы $□\, A$ было высказывание «$A$ необходимо». (Здесь мы говорим о языковой конструкции, присутствующей в нашем естественном языке, а не о каком‐либо математическом понимании того, что значит «необходимо».) Двойственное высказывание «не $A$ не является необходимым» обычно отождествляется с высказыванием «$A$ возможно» и обозначается $◇\, A$.

Перечислим некоторые известные интерпретации модальности, приводящие к интересным и полезным семействам логик.

Логика доказуемости: $□\, A$ означает «$A$ доказуемо» в данной аксиоматической теории, например в теории множеств. При этом высказывания понимаются как высказывания в языке теории множеств, каковым можно считать и само высказывание о доказуемости утверждения $A$. Эта логика интересна тем, что даёт точную математическую семантику модальности и применяется для исследования обычных классических аксиоматических теорий.

Временная логика, описывающая развитие некоторого процесса во времени: $□\, A$ означает «всегда в будущем будет верно $A$». Различные модели течения времени — непрерывное, дискретное или даже ветвящееся — приводят к разным временным логикам. Временные логики, применяемые на практике для верификации программ, используют и некоторые дополнительные связки, например двухместную связку, выражающую «$A$ имеет место до тех пор, пока $B$».

Эпистемическая логика, описывающая знания и обмен информации между несколькими агентами: $□\,_x A$ означает «агенту $x$ известно $A$» (в этой логике, как правило, описываются знания нескольких агентов $x$, $y$, … и каждому из них соответствует своя модальность $□\,_x$, $□\,_y$, …). Эпистемическая логика является частью (формальной) эпистемологии — обширного и важного раздела философии, занимающегося исследованием таких понятий, как знание и вера, того как знание возникает, как оно связано с понятием доказательства (обоснования). Формализм эпистемической логики позволяет построить модели различных аспектов этих явлений и использовать их для анализа тех или иных теоретических положений.

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

Деонтическая логика формализует модальности типа долженствования, например $□\, A$ можно понимать как «$A$ требуется» или «$A$ обязательно» (двойственную модальность можно понимать как «$A$ разрешено»). Такие логики впервые стали рассматриваться в философии и теории права для формализации и анализа различных аспектов правовых систем.

Многозначная логика и нечёткая логика. Многозначные логики возникают, если допускаются другие истинностные значения, помимо классических истины 1 и лжи 0. Например, можно рассматривать промежуточное значение 1/2 и интерпретировать его как «неизвестно». Следующий шаг требует определения того, каким образом вычисляются значения логических связок, и конкретное решение по этому поводу может привести к различным логикам.

Если пойти дальше по пути многозначности, то естественно возникает идея о том, что истинностным значением высказывания может быть любое вещественное число в интервале $[0,1]$ (например, это число может выражать степень нашей уверенности в справедливости высказывания). Такие логики часто называют «нечёткими» (fuzzy), поскольку предикаты в такой системе могут выглядеть как размытые, не имеющие чётких границ. Например, высказывание о том, что видимый цвет является красным, не является чётким в силу неопределённости самого понятия «красный».

Нечёткие логики призваны формализовать рассуждения в условиях неопределённости или неточности информации. Подлинным «отцом» нечёткой логики и теории нечётких множеств был Л. Заде. Он увидел потенциал этой логики для различных инженерных применений, например в такой области, как экспертные системы или теория управления, и сделал очень много для её популяризации.

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

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

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

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

Грамматики Хомского и семантика Монтегю. Одной из теорий, соединивших в себе сразу несколько аспектов неклассических логик — кванторы, предикаты, модальности, модели Крипке и лямбда‐абстракцию — является семантика Монтегю. Эта теория, предложенная американским логиком Р. Монтегю в начале 1970‐х годов, представляет собой попытку применить идеи математической логики к трудной задаче описания семантики естественного языка. Она, по существу, положила начало целому направлению в математической лингвистике — формальной семантике. Ранее работы Н. Хомского, создавшего теорию формальных грамматик, произвели революцию в понимании синтаксиса естественных языков. Применения математической логики в лингвистике, из которых мы вскользь упомянули лишь два важных направления, безусловно заслуживают отдельного разговора.

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

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

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

Открытое образование — Математическая логика

Эдсгеру Дейкстре приписывают высказывание: «наука о вычислимости изучает компьютеры не в большей мере, чем астрономия изучает телескопы». Смысл этой фразы в том, что конкретный компьютер или конкретный язык программирования – только инструмент познания общих закономерностей, справедливых для всех вычислений. Основы этой науки заложены Тьюрингом, Гёделем, Чёрчем, Клини, Постом и другими математиками в 1930-х годах, когда вычислительных машин в современном понимании ещё не было. При этом базовые предположения в полной мере выполняются для современных компьютеров и, наверняка, будут верны для всех будущих, в том числе квантовых.

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

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

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

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

В конце – итоговая проверочная работа. Студенты, которые набрали достаточное количество баллов, смогут получить сертификат.

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

Какая разница между «логикой» и «логистикой» — Российская газета

Честно говоря, отец имел в виду «логику». Он хотел сказать, что у его отпрыска… м-м… странная ЛОГИКА. Он думает, что «логика» и «логистика» — одно и то же. А сын, который намерен заниматься именно «логистикой», но никак не логикой, уже знает, что это не так.

Так что же такое «логистика»? И чем она отличается от логики? Попробуем разобраться.

Начнем с хорошо знакомого, то есть с логики. «Логика» — изначально от латинского «logos» (довод, доказательство, разумное основание). Во-первых и в главных, «логика» — это наука о законах мышления и его формах. Кроме того, мы называем «логикой» ход рассуждений и умозаключений. В этом смысле мы можем говорить, например, о женской логике.

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

Но теперь… теперь «логистика» — это нечто совсем иное. Это экономический термин. Логистика — это управление материально-техническим обеспечением, товарами и сырьем. Бывает логистика снабжения, логистика производства, логистика сбыта, логистика транспорта… или всего этого, вместе взятого. Ну а логистик — это как раз специалист по материально-техническому обеспечению. Как сказали бы раньше — снабженец… Может быть, зря беспокоились родители?

С петлей — в словарь

Сотни зрителей на трибунах аэродрома наблюдают, что происходит в небе — а там творится что-то невероятное! Сразу несколько самолетов синхронно выписывают в воздухе фигуры: то сердце получится, то бантик, то звезда… И вдруг трибуны хором ахают — смотрите, что делает во-он тот летчик! Это же мертвая пЕтля!.. Кто-то кричит «пЕтля», а кто-то «петлЯ».

А все-таки — пЕтля или петлЯ? Вопрос не такой простой, как могло бы показаться. Один из самых либеральных словарей, Орфоэпический, позволяет и то, и другое — и петлЯ, и пЕтля. А вот другой, более строгий, Словарь ударений, выбора не оставляет: петлЯ и только петлЯ.

ПетлЯ, петлИ, петлЕ, петлЁй, о петлЕ — в единственном числе ударение на последнем слоге. Такова рекомендация современных нормативных словарей.

Интервальная логика и некоторые ее применения Текст научной статьи по специальности «Математика»

В.И.Левин

ИНТЕРВАЛЬНАЯ ЛОГИКА И НЕКОТОРЫЕ ЕЕ ПРИМЕНЕНИЯ

Abstract. Generalization of continuous logic in the case of uncertainty is considered. Logical operations in this case are carried out not over exactly known numbers but over the intervals of such numbers. The basic laws of interval logic algebra are given. Possible applications of interval logic are shown.

Введение

В 1950-е — 1960-е годы усилиями ученых ряда стран [1-4] были заложены основы непрерывной логики (НЛ), в которой логические операции совершаются над переменными из непрерывных множеств. В качестве последних обычно берутся конечные или бесконечные интервалы. Переход от традиционных дискретных логик, в которых логические операции совершались над дискретными переменными, к непрерывной логике сулил значительное увеличение областей применения логических методов. Уже исследования конца 1960-х — начала 1970-х годов показали ряд прикладных направлений, где с успехом могли быть применены непрерывно-логические методы, а также важные для этих и других возможных приложений усовершенствования основ и математического аппарата НЛ [5-7]. В настоящее время НЛ представляет собой развитую область исследований, находящуюся на стыке прикладной математики и математической логики и имеющую многочисленные приложения в технике, экономике, гуманитарных и общественных науках, в том числе в задачах управления техническими, экономическими и другими системами [3, 6-19]. Все известные на сегодня результаты в теории НЛ и ее приложениях относятся к случаю, когда независимые переменные задаются, а зависимые переменные вычисляются по ним с помощью операций НЛ абсолютно точно. Между тем, все большее число прикладных задач приходится решать в условиях той или иной неопределенности, когда независимые переменные, характеризующие изучаемую систему, задаются лишь приближенно, так что и зависимые переменные, являющиеся различными характеристиками этой системы, могут быть вычислены лишь приближенно. Эта качественно новая ситуация означает, что упомянутые выше многочисленные прикладные системы для адекватного их описания в условиях неопре-

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

Постановка задачи

Как известно [1, 3, 8-10], основные операции НЛ: дизъюнкция V, конъюнкция л и отрицание — определяются следующим образом.,л,—). (2)

Операции дизъюнкции и конъюнкции в алгебре (2) над переменными а и Ь дают значение одной из этих переменных, а операция отрицания над переменной а — число, симметричное с а относительно М. Более того, любая функция НЛ в алгебре (2) на любом наборе значений аргументов принимает значение одного из аргументов или его отрицания. Поэтому задать такую функцию можно таблицей значений. От таблицы можно перейти к аналитическому представлению функции НЛ в виде суперпозиции операций v,л,— (1). Для этого используется метод сочленения [8, 10].

В квазибулевой алгебре НЛ (2) справедливы следующие логические законы

ала=а, ала=а — тавтологии (3)

avЬ=Ьva, алЬ=Ьла — переместительный (4) (avЬ)vc=av(Ьvc), (алЬ)лс=ал(Ьлс) — сочетательный (5) aл(Ьvc)=(aлb)v(aлc), aл(Ьvc)=(aлЬ)v(aлc) — распреде

_ _ _ _ лительный (6)

а v Ь = а л Ь , а л Ь = а v Ь — де Моргана (7) av(aлЬ)=a, aл(avЬ)=a, — поглощения (8)

а =а — двойного отрицания (9)

алА=А, алВ=а, avA=a, avB=B — действий с константами (10) ал а =М-|а-М| — псевдопротиворечия (11)

av а =М+|а-М| — псевдоисключенного третьего (12) а лb)=(аvb)л(M+|а-M| — псевдоортогональности (13)

Кроме того, при комбинировании базовых логических операций v,л,—I (1) квазибулевой алгебры (2) со сложением и умножением появляются новые, комбинированные законы:

а+(^с)=(а+Ь^(а+с)] распределительный для сложения

относительно дизъюнкции (14)

a-(bv с)= (а-Ь)л (а-с)]

а+(Ьлс)=(а+Ь)л(а+с)} распределительный для сложения

относительно конъюнкции (15)

а-(Ьл с)= (a-b)v (а-с)]

a•(bvc) = (а’Ь^(а’с) ] распределительный

¡% а,Ь,с>0 для умножения (16) (Ь v с)= (-а • Ь)л (-а • с) ] относительно дизъюнкции

а^(Ьлс) = (а^Ь)л(а^с) ] распределительный

¡% а,Ь,с>0 для умножения (17) (Ьл с)= (-а • Ь) v (-а • с) ] относительно конъюнкции

а + Ь = а -Ь= Ь -а; — спуска отрицания на слагаемые (18)

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

Пусть теперь значения логических переменных а,Ь,с,… из отрезка С=\Л,Б\ известны не точно, а приближенно и заданы с точностью до интервала возможных значений. Т.е. любая переменная а задается в виде замкнутого интервала

~ ={а|а1<а<а2}=[аьа2] (19)

В этом, более общем случае операции НЛ не могут определяться прежними выражениями типа (1), а нуждаются в новых, обобщенных определениях. Наша задача — дать эти новые определения для основных логических операций и принципы их получения для всех остальных операций, установить основные законы получающейся новой, интервальной НЛ и их отличия от аналогичных законов (3)-(18) классической НЛ, а также наметить пути применения этой новой НЛ для решения разнообразных прикладных задач в условиях неопределенности.

Общее описание интервальной непрерывной логики

Независимые переменные а,Ь,с в интервальной НЛ рассматриваются как замкнутые интервалы возможных значений этих пере-

менных, т.е. как ~ =[аьа2], Ь =[ЬьЬ2], ~ =[cl,c2]. Введение логических операций над такими интервальными переменными возможно на основе различных принципов. Мы будем исходить из принципа, принятого в современной интервальной математике [20]. Согласно ему произвольная операция о над двумя интервальными переменными а~ и Ь вводится как прямое теоретико-множественное обобщение соответствующей операции • над точными переменными а и Ь при у~словии, что а и Ь принадлежат соответственно множествам а~ и Ь , т.е.

~ о Ь =а • Ь | ае а , Ье Ь (20)

Другими словами, результатом операции о над интервалами ~ и Ь в интервальной математике считается множество результатов соответствующей операции • над вещественными числами а и Ь при условии, что а пробегает множество значений ~ , а Ь — множество значений Ь . Операция о над одним или несколькими интервальными переменными вводится аналогично (20). Пользуясь определением (20), в интервальной математике вводят и изучают алгебраические операции над интервалами — сложение, вычитание, умножение и деление.л,-,). (22)

Эта алгебра отличается от квазибулевой алгебры обычной НЛ (2) тем, что логические операции дизъюнкции, конъюнкции и отрицания выполняются в ней не над вещественными числами из интервала С в соответствии с определением (1), а над вещественными интервалами из С в соответствии с определением (21). Данное отличие двух алгебр приводит к большим различиям в их

свойствах.

Основные свойства интервальной НЛ описаны ниже. При этом мы ограничиваемся только рамками квазибулевой алгебры (22) этой НЛ, что не снижает общности, поскольку в интервальной НЛ, как и в обычной НЛ (см. \19\), различные возможные операции обычно выражаются суперпозицией операций v,л,—I алгебры (22). Теорема 1. Результаты операций дизъюнкции v, конъюнкции л и отрицания — НЛ над интервалами а =\аьа2\, Ь =\ЬьЬ2\, есть интервалы, вычисляемые по формулам

а~у Ь~=[аьа2^[Ь ьЬ2\=\а1 vb ь а2 vb2\, а лЬ =\а1,а2\л\Ь1,Ь2\=\а1 лЬи а2лЬ2\, (23)

3 =\аь а 2 \ =\ а 2, 31 \ Доказательство теоремы 1.уЬ2, где v=max — операция дизъюнкции обычной НЛ (1). Как известно из теории чисел, множество вещественных чисел всюду плотное. Это значит, что интервал а (интервал Ь ) содержит все вещественные значения между его нижней и верхней границами а! и а2 (Ь\ и Ь2). Отсюда следует, что множество значений результата операции v над интервалами ~ и Ь содержит все вещественные значения между нижней и верхней границами этого результата, найденными выше, что и означает первую формулу (23). Доказательство остальных формул (23) получается аналогично.

Как следует из формул (23), дизъюнкция (конъюнкция) НЛ двух интервалов а3 и Ь есть интервал, нижняя граница которого есть дизъюнкция v=max (конъюнкция л=тт) НЛ нижних границ а и Ь , а верхняя граница — дизъюнкция v=max (конъюнкция л=тт) НЛ верхних границ а и Ь . Отрицание НЛ интервала а есть интервал, нижняя (верхняя) граница которого есть отрицание верхней (нижней) границы интервала ~, т.е. интервал, расположенный симметрично с а относительно центра М множества-носителя С=\Л,Б\ алгебры НЛ (22).(а:лЬ 1=Ь 1, а2лЬ2=Ь2):([а1лЬь а2лЬ2\=\Ь1,Ь2\):( а лЬ = Ь ),

что и требовалось доказать. Доказательство того, что из правой части (24) следует левая часть, аналогично.

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

Теорема 3. Для того чтобы в паре интервалов ~~=[а1,а2], Ь =[Ь1,Ь2] выполнялись равенства а v Ь = ~, ~ л Ь = Ь , необходимо и достаточно выполнения системы неравенств а1>Ь1, а1>Ь1, а2>Ь2.

Доказательство теоремы 3. Первая половина цепочки следствий ь из доказательства теоремы 2 показывает, что (~ v Ь = а)^(а1>Ь1, а2>Ь2~ Аналогичная цепочка следствий показывает, что (а лЬ = Ь )^(а1>Ь1, а2>Ь2). Два полученных следствия доказывают необходимость сформулированного в теореме условия. Достаточность этого условия доказывается аналогично.

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

Ситуация, когда операции дизъюнкции и конъюнкции НЛ над двумя интервалами аь иь Ь приводят к новому интервалу, отличному и от аь и от Ь , полностью описывается следующим утверждением.

Теорема 4. Для того чтобы для пары интервалов а=[аьа2], Ь =[Ь1,Ь2], выполнялись неравенства а vЬ Фа,Ь, а лЬ Фа,Ь, необходимо и достаточно выполнения какой-нибудь одной из двух систем неравенств а1<Ь1, а2>Ь2 или Ь1<а1, Ь2>а2.

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

Из теоремы 4 следует, что операции~дизъюнкции и конъюнкции НЛ над двумя интервалами аь и Ь ьдают результат в виде нового интервала, отличного и от аь и от Ь , только в тех случаях, когда один из интервалов накрывает другой. В целом, приведен-

ные результаты свидетельствуют о значительных отличиях интервальной НЛ от обычной НЛ и тем более от дискретных логик. Главное отличие состоит в том, что операции дизъюнкции и конъюнкции НЛ (21) над интервалами 3 и Ь не всегда дают значение одного из них. В связи с этим функции интервальной НЛ в алгебре (22) не на любом наборе значений аргументов принимают значение одного из аргументов или его отрицания.21, находим 3 =\vьv2\=(\xьx2\v\yl,y2\)л3zьz2\ = [(xlvyl)л 22 , (х2уу2)л ¿1 \. Теперь для вычисления значений V остается подставить в полученное выражение ~ численные значения интервалов х,~, 3 и выполнить операции обычной НЛ (1).

Законы интервальной непрерывной логики

Особенно большие отличия между обычной и интервальной НЛ имеются на уровне их логических законов. При этом лишь 7 из 16 законов обычной НЛ сохраняют свою силу в интервальной НЛ, в то время как 9 других законов меняются. Начнем с законов НЛ, сохраняющих свою силу.

3 v~ = а л~= а — тавтологии (25)

Доказательство закона (25). Согласно определению (21) операций дизъюнкции и конъюнкции интервальной НЛ и с учетом закона тавтологии (3) обычной НЛ а v~ = {ava|ae ~ }={а|ае ~ }, что доказывает первое тождество (25). Доказательство второго тождества аналогично. ~ ~

а vЬ = Ь v~лЬ = Ь л~ — переместительный (26)

Доказательство закона (26) аналогично доказательству закона (25), причем используется соответствующий закону (26) закон (4) обычной НЛ.

Последующие 5 законов также доказываются аналогично закону (25). 3 3 3

(~ v Ь )\/~ = ~ v(Ь v 33), (3 л Ь~) л се = еел( Ь л 3) -сочетательный (27) а v Ь = 3 лЬ , 3 л Ь = 3 v Ь — де Моргана (28) 3 = а — двойного отрицания (29)

3лЛ=Л, 3 лБ= з_:_ззуЛ=E:3, 3 лБ=Б — действий с константами (30) 3 + Ь = 3 -Ь = Ь -3 — спуска отрицания на слагаемые (31)

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

а v(а лЬ а л(~ vЬ а — субпоглощения (32)

Доказательство закона (32).п(М3-М)\ —

субортогональности (40)

(М, М3 и sgn х — те же).

Доказательство закона _(40). Положив во втором выражении (33) 3 = 3, получим 3 v( 3 лЬ )с(3 vЬ )л( 3 v3), откуда после замены (3 v 3) по3формуле (39) получим (40). а л( 3 v Ь )с(3 л Ь )v \М+( 3 -M)sgn(М3 -М)\ —

субортогональности (41)

(М, М3, sgn х — те же).

Доказательство закона (41) аналогично доказательству закона (40) и использует первое выражение (33) и формулу (38).

Законы интервальной НЛ (25)-(31), (38), (39), в форме тождеств, можно использовать для эквивалентных преобразований логических выражений для приведения к наиболее простому (удобному) виду. Законы (32)-(37), (40), (41), в форме включений, можно использовать только для оценки логических выражений.

Применения интервальной непрерывной логики

Интервальная НЛ может найти широкое применение в задачах управления, вычислительной и измерительной техники, экономики и т.д. при наличии неопределенности. Ограничимся тремя примерами.

1. Г е о м е т р и ч е с к о е м о д е л и р о в а н и е. Пусть задана точно некоторая кривая, характеризующая объект управления; требуется описать ее аналитически соответствующим уравнением

1

Рисунок. Размытая (интервальная) кривая, полученная пересечением интервальных прямых (1 — вогнутая, 2 — выпуклая).

[19]. В случае сложных (изломанных, разрывных и т.д.) кривых решение данной задачи с помощью НЛ обычно требует меньше исходных параметров и проще описывает объект, чем другие методы [17, 19]. Так, изломанную кривую, полученную пересечением двух прямых а1х+Ь1 и а2х+Ь2 можно записать аналитически

у=(а1Х+Ь 1) X (а2х+Ь2), (42)

где операция конъюнкции НЛ берется для выпуклой кривой, а операция дизъюнкции НЛ — для вогнутой.

Представление (42) не требует знания даже точки пересечения прямых, и потому оно особенно простое. Пусть теперь параметры указанных прямых известны не точно, а приближеннсо — в виде интервалов возможных значений а-! =[а11,а12], Ь =[Ь11,Ь12], а2 =[а21,а22], Ь2 =[Ь21,Ь22]. Тогда каждая прямая в любой точке X принимаетс не одно знсачение, а интервал возможных значений: с = с х+ Ьх, гу 2 = с2 х+ Ь2 . Как видим, исходные прямые превратились теперь в полосы с линейно возрастающей при увеличении х

толщиной (см.), х2(0. При обозначении 1(Л,Б) двоичного процесса в виде импульса в интервале времени (Л,Б) у(0 равен импульсу 1(а,Ь) при Ь>а и постоянному 0 при Ь<а. Интерпретируя постоянный 0 как импульс 1(а,а) с совпадающими началом и концом и используя операцию дизъюнкции НЛ, получим выражение выходного процесса у(0 в виде

Г 1(а,Ь), Ь>а I у(0 = \ I = 1(а, аvb) (45)

I 0 = 1(а,а), Ь<а | Аналогично находятся выходные процессы в других элементарных автоматах и при других входных процессах. На базе этих расчетов строятся расчеты выходных процессов в произвольных дискретных автоматах, собранных из элементарных автоматов [8, 17— 19\. Пусть теперь временные параметры а, Ь входных процессов изученного элементарного автомата известны не точно, а приближенно — в виде интервалов возможных значений а=\а!,а2\, Ь =\ЬьЬ2\. Тогда двоичные процессы на входах автомата можно записать в виде 3

Г 0, К 3 =\аьа2\, Г 1, Г< Ь =\ЬьЬ2\,

х^) = ^ х2(^) = ^ 3 (46)

I 1, О 3=\аьа2\, I 1, Ь =\Ь1,Ь2\.Ь |

или, объединяя два выражения с помощью дизъюнкции НЛ (1),

y(t)=©(al,a2)1(a2,a2vЬl)©(a2vЬl, a2vЬ2) (47)

Выражения вида (47) получаются при расчетах динамики в условиях неопределенности и более сложных автоматов, чем рассмотренный [18].

3. Д и с к р е т н а я о п т и м и з а ц и я. Пусть надо распределить 3 кандидатов по 3 должностям так, чтобы все должности были заняты, все кандидаты трудоустроены, а суммарная эффективность была максимальной. При этом значения а7] эффективности кандидатов 7 в должностях j (7]= 1,3) известны лишь с точностью до интервала возможных значений: а7]- =[агу1,агу2]. Детерминированный вариант этой задачи с точно известными эффективностями а7]- рассмотрен в [10, 13, 17, 19]. Сейчас используем аналогичный подход. Каждому распределению должностей

соответствует своя распределяющая сумма элементов матрицы эффективности Л =|| ау ||, включающаяровно по одному элементу из каждой строки и каждого столбца Л .(а1>Ь1,32>Ь2). (49)

Выделенная максимальная скобка в (48) и определит оптимальное распределение должностей между кандидатами. Например, если (311+ 323 + а32 )=тах, то оптимально такое распределение: кандидат 1 занимает должность 1, кандидат 2 — должность 3, а кандидат 3 — должность 2.

Заключение

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

интервальной НЛ. Это вызвано тем, что часть законов интервальной НЛ, в отличие от традиционных логик, вообще не являются эквивалентными логическими преобразованиями, а носят лишь оценочный характер [законы (З2)-(ЗТ), (4G), (41)], а часть законов, являющихся такими преобразованиями, существенно усложняются [законы (3S), (39)]. Такое уменьшение возможностей логических методов при переходе к интервальной НЛ следует рассматривать как неизбежную плату за получаемую возможность изучения с помощью логических методов систем в условиях неопределенности, когда параметры системы известны лишь с точностью до интервалов возможных значений.

ЛИТЕРАТУРА

1. Мак-Нотон Р. Теорема о бесконечнозначной логике высказываний // Кибернетический сб. Вып. 3. M.: Изд-во иностр. лит. 19б1. С. 5-lS.

2. Schaefer D.H. A rectifier algebra // Trans. American Inst. Electrical Eng. 1955. V. 73. № 1. P. 679-6S2.

3. Гинзбург С.А. Mатематическая непрерывная логика и изображение функций. M.: Энергия. 196S.

4. Иванов Л.Л. Начала аналитической теории разрывных функций и расчет нелинейных цепей // Электричество. 196G. №9. С. 23-29.

5. Гинзбург С.А. Непрерывная логика и ее применения // Автоматика и телемеханика. 1967. №2. С. 115-132.

6. Рвачев В.Л. Геометрические приложения алгебры логики. Киев: Техника, 1967.

I. Гинзбург С.А., Любарский Ю.Я. Функциональные преобразователи с аналогово-цифровым представлением информации. M.: Энергия, 1973.

S. Левин В.И. Динамика логических устройств и систем. M.: Энергия, 19SG.

9. Коффман А. Введение в теорию нечетких множеств. M.: Радио и связь, 19S2.

1G. Левин В.И. Бесконечнозначная логика в задачах кибернетики. M.: Радио и связь, 19S2.

II. Левин В.И. Логическая теория надежности сложных систем. M.: Энергоатомиздат, 19S5.

12. Золотова Т.М., Кербников Ф.И., Розенблат М.А. Резервирование аналоговых устройств автоматики. M.: Энергоатомиздат, 19S6.

13. Левин В.И. Структурно-логические методы исследования сложных систем. M.: Наука, 19S7.

14. Беркович Е. И. Непрерывнозначная логика в задачах микроэлектроники // Опыт, результаты, проблемы. Повышение конкурентоспособности радиоэлектронной аппаратуры. Таллинн: Валгус. 19SS. С. 165-

2G1.

15. Волгин Л. И. Синтез устройств для обработки и преобразования

информации в элементном базисе реляторов. Таллинн: Валгус, 1989.

16. Шимбирев П.Н. Гибридные непрерывно-логические устройства. М.: Энергоатомиздат, 1990.

17. Волгин Л.И., Левин В.И. Непрерывная логика: Теория и применения. Таллинн: АН Эстонии, 1990.

18. Левин В.И. Теория динамических автоматов. Пенза: Изд-во Пенз. гос. техн. ун-та. 1995.

19. Левин В.И. Методы непрерывной логики в задачах управления // Автоматика и телемеханика. 2003. № 3. С. 28-51.

20. Алефельд Г., Херцбергер Ю. Введение в интервальные вычисления. М.: Мир, 1987.

21. Левин В.И. Дискретная оптимизация в условиях интервальной неопределенности // Автоматика и телемеханика. 1992. № 7. С. 97107.

Функция логического ИЛИ — цифровые логические ворота

Функция логического ИЛИ Функция заявляет, что выходное действие станет ИСТИНА, если какое-либо еще одно событие «ИЛИ» будет ИСТИНА, но порядок, в котором они происходят, не имеет значения, поскольку это не влияет на конечный результат.

Например, A + B = B + A. В булевой алгебре функция логического ИЛИ следует закону коммутации так же, как и для функции логического И, позволяя изменять положение любой переменной.

Функцию OR иногда называют полным именем «Inclusive OR», в отличие от функции Exclusive-OR, которую мы рассмотрим позже в шестом уроке.

Логическое или логическое выражение, данное для логического элемента ИЛИ, соответствует Логическому сложению , которое обозначено знаком плюс (+). Таким образом, логический элемент ИЛИ с 2 входами (A B) имеет выходной член, представленный логическим выражением: A + B = Q.

Переключить представление функции ИЛИ

Здесь два переключателя A и B соединены параллельно, и любой переключатель A ИЛИ можно замкнуть, чтобы включить лампу.Другими словами, любой переключатель может быть замкнут, или при логической «1» лампа должна быть «ВКЛЮЧЕНА».

Тогда этот тип логического элемента производит и выводит только тогда, когда присутствует «ЛЮБОЙ» из его входов, а в терминах булевой алгебры выход будет ИСТИНА, когда любой из его входов будет ИСТИНА. С точки зрения электричества, функция логического ИЛИ приравнивается к параллельной схеме.

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

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

Переключатель A	Переключатель B	Выход	Описание
0	0	0	A и B оба разомкнуты, лампа не горит
0	1	1	A разомкнут, а B замкнут, лампа горит
1	0	1	A замкнут и B разомкнут, лампа горит
1	1	1	A замкнут, а B замкнут, лампа горит
Логическое выражение (A OR B)			А + В

В стандартной комплектации доступны логические элементы ИЛИ

i.c. пакеты, такие как общий TTL 74LS32 Quadruple 2-input Positive OR Gates. Как и в случае с предыдущим логическим элементом И, логическое ИЛИ также можно «каскадировать» для создания цепей с большим количеством входов, например, в системах охранной сигнализации (Зона A, Зона B, Зона C и т. Д.).

Ternary Logic — Snowflake Documentation

Как указано в стандарте SQL, троичная логика или трехзначная логика (3VL) — это логическая система с тремя значениями истинности: ИСТИНА, ЛОЖЬ и НЕИЗВЕСТНО.В Snowflake UNKNOWN представлен NULL. Тернарная логика применяется к оценке логических выражений, а также предикатов и влияет на результаты логических операций, таких как AND, OR и NOT:

• При использовании в выражениях (например, в списке SELECT) результаты UNKNOWN возвращаются как значения NULL.

• При использовании в качестве предиката (например, предложение WHERE) результаты UNKNOWN оцениваются как FALSE.

В этой теме:

Таблицы истинности¶

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

Операторы сравнения¶

Если какой-либо операнд для оператора сравнения равен NULL, результат будет NULL. Операторы сравнения:

Логические операторы¶

Для столбца BOOLEAN C :

Если C :	C AND NULL дает результат:	C OR NULL дает результат:	НЕ C оценивается как:
ИСТИННО	ПУСТО	ИСТИНА	НЕВЕРНО
ЛОЖНО	ЛОЖЬ	ПУСТО	ИСТИНА
NULL	ПУСТО	ПУСТО	ПУСТО

Дополнительно:

Если C :	C И (НЕ C) оценивается как:	C ИЛИ (НЕ C) дает результат:	NOT (C OR NULL) дает результат:
ИСТИННО	НЕВЕРНО	ИСТИНА	НЕВЕРНО
ЛОЖНО	НЕВЕРНО	ИСТИНА	ПУСТО
NULL	ПУСТО	ПУСТО	ПУСТО

Замечания по использованию условных выражений¶

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

IFF ​​Behavior¶

Функция IFF возвращает следующие результаты для троичной логики. Для столбца BOOLEAN C :

Если C :	IFF (C, e1, e2) оценивается как:
ИСТИННО	e1
ЛОЖНО	e2
NULL	e2

[НЕ] В поведении¶

Функции [НЕ] IN возвращают следующие результаты для троичной логики.Даны 3 числовых столбца c1 , c2 и c3 :

• c1 IN (c2, c3, ...) синтаксически эквивалентен (c1 = c2 или c1 = c3 или ...) .

  В результате, когда значение c1 равно NULL, выражение c1 IN (c2, c3, NULL) всегда оценивается как FALSE.

• c1 NOT IN (c2, c3, ...) синтаксически эквивалентен (c1 <> c2 AND c1 <> c3 AND...) .

  Следовательно, даже если c1 NOT IN (c2, c3) имеет значение TRUE, c1 NOT IN (c2, c3, NULL) оценивается как NULL.

Wolfram | Примеры альфа: логика и теория множеств

---

Другие примеры

Булева алгебра

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

Проанализируйте логическое выражение:

Вычислить таблицу истинности для логической функции:

Вычислите логическую схему для логической функции:

Преобразуйте логическое выражение в дизъюнктивную нормальную форму:

Другие примеры

---

Другие примеры

Теория множеств

Проверка принадлежности к множеству, равенства множеств и отношений подмножеств.Нарисуйте диаграмму Венна для умеренного количества подходов.

Проверить, истинно ли данное уравнение множеств:

Другие примеры

---

Другие примеры

Трансфинитные числа

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

Получите информацию о трансфинитном кардинале:

Упростите выражение с участием кардиналов:

Другие примеры

Глава 4 Логика высказываний | В поисках истины: руководство к критическому мышлению

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

1. Я пойду сегодня ужинать куда-нибудь или завтра пойду завтракать.
2. Я не пойду сегодня ужинать.
3. Я пойду завтракать завтра.

Ни одно из этих предложений не укладывается ни в одну из четырех категориальных схем.Итак, нам нужна новая логика, называемая логикой высказываний. Хорошая новость в том, что это довольно просто.

Простые и сложные предложения

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

• Баптистский университет Оклахомы находится в Шони, штат Оклахома.
• Барак Обама сменил на посту президента США Дональд Трамп.
• Снаружи 33 градуса.

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

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

• Отрицания
• Союзы
• Дезъюнкции
• Условные обозначения
• Биокондиционеры

Отрицания

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

Отрицание обозначается помещением этого символа «\ (\ neg \)» перед буквой предложения. Символ выглядит как тире с хвостиком на правой стороне.Если \ (\ textrm {D} \) = ‘Это 33 градуса снаружи’, тогда \ (\ neg \ textrm {D} \) = ‘Это не 33 градуса снаружи.’ Символ отрицания используется для перевода этих английских слов. фраз:

• не
• это не тот случай, когда
• неправда, что
• неверно, что

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

При переводе старайтесь, чтобы простые предложения имели положительный смысл. Обратите внимание на предупреждение на странице 24 о примере утверждения и отрицания. Отрицание — это не просто отрицание утверждения.

Соединение

Отрицания — это предложения «и». Они складывают два предложения, называемые союзами, вместе и утверждают, что оба они верны. Мы будем использовать амперсанд (&) для обозначения отрицания. Другие распространенные символы — точка и перевернутый клин. Английские слова, переведенные с амперсандом, включают:

• и
• но
• также
• однако
• еще
• неподвижный
• кроме того
• хотя
• тем не менее
• оба

Например, мы могли бы перевести предложение «Сегодня идет дождь, и мой люк на крыше открыт» как «\ (\ textrm {R} \ & \ textrm {O} \)».’

Дизъюнкция

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

Мы используем этот символ, называемый «vel», для дизъюнкций: \ (\ vee \). Vel используется для перевода — или — либо или — если только

условно

Условное предложение — это распространенный тип приговора.Он утверждает, что что-то правда, если что-то еще тоже. Примеры условных операторов:

.

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

Мы можем перевести эти предложения стрелкой так:

• \ (F \ стрелка вправо C \)
• \ (М \ стрелка вправо L \)
• \ (L \ rightarrow \ neg W \)

Стрелка переводит множество английских слов и фраз, в том числе

• если
• если… то
• только если
• всякий раз, когда
• когда
• только тогда, когда
• означает
• при условии, что
• означает
• влечет за собой
• — достаточное условие для
• — необходимое условие для
• при том, что
• при условии, что
• в кейсе

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

• Олбани — столица Нью-Йорка, а Остин — столица Техаса.
• Остин — столица Техаса, а Олбани — столица Нью-Йорка.

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

Это не относится к условным операторам. Обратите внимание на разницу между этими двумя предложениями:

• Если вы вытащили ромб, вы вытянули красную карточку.
• Если вы вытянули красную карточку, значит вы вытянули ромб.

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

Посмотрите еще раз на эти три примера:

1. «Если Сара сделает пятёрку в финале, то она получит пятёрку за курс».
2. «Ваш автомобиль прослужит много лет, если вы будете выполнять необходимое обслуживание».
3. «Вы можете зажечь эту спичку, только если она не мокрая.”

Антецедент для первого предложения — «Сара делает пятерку в финале». Как следствие: «Она получит пятёрку за курс». Обратите внимание, что , если , и , то не являются частями антецедента и следствия.

Во втором предложении antecdent: «Вы выполняете необходимое техническое обслуживание». Как следствие, «Ваша машина прослужит много лет». Это говорит нам о том, что антецедент не всегда стоит на первом месте в английском предложении.

Третье предложение сложное.Антецедент: «Вы можете зажечь эту спичку». Почему? Объяснение включает то, что называется необходимыми и достаточными условиями.

Необходимые и достаточные условия

Достаточное условие — это то, чего достаточно, чтобы гарантировать истинность чего-то еще. Например, для того, чтобы получить пятерку, достаточно получить 95 баллов за экзамен, при условии, что экзамен стоит 100 баллов. Необходимое условие — это что-то, что должно быть истинным, чтобы было истинно что-то еще. Чтобы получить пятерку, не обязательно набирать 95 баллов на экзамене — 94 балла все равно равнялись бы А.Однако для получения пятерки необходимо сдать экзамен. Вы не сможете получить пятерку, если не сдадите экзамен, или, другими словами, вы можете получить пятерку, только если вы зарегистрируетесь на курс.

Вот несколько важных правил, о которых следует помнить:

• «Если» вводит антецеденты, но Только если вводит консеквенты.
• Если A — достаточное условие для B, то \ (A \ rightarrow B \).
• Если A — необходимое условие для B, то \ (B \ rightarrow A \).

Двусторонняя

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

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

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

• это и только если
• тогда и только тогда, когда
• на всякий случай
• — необходимое и достаточное условие для

Переводы

Логика высказываний — это язык.Как и другие языки, у него есть синтаксис и семантика. Синтаксис языка включает основные символы языка плюс правила составления правильных операторов на языке. Чтобы использовать логику высказываний, нам нужно знать, как переводить английские предложения на язык логики высказываний. Мы начинаем с букв предложения, которые представляют собой простые английские предложения. Возьмем три, позаимствованные у читателя начальной школы:

T : Том ударил по мячу.
J : Джейн поймала мяч.
S : Точечная погоня за мячом.

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

Том не ударил по мячу	\ (\ neg T \)
Либо Том ударил по мячу, либо Джейн поймала мяч	\ (Т \ Вее J \)
Спот погнался за мячом, но Джейн его поймала.	\ (S \ mathbin {\ &} J \)
Если Джейн поймала мяч, то Спот не стал его преследовать.	\ (L \ rightarrow \ neg S \)
Спот преследовал мяч тогда и только тогда, когда Том бил по мячу.	\ (S \ leftrightarrow T \)

Мы можем составлять даже более сложные предложения, но вскоре мы столкнемся с проблемой. Рассмотрим этот пример:

\ [T \ mathbin {\ &} J \ rightarrow S \]

Мы не знаем, что это значит. Это может быть одно из следующих значений:

1. Том отбивал мяч, и если Джейн ловила мяч, то Спот преследовал его.
2. Если Том ударил по мячу, а Джейн поймала его, то Спот погнался за ним.

Первое предложение — это союз, \ (T \) — первый конъюнкт, а \ (M \ rightarrow S \) — второй конъюнкт. Второе предложение, тем не менее, является условным, \ (T \ mathbin {\ &} M \) — предшествующим, а \ (S \) — следствием. Наши две интерпретации не эквивалентны, поэтому нам нужен способ устранить двусмысленность. Мы можем сделать это с помощью скобок. Наше первое предложение становится:

\ [T \ mathbin {\ &} (J \ rightarrow S) \]

Второе предложение:

\ [(T \ mathbin {\ &} J) \ rightarrow S \]

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

\ [[(P \ mathbin {\ &} Q) \ vee R] \ rightarrow \ {[(\ neg P \ leftrightarrow Q) \ mathbin {\ &} S] \ vee \ neg P \} \]

Каждое предложение в логике высказываний может быть одного из шести типов:

1. Простой
2. Отрицание
3. Соединение
4. Дизъюнкция
5. условно
6. Двусторонняя

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

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

Вот несколько примеров:

п.	Нет	Простой
\ (\ neg P \ mathbin {\ &} Q \)	и	Соединение
\ (\ neg (P \ mathbin {\ &} Q) \)	\ (\ neg \)	Отрицание
\ (P \ vee (Q \ rightarrow R) \)	\ (\ vee \)	Дизъюнкция
\ ([(P \ mathbin {\ &} \ neg Q) \ leftrightarrow R] \ rightarrow P \)	\ (\ rightarrow \)	условно

Дуглас В.Джонс о троичной логике

Дуглас В. Джонс о троичной логике

Часть http://homepage.cs.uiowa.edu/~dwjones/ternary/ — пользователем Дуглас В. Джонс T HE U NIVERSITY ИЗ И OWA Департамент компьютерных наук Заявление об ограничении ответственности: никто, кроме автора, не поддерживает использование описанных здесь обозначений, хотя в целом обозначения, используемые исследователями в этой области, ужасно плохи, и автор хотел бы, чтобы другие приняли его предложенные обозначения. © 2012 Дуглас В. Джонс; пересмотрено в 2016 году. Настоящим предоставляется разрешение на неограниченное использование представленных здесь схематических диаграмм для любых целей, включая производные работы; нет никаких ограничений на ссылки на эту веб-страницу.

Аннотация

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

1. Тернарные константы
2. Монадические операторы
   1. Буферы и драйверы
   2. Отрицание
   3. Увеличение и уменьшение
   4. Декодеры
   5. Зажимы
3. Диадические операторы
   1. Мин или А
   2. Макс или Или
   3. Антимин и Антимакс
   4. Эксклюзив Или
   5. Сумма
   6. Консенсус
   7. Принять что угодно
   8. Сравнение
4. Минимизация
   1. Каноническая сумма произведений
   2. Объединение минтермов
   3. Сокращенное обозначение
   4. Оценка сложности результата

---

Логика Клини дополняет обычную истина и ложь логической логики с третьим значением, неизвестно [Фиттинг, 1994].Различные авторы предлагали присваивать разные числовые значения. эквиваленты этих значений. Здесь мы принимаем следующее:

троичные значения

значение истинности	числовое	краткая форма
правда	+1	+
неизвестно	0	0
ложный	–1	—

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

Однако не все идеально. Для беззнаковых троичных чисел мы бы предпочитают значения 0, 1 и 2, а пользователи обычной булевой логики иметь глубоко укоренившееся желание иметь ложь представлена ​​нулем и правда по одному, предполагая, что, возможно, неизвестно должно быть два.В более абстрактной теоретико-решеточной смысл, истина и ложь оба больше, чем неизвестно в том, что они передают больше информации. Чтобы завершить решетку (и перейти к 4-значная логика) мы могли бы даже добавить завышенное значение, которое больше чем оба истинный и ложный [Маскенс, 1999]. Здесь мы просто игнорируем эти альтернативы, пока оставляя за собой право использовать альтернативные порядки и числовые интерпретации всякий раз, когда это удобно.

Мы используем символы +, 0 и — для сокращения +1, 0 и -1 следующим образом. [Александр, 1964].

В обычной булевой логике всего четыре (2 в квадрате) монадические (с одним аргументом) функции, три из которых тривиальны:

Монадические логические функции

вход	ложь	идентификация	не	правда
ложь	ложь	ложь	правда	правда
истинно	ложно	истинно	ложно	правда

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

Переход к Ternary увеличивает количество монадических функций с 4 до 27. (3 куба), из которых четыре тривиальные, три функции с постоянным значением и функция идентичности.Все эти функции перечислены здесь:

перечисление монадических троичных функций

вход	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F	G	H	К	M	N	п	п	т	V	X	Z
—	—	0	+	—	0	+	—	0	+	—	0	+	—	0	+	—	0	+	—	0	+	—	0	+	—	0	+
0	—	—	—	0	0	0	+	+	+	—	—	—	0	0	0	+	+	+	—	—	—	0	0	0	+	+	+
+	—	—	—	—	—	—	—	—	—	0	0	0	0	0	0	0	0	0	+	+	+	+	+	+	+	+	+

Функции 0 , D и Z являются тривиальными постоянными значениями функции false , unknown и true .Это перечисление использует последовательность цифр стандартного гептавинтимального обозначение.

В пороговой логике вход i умножается на константу k и затем сравнивается с двумя пороговыми значениями т ₊ и т _— . Если ki ≥ t ₊ , на выходе будет +1. Если ki ≤ t _— , отупут равен -1. В противном случае на выходе будет 0. Только 17 монадических символов. операторы могут быть вычислены с помощью пороговой логики:

пороговые реализации монадических функций

	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F	G	H	К	M	N	п	п	т	V	X	Z
к	0	-1	-1		-1	-1			-1	1			1	0	-1			-1	1			1	1		1	1	0
т +	1	2	1		2	1			0	2			2	1	1			0	1			1	1		0	0	0
т —	0	0	0		-1	-1			-1	0			-1	-1	-2			-2	0			-1	-2		-1	-2	-1

Пороговые реализации функций с постоянным знаком глупо, но включены выше для полноты картины.Это обсуждение пороговой логики следует схеме, приведенной в [Merrill 1965].

2.1 Буферы и драйверы

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

Буферы и драйверы

a с — — 0 0 + +

c = a

2.2 Отрицание

Функция 5 в перечислении выше является тернарным эквивалентом логической функции , а не . Здесь мы называем эту функцию троичная функция отрицание или neg . Это инвертирует свой вход, возвращая false , когда дано true и наоборот, оставив без изменений неизвестных входных данных. В логических схемах инверсия обозначается обычным символ для логического инвертора с добавленным треугольником чтобы пометить его как троичное устройство.

Отрицание

a с — + 0 0 + —

c = — a

Обратите внимание, что, как и в случае с логическими инверторами, символ состоит из символа для простого буфера или усилителя, с пузырьком на выходе, указывающим инверсия.Здесь мы никогда не будем использовать пузырь для обозначения чего-либо, кроме полностью симметричная инверсия. Многие авторы предложили практические реализации троичных инверторов, из их [Doostaregan, Moaiyeri Navi and Hashemipour, 2010; Горд, 2010; Лин Ким и Ломбарди, 2009; Мали и Уолш, 1972; Муфта, 1978 Ву и Проссер, 1990].

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

Функции 2 и 8 в наше перечисление было названо инвертор отрицательного порога или NTI и инвертор положительного порога или PTI потому что они инвертируют истинные и ложные значения, в то время как обработка неизвестного входного значения как истинного (NTI) или ложный (PTI). Их можно считать троичными для логических функции преобразования, потому что они имеют чисто двузначные выходные данные.

Альтернативные инверторы

вход NTI ПТИ — + + 0 — + + — —

NTI ( a ) = ( a = –1) PTI ( a ) = — ( a = +1)

Некоторые подходы к построению троичной логики в оборудовании приводят к реализации функций PTI и NTI как тривиальные вариации стандартных инвертор, но на практике эти функции не используются для инверсии, скорее они используются как декодеры, как обсуждается в Раздел 2.4. Кроме того, их результаты строго двузначны и поэтому, собственно говоря, их можно рассматривать как троичные по отношению к Булевы преобразователи.

2.3 Увеличение и уменьшение

В булевой логике инвертор можно рассматривать как инкремент или уменьшая свой аргумент по модулю 2. В тернарной логике, по модулю 3 Приращение и декремент Функции совершенно разные от инверсии. Эти функции, номера 7 и B в нашем перечислении были названы повернуть вверх и вниз , а также цикл и обратный цикл , с необычно непонятные обозначения, как задокументировано [Коннелли, 2008].Здесь мы используем следующие обозначения:

Инкремент

a с — 0 0 + + —

c = ( a + 1)

Декремент

a с — + 0 — + 0

c = ( a — 1)

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

Строго говоря, обе эти функции нам не нужны, так как:

• ( a — 1) = (( a + 1) + 1) = — (- a + 1)

Обратите внимание, что отрицание плюс приращение могут использоваться в комбинации, реализовать любую из тернарных функций, которые обеспечивают некоторую перестановку их входы как выходы; они также известны как обратимые функции, поскольку каждая функция перестановки имеет инверсную перестановку.В нашем перечислении функции 7 ( шаг ) и B ( декремент ) — обратные. Функции 5 ( отрицание ), F (без названия) и M (безымянный) все свои инверсии, так как каждый из них меняет местами два значения, оставляя третье неизменным. Функция P (идентификатор ) также является собственной инверсией, в тривиальном смысле, округляя 6 возможных функций перестановок на 3-значная переменная.Упражнение по вычислению безымянных функций F и M с использованием только отрицания плюс приращения оставлен в качестве упражнения для читателя.

Стоит отметить, что приращение и декремент Функции не могут быть реализованы пороговая логика.

2.4 Декодеры

Функции 2 , 6 и K дюйм наше перечисление вывод истина , когда их вход имеет определенное значение истинности, и ложно в противном случае.Эти функции можно использовать для создавать декодеры, и мы называем их здесь функциями декодирования, игнорирование обозначений PTI и NTI и причудливых надстрочных обозначений использован [Муфта, 1976]. Мы используем следующие обозначения для этих функций:

Является ли ложным (НТИ)

a с — + 0 — + —

c = ( a = –1)

неизвестно

a с — — 0 + + —

c = ( a = 0)

правда

a с — — 0 — + +

c = ( a = +1)

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

Обратите внимание, что мы используем знак равенства (=) двумя разными способами: Когда используется на внешнем уровне мы используем его для подтверждения идентичности выражений слева и справа от символа.При использовании в скобках выражение, мы используем его для логического сравнения. В последнем контексте мы можем также используйте знак «не равно» (≠) в его обычном булевом смысле.

Строго говоря, все эти функции нам не нужны, так как:

• ( a = –1) = (- a = +1) = (( a — 1) = +1)
• ( a = 0) = (( a + 1) = +1)

Во многих случаях нам нужно будет декодировать два или три возможных значения тернарной переменной.[Кумар и Прия, 2010] дает практическую реализацию такого декодера, хотя с использованием несовместимые обозначения. Здесь используются следующие обозначения:

Декодер

Функции V , N и 8 дюймов наше перечисление обратные функции декодирования, указанные выше. Как в логическом логики, мы используем пузырек на выходе функции, чтобы указать инверсия, поэтому функция 8 может быть представлена ​​как:

Не правда (ПТИ)

a с — + 0 + + —

c = — ( a = +1) = ( a ≠ +1)

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

2,4 Зажимы

Бывают случаи, когда данные в диапазоне от true to false необходимо преобразовать в диапазон верно от до неизвестно или неизвестно до ложно . Функции C и R в наше перечисление делает это, но мы не будем ввести для них специальные обозначения. Вместо этого мы будем использовать диадические операторы описывают эти функции.

Зажать

a с — — 0 0 + 0

c = ( a ∧ 0)

Зажать

a с — 0 0 0 + +

c = ( a ∨ 0)

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

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

В троичной логике таблица истинности с двумя входами имеет 9 строк, где каждая строка вывода может принимать три значения, что дает 19 683 возможных (то есть 3 в 9-й степени) функции 2-х переменных.Ясно, что это слишком много функций, чтобы их перечислить, но, как и в случае с булевой логикой, некоторые из этих функций заслуживают наименования.

В пороговой логике каждый вход i _j умножается на константу k _j , а затем входы суммируются и затем сравниваются с двумя пороговыми значениями t ₊ и т _— . Если сумма равна t ₊ или больше, результат будет +1.Если сумма составляет т _— , вывод будет -1. В соответствии с [Merrill 1965], 471 из 19 683 диадических тернарных операторов может быть вычислен с использованием порога логика. Учитывая, что это явное меньшинство, мы особо отметим случаев, когда пороговая логика может использоваться в функциях, перечисленных ниже.

3,1 мин или И

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

И или минимум

с б — 0 + — — — — 0 — 0 0 + — 0 +

c = ( a ∧ b ) = мин ( a , b )

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

3,2 Макс или или

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

Или или Максимум

с б — 0 + — — 0 + 0 0 0 + + + + +

c = ( a ∨ b ) = макс ( a , b )

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

Обратите внимание, что, как и в булевой логике, законы ДеМоргана по-прежнему остаются троичными:

• ( a ∨ b ) = — (- a ∧ — b ) или мин. ( a , b ) = — макс (- a , — b )
• ( a ∧ b ) = — (- a ∨ — b ) или макс ( a , b ) = — мин (- a , — b )

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

Также, как и в булевой логике, функции и и или являются дистрибутив:

• ( a ∨ ( b ∧ c )) = (( a ∨ b ) ∧ ( a ∨ c )) или макс. ( a , мин. ( b , c )) = мин. ( макс. ( a , b ), макс ( , ))
• ( a ∧ ( b ∨ c )) = (( a ∧ b ) ∨ ( a ∧ c )) или мин. ( a , макс. ( b , c )) = макс ( мин ( a , b ), мин. ( a , c ))

Есть одно существенное различие между булевой и тернарной логикой: эти функции вводят: в булевой логике, и , или и , а не вместе взятые функции составляют основу всей алгебры; то есть, любая логическая функция может быть выражена исключительно в терминах этих трех функций.Фактически, из-за законов ДеМоргана, и плюс , но не , достаточно, без необходимости или . В тернарной логике есть много функций, которые нельзя выразить с точки зрения мин. плюс макс. и отрицание .

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

3.3 Антимин и Антимакс

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

Нанд или Антимин

с б — 0 + — + + + 0 + 0 0 + + 0 —

c = — ( a ∧ b )

Нор или Антимакс

с б — 0 + — + 0 — 0 0 0 — + — — —

c = — ( a ∨ b )

Конечно, как и в булевой логике, формальной необходимости в этих функциях нет.

3.4 Эксклюзив или

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

Тернарное исключительное или

с б — 0 + — — 0 + 0 0 0 0 + + 0 —

c = ( a ⊕ b ) = xor ( a , b )

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

• ( a ⊕ b ) = (( a ∧ — b ) ∨ ( b ∧ — a ))

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

3,5 Сумма

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

Сумма по модулю-3

с б — 0 + — + — 0 0 — 0 + + 0 + —

c = ( a + b )

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

Полезность этого оператора была понята еще в 1964 году. [Александр, 1964]. В этой ранней презентации использовался символ ⊕, в то время как инвертированный оператор исключающее ИЛИ был описан как троичное умножение и обозначается символом ⊗.

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

• ( a + b ) = (( a = –1) ∧ ( b — 1)) ∨ (( a = 0) ∧ ( b )) ∨ (( a = +1) ∧ ( b + 1))

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

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

• ( a + b )	=	(( a = –1)	∧ ( b = –1)	∧ +1)
  	∨	(( a = –1)	∧ ( b = +1)	∧ 0)
  	∨	(( a = 0)	∧ ( b = 0)	∧ 0)
  	∨	(( a = 0)	∧ ( b = +1)	∧ +1)
  	∨	(( a = +1)	∧ ( b = –1)	∧ 0)
  	∨	(( a = +1)	∧ ( b = 0)	∧ +1)

В канонической сумме произведений могло быть до 9 минут, потому что есть два 3-значных входа.Минтермы с выходными значениями false (-1) были исключено, осталось только 6 минут. В булевой логике каждый минтерм будет было всего два входа, но здесь мы добавили по третьему входу к каждому, константа, указывающая значение функции, когда этот minterm выбрано.

На логической схеме мы отметили, какие логические значения были простыми логическими значениями. значения, пересекая каждый конец соответствующей строки. Где все входы логического элемента являются логическими, выход этого элемента также Boolean, поэтому мы отметили это, опустив значок треугольника.Как результат, мы определили, что совместимые логические элементы могут использоваться для вычисления три minterms, соответствующие истинным выходам (+1) функции. Ворота, используемые для других минтермов, также имеют двузначные обозначения. выход, но они ограничены в диапазоне между ложный и неизвестный . Только последние ворота макс , Используемый для объединения minterms является полностью общим тернарным логическим вентилем.

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

3,6 Консенсус

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

Консенсус

с б — 0 + — — 0 0 0 0 0 0 + 0 0 +

c = ( a ⊠ b ) = cons ( a , b )

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

Обведенный в кружок символ времени ⊗ использовался для консенсус оператор в 4-значной логике вместе с обведенным кружком плюс символ ⊕ для двойного, принимает все, что угодно или доверчивость оператор [Фиттинг, 1994; Маскенс, 1999; Якобс, 2011]. К сожалению, последний символ уже давно используется для обозначения исключающий или оператор в булевой алгебре, и наша цель здесь по возможности строить на аналогичных логических операторах.Следовательно, мы не можем использовать ⊕ для обозначения чего-либо, кроме тернарного аналога эксклюзив — или . Это не позволяет использовать его для тернарный принимает что-либо оператор и предлагает, что мы не должны используйте ⊗ для консенсуса . Вместо этого мы предпочитаем использовать квадрат умножить на и и в квадрате плюс ⊞ для консенсуса и принимают все, что угодно, .

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

Консенсус Функция одновременно коммутативна и ассоциативна, и существуют полезные законы о распределении, которые применяются:

• (( a ⊠ b ) ⊠ c ) = ( a ⊠ ( b ⊠ c ))
• ( a ⊠ ( b ∧ c )) = (( a ⊠ b ) ∧ ( a ⊠ c ))
• ( a ⊠ ( b ∨ c )) = (( a ⊠ b ) ∨ ( a ⊠ c ))
• ( a ∧ ( b ⊠ c )) = (( a ∧ b ) ⊠ ( a ∧ c ))
• ( a ∨ ( b ⊠ c )) = (( a ∨ b ) ⊠ ( a ∨ c ))

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

• ( a ⊠ b )	=	(( a = –1)	∧ ( b = 0)	∧ 0)
  	∨	(( a = –1)	∧ ( b = +1)	∧ 0)
  	∨	(( a = 0)	∧ ( b = –1)	∧ 0)
  	∨	(( a = 0)	∧ ( b = 0)	∧ 0)
  	∨	(( a = 0)	∧ ( b = +1)	∧ 0)
  	∨	(( a = +1)	∧ ( b = –1)	∧ 0)
  	∨	(( a = +1)	∧ ( b = 0)	∧ 0)
  	∨	(( a = +1)	∧ ( b = +1)	∧ +1)

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

• ( a ⊠ b ) = ( a ∧ b ) ∨ (( a ≠ –1) ∧ 0) ∨ (( b ≠ –1) ∧ 0)

В отличие от эксклюзив или и сумма , есть естественные реализации троичной консенсусной функции , которые столь же просты, как и те, которые были широко протестированы для функций max и min .Следовательно, нет особых причин для достижения консенсуса с использованием канонического сумма продуктов. Кроме того, эти реализации естественным образом распространяются на более двух входов, поэтому разумно воспользоваться тем фактом, что консенсус является коммутативным и ассоциативным и использует консенсусные функции с более чем двумя входами. Вот схема резистора-MOSFET инвертирование консенсуса гейта с использованием обозначения Ву и Проссер, 1990:

Обращение к консенсусу

c = — ( a ⊠ b )

В этом вентиле, если оба входа a и b находятся ниже нижнего пороговое напряжение, верхние транзисторы включаются и на выходе c тянули высоко.Точно так же, если входы a и b оба выше верхнее пороговое напряжение, включаются нижние транзисторы и c выход понижен. Во всех остальных случаях резистор тянет c Выход в сторону среднего напряжения между двумя порогами. В разветвление этой конструкции затвора ограничено количеством полевых МОП-транзисторов, которые могут быть соединены последовательно; можно с уверенностью предположить, что значения разветвления превышают 4 достижимы.

Пороговая логика может использоваться для вычисления консенсусной функции с использованием множители +1 на каждом входе и пороги +2 и –2, хотя практические аппаратные реализации с использованием множителя 0.5 и пороги +1 и –1 более вероятны.

3.6 Принять что-нибудь

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

Принять что угодно

с б — 0 + — — — 0 0 — 0 + + 0 + +

c = ( a ⊞ b ) = любой ( a , b )

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

принимает все, что угодно Оператор участвует в двух полезных распределительных правила:

• ( a ⊞ ( b ∧ c )) = (( a ⊞ b ) ∧ ( a ⊞ c ))
• ( a ⊞ ( b ∨ c )) = (( a ⊞ b ) ∨ ( a ⊞ c ))

Однако этот троичный принимает все, что угодно, оператор не ассоциативен, и он не участвует в других правилах распространения:

• (( a ⊞ b ) ⊞ c ) ≠ ( a ⊞ ( b ⊞ c ))
• ( a ∧ ( b ⊞ c )) ≠ (( a ∧ b ) ⊞ ( a ∧ c ))
• ( a ∨ ( b ⊞ c )) ≠ (( a ∨ b ) ⊞ ( a ∨ c ))
• ( a ⊞ ( b ⊠ c )) ≠ (( a ⊞ b ) ⊠ ( a ⊞ c ))
• ( a ⊠ ( b ⊞ c )) ≠ (( a ⊠ b ) ⊞ ( a ⊠ c ))

Пороговая логика может использоваться для вычисления функции accept-something используя множители +1 на каждом входе и пороговые значения +1 и –1, хотя практические аппаратные реализации с использованием множителя 0.5 и пороги +0,5 и –0,5 более вероятны.

3.7 Сравнение

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

Равенство

с б — 0 + — + — — 0 — + — + — — +

c = ( a = b )

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

Обратите внимание, что оператор равенства в булевой логике является обратным оператору оператор исключающее или . Здесь дело обстоит иначе! В Клини логика обратный оператор исключающее или отвечает на вопрос «являются ли два операнда равны, насколько вам известно? «На этот вопрос мы может дать окончательный ответ только в том случае, если все входные данные правда или ложь .Напротив, оператор равенства, определенный здесь два неизвестных входа считаются равными.

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

4.1 Каноническая сумма произведений

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

Таблица истинности для консенсуса с нумерацией ячеек

⊠ б — 0 + — — 0 0 0 0 0 0 + 0 0 +

ячеек б — 0 + — 0 1 2 0 3 4 5 + 6 7 8

Каждая ячейка в таблице истинности может быть представлена ​​одним минтермом в выражение суммы произведений функции, как показано ниже:

• ( a ⊠ b )	=	(( a = –1)	∧ ( b = –1)	∧ –1)	-0
  	∨	(( a = –1)	∧ ( b = 0)	∧ 0)	— 1
  	∨	(( a = –1)	∧ ( b = +1)	∧ 0)	— 2
  	∨	(( a = 0)	∧ ( b = –1)	∧ 0)	-3
  	∨	(( a = 0)	∧ ( b = 0)	∧ 0)	-4
  	∨	(( a = 0)	∧ ( b = +1)	∧ 0)	— 5
  	∨	(( a = +1)	∧ ( b = –1)	∧ 0)	— 6
  	∨	(( a = +1)	∧ ( b = 0)	∧ 0)	— 7
  	∨	(( a = +1)	∧ ( b = +1)	∧ +1)	— 8

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

Для наглядности мы включили все 9 минут для функции с двумя входами. мы работаем с. Однако обратите внимание, что один из этих минтермов всегда будет быть ложным (–1), член номер 0. Нам никогда не нужно выписывать этот термин, поскольку он никогда ничего не влияет на ценность функция.Опуская этот термин, мы получаем каноническую сумму произведений. представление нашей функции:

• ( a ⊠ b )	=	(( a = –1)	∧ ( b = 0)	∧ 0)	— 1
  	∨	(( a = –1)	∧ ( b = +1)	∧ 0)	— 2
  	∨	(( a = 0)	∧ ( b = –1)	∧ 0)	-3
  	∨	(( a = 0)	∧ ( b = 0)	∧ 0)	-4
  	∨	(( a = 0)	∧ ( b = +1)	∧ 0)	— 5
  	∨	(( a = +1)	∧ ( b = –1)	∧ 0)	— 6
  	∨	(( a = +1)	∧ ( b = 0)	∧ 0)	— 7
  	∨	(( a = +1)	∧ ( b = +1)	∧ +1)	— 8

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

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

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

4.2 Объединение минтермов

Упрощение функции начинается с поиск в таблице минтермов, проверка каждой тройки из 3 терминов которые отличаются ровно одним из входов функции и имеют одинаковые выход. Для функции с двумя входами тройки мы интересуют: Minterms {0,3,6} {1,4,7} и {2,5,8}, поскольку они отличаются только стоимостью первая переменная и minterms {0,1,2}, {3,4,5} и {6,7,8}, поскольку они различаются только стоимостью вторая переменная.Если есть минтермы, для которых функция вывод не имеет значения, их можно считать равными любому другому значению где такое равенство позволяет комбинировать термины.

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

• ( a ⊠ b )	=	(( a = –1)	∧ ( b = 0)	∧ 0)	— 1 *
  	∨	(( a = –1)	∧ ( b = +1)	∧ 0)	— 2
  	∨	(( a = 0)	∧ ( b = –1)	∧ 0)	— 3 *
  	∨	(( a = 0)	∧ ( b = 0)	∧ 0)	— 4 **
  	∨	(( a = 0)	∧ ( b = +1)	∧ 0)	— 5 *
  	∨	(( a = +1)	∧ ( b = –1)	∧ 0)	— 6
  	∨	(( a = +1)	∧ ( b = 0)	∧ 0)	— 7 *
  	∨	(( a = +1)	∧ ( b = +1)	∧ +1)	— 8
  	∨	(( b = 0)	∧ 0)		— 1, 4, 7
  	∨	(( a = 0)	∧ 0)		— 3, 4, 5

Выше мы уменьшили один столбец (minterms {1,4,7}) и одна строка (minterms {3,4,5}) нашей исходной таблицы истинности.В результате минтерм 4 освещался дважды. Минтермы покрытые двумя сокращениями, которые мы сделали, имели все свои результаты то же самое, поэтому все закрытые минтермы отмечены звездочкой. Все эти сокращения были бы разрешены в обычном логическом минимизация логики.

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

• ( a ⊠ b )	=	(( a = –1)	∧ ( b = 0)	∧ 0)	— 1 *
  	∨	(( a = –1)	∧ ( b = +1)	∧ 0)	— 2 *
  	∨	(( a = 0)	∧ ( b = –1)	∧ 0)	— 3 *
  	∨	(( a = 0)	∧ ( b = 0)	∧ 0)	— 4 **
  	∨	(( a = 0)	∧ ( b = +1)	∧ 0)	— 5 **
  	∨	(( a = +1)	∧ ( b = –1)	∧ 0)	— 6 *
  	∨	(( a = +1)	∧ ( b = 0)	∧ 0)	— 7 **
  	∨	(( a = +1)	∧ ( b = +1)	∧ +1)	— 8
  	∨	(( b = 0)	∧ 0)		— 1, 4, 7
  	∨	(( b = +1)	∧ 0)		— 2, 5, 8
  	∨	(( a = 0)	∧ 0)		— 3, 4, 5
  	∨	(( a = +1)	∧ 0)		— 6, 7, 8

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

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

• ( a ⊠ b )	=	(( a = +1)	∧ ( b = +1)	∧ +1)	— 8
  	∨	(( b = 0)	∧ 0)		— 1, 4, 7
  	∨	(( b = +1)	∧ 0)		— 2, 5, 8
  	∨	(( a = 0)	∧ 0)		— 3, 4, 5
  	∨	(( a = +1)	∧ 0)		— 6, 7, 8

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

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

• ( a ⊠ b )	=	(( a = +1) ∧ ( b = +1) ∧ +1)	— 8
  	∨	(( b ≠ –1) ∧ 0)	— 1, 4, 7, 2, 5, 8
  	∨	(( a ≠ –1) ∧ 0)	— 3, 4, 5, 6, 7, 8

Эта оптимизация не гарантирует окупаемости.Например, если в конечном итоге нам понадобятся и ( a = + 1), и ( a ≠ + 1), необходимость поскольку дополнительная функция декодирования может компенсировать устранение минтерма.

Есть несколько финальных оптимизаций: везде, где мы включили буквальный правда через минуту, мы можем это устранить. Кроме того, в редких случаях, подобных этому примеру, мы можем заменить (( a = + 1) ∧ ( b = + 1)) с ( a ∧ b ). Это возможно только тогда, когда таблица истинности для всей функции покрывает таблицу истинности для мин функция — то есть все термины рассматриваемой функции имеют выходные значения больше или равны соответствующим членам мин. функция.Чистый результат применения этих двух оптимизаций является:

• ( a ⊠ b )	=	( a ∧ b )		— 8
  	∨	(( b ≠ –1) ∧ 0)		— 1, 4, 7, 2, 5, 8
  	∨	(( a ≠ –1) ∧ 0)		— 3, 4, 5, 6, 7, 8

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

Приведенные здесь правила минимизации сопоставимы с правилами, приведенными в [Йоэли и Розенфельд, 1965].В этой работе представлены как 2-х, так и 3-х переменные аналоги карт Карно. как табличные методы. [Кумар и Прия, 2010] также попытался применить карты Карно к троичным функциям, но затем сосредоточился совершенно другой подход к минимизации, пытаясь минимизировать количество мультиплексоров, необходимых в реализации мультиплексорного дерева тернарная функция. Иногда это может быть полезно, но в целом чистая сумма продуктов решений, полученных табличными методами приведено здесь будет производят более быструю логику, потому что количество задержек гейта всегда равно трем, задержка для декодирования, затем одна задержка для минтермов, а затем заключительный max операция, используемая для объединения минтермов.

4.3 Сокращенное обозначение

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

Таблица истинности для консенсуса

входов выходов б a ⊠ b — — — 0 — 0 0 1 — + 0 2 0 — 0 3 0 0 0 4 0 + 0 5 + — 0 6 + 0 0 7 + + + 8

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

Таблица для консенсуса , после двух шагов

входов выходов б a ⊠ b — — — 0 — 0 0 1 * — + 0 2 0 — 0 3 * 0 0 0 4 * * 0 + 0 5 * + — 0 6 + 0 0 7 * + + + 8 0 0 3,4,5 0 0 1,4,7

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

Следующий шаг менее очевиден. Здесь определите тройки строк в таблице истинности, которые имеют выходы 0 или +1 для всех трех значений одной из входных переменных. В этих случаях мы отмечаем строки звездочкой, где на выходе 0 и с x, где вывод равен +1, и мы добавляем новую строку внизу, снова, исключив входную переменную, которая допускала комбинацию и давая ему выход 0.Мы можем сделать это дважды:

Таблица для консенсуса , после четырех шагов

входов выходов б a ⊠ b — — — 0 — 0 0 1 * — + 0 2 * 0 — 0 3 * 0 0 0 4 * * 0 + 0 5 * * + — 0 6 * + 0 0 7 * * + + + 8 x x 0 0 3,4,5 0 0 1,4,7 + 0 6,7,8 + 0 2,5,8

В нашем примере больше невозможно исключить ввод, поэтому теперь мы можем переписать таблицу, удалив все строки с выходными –1, а также отбрасывает все отмеченные звездочкой строки.Строки отмечены с отметками x должны быть сохранены, чтобы вывести на выходе +1, где в противном случае одна из новых строк выдала бы ноль. Мы также удаляем все наши бухгалтерские комментарии на этом этапе, давая следующую упрощенную таблицу:

Таблица для консенсуса , после исключения строки

входов выходов б a ⊠ b + + + 0 0 0 0 + 0 + 0

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

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

4.4 Оценка сложности результата

Когда тернарные функции выражаются в форме суммы произведений, важно отметить, что все ворота min , используемые для декодирования minterms на самом деле являются простыми логическими вентилями и . Переменная все входные данные для этих вентилей являются логическими, либо истинно , либо ложно , с неизвестным значением исключено.Если постоянный вход равен +1, вывод также является логическим. Если постоянный вход равен 0, это не требует использование троичного мин , вернее, постоянный вход служит для зажима вывод между ложным (-1) и неизвестным (0). Таким образом, и гейт, выход которого ограничен этим диапазоном, — это все, что требуется.

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

УРОК №20

УРОК №20

ЛОГИКА ПРЕДЛОЖЕНИЯ

Введение

Щелкните здесь, чтобы пропустить этот напутственный разговор и переходите к обсуждению урока 20.

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

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

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

Если вы один из этих людей, расслабьтесь. Не невозможно сделать ну в этих разделах. На самом деле это ОЧЕНЬ возможно до ace им. Даже для «обычные люди.

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

Следующий совет — не переходить к каждому новому уроку, пока вы не освоитесь и не освоите предыдущие. один. С Урока №20 до конца курса быть постепенным развитием навыков, описанных в каждом разделе. Эти навыки будут развиваться и зависеть от каждого предыдущего раздела. (Именно здесь у большинства студентов возникают проблемы.)

Постарайтесь делать вещи шаг за шагом. Это руководство расскажет вам простой язык , как для выполнения каждой задачи, которую вам нужно выучить.Ты можно получить , почему от Hurley. Надеюсь, вы поймете оба как и почему, но обратите внимание на это:

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

Мое последнее предложение — попрактиковаться в чтении символов. громко.Или хотя бы привыкнуть их правильно думать. IE: «A (B C)» равно «если А тогда и Б, и В «не» А, гм, волнистая штука круглые скобки-doohickie B точка C закрывающие скобки «Большая часть то, что вы узнаете от , интуитивно понятно, и ваш общий смысл тебе очень поможет, если ты что-то отдашь работать с.

УРОК № 20

Символы и перевод

Задание по чтению: 6.1 (стр. 301-309) и стр. 319-322 (Дальнейшее сравнение с обычным языком)

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

Язык P

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

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

Простые утверждения (представленные заглавными буквами) затем могут быть в сочетании с использованием одной из пяти связок (символы) ~ v (см. п. 302) для представления сложных утверждений.

Из пяти связок тильда ~ (отрицание) немного отличается от других тем, что на самом деле «соединять» что угодно, но просто сводит на нет все, что приходит после этого.

Мы также будем использовать круглые скобки (), (и квадратные скобки [] и фигурные скобки {}), чтобы построить правильно сформированный формулы — WFF (произносится как «гавс».. . и вы думали, что у логиков нет чувства юмора. . . (!)) Это знаки препинания языка P. WFF — это предложения этого языка. Когда бы ты не иметь более двух терминов или вы хотите отменить более чем простое заявление, вам нужно будет использовать круглые скобки, чтобы прояснить значение ваших сложных заявлений. Вне скобок вы можете необходимо использовать скобки, а иногда даже могут понадобиться скобки. Должен никогда не может быть более двух простых предложений и одной связки, кроме ~ без пары скобок, разделяющих их.

~ A B не то же самое, что ~ (A B)

(A B) v C не то же самое, что A (B v C), поэтому круглые скобки необходимо, чтобы избежать двусмысленности.

Важно, даже на заочном курсе, вербализовать этих переведенных сложных утверждений:

Предложение		«скажи»
~ А		«не А» или «не так» что A «или» A ложно «
B C		«В и С»
D против E		«D или E»
Ф G		«Если F, то G» или «F» следует G «
H Я		«H, если и только если я»
ПРИМЕЧАНИЕ:
ф. G		F = антецедент условного, «если» часть »или достаточное условие
		G = , следовательно, условного, «затем» часть »или необходимое условие.

ВАЖНО: Определяется тип выписки символом вне скобок. Например, выписка классифицируется как выписка « и » или « конъюнкция », если точка не заключена в скобки.

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

* Обратите внимание, что то, что следует за «если» в условном предложении, будет помещено перед символом, независимо от того, где оно встречается в Заявление на английском языке. Пример: A, если B = B A .Фраза «только если» трактуется иначе. «Только если» всегда предшествует консеквенту на английском языке. Пример: A только если B = A В .

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

~ (A v M) и ~ A ~ M

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

~ A v ~ B и ~ (A Б)

Чтобы понять разницу, может потребоваться некоторое ясное мышление. между «не оба» и «оба не», но есть это очень важное отличие.Задумайтесь над этим некоторое время.

*** Также подумайте о кусочке чтение из раздела 6.2. ***

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

Logic Coach Assignment: 6.1 I all. Сделай II тоже, если ты думаешь, что тебе нужно больше практики.

ЗАДАНИЕ 1 (По восемь баллов)

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

1. Если Джесси опоздает, Бекки разозлится.

2. Кардиналы или Храбрецы выиграют вымпел.

3.Президент является главой государства; но она также Главнокомандующий.

4. Аборт — это то же самое, что и убийство.

5. Если Кэти, Дороти и Джей Си отправятся в отпуск, то Джером останусь дома.

6. Экономика улучшается с увеличением продаж автомобилей.

7. Ни Стив, ни Джошуа не индуисты.

8. СПИД снизится только в том случае, если АЗТ станет недорогим и этого не произойдет.

9. Если Палата представителей и Сенат проголосуют против, либо президент наложит вето, законопроект не пройдет.

10. Если вы одновременно недовольны и вам недоплачивают, вам следует покидать. Если ты счастлив и тебе хорошо платят, тебе стоит остаться. (не не обращайте внимания на термин «комплименты» — вам следует использовать некоторые ~ s)

ЗАДАНИЕ 2 (по два балла)

Какие из следующих не соответствуют правильно сформированным формулы (WFF)? Для приведенных ниже заявлений это , а не . WFF, укажите, в чем проблема.Для тех, что — это WFF, напишите, как бы вы сказали сложное утверждение.

Модель : ~ (D ~ T) v [(S R) V]

«Либо если D, то не T, либо если S и R, затем V «

1. ~ L v (X М)

2. (M v N) v (P v ~ Q)

3. (R S) (~ Т ~ В)

4. (X Y) ~ [V (L M)]

5.(M v N v O) П

6. ~ A (~ B В)

7. [(D E) v F v G] (H v ~ I)

8. ~ (R ~ S) т

9. ~ R v ~ S ~ T

10. ~ (C v D) [(S ~ T) v (E ~ F)]

На главную | Содержание | Следующий Назначение | Вопросы

Логические операции и булевы функции — x-engineer.org

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

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

Большинство физических вычислений выполняется с десятичными числами.Это потому, что мы используем десятичные числа для всех физических величин (например, 10 А, 250 Нм, 120 км и т. Д.). Компьютеры используют двоичные числа для выполнения вычислений. Чтобы вспомнить, как преобразовать десятичное число в двоичное, прочитайте статью Преобразование десятичного числа в двоичное.

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

В наших примерах мы собираемся использовать два символа A и B , которые называются входами . Каждый из них может иметь либо истинное значение ( 1 ), либо ложное значение ( 0 ). После того, как над входами будут выполнены логические операции, мы получим результат с символом Q , который называется output . Аналогично входам, выход Q может иметь только истинное значение ( 1 ) или ложное значение ( 0 ).

Логическое состояние / значение true , также называемое HIGH , эквивалентно двоичному значению 1 . Логическое значение false , также называемое LOW , эквивалентно двоичному значению 0 .

Наиболее распространенными логическими операциями (также называемыми воротами, операторами) являются:

• НЕ
• И
• OR
• NAND
• 03 NAND
• 03 NOR
• XNOR

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

Таблица истинности определяет, как работает логическая (логическая) операция, каково значение выхода Q , функция значения входов A и B .

Элемент НЕ

Логическая операция НЕ также называется инвертором или отрицанием, поскольку она инвертирует логическое значение входа.Например, если A равно true , применение к нему операции NOT даст результат Q как false . Таким же образом, если A является ложным , применение к нему логического элемента НЕ даст результат Q как истинный .

Логический вентиль	Символ ANSI	Символ IEC	Таблица истинности
НЕ			выход	вход			Q = НЕ А
			0	1
			1	0

И вентиль

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

Логический вентиль	Символ ANSI	Символ МЭК	Таблица истинности
И		вход
		вход
		B	Q = A AND B
		0	0	0
		0	1	0
		1	0	0
1	1	1

Логический элемент ИЛИ

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

Логический вентиль	Символ ANSI	Символ МЭК	Таблица истинности
OR		вход
		вход
		B	Q = A OR B
		0	0	0
		0	1	1
		1	0	1
1	1	1

вентиль И-НЕ

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

Логический вентиль	Символ ANSI	Символ IEC	Таблица истинности
NAND			вход
					B	Q = A NAND B
			0	0	1
			0	1	1
			1	0	1
			1	1	0

вентиль ИЛИ

Логическая операция ИЛИ (отрицательное / не ИЛИ) дает истинный выход только тогда, когда на обоих входах ложь , в противном случае — ложь на выходе.Другими словами, если только один или оба входа равны истинно , оператор NOR выдает результат ложь . Вентиль ИЛИ-НЕ является результатом отрицания оператора ИЛИ.

Логический вентиль	Символ ANSI	Символ IEC	Таблица истинности
NOR			вход
			B	Q = A NOR B
			0	0	1
			0	1	0
			1	0	0
			1	1	0

Логический элемент XOR

Логический оператор XOR (произносится как исключающее OR) дает истинный выход только тогда, когда входы имеют разные состояния.Если входы имеют одинаковые логические состояния, либо истина, , либо ложь , вентиль XOR выдает результат ложь . Чтобы вывести результат true , только один из входов должен быть true , другой должен быть false .

Логический вентиль	Символ ANSI	Символ IEC	Таблица истинности
XOR			вход
			B	Q = A XOR B
			0	0	0
			0	1	1
			1	0	1
			1	1	0

вентиль XNOR

Логический оператор XNOR (произносится как исключающее NOR) является логическим дополнением логического элемента XOR.Вывод true является результатом, если входы имеют одинаковое логическое состояние (либо оба true , либо оба false ). Если входы имеют разные логические значения, вентиль XNOR выдает результат ложный результат .

Логический вентиль	Символ ANSI	Символ IEC	Таблица истинности
XNOR			вход
			B	Q = A XNOR B
			0	0	1
			0	1	0
			1	0	0
			1	1	1

Все вышеперечисленные логические операторы (вентили) приведены в таблице ниже.

A	B	И	OR	NAND	NOR	XOR	XNOR
	XNOR
0	1	1	0	1
0	1	0	1	1	0	1	0
1	0	0	1	1	0	1	0
1	1	1	1	0	0	0	1

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