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

редактировать
Алгебра с переменными, содержащими только «истина» и «ложь» (или 1 и 0) в качестве значений

В математика и математическая логика, Булева алгебра - это ветвь алгебры, в которой значения переменных являются значения истинности истина и ложь, обычно обозначаемые 1 и 0 соответственно. Вместо элементарной алгебры, где значения переменных являются числами, а простыми операциями являются сложение и умножение, основными операциями булевой алгебры являются конъюнкция (и), обозначенная как ∧, дизъюнкция (или), обозначенная как ∨, и отрицание (не), обозначенная как ¬. Таким образом, это формализм для описания логических операций так же, как элементарная алгебра описывает числовые операции.

Булеву алгебру представил Джордж Буль в его первой книге «Математический анализ логики» (1847) и более подробно изложил в его Исследование законов мышления (1854 г.). Согласно Хантингтону, термин «булева алгебра» впервые был предложен Шеффером в 1913 году, хотя Чарльз Сандерс Пирс дал название «Булева алгебра с одной константой». "к первой главе его" Простейшей математики "1880 года. Булева алгебра была фундаментальной в развитии цифровой электроники и предусмотрена во всех современных языках программирования. Он также используется в теории множеств и статистике.

Содержание

  • 1 История
  • 2 Значения
  • 3 Операции
    • 3.1 Основные операции
    • 3.2 Вторичные операции
  • 4 Закона
    • 4.1 Монотонные законы
    • 4.2 Немонотонные законы
    • 4.3 Полнота
    • 4.4 Принцип двойственности
  • 5 Схематические представления
    • 5.1 Диаграммы Венна
    • 5.2 Цифровые логические вентили
  • 6 Булевы алгебры
    • 6.1 Конкретные булевы алгебры
    • 6.2 Подмножества как битовые векторы
    • 6.3 Прототипная булева алгебра
    • 6.4 Булевы алгебры: определение
    • 6.5 Представимые булевы алгебры
  • 7 Аксиоматизирующая булева алгебра
  • 8 Логика высказываний
    • 8.1 Приложения
    • 8.2 Дедуктивные системы для логики высказываний
      • 8.2.1 Исчисление последовательностей
  • 9 Приложения
    • 9.1 Компьютеры
    • 9.2 Двузначная логика
    • 9.3 Логические операции
      • 9.3.1 Логический поиск
  • 10 См. Также
  • 11 Ссылки
  • 12 Источники
  • 13 Дополнительная литература
    • 13.1 Историческая перспектива
  • 14 Внешние ссылки

История

A предвестники или булевой алгебры была алгебра понятий Готфрида Вильгельма Лейбница . Алгебра понятий Лейбница дедуктивно эквивалентна булевой алгебре множеств.

Алгебра Буля предшествовала современным разработкам в абстрактной алгебре и математической логике ; однако считается, что он связан с истоками обеих областей. В абстрактной обстановке булева алгебра была усовершенствована в конце 19 века Джевонсом, Шредером, Хантингтоном и другими, пока не достигла современной концепции ( аннотация) математическая структура. Например, эмпирическое наблюдение, что можно манипулировать выражениями в алгебре множеств, переводя их в выражения в алгебре Булевых, объясняется современными терминами, говоря, что алгебра множеств является логическим алгебра (обратите внимание на неопределенный артикль ). Фактически, М. Х. Стоун в 1936 г. доказал, что каждая булева алгебра изоморфна полю множеств.

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

Эффективная реализация из булевых функций - это фундаментальная проблема в разработке цепей комбинационной логики. Современные инструменты автоматизации проектирования электроники для схем СБИС часто полагаются на эффективное представление булевых функций, известных как (сокращенно упорядоченные) диаграммы двоичных решений (BDD) для <365.>логический синтез и формальная проверка.

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

Хотя развитие математической логики не следовало программе Буля, связь между его алгеброй и логикой была позже прочно обосновался в системе алгебраической логики, которая также изучает алгебраические системы многих других логик. Проблема определения того, могут ли быть присвоены переменным данной булевой (пропозициональной) формулы таким образом, чтобы формула оценивалась как истинная, называется проблемой логической выполнимости (SAT), и имеет важное значение для теоретической информатики, будучи первой проблемой, показанной как NP-завершенная. Тесно связанная модель вычислений, известная как логическая схема, связывает временную сложность (алгоритма ) с сложностью схемы.

Значения

В то время как выражения обозначают в основном числа в элементарной алгебре, в булевой алгебре они обозначают значения истинности ложные и истинные. Эти значения представлены битами (или двоичными цифрами), а именно 0 и 1. Они не ведут себя как целые числа 0 и 1, для которых 1 + 1 = 2, но могут быть отождествлены с элементами двухэлементного поля GF (2), то есть целочисленной арифметики по модулю 2, для которой 1 + 1 = 0. Затем играйте сложение и умножение булевы роли XOR (исключающее ИЛИ) и AND (соединение), соответственно, с дизъюнкцией x∨y (включающее ИЛИ), определяемой как x + y - xy.

Булева алгебра также имеет дело с функциями, значения которых находятся в наборе {0, 1}. Для таких функций обычно используется последовательность битов. Другой распространенный пример - это подмножества множества E: для подмножества F из E можно определить индикаторную функцию , которая принимает значение 1 на F и 0 вне F. Самый общий пример - это элементы булевой алгебры , причем все вышеперечисленное является ее экземплярами.

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

Операции

Базовые операции

Основные операции булевой алгебры следующие:

  • AND (конъюнкция ), обозначаемая x∧y (иногда x AND y или Kxy), удовлетворяет x∧y = 1, если x = y = 1, и x∧y = 0 в противном случае.
  • OR(дизъюнкция ), обозначаемая x∨y (иногда x OR y или Axy), удовлетворяет x∨y = 0, если x = y = 0, и x∨ y = 1 в противном случае.
  • НЕ (отрицание ), обозначаемый ¬x (иногда НЕ x, Nx или! x), удовлетворяет ¬x = 0, если x = 1 и ¬x = 1 если x = 0.

В качестве альтернативы значения x∧y, x∨y и ¬x могут быть выражены путем табулирования их значений с помощью таблиц истинности следующим образом:

x {\ displaystyle x }x y {\ displaystyle y}y x ∧ y {\ displaystyle x \ wedge y}x \ wedge y x ∨ y {\ displaystyle x \ vee y}x \ vee y
0000
1001
0101
1111
x {\ displaystyle x}x ¬ x {\ displaystyle \ neg x}\ neg x
01
10

Если значения истинности 0 и 1 интерпретируются как inte Например, эти операции могут быть выражены с помощью обычных операций арифметики (где x + y использует сложение, а xy использует умножение) или функции минимума / максимума:

x ∧ y = xy = min (x, y) x ∨ Y знак равно Икс + Y - ху знак равно макс (х, у) ¬ х = 1 - х {\ Displaystyle {\ begin {выровнено} х \ клин у = ху = \ мин (х, у) \\ х \ ви у = x + y-xy = \ max (x, y) \\\ neg x = 1-x \ end {align}}}{\ displaystyle {\ begin {align} x \ wedge y = xy = \ min ( x, y) \\ x \ vee y = x + y-xy = \ max (x, y) \\\ neg x = 1-x \ end {выровнено}}}

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

x ∧ y = ¬ (¬ x ∨ ¬ y) x ∨ y знак равно ¬ (¬ x ∧ ¬ y) {\ displaystyle {\ begin {выровнено} x \ wedge y = \ neg (\ neg x \ vee \ neg y) \\ x \ vee y = \ neg (\ neg x \ wedge \ neg y) \ end {align}}}{\ begin {align} x \ wedge y = \ neg (\ neg x \ vee \ neg y) \\ x \ vee y = \ neg (\ neg x \ wedge \ neg y) \ end {align}}

Вторичные операции

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

x → y = ¬ x ∨ yx ⊕ y = ¬ (x ≡ y) = (x ∨ y) ∧ (¬ x ∨ ¬ y) = (x ∧ ¬ y) ∨ (¬ x ∧ y) x ≡ y = ¬ (x ⊕ y) = (x ∧ y) ∨ (¬ x ∧ ¬ y) {\ displaystyle {\ begin {align} x \ rightarrow y = \ neg { x} \ vee y \\ x \ oplus y = \ neg (x \ Equiv y) = (x \ vee y) \ wedge (\ neg x \ vee \ neg y) = (x \ wedge \ neg y) \ vee (\ neg x \ wedge y) \\ x \ Equiv y = \ neg {(x \ oplus y)} = (x \ wedge y) \ vee (\ neg x \ wedge \ neg y) \ end {align}} }{\ displaystyle {\ begin {выровнено} x \ rightarrow y = \ neg {x} \ vee y \\ x \ oplus y = \ neg (x \ Equiv y) = (x \ vee y) \ wedge (\ neg x \ vee \ neg y) = (x \ wedge \ neg y) \ vee (\ neg x \ wedge y) \\ x \ Equiv y = \ neg {(x \ oplus y)} = (x \ wedge y) \ vee (\ neg x \ клин \ отр y) \ конец {выровнен}}}

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

Вторичные операции. Таблица 1
x {\ displaystyle x}x y {\ displaystyle y}y x → y {\ displaystyle x \ rightarrow y}x \ rightarrow y x ⊕ y {\ displaystyle x \ oplus y}x \ oplus y x ≡ y {\ displaystyle x \ Equiv y}x \ Equiv y
00101
10010
01110
11101

Первая операция, x → y или Cxy, называется импликацией материала . Если x истинно, тогда значение x → y считается равным y (например, если x истинно, а y ложно, то x → y также ложно). Но если x ложно, то значение y можно игнорировать; однако операция должна возвращать некоторое логическое значение, и есть только два варианта. Таким образом, по определению, x → y истинно, когда x ложно. (логика релевантности предлагает это определение, рассматривая импликацию с ложной предпосылкой как нечто иное, чем истинное или ложное.)

Вторая операция, x ⊕ y, или Jxy, называется исключающим или (часто сокращенно XOR), чтобы отличать его от дизъюнкции как включающего вида. Это исключает возможность того, что оба x и y будут истинными (например, см. Таблицу): если оба истинны, результат будет ложным. С точки зрения арифметики это сложение, где mod 2 равен 1 + 1 = 0.

