Основные логические операции
Логические операции в создании компьютерных программ — действия, которые производятся над входными данными. Такие функции производятся над сигналами булевского типа, то есть над примитивными выражениями, имеющими только два возможных значения: истина или ложь.
Виды операций
В программировании выделяют следующие виды функций:
- Логическое умножение или конъюнкция.
- Логическое сложение или дизъюнкция.
- Логическое отрицание или инверсия.
- Логическое следование или импликация.
- Логическая равнозначность или эквивалентность.
- Стрелка Пирса.
- Штрих Шеффера .
Логическое умножение (конъюнкция)
Конъюнкция — это действие, в результате которого каждым двум входным данным соответствует одно новое высказывание. Истинное значение на выходе получается, когда оба входных значения истинны.
Осторожно! Если преподаватель обнаружит плагиат в работе, не избежать крупных проблем (вплоть до отчисления). Если нет возможности написать самому, закажите тут.
Для обозначения логического умножения используют союз «и», значки \( \wedge\) , \(\&.\)
Таблица истинности для логического умножения выглядит так:
A, B — исходные данные;
A и B — значение, приобретаемое в результате реализации конъюнкции.
Из таблицы следуют свойства логического умножения:
- при ложном значении одной входной информации из двух конъюнкция будет ложной;
- при истинном значении переменных конъюнкция будет истинной;
- результат логического умножения не зависит от порядка записи ее переменных.
Логическое сложение (дизъюнкция)
Дизъюнкция — это булева функция, в итоге которой выходные данные будут ложными только при ложности всех исходных выражений.
Обозначается дизъюнкция союзом «или», символами +, \( \vee\) .
Таблица истинности логического сложения:
A, B — входная информация;
A или B — значение, приобретаемое в результате выполнения дизъюнкции.
Для дизъюнкции справедливы следующие утверждения:
- при истинности хотя бы одного подвыражения дизъюнкция будет истинной;
- при ложности всех высказываний дизъюнкция примет ложное значение;
- итог дизъюнкции не зависит от перемены мест слагаемых.
Логическое отрицание (инверсия)
Инверсия — выражение, ставящее в соответствие одному значению противоположное.
Условное обозначение логического отрицания: с помощью частицы «не», символов ¯, \(\neg.\)
Таблица истинности инверсии:
A — исходные данные;
не A — значение, приобретаемое в результате логического отрицания.
Логическое следование (импликация)
Импликация — это булева операция, ложная лишь тогда, когда первая исходная переменная является истиной, а вторая — ложью.
Следование записывается с помощью знака \(\rightarrow.\)
Таблица истинности для импликации:
A — входная информация, означающая условие;
B — входная информация, означающая следствие;
A → B — значение, приобретаемое в результате импликации.
По своему употреблению данная связка схожа со значением союзов «если. то. ».
Логическая равнозначность (эквивалентность)
Эквивалентность — выражение, являющееся истинным лишь в случае равенства двух входных элементов.
При записи равнозначности используют стрелки \(\Leftrightarrow\) , \(\leftrightarrow\) , \(\Xi\) .
Таблица истинности для равнозначности:
Стрелка Пирса
Стрелка Пирса — двухместное логическое действие со следующей последовательностью: сначала над исходными показаниями производится дизъюнкция, затем происходит отрицание полученного результата.
Данная манипуляция является отрицание логического сложения. Свое название рассматриваемая функция получила от своего автора — американского ученого Чарльза Пирса.
Запись стрелки Пирса осуществляется через знак \(\downarrow\) .
Таблица истинности для этой операции следующая:
Особенность стрелки Пирса заключается в ее возможности строить другие булевы функции.
Пример
Штрих Шеффера
Штрих Шеффера — это действие, приводящее к ложному итогу лишь при истинности обоих исходных данных. По порядку выполнения операций эта функция эквивалентна отрицанию конъюнкции.
Символ Шеффера назван по фамилии своего создателя — американского логика Генри Шеффера — и обозначается посредством знака \(\vert.\)
Таблица истинности для данной функции:
С помощью штриха Шеффера можно воспроизвести другие логические манипуляции.
Пример
Порядок выполнения операций
В составном логическом выражении действия выполняются в такой последовательности:
- инверсия;
- конъюнкция;
- дизъюнкция;
- импликация;
- эквивалентность.
Для построения нужного порядка, как и в математических выражениях, используют скобки.
Логическое сложение (дизъюнкция)
Так, из приведённых ниже четырёх составных высказываний, образованных с помощью операции логического сложения, ложно только первое, так как в последних трёх составных высказываниях хотя бы одно из простых высказываний истинно:
Логические основы работы ЭВМ 1
Основы логики и логические основы компьютера 3
1. Формы мышления 3
1.1. Логика — это наука о формах и способах мышления 3
1.3. Высказывание 4
1.4. Умозаключение 5
2. Алгебра логики 6
2.1. Логическое умножение (конъюнкция) 7
2.2. Логическое сложение (дизъюнкция) 9
2.3. Логическое отрицание (инверсия) 11
2.4. Логическое следование (импликация) 11
2.5. Логическое тождество (эквиваленция) 12
2.6. Операция «ИСКЛЮЧАЮЩЕЕ ИЛИ» 12
3. Порядок выполнения логических операций в сложном логическом выражении 14
4. Логические выражения и таблицы истинности 15
4.1. Логические выражения 15
4.2. Таблицы истинности 16
4.3. Равносильные логические выражения 17
5. Построение таблиц истинности для сложных выражений 18
6. Логические функции 19
6.1. Логическое следование (импликация) 20
6.2. Логическое равенство (эквивалентность) 21
7. Логические законы и правила преобразования логических выражений 22
7.1. Закон тождества 22
7.2. Закон непротиворечия 22
7.3. Закон исключённого третьего 22
7.4. Закон двойного отрицания 23
7.5. Законы де Моргана (общей инверсии) 23
7.6. Закон коммутативности (переместительный) 23
7.7. Закон ассоциативности (сочетательный) 23
7.8. Закон дистрибутивности (распределительный) 24
8. Логические элементы 24
8.1. Простейший логический элемент НЕ (инвертор) 25
Базовый набор операций 26
8.2. Логический элемент И (конъюнктор) 26
8.3. Логический элемент ИЛИ (дизъюнктор) 27
8.4. Логический элемент «ИСКЛЮЧАЮЩЕЕ ИЛИ» 27
9. Таблица 18 – Условные обозначения логических элементов компьютера 28
10. Вопросы для самопроверки 29
11. Решение логических задач 30
11.1. Примеры решения задач 30
Библиографический список 37
Запишем теперь операцию логического сложения на формальном языке алгебры логики.
Образуем составное высказывание F, которое получится в результате дизъюнкции двух простых высказываний:
С точки зрения алгебры высказываний мы записали формулу функции логического сложения, аргументами которой являются логические переменные А и В. Значение логической функции можно определить с помощью таблицы истинности данной функции, которая показывает, какие значения принимает логическая функция при всех возможных наборах ее аргументов (таблица 2).
Таблица 2 – Таблица истинности функции логического сложения (дизъюнкция)
Логические операции и их свойства
Конъюнкция или логическое умножение (в теории множеств – это пересечение)
Конъюнкция является сложным логическим выражением, которое истинно в том и только том случае, когда оба простых выражения являются истинными. Такая ситуация возможно лишь в единственном случае, во всех остальных случаях конъюнкция ложна.
Обозначение: &, $\wedge$, $\cdot$.
Таблица истинности для конъюнкции
- Если хотя бы одно из подвыражений конъюнкции ложно на некотором наборе значений переменных, то и вся конъюнкция будет ложной для этого набора значений.
- Если все выражения конъюнкции истинны на некотором наборе значений переменных, то и вся конъюнкция тоже будет истинна.
- Значение всей конъюнкции сложного выражения не зависит от порядка записи подвыражений, к которым она применяется (как в математике умножение).
Дизъюнкция или логическое сложение (в теории множеств это объединение)
Дизъюнкция является сложным логическим выражением, которое истинно практически всегда, за исключением, когда все выражения ложны.
Таблица истинности для дизъюнкции
- Если хотя бы одно из подвыражений дизъюнкции истинно на некотором наборе значений переменных, то и вся дизъюнкция принимает истинное значение для данного набора подвыражений.
- Если все выражения из некоторого списка дизъюнкции ложны на некотором наборе значений переменных, то и вся дизъюнкция этих выражений тоже ложна.
- Значение всей дизъюнкции не зависит от порядка записи подвыражений (как в математике – сложение).
Отрицание, логическое отрицание или инверсия (в теории множеств это отрицание)
Отрицание — означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО и в итоге получаем, что если исходное выражение истинно, то отрицание исходного – будет ложно и наоборот, если исходное выражение ложно, то его отрицание будет истинно.
Обозначения: не $A$, $\bar$, $¬A$.
Таблица истинности для инверсии
«Двойное отрицание» $¬¬A$ является следствием суждения $A$, то есть имеет место тавтология в формальной логике и равно самому значению в булевой логике.
Импликация или логическое следование
Импликация — это сложное логическое выражение, которое истинно во всех случаях, кроме как из истины следует ложь. То есть, данная логическая операция связывает два простых логических выражения, из которых первое является условием ($A$), а второе ($A$) является следствием условия ($A$).
Обозначения: $\to$, $\Rightarrow$.
Таблица истинности для импликации
- $A \to B = ¬A \vee B$.
- Импликация $A \to B$ ложна, если $A=1$ и $B=0$.
- Если $A=0$, то импликация $A \to B$ истинна при любом значении $B$, (из лжи может следовать истинна).
Эквивалентность или логическая равнозначность
Эквивалентность — это сложное логическое выражение, которое истинно на равных значениях переменных $A$ и $B$.
Обозначения: $\leftrightarrow$, $\Leftrightarrow$, $\equiv$.
Таблица истинности для эквивалентности
- Эквивалентность истинна на равных наборах значений переменных $A$ и $B$.
- КНФ $A \equiv B = (\bar \vee B) \cdot (A \cdot \bar)$
- ДНФ $A \equiv B = \bar \cdot \bar \vee A \cdot B$
Строгая дизъюнкция или сложение по модулю 2 ( в теории множеств это объединение двух множеств без их пересечения)
Строгая дизъюнкция истинна, если значения аргументов не равны.
Для функции трёх и более переменных результат выполнения операции будет истинным только тогда, когда количество аргументов равных $1$, составляющих текущий набор — нечетное. Такая операция естественным образом возникает в кольце вычетов по модулю 2, откуда и происходит название операции.
Обозначения: $A \oplus B$ (в языках программирования), $A≠B$, $A \wedge B$ (в языках программирования).
Таблица истинности для операции сложения по модулю два
Свойства строгой дизъюнкции:
- $a \oplus 0 = a$(идемпотентность)
- $a \oplus 1 = \bar$(отрицание)
- $a \oplus a = 0$(получение 0)
- $a \oplus b = b \oplus a$(коммутативность)
- $(a \oplus b) \oplus c = a \oplus (b \oplus c)$(ассоциативность)
- $(a \oplus b) \oplus b = a$(поглощение)
- $\bar \oplus b = a \oplus \bar = (a \equiv b)$(сравнения по модулю)
Стрелка Пирса
Бинарная логическая операция, булева функция над двумя переменными. Названа в честь Чарльза Пирса и введена в алгебру логики в $1880—1881$ гг.
Обозначения: $\downarrow$ , ИЛИ-НЕ
Таблица истинности для стрелки Пирса
Стрелка Пирса, как и конъюнкция, дизъюнкция, отрицание, образует базис для булевых функций двух переменных. При помощи стрелки Пирса, можно построить все остальные логические операции, например:
$X \downarrow X = ¬X$— отрицание
$(X \downarrow Y) \downarrow (X \downarrow Y) \equiv X \vee Y$ — дизъюнкция
$(X \downarrow X) \downarrow (Y \downarrow Y) \equiv X \wedge Y$ — конъюнкция
$((X \downarrow X) \downarrow Y) \downarrow ((X \downarrow X) \downarrow Y) = X \to Y$ — импликация
В электронике стрелка Пирса представлена в виде элемента, который носит название «операция 2ИЛИ-НЕ» (2-in NОR).
Штрих Шеффера
Булева функция двух переменных или бинарная логическая операция. Введена в рассмотрение Генри Шеффером в 1913 г.
Обозначения: $|$, эквивалентно операции И-НЕ.
Таблицей истинности для функции штрих Шеффера
Штрих Шеффера образует базис для всех булевых функций двух переменных. Применяя штрих Шеффера можно построить остальные операции, например,
$X \mid X = ¬X$ — отрицание
$(X \mid Y) \mid (X \mid Y) = (X \wedge Y)$ — конъюнкция
$(X \mid X) \mid (Y \mid Y) = X \vee Y$ — дизъюнкция
Для электроники это означает, что реализация схем возможна с использованием одного типового элемента (правда это дорогостоящий элемент).
Порядок выполнения логических операций в сложном логическом выражении
- Инверсия(отрицание);
- Конъюнкция (логическое умножение);
- Дизъюнкция и строгая дизъюнкция (логическое сложение);
- Импликация (следствие);
- Эквивалентность (тождество).
Для того чтобы изменить указанный порядок выполнения логических операций, необходимо использовать скобки.
Общие свойства
Для набора из $n$ логических переменных существует ровно $2^n$ различных значений. Таблица истинности для логического выражения от $n$ переменных содержит $n+1$ столбец и $2^n$ строк.
Основы логики. Логические операции и таблицы истинности
На данной странице будут рассмотренны 5 логических операций: конъюнкция, дизъюнкция, инверсия, импликация и эквивалентность, которых Вам будет достаточно для решения сложных логических выражений. Также мы рассмотрим порядок выполнения данных логических операций в сложных логических выражениях и представим таблицы истинности для каждой логической операции. Советуем Вам воспользоваться нашими программами для решения задач по математике, геометрии и теории вероятности. Помоми большого количества программ для решения задач на сайте работает форум, на котором Вы всегда можете задать вопрос и на котором Вам всегда помогуть с решением задач. Пользуйтесь нашими сервисами на здоровье!
Глоссарий, определения логики
Высказывание — это повествовательное предложение, про которое можно определенно сказать истинно оно или ложно (истина (логическая 1), ложь (логический 0)).
Логические операции — мыслительные действия, результатом которых является изменение содержания или объема понятий, а также образование новых понятий.
Логическое выражение — устное утверждение или запись, в которое, наряду с постоянными величинами, обязательно входят переменные величины (объекты). В зависимости от значений этих переменных величин (объектов) логическое выражение может принимать одно из двух возможных значений: истина (логическая 1) или ложь (логический 0).
Сложное логическое выражение — логическое выражение, состоящее из одного или нескольких простых логических выражений (или сложных логических выражений), соединенных с помощью логических операций.
Логические операции и таблицы истинности
1) Логическое умножение или конъюнкция:
Конъюнкция — это сложное логическое выражение, которое считается истинным в том и только том случае, когда оба простых выражения являются истинными, во всех остальных случаях данное сложеное выражение ложно.
Обозначение: F = A & B.
Таблица истинности для конъюнкции
| A | B | F |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 0 |
2) Логическое сложение или дизъюнкция:
Дизъюнкция — это сложное логическое выражение, которое истинно, если хотя бы одно из простых логических выражений истинно и ложно тогда и только тогда, когда оба простых логических выраженныя ложны.
Обозначение: F = A + B.
Таблица истинности для дизъюнкции
| A | B | F |
| 1 | 1 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
3) Логическое отрицание или инверсия:
Инверсия — это сложное логическое выражение, если исходное логическое выражение истинно, то результат отрицания будет ложным, и наоборот, если исходное логическое выражение ложно, то результат отрицания будет истинным. Другими простыми слова, данная операция означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО.
Таблица истинности для инверсии
| A | неА |
| 1 | 0 |
| 0 | 1 |
4) Логическое следование или импликация:
Импликация — это сложное логическое выражение, которое истинно во всех случаях, кроме как из истины следует ложь. Тоесть данная логическая операция связывает два простых логических выражения, из которых первое является условием (А), а второе (В) является следствием.
Таблица истинности для импликации
| A | B | F |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 0 | 1 |
5) Логическая равнозначность или эквивалентность:
Эквивалентность — это сложное логическое выражение, которое является истинным тогда и только тогда, когда оба простых логических выражения имеют одинаковую истинность.
Таблица истинности для эквивалентности
| A | B | F |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |
Порядок выполнения логических операций в сложном логическом выражении
1. Инверсия;
2. Конъюнкция;
3. Дизъюнкция;
4. Импликация;
5. Эквивалентность.
Для изменения указанного порядка выполнения логических операций используются скобки.