Ниже мы рассмотрим основные операции, которые используются в булевой алгебре. Этого достаточно, чтобы упростить львиную долю всех выражений, с которыми вы столкнетесь.
Хорошее место для начала – булева алгебра, раздел математики и информатики, который занимается в основном логическими выражениями и предложениями.
Логическое утверждение это утверждение (или условное обозначение), которые мы можем однозначно классифицировать как истинные или ложные (1 или 0 по информатике.).
Примером такого заявления может быть:
- Сегодня светит солнце;
- 5 > 3;
- Химическая таблица элементов была создана Д.И. Менделеевым.
Из этого можно сделать вывод, что в русском языке повествовательные предложения являются логическими предложениями, но не все повествовательные предложения являются логическими предложениями. ПримерХимия – скучный предмет. Здесь мы не можем однозначно сказать, является ли выражение ложным или истинным.
Логические утверждения делятся на два типа – простые и сложные..
- Простой Высказывания состоят из одного утверждения, которое мы можем однозначно охарактеризовать как истинное или ложное.
- Составные заявления состоят из нескольких таких утверждений, которые связаны между собой логическими операциями (рассматривается далее).
В алгебре логики как простые, так и сложные высказывания описываются булевыми выражениями.
Булево выражение – является символическим (подписать) описание высказывания.
В таких выражениях простые выражения выступают в качестве переменных и обозначаются буквами латинского алфавита, а операции обозначаются специальными знаками. После выполнения всех операций и упрощения выражения получается результат, на основе которого строится таблица истинности.
Операции над булевыми типами очень часто встречаются при построении выражений, используемых в программировании. К ним относятся следующие:
Операторы сравнения
Подходящие символы используются для создания логических условий. Это: больше (>), меньше (<), больше или равно (>=), меньше или равно (<=), равно (==) и не равно (==!).. Чтобы понять, что они означают, нам необходимо рассмотреть практические примеры:
- >: 5>4.
- <: 3<9.
- >=: 5>=5 и 6>=8.
- <=: 3<=3 и 6<=11.
- <> <>
Обратите внимание, что в этих примерах истинное значение получено, потому что условие выполнено. В информатике, однако, методы ветвления используются при построении алгоритмов. Это следующие конструкции: IF (a>b), THEN a+b. ИЛИ иначе (a*b). Он гласит следующее: если a больше b, мы складываем оба числа, иначе (a
В этом случае программа будет работать для всех значений, так как были рассчитаны все возможные варианты. Однако булева алгебра основана не только на операторах сравнения, но и на логических операциях.
Другими названиями конъюнкции являются логическое умножение, логическое И или просто И.
Таблица истинности конъюнкции
Истинность конъюнкции определяется ее таблицей истинности.
| A | B | A / B |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
1 Рассмотрим утверждение: “Вы можете взять книгу в библиотеке или встретиться с кем-то из знакомых”. Формально это утверждение можно представить следующим образом: C = A V B, где A – “Вы можете взять книгу в библиотеке”, а B – “Вы можете встретиться с другом в библиотеке”. Объединение этих утверждений с помощью операции логического сложения означает, что события могут происходить как отдельно, так и одновременно.
Как называется логическое умножение
Прежде всего, начнем с разбора самого названия предмета, который имеет значение алгебра, логика, а затем алгебра логики.
Алгебра – это раздел математики, занимающийся описанием операций над переменными, обычно обозначаемыми строчными буквами латинского алфавита – a, b, x, y и т.д. Операции над переменными записываются в виде математических выражений.
Термин “логика” происходит от древнегреческого “логос”, что означает “слово, мысль, понятие, рассуждение, закон”.
Алгебра логики это аппарат, позволяющий оперировать высказываниями.
Алгебру логики также называют Булева алгебраили Булева алгебраВ честь английского математика Джорджа Буля, который развил основные идеи в 19 веке. В булевой алгебре теоремы обозначаются заглавными латинскими буквами: A, B, X, Y. В булевой алгебре вводятся три основные логические операции над высказываниями: Сложение, умножение, отрицание. Определены аксиомы (законы) булевой алгебры для выполнения этих операций. Действия, выполняемые над выражениями, записываются в виде логических выражений.
Логические выражения могут быть простыми и сложными.
Простое логическое выражение Состоит из одного утверждения и не содержит никаких логических операций. В простом логическом выражении возможны только два исхода: либо “истинно”, либо “ложно”.
Сложное логическое выражение содержит утверждения, связанные логическими операциями. Подобно концепции функций в алгебре, сложное логическое выражение содержит аргументы, которые являются утверждениями.
Основными логическими операциями являются логические операции используются в сложных логических выражениях следующим образом:
– NOT (логическое отрицание, инверсия);
– ИЛИ (логическое сложение, дизъюнкция);
– AND (логическое умножение, конъюнкция).
Логическое отрицание является одномоментной операцией, поскольку задействована одна инструкция. Логическое сложение и умножение – это бинарные операции, включающие два высказывания. Существуют и другие операции, например, операции следования и эквивалентности, принцип действия которых может быть выведен из основных операций.
Все операции в булевой алгебре определяются через массивы истины значения. Таблица истинности определяет результат операции для все возможные логические значения исходных утверждений. Количество вариантов, отражающих результат операции, будет зависеть от количества утверждений в логическом выражении, напр:
- Таблица истинности одноместной логической операции состоит из двух строк: два различных значения аргумента – “истина” (1) и “ложный” (0) и два соответствующих значения функции;
- таблица истинности логической операции двух лиц имеет четыре строки: 4 различных комбинации значений аргументов – 00, 01, 10 и 11 и 4 соответствующих значения функции;
- Если количество предложений в логическом выражении равно N, то таблица истинности будет содержать 2N строк, поскольку существует 2N различных комбинаций возможных значений аргументов.
Операция NOT – логическое отрицание (инверсия)
Логическая операция NOT применяется к единственному аргументу, который может быть простым или сложным логическим выражением. Результат операции NOT выглядит следующим образом:
– если исходное выражение истинно, то результат его отрицания ложен;
– Если исходное выражение ложно, то его отрицание истинно.
Для отрицания NOT используются следующие соглашения:
Результат операции отрицания NOT определяется следующей таблицей истинности:
| A | не A |
| 0 | 1 |
| 1 | 0 |
Результат операции отрицания истинен, если исходное утверждение ложно, и наоборот.
Вот несколько примеров отрицания.
1. утверждение “Земля вращается вокруг Солнца” является истинным. Утверждение “Земля не вращается вокруг Солнца” является ложным. 2.
2. Утверждение “Уравнение y = 4x + 3 в интервале -2 < x < 2 не имеет корней" ложно. Утверждение "Уравнение y = 4x + 3 в интервале -2 < x < 2 имеет корень" верно.
3 Утверждение “4 – простое число” является ложным. Утверждение “4 не является простым числом” верно.
Принцип работы выключателя настольной лампы таков: если лампа горит, выключатель выключает ее, если лампа не горит – включает. Такой переключатель можно рассматривать как электрический эквивалент операции отрицания.
OR – логическое дополнение (дизъюнкция, конъюнкция)
Логическая операция ИЛИ выполняет функцию объединения двух утверждений, которые могут быть простым или сложным логическим выражением. Выражения, которые являются отправной точкой для логической операции, называются аргументами. Результатом операции OR является выражение, которое истинно тогда и только тогда, когда истинно хотя бы одно из исходных выражений.
Используются следующие символы: A или B, A V B, A или B.
Результат операции ИЛИ определяется следующей таблицей истинности:
| A | B | A или B |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Результат операции ИЛИ истинен, если истинно A, или истинно B, или истинны оба A и B, и ложен, если A и B ложны.
Вот несколько примеров логического сложения.
1 Рассмотрим утверждение: “Вы можете взять книгу в библиотеке или встретиться с другом”. Формально это утверждение можно представить следующим образом: C = A V B, где утверждение A – “Вы можете взять книгу в библиотеке”, а B – “Вы можете встретиться с другом в библиотеке”. Объединение этих утверждений с помощью операции логического сложения означает, что события могут происходить как отдельно, так и одновременно.
2 Рассмотрим утверждение: “Ключ к сдаче экзамена – знание или удача”. “Экзамен может сдавать тот, кто знает все, или тот, кому повезло (напр. вытянули единственный заученный билет), или тот, кто знает все и выбрал “правильный” билет.
Каждый, кто когда-либо пользовался елкой с параллельно подключенными лампочками, знает, что елка будет гореть до тех пор, пока хотя бы одна лампочка цела. Операция логического ИЛИ очень похожа на работу такой гирлянды, поскольку результат этой операции ложен только в одном случае – когда все аргументы ложны.
Операция AND – логическое умножение (конъюнкция)
Операция AND выполняет функцию пересечения двух утверждений (аргументов), которые могут быть как простыми, так и сложными логическими выражениями. Результатом операции AND является выражение, которое истинно тогда и только тогда, когда оба исходных выражения истинны.
Используемые обозначения: A и B, A ⋀ B, A и B, A и B.
Результат операции AND определяется следующей таблицей истинности:
| A | B | A и B |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Результат операции AND истинен тогда и только тогда, когда высказывания A и B истинны одновременно, и ложен во всех остальных случаях.
Приведем примеры логического умножения.
1 Рассмотрим утверждение: “Мастерство и настойчивость ведут к достижению цели”. Цель достигается только в том случае, если обе предпосылки – мастерство и настойчивость – верны одновременно.
Логическую операцию AND можно сравнить с рядом лампочек в гирлянде. Если хотя бы одна лампочка не работает, электрическая цепь разомкнута, т.е. гирлянда не работает. Ток может течь только в том случае, если все элементы в цепи находятся в порядке.
Операция “IF-THEN” – логическое следствие (импликация)
Эта операция объединяет два простых логических выражения, первое из которых является условием, а второе – следствием этого условия.
если А, то В; А влечет за собой В; если А, то В; А->В
| A | B | A -> B |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Результат операции импликации ложен только в том случае, если посылка A истинна, а заключение B (следствие) ложно.
Ниже приведены примеры работы последовательностей.
1 Рассмотрим утверждение: “Если идет дождь, то на улице сыро”. Первыми предложениями здесь являются “Идет дождь” и “На улице сыро”. Если на улице нет дождя и не сыро, то результат следующей операции истинен. На улице может быть сыро и без дождя, например, если закончился полив или накануне прошел дождь. Результат операции будет ложным только в том случае, если идет дождь и на улице не сыро.
2 Рассмотрите два утверждения: A <х делится="" на="" 9="">, В <х делится="" на="" 3="">. Операция A -> B означает следующее: “Если число делится на 9, то оно также делится на 3”. Рассмотрите возможности:
(a) A ложно, B ложно (строка 1 таблицы истинности). Вы можете найти числа, для которых утверждение “Если A ложно, то B ложно” истинно. Например, x = 4, 17, 22.
(b) A – ложно, B – истинно (строка 2 таблицы истинности). Вы можете найти числа, для которых утверждение “если A ложно, то B истинно” является истинным. Например, x = b, 12, 21.
(c) A – истинно, B – ложно (строка 3 таблицы истинности). Невозможно найти число, которое делится на 9, но не делится на 3. Истинная посылка не может привести к ложному следствию.
(d) A истинно, B истинно (строка 4 таблицы истинности). Вы можете найти числа, для которых верно утверждение “если A истинно, то B истинно”. Например, x = 9, 18, 27.
Операция “A тогда и только тогда, когда B” (эквивалентность, эквивалентность)
Применяемые обозначения: A = B, A
Результат операции эквивалентности истинен только в том случае, если A и B оба истинны или оба ложны.
Приведем примеры операций эквивалентности:
1. день сменяет ночь тогда и только тогда, когда солнце исчезает за горизонтом;
2. результат в спорте может быть достигнут тогда и только тогда, когда прикладываются максимальные усилия.
$(X ¯mid X) ¯mid (Y ¯mid Y) = X ¯vee Y$ – дизъюнкция
Эквивалентность или логическая эквивалентность
Эквивалентность – это сложное логическое выражение, которое верно для равных значений $A$ и $B$.
Символы: $leftrightrightarrow$, $Leftrightarrow$, $equiv$.
Таблица истинности для эквивалентности
- Эквивалентность верна на равных наборах значений переменных $A$ и $B$.
- KNF $A equiv$ B = (˜bar ˜vee B) ˜cdot (A ˜cdot ˜bar)$
- ДНФ $A þequiv B = þbar þcdot þbar. A ™dot B$
В в логических схемах этот элемент, независимо от элементной базы, на которой он реализован, маркируется, как показано на рис. 1.5,а. Таблица истинности показана на рисунке 1.5,б.
Основы компьютерной логики
Каждый цифровой компьютер состоит из Логические схемы – схемы, которые могут находиться только в одном из двух возможных состояний – либо “логический ноль”, либо “логическая единица”.. Любое выражение, включая словесные выражения, которые могут быть описаны как “истина” и “ложь”, можно рассматривать как логический 0 и логическую 1. В компьютерной технике логические 0 и 1 – это состояния электрических цепей с определенными параметрами. В транзисторно-транзисторных логических схемах, например, логический 0 – это напряжение в диапазоне 0 … + 0,4 В, а логическая 1 – это напряжение в диапазоне + 2,4 … + 5 V [1]. Работа логических схем описывается специальным математическим аппаратом, называемым булевой алгеброй или булевой алгеброй. Булева алгебра была разработана Джорджем Булем (1815 – 1864), она является основой для всех методов упрощения булевых выражений.
Булевы переменные и функции Булевы переменные и функции – это переменные и функции, которые могут принимать только два значения – либо булев 0, либо булева 1..
Основные логические функции и элементы
Логический элемент – Графическое представление элементарного логическая функция.
Логическое умножение (конъюнкция) – функция AND
Рассмотрим ключевую диаграмму, показанную на рис. 1.1,а. В качестве логики возьмем 0 [2]:
- на входе схемы открыть состояние соответствующего ключа, например,
; - на выходе системы (
) – это его состояние, когда текущий не проходит через сопротивление R.
Таблица истинности – это таблица, содержащая все возможные комбинации входных логических переменных и соответствующие им значения логической функции.
Таблица истинности для логической схемы, показанной на рис. 1.1,b, состоит из 8 строк, так как схема имеет три входа – 
, 
и 
. Каждая из этих логических переменных может находиться либо в состоянии логического 0, либо в состоянии логической 1. Соответственно, число комбинаций этих переменных равно 
, и . Отсюда другое название логического умножения – логический элемент И. В логических схемах этот элемент, независимо от элементной базы, на которой он реализован, обозначается так, как показано на рис. 1.1,в.
Принцип логического умножения Если на вход элемента логического И подать хотя бы один логический 0, то на его выходе появится логический 0.
Уровень логического 0 является решающим для Логический 0 является определяющим уровнем для логического умножения. .
Для обозначения логического умножения в логических выражениях используется несколько вариантов. Например, для трехвходового элемента И, показанного на рисунке 1.1,c, логическое выражение может быть представлено как
- или
но из контекста должно быть ясно, что данное умножение является логическим; - либо
; - или
– используя знак соединения; - или
но из контекста должно быть ясно, что между переменными , 
и 
является логическим умножением.
Логическое сложение (дизъюнкция) – функция ИЛИ
Рассмотрим ключевую диаграмму, показанную на рис. 1.2,а. Таблица истинности для этого логическая схема (рис. 1.2,б) состоит из 4 линий, так как эта схема имеет два входа – (рис. 1.2,б). и . Количество комбинаций этих переменных равно 
. Отсюда другое название логического сложения -. логическое ИЛИ. В логических схемах соответствующий логический элемент независимо от того, на какой элементной базе он реализован, определяется, как показано на рис. 1.2,в.
Принцип логического сложения: Если хотя бы один логический элемент ИЛИ подключен к входу 
на его выходе будет логическая 1.
На добавление логики уровень логической 1 является решающим.
Два различных булевых выражения используются для .. Например, для данного двухвходового элемента ИЛИ булево выражение может быть представлено как:
- либо
но из контекста должно быть ясно, что это логическое дополнение; - или
– С использованием знака дизъюнкции.
Логическое отрицание (инверсия) – функция НЕ
Рассмотрим схему ключа, показанную на рис. 1.3,а. Таблица истинности для этой схемы (рис. 1.3,б) является самой простой и состоит всего из 2 строк, поскольку имеет (как единственный среди всех логических элементов) только один вход – . . Количество вариантов выбора для одного логическая переменная равен 
не закрыт, т.е. . Другое название для этого логическая функция – отрицаниеа соответствующий логический элемент называется инвертор. В логические схемы этот элемент, независимо от того, на какой элементной базе он реализован, маркируется, как показано на рисунке 1.3c. Поскольку он имеет только один вход, в его обозначении допускаются как знак логического сложения, так и знак логического умножения.
Принцип инверсии: При прохождении через инвертор сигнал инвертирует свое значение.
Единственный вариант символа инверсии используется в логических выражениях:
К основным логические элементы Есть еще два элемента, которые являются комбинациями AND, OR и NOT: элемент AND-NE и элемент OR-NE.
Булева функция и элемент AND-NE
Эта функция выполняет логическое умножение входных сигналов, а затем инвертирует результат этого умножения. В логические схемы этот элемент, независимо от того, на какой элементной базе он реализован, маркируется, как показано на рис. 1.4, а. Таблица истинности приведен на рисунке 1.4,б.
Если на вход логического элемента И-НЕ подается хотя бы один логический 0, то на его выходе будет логическая 1.
Такая же нотация применяется в логических выражениях:
- либо
но из контекста должно быть ясно, что данное умножение является логическим - или
.
Булева функция и элемент ИЛИ-НЕ
В в логических схемах Этот элемент, независимо от того, на какой элементной базе он реализован, обозначается так, как показано на рисунке 1.5, а. Таблица истинности показана на рисунке 1.5,б.
Если на вход логического элемента ИЛИ-НЕ подается хотя бы одна логическая 1, то на его выходе будет логический 0.Такая же нотация применяется в логических выражениях:
Читайте далее: