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



Импликация

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

Импликация записывается как посылка следствие; применяются также стрелки другой формы и направленные в другую сторону (остриё всегда указывает на следствие).

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

Содержание

Булева логика

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

если , то истинно (1),

«Житейский» смысл импликации. Для более лёгкого понимания смысла прямой импликации и запоминания ее таблицы истинности может пригодиться житейская модель: А — начальник. Он может приказать «работай» (1) или сказать «делай что хочешь» (0). В — подчиненный. Он может работать (1) или бездельничать (0). В таком случае импликация — не что иное, как послушание подчиненного начальнику. По таблице истинности легко проверить, что послушания нет только тогда, когда начальник приказывает работать, а подчиненный бездельничает.

обратная импликация (от b к a, )

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

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

Импликация и следствие

Не следует путать импликацию (->) и логическое следование (=>). Импликация, как логическое выражение может сама принимать значения истины или лжи. Логическое же следование A => B, утверждает, что во всех случаях, когда формула А — истина, B — тоже будет истина.

Синонимические импликации выражения в русском языке

1. Когда А, то B
2. В в том случае, если А
3. При А В
4. Из А следует В
5. В случае А произойдет В
6. В, так как А
7. В потому, что А
8. Без А не будет В
9. В невозможно в отсутствие А
10. В необходимое условие для А
11. А достаточное условие для В.

Многозначная логика

Теория множеств

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

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

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

Классическая логика

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

Можно доказать эквивалентность импликации A → B формуле (с первого взгляда более очевидна её эквивалентность формуле , которая принимает значение «ложь» в случае, если выполняется A (посылка), но не выполняется B (следствие)).

Интуиционистская логика

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

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

Логика силлогизмов

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

Программирование

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

будет успешно выполняться если и только если верна импликация A→B. В то же время эти условия можно спокойно написать в одной строке, объединив их оператором AND или &&. При стандартных опциях компилятора (Delphi, C++ Builder) проверка идет до тех пор, пока результат не станет очевидным, и если А ложно, то (А и В) ложно вне зависимости от В, и не нужно ставить еще один условный оператор.

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

См. также

• Логический элемент
• Логическая операция
• Дизъюнкция
• Конъюнкция
• Отрицание
• Modus ponens
• Условная вероятность

Ссылки

Wikimedia Foundation . 2010 .

Смотреть что такое «Импликация» в других словарях:

ИМПЛИКАЦИЯ — (от лат. implicatio сплетение, от implico тесно связываю) логическая связка, соответствующая грамматической конструкции «если. то. », с помощью которой из двух простых высказываний образуется сложное высказывание. В импликативном высказывании… … Философская энциклопедия

ИМПЛИКАЦИЯ — ИМПЛИКАЦИЯ, логическое высказывание типа «если Р, то Q», соединяющее два элементарных высказывания Р (антецедент) и Q (логическое следствие). В математической ЛОГИКЕ эти два высказывания не связываются. Существует материальная импликация,… … Научно-технический энциклопедический словарь

Импликация — Импликация ♦ Implication Отношение между двумя суждениями, при котором второе является необходимым следствием первого: если р, то q. Если первое суждение истинно, истинно и второе. Если второе ложно, ложно и первое. Напротив, если первое… … Философский словарь Спонвиля

ИМПЛИКАЦИЯ — (от лат. implico тесно связываю) (материальная импликация) приблизительный логический эквивалент оборота если. то. ; операция, формализующая логические свойства этого оборота … Большой Энциклопедический словарь

ИМПЛИКАЦИЯ — [лат. implicatio сплетение, переплетение] лог. логическая операция, образующая сложное высказывание из двух высказываний посредством логической связки, соответствующей союзу «если. то. ». Словарь иностранных слов. Комлев Н.Г., 2006. импликация … Словарь иностранных слов русского языка

импликация — и, ж. implication f., нем. Implikation <лат. implicatio сплетение, переплетение. 1. В логике: операция, образующая сложное высказывание из двух высказываний посредством логической связки, соответствующей по смыслу союзу если . то . Крысин… … Исторический словарь галлицизмов русского языка

