что такое строгая дизъюнкция в информатике
Логические операции и их свойства
Вы будете перенаправлены на Автор24
Конъюнкция или логическое умножение (в теории множеств – это пересечение)
Конъюнкция является сложным логическим выражением, которое истинно в том и только том случае, когда оба простых выражения являются истинными. Такая ситуация возможно лишь в единственном случае, во всех остальных случаях конъюнкция ложна.
Таблица истинности для конъюнкции
Дизъюнкция или логическое сложение (в теории множеств это объединение)
Дизъюнкция является сложным логическим выражением, которое истинно практически всегда, за исключением, когда все выражения ложны.
Таблица истинности для дизъюнкции
Готовые работы на аналогичную тему
Отрицание, логическое отрицание или инверсия (в теории множеств это отрицание)
Таблица истинности для инверсии
Импликация или логическое следование
Таблица истинности для импликации
Эквивалентность или логическая равнозначность
Таблица истинности для эквивалентности
Строгая дизъюнкция или сложение по модулю 2 ( в теории множеств это объединение двух множеств без их пересечения)
Строгая дизъюнкция истинна, если значения аргументов не равны.
Таблица истинности для операции сложения по модулю два
Свойства строгой дизъюнкции:
Стрелка Пирса
Таблица истинности для стрелки Пирса
Стрелка Пирса, как и конъюнкция, дизъюнкция, отрицание, образует базис для булевых функций двух переменных. При помощи стрелки Пирса, можно построить все остальные логические операции, например:
$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$ — дизъюнкция
Для электроники это означает, что реализация схем возможна с использованием одного типового элемента (правда это дорогостоящий элемент).
Порядок выполнения логических операций в сложном логическом выражении
Для того чтобы изменить указанный порядок выполнения логических операций, необходимо использовать скобки.
Общие свойства
Получи деньги за свои студенческие работы
Курсовые, рефераты или другие работы
Автор этой статьи Дата написания статьи: 24 03 2016
Что такое строгая дизъюнкция в информатике
2) Логическое сложение или дизъюнкция:
Таблица истинности для дизъюнкции
| A | B | F |
| 1 | 1 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
3) Логическое отрицание или инверсия:
Таблица истинности для инверсии
| A | ¬ А |
| 1 | 0 |
| 0 | 1 |
4) Логическое следование или импликация:
«A → B» истинно, если из А может следовать B.
Обозначение: F = A → B.
Таблица истинности для импликации
| A | B | F |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 0 | 1 |
5) Логическая равнозначность или эквивалентность:
Что такое строгая дизъюнкция в информатике
§ 2. Логические операции. Формализация высказываний
Сейчас мы познакомимся с шестью основными логическими операциями. Каждая из них имеет несколько названий и обозначений.
Названия операции
Возможные обозначения
Конъюнкция, логическое умножение, операция И, операция AND.
`&, ^^, *,` по аналогии с алгебраическим умножением может никак не обозначаться
Дизъюнкция, нестрогая дизъюнкция, логическое сложение, операция ИЛИ, операция OR.
Строгая дизъюнкция, разделительная дизъюнкция, исключающее ИЛИ, сложение по модулю `2`.
Эквивалентность, эквиваленция, равенство, равнозначность.
Импликация, следование, следствие
Теперь для того чтобы строго определить эти логические операции, нам нужно для каждой из них выписать таблицу истинности. Все перечисленные операции кроме отрицания имеют два операнда. Знак операции в выражениях пишется между операндами (как в алгебре чисел). Операция отрицания имеет один операнд и в выражениях записывается либо в виде черты над операндом, либо в виде символа «приставка» слева от операнда.
1) `p` и `q` ложны. Это значит, что четырёхугольник не является квадратом и его стороны не равны. Это возможная ситуация.
2) `p` – ложно, `q` – истинно. Это значит, что четырёхугольник не является квадратом, но стороны у него равны. Это возможно (ромб).
3) `p` – истинно, `q` – истинно. Это значит, что четырёхугольник является квадратом и стороны у него равны. Это возможная ситуация.
4) `p` – истинно, `q` – ложно. Это значит, что четырёхугольник является квадратом, но стороны у него не равны. Это невозможная ситуация.
Очень часто вместо «присвоим логическим переменным эти высказывания» говорят «обозначим высказывания следующим образом». В дальнейшем мы тоже будем использовать этот речевой оборот.
Кроме базовых операций существует еще ряд дополнительных логических операций. Рассмотрим отдельные из них, наиболее часто встречающиеся в логических выражениях.
Строгая (разделительная) дизъюнкция
Высказывание, образованное из двух высказываний путем объединения их связкой «либо» называется разделительной (строгой) дизъюнкцией, исключающим ИЛИ.
В отличии от обычной дизъюнкции, разделительная дизъюнкция утверждает, что произойдет только одно из двух событий. Например, пусть есть два высказывания: А – «Число 22 четное», В – «Число 22 нечетное», тогда высказывание А либо В (Формально, F = А ⊕ В): «Число 22 четное либо нечетное». В сложном высказывании утверждается, что число 22 либо только четное, либо только нечетное.
Определение. Логическая операция, ставящая в соответствие двум высказываниям новое, являющееся истинным тогда и только тогда, когда только одно из двух исходных высказываний является истинным, называется строгой, или разделительной дизъюнкцией.
Логическая операция строгая (разделительная) дизъюнкция задается следующей таблицей истинности:
| A | B | F = A ⊕ B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Импликация
Высказывание, образованное из двух высказываний путем объединения их связкой «если…, то…» называется импликацией.
Например, пусть есть два высказывания: А – «На каникулах будет экскурсия», В – «Старшеклассники посетят Третьяковскую галерею», тогда высказывание Если А, то В (Формально, F = А ⇒ В): «Если на каникулах будет экскурсия, то старшеклассники посетят Третьяковскую галерею».
Определение. Логическая операция, ставящая в соответствие двум элементарным высказываниям новое высказывание, являющееся ложным тогда и только тогда, когда условие (посылка) — истинно, а следствие (заключение) — ложно, называется импликацией.
Логическая операция импликация задается следующей таблицей истинности:
| A | B | F = A ⇒ B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Эквивалентность
Высказывание, образованное из двух высказываний путем объединения их связкой «…тогда и только тогда, когда…» называется эквивалентностью.
Например, пусть есть два высказывания: А – «Треугольник равнобедренный», В – «Треугольник имеет хотя бы две равные стороны», тогда высказывание А тогда и только тогда, когда В (Формально, F = А ≡ В): «Треугольник равнобедренный, тогда и только тогда, когда он имеет хотя бы две равные стороны».
Определение. Логическая операция, ставящая в соответствие двум элементарным высказываниям новое, являющееся истинным тогда и только тогда, когда оба исходных высказывания одновременно истинны или одновременно ложны, называется эквивалентностью.
Логическая операция эквивалентность задается следующей таблицей истинности:
| A | B | F = A ≡ B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Copyright © 2014-2021, Урок информатики
Все права защищены
Информатика. 10 класс
Конспект урока
Информатика, 10 класс. Урок № 11.
Тема — Алгебра логики. Таблицы истинности
Перечень вопросов, рассматриваемых в теме: высказывание, логическая переменная, логические операции (отрицание, конъюнкция, дизъюнкция, строгая дизъюнкция, импликация, эквиваленция), логические выражения, предикаты и их множества истинности, таблицы истинности и их анализ.
Глоссарий по теме: импликация, эквиваленция, предикат, примеры законов алгебры логики.
Основная литература по теме урока:
Л. Л. Босова, А. Ю. Босова. Информатика. Базовый уровень: учебник для 10 класса
— М.: БИНОМ. Лаборатория знаний, 2017 (с.174—197)
Открытые электронные ресурсы по теме:
Теоретический материал для самостоятельного изучения:
Алгебра логики — раздел математики, изучающий высказывания, рассматриваемые с точки зрения их логических значений (истинности или ложности), и логические операции над ними.
Алгебра логики возникла в середине XIX века в трудах английского математика Джорджа Буля. Ее создание представляло собой попытку решать традиционные логические задачи алгебраическими методами. В 1938 году Клод Шеннон применил алгебру логики для описания процесса функционирования релейно-контактных и электронно-ламповых схем. Логическое высказывание — это повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.
Например, предложение «Джордж Буль — основоположник алгебры логики» истинно, а «Солнце — спутник Земли» ложно.
Употребляемые в обычной речи логические связки «не», «и», «или», «если…то», «тогда и только тогда» и др. позволяют из уже заданных высказываний строить новые высказывания. Высказывания, образованные из других высказываний, называются составными. Высказывание, никакая часть которого не является высказыванием, называется элементарным. Например, из двух простых высказываний (каких?) можно получить следующее составное высказывание: «Алгебра логики является основой строения логических схем компьютеров и служит математической основой решения сложных логических задач». Истинность или ложность составных высказываний зависит от истинности или ложности образующих их высказываний и определённой трактовки связок (логических операций над высказываниями).
Обоснование истинности или ложности элементарных высказываний не является задачей алгебры логики. Эти вопросы решаются теми науками, к сфере которых относятся элементарные высказывания. Такое сужение интересов позволяет обозначать высказывания символическими именами (например, А, В, С).
Логическая переменная — это переменная, которая обозначает любое высказывание и может принимать логические значения «истина» или «ложь». Для логических значений «истина» — «ложь» могут использоваться следующие обозначения: И — Л, true — false, да — нет, 1 — 0.
Логическая операция полностью может быть описана таблицей истинности, указывающей, какие значения принимает составное высказывание при всех возможных значениях образующих его элементарных высказываний.
В алгебре логики имеется шесть логических операций. Из курса информатики 8—9 классов вам знакомы три из них:
— отрицание (инверсия, логическое НЕ)
Высказыванию ставится в соответствие новое высказывание, значение которого противоположно исходному.
— конъюнкция (логическое умножение, логическое И)
Высказывание истинно тогда и только тогда, когда истинны оба исходных высказывания.
— дизъюнкция (логическое сложение, логическое ИЛИ)
Высказывание ложно тогда и только тогда, когда ложны оба исходных высказывания.
Рассмотрим новые логические операции.
— Логическая операция, ставящая в соответствие двум высказываниям новое, являющееся ложным тогда и только тогда, когда первое высказывание (посылка) истинно, а второе (следствие) — ложно, называется импликацией (от лат. implicatio — сплетение, тесная связь) или логическим следованием.
Операция импликации обозначается символом 
и задается следующей таблицей истинности:
В разговорной речи импликации соответствуют предложения, содержащие связку «если…, то». Как правило, эту связку мы используем, когда хотим показать зависимость одного события от другого.
Импликацию можно заменить на выражение, использующее ранее изученные операции НЕ и ИЛИ: 
— Логическая операция, ставящая в соответствие двум высказываниям новое, являющееся истинным тогда и только тогда, когда только одно из двух высказываний истинно, называется строгой (исключающей) дизъюнкцией.
Строгая дизъюнкция обозначается символом
и задается следующей таблицей истинности:
В русском языке строгой дизъюнкции соответствует связка «либо». Например, в пословице «Либо пан, либо пропал», выполнение обоих условий одновременно невозможно. В отличие от обычной дизъюнкции в высказывании, содержащем строгую дизъюнкцию, мы утверждаем, что произойдет только одно событие.
Строгую дизъюнкцию можно представить через базовые операции следующим образом:
Чтобы доказать это равенство, достаточно для всех возможных комбинаций и вычислить значения выражения, стоящего в правой части равенства, и сравнить их со значениями выражения 
для тех же исходных данных.
— Логическая операция, ставящая в соответствие двум высказываниям новое, являющееся истинным, когда оба исходных высказывания истинны или оба исходных высказывания ложны, называется эквиваленцией или равнозначностью.
В логике эквиваленция обозначается символом 
и задается следующей таблицей истинности:
В разговорной речи эквивалентности соответствует связка «тогда и только тогда, когда», а в математике — «необходимо и достаточно».
Если посмотреть внимательно на таблицы истинности для двух последних логических операций, то можно заметить, что эквивалентность — это обратная операция для операции «исключающее ИЛИ», т. е. 
Можно заменить эквивалентность выражением, которое включает только базовые логические операции: 
Составное логическое высказывание можно представить в виде логического выражения (формулы), состоящего из логических констант (0, 1), логических переменных, знаков логических операций и скобок.
Для логического выражения справедливо:
При преобразовании или вычислении значения логического выражения логические операции выполняются в соответствии с их приоритетом:
Операции одного приоритета выполняются в порядке их следования, слева направо. Как в математике, скобки меняют порядок выполнения операций.
Дан фрагмент таблицы истинности выражения F.