Что выполняется первым конъюнкция или дизъюнкция

0

Логические операции. ➞ Что такое конъюнкция, дизъюнкция, импликация

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

Основные положения

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

Логическим высказыванием называется утверждение (или запись), которое мы можем однозначно классифицировать, как истинное или ложное (1 или 0 в информатике).

Примером таким высказываний будут являться:

1. Сегодня светит солнце;
2. 5 > 3;
3. Химическая таблица элементов была разработана Д.И. Менделеевым.

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

Логические высказывания делятся на два типа — простые и сложные.

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

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

Булево выражение – это символическое (знаковое) описание высказывания.

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

Операции

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

Конъюнкция

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

Функция может работать как с двумя операндами (высказываниями), так и с тремя, четырьмя и т.д. В математике обозначается с помощью знаков ​\( \wedge \) и &. Обозначение в языках программирования AND, &&. Таблица истинности для двух операндов:

Дизъюнкция

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

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

Инверсия

Логическое отрицание – функция, работающая с одним высказыванием, и заменяющая истину на ложь, а ложь на истину. В математике обозначается с помощью черты над значением, а в программирование и информатике с помощью слова NOT.

Импликация

Также называется булевым следованием. В русском языке данной функции соответствует оборот «Если …, то …». Например, если на улице гремит гром, то стоит пасмурная погода.

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

Эквивалентность

Булева тождественность или равенство. На простом языке будет обозначено как «… эквивалентно (равно) …». Результат будет истинным тогда, когда все значения в выражении будут иметь одинаковую истинность.

Обозначается с помощью трех черточек или ⟺.

Порядок выполнения операций

Логические операции выполняются в следующем порядке:

1. Первой выполняется инверсия переменных.
2. Вторым выполняется конъюнкция (булево умножение);
3. Третьим номером идет дизъюнкция (сложение);
4. Затем выполняется импликация;
5. Самым низким приоритетом выполнения обладает эквивалентность.

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

Пример

Дано два отрезка B = [2,10], C = [6,14]. Из предложенных вариантов ответа выберите такой отрезок A, что формула \( ((z \in A) \Longrightarrow (z \in B)) \vee (z \in C) \) истинна при любом значении z. Варианты ответа:

1. [0,3];
2. [3,11];
3. [11,15];
4. [15,17].

Решение: Подставим в уравнение \( ((z \in A) \Longrightarrow (z \in B)) \vee (z \in C) \) =1 значения B и C и составим таблицу истинности:

Получившаяся формула \( ((z \in A) \Longrightarrow (z \in [2,10])) \vee (z \in [6,14])=1 \). По условию ​​​\( z \in A \)=1.

Таблица истинности для всех отрезков:

Ответ: A = [3,11].

Видео

Заключение

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

Таблицы истинности и логические схемы

Алгебра логики (англ. algebra of logic) — один из основных разделов математической логики, в котором методы алгебры используются в логических преобразованиях.

Основоположником алгебры логики является английский математик и логик Дж. Буль (1815–1864), положивший в основу своего логического учения аналогию между алгеброй и логикой. Любое высказывание он записывал с помощью символов разработанного им языка и получал «уравнения», истинность или ложность которых можно было доказать, исходя из определенных логических законов, таких как законы коммутативности, дистрибутивности, ассоциативности и др.

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

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

Например, «3 умножить на 3 равно 9», «Архангельск севернее Вологды» — истинные высказывания, а «Пять меньше трех», «Марс — звезда» — ложные.

Очевидно, что не всякое предложение может быть логическим высказыванием, т. к. не всегда есть смысл говорить о его ложности или истинности. Например, высказывание «Информатика — интересный предмет» неопределенно и требует дополнительных сведений, а высказывание «Для ученика 10-А класса Иванова А. А. информатика — интересный предмет» в зависимости от интересов Иванова А. А. может принимать значение «истина» или «ложь».

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

В алгебре логики различаются простые (элементарные) высказывания, обозначаемые латинскими буквами (A, B, C, D, …), и сложные (составные), составленные из нескольких простых с помощью логических связок, например таких, как «не», «и», «или», «тогда и только тогда», «если … то». Истинность или ложность получаемых таким образом сложных высказываний определяется значением простых высказываний.

Обозначим как А высказывание «Алгебра логики успешно применяется в теории электрических схем», а через В — «Алгебра логики применяется при синтезе релейно-контактных схем».

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

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

Логических значений всего два: истина (TRUE) и ложь (FALSE). Это соответствует цифровому представлению — 1 и 0. Результаты каждой логической операции можно записать в виде таблицы. Такие таблицы называют таблицами истинности.