Третья операция, дополнение исключающего или, является эквивалентностью или логическим равенством: x ≡ y, или Exy, верно только тогда, когда x и y имеют одинаковое значение. Следовательно, x ⊕ y как его дополнение может пониматься как x ≠ y, что верно только тогда, когда x и y различны. Таким образом, его аналог в арифметическом модуле 2 - x + y. Аналог эквивалентности в арифметическом модуле 2 - x + y + 1.

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

законы

A закон булевой алгебры - это тождество, например x ∨ (y ∨ z) = (x ∨ y) ∨ z между двумя логическими терминами, где логический термин определяется как выражение, составленное из переменных и констант 0 и 1 с использованием операций ∧, ∨ и ¬. Концепция может быть расширена до терминов, включающих другие логические операции, такие как ⊕, → и ≡, но такие расширения не нужны для целей, для которых установлены законы. Такие цели включают определение булевой алгебры как любой модели булевых законов, а также в качестве средства для вывода новых законов из старых, как при выводе x∨ (y∧z) = x∨ (z∧y) из y∧z = z∧y (как описано в разделе § Аксиоматизирующая булева алгебра).

Монотонные законы

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

Ассоциативность ∨ {\ displaystyle \ vee}\ vee :x ∨ (y ∨ z) {\ displaystyle x \ vee (y \ vee z) }{\ displaystyle x \ vee (y \ vee z)} = (x ∨ y) ∨ z {\ displaystyle = (x \ vee y) \ vee z}{\ displaystyle = (x \ vee y) \ vee z}
ассоциативность ∧ {\ displaystyle \ wedge}\ клин :x ∧ (y ∧ z) {\ displaystyle x \ wedge (y \ wedge z)}{\ displaystyle x \ wedge (y \ wedge z)} = (x ∧ y) ∧ z {\ displaystyle = (x \ wedge y) \ wedge z}{\ displ aystyle = (x \ клин y) \ клин z}
Коммутативность ∨ {\ displaystyle \ vee}\ vee :x ∨ y {\ displaystyle x \ vee y}x \ vee y = y ∨ x {\ displaystyle = y \ vee x}{\ displaystyle знак равно y \ vee x}
Коммутативность ∧ {\ displaystyle \ wedge}\ клин :Икс ∧ Y {\ Displaystyle x \ wedge y}x \ wedge y = y ∧ x {\ displaystyle = y \ wedge x}{\ displaystyle = y \ wedge x}
Распределимость ∧ {\ displaystyle \ wedge}\ клин над ∨ {\ displaystyle \ vee}\ vee :x ∧ (y ∨ z) {\ displaystyle x \ wedge (y \ vee z)}{\ displaystyle x \ wedge (y \ vee z)} = (x ∧ y) ∨ (x ∧ z) { \ displaystyle = (x \ wedge y) \ vee (x \ wedge z)}{\ displaystyle = (x \ wedge y) \ vee (x \ wedge z)}
Идентичность для ∨ {\ displaystyle \ vee}\ vee :x ∨ 0 {\ displaystyle x \ vee 0}{\ displaystyle x \ vee 0} = x {\ displaystyle = x}= x
Идентификация для ∧ {\ displaystyle \ wedge}\ клин :x ∧ 1 {\ displaystyle x \ wedge 1}{\ displaystyle x \ wedge 1} = x {\ displaystyle = x}= x
аннигилятор для ∧ {\ displaystyle \ wedge}\ клин :x ∧ 0 {\ displaystyle x \ wedge 0}{\ displaystyle x \ wedge 0} = 0 {\ displaystyle = 0}= 0

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

Аннигилятор для ∨ {\ displaystyle \ vee}\ vee :x ∨ 1 {\ displaystyle x \ vee 1}{\ displaystyle x \ vee 1} = 1 {\ displaystyle = 1}= 1
Idempotence of ∨ {\ displaystyle \ vee}\ vee :x ∨ x {\ displaystyle x \ vee x}{\ displaystyle x \ vee x} = x {\ displaystyle = x}= x
Idempotence of ∧ {\ displaystyle \ wedge}\ клин :x ∧ x {\ displaystyle x \ wedge x}{\ displaystyle x \ wedge x} = x {\ displaystyle = x}= x
Поглощение 1:x ∧ (x ∨ y) {\ displaystyle x \ wedge (x \ vee y)}{\ displaystyle x \ wedge (x \ vee y)} = x {\ displaystyle = x }= x
Поглощение 2:x ∨ (x ∧ y) {\ displaystyle x \ vee (x \ wedge y)}{\ displaystyle x \ vee (x \ wedge y)} = x {\ displaystyle = x}= x
Распределимость ∨ {\ displaystyle \ vee}\ vee над ∧ {\ displaystyle \ wedge}\ клин :x ∨ (y ∧ z) {\ displaystyle x \ vee (y \ wedge z)}{\ displaystyle x \ vee (y \ wedge z)} = (х ∨ у) ∧ ( x ∨ z) {\ displaystyle = (x \ vee y) \ wedge (x \ vee z)}{\ displaystyle = (x \ vee y) \ wedge (x \ vee z)}

Принятие x = 2 в третьем законе выше показывает, что это не обычный закон алгебры, поскольку 2 × 2 = 4. Остальные пять законов могут быть опровергнуты в обычной алгебре, если принять все переменные равными 1. Например, в Законе поглощения 1 левая часть будет 1 (1 + 1) = 2, а правая часть будет 1 (и так далее).

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

Законы немонотонности

Операция дополнения определяется следующими двумя законами.

Дополнение 1 x ∧ ¬ x = 0 Дополнение 2 x ∨ ¬ x = 1 {\ displaystyle {\ begin {align} {\ text {Complementation 1}} x \ wedge \ neg x = 0 \\ {\ text {Дополнение 2}} x \ vee \ neg x = 1 \ end {align}}}{\ begin {выровнено} {\ text {Дополнение 1}} x \ wedge \ neg x = 0 \\ {\ text {Дополнение 2}} x \ vee \ neg x = 1 \ end {выровнено }}

Все свойства отрицания, включая законы ниже, вытекают только из двух вышеуказанных законов.

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

Двойное отрицание ¬ (¬ x) = x {\ displaystyle {\ begin {align} { \ text {Двойное отрицание}} \ neg {(\ neg {x})} = x \ end {align}}}{\ begin {align} {\ text {двойное отрицание}} \ neg {(\ neg { x})} = x \ end {align}}

Но в то время как обычная алгебра удовлетворяет двум законам

(- x) (- y) знак равно ху (- х) + (- у) = - (х + у) {\ Displaystyle {\ begin {выровнено} (- х) (- у) = ху \\ (- х) + (- у) = - (x + y) \ end {align}}}{\ begin {align} (- x) (- y) = xy \\ (- x) + (- y) = - (x + y) \ end {align}}

Булева алгебра удовлетворяет законам Де Моргана :

Де Морган 1 ¬ x ∧ ¬ y = ¬ (x ∨ y) Де Морган 2 ¬ x ∨ ¬ y знак равно ¬ (Икс ∧ Y) {\ Displaystyle {\ begin {выровнено} {\ text {Де Морган 1}} \ neg x \ клин \ п например, y = \ neg {(x \ vee y)} \\ {\ text {De Morgan 2}} \ neg x \ vee \ neg y = \ neg {(x \ wedge y)} \ end {выровнено} }}{\ begin {align} {\ text {Де Морган 1}} \ neg x \ wedge \ neg y = \ neg {(x \ vee y)} \\ {\ text {De Morgan 2}} \ neg x \ vee \ neg y = \ neg {(x \ wedge y)} \ end {align}}

Полнота

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

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

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

Принцип двойственности

Принцип: если {X, R} является poset, то {X, R (инверсия)} также является poset.

Нет ничего волшебного в выборе символов для значений булевой алгебры. Мы могли бы переименовать 0 и 1 в α и β, и если бы мы делали это последовательно на всем протяжении, это все равно была бы булевой алгеброй, хотя и с некоторыми очевидными косметическими различиями.

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

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

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

Одно изменение, которое нам не нужно было вносить в рамках этого обмена, - это дополнение. Мы говорим, что дополнение - это самодвойственная операция. Операция идентичности или бездействия x (копирование ввода в вывод) также является самодвойственной. Более сложным примером самодвойственной операции является (x∧y) ∨ (y∧z) ∨ (z∧x). Не существует самодвойственной бинарной операции, которая зависит от обоих ее аргументов. Композиция самодуальных операций является самодвойственной операцией. Например, если f (x, y, z) = (x∧y) ∨ (y∧z) ∨ (z∧x), то f (f (x, y, z), x, t) является самостоятельным -двойная операция четырех аргументов x, y, z, t.

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

Диаграммы

Диаграммы Венна

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

Три диаграммы Венна на рисунке ниже представляют соответственно конъюнкцию x∧y, дизъюнкцию x∨y и дополнение ¬x.

Рисунок 2. Диаграммы Венна для конъюнкции, дизъюнкции и дополнения

Для конъюнкции область внутри обоих кругов заштрихована, чтобы указать, что x∧y равно 1, когда обе переменные равны 1. Остальные области оставлены незатененными, чтобы указать что x∧y равно 0 для остальных трех комбинаций.

Вторая диаграмма представляет дизъюнкцию x∨y путем закрашивания тех областей, которые лежат внутри одной или обеих окружностей. Третья диаграмма представляет собой дополнение ¬x, заштриховав область вне круга.

Хотя мы не показали диаграммы Венна для констант 0 и 1, они тривиальны, представляя собой соответственно белый и темный прямоугольники, ни одна из которых не содержит круга. Однако мы могли бы поместить кружок для x в эти поля, и в этом случае каждый будет обозначать функцию одного аргумента, x, которая возвращает то же значение независимо от x, называемую постоянной функцией. Что касается их выходных данных, константы и постоянные функции неотличимы; разница в том, что константа не принимает аргументов, что называется нулевой или нулевой операцией, тогда как постоянная функция принимает один аргумент, который она игнорирует, и является унарной операцией.

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

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

Чтобы увидеть первый закон поглощения, x∧ (x∨y) = x, начните с диаграммы в середине для x∨y и обратите внимание, что часть заштрихованной области, общая с кружком x, равна весь круг x. Для второго закона поглощения, x∨ (x∧y) = x, начните с левой диаграммы для x∧y и обратите внимание, что затенение всего круга x приводит к затенению только круга x, поскольку предыдущее затенение было внутри круг x.