импликация — сущ., кол во синонимов: 1 • операция (457) Словарь синонимов ASIS. В.Н. Тришин. 2013 … Словарь синонимов

импликация — вовлечение проблема смысл значение последствие — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом Синонимы вовлечениепроблемасмыслзначениепоследствие EN… … Справочник технического переводчика

ИМПЛИКАЦИЯ — в информатике эквивалент оборота «если. то. », образующий сложное высказывание из двух высказываний, а также логическая операция, формализующая в программе логические свойства этого оборота … Большая политехническая энциклопедия

Импликация — логическая функция, следствие (если А, то В); в трактовке математической логики, материальная импликация , утверждение если А, то В считается ложной, только если А истинно, а В ложно, и при установлении истинности материальной импликации не… … Мир Лема — словарь и путеводитель

Источник

Операции над высказываниями и предикатами. Таблицы истинности

п.1. Отрицание

Расшифровка первого правила: высказывание «неверно, что для любого x выполняется A(x)» совпадает с высказыванием «найдётся x, для которого A(x) не выполняется».
Расшифровка второго правила: высказывание «неверно, что найдётся x, для которого выполняется A(x)» совпадает с высказыванием «для любого x A(x) не выполняется».

п.2. Конъюнкция

Обозначение конъюнкции A ∧ B, читается «А и В». Таблица истинности:

С точки зрения операций над множествами, конъюнкция аналогична пересечению двух множеств (см. §10 справочника для 8 класса).

С точки зрения записи условий, конъюнкция аналогична системе с фигурной скобкой.

п.3. Дизъюнкция

Обозначение дизъюнкции A ∨ B, читается «А или В». Таблица истинности:

С точки зрения операций над множествами, дизъюнкция аналогична объединению двух множеств (см. §10 справочника для 8 класса).

С точки зрения записи условий, дизъюнкция аналогична совокупности с квадратной скобкой. Например, запись \(\mathrm<(x^2-1\geq 0)\vee \left(x\gt \frac12\right)>\) аналогична совокупности $$ \left[ \begin < l >\mathrm & \\ \mathrm & \end\right. \Leftrightarrow x\leq -1 \cup x\gt\frac12 $$

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

Обозначение импликации A → B, читается «если A, то B».
Высказывание A называют «посылкой», а высказывание B – «заключением».
Значение импликации зависит от порядка высказываний.
Таблица истинности:

п.5. Эквиваленция

Обозначение эквиваленции A ↔ B, читается «A то же самое, что B» или «A эквивалентно B».
Таблица истинности:

п.6. Законы де Моргана

Докажем эквивалентность с помощью таблиц истинности:

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

Докажем эквивалентность с помощью таблиц истинности:

Высказывания слева и справа эквивалентны.

Не путайте эквиваленцию и эквивалентность.
Эквиваленция – это логическая операция с 0 или 1 на выходе, в зависимости от исходных А и В.
Эквивалентность(равносильность) – это отношение, при котором эквиваленция A ↔ B истинна при всех значениях логических переменных на области определения. Тогда A ⇔ B (пишут также A=B, A≡B, A

B).
Если A ⇔ B, то каждое из предложений является и необходимым и достаточным условием для другого предложения; используются словосочетания «необходимо и достаточно», «равносильно».

п.7. Алгоритм доказательства эквивалентности высказываний с помощью таблиц истинности

Например:
Докажем следующее свойство:

Столбцы совпадают. Значит, формулы эквивалентны.
Что и требовалось доказать.

п.8. Тавтология

Таблица истинности для тавтологии даёт итоговый столбец, заполненный только единицами.

Например: \(\mathrm\)

«Быть иль не быть» — это тавтология.

п.9. Примеры

Пример 1. Для формулы P(x, y)=(∃x∀y)(A(x,y)∧B(x,y))
сформулируйте предложения A и B, при которых:

а) формула всегда истинна; б) формула всегда ложна.
a) A(x,y): квадрат числа x больше y
B(x,y): куб числа x больше y
Пусть x = |y + 1|. Тогда x 2 = (y + 1) 2 > y – истинно ∀y
x 3 = |y + 1| 3 > y – ∀y
Таким образом, мы нашли x, при котором A(x,y) ∧ B(x,y) = 1 для любого y, т.е.
P(x,y) = 1.