Основные операции алгебры логики

1. Логическое отрицание, инверсия (лат. inversion — переворачивание) — логическая операция, в результате которой из данного высказывания (например, А) получается новое высказывание (не А), которое называется отрицанием исходного высказывания, обозначается символически чертой сверху ($A↖<->$) или такими условными обозначениями, как ¬, 'not', и читается: «не А», «А ложно», «неверно, что А», «отрицание А». Например, «Марс — планета Солнечной системы» (высказывание А); «Марс — не планета Солнечной системы» ($A↖<->$); высказывание «10 — простое число» (высказывание В) ложно; высказывание «10 — не простое число» (высказывание B ) истинно.

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

Высказывание $A↖<->$ ложно, когда А истинно, и истинно, когда А ложно.

Геометрически отрицание можно представить следующим образом: если А — это некоторое множество точек, то $A↖<->$ — это дополнение множества А, т. е. все точки, которые не принадлежат множеству А.

2. Конъюнкция (лат. conjunctio — соединение) — логическое умножение, операция, требующая как минимум двух логических величин (операндов) и соединяющая два или более высказываний при помощи связки «и» (например, «А и В»), которая символически обозначается с помощью знака ∧ (А ∧ В) и читается: «А и В». Для обозначения конъюнкции применяются также следующие знаки: А ∙ В; А & В, А and В, а иногда между высказываниями не ставится никакого знака: АВ. Пример логического умножения: «Этот треугольник равнобедренный и прямоугольный». Данное высказывание может быть истинным только в том случае, если выполняются оба условия, в противном случае высказывание ложно.

Таблица истинности операции имеет вид

Высказывание А ∧ В истинно только тогда, когда оба высказывания — А и В истинны.

Геометрически конъюнкцию можно представить следующим образом: если А, В — это некоторые множества точек, то А ∧ В есть пересечение множеств А и В.

3. Дизъюнкция (лат. disjunction — разделение) — логическое сложение, операция, соединяющая два или более высказываний при помощи связки «или» (например, «А или В»), которая символически обозначается с помощью знака ∨ (А ∨ В) и читается: «А или В». Для обозначения дизъюнкции применяются также следующие знаки: А + В; А or В; А | B. Пример логического сложения: «Число x делится на 3 или на 5». Это высказывание будет истинным, если выполняются оба условия или хотя бы одно из условий.

Таблица истинности операции имеет вид

Высказывание А ∨ В ложно только тогда, когда оба высказывания — А и В ложны.

Геометрически логическое сложение можно представить следующим образом: если А, В — это некоторые множества точек, то А ∨ В — это объединение множеств А и В, т. е. фигура, объединяющая и квадрат, и круг.

4. Дизъюнкция строго-разделительная, сложение по модулю два — логическая операция, соединяющая два высказывания при помощи связки «или», употребленной в исключающем смысле, которая символически обозначается с помощью знаков ∨ ∨ или ⊕ (А ∨ ∨ В, А ⊕ В) и читается: «либо А, либо В». Пример сложения по модулю два — высказывание «Этот треугольник тупоугольный или остроугольный». Высказывание истинно, если выполняется какое-то одно из условий.

Таблица истинности операции имеет вид

Высказывание А ⊕ В истинно только тогда, когда высказывания А и В имеют различные значения.

5. Импликация (лат. implisito — тесно связываю) — логическая операция, соединяющая два высказывания при помощи связки «если. то» в сложное высказывание, которое символически обозначается с помощью знака → (А → В) и читается: «если А, то В», «А влечет В», «из А следует В», «А имплицирует В». Для обозначения импликации применяется также знак ⊃ (A ⊃ B). Пример импликации: «Если полученный четырехугольник квадрат, то около него можно описать окружность». Эта операция связывает два простых логических выражения, из которых первое является условием, а второе — следствием. Результат операции ложен только тогда, когда предпосылка есть истина, а следствие — ложь. Например, «Если 3 * 3 = 9 (А), то Солнце — планета (В)», результат импликации А → В — ложь.

Таблица истинности операции имеет вид

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

6. Эквивалентность, двойная импликация, равнозначность (лат. aequalis — равный и valentis — имеющий силу) — логическая операция, позволяющая из двух высказываний А и В получить новое высказывание А ≡ В, которое читается: «А эквивалентно B». Для обозначения эквивалентности применяются также следующие знаки: ⇔, ∼. Эта операция может быть выражена связками «тогда и только тогда», «необходимо и достаточно», «равносильно». Примером эквивалентности является высказывание: «Треугольник будет прямоугольным тогда и только тогда, когда один из углов равен 90 градусам».

Таблица истинности операции эквивалентности имеет вид

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

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

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

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

Рассмотрим, например, построение составного высказывания из высказываний А и В, которое было бы ложно тогда и только тогда, когда оба высказывания истинны. В таблице истинности для операции сложения по модулю два находим: 1 ⊕ 1 = 0. А высказывание может быть, например, таким: «Этот мяч полностью красный или полностью синий». Следовательно, если утверждение А «Этот мяч полностью красный» — истина, и утверждение В «Этот мяч полностью синий» — истина, то составное утверждение — ложь, т. к. одновременно и красным, и синим мяч быть не может.

Примеры решения задач

Пример 1. Определить для указанных значений X значение логического высказывания ((X > 3) ∨ (X < 3)) → (X < 4) :

1) X = 1; 2) X = 12; 3) X = 3.

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

((1 > 3) ∨ (1 < 3)) → (1 < 4) = ложь ∨ истина → истина = истина → истина = истина;

((12 > 3) ∨ (12 < 3) → (12 < 4) = истина ∨ ложь → ложь = истина → ложь = ложь;

((3 > 3) ∨ (3 < 3)) → (3<4) = ложь ∨ ложь → истина = ложь → истина = истина.

Пример 2. Указать множество целых значений X, для которых истинно выражение ¬((X > 2) → (X > 5)) .

Решение. Операция отрицания применена ко всему выражению ((X > 2) → (X > 5)) , следовательно, когда выражение ¬((X > 2) → (X > 5)) истинно, выражение ((X > 2) →(X > 5)) ложно. Поэтому необходимо определить, для каких значений X выражение ((X > 2) → (X > 5)) ложно. Операция импликации принимает значение «ложь» только в одном случае: когда из истины следует ложь. А это выполняется только для X = 3; X = 4; X = 5.

Пример 3. Для каких из приведенных слов ложно высказывание ¬(первая буква гласная ∧ третья буква гласная) ⇔ строка из 4 символов? 1) асса; 2) куку; 3) кукуруза; 4) ошибка; 5) силач.

Решение. Рассмотрим последовательно все предложенные слова:

1) для слова асса получим: ¬(1 ∧ 0) ⇔ 1, 1 ⇔ 1 — высказывание истинно;

2) для слова куку получим: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 1 — высказывание истинно;

3) для слова кукуруза получим: ¬ (0 ∧ 0) ⇔ 0, 1 ⇔ 0 — высказывание ложно;

4) для слова ошибка получим: ¬ (1 ∧ 1) ⇔ 0, 0 ⇔ 0 — высказывание истинно;

5) для слова силач получим: ¬ (0 ∧ 0) ⇔ 1, 1 ⇔ 0 — высказывание ложно.

Логические выражения и их преобразование

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

• выражения, которые используют операции сравнения («больше», «меньше», «равно», «не равно» и т. п.) и принимают логические значения (например, выражение а > b , где а = 5 и b = 7, равно значению «ложь»);
• непосредственные логические выражения, связанные с логическими величинами и логическими операциями (например, A ∨ В ∧ С, где А = истина, B = ложь и C = истина).

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

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

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

Пример. Найти значение выражения:

$1 ≤ a ∨ A ∨ sin(π/a — π/b) < 1 ∧ ¬B ∧ ¬(b^a + a^b > a + b ∨ A ∧ B)$ для а = 2, b = 3, A = истина, В = ложь.

Решение. Порядок подсчета значений:

1) b a + a b > a + b, после подстановки получим: 3 2 + 2 3 > 2 + 3, т. е. 17 > 2 + 3 = истина;

2) A ∧ B = истина ∧ ложь = ложь.

Следовательно, выражение в скобках равно (b a + a b > a + b ∨ A ∧ B) = истина ∨ ложь = истина;

3) 1≤ a = 1 ≤ 2 = истина;

4) sin(π/a — π/b) < 1 = sin(π/2 — π/3) < 1 = истина.

После этих вычислений окончательно получим: истина ∨ А ∧ истина ∧ ¬В ∧ ¬истина.

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

5) ¬В = ¬ложь = истина; ¬истина = ложь;

6) A ∧ истина ∧ истина ∧ ложь = истина ∧ истина ∧ истина ∧ ложь = ложь;

7) истина ∨ ложь = истина.

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