Закон двойного отрицания можно увидеть, дополнив затенение на третьей диаграмме для ¬x, которое закрашивает круг x.

Чтобы визуализировать первый закон Де Моргана, (¬x) ∧ (¬y) = ¬ (x∨y), начните со средней диаграммы для x∨y и дополните ее штриховкой так, чтобы только область вне оба круга заштрихованы, что и описывает правая часть закона. Результат такой же, как если бы мы закрасили ту область, которая находится как за пределами круга x, так и за пределами круга y, то есть соединение их внешних сторон, что описывает левая часть закона.

Второй закон Де Моргана, (¬x) ∨ (¬y) = ¬ (x∧y), работает таким же образом, но две диаграммы меняются местами.

Первый закон дополнения, x∧¬x = 0, гласит, что внутренняя и внешняя части круга x не перекрываются. Второй закон дополнения, x∨¬x = 1, говорит, что все находится либо внутри, либо вне круга x.

Цифровые логические вентили

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

Слева направо: И, OR и НЕ вентили.

Линии слева от каждого вентиля представляют входные провода или порты. Значение входа представлено напряжением на проводе. Для так называемой логики «активно-высокий» 0 представлен напряжением, близким к нулю или «землей», а 1 представлен напряжением, близким к напряжению питания; active-low меняет это положение. Линия справа от каждого затвора представляет выходной порт, который обычно соответствует тем же правилам напряжения, что и входные порты.

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

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

DeMorganGates.GIF

В более общем плане можно дополнить любой из восьми подмножеств трех портов логического элемента И или ИЛИ. Результирующие шестнадцать возможностей приводят только к восьми булевым операциям, а именно к тем, у которых нечетное число единиц в их таблице истинности. Таких восемь, потому что «нечетный бит» может быть либо 0, либо 1 и может занимать любую из четырех позиций в таблице истинности. Имеется шестнадцать двоичных логических операций, поэтому в их таблицах истинности должно остаться восемь операций с четным числом единиц. Две из них - это константы 0 и 1 (как двоичные операции, игнорирующие оба их входа); четыре - это операции, которые нетривиально зависят ровно от одного из двух входов, а именно x, y, ¬x и ¬y; а оставшиеся два - это x⊕y (XOR) и его дополнение x≡y.

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

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

Конкретные булевы алгебры

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

(Кстати, исторически X сам должен был быть непустым, а также исключать вырожденные или -элементная булева алгебра, которая является единственным исключением из правила, согласно которому все булевы алгебры удовлетворяют одним и тем же уравнениям, поскольку вырожденная алгебра удовлетворяет всем уравнениям. Однако это исключение противоречит предпочтительному чисто эквациональному определению "булевой алгебры", поскольку нет возможности исключить одноэлементную алгебру, используя только уравнения - 0 ≠ 1 не считается, поскольку это отрицательное уравнение. Следовательно, современные авторы допускают вырожденную булеву алгебру и пусть X будет пустым.)

Пример 1. набор мощности 2 из X, состоящий из всех подмножеств X. Здесь X может быть любым набором: пустым, конечным, бесконечным или даже uncoun table.

Пример 2. Пустое множество и X. Эта двухэлементная алгебра показывает, что конкретная булева алгебра может быть конечной, даже если она состоит из подмножеств бесконечного множества. Можно видеть, что каждое поле подмножеств X должно содержать пустое множество и X. Следовательно, не может быть меньшего примера, кроме вырожденной алгебры, полученной путем взятия X пустым так, чтобы пустое множество и X совпадали.

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

Пример 4. В качестве менее тривиального примера вывода, сделанного в Примере 2, рассмотрим диаграмму Венна, образованную n замкнутыми кривыми , разбивающими диаграмму на 2 области, и пусть X будет (бесконечным) множеством всех точек на плоскости не на какой-либо кривой, а где-то внутри диаграммы. Таким образом, внутренность каждой области представляет собой бесконечное подмножество X, и каждая точка в X находится ровно в одной области. Тогда множество всех двух возможных объединений регионов (включая пустое множество, полученное как объединение пустого множества регионов, и X, полученное как объединение всех двух регионов) замкнуто относительно объединения, пересечения и дополнения относительно X и, следовательно, образует конкретную булеву алгебру. Снова у нас есть конечное число подмножеств бесконечного множества, образующего конкретную булеву алгебру, причем пример 2 возникает как случай n = 0 отсутствия кривых.

Подмножества как битовые векторы

Подмножество Y из X может быть идентифицировано с помощью индексированного семейства битов с набором индексов X, с битом индексируется x ∈ X, равным 1 или 0, в зависимости от того, является ли x ∈ Y или нет. (Это так называемая характеристическая функция понятие подмножества.) Например, 32-битное компьютерное слово состоит из 32 бита, индексированные набором {0,1,2,..., 31}, причем 0 и 31 индексируют биты младшего и высокого порядка соответственно. Для меньшего примера, если X = {a, b, c}, где a, b, c рассматриваются как битовые позиции в этом порядке слева направо, восемь подмножеств {}, {c}, {b}, {b, c}, {a}, {a, c}, {a, b} и {a, b, c} X могут быть идентифицированы соответствующими битовыми векторами 000, 001, 010, 011, 100, 101, 110 и 111. Битовые векторы, проиндексированные набором натуральных чисел, представляют собой бесконечные последовательности битов, в то время как векторы, индексированные вещественными в единичном интервале [0, 1] упакованы слишком плотно, чтобы можно было писать обычным способом, но, тем не менее, образуют четко определенные индексированные семейства (представьте, что каждая точка интервала [0,1] окрашивается в черный или белый цвет независимо; черные точки затем образуют произвольное подмножество [ 0,1]).

