Редактор схемы логических элементов

Введение в булевую алгебру

В 1854 году Джордж Буль провел исследование «законов мышления», которые основывались на упрощенной версии теории «групп» или «множеств», и из этого была выведена булевая алгебра.

Булева алгебра имеет дело, главным образом, с теорией, согласно которой логические операции и операции над множествами являются либо «ИСТИННЫМИ», либо «ЛОЖНЫМИ», но не обеими одновременно.

Например, A + A = A, а не 2A, как это было бы в обычной алгебре. Булева алгебра — это простой и эффективный способ представления действия переключения стандартных логических вентилей, а основные логические операторы, которые нас здесь интересуют, задаются операциями логических вентилей функций И , ИЛИ и НЕ.

Таблицы истинности для основных двоичных логических функций

В программировании:

• Конъюнкция = AND = И = ∧{\displaystyle \land } = &
• Дизъюнкция = OR = ИЛИ = ∨{\displaystyle \lor } = |
• Сложение по модулю 2 = XOR = ИСКЛЮЧАЮЩЕЕ ИЛИ = ⊕{\displaystyle \oplus } = ~
• Отрицание = NOT = НЕ = ¬{\displaystyle \neg } = !

Формальная логика

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

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

• отрицание;
• ограничение;
• обобщение;

К операциям, которые связаны преимущественно с объёмами понятий, относятся:

• логическое сложение;
• логическое умножение;
• логическое вычитание.

Данные операции могут быть записаны математически с помощью теории множеств.

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

Таблицы истинности для основных двоичных логических функций

В программировании:

• Конъюнкция = AND = И = ∧{\displaystyle \land } = &
• Дизъюнкция = OR = ИЛИ = ∨{\displaystyle \lor } = |
• Сложение по модулю 2 = XOR = ИСКЛЮЧАЮЩЕЕ ИЛИ = ⊕{\displaystyle \oplus } = ~
• Отрицание = NOT = НЕ = ¬{\displaystyle \neg } = !

Логическая функция «НЕ И»

Функция «НЕ И» представляет собой комбинацию двух отдельных логических функций, функции «И» и функции «НЕ» последовательно. Логическая функция «НЕ И» может быть выражена логическим выражением AB (с верхней чертой)

Функция логического «НЕ И» генерирует выход, только когда «ЛЮБЫЕ» из ее входов отсутствуют, и в терминах булевой алгебры выход будет ИСТИНА, только когда любой из ее входов ЛОЖЬ (0).

Представление функции «НЕ И» на схеме

Таблица истинности для функции «НЕ И» противоположна таблице для предыдущей функции «И», потому что элемент «НЕ И» выполняет обратную операцию элемента «И». Другими словами, элемент «НЕ И» является дополнением элемента «И».

Таблица истинности для функции «НЕ И»

Логика «НЕ И» используется в качестве основных «строительных блоков», чтобы построить другие функции логического элемента и доступны в стандартных IC пакетов, такие как общий TTL — 74LS00 Четырехместный 2-входной «НЕ И» элемент, TTL — 74LS10 Тройной 3-входной «НЕ И» элемент или 74LS20 Двойной 4-х входной «НЕ И» элемент. Есть даже один чип 74LS30 с 8 входами «НЕ И» элемента.

Побитовые логические операции

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

В некоторых языках программирования названия операторов, соответствующих логическим и побитовым логическим операциям, похожи. Кроме того, язык программирования может допускать числового типа к логическому и наоборот. В таких языках программирования необходимо внимательно следить за использованием логических и побитовых операций, перемешивание которых может привести к ошибкам. Например, в C++ результатом выражения «2 && 1» (логическое И) является булево значение true, а результатом выражения «2 & 1» (побитовое И) — целое значение .

Побитовое отрицание (NOT)

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

Побитовое «И» (AND)

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

Пример.

Побитовое «ИЛИ» (OR)

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

Пример.

