Меню Рубрики

Выберите значки для обозначения логической операции импликация

Содержание

Импликация
Не больше, IMPLY

Диаграмма Венна
Определение x → y <displaystyle x
ightarrow y>
Таблица истинности ( 1011 ) <displaystyle (1011)>
Логический вентиль
Нормальные формы
Дизъюнктивная x ¯ + y <displaystyle <overline >+y>
Конъюнктивная x ¯ + y <displaystyle <overline >+y>
Полином Жегалкина 1 ⊕ x ⊕ x y <displaystyle 1oplus xoplus xy>
Принадлежность предполным классам
Сохраняет 0 Нет
Сохраняет 1 Да
Монотонна Нет
Линейна Нет
Самодвойственна Нет

Импликация (от лат. implicatio — «связь») — бинарная логическая связка, по своему применению приближенная к союзам «если…, то…».

Импликация записывается как посылка ⇒ <displaystyle Rightarrow > следствие; применяются также стрелки другой формы и направленные в другую сторону, но всегда указывающие на следствие.

Суждение, выражаемое импликацией, выражается также следующими способами [1] [2] :

  • посылка является условием, достаточным для выполнения следствия;
  • следствие является условием, необходимым для истинности посылки.

Импликация играет очень важную роль в умозаключениях. С её помощью формулируются определения различных понятий, теоремы, научные законы [3] .

При учёте смыслового содержания высказываний импликация подразумевает причинную связь между посылкой и заключением [4] .

Содержание

Булева логика [ править | править код ]

В булевой логике импликация — это функция двух переменных (они же — операнды операции, они же — аргументы функции). Переменные могут принимать значения из множества < 0 , 1 ><displaystyle <0,1>> . Результат также принадлежит множеству < 0 , 1 ><displaystyle <0,1>> . Вычисление результата производится по простому правилу, либо по таблице истинности. Вместо значений 0 , 1 <displaystyle 0,1> может использоваться любая другая пара подходящих символов, например false , true <displaystyle operatorname ,operatorname > или F , T <displaystyle F,T> или «ложь», «истина».

Импликация как булева функция ложна лишь тогда, когда посылка истинна, а следствие ложно. Иными словами, импликация A → B <displaystyle A o B> это сокращённая запись для выражения ¬ A ∨ B <displaystyle
eg Alor B> .

«Житейский» смысл импликации. Для более лёгкого понимания смысла прямой импликации и запоминания её таблицы истинности может пригодиться житейская модель:

А — начальник. Он может приказать «работай» (1) или сказать «делай что хочешь» (0). В — подчиненный. Он может работать (1) или бездельничать (0).

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

обратная импликация (англ.) русск. (от b к a, A ∨ ( ¬ B ) <displaystyle Alor (
eg B)> )

Обратная импликация — отрицание (негация, инверсия) обнаружения увеличения (перехода от 0 к 1, инкремента).

отрицание (инверсия, негация) прямой импликации

отрицание (инверсия, негация) обратной импликации (англ.) русск. ( ¬ A ∧ B <displaystyle lnot Aland B> ), разряд займа в двоичном полувычитателе.

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

Синонимические импликации выражения в русском языке [ править | править код ]

  • Если А, то Б
  • Б в том случае, если А
  • При А будет Б
  • Из А следует Б
  • В случае А произойдет Б
  • Б, так как А
  • Б, потому что А
  • А — достаточное условие для Б
  • Б — необходимое условие для А

Многозначная логика [ править | править код ]

Теория множеств [ править | править код ]

Импликация высказываний означает, что одно из них следует из другого. Импликация обозначается символом ⇒ <displaystyle Rightarrow > , и ей соответствует вложение множеств: пусть A ⊂ B <displaystyle Asubset B> , тогда

x ∈ A ⇒ x ∈ B . <displaystyle xin ARightarrow xin B.>

Например, если A <displaystyle A> — множество всех квадратов, а B <displaystyle B> — множество прямоугольников, то, конечно, A ⊂ B <displaystyle Asubset B> и

(a — квадрат) ⇒ <displaystyle Rightarrow > (a — прямоугольник).

(если a является квадратом, то a является прямоугольником).

Классическая логика [ править | править код ]

Можно доказать эквивалентность импликации A → B <displaystyle A
ightarrow B> формуле ¬ A ∨ B <displaystyle
eg Alor B> (с первого взгляда более очевидна её эквивалентность формуле ¬ ( A ∧ ¬ B ) <displaystyle
eg (Aland
eg B)> , которая принимает значение «ложь» в случае, если выполняется A (посылка), но не выполняется B (следствие)). Поэтому любое высказывание можно заменить на эквивалентное ему без знаков импликации.

Интуиционистская логика [ править | править код ]

В интуиционистской логике импликация никоим образом не сводится к отрицаниям. Скорее напротив, отрицание ¬A можно представить в виде A → ⊭ <displaystyle A
ightarrow
vDash > , где ⊭ <displaystyle
vDash > — пропозициональная константа «ложь». Впрочем, такое представление отрицания возможно и в классической логике.

В интуиционистской теории типов импликации соответствует множество (тип) отображений из A в B.

Логика силлогизмов [ править | править код ]

В учении о силлогизмах импликации отвечает «общеутвердительное атрибутивное высказывание».

Программирование [ править | править код ]

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

будет успешно выполняться тогда и только тогда, когда верна импликация A → B. В то же время эти условия можно спокойно написать в одной строке, объединив их оператором конъюнкции.

При стандартных опциях компилятора (Delphi, C++ Builder) [ прояснить ] проверка идёт до тех пор, пока результат не станет очевидным, и если А ложно, то (А и В) ложно вне зависимости от В, и не нужно ставить ещё один условный оператор.

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

Импликация или логическое следование соответствует обороту «если. то. », обозначается A→ B. Таблица истинности импликации имеет вид:

Высказывание A→ B ложно в том и только в том случае, когда условие (первое высказывание A) истинно, а следствие (второе высказывание B) ложно.

A = «Завтра будет хорошая погода»

A→ B = «Если завтра будет хорошая погода, я пойду гулять»

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

A= « Поезд прибывает на данный путь»

В= «Подается сигнал, что путь закрыт»

Рассматриваемое сложное высказывание истинно, если:

1) поезд прибывает, сигнал «закрыт» (1, 1, 1);

2) поезд не прибывает, сигнал «свободен» (0, 0, 1);

3) поезд не пребывает, сигнал «закрыт» (0, 0, 1) — если поезд не пребывает, безопасен любой сигнал.

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

Операция импликации в русском языке является самой «загадочной». Ей соответствую также следующие речевые обороты: «из А следует В»; «В только в случае А»; «А влечет В»; «А достаточно для В»; «В необходимо для А».

В обычной речи связка "если . то…" описывает причинно-следственную связь между высказываниями. Но в логических операциях смысл высказываний не учитывается. Рассматривается только их истинность или ложность. Поэтому не надо смущаться "бессмысленностью" импликаций, образованных высказываниями, совершенно не связанными по содержанию. Например, такими: "если президент США — демократ, то в Африке водятся жирафы", "если арбуз — ягода, то в бензоколонке есть бензин".

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

Эквивалентность (равноценность или равнозначность) соответствует оборотам речи «тогда и только тогда», «в том и только в том случае», «. равносильно . » и обозначается A↔B , или A≡B.

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

Выражение A↔B истинно в том и только в том случае, когда оба исходных высказывания одновременно истинны или одновременно ложны.

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

В русском языке операции эквивалентности также соответствует речевой оборот «A необходимо и достаточно B».

Строгая дизъюнкция

Строгая дизъюнкция или «исключающее или», соответствует оборотам речи «или. или. » или «либо. либо...», и обозначается AB .

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

Выражение AB истинно в том и только в том случае, когда исходные высказывания A и B не равны между собой.

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

A B C = 1, (3)

Логические формулы и функции Логическая формула

С помощью логических переменных и символов логических операций любое сложное (составное) высказывание можно записать в виде логической формулы. Её определение:

Всякая логическая переменная и символы "истина" ("1") и "ложь" ("0") — формулы.

Если А и В — формулы, то — тоже формулы.

Никаких других формул в алгебре высказываний нет.

Значение логической формулы определяется заданными значениями входящих в фор­мулу переменных. Тем самым каждая формула может рассматриваться как способ задания функции в алгебре высказываний.

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

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

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

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

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

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

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

Попробуй обратиться за помощью к преподавателям

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

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

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

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

Задай вопрос специалистам и получи
ответ уже через 15 минут!

Обозначения: не $A$, $ar$, $¬A$.

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

«Двойное отрицание» $¬¬A$ является следствием суждения $A$, то есть имеет место тавтология в формальной логике и равно самому значению в булевой логике.

Импликация или логическое следование

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

Обозначения: $ o$, $Rightarrow$.

Таблица истинности для импликации

  1. $A o B = ¬A vee B$.
  2. Импликация $A o B$ ложна, если $A=1$ и $B=0$.
  3. Если $A=0$, то импликация $A o B$ истинна при любом значении $B$, (из лжи может следовать истинна).

Эквивалентность или логическая равнозначность

Эквивалентность — это сложное логическое выражение, которое истинно на равных значениях переменных $A$ и $B$.

Обозначения: $leftrightarrow$, $Leftrightarrow$, $equiv$.

Таблица истинности для эквивалентности

Строгая дизъюнкция или сложение по модулю 2 ( в теории множеств это объединение двух множеств без их пересечения)

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

Для функции трёх и более переменных результат выполнения операции будет истинным только тогда, когда количество аргументов равных $1$, составляющих текущий набор — нечетное. Такая операция естественным образом возникает в кольце вычетов по модулю 2, откуда и происходит название операции.

Обозначения: $A oplus B$ (в языках программирования), $A≠B$, $A wedge 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 o Y$ — импликация

В электронике стрелка Пирса представлена в виде элемента, который носит название «операция 2ИЛИ-НЕ» (2-in NОR).

Штрих Шеффера

Булева функция двух переменных или бинарная логическая операция. Введена в рассмотрение Генри Шеффером в 1913 г.

Обозначения: $|$, эквивалентно операции И-НЕ.

Таблицей истинности для функции штрих Шеффера

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

Для электроники это означает, что реализация схем возможна с использованием одного типового элемента (правда это дорогостоящий элемент).

Порядок выполнения логических операций в сложном логическом выражении

  1. Инверсия(отрицание);
  2. Конъюнкция (логическое умножение);
  3. Дизъюнкция и строгая дизъюнкция (логическое сложение);
  4. Импликация (следствие);
  5. Эквивалентность (тождество).

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

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

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

Так и не нашли ответ
на свой вопрос?

Просто напиши с чем тебе
нужна помощь

Читайте также:  Kitfort kt 501 аккумулятор

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Adblock
detector