С этой точки зрения битового вектора конкретная булева алгебра может быть эквивалентно определена как непустой набор битовых векторов одинаковой длины (в более общем смысле, индексированных одним и тем же набором) и закрытых операциями с битовым вектором поразрядный ∧, ∨ и ¬, как в 1010∧0110 = 0010, 1010∨0110 = 1110 и ¬1010 = 0101, реализация битового вектора пересечения, объединения и дополнения соответственно.

Прототипная логическая алгебра

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

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

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

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

Булевы алгебры: определение

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

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

A Булева алгебра - это любое множество с двоичными операциями ∧ и ∨ и унарной операцией ¬ над ними, удовлетворяющее логическим законам.

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

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

A Булева алгебра представляет собой дополненную дистрибутивную решетку.

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

Представимые булевы алгебры

Хотя каждая конкретная булева алгебра является булевой алгеброй, не все булевы алгебры gebra нужно быть конкретным. Пусть n будет положительным целым числом без квадратов, которое не делится на квадрат целого числа, например 30, но не 12. Операции наибольшего общего делителя, наименьшего общее кратное и деление на n (то есть ¬x = n / x), как можно показать, удовлетворяют всем булевым законам, когда их аргументы превышают положительные делители n. Следовательно, эти дивизоры образуют булеву алгебру. Эти делители не являются подмножествами множества, что делает делители n булевой алгеброй, которая не является конкретной согласно нашим определениям.

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

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

На следующий очевидный вопрос дан положительный ответ.

Каждая булева алгебра представима.

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

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

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

Аксиоматизирующая булева алгебра

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

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

Можно ли еще сократить этот список? Опять же, да. Начнем с того, что некоторые из вышеперечисленных законов подразумеваются некоторыми другими. Достаточное подмножество вышеупомянутых законов состоит из пар законов ассоциативности, коммутативности и поглощения, дистрибутивности ∧ над (или другого закона дистрибутивности - достаточно одного) и двух законов дополнения. Фактически это традиционная аксиоматизация булевой алгебры как дополненной дистрибутивной решетки.

. Введение дополнительных законов, не перечисленных выше, становится возможным еще больше сократить список. В 1933 году Эдвард Хантингтон показал, что если в качестве базовых операций взять x∨y и ¬x, то x∧y считается производной операцией (например, с помощью закона Де Моргана в форме x∧y = ¬ (¬x∨¬y)), то уравнение ¬ (¬x∨¬y) ¬ (¬x∨y) = x вместе с двумя уравнениями, выражающими ассоциативность и коммутативность ∨ полностью аксиоматизированной булевой алгебры. Когда единственной базовой операцией является двоичная операция И-НЕ ¬ (x∧y), Стивен Вольфрам предложил в своей книге A New Kind of Science единую аксиому ((xy) z) (x ((xz) x)) = z как аксиоматизация с одним уравнением булевой алгебры, где для удобства здесь xy обозначает И-НЕ, а не И-x и y.

Логика высказываний

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

Синтаксически каждый логический член соответствует пропозициональной формуле пропозициональной логики. В этом переводе между булевой алгеброй и логикой высказываний булевы переменные x, y... становятся пропозициональными переменными (или атомами ) P, Q,..., Логические термины, такие как x∨y, становятся пропозициональными формулами P∨Q, 0 становится ложным или ⊥, а 1 становится истинным или T . При обращении к общим предложениям удобно использовать греческие буквы Φ, Ψ,... как метапеременные (переменные вне языка исчисления высказываний, используемые при разговоре о пропозициональном исчислении) для обозначения предложений.

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

Эта семантика допускает перевод между тавтологиями логики высказываний и эквациональными теоремами булевой алгебры. Всякая тавтология Φ логики высказываний может быть выражена как булево уравнение Φ = 1, которое будет теоремой булевой алгебры. Наоборот, каждая теорема Φ = Ψ булевой алгебры соответствует тавтологиям (Φ∨¬Ψ) ∧ (¬Φ∨Ψ) и (Φ∧Ψ) ∨ (¬Φ∧¬Ψ). Если → на языке, эти последние тавтологии также могут быть записаны как (Φ → Ψ) ∧ (Ψ → Φ) или как две отдельные теоремы Φ → Ψ и Ψ → Φ; если имеется available, то можно использовать единственную тавтологию Φ ≡ Ψ.

Приложения

Одним из мотивирующих приложений исчисления высказываний является анализ предложений и дедуктивных аргументов на естественном языке. В то время как утверждение «если x = 3, то x + 1 = 4» зависит от значений таких символов, как + и 1, утверждение «если x = 3, то x = 3» - нет; это верно только в силу своей структуры и остается верным независимо от того, заменяется ли «x = 3» на «x = 4» или «луна сделана из зеленого сыра». Общая или абстрактная форма этой тавтологии - «если P, то P», или на языке булевой алгебры «P → P».

