Значок дизъюнкции. Простейшие логические операции в информатике. Импликация или логическое следование

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

Отличное определение

Неполное определение ↓

ДИЗЪЮНКЦИЯ

от лат. disjunctio - разобщение, различение)

Логическая операция - аналог употребления союза "или" в обычном языке, с помощью которой из двух или более исходных суждений строится новое суждение. Так, из суждений "Он - способен" и "Он - прилежен" с помощью операции "или" можно получить новое суждение "Он способен или он прилежен" (1). Из суждений "Он совершил преступление", "Он не совершал преступления" с помощью "или" можно получить новое суждение "Он совершил преступление или он не совершал преступления" (2). Суждение (1) истинно в трех случаях: 1) когда какой-то человек оказывается способным, но не прилежным; 2) когда этот человек оказывается прилежным, но не способным; 3) когда установлено, что этот человек и способен, и прилежен. Оно является ложным, когда оказалось, что этот человек не является ни способным, ни прилежным. Суждения типа (1) в логике называют соединительно-разделительными. Суждение же (2) истинно лишь только в том случае, когда имеет место или только первая ситуация ("Он совершил преступление"), или только вторая ситуация ("Он не совершал преступления"). Суждение (2) не допускает, чтобы имели место обе ситуации. Суждения типа (2) носят название исключающе-разделительных или строго разделительных.

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

Отрицание

Перед тем как начать подробно рассматривать конкретные примеры, перечислим основные логические операции в информатике:

• отрицание;
• сложение;
• умножение;
• следование;
• равенство.

Также перед началом изучения логических операций стоит сказать, что в информатике ложь обозначается "0", а правда "1".

Для каждого действия, как и в обычной математике, используются следующие знаки логических операций в информатике: ¬, v, &, ->.

Каждое действие возможно описать либо цифрами 1/0, либо просто логическими выражениями. Начнём рассмотрение математической логики с простейшей операции, использующей всего одну переменную.

Логическое отрицание - операция инверсии. Суть заключается в том, что если исходное выражение - истина, то результат инверсии - ложь. И наоборот, если исходное выражение - ложь, то результатом инверсии станет - правда.

При записи этого выражения используется следующее обозначение "¬A".

Приведём таблицу истинности - схему, которая показывает все возможные результаты операции при любых исходных данных.

То есть, если у нас исходное выражение - истина (1), то его отрицание будет ложным (0). А если исходное выражение - ложь (0), то его отрицание - истина (1).

Сложение

Оставшиеся операции требуют наличия двух переменных. Обозначим одно выражение -

А, второе - В. Логические операции в информатике, обозначающие действие сложения (или дизъюнкция), при написании обозначаются либо словом "или", либо значком "v". Распишем возможные варианты данных и результаты вычислений.

1. Е=1, Н=1 ,тогда Е v Н = 1. Если оба тогда и их дизъюнкция также истинна.
2. Е=0, Н=1 ,в итоге Е v Н = 1. Е=1, Н=0 , тогда Е v Н= 1. Если хотябы одно из выражений истинно, тогда и результат их сложения будет истиной.
3. Е=0, Н=0 ,результат Е v Н = 0. Если оба выражения ложны, то их сумма также - ложь.

Для краткости создадим таблицу истинности.

Умножение

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

1. Е=1, Н=1 ,тогда Е & Н = 1. Если оба тогда их конъюнкция - истина.
2. Если хотя бы одно из выражений - ложь, тогда результатом логического умножения также будет ложь.

• Е=1, Н=0, поэтому Е & Н = 0.
• Е=0, Н=1, тогда Е & Н = 0.
• Е=0, Н=0, итог Е & Н = 0.

Следствие

Логическая операция следования (импликация) - одна из простейших в математической логике. Она основана на единственной аксиоме - из правды не может следовать ложь.

1. Е=1, Н=, поэтому Е -> Н = 1. Если пара влюблена, то они могут целоваться - правда.
2. Е=0, Н=1, тогда Е -> Н = 1. Если пара не влюблена, то они могут целоваться - также может быть истиной.
3. Е=0, Н=0, из этого Е -> Н = 1. Если пара не влюблена, то они и не целуются - тоже правда.
4. Е=1, Н=0, результатом будет Е -> Н = 0. Если пара влюблена, то они не целуются - ложь.

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

Равенство

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

1. А=1, В=1, тогда А≡В = 1. Человек пьёт таблетки тогда и только тогда, когда болеет. (истина)
2. А=0, В=0, в итоге А≡В = 1. Человек не пьёт таблетки тогда и только тогда, когда не болеет. (истина)
3. А=1, В=0, поэтому А≡В = 0. Человек пьёт таблетки тогда и только тогда, когда не болеет. (ложь)
4. А=0, В=1 ,тогда А≡В = 0. Человек не пьёт таблетки тогда и только тогда, когда болеет. (ложь)

Свойства

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

А v В & ¬В -> В ≡ А

Порядок выполнения действий следующий.

1. В&(¬В)
2. А v(В&(¬В))
3. (А v(В&(¬В)))->В
4. ((А v(В&(¬В)))->В)≡А

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

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

Заключение

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

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

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

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

Если хотя бы один из ее членов ложен, то и вся конъюнкция ложна.

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

Обозначим конъюнкцию символом «˄». Используется также символ «&». Таблица истинности для конъюнкции такова.

Дизъюнкция

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

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

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

Пример . Суждение «В этом сезоне я хочу пойти на “Пиковую даму” или на “Аиду”» является нестрогой дизъюнкцией.

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

Пример . В суждении «Он учится в Московском или в Саратовском университете» подразумевается, что упоминаемый человек учится только в одном из этих университетов.

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

Символ «v» обозначает нестрогую дизъюнкцию, символ «V» – строгую дизъюнкцию. Применяются также другие обозначения.

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

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

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

Импликация

Импликация 3 – это суждение , полученное из любых двух суждений посредством логического союза «если …, то …» .

Примеры. «Если есть огонь, то есть дым», «Если число делится на 9, то оно делится на 3» и т.п.

Суждение, которому предпослано слово «если», называется основанием , или антецедентом 4 . Суждение, идущее после слова «то», называется следствием , или консеквентом 5 . Антецедент ‒ достаточное условие для консеквента, консеквент – необходимое условие для антецедента.

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

Пример. «Так как вода ‒ жидкость, она передает давление во все стороны равномерно».

Импликация не предполагает, что суждения А и В как-то связаны между собой по содержанию. В случае истинности В суждение «если А, то В» истинно независимо от того, является А истинным или ложным и связано оно по смыслу с В или нет.

Не может случиться так , чтобы основание было истинным, а следствие – ложным .

Только когда основание истинно, а следствие ложно, вся импликация ложна.

Примеры . Истинными считаются суждения: «Если на Солнце есть жизнь, то дважды два равно четырем», «Если Волга – озеро, то Токио – большой город» и т.п. К истинным относятся, к примеру, высказывания: «Если Солнце – куб, то Земля – треугольник», «Если дважды два равно пяти, то Токио ‒ маленький город» и т.п.

В обычном рассуждении все эти суждения вряд ли будут рассматриваться как имеющие смысл и еще в меньшей степени как истинные.

Будем обозначать импликацию символом «→». Таблица истинности для импликации такова.

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

Условное обозначение на структурных схемах логического элемента ИЛИ с двумя входами представлено на Рис. 2.8. Знак 1 на схеме - от устаревшего обозначения дизъюнкции как >=1 (т.е. значение дизъюнкции равно единице, если сумма значений операндов больше или равна 1). Связь между выходом F этой схемы и входами A и B описывается соотношением: F = A v B (читается как A или B).

Рис. 2.8. Логический элемент электронной схемы ИЛИ

Рассмотрим таблицу истинности для операции дизъюнкции ИЛИ с двумя входами A и B.

Таблица 2.3

Операция дизъюнкции (логическое сложение)

Для обозначения дизъюнкции используют знаки Ú, + , или .

Операции дизъюнкции в электрических контактных схемах соответствует параллельное соединение контактов. Например, электрическая контактная схема на рисунке 2.9 соответствует дизъюнкции .

Рис. 2.9 Параллельное соединение контактов

Набор выше рассмотренных логических функций НЕ, И, ИЛИ (отрицание, конъюнкция, дизъюнкция) наиболее известный и называется функционально полным набором или базисом . С помощью этих логических функций можно выразить любые другие логические функции.

Конъюнкция: соответствует союзу: «и», обозначается знаком^, обозначает логическое умножение.

Конъюнкция двух логических ~ истинна тогда и только тогда, когда оба высказываний истинны. Можно обобщить для любого количества переменных А^В^С = 1 если А=1, В=1, С=1.

Таблица истинности для операции «Конъюнкция»:

Таблица №2

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

Логическая операция соответствует союзу ИЛИ, обозначается знаком v, иначе называется ЛОГИЧЕСКОЕ СЛОЖЕНИЕ.

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

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

A v В v С = 0, только если А = О, В = О, С - 0.

Таблица истинности для операции «Дизъюнкция»:

Таблица №3

1. Инверсия

Логическая операция соответствует частице не, обозначается ¬ или ¯ и является логическим отрицанием.

Инверсия логической переменной истинна, если переменная ложна и наоборот: инверсия ложна, если переменная истинна.

Таблица истинности для операции «Инверсия»:

Таблица №5

Эквивалентность «А тогда В и только тогда», обозначается А ~ В

Таблица №6

При вычислении значения логического выражения (формулы) логические операции вычисляются в определенном порядке, согласно их приоритету:

инверсия;

конъюнкция;

дизъюнкция;

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

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

Формализация высказываний

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

Земля вращается вокруг своей оси и вокруг Солнца;

орбиты всех планет проходят вокруг Солнца;

С помощью формальных языков строятся формальные информационные модели (математические, логические и др.). Одним из наиболее широко используемых формальных языков является математика. Модели, построенные с использованием математических понятий и формул, называются математическими моделями. Язык математики является совокупностью формальных языков.

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

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

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

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