Отрицание в информатике кратко
Обновлено: 04.07.2024
Алгебра логики (англ. algebra of logic) — один из основных разделов математической логики, в котором методы алгебры используются в логических преобразованиях.
Современная алгебра логики является разделом математической логики и изучает логические операции над высказываниями с точки зрения их истинностного значения (истина, ложь). Высказывания могут быть истинными, ложными или содержать истину и ложь в разных соотношениях.
Логическое высказывание — это любое повествовательное предложение, в отношении которого можно однозначно утверждать, что его содержание истинно или ложно.
Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение.
Логических значений всего два: истина (TRUE) и ложь (FALSE). Это соответствует цифровому представлению — 1 и 0. Результаты каждой логической операции можно записать в виде таблицы. Такие таблицы называют таблицами истинности.
Основные операции алгебры логики
Операция, используемая относительно одной величины, называется унарной. Таблица значений данной операции имеет вид
A | ¬A |
истина | ложь |
ложь | истина |
A | ¬A |
1 | 0 |
0 | 1 |
Высказывание $A↖$ ложно, когда А истинно, и истинно, когда А ложно.
Геометрически отрицание можно представить следующим образом: если А — это некоторое множество точек, то $A↖$ — это дополнение множества А, т. е. все точки, которые не принадлежат множеству А.
Таблица истинности операции имеет вид
A | B | A ∧ B |
истина | ложь | ложь |
ложь | истина | ложь |
ложь | ложь | ложь |
истина | истина | истина |
A | B | A ∧ B |
1 | 0 | 0 |
0 | 1 | 0 |
0 | 0 | 0 |
1 | 1 | 1 |
Высказывание А ∧ В истинно только тогда, когда оба высказывания — А и В истинны.
Геометрически конъюнкцию можно представить следующим образом: если А, В — это некоторые множества точек, то А ∧ В есть пересечение множеств А и В.
Таблица истинности операции имеет вид
A | B | A ∨ B |
истина | ложь | истина |
ложь | истина | истина |
ложь | ложь | ложь |
истина | истина | истина |
A | B | A ∨ B |
1 | 0 | 1 |
0 | 1 | 1 |
0 | 0 | 0 |
1 | 1 | 1 |
Высказывание А ∨ В ложно только тогда, когда оба высказывания — А и В ложны.
Геометрически логическое сложение можно представить следующим образом: если А, В — это некоторые множества точек, то А ∨ В — это объединение множеств А и В, т. е. фигура, объединяющая и квадрат, и круг.
Таблица истинности операции имеет вид
А | В | А ⊕ B |
истина | ложь | истина |
ложь | истина | истина |
ложь | ложь | ложь |
истина | истина | ложь |
А | В | А ⊕ B |
1 | 0 | 1 |
0 | 1 | 1 |
0 | 0 | 0 |
1 | 1 | 0 |
Высказывание А ⊕ В истинно только тогда, когда высказывания А и В имеют различные значения.
Таблица истинности операции имеет вид
А | В | А → В |
истина | ложь | ложь |
ложь | истина | истина |
ложь | ложь | истина |
истина | истина | истина |
А | В | А → В |
1 | 0 | 0 |
0 | 1 | 1 |
0 | 0 | 1 |
1 | 1 | 1 |
Для операции импликации справедливо утверждение, что из лжи может следовать все что угодно, а из истины — только истина.
Таблица истинности операции эквивалентности имеет вид
А | В | А ∼ В |
истина | ложь | ложь |
ложь | истина | ложь |
ложь | ложь | истина |
истина | истина | истина |
А | В | А ∼ В |
1 | 0 | 0 |
0 | 1 | 0 |
0 | 0 | 1 |
1 | 1 | 1 |
Зная значения простых высказываний, можно на основании таблиц истинности определить значения сложных высказываний. При этом важно знать, что для представления любой функции алгебры логики достаточно трех операций: конъюнкции, дизъюнкции и отрицания.
Сложение по модулю два | А ⊕ В | $(A↖ ∧B) ∧ (A ∧ B↖)$ |
Импликация | А → В | $A↖ ∨ B$ |
Эквивалентность | А ∼ В | $(A↖ ∧ B↖) ∨ (A ∧ B)$ |
Примеры решения задач
Пример 1. Определить для указанных значений X значение логического высказывания ((X > 3) ∨ (X 3) ∨ (1 3) ∨ (12 3) ∨ (3 2) → (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 — высказывание ложно.
Логические выражения и их преобразование
Логические выражения могут включать в себя функции, алгебраические операции, операции сравнения и логические операции. В этом случае приоритет выполнения действий следующий:
- вычисление существующих функциональных зависимостей;
- выполнение алгебраических операций (вначале умножение и деление, затем вычитание и сложение);
- выполнение операций сравнения (в произвольном порядке);
- выполнение логических операций (вначале операции отрицания, затем операции логического умножения, логического сложения, последними выполняются операции импликации и эквивалентности).
В логическом выражении могут использоваться скобки, которые изменяют порядок выполнения операций.
Пример. Найти значение выражения:
$1 ≤ a ∨ A ∨ sin(π/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 = истина;
Из логических элементов составляются электронные логические схемы, выполняющие более сложные логические операции. Набор логических элементов, состоящий из элементов НЕ, ИЛИ, И, с помощью которых можно построить логическую структуру любой сложности, называется функционально полным.
Построение таблиц истинности логических выражений
Для логической формулы всегда можно записать таблицу истинности, т. е. представить заданную логическую функцию в табличном виде. В этом случае таблица должна содержать все возможные комбинации аргументов функции (формулы) и соответствующие значения функции (результаты формулы на заданном наборе значений).
Удобной формой записи при нахождении значений функции является таблица, содержащая, кроме значений переменных и значений функции, также значения промежуточных вычислений. Рассмотрим пример построения таблицы истинности для формулы $↖ ∧ X2 ∨ ↖ ∨ X1$.
X1 | X2 | $↖$ | $↖$ \ X2 | X1 ∧ X2 | $↖$ | $↖$ ∧ X2 ∨ $↖$ | $↖$ ∧ X2 ∨ $↖$ ∨ X1 |
1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 |
0 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 |
Если функция принимает значение 1 при всех наборах значений переменных, она является тождественно-истинной; если при всех наборах входных значений функция принимает значение 0, она является тождественно-ложной; если набор выходных значений содержит как 0, так и 1, функция называется выполнимой. Приведенный выше пример является примером тождественно-истинной функции.
Зная аналитическую форму логической функции, всегда можно перейти к табличной форме логических функций. С помощью заданной таблицы истинности можно решить обратную задачу, а именно: для заданной таблицы построить аналитическую формулу логической функции. Различают две формы построения аналитической зависимости логической функции по таблично заданной функции.
1. Дизъюнктивно нормальная форма (ДНФ) — сумма произведений, образованных из переменных и их отрицаний для ложных значений.
Алгоритм построения ДНФ следующий:
Пример. Построить функцию, определяющую, что первое число равно второму, используя метод ДНФ. Таблица истинности функции имеет вид
X1 | X2 | F(X1, X2) |
1 | 1 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
0 | 0 | 1 |
Решение. Выбираем наборы значений аргументов, в которых функция равна 1. Это первая и четвертая строки таблицы (строку заголовка при нумерации не учитываем).
Записываем логические произведения аргументов этих наборов, объединив их логической суммой: X1 ∧ X2 ∨ X1 ∧ X2 .
Записываем отрицание относительно аргументов выбранных наборов, имеющих ложное значение (четвертая строка таблицы; второй набор в формуле; первый и второй элементы): X1 ∧ X2 ∨ $↖$ ∧ $↖$.
2. Конъюнктивно нормальная форма (КНФ) — произведение сумм, образованных из переменных и их отрицаний для истинных значений.
Алгоритм построения КНФ следующий:
Примеры решения задач
Пример 1. Рассмотрим предыдущий пример, т. е. построим функцию, определяющую, что первое число равно второму, используя метод КНФ. Для заданной функции ее таблица истинности имеет вид
X1 | X2 | F(X1, X2) |
1 | 1 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
0 | 0 | 1 |
Решение. Выбираем наборы значений аргументов, в которых функция равна 0. Это вторая и третья строки (строку заголовка при нумерации не учитываем).
Записываем логические суммы аргументов этих наборов, объединив их логическим произведением: X1 ∨ X2 ∧ X1 ∨ X2 .
Записываем отрицание относительно аргументов выбранных наборов, имеющих истинное значение (вторая строка таблицы, первый набор формулы, второй элемент; для третьей строки, а это второй набор формулы, первый элемент): X1 ∨ $↖$ ∧ $↖$ ∨ X2.
Таким образом, получена запись логической функции в КНФ.
Полученные двумя методами значения функций являются эквивалентными. Для доказательства этого утверждения используем правила логики: F(X1, X2) = X1 ∨ $↖$ ∧ $↖$ ∨ X2 = X1 ∧ $↖$ ∨ X1 ∧ X2 ∨ $↖$ ∧ $↖$ ∨ $↖$ ∧ X2 = 0 ∨ X1 ∨ X2 ∨ $↖$ ∧ $↖$ ∨ 0 = X1 ∧ X2 ∨ $↖$ ∧ $↖$.
Пример 2. Построить логическую функцию для заданной таблицы истинности:
X1 | X2 | F(X1, X2) |
1 | 1 | 1 |
1 | 0 | 0 |
0 | 1 | 1 |
0 | 0 | 0 |
Решение. Используем алгоритм ДНФ для построения исходной функции:
X1 | X2 | F(X1, X2) | ||
1 | 1 | 1 | • | X1 ∧ X2 |
1 | 0 | 0 | ||
0 | 1 | 1 | • | $↖$ ∧ X2 |
0 | 0 | 0 |
Искомая формула: X1 ∧ X2 ∨ $↖$ ∧ X2 .
Ее можно упростить: X1 ∧ X2 ∨ $↖$ ∧ X2 = X2 ∧ (X1 ∨ $↖$) = X2 ∧ 1 = X2.
Пример 3. Для приведенной таблицы истинности построить логическую функцию, используя метод ДНФ.
X1 | X2 | X3 | F(X1, X2, X3) | ||
1 | 1 | 1 | 1 | • | X1 ∧ X2 ∧ X3 |
1 | 0 | 1 | 0 | ||
0 | 1 | 1 | 1 | • | $↖$ ∧ X2 ∧ X3 |
0 | 0 | 1 | 0 | ||
1 | 1 | 0 | 1 | • | X1 ∧ X2 ∧ $↖$ |
1 | 0 | 0 | 1 | • | X1 ∧ $↖$ ∧ $↖$ |
0 | 1 | 0 | 0 | ||
0 | 0 | 0 | 0 |
Искомая формула: X1 ∧ X2 ∧ X ∨ $↖$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $↖$ ∪ X1 ∧ $↖$ ∧ $↖$.
Формула достаточно громоздка, и ее следует упростить:
X1 ∧ X2 ∧ X3 ∨ $↖$ ∧ X2 ∧ X3 ∨ X1 ∧ X2 ∧ $↖$ ∨ X1 ∧ $↖$ ∧ $↖$ = X2 ∧ X3 ∧ (X1 ∨ $↖$) ∨ X1 ∧ $↖$ ∧ (X2 ∨ $↖$) = X2 ∧ X3 ∨ X1 ∧ $↖$.
Таблицы истинности для решения логических задач
Составление таблиц истинности — один из способов решения логических задач. При использовании такого способа решения, условия, которые содержит задача, фиксируются с помощью специально составленных таблиц.
Примеры решения задач
Пример 1. Составить таблицу истинности для охранного устройства, которое использует три датчика и срабатывает при замыкании только двух из них.
X1 | X2 | X3 | Y(X1, X2, X3) |
1 | 1 | 1 | 0 |
1 | 1 | 0 | 1 |
1 | 0 | 1 | 1 |
1 | 0 | 0 | 0 |
0 | 1 | 1 | 1 |
0 | 1 | 0 | 0 |
0 | 0 | 1 | 0 |
0 | 0 | 0 | 0 |
Пример 2. Составить расписание уроков на день, учитывая, что урок информатики может быть только первым или вторым, урок математики — первым или третьим, а физики — вторым или третьим. Возможно ли составить расписание, удовлетворив всем требованиям? Сколько существует вариантов расписания?
Решение. Задача легко решается, если составить соответствующую таблицу:
1-й урок | 2-й урок | 3-й урок | |
Информатика | 1 | 1 | 0 |
Математика | 1 | 0 | 1 |
Физика | 0 | 1 | 1 |
Из таблицы видно, что существуют два варианта искомого расписания:
- математика, информатика, физика;
- информатика, физика, математика.
Пример 3. В спортивный лагерь приехали трое друзей — Петр, Борис и Алексей. Каждый из них увлекается двумя видами спорта. Известно, что таких видов спорта шесть: футбол, хоккей, лыжи, плавание, теннис, бадминтон. Также известно, что:
- Борис — самый старший;
- играющий в футбол младше играющего в хоккей;
- играющие в футбол и хоккей и Петр живут в одном доме;
- когда между лыжником и теннисистом возникает ссора, Борис мирит их;
- Петр не умеет играть ни в теннис, ни в бадминтон.
Какими видами спорта увлекается каждый из мальчиков?
Решение. Составим таблицу и отразим в ней условия задачи, заполнив соответствующие клетки цифрами 0 и 1 в зависимости от того, ложно или истинно соответствующее высказывание.
Так как видов спорта шесть, получается, что все мальчики увлекаются разными видами спорта.
Футбол | Хоккей | Лыжи | Плавание | Бадминтон | Теннис | |
Петр | 0 | 0 | 1 | 1 | 0 | 0 |
Борис | 0 | 0 | 0 | |||
Алексей | 0 | 0 |
Из таблицы видно, что в теннис может играть только Алексей.
Футбол | Хоккей | Лыжи | Плавание | Бадминтон | Теннис | |
Петр | 0 | 0 | 1 | 1 | 0 | 0 |
Борис | 0 | 0 | 0 | 0 | ||
Алексей | 1 | 0 | 0 | 0 | 0 | 1 |
Окончательно получаем, что Борис увлекается хоккеем и бадминтоном. Итоговая таблица будет выглядеть следующим образом:
Футбол | Хоккей | Лыжи | Плавание | Бадминтон | Теннис | |
Петр | 0 | 0 | 1 | 1 | 0 | 0 |
Борис | 0 | 1 | 0 | 0 | 1 | 0 |
Алексей | 1 | 0 | 0 | 0 | 0 | 1 |
Ответ: Петр увлекается лыжами и плаванием, Борис играет в хоккей и бадминтон, а Алексей занимается футболом и теннисом.
Логическая операция инверсия — унарная операция над высказываниями, в результате выполнения которой высказывание становится противоположным исходному высказыванию.
Другие названия отрицания — отрицание или логическое НЕ.
Инверсия или отрицание изучается в информатике при рассмотрении раздела алгебра логики.
В естественных языках отрицанию соответствует частица ‘не‘ или слова ‘неверно, что‘. Например, если высказывание A = ‘Москва — столица России’, то его отрицание будет звучать как ‘Москва не столица России’.
В языках программирования для отрицания используют обозначение ‘ not ‘ или восклицательный знак ‘ ! ‘ (например, not(x = 5) или !(x ).
Для обозначения отрицания используют символ ¬ или черту над высказыванием. Например, отрицание A можно обозначить либо ¬A , либо \overline.
Как набрать знак инверсии на клавиатуре
В Word чтобы набрать символ ¬ необходимо нажать левый Alt, и удерживая его на цифровой клавиатуре (которая справа клавиатуры) набрать цифры 0172. Т. е. символ ¬ — это Alt+0172 . Режим Num Lock должен быть включен.
Чтобы сделать черту над буквой, необходимо зайти в пункт меню Вставка -> Формула (или Уравнение). После этого на панели инструментов найти диакритические знаки и среди них нужный нам знак с чертой над буквой.
Таблица истинности инверсия
Отрицание и круги Эйлера
Обозначим высказывание A кругом, тогда отрицание A будет располагаться снаружи круга.
Конъюнкция или логическое умножение (в теории множеств – это пересечение)
Конъюнкция является сложным логическим выражением, которое истинно в том и только том случае, когда оба простых выражения являются истинными. Такая ситуация возможно лишь в единственном случае, во всех остальных случаях конъюнкция ложна.
Обозначение: &, $\wedge$, $\cdot$.
Таблица истинности для конъюнкции
- Если хотя бы одно из подвыражений конъюнкции ложно на некотором наборе значений переменных, то и вся конъюнкция будет ложной для этого набора значений.
- Если все выражения конъюнкции истинны на некотором наборе значений переменных, то и вся конъюнкция тоже будет истинна.
- Значение всей конъюнкции сложного выражения не зависит от порядка записи подвыражений, к которым она применяется (как в математике умножение).
Дизъюнкция или логическое сложение (в теории множеств это объединение)
Дизъюнкция является сложным логическим выражением, которое истинно практически всегда, за исключением, когда все выражения ложны.
Таблица истинности для дизъюнкции
- Если хотя бы одно из подвыражений дизъюнкции истинно на некотором наборе значений переменных, то и вся дизъюнкция принимает истинное значение для данного набора подвыражений.
- Если все выражения из некоторого списка дизъюнкции ложны на некотором наборе значений переменных, то и вся дизъюнкция этих выражений тоже ложна.
- Значение всей дизъюнкции не зависит от порядка записи подвыражений (как в математике – сложение).
Готовые работы на аналогичную тему
Отрицание, логическое отрицание или инверсия (в теории множеств это отрицание)
Отрицание - означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО и в итоге получаем, что если исходное выражение истинно, то отрицание исходного – будет ложно и наоборот, если исходное выражение ложно, то его отрицание будет истинно.
Обозначения: не $A$, $\bar$, $¬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$ — импликация
Штрих Шеффера
Булева функция двух переменных или бинарная логическая операция. Введена в рассмотрение Генри Шеффером в 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$ строк.
Информатика не может существовать без такого важного раздела математики, который называется алгеброй логики. В данной статье будет рассказана основополагающая информация по данной теме, обозначены её главные правила и законы.
Что такое алгебра и алгебра логики
Алгебра — это раздел математики, который обобщенно можно охарактеризовать, как расширение и обобщение арифметики.
Алгебра логики — это раздел математической логики, который исследует операции над высказываниями.
Законы алгебры логики
Имеется большое количество правил в данной сфере деятельности, но сегодня будет рассмотрено несколько основных.
Переместительный закон - предназначен для процесса сложения и вычитания. Суть данного правила в том, что обозначения А и В в операциях дизъюнкции и конъюнкции можно менять.
Сочетательный закон - применяется, когда есть или только операция дизъюнкции, или только операция конъюнкции. Тогда можно обходиться без скобок или хаотично ставить скобки.
Распределительный закон - имеется два типа данного правила: дистрибутивность дизъюнкции относительно конъюнкции и дистрибутивность конъюнкции относительно дизъюнкции. Первый тип схож с дистрибутивным законом алгебры, а второй — нет, поэтому его нужно доказывать.
Закон двойственности и инверсии (закон Моргана) - основоположником данного правила стал шотландский математик и логик де Морган. Он разработал правило, которое связывает логические операции конъюкцию (И) и дизъюнкцию (ИЛИ) с помощью отрицания.
Основные законы алгебры логики представлены в таблице:
Логические выражения
В информатике предоставляется два вида высказываний: простое и сложное.
Простое — это утверждение, которое обычно обозначается в виде предложения и про него можно сказать — ложное оно или истинное.
Нью-Йорк — столица США (ложное);
в России 1117 городов (верное).
Сложное высказывание обозначает некий набор простых утверждений, которые связаны логическими процессами.
Идёт дождь, а у меня нет зонта.
Основные логические операции
Логические процессы подразделяются на несколько классов. Рассмотрим их последовательно.
Логическое отрицание (инверсия) —НЕ
Данная операция используется при обозначении отрицания. Она обозначается знаками — NO, NOT, ! В=2 (истина), а после выполнения операции отрицания, В, к примеру, приобретет значение 1 (ложное).
Таблица истинности инверсии:
Результаты операции НЕ следующие:
если исходное выражение истинно, то результат его отрицания будет ложным;
если исходное выражение ложно, то результат его отрицания будет истинным.
Логическое сложение (дизъюнкция, объединение) — ИЛИ
Таблица истинности операции ИЛИ:
Логическое умножение(конъюнкция) — И
В истории данная операция также обозначается как логическое умножение и конъюнкция. Данная операция обозначается элементами — И, AND, &&, &.
За объект описания возьмём А и В. Оба данных выражения могут иметь или неверное значение, или правдивое значение. Для применения операции логическое умножение, и А, и В должны является истинными (то есть равными единице).
При всех остальных значениях операция будет ложной.
Таблица истинности операции И приведена ниже:
Логическое следование (импликация) — ЕСЛИ ТО
Необходимо запомнить, что данная операция ложна только тогда, когда из первого ложного утверждения следует ложный итог. На компьютерном языке данный процесс обозначается формулой: if. then.
Таблица истинности операции ЕСЛИ ТО выглядит так:
Операция эквивалентности (равнозначности) - А ТОГДА И ТОЛЬКО ТОГДА, КОГДА В
Данная операция определяется так: сложное высказывание будет истинно тогда и только тогда, когда и А, и В — истинные.
И наоборот: сложное высказывание будет ложным тогда и только тогда, когда и А, и В — ложные.
Таблица истинности операции эквивалентности:
Читайте также:
- Эффект пельтье кратко и понятно
- Температура тела земноводных кратко
- Реалистическая литература возрождение модернистской и авангардной тенденций в литературе кратко
- Применение принудительных мер воспитательного воздействия к несовершеннолетним кратко
- Договор фрахтования судна на время тайм чартер кратко