Замена P на x = 3 или любое другое предложение называется реализацией P этим предложением. Результат инстанциирования P в абстрактном предложении называется экземпляром предложения. Таким образом, «x = 3 → x = 3» является тавтологией в силу того, что является примером абстрактной тавтологии «P → P». Все вхождения конкретной переменной должны быть конкретизированы с одним и тем же предложением, чтобы избежать такой бессмыслицы, как P → x = 3 или x = 3 → x = 4.

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

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

Дедуктивные системы для логики высказываний

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

Последовательное исчисление

Исчисление высказываний обычно организована как система Гильберта, операции которой аналогичны операциям булевой алгебры, а теоремы являются булевыми тавтологиями, эти булевы члены равны булевой константе 1. Другой формой является исчисление секвенций, которое имеет два вида пропозиций, как в обычном исчислении высказываний, и пары списков пропозиций, называемых секвентами, например A∨B, A∧C,... ⊢ {\ displaystyle \ vdash}\ vdash A, B → C,.... Две половины секвенции называются антецедентом и преемником соответственно. Обычной метапеременной, обозначающей антецедент или его часть, является Γ, а для преемника Δ; таким образом, Γ, A ⊢ {\ displaystyle \ vdash}\ vdash Δ будет обозначать секвенцию, преемником которой является список Δ, а антецедентом является список Γ с дополнительным предложением A, добавленным после него. Антецедент интерпретируется как соединение его предложений, преемник как дизъюнкция его предложений, а сама секвенция как влечение преемника антецедентом.

Вступление отличается от импликации тем, что, в то время как последняя является бинарной операцией, возвращающей значение в булевой алгебре, первая представляет собой бинарное отношение, которое либо выполняется, либо не выполняется. В этом смысле следствие - это внешняя форма импликации, то есть внешняя по отношению к булевой алгебре, когда мы думаем о читателе секвенции как о внешнем и интерпретируем и сравниваем антецеденты и последователи в некоторой булевой алгебре. Естественная интерпретация ⊢ {\ displaystyle \ vdash}\ vdash - это как ≤ в частичном порядке булевой алгебры, определяемом как x ≤ y, как раз тогда, когда x∨y = y. Эта способность сочетать внешнюю импликацию ⊢ {\ displaystyle \ vdash}\ vdash и внутреннюю импликацию → в одной логике - одно из существенных различий между последовательным исчислением и пропозициональным исчислением.

Приложения

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

Компьютеры

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

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

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

Компьютеры используют логические схемы с двумя значениями по указанным выше причинам. Наиболее распространенные компьютерные архитектуры используют упорядоченные последовательности логических значений, называемые битами, из 32 или 64 значений, например 011010001101011001010101001011. При программировании на машинном коде, языке ассемблера и некоторых других языках программирования программисты работают с низкоуровневой цифровой структурой данных . регистры. Эти регистры работают на напряжениях, где ноль вольт представляет Логическое 0, и опорное напряжение (часто + 5V + 3.3V, + 1,8В) представляет собой булеву 1. Такие языки поддерживают как числовые операции и логические операции. В этом контексте «числовой» означает, что компьютер обрабатывает последовательности битов как двоичные числа (числа с основанием два) и выполняет арифметические операции, такие как сложение, вычитание, умножение или деление. «Логический» относится к булевым логическим операциям дизъюнкции, конъюнкции и отрицания между двумя последовательностями битов, в которых каждый бит в одной последовательности просто сравнивается со своим аналогом в другой последовательности. Поэтому программисты имеют возможность работать и применять правила числовой алгебры или булевой алгебры по мере необходимости. Основным отличительным признаком этих семейств операций является наличие операции переноса в первом, но не во втором.

Двузначная логика

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

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

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

Двузначная логика может быть расширена до многозначной логики, в частности, путем замены логической области {0, 1} единичным интервалом [0,1], и в этом случае скорее чем принимать только значения 0 или 1, можно принять любое значение от 0 до 1 включительно. Алгебраически отрицание (НЕ) заменяется на 1 - x, соединение (AND) заменяется умножением (xy {\ displaystyle xy}xy ), а дизъюнкция (OR) определяется через Закон Де Моргана. Интерпретация этих значений как логических значений истинности дает многозначную логику, которая формирует основу для нечеткой логики и вероятностной логики. В этих интерпретациях ценность интерпретируется как «степень» истинности - насколько истинно предложение или вероятность того, что предложение истинно.

Логические операции

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

В естественных языках, таких как английский, есть слова для нескольких логических операций, в частности соединения (и), дизъюнкции (или), отрицания (не) и импликации (подразумевает). Но не является синонимом и не является. Когда они используются для объединения ситуативных утверждений, таких как «блок на столе» и «кошки пьют молоко», которые наивно истинны или ложны, значения этих логических связок часто имеют значение их логических аналоги. Однако при описании поведения, такого как «Джим прошел через дверь», можно заметить различия, такие как нарушение коммутации, например соединение «Джим открыл дверь» с «Джим прошел через дверь» в этом порядке не эквивалентно их соединению в другом порядке, поскольку и в таких случаях обычно означает and then. Вопросы могут быть похожие: порядок «Небо голубое, а почему небо голубое?» имеет больше смысла, чем обратный порядок. Конъюнктивные команды о поведении подобны поведенческим утверждениям, например, одеться и пойти в школу. Дизъюнктивные команды, такие как люби меня, или оставь меня, или лови рыбу, или нарежь наживку, имеют тенденцию быть асимметричными из-за того, что одна альтернатива менее предпочтительна. Сочлененные существительные, такие как чай и молоко, обычно описывают объединение как соединение множества, тогда как чай или молоко являются выбором. Однако контекст может перевернуть эти чувства, поскольку ваш выбор - кофе и чай, что обычно означает то же самое, что и ваш выбор - кофе или чай (альтернативы). Двойное отрицание, например, «Я не люблю молоко», редко означает буквально «Я люблю молоко», а скорее выражает некую ограниченность, как бы подразумевая, что существует третья возможность. «Not not not P» можно в общих чертах интерпретировать как «конечно P», и хотя P обязательно подразумевает «not not P», обратное утверждение в английском языке подозрительно, так же как и с интуиционистской логикой. Ввиду весьма своеобразного использования союзов в естественных языках, булева алгебра не может считаться надежной основой для их интерпретации.

Логические операции используются в цифровой логике для объединения битов, переносимых по отдельным проводам, тем самым интерпретируя их по {0,1}. Когда вектор из n идентичных двоичных вентилей используется для объединения двух битовых векторов, каждый из n битов, отдельные битовые операции могут пониматься вместе как одна операция над значениями из логической алгебры с 2 элементами.

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

256-элементная свободная булевская алгебра на трех генераторах развернута в компьютерных дисплеях на основе растровой графики, которые используют двоичный бит для управления целые области, состоящие из пикселей, полагаясь на логические операции, чтобы указать, как исходная область должна быть объединена с целевым, обычно с помощью третьей области, называемой маской. Современные видеокарты предлагают для этой цели все 2 = 256 троичных операций, причем выбор операции является однобайтовым (8-битным) параметром. Константы SRC = 0xaa или 10101010, DST = 0xcc или 11001100 и MSK = 0xf0 или 11110000 позволяют записывать логические операции, такие как (SRC ^ DST) MSK (что означает XOR источника и назначения, а затем результат AND с маской) непосредственно как константа, обозначающая байт, вычисленный во время компиляции, 0x60 в примере (SRC ^ DST) и MSK, 0x66, если просто SRC ^ DST, и т. д. Во время выполнения видеокарта интерпретирует байт как растровую операцию, указанную исходным выражением единообразно, что требует очень мало оборудования и времени, полностью независимого от сложности выражения.

Твердотельное моделирование Системы для автоматизированного проектирования предлагают множество методов для построения объектов из других объектов, одним из которых является комбинация с помощью логических операций. В этом методе пространство, в котором существуют объекты, понимается как набор S из вокселей (трехмерный аналог пикселей в двумерной графике), а формы определяются как подмножества S, что позволяет объектам быть объединены в виде наборов через объединение, пересечение и т. д. Одно очевидное использование - создание сложной формы из простых форм просто как объединение последних. Другое применение - скульптура, понимаемая как удаление материала: любые операции шлифования, фрезерования, фрезерования или сверления, которые могут быть выполнены с помощью физического оборудования на физических материалах, могут быть смоделированы на компьютере с помощью логической операции x ∧ ¬y или x - y, что в теории множеств является разностью множеств, удалите элементы y из элементов x. Таким образом, даны две формы, одна из которых должна быть обработана, а другая - материал, который необходимо удалить, результат механической обработки первой для удаления последней описывается просто как их установленная разница.

Логический поиск

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

  • Двойные кавычки используются для объединения слов, разделенных пробелами, в один поисковый запрос.
  • Пробелы используются для указания логического И, так как это значение по умолчанию оператор для объединения условий поиска:
"Поисковый запрос 1" "Поисковый запрос 2"
  • Ключевое слово OR используется для логического OR:
"Поисковый запрос 1" OR "Поисковый запрос 2"
  • A с префиксом знак минус используется для логического НЕ:
«Поисковый запрос 1» - «Поисковый запрос 2»

См. также

  • значок Математический портал

Ссылки

Источники

  • Мано, Моррис; Чилетти, Майкл Д. (2013). Цифровой дизайн. Пирсон. ISBN 978-0-13-277420-8.

Дополнительная литература

  • J. Элдон Уайтситт (1995). Булева алгебра и ее приложения. Courier Dover Publications. ISBN 978-0-486-68483-3.Подходящее введение для студентов в прикладных областях.
  • Двинджер, Филип (1971). Введение в булевы алгебры. Вюрцбург: Physica Verlag.
  • Sikorski, Roman (1969). Булевы алгебры (3 / е изд.). Берлин: Springer-Verlag. ISBN 978-0-387-04469-9.
  • Бохенский, Юзеф Мария (1959). Краткое изложение математической логики. Перевод Отто Берда с французского и немецкого изданий. Дордрехт, Южная Голландия: Д. Рейдел.

Историческая перспектива

Внешние ссылки

В Wikibook Как искать есть страница по теме: Логическая логика
В Викибуке Электроника есть страница по теме: Булевой алгебры
Последняя правка сделана 2021-05-13 14:35:32
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте