Как раскрывается импликация в информатике

Импликация и эквивалентность

Известно, что любая логическая формула может быть выражена через три ранее рассмотренные логические операции, однако на практике часто используют еще две логические связки. Первая из них называется импликацией и служит для задания так называемых условных высказываний. В русском языке этой логической операции соответствуют фразы если . то . или когда . тогда . Импликация — двухместная операция: часть формулы до импликации называют основанием условного высказывания, а часть, расположенную за ней — следствием. В логических формулах импликация обозначается знаком -> . Операция A -> B определяет логическую функцию, тождественно совпадающую с функцией !A || B.

Пример
Дано сложное высказывание: «Если выглянет солнце, то станет тепло». Требуется записать его в виде логической формулы.
Обозначим через А простое высказывание «выглянет солнце», а через В — «станет тепло». Тогда логической формулой этого сложного высказывания будет импликация: A -> B.

Другой распространенной операцией является эквивалентность. Ее аналог в разговорной речи — фразы, подобные словосочетанию тогда и только тогда, когда . или если и только если . Для ее обозначения используется символ или просто =. Мы будем использовать для обозначения эквивалентности обе эти формы. Отметим, что логическая формула A B эквивалентна формуле (A -> B) && (B -> A).

Пример
Дано сложное высказывание: «В зачетную книжку выставляется оценка за экзамен тогда и только тогда, когда он сдан». Нужно преобразовать высказывание к логической формуле. Обозначим через А простое высказывание «В зачетную книжку выставляется оценка за экзамен», а через В — «Экзамен сдан». Тогда логическая формула сложного высказывания запишется в виде A B.

Приведем таблицу истинности, задающую операции импликации и эквивалентности:

A	B	A -> B	A B
T	T	T	T
T	F	F	F
F	T	T	F
F	F	T	T

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

Импликация

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

A	B	A → B
И	И	И
И	Л	Л
Л	И	И
Л	Л	И

В классической логике (см. Логика), формальной логике (см. Логика формальная), языках формальных теорий (см. Формализация) и языках программирования импликация составляет одну из пяти наиболее распространённых логических связок, или логических операций (см. Логические операции), наряду с конъюнкцией (см. Конъюнкция), дизъюнкцией (см. Дизъюнкция), эквиваленцией (см. Эквиваленция) и отрицанием (см. Отрицание).

Библиография

Ершов Ю. Л., Палютин Е. А. Математическая логика. — М., 1979.
Марков А. А. Элементы математической логики. — М., 1984.
Мендельсон Э. Введение в математическую логику, изд. — М., 1984.
Новиков П. С. Элементы математической логики, изд. — М., 1973.
Справочная книга по математической логике, т. . — М., .
Сидоренко Е. А. Логическое следование и условные высказывания. — М., 1983.
Стяжкин Н. И. Формирование математической логики. — М., «Наука», 1967.
Эдельман С. Л. Математическая логика. — М., 1975.
Gomez-Torrente M. Tarski on Logical Consequence. — Notre Dame Journal of Formal Logic. 1996. Vol. 37. № 1.
Tarski A. On the Concept of Logical Consequence. — Tarski A. Logic, Semantics, Metamatematics. Indianapolis, 1983. P. .

Логика: понятия и концепции

Абдукция
Аксиома
Аксиома выбора
Алгебра логики
Алгоритм
Алгоритмическая неразрешимость
Аналогия
Антиномизм
Антиномии отношения именования
Антиномия
Апория
Аргументация
Возможные миры
Вопрос
Вопрос и ответ
Высказывание
Дедукция
Денотат
Дефиниция
Дизъюнкция
Закон достаточного основания
Закон исключённого третьего
Закон противоречия
Закон тождества
Законы логики
Значение
Импликация
Имя
Индукция
Интенсионал и экстенсионал
Исчисление классов
Исчисление секвенций
Коннотация
Конструктивизм математический
Конструктивизм радикальный
Конструктивный объект
Конструктивный процесс
Конъюнкция
Логика
Логика вероятностная
Логика вопросов
Логика временная
Логика высказываний
Логика дедуктивная
Логика деонтическая
Логика индуктивная
Логика интенсиональная
Логика интуиционистская
Логика классов
Логика комбинаторная
Логика конструктивная
Логика математическая
Логика модальная
Логика науки
Логика нечёткая
Логика отношений
Логика паранепротиворечивая
Логика предикатов
Логика причинности
Логика релевантная
Логика свободная
Логика событий
Логика символическая
Логика трансцендентальная
Логика философская
Логика формальная
Логика эпистемическая
Логики многозначные
Логики неклассические
Логическая семантика
Логическая теория
Логическая форма
Логические ошибки
Логические связки
Логический атомизм
Логический вывод
Логический фатализм
Логическое противоречие
Логическое следование
Металогика
Метатеория
Метаязык
Метод семантических таблиц
Множество
Модальность
Модус
Обоснование
Определимость
Опровержение
Отношение
Отрицание
Парадокс
Подтверждение
Понятие
Предложение
Принцип многозначности
Проблема разрешимости
Программа интуиционизма
Программа логицизма
Программа формализма
Программа эффективизма
Противоречие
Равенство
Рассуждение
Рассуждения правдоподобные
Семантика возможных миров
Семантические категории
Силлогизм
Силлогистика
Смысл
Софизм
Суждение
Суждения аналитические
Теория именования
Теория множеств
Теория моделей
Теория нелинейных динамик
Теория семантических категорий
Термин
Тождество
Умозаключение
Эквиваленция
Энтимема

