СВОЙСТВА ЛОГИЧЕСКИХ ОПЕРАЦИЙ
1. Обозначения
1.1. Обозначения для логических связок (операций):
a) отрицание (инверсия, логическое НЕ) обозначается ¬ (например, ¬А);
b) конъюнкция
(логическое умножение, логическое И) обозначается /\
(например, А /\ В) либо & (например, А & В);
c) дизъюнкция
(логическое сложение, логическое ИЛИ) обозначается \/
(например, А \/ В);
d) следование (импликация) обозначается → (например, А → В);
e) тождество обозначается ≡ (например, A ≡ B). Выражение A ≡ B истинно тогда и только тогда, когда значения A и B совпадают (либо они оба истинны, либо они оба ложны);
f) символ 1 используется для обозначения истины (истинного высказывания); символ 0 – для обозначения лжи (ложного высказывания).
1.2. Два логических выражения, содержащих переменные, называются равносильными (эквивалентными), если значения этих выражений совпадают при любых значениях переменных. Так, выражения А → В и (¬А) \/ В равносильны, а А /\ В и А \/ В – нет (значения выражений разные, например, при А = 1, В = 0).
1.3. Приоритеты логических операций: инверсия (отрицание), конъюнкция (логическое умножение), дизъюнкция (логическое сложение), импликация (следование), тождество. Таким образом, ¬А \/ В \/ С \/ D означает то же, что и
((¬А) \/ В)\/ (С \/ D).
Возможна запись А \/ В \/ С вместо (А \/ В) \/ С. То же относится и к конъюнкции: возможна запись А /\ В /\ С вместо (А /\ В) /\ С.
2. Свойства
Приведенный ниже список НЕ претендует на полноту, но, надеемся, достаточно представителен.
2.1. Общие свойства
- Для набора из n логических переменных существует ровно 2 n различных значений. Таблица истинности для логического выражения от n переменных содержит n+1 столбец и 2 n строк.
2.2.Дизъюнкция
- Если хоть одно из подвыражений, к которым применяется дизъюнкция, истинно на некотором наборе значений переменных, то и вся дизъюнкция истинна для этого набора значений.
- Если все выражения из некоторого списка истинны на некотором наборе значений переменных, то дизъюнкция этих выражений тоже истинна.
- Если все выражения из некоторого списка ложны на некотором наборе значений переменных, то дизъюнкция этих выражений тоже ложна.
- Значение дизъюнкции не зависит от порядка записи подвыражений, к которым она применяется.
2.3. Конъюнкция
- Если хоть одно из подвыражений, к которым применяется конъюнкция, ложно на некотором наборе значений переменных, то и вся конъюнкция ложна для этого набора значений.
- Если все выражения из некоторого списка истинны на некотором наборе значений переменных, то конъюнкция этих выражений тоже истинна.
- Если все выражения из некоторого списка ложны на некотором наборе значений переменных, то конъюнкция этих выражений тоже ложна.
- Значение конюнкции не зависит от порядка записи подвыражений, к которым она применяется.
2.4. Простые дизъюнкции и конъюнкции
Назовем (для удобства) конъюнкцию простой , если подвыражения, к которым применяется конъюнкция, – различные переменные или их отрицания. Аналогично, дизъюнкция называется простой , если подвыражения, к которым применяется дизъюнкция, – различные переменные или их отрицания.
- Простая конъюнкция принимает значение 1 (истина) ровно на одном наборе значений переменных.
- Простая дизъюнкция принимает значение 0 (ложь) ровно на одном наборе значений переменных.
2.5. Импликация
- Импликация A →B равносильна дизъюнкции (¬ А) \/ В. Эту дизъюнкцию можно записать и так: ¬А \/ В.
- Импликация A →B принимает значение 0 (ложь) только если A=1 и B=0. Если A=0, то импликация A →B истинна при любом значении B.
Математика характерно широкое использование символики, которая, до сути, является аппаратом формальной логики. Формальная, или символическая, логика - это специальный метод познания структуры мышления. Такой разработанный аппарат используют везде. В математике многие важные положения удается записывать в виде символов. Запись логических рассуждений в символах придает доказательствам более краткий, простой вид. Формальная логика оперирует высказываниями (из них, кстати, состоит и наша речь). Высказыванием называют предложение, относительно которого имеет смысл утверждать, что оно истинно или ложно. Пример 1.3. „Москва - столица России**, „Петров И.И. - студент МГТУ ", х2+у2 = 1, х € R - высказывания; х2 -2х + + У2 - не является высказыванием. # Соединяя простые высказывания словами „и", „или", „не", „если..., то", мы получаем более сложные высказывания, которые определяют нашу речь. В математике эти слова называют логическими связками, в формальной логике они соответствуют основным логическим символам, на которых мы кратко и остановимся. 1. Конъюнкцией pAq высказываний р и q называют высказывание, которое истинно тогда и только тогда, когда оба высказывания (и р, и q) истинны. Логический симвЪл конъюнкции А заменяет в речи союз „и". Конъюнкцию обозначают также р & q. 2. Дизъюнкцией pW q высказываний р и q называют высказывание, которое ложно в том и только в том случае, когда оба высказывания ложны, а истинно, когда хотя бы одно из них (р или q) истинно. Логический символ дизъюнкции V в речи заменяет слово „или". 3. Импликацией р => q высказываний р и q называют высказывание, которое ложно тогда и только тогда, когда р истинно, a q - ложно. Логический символ импликации => используют при указании на последствия некоторого факта. Он заменяет слова „если..., то". Можно также читать „р влечет qu. 4. Логический символ эквиваленции & означает, что высказывание р q истинно тогда и только тогда, когда оба высказывания р и q истинны или оба высказывания ложны. Этот символ заменяет в речи слово „равносильно". 5. Отрицанием высказывания р называют высказывание -»р, которое истинно, если р ложно, и ложно, когда р истинно. Логический символ -» в речи заменяет слово „не". Для сокращения и уточнения записи высказываний вводят два знака V и 3, называемых соотвеНекоторые основные логические символы. Формальная, или символическая, логика. тственно кванторами общности и существования. Выражение „для всякого элемента х множества Еи записывают в виде Vs 6 Е. Эта запись означает, что утверждение, следующее за ней, будет выполнено для произвольного элемента множества Е. Запись V&i, «2» хп€Е означает: „каковы бы ни были элементы xi, 32, хп множества Еи. Выражение „существует по крайней мере один элемент множества Е, такой, что..." заг писывают Зх £ Е: ... Все, что следует за этой записью, выпол- дается хотя бы для одного элемента множества Е. Наоборот, $х е Е: ... означает, что все следующее далее не выполняется ни для одного элемента из Е. Выражение „ существует один и только один элемент из Е, такой, что...u записывают в виде Э!ж € Е: ... Запись Зх\} хз, хп € Е: ... означает: ясуществуют такие элементы х\у а?2» » я» множества Е, что...ц. Введенными символами удобно пользоваться, например, при определении операций над множествами. Так, AUB:<*{х: (х € А) V (х € В)}, АПВ:*>{х: {х € А) Л (ж € В)}, А\В:*>{х: {х € А) Л (х g В)}, А:<${х: (ж €Й)Л(х£ Л)}, где символ означает эквивалентность по определению. Связь теории множеств и формальной логики достаточно широка. Исследованием этой связи впервые занимался английский математик Джордж Буль (1815-1864), работы которого положили начало одному из важнейших направлений современной алгебры, называемому булевой алгеброй. Ясно, что взятие дополнения тесно связано с отрицанием высказывания, операции объединены и пересечения множеств - с дизъюнкцией и конъюнкцией высказываний соответственно, включение подмножества в множество - с импликацией, а равенство множеств - с эквиваленцией высказываний. В силу этой связи с помощью теории множеств можно решать некоторые логические задачи. Пример 1.4. Рассмотрим набор высказываний: 1) животные, которых не видно в темноте, серы; 2) соседи не любят тех, кто не дает им спать; 3) кто кредко спит, громко храпит; 4) соседи любят животных, которых видно в темноте; 5) все слоны крепко спят; 6) кто громко храпит, не дает спать соседям. Эти высказывания можно перевести на язык теории множеств, если ввести следующие обозначения: А - множество тех, кто будит соседей; В - множество тех, кто крепко спит; С - множество тех, кто громко храпит; D - множество животных, которых видно в темноте; Е - множество слонов; F - множество тех, кого любят соседи; G - множество тех, кто серые. Высказывание 1) означает, что элементы, не лежащие в D) содержатся в G, т.е. 1) D С G. Остальные высказывания принимают вид: 2) Л С F; 3) £ С С; 4) D С F; 5) Е С В; б)ССЛ. Взяв дополнения множеств D и F, из 4) согласно принципу двойственности получим F С D и затем соединим все выскаг зывания в цепочку ECCCACFCDCG. Из этой цепочки (с учетом свойства транзитивности символа включения) следует, что ECGy т.е. все слоны серы. # Рассмотренные логические символы и кванторы существования и общности широко используют математики для записи предложений, в которых они, по сути, воплощают плоды своего творчества. Эти предложения представляют собой устанавливающие свойства математических объектов теоремы, леммы, утверждения и следствия из них, а также различные формулы. Однако следует отметить, что часть предложений приходится все же выражать словами. Любая теорема состоит, вообще говоря, в задании некоторого свойства Л, называемого условием, из которого выводят свойство Ву называемое заключением. Коротко теорему пА влечет Ви записывают в виде А В и говорят, что А является достаточным условием для Б, а Б - необходимым условием для А. Тогда обратная теорема имеет вид В А (возможна запись при помощи обратной импликации А <= В), но справедливость прямой теоремы еще не гарантирует справедливости обратной ей теоремы. Если справедливы данная тедрема и обратная ей, то свойства А я В эквивалентны, и такую теорему можно записать в виде А о В. Эта запись соответствует фразам: „Для того, чтобы Л, необходимо и достаточно, чтобы В", „А тогда и только тогда, когда Ви или „А, если и только если Ви. Ясно, что в этих фразах А и В можно поменять местами. Утверждение, противоположное утверждению А} записывают -^Л, что соответствует словам „не Аи. Если в символьную запись утверждения А входят кванторы 3, V и условие Р, то при построении символьной записи противоположного утверждения -*А квантор 3 заменяют на V, квантор V - на 3, а условие Р заменяют на условие -»Р. Пример 1.6. Рассмотрим утверждение Зх € Е: Р (существует элемент х множества Е, обладающий свойством Р) и построим его отрицание. Если это утверждение неверно, то указанного элемента не существует, т.е. для каждого х € Е свойство Р не выполняется, или -.(За: 6 Е: Р) = Vx € Е: -.Р. Теперь построим отрицание утверждения Vx 6 Е: Р (для каждого элемента х множества Е имеет место свойство Р). Если данное утверждение неверно, то свойство Р имеет место не для каждого элемента указанного множества, т.е. существует хотя бы один элемент х € Е, не обладающий этим свойством, или -.(УхбЕ: Р) = Зх€Я: -чР. # Доказательство предложения представляет собой проводимое по определенным правилам рассуждение, в котором для обоснования сформулированного предложения используют определения, аксиомы и ранее доказанные предложения. Примеры доказательств свойств абсолютных значений действительных чисел приведены доше (см. 1.3), а первого из соотношений свойства дистрибутивности операций объединения и пересечения и первого из законов де Моргана (1.7) - в 1.4. Одним из используемых приемов является метод доказательства от противного. Для доказательства таким методом теоремы А => В предполагают, что верно -«В. Если рассуждения приводят к тому, что при таком предположении условие А невыполнимо, т.е. возникает противоречие, то теорему считают доказанной. Пример 1.6. Используем метод доказательства от противного, чтобы убедиться в справедливости второго закона де Моргана (1.7) AC\B = AUB. Если это равенство верно, то каждый элемент х € А П В должен принадлежать и A U В, т.е. х € A U В. Предположим противное: s £ AUB. Тогда по принципу двойственности (см. 1.4) х € АПВ, т.е. х ^ АПВ, а это противоречит исходному условию х € А П В, что доказывает справедливость импликации высказываний х€ АГ\В=>хе лив. Наоборот, каждый элемент х 6 A U В должен принадлежать и Л Г) В, т.е. х € А О В. Снова предположим противное: х £ i АП В, т.е. х £ АП В, или (хбА)Л(хбВ). Тогда (х£А)Л Л (х £ В) и х £ AUB, а это опять противоречит принятому условию х £ A U В, что доказывает справедливость обратной импликации высказываний х€ АПВ«=х€ AUB. Некоторые основные логические символы. Формальная, или символическая, логика. В итоге справедливость второй формулы (1.7) доказана полностью. # При доказательстве предложений, справедливых для произвольного натурального числа п G N, иногда применяют метод математической индукции: непосредственной проверкой устанавливают справедливость предложения для нескольких первых значений п (n= 1, 2, ...), а затем предполагают, что оно верно для п = к} и если из этого предположения следует справедливость данного предложения для п = к -f 1, то его считают доказанным для всех п € N. Пример 1.7. Докажем справедливость формулы «П = «1 (1.8) для суммы первых п членов геометрической прогрессии 0|, a2 = aitf, a3 = alq2) an = aign_1 со знаменателем прогрессии q ^ 1. Ясно, что формула верна для п= 1 и п = 2. Предположим, что она верна и для п = к, т.е. Некоторые основные логические символы. Формальная, или символическая, логика. Если в (1.9) обозначить к +1 = п, то снова придем к (1.8), что доказывает справедливость этой формулы.
Именно она используется для вычисления логических операций. Рассмотрим ниже все самые элементарные логические операции в информатике. Ведь если задуматься, именно они используются при создании логики вычислительных машин и приборов.
Отрицание
Перед тем как начать подробно рассматривать конкретные примеры, перечислим основные логические операции в информатике:
- отрицание;
- сложение;
- умножение;
- следование;
- равенство.
Также перед началом изучения логических операций стоит сказать, что в информатике ложь обозначается "0", а правда "1".
Для каждого действия, как и в обычной математике, используются следующие знаки логических операций в информатике: ¬, v, &, ->.
Каждое действие возможно описать либо цифрами 1/0, либо просто логическими выражениями. Начнём рассмотрение математической логики с простейшей операции, использующей всего одну переменную.
Логическое отрицание - операция инверсии. Суть заключается в том, что если исходное выражение - истина, то результат инверсии - ложь. И наоборот, если исходное выражение - ложь, то результатом инверсии станет - правда.
При записи этого выражения используется следующее обозначение "¬A".
Приведём таблицу истинности - схему, которая показывает все возможные результаты операции при любых исходных данных.
То есть, если у нас исходное выражение - истина (1), то его отрицание будет ложным (0). А если исходное выражение - ложь (0), то его отрицание - истина (1).
Сложение
Оставшиеся операции требуют наличия двух переменных. Обозначим одно выражение -
А, второе - В. Логические операции в информатике, обозначающие действие сложения (или дизъюнкция), при написании обозначаются либо словом "или", либо значком "v". Распишем возможные варианты данных и результаты вычислений.
- Е=1, Н=1 ,тогда Е v Н = 1. Если оба тогда и их дизъюнкция также истинна.
- Е=0, Н=1 ,в итоге Е v Н = 1. Е=1, Н=0 , тогда Е v Н= 1. Если хотябы одно из выражений истинно, тогда и результат их сложения будет истиной.
- Е=0, Н=0 ,результат Е v Н = 0. Если оба выражения ложны, то их сумма также - ложь.
Для краткости создадим таблицу истинности.
| Е | х | х | о | о |
| Н | х | о | х | о |
| Е v Н | х | х | х | о |
Умножение
Разобравшись с операцией сложения, переходим к умножению (конъюнкции). Воспользуемся теми же обозначениями, которые были приведены выше для сложения. При письме логическое умножение обозначается значком "&", либо буквой "И".
- Е=1, Н=1 ,тогда Е & Н = 1. Если оба тогда их конъюнкция - истина.
- Если хотя бы одно из выражений - ложь, тогда результатом логического умножения также будет ложь.
- Е=1, Н=0, поэтому Е & Н = 0.
- Е=0, Н=1, тогда Е & Н = 0.
- Е=0, Н=0, итог Е & Н = 0.
| Е | х | х | 0 | 0 |
| Н | х | 0 | х | 0 |
| Е & Н | х | 0 | 0 | 0 |
Следствие
Логическая операция следования (импликация) - одна из простейших в математической логике. Она основана на единственной аксиоме - из правды не может следовать ложь.
- Е=1, Н=, поэтому Е -> Н = 1. Если пара влюблена, то они могут целоваться - правда.
- Е=0, Н=1, тогда Е -> Н = 1. Если пара не влюблена, то они могут целоваться - также может быть истиной.
- Е=0, Н=0, из этого Е -> Н = 1. Если пара не влюблена, то они и не целуются - тоже правда.
- Е=1, Н=0, результатом будет Е -> Н = 0. Если пара влюблена, то они не целуются - ложь.
Для облегчения выполнения математических действий также приведём таблицу истинности.
Равенство
Последней рассмотренной операцией станет логическое тождественное равенство или эквивалентность. В тексте оно может обозначаться как "...тогда и только тогда, когда...". Исходя из этой формулировки, напишем примеры для всех исходных вариантов.
- А=1, В=1, тогда А≡В = 1. Человек пьёт таблетки тогда и только тогда, когда болеет. (истина)
- А=0, В=0, в итоге А≡В = 1. Человек не пьёт таблетки тогда и только тогда, когда не болеет. (истина)
- А=1, В=0, поэтому А≡В = 0. Человек пьёт таблетки тогда и только тогда, когда не болеет. (ложь)
- А=0, В=1 ,тогда А≡В = 0. Человек не пьёт таблетки тогда и только тогда, когда болеет. (ложь)
Свойства
Итак, рассмотрев простейшие в информатике, можем приступить к изучению некоторых их свойств. Как и в математике, у логических операций существует свой порядок обработки. В больших логических выражениях операции в скобках выполняются в первую очередь. После них первым делом подсчитываем все значения отрицания в примере. Следующим шагом станет вычисление конъюнкции, а затем дизъюнкции. Только после этого выполняем операцию следствия и, наконец, эквивалентности. Рассмотрим небольшой пример для наглядности.
А v В & ¬В -> В ≡ А
Порядок выполнения действий следующий.
- В&(¬В)
- А v(В&(¬В))
- (А v(В&(¬В)))->В
- ((А v(В&(¬В)))->В)≡А
Для того чтобы решить этот пример, нам потребуется построить расширенную таблицу истинности. При её создании помните, что столбцы лучше располагать в том же порядке, в каком и будут выполняться действия.
| А | В | (А v(В&(¬В)))->В | ((А v(В&(¬В)))->В)≡А |
|||
| х | о | х | о | х | х | х |
| х | х | о | о | х | х | х |
| о | о | х | о | о | х | о |
| о | х | о | о | о | х | о |
Как мы видим, результатом решения примера станет последний столбец. Таблица истинности помогла решить задачу с любыми возможными исходными данными.
Заключение
В этой статье были рассмотрены некоторые понятия математической логики, такие как информатика, свойства логических операций, а также - что такое логические операции сами по себе. Были приведены некоторые простейшие примеры для решения задач по математической логике и таблицы истинности, необходимые для упрощения этого процесса.
Конъюнкция или логическое умножение (в теории множеств – это пересечение)
Конъюнкция является сложным логическим выражением, которое истинно в том и только том случае, когда оба простых выражения являются истинными. Такая ситуация возможно лишь в единственном случае, во всех остальных случаях конъюнкция ложна.
Обозначение: &, $\wedge$, $\cdot$.
Таблица истинности для конъюнкции
Рисунок 1.
Свойства конъюнкции:
- Если хотя бы одно из подвыражений конъюнкции ложно на некотором наборе значений переменных, то и вся конъюнкция будет ложной для этого набора значений.
- Если все выражения конъюнкции истинны на некотором наборе значений переменных, то и вся конъюнкция тоже будет истинна.
- Значение всей конъюнкции сложного выражения не зависит от порядка записи подвыражений, к которым она применяется (как в математике умножение).
Дизъюнкция или логическое сложение (в теории множеств это объединение)
Дизъюнкция является сложным логическим выражением, которое истинно практически всегда, за исключением, когда все выражения ложны.
Обозначение: +, $\vee$.
Таблица истинности для дизъюнкции
Рисунок 2.
Свойства дизъюнкции:
- Если хотя бы одно из подвыражений дизъюнкции истинно на некотором наборе значений переменных, то и вся дизъюнкция принимает истинное значение для данного набора подвыражений.
- Если все выражения из некоторого списка дизъюнкции ложны на некотором наборе значений переменных, то и вся дизъюнкция этих выражений тоже ложна.
- Значение всей дизъюнкции не зависит от порядка записи подвыражений (как в математике – сложение).
Отрицание, логическое отрицание или инверсия (в теории множеств это отрицание)
Отрицание - означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО и в итоге получаем, что если исходное выражение истинно, то отрицание исходного – будет ложно и наоборот, если исходное выражение ложно, то его отрицание будет истинно.
Обозначения: не $A$, $\bar{A}$, $¬A$.
Таблица истинности для инверсии
Рисунок 3.
Свойства отрицания:
«Двойное отрицание» $¬¬A$ является следствием суждения $A$, то есть имеет место тавтология в формальной логике и равно самому значению в булевой логике.
Импликация или логическое следование
Импликация - это сложное логическое выражение, которое истинно во всех случаях, кроме как из истины следует ложь. То есть, данная логическая операция связывает два простых логических выражения, из которых первое является условием ($A$), а второе ($A$) является следствием условия ($A$).
Обозначения: $\to$, $\Rightarrow$.
Таблица истинности для импликации
Рисунок 4.
Свойства импликации:
- $A \to B = ¬A \vee B$.
- Импликация $A \to B$ ложна, если $A=1$ и $B=0$.
- Если $A=0$, то импликация $A \to B$ истинна при любом значении $B$, (из лжи может следовать истинна).
Эквивалентность или логическая равнозначность
Эквивалентность - это сложное логическое выражение, которое истинно на равных значениях переменных $A$ и $B$.
Обозначения: $\leftrightarrow$, $\Leftrightarrow$, $\equiv$.
Таблица истинности для эквивалентности
Рисунок 5.
Свойства эквивалентности:
- Эквивалентность истинна на равных наборах значений переменных $A$ и $B$.
- КНФ $A \equiv B = (\bar{A} \vee B) \cdot (A \cdot \bar{B})$
- ДНФ $A \equiv B = \bar{A} \cdot \bar{B} \vee A \cdot B$
Строгая дизъюнкция или сложение по модулю 2 (в теории множеств это объединение двух множеств без их пересечения)
Строгая дизъюнкция истинна, если значения аргументов не равны.
Для электроники это означает, что реализация схем возможна с использованием одного типового элемента (правда это дорогостоящий элемент).
Порядок выполнения логических операций в сложном логическом выражении
- Инверсия(отрицание);
- Конъюнкция (логическое умножение);
- Дизъюнкция и строгая дизъюнкция (логическое сложение);
- Импликация (следствие);
- Эквивалентность (тождество).
Для того чтобы изменить указанный порядок выполнения логических операций, необходимо использовать скобки.
Общие свойства
Для набора из $n$ логических переменных существует ровно $2^n$ различных значений. Таблица истинности для логического выражения от $n$ переменных содержит $n+1$ столбец и $2^n$ строк.
⊃ может означать то же самое, что и ⇒ (символ может также обозначать надмножество).
⇒
{\displaystyle \Rightarrow }
→
{\displaystyle \to }
\to
⊃
{\displaystyle \supset }
⟹
{\displaystyle \implies }
\implies
U+003A U+229C
:
:=
{\displaystyle:=}
:=
≡
{\displaystyle \equiv }
⇔
{\displaystyle \Leftrightarrow }
- U+2310 ⌐ Отменённый НЕ
Следующие операторы редко поддерживаются стандартными фонтами. Если вы хотите использовать их на своей странице, вам следует всегда встраивать нужные фонты, чтобы браузер мог отражать символы без необходимости устанавливать фонты на компьютер.
Польша и Германия
В Польше квантор всеобщности иногда записывается как ∧ {\displaystyle \wedge } , а квантор существования как ∨ {\displaystyle \vee } . То же самое наблюдается в немецкой литературе.