Примечание. Учитывая, что исходное выражение есть, в конечном итоге, сумма двух слагаемых, и значение одного из них 1 ≤ a = 1 ≤ 2 = истина, без дальнейших вычислений можно сказать, что результат для всего выражения тоже «истина».

Тождественные преобразования логических выражений

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

Доказательства этих утверждений производят на основании построения таблиц истинности для соответствующих записей.

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

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

Рассмотрим на примерах некоторые приемы и способы, применяемые при упрощении логических формул:

1) X1 ∧ X2 ∨ X1 ∧ X2 ∪ ¬X1 ∧ X2 = X1 ∧ X2 ∨ ¬X1 ∧ X2 = (X1 ∨ ¬X1) ∧ X2 = 1 ∧ X2 = X2 .

Для преобразования здесь можно применить закон идемпотенции, распределительный закон; операцию переменной с инверсией и операцию с константой.

2) X1 ∨ X1 ∧ X2 = X1 ∨ (1 ∨ 1 ∧ X2) = X1 ∨ (1 ∨ X2) = X1 .

Здесь для упрощения применяется закон поглощения.

3) ¬(X1 ∧ X2) ∨ X2 = (¬X1 ∨ ¬X2) ∨ X2 = ¬X1 ∨ ¬X2 ∨ X2 = ¬X1 ∨ 1 = 1 .

При преобразовании применяются правило де Моргана, операция переменной с ее инверсией, операция с константой

Примеры решения задач

Пример 1. Найти логическое выражение, равносильное выражению A ∧ ¬(¬B ∨ C) .

Решение. Применяем правило де Моргана для В и С: ¬(¬B ∨ C) = B ∧ ¬C .

Получаем выражение, равносильное исходному: A ∧ ¬(¬B ∨ C) = A ∧ B ∧ ¬C .

Пример 2. Указать значение логических переменных А, В, С, для которых значение логического выражения (A ∨ B) → (B ∨ ¬C ∨ B) ложно.

Решение. Операция импликации ложна только в случае, когд а из истинной посылки следует ложь. Следовательно, для заданного выражения посылка A ∨ B должна принимать значение «истина», а следствие, т. е. выражение B ∨ ¬C ∨ B , — «ложь».

1) A ∨ B — результат дизъюнкции — «истина», если хотя бы один из операндов — «истина»;

2) B ∨ ¬C ∨ B — выражение ложно, если все слагаемые имеют значение «ложь», т. е. В — «ложь»; ¬C — «ложь», а следовательно, переменная С имеет значение «истина»;

3) если рассмотреть посылку и учесть, что В — «ложь», то получим, что значение А — «истина».

Ответ: А — истина, В — ложь, С — истина.

Пример 3. Каково наибольшее целое число X, при котором истинно высказывание (35

Что выполняется первым конъюнкция или дизъюнкция

Обозначение:

Обозначение:

Обозначение:

Обозначение:

Обозначение:

Обозначение:

Обозначение:

1. Инверсия
2. Конъюнкция
3. Дизъюнкция
4. Импликация
5. Эквиваленция
6. Штрих Шеффера
7. Стрелка Пирса

II –

III –

IV –

Я скажу про него две вещи:

1. Этот кот в галстуке.
2. Этот кот белого цвета.

Очевидно, что с первым высказыванием и поспорить нельзя, а вот второе — наглая ложь. А если я захочу вас запутать: «Этот кот в галстуке или он белого цвета, из чего следует, что он белого цвета и в галстуке или не белый». Что это в итоге — правда или ложь?

Чтобы это определить, в математике есть отдельный раздел.

Алгебра логики — это раздел математики, который занимается логическими операциями над высказываниями.

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

Логические выражения и операторы

Как вычислить истинность логического выражения?

Термин высказывание, мы теперь знаем. Но что такое логическое выражение? Выражение — это уравнение из высказываний, как математическое уравнение из чисел.

«Этот кот вооружен и его глаза зеленого цвета», — в одном выражении мы использовали два высказывания.

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

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

Так и работают логические операторы — в зависимости от них все выражение и принимает значение истины или лжи.

Основные логические операторы алгебры логики:

Конъюнкция: логическое умножение или логическое И. В записи обозначается как ∧. А ∧ В дает истину только в том случае, если оба высказывания А и В истинны.

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

Называется логическим сложением за схожесть: если складывать только 0 и 1, чем мы и занимаемся, то достаточно одному слагаемому быть 1, чтобы все выражение не было равно 0.

Важно сразу понять — если применить логическое сложение к двум единицам (1 ∨ 1), мы получим не 2, а все еще 1. Все-таки единица здесь означает не число, а истину, и сложив две, мы не получим одну сверх-истину.

Приоритет этих операторов:

1. инверсия;
2. конъюнкция;
3. дизъюнкция;
4. импликация;
5. эквиваленция.

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

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

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

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

В этой таблице содержатся все возможные наборы переменных. Количество наборов N зависит от количества различных переменных i как N = 2 i .

Чтобы удобно записать наборы, нумеруем их по порядку начиная с 0, переводим их номер в двоичную систему счисления (2сс) и записываем набор цифр.

Давайте запишем таблицы истинности для известных нам логических операторов:

• инверсия берет только 1 переменную и сразу меняет ее значение:

• конъюнкция берет две переменные и возвращает 1 только в том случае, если обе равны 1:

• дизъюнкция вернет 1, если хотя бы одна из переменных равна 1:

• эквиваленция вернет 1, если переменные равны, и 0 в противном случае:

• импликация вернет 0, если из истины будет следовать ложь, и 1 во всех остальных случаях:

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

Например, для выражения: А ∧ (В ∨ С) ≡ В ⇒ ¬А.

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

Здесь порядок операций будет следующим:

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

Чтобы удобно записать наборы, пронумеруем их по порядку начиная с 0. Переведем их номер в 2сс и запишем набор цифр. У нас 3 различные переменные, поэтому должно быть 8 наборов.

1. Первое действие — сложение В и С. Для каждого набора запишем результат сложения в соответствующий столбец.

1. Второе действие — инверсия переменной А.

1. Третье действие — умножение значения А на результат первого действия:

1. Четвертое — импликация значения В и результата второго действия:

1. И последнее действие — эквиваленция результатов 3 и 4 действий:

Последний столбец — и есть результат таблицы истинности. По нему можно сказать, что при А = 1, В = 0 и С = 1 все исходное выражение равно 1, а во всех остальных случаях — 0.

Законы логики

Их не так уж и мало: от самых простых и очевидных до достаточно хитрых; от тех, которые встречаются очень часто до довольно редких.

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

Попробуем упростить исходное выражение ¬(¬А ∧ ¬В) ∨ В ∧ С:

1. Первым можно увидеть закон де Моргана, где у нас идет отрицание целой скобки:

¬(¬А ∧ ¬В) ∨ В ∧ С = ¬(¬А) ∨ ¬(¬В) ∨ В ∧ С

1. Здесь же появляются переменные А и В, к которым можно применить закон двойного отрицания:

¬(¬А) ∨ ¬(¬В) ∨ В ∧ С = А ∨ В ∨ В ∧ С

1. Можно заметить закон поглощения — В складывается с умножением В на С:

А ∨ В ∨ В ∧ С = А ∨ В

Итого, уравнение с 3 переменными и множеством отрицаний мы смогли превратить в максимально простую запись, где осталось всего 2 переменные:

¬(¬А ∧ ¬В) ∨ В ∧ С = А ∨ В

Фактчек

• Алгебра логики — это математика, которая пользуется не числами, а высказываниями, являющимися истинными или ложными. Истина обозначается как 1, а ложь — как 0.
• Основными логическими операторами являются инверсия, конъюнкция, дизъюнкция, импликация и эквиваленция.
• Для расчета истинности логического уравнения используется таблица истинности.
• Законы логики помогают сокращать логические уравнения.

Проверь себя

Задание 1.
Выберите правильный порядок приоритета логических операторов:

1. Импликация, эквиваленция, конъюнкция, дизъюнкция, инверсия.
2. Инверсия, конъюнкция, дизъюнкция, импликация, эквиваленция.
3. Инверсия, конъюнкция, дизъюнкция, эквиваленция, импликация.
4. Инверсия, дизъюнкция, конъюнкция, эквиваленция, импликация.

Задание 2.
Сопоставьте название логического оператора с упрощенным:

Задание 3.
Чему будет равен последний столбец таблицы истинности для уравнения: А ∨ В ⇒ ¬С?

1. 11101010
2. 11101111
3. 11111110
4. 11000100

Задание 4.
Сократите логическое выражение: ¬(А ∨ В) ∧ (¬А ∨ С)

1. ¬(А ∧ В)
2. ¬А ∨ ¬В ∨ С
3. ¬А ∧ ¬В ∧ С
4. ¬А ∧ ¬В

Ответы: 1. — 2; 2. — 1Б, 2Г, 3В, 4Д, 5А; 3. — 1; 4. — 4.