Исключающее «ИЛИ» (XOR)

Основная статья: Сложение по модулю 2

Исключающее« ИЛИ» (или сложение по модулю 2) — это бинарная операция, результат действия которой равен 1, если число складываемых единичных битов нечётно и равен 0, если чётно. Другими словами, если оба соответствующих бита операндов равны между собой, двоичный разряд результата равен 0; в противном случае, двоичный разряд результата равен 1.

Пример.

Первое русское название операции обусловлено тем, что результат данной операции отличается от результата «ИЛИ» только в одном случае из 4 случаев входа — обоих 1 (случай одновременной истинности аргументов «исключается»). Ещё в русской грамматике значение данной логической связки передаётся союзом «либо».

Второе название — тем, что действительно является сложением в кольце вычетов по модулю два, из чего следуют некоторые интересные свойства. Например, в отличие от вышеописанных «И» и «ИЛИ», данная операция является обратимой, или инволютивной: (x⊕y)⊕y=x{\displaystyle (x\oplus y)\oplus y=x}.

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

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

Другие побитовые логические операции

В распространённых языках программирования встроенными средствами реализуются только четыре побитовые логические операции: И, ИЛИ, НЕ и исключающее ИЛИ. Для задания произвольной побитовой логической операции вполне достаточно перечисленных, и, более того, как следует из теории булевых функций, можно ограничиться ещё меньшим набором базовых операций. Есть также языки программирования, где существует встроенная возможность выполнить любую бинарную логическую операцию побитово. Например, в PL/I есть встроенная функция BOOL, третий аргумент которой предназначен для указания произвольной логической операции, которую необходимо побитово применить к первым двум аргументам.

Связь с другими науками

Битовые операции и математическая логика

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

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

Обобщение операций на булеву алгебру

Вместо одиночных битов мы можем рассмотреть векторы из фиксированного количества битов (в программировании их называют регистрами), например, байты.
В программировании регистры рассматривают как двоичное разложение целого числа: b=b+2b1+22b2+…+2N−1bN−1{\displaystyle b=b_{0}+2b_{1}+2^{2}b_{2}+…+2^{N-1}b_{N-1}}, где N — количество битов в регистре.

Тем не менее, ничто не мешает рассматривать эти регистры именно как битовые векторы и проводить булевые операции покомпонентно (бит номер k значения есть результат операции от битов номер k аргументов).
Кстати, математически говоря, булевы операции распространяются таким образом на произвольную булеву алгебру.
Таким образом мы получаем операции побитового И, ИЛИ, НЕ, искл. ИЛИ и т. д.
Как арифметические, данные операции не обладают хорошими свойствами за исключением побитового НЕ, которое для чисел в дополнительном коде совпадает с вычитанием из −1 ().
Однако, они очень полезны в программировании.

2-адическая интерпретация

Целое число, записанное (в дополнительном коде) в бесконечный (в сторону положительных степеней двойки) двоичный регистр является естественным объектом для теории p-адических чисел при p=2{\displaystyle p=2}.
Множество целых 2-адических чисел (то есть произвольных бесконечных битовых последовательностей) может быть рассмотрено как булева алгебра точно так же как и множество значений битового регистра конечной длины.
Все вышеперечисленные битовые операции оказываются непрерывными отображениями.
Хотя практическое программирование не располагает регистрами бесконечной длины, это не мешает использовать данный теоретический факт в криптографии для создания быстродействующих алгоритмов шифрования.

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

Алгебра высказываний

Высказывание – повествовательное предложение, о котором можно сказать истинно оно или ложно. В алгебре простым высказываниям ставятся в соответствии логические переменные (А, В, С и т.д.)

Логическая переменная – это простое высказывание. Логические переменные обозначаются прописными и строчными латинскими буквами (a-z, A-Z) и могут принимать всего два значения – 1, если высказывание истинно, или 0, если высказывание ложно.

 Пример высказываний:

 
 
 
 
 
 
 
 

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

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