Базисные концепты

Новые концепты

Исследования:
Исследования государств
Исследования общества
Исследования образования
Исследования экономики
Исследования рынков
Исследования медиа
Энциклопедия:
Государства
Организации
Персоналии
Концепты
Тексты
Библиотека:
Гуманитарный базис
Гуманитарная мысль

Здесь поберите флизелиновые обои для любой комнаты.
Гуманитарный портал ISSN 2310-1792 About • Agreement • Terms

Логика

f) символ 1 используется для обозначения истины (истинного высказывания); символ 0 – для обозначения лжи (ложного высказывания).

1.2. Два логических выражения, содержащих переменные, называются равносильными (эквивалентными), если значения этих выражений совпадают при любых значениях переменных. Так, выражения А → В и (¬А) \/ В равносильны, а А /\ В и А \/ В – нет (значения выражений разные, например, при А = 1, В = 0).

1.3. Приоритеты логических операций: инверсия (отрицание), конъюнкция (логическое умножение), дизъюнкция (логическое сложение), импликация (следование), тождество. Таким образом, ¬А \/ В \/ С \/ D означает то же, что и

Возможна запись А \/ В \/ С вместо (А \/ В) \/ С. То же относится и к конъюнкции: возможна запись А /\ В /\ С вместо (А /\ В) /\ С.

2. Свойства

Приведенный ниже список НЕ претендует на полноту, но, надеемся, достаточно представителен.

2.1. Общие свойства

Для набора из n логических переменных существует ровно 2n различных значений. Таблица истинности для логического выражения от n переменных содержит n+1 столбец и 2n строк.

2.2.Дизъюнкция

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

2.3. Конъюнкция

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

2.4. Простые дизъюнкции и конъюнкции

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

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

2.5. Импликация

Импликация A →B равносильна дизъюнкции (¬А) \/ В. Эту дизъюнкцию можно записать и так: ¬А \/ В.
Импликация A →B принимает значение 0 (ложь) только если A=1 и B=0. Если A=0, то импликация A →B истинна при любом значении B.

Логические операции и их свойства

Конъюнкция или логическое умножение (в теории множеств – это пересечение)

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

Обозначение: &, $\wedge$, $\cdot$.

Таблица истинности для конъюнкции

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

Получи помощь с рефератом от ИИ-шки
ИИ ответит за 2 минуты

Дизъюнкция или логическое сложение (в теории множеств это объединение)

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

Таблица истинности для дизъюнкции

Если хотя бы одно из подвыражений дизъюнкции истинно на некотором наборе значений переменных, то и вся дизъюнкция принимает истинное значение для данного набора подвыражений.
Если все выражения из некоторого списка дизъюнкции ложны на некотором наборе значений переменных, то и вся дизъюнкция этих выражений тоже ложна.
Значение всей дизъюнкции не зависит от порядка записи подвыражений (как в математике – сложение).

Начинай год правильно ��
Выигрывай призы на сумму 400 000 ₽

Отрицание, логическое отрицание или инверсия (в теории множеств это отрицание)

Отрицание — означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО и в итоге получаем, что если исходное выражение истинно, то отрицание исходного – будет ложно и наоборот, если исходное выражение ложно, то его отрицание будет истинно.

Обозначения: не $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$ строк.