б) A(x,y): x больше y
B(x,y): x меньше y
A(x,y)∧B(x,y) = 0 – ложно для любого y, т.к. не существует x, который одновременно был бы больше и меньше y.
P(x,y) = 0.

Источник

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

п.1. Отрицание

Расшифровка первого правила: высказывание «неверно, что для любого x выполняется A(x)» совпадает с высказыванием «найдётся x, для которого A(x) не выполняется».
Расшифровка второго правила: высказывание «неверно, что найдётся x, для которого выполняется A(x)» совпадает с высказыванием «для любого x A(x) не выполняется».

п.2. Конъюнкция

Обозначение конъюнкции A ∧ B, читается «А и В». Таблица истинности:

С точки зрения операций над множествами, конъюнкция аналогична пересечению двух множеств (см. §10 справочника для 8 класса).

С точки зрения записи условий, конъюнкция аналогична системе с фигурной скобкой.

п.3. Дизъюнкция

Обозначение дизъюнкции A ∨ B, читается «А или В». Таблица истинности:

С точки зрения операций над множествами, дизъюнкция аналогична объединению двух множеств (см. §10 справочника для 8 класса).

С точки зрения записи условий, дизъюнкция аналогична совокупности с квадратной скобкой. Например, запись \(\mathrm<(x^2-1\geq 0)\vee \left(x\gt \frac12\right)>\) аналогична совокупности $$ \left[ \begin < l >\mathrm & \\ \mathrm & \end\right. \Leftrightarrow x\leq -1 \cup x\gt\frac12 $$

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

Обозначение импликации A → B, читается «если A, то B».
Высказывание A называют «посылкой», а высказывание B – «заключением».
Значение импликации зависит от порядка высказываний.
Таблица истинности:

п.5. Эквиваленция

Обозначение эквиваленции A ↔ B, читается «A то же самое, что B» или «A эквивалентно B».
Таблица истинности:

п.6. Законы де Моргана

Докажем эквивалентность с помощью таблиц истинности:

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

Докажем эквивалентность с помощью таблиц истинности:

Высказывания слева и справа эквивалентны.

Не путайте эквиваленцию и эквивалентность.
Эквиваленция – это логическая операция с 0 или 1 на выходе, в зависимости от исходных А и В.
Эквивалентность(равносильность) – это отношение, при котором эквиваленция A ↔ B истинна при всех значениях логических переменных на области определения. Тогда A ⇔ B (пишут также A=B, A≡B, A

B).
Если A ⇔ B, то каждое из предложений является и необходимым и достаточным условием для другого предложения; используются словосочетания «необходимо и достаточно», «равносильно».

п.7. Алгоритм доказательства эквивалентности высказываний с помощью таблиц истинности

Например:
Докажем следующее свойство:

Столбцы совпадают. Значит, формулы эквивалентны.
Что и требовалось доказать.

п.8. Тавтология

Таблица истинности для тавтологии даёт итоговый столбец, заполненный только единицами.

Например: \(\mathrm\)

«Быть иль не быть» — это тавтология.

п.9. Примеры

Пример 1. Для формулы P(x, y)=(∃x∀y)(A(x,y)∧B(x,y))
сформулируйте предложения A и B, при которых:

а) формула всегда истинна; б) формула всегда ложна.
a) A(x,y): квадрат числа x больше y
B(x,y): куб числа x больше y
Пусть x = |y + 1|. Тогда x 2 = (y + 1) 2 > y – истинно ∀y
x 3 = |y + 1| 3 > y – ∀y
Таким образом, мы нашли x, при котором A(x,y) ∧ B(x,y) = 1 для любого y, т.е.
P(x,y) = 1.

б) A(x,y): x больше y
B(x,y): x меньше y
A(x,y)∧B(x,y) = 0 – ложно для любого y, т.к. не существует x, который одновременно был бы больше и меньше y.
P(x,y) = 0.

Источник

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

• Что такое таблицы истинности
• Логические операции
• Логические выражения
• Инверсия
• Конъюнкция
• Дизъюнкция
• Правила составления таблицы истинности
• Примеры построения таблицы истинности

Что такое таблицы истинности