Многие люди  не любят сырую погоду.

Пусть А = «Многие люди любят сырую погоду». Получаем логическую функцию F(A) = не А.

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

Логическая формула (логическое выражение) — формула, содержащая лишь логические величины и знаки логических операций. Результатом вычисления логической формулы является ИСТИНА (1) или ЛОЖЬ (0).

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

                                                                      Основные (базовые) логические операции:

1. Логическое умножение (конъюнкция), от лат. konjunctio – связываю:•    Объединение двух (или нескольких) высказываний в одно с помощью союза И;•     в языках программирования — And. •    Принятые обозначения: /\ , •, и, and.•    В алгебре множеств конъюнкции соответствует операция пересечения множеств.  

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

Пример: Рассмотрим составное высказывание  «2 • 2 = 4 и 3 • 3 = 10». Выделим простые высказывания:А = «2 • 2 = 4» = 1 (т.к. это истинное высказывание)В = «3 • 3 = 10» = 0 (т.к. это ложное высказывание)Поэтому, логическая функция F(A, B) = A /\ B = 1 /\ 0 = 0 (в соответствии с таблицей истинности), то есть данное составное высказывание ложное.

2. Логическое сложение (дизъюнкция), от лат. disjunctio – различаю:•    Объединение двух (или нескольких) высказываний в одно с помощью союза ИЛИ;•     в языках программирования — Or. •    Обозначение:  \/, +, или, or.•    В алгебре множеств дизъюнкции соответствует операция объединения множеств.  

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

Пример: Рассмотрим составное высказывание  «2 • 2 = 4 или 2 • 2 = 5». Выделим простые выска-зывания:А = «2 • 2 = 4» = 1 (т.к. это истинное высказывание)В = «2 • 2 = 5» = 0 (т.к. это ложное высказывание)Поэтому, логическая функция F(A, B) = A \/ B = 1 \/ 0 = 1 (в соответствии с таблицей истинности), то есть данное составное высказывание истинно.

3. Отрицание (инверсия), от лат. InVersion – переворачиваю:

•    Соответствует частице НЕ, словосочетаниям НЕВЕРНО, ЧТО или НЕ ЯВЛЯЕТСЯ ИСТИНОЙ, ЧТО;•    в языках программирования — Not; •    Обозначение: не А, ¬А, not•    В алгебре множеств логическому отрицанию соответствует операция дополнения до универсального множества.

 
 
 
 
 
 
Инверсия логической переменной истинна, если сама переменная ложна, и, наоборот, инверсия ложна, если переменная истинна.

 Пример:

А = {два умножить на два равно четырем} = 1.

 ¬A= {Неверно, что два умножить на два равно четырем}= 0.

Рассмотрим высказывание А : «Луна — спутник Земли«;  тогда   ¬А будет формулироваться так:  «Луна — не спутник Земли«.

Рассмотрим высказывание: «Неверно, что 4 делится на 3». Обозначим через А простое высказывание «4 делится на 3». Тогда логическая форма отрицания этого высказывания имеет вид ¬А

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

Операции в логическом выражении выполняются слева направо с учетом скобок в следующем порядке:     1. инверсия;     2. конъюнкция;     3. дизъюнкция;Для изменения указанного порядка выполнения логических операций используются круглые скобки.

Составные логические выражения алгебры высказываний называют формулами.Истинно или ложно значение формулы можно определить законами алгебры логики, не обращаясь к смыслу: F = (0 \/ 1) /\ (¬0 \/ ¬1) = (0 \/ 1) /\ (1 \/ 0) =1 /\ 1=1 — истинаF = (¬0 /\ ¬1) \/ (¬1 \/ ¬1) = (1 /\ 0) \/ (0 \/ 0) = 0 \/ 0 = 0 — ложь

Примеры СДНФ для некоторых функций

Стрелка Пирса: $x \downarrow y = (\neg { x } \land \neg { y } )$

Исключающее или: $x \oplus y \oplus z = (\overline { x } \land \overline { y } \land z) \lor (\overline { x } \land y \land \overline { z } ) \lor (x \land \overline { y } \land \overline { z } ) \lor (x \land y \land z)$

Совершенной дизъюнктивной нормальной формой формулы $A(x_1,x_2,…,x_n)$ называется ДНФ, обладающая следующими свойствами:

а } в ней нет одинаковых дизъюнктивных элементов;

б } ни одна элементарная конъюнкция не содержит двух одинаковых высказываний;

в } ни какая элементарная конъюнкция не содержит высказывание вместе с ее отрицанием;

г } в каждой элементарной конъюнкции содержится либо $X_i$, либо $\overline { X } _i$, где $i = 1, n$.

Условие а } – г } являются необходимыми и достаточными для того, чтобы ДНФ стала СДНФ. В свою очередь эти условия дают возможность составить алгоритм получения СДНФ из ДНФ:

1) если какая-нибудь элементарная конъюнкция не содержит высказывание $X_i$, то заменим выражением $B\wedge (X_i\vee \overline { X } _i) \equiv (B\wedge X_i)\vee (B\wedge \overline { X } _i)$;

2) если в полученном выражении окажутся одинаковые элементарные конъюнкции, то лишние опускаются;

3) если в некоторых элементарных конъюнкциях окажутся одинаковые высказывания, то лишние опускаются;

4) удаляем элементарные конъюнкции, в которых содержатся высказывания вместе с их отрицанием.

Если все элементарные конъюнкции окажутся таковыми, т.е. вся формула будет ложной, то она не будет иметь СДНФ.

Если все элементарные конъюнкции окажутся таковыми, т.е. вся формула будет ложной, то она не будет иметь СДНФ.

Формула называется дизъюнктивной нормальной формой { ДНФ } , если она является дизъюнкцией неповторяющихся элементарных конъюнкций. ДНФ записываются в виде: $A_1\vee A_2\vee …\vee A_n$ , где каждое $A_n$ — элементарная конъюнкция.

Формула $A$ от $k$ переменных называется совершенной дизъюнктивной нормальной формой { СДНФ } , если:

1. $A$ является ДНФ, в которой каждая элементарная конъюнкция есть конъюнкция $k$ переменных $x_1,x_2,…,x_k$, причем на $i$-м месте этой конъюнкции стоит либо переменная $x_i$ либо ее отрицание;

2. Все элементарные конъюнкции в такой ДНФ попарно различны.

Например: $A = x_1 \wedge$ НЕ $x_2 \vee x_1 \wedge x_2$

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

Она является примером однозначного представления булевой функции в виде формульной { алгебраической } записи.

Теорема о СДНФ: Пусть $f(x_1 x_2, …, x_n)$ – булева функция от n переменных, не равная тождественно нулю. Тогда существует совершенная дизъюнктивная нормальная форма, выражающая функцию $f$.

• В таблице истинности отмечаем наборы переменных, на которых значение функции $f = 1$.
• Записываем для каждого отмеченного набора конъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 1, то в конъюнкцию включаем саму переменную, в противном случае – ее отрицание.
• Все полученные конъюнкции связываем операциями дизъюнкции.

Далее:

Линейный интеграл и циркуляция векторного поля

Замена переменных в двойном интеграле. Двойной интеграл в полярных координатах

Теорема о предполных классах

Определение двойного интеграла

Поток жидкости через поверхность

Свойства потока векторного поля

Класс M. Теорема о замкнутости класса M

Полином Жегалкина. Пример.

Односторонние и двусторонние поверхности. Ориентация поверхности

Поверхностный интеграл первого рода и его свойства

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

Вычисление поверхностного интеграла второго рода

Теорема Стокса

Вычисление площади поверхности

Огравление $\Rightarrow $