Таблица истинности — это таблица, описывающая логическую функцию, а именно отражающую все значения функции при всех возможных значениях её аргументов.

Таблица истинности необходима для совершения логических операций. Она включает в себя n+1 столбцы и 2 n строки, где n — число используемых переменных. В первых n столбцах представлены разные значения аргументов функции, а в n+1 столбце представлены значения функции, которые она принимает на данном наборе аргументов.

Набором называется совокупность значений переменных. А = 0, В = 1. В случае, когда количество переменных n, число различных наборов будет равно 2 N . Например, для трех переменных число разных наборов будет равно 2 3 = 8.

Осторожно! Если преподаватель обнаружит плагиат в работе, не избежать крупных проблем (вплоть до отчисления). Если нет возможности написать самому, закажите тут.

Для создания таблиц истинности используются обозначения логических значений 0 (ложь) и 1 (истина).

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

Применение таблиц истинности чаще всего встречается в булевой алгебре и в цифровой электронной технике для описания работы логических схем.

Логические операции

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

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

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

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

Логическое выражение — это запись, принимающая логическое значение «истина» или «ложь».

Их можно разделить на два типа:

выражения, использующие операции сравнения и принимающие логические значения. Например, выражение a Определение

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

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

Конъюнкция

Конъюнкция — это логическое умножение. Эта операция, для которой требуются два и более логических величины. Конъюнкция соединяет логические высказывания при помощи связки «и». Связка изображается символом ∧.

Конъюнкция может быть истинной только в том случае, если оба высказывания истинны. Например, A ∧ B, если A = ложь, а B = истина, является ложным.

Дизъюнкция

Дизъюнкция — логическое сложение. Эта логическая операция соединяет два и более высказываний с помощью связки «или». Эта связка обозначается как ∨.

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

Правила составления таблицы истинности

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

Строить таблицы истинности необходимо по следующему алгоритму:

1. Вычислить число переменных в выражении (n).
2. Вычислить общее количество логических операций в выражении.
3. Определить последовательность, в которой будут выполняться логические операции.
4. Установить количество столбцов в таблице — количество переменных и количество операций.
5. Внести в шапку таблицы переменные и операции, соблюдая последовательность, определенную в пункте 3.
6. Высчитать количество строк в таблице, используя формулу m = 2 n
7. Занести в таблицу наборы входных переменных. Они представляют собой целый ряд n-разрядных двоичных чисел от 0 до 2 n −1.
8. Заполнить таблицу, совершая логические операции.

Примеры построения таблицы истинности

Задача

Построим таблицу истинности и решим выражение \( F = (A \vee B) \wedge (¬A \vee ¬B)\) . Будем пользоваться приведенным выше алгоритмом.

1. Число переменных в выражении n = 2.
2. Общее количество логических операций в выражении — 5.
3. Последовательность выполнения логических операций — 1, 5, 2, 4, 3.
4. Количество столбцов — 7. Логические переменные (А и В) + логические операции \(\vee\) , \(\wedge\) , \(¬\) , \(\vee\) , \(¬\) = 2 +5 = 7.
5. Количество строк — 5, исходя из m =2 n , таким образом 2 2 = 4, 4+1 (строка заголовков столбцов) = 5.
6. Заполним таблицу.

Решение

После заполнения таблицы, ответ будет выглядеть следующим образом:

F = 0 при A = B = 0 и A = B = 1

Задача

Построим еще одну таблицу истинности и решим выражение \(F = X \vee Y \wedge ¬Z\)

1. Число переменных в выражении n = 3.
2. Общее количество логических операций в выражении — 3.
3. Последовательность выполнения логических операций — 3, 2, 1.
4. Количество столбцов — 6. Логические переменные (X, Y, Z) + логические операции \( \vee\) , \(\wedge\) , ¬ = 3 + 3 = 6.
5. Количество строк — 9, исходя из m =2 n , таким образом 2 3 = 8, 8+1 (строка заголовков столбцов) = 9.
6. Заполним таблицу.

Решение

После заполнения таблицы, ответ будет выглядеть следующим образом:

F = 0, при X = Y = Z = 0; при X = Y = 0 и Z = 1.

Источник