Математическая логика (ЧАСТЬ 1)
Что такое логический вывод?
Пусть дано два утверждения:
1. Фрукты могут расти на деревьях.
2. Яблоко это фрукт.
Так как оба эти утверждения истинны, то можно сказать, что утверждение «Яблоки могут расти на деревьях» также истинно. Это третье утверждение никак не содержится в двух первых, оно из них следует. Или, иначе говоря, третье утверждение является логическим выводом из первых двух.
Это был простой пример. Сейчас рассмотрим пример посложнее. Попробуем решить задачу из книги профессора Р.М. Смаллиана, «Принцесса или тигр».
Условие. В этой задаче необходимо выяснить: в какой из двух комнат находится принцесса, а в какой тигр. На дверях каждой из комнат есть таблички с некоторыми утверждениями, кроме того, дополнительно известно, что на одной табличке написана правда, а на другой нет, но на какой правда, а на какой ложь не известно. И ещё известно, что в каждой комнате кто-то есть.
| 1. В этой комнате находится принцесса, а в другой комнате сидит тигр. | 2. В одной из этих комнат находится принцесса; кроме того, в одной из этих комнат сидит тигр. |
Решение. Утверждения на табличках не могут быть одновременно истинными или ложными. Следовательно, возможны только две ситуации. Первая: первое истинно, а второе ложно и вторая: первое ложно, а второе истинно. Рассмотрим их.
Ситуация 1. Из истинности первого утверждения следует, что принцесса находится в первой комнате, а тигр во второй. В это же время из ложности второго утверждения следует, что нет комнаты, в которой находится принцесса и нет комнаты в которой сидит тигр. Следовательно, истинность первого утверждения и ложность второго невозможны одновременно.
Ситуация 2. Из истинности второго утверждения следует только то, что и тигр и принцесса имеются в наличии. Из ложности же первого следует, что принцесса находится во второй комнате, а тигр в первой. Анализируя вторую ситуацию, мы не получили противоречия, следовательно ситуация 2 и есть решение задачи.
Решение данной задачи есть пример более сложного рассуждения. Однако нетрудно заметить общий принцип. В этом рассуждении, так же как и в первом примере есть элементарные утверждения из истинности, которых следует истинность или ложность других утверждений. А цель логического вывода как раз и заключается в установлении истинности или ложности различных утверждений.
Логический вывод опирается на вроде бы очевидное утверждение, что при истинных исходных утверждениях и правильном логическом выводе, утверждение которое получается в результате такого вывода также истинно.
Остается выяснить, что такое правильный логический вывод. А это уже очень сложный вопрос. Чтобы на него ответить и нужна целая наука, называемая математической логикой. А сейчас нам нужно несколько определений.
Понятие высказывания
У всех утверждений, которые мы использовали выше в качестве примеров, есть одно общее свойство. Независимо от их смысла они могут быть либо истинными, либо ложными. Утверждения, обладающие таким свойством, называются высказываниями. Не всякое утверждение может быть высказыванием. К примеру, следующее утверждение: «Малахит самый красивый камень из всех известных самоцветов» высказыванием быть не может, так как это вопрос вкуса.
Бывают утверждения истинность или ложность, которых в принципе проверить можно, но только в принципе, реально же это невозможно. Например, невозможно проверить истинность следующего утверждения: «На планете Земля в настоящее время есть одно и только одно дерево, на котором растет ровно 10000 листьев». Теоретически это проверить можно, но только теоретически, так как для такой проверки придётся использовать слишком большое количество проверяющих, значительно большее чем проживает на планете людей.
Таким образом, математическая логика изучает только высказывания, и только то, как определять их истинность или ложность. Математическая логика не исследует смысл высказываний, из чего следует, что формулировка высказывания роли не играет и для высказывания достаточно ввести простое обозначение.
Собственно так и происходит. Высказывания обозначают просто буквами: А, В, С и т.д. и говорят о них только то, что они истинны или ложны.
Сложные высказывания. Логические операции
Ранее, мы говорили только о простых высказываниях, высказывания же могут быть и сложными состоящими из нескольких простых. Приведем пример:
Помидор может быть красным и помидор может быть круглым.
Это высказывание состоит из двух простых: «Помидор может быть красным», «Помидор может быть круглым» соединённых логической связкой «И». Объединение двух и более простых высказываний логической связкой «И» называется логической операцией конъюнкции. Результатом конъюнкции является сложное высказывание, истинность которого зависит от истинности входящих в него простых высказываний и определяется следующим правилом: Конъюнкция является истинной тогда и только тогда, когда истинны все входящие в неё высказывания.
В математической логике есть общепринятое обозначение конъюнкции – Ù. Если в конъюнкции участвуют два простых высказывания A и B, то это записывается так A Ù B.
Правило истинности для конъюнкции можно представить в виде следующей таблицы:
| A | B | A and B |
Истинность в этой таблице записывается единицей, а ложность нулем. Если A имеет значение 0 и B имеет значение 1, то конъюнкция будет такая: 0 and 1 = 0, то есть ложь.
Конечно, конъюнкция не единственная логическая операция позволяющая строить из простых высказываний сложные. Дадим определение ещё нескольких:
Дизъюнкция. Сложное высказывание являющееся дизъюнкцией двух простых истинно, если истинно хотя бы одно простое высказывание, входящее в дизъюнкцию. Обозначается дизъюнкция следующим образом:
A Ú B. Её таблица истинности:
Эквиваленция. Сложное высказывание, построенное с помощью операции эквиваленции истинно в том случае, когда оба входящие в него высказывания одновременно истинны или одновременно ложны. Обозначается эквиваленция так: A ~ B. Таблица истинности приведена ниже.
С помощью логических операций можно строить логические выражения любой степени сложности, истинность которых также можно определять с помощью таблицы истинности. Возьмём в качестве примера следующее выражение: (A Ù B) ® (A Ú B) и построим для него таблицу истинности:
Из таблицы истинности данного выражения видно, что оно принимает истинное значение при любых значениях простых высказываний A и B. Такие выражения называются тождественно истинными. Выражения, принимающие всегда значение ложь, называются тождественно ложными.
Проверка истинности с помощью таблиц истинности не всегда проста. Логические выражения могут включать в себя много операций, количество элементарных высказываний, обозначаемых буквами, также может быть велико, а при достаточно большом количестве элементарных высказываний, таблица истинности может быть настолько велика, что построить её окажется просто невозможным.
Из таблиц приведённых выше видно, что, для их построения необходимо перебрать все возможные комбинации истинности и ложности элементарных высказываний. Для двух высказываний возможны четыре комбинации. Для трех, количество комбинаций равно 8. Для N высказываний количество комбинаций равно числу 2 N . То есть, например для N=10 2 N = 2 10 = 1024. Это уже слишком много.
В таких ситуациях уже нужны специальные приёмы для выяснения истинности и ложности выражения. Эти приёмы заключаются в упрощении исходного выражения, приведения его к стандартному, более простому виду. Под более простым видом, обычно понимается более короткое выражение, однако сократить логическое выражение может не получиться. Однако всегда можно уменьшить количество логических операций и всегда можно упростить форму логического выражения.
Существуют две стандартные формы, к которым можно привести любое логическое выражение.
Дизъюнктивная нормальная форма. Это логическое выражение представляющее собой дизъюнкцию элементарных конъюнкций, в которые входят элементарные высказывания или их отрицания.
Пример
(AÙBÙC)Ú(AÙùBÙùC)Ú(AÙBÙùC)
Конъюнктивная нормальная форма. Это логическое выражение представляющее собой конъюнкцию элементарных дизъюнкций, в которые входят элементарные высказывания или их отрицания.
(AÚùBÚC) Ù(AÚùBÚC)Ù (AÚBÚùC)
Истинность выражения представленного в нормальной форме проверяется значительно проще. Дизъюнктивная нормальная форма истинна если истинна хотя бы одна элементарная конъюнкция. Конъюнктивная нормальная форма ложна если ложна хотя бы одна элементарная дизъюнкция. Элементарная дизъюнкция истинна, если истинно хотя бы одно элементарное высказывание в неё входящее. Элементарная конъюнкция ложна, если ложно хотя бы одно элементарное высказывание в неё входящее (Отрицание высказывания элементарным не является).
Для того чтобы привести логическое выражение к одной из указанных выше форм применятся правила подстановки, переводящие логическое выражение в равнозначное (то есть имеющее точно такую же таблицу истинности). Ниже приведен список таких правил.
©2015-2019 сайт
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-11
Под высказыванием понимается языковое выражение, о котором можно сказать только одно из двух: истинно оно или ложно. Высказывание, в отличие от суждений, не имеет личностного характера.
Вопросы, просьбы, приказы, восклицания, отдельные слова (кроме случаев, когда они выступают представителями высказываний типа «вечереет», «похолодало» и т. п.) не являются высказываниями. Истинность и ложность высказываний являются их логическими значениями.
Высказывания делятся на атрибутивные, экзистенциальные и реляционные.
Атрибутивными называются высказывания, в которых утверждается или отрицается свойство или состояние предмета.
Экзистенциальными называются высказывания, которые утверждают или отрицают факт существования.
Реляционными называются высказывания, выражающие отношения между предметами.
Высказывания, как и их логические формы, бывают простыми и сложными. Сложное высказывание можно разбить на простые. Простые высказывания на более простые не расчленяются.
Простое атрибутивное высказывание имеет структуру, в которую входят субъект, предикат и связка.
Субъект высказывания (S) - это та часть высказывания, которая выражает предмет мысли.
Предикат высказывания (Р) - это часть высказывания, в которой отображается признак предмета мысли, его свойство, состояние, отношение.
Субъект (S) и предикат (Р) называются терминами. Связка указывает на то, в каком взаимоотношении находятся между собой термины (S и Р).
В атрибутивных высказываниях часто используются кванторы существования и общности.
Атрибутивные высказывания делятся по качеству и количеству.
По качеству они делятся на утвердительные и отрицательные. В утвердительных указывается на принадлежность (наличие) признака, мыслимого в предикате, субъекту высказывания: «S есть Р». Например: «Платон - философ-идеалист». В отрицательных указывается на непринадлежность предиката его субъекту: «S не есть Р».
По количеству высказывания делятся на единичные, частные и общие. Имеется в виду совокупность (число, количество) индивидуальных предметов, составляющих имя класса субъекта.
В единичных высказываниях субъект состоит из одного предмета.
Частные высказывания имеют форму: «Некоторые S есть (не есть) Р».
В общих высказываниях субъект охватывает все предметы. Такие высказывания имеют форму: «Все S есть (не есть) Р».
Высказывания классифицируются по качеству и количеству. Выделяются 4 класса высказываний:
1) общеутвердительное (А) - общее по количеству и утвердительное по качеству («Все S есть Р»);
2) частноутвердительное (J) - частное по количеству и утвердительное по качеству («Некоторые S есть Р»);
3) общеотрицательное (Е) - общее по количеству и отрицательное по качеству («Ни одно S не есть Р»);
4) частноотрицательное (О) - частное по количеству и отрицательное по качеству («Некоторые S не есть Р»).
В каждом классе высказываний соотношение объемов S и Р (терминов) различно. В логике проблема соотношения объемов S и Р называется проблемой распределенности терминов. Термин распределен, если он полностью входит в объем другого термина или полностью из него исключается.
В классе А |Все S есть Р| субъект полностью распределен в предикате, а предикат не распределен.
Высказывание - более сложное образование, чем имя. При разложении высказываний на более простые части мы всегда получаем те или иные имена. Скажем, высказывание «Солнце есть звезда» включает в качестве своих частей имена «Солнце» и «звезда».
Высказывание - грамматически правильное предложение, взятое вместе с выражаемым им смыслом (содержанием) и являющееся истинным или ложным.
Понятие высказывания - одно из исходных, ключевых понятий современной логики. Как таковое оно не допускает точного определения, в равной мере приложимого в разных ее разделах.
Высказывание считается истинным, если даваемое им описание соответствует реальной ситуации, и ложным, если не соответствует ей. «Истина» и «ложь» называются «истинностными значениями высказываний».
Из отдельных высказываний разными способами можно строить новые высказывания. Например, из высказываний «Дует ветер» и «Идет дождь» можно образовать более сложные высказывания «Дует ветер и идет дождь», «Либо дует ветер, либо идет дождь», «Если идет дождь, то дует ветер» и т.п.
Высказывание называется простым, если оно не включает других высказываний в качестве своих частей.
Высказывание называется сложным, если оно получено с помощью логических связок из других более простых высказываний.
Рассмотрим наиболее важные способы построения сложных высказываний.
Отрицательное высказывание состоит из исходного высказывания и отрицания, выражаемого обычно словами «не», «неверно, что». Отрицательное высказывание является, таким образом, сложным высказыванием: оно включает в качестве своей части отличное от него высказывание. Например, отрицанием высказывания «10 - четное число» является высказывание «10 не есть четное число» (или: «Неверно, что 10 есть четное число»).
Обозначим высказывания буквами А, В, С, ... Полный смысл понятия отрицания высказывания задается условием: если высказывание А истинно, его отрицание ложно, и если А ложно, его отрицание истинно. Например, так как высказывание «1 есть целое положительное число» - истинно, его отрицание «1 не является целым положительным числом» - ложно, а так как «1 есть простое число» - ложно, его отрицание «1 не есть простое число» - истинно.
Соединение двух высказываний при помощи слова «и» дает сложное высказывание, называемоеконъюнкцией. Высказывания, соединяемые таким образом, называются «членами конъюнкции».
Например, если высказывания «Сегодня жарко» и «Вчера было холодно» соединить таким способом, получится конъюнкция «Сегодня жарко и вчера было холодно».
Конъюнкция истинна только в случае, когда оба входящих в нее высказывания являются истинными; если хотя бы один из ее членов ложен, то и вся конъюнкция ложна.
В обычном языке два высказывания соединяются союзом «и», когда они связаны между собой по содержанию или смыслу. Характер этой связи не вполне ясен, но понятно, что мы не рассматривали бы конъюнкцию «Он шел в пальто, и я шел в университет» как выражение, имеющее смысл и способное быть истинным или ложным. Хотя высказывания «2 - простое число» и «Москва - большой город» истинны, мы не склонны считать истинной также их конъюнкцию «2 - простое число и Москва - большой город», поскольку составляющие се высказывания не связаны между собой по смыслу. Упрощая значение конъюнкции и других логических связок и отказываясь для этого от неясного понятия «связь высказываний по смыслу», логика делает значение этих связок одновременно и более широким, и более определенным.
Соединение двух высказываний с помощью слова «или» дает дизъюнкцию этих высказываний. Высказывания, образующие дизъюнкцию, называются «членами дизъюнкции».
Слово «или» в повседневном языке имеет два разных смысла. Иногда оно означает «одно или другое или оба», а иногда «одно или другое, но не оба вместе». Например, высказывание «В этом сезоне я хочу пойти на «Пиковую даму» или на «Аиду» допускает возможность двукратного посещения онеры. В высказывании же «Он учится в Московском или в Ярославском университете» подразумевается, что упоминаемый человек учится только в одном из этих университетов.
Первый смысл «или» называется неисключающим. Взятая в этом смысле дизъюнкция двух высказываний означает, что, по крайней мере, одно из этих высказываний истинно, независимо от того, истинны они оба или пет. Взятая во втором, исключающему или строгом, смысле дизъюнкция двух высказываний утверждает, что одно из высказываний истинно, а второе - ложно.
Неисключающая дизъюнкция истинна, когда хотя бы одно из входящих в нее высказываний истинно, и ложна, только когда оба ее члена ложны.
Исключающая дизъюнкция истинна, когда истинным является только один из ее членов, и она ложна, когда оба ее члена истинны или оба ложны.
В логике и математике слово «или» почти всегда употреб***яется в неисключающем значении.
Условное высказывание - сложное высказывание, формулируемое обычно с помощью связки «если..., то...» и устанавливающее, что одно событие, состояние и т.п. является в том или ином смысле основанием или условием для другого.
Например: «Если есть огонь, то есть дым», «Если число делится на 9, оно делится на 3» и т.п.
Условное высказывание слагается из двух более простых высказываний. То из них, которому предпослано слово «если», называется основанием, или антецедентом (предыдущим), высказывание, идущее после слова «то», называется следствием, или консеквентом (последующим).
Утверждая условное высказывание, мы прежде всего имеем в виду, что не может быть так, чтобы то, о чем говорится в его основании, имело место, а то, о чем говорится в следствии, отсутствовало. Иными словами, не может случиться, чтобы антецедент был истинным, а консеквент - ложным.
В терминах условного высказывания обычно определяются понятия достаточного и необходимого условия: антецедент (основание) есть достаточное условие для консеквента (следствия), а консеквент - необходимое условие для антецедента. Например, истинность условного высказывания «Если выбор рационален, то выбирается лучшая из имеющихся альтернатив» означает, что рациональность - достаточное основание для избрания лучшей из имеющихся возможностей и что выбор такой возможности есть необходимое условие его рациональности.
Типичной функцией условного высказывания является обоснование одного высказывания ссылкой на другое высказывание. Например, то, что серебро электропроводно, можно обосновать ссылкой на то, что оно металл: «Если серебро - металл, оно электропроводно».
Выражаемую условным высказыванием связь обосновывающего и обосновываемого (основания и следствия) трудно охарактеризовать в общем виде, и только иногда природа се относительно ясна. Эта связь может быть, во-первых, связью логического следования, имеющей место между посылками и заключением правильного умозаключения («Если все живые многоклеточные существа смертны, а медуза является таким существом, то она смертна»); во-вторых, законом природы («Если тело подвергнуть трению, оно начнет нагреваться»); в-третьих, причинной связью («Если Луна в новолуние находится в узле своей орбиты, наступает солнечное затмение»); в-четвертых, социальной закономерностью, правилом, традицией и т.п. («Если меняется общество, меняется и человек», «Если совет разумен, он должен быть выполнен»).
Со связью, выражаемой условным высказыванием, обычно соединяется убеждение, что следствие с определенной необходимостью «вытекает» из основания и что имеется некоторый общий закон, сумев сформулировать который, мы могли бы логически вывести следствие из основания.
Например, условное высказывание «Если висмут - металлом пластичен» как бы предполагает общий закон "Нес металлы пластичны», делающий консеквент данного высказывания логическим следствием его антецедента.
И в обычном языке, и в языке науки условное высказывание кроме функции обоснования может выполнять также ряд других задач: формулировать условие, не связанное с каким-либо подразумеваемым общим законом или правилом («Если захочу, разрежу свой плащ»); фиксировать какую-либо последовательность («Если прошлое лето было сухим, то в этом году оно дождливое»); выражать в своеобразной форме неверие («Если вы решите эту задачу, я докажу великую теорему Ферма»); противопоставление («Если в огороде растет бузина, то в Киеве живет дядька») и т.п. Многочисленность и разнородность функций условного высказывания существенно затрудняет его анализ.
Употребление условного высказывания связано с определенными психологическими факторами. Так, обычно мы формулируем такое высказывание, только если не знаем с определенностью, истинны или нет его антецедент и консеквент. В противном случае его употребление кажется неестественным («Если вата - металл, она электропровод на»).
Условное высказывание находит очень широкое применение во всех сферах рассуждения. В логике оно представляется, как правило, посредством импликативного высказывания, или импликации. При этом логика проясняет, систематизирует и упрощает употребление «если..., то...», освобождает его от влияния психологических факторов.
Логика отвлекается, в частности, от того, что характерная для условного высказывания связь основания и следствия в зависимости от контекста может выражаться с помощью нс только «если..., то...», но и других языковых средств. Например, «Так как вода жидкость, она передает давление во все стороны равномерно», «Хотя пластилин и не металл, он пластичен», «Если бы дерево было металлом, оно было бы электропроводным» и т.п. Эти и подобные им высказывания представляются в языке логики посредством импликации, хотя употребление в них «если..., то...» было бы не совсем естественным.
Утверждая импликацию, мы утверждаем, что не может случиться, чтобы ее основание имело место, а следствие - отсутствовало. Иными словами, импликация является ложной только в том случае, когда се основание истинно, а следствие ложно.
Это определение предполагает, как и предыдущие определения связок, что всякое высказывание является либо истинным, либо ложным и что истинностное значение сложного высказывания зависит только от истинностных значений составляющих его высказываний и от способа их связи.
Импликация истинна, когда и ее основание, и ее следствие истинны или ложны; она истинна, если ее основание ложно, а следствие истинно. Только в четвертом случае, когда основание истинно, а следствие ложно, импликация ложна.
Импликацией не предполагается, что высказывания А и В как-то связаны между собой по содержанию. В случае истинности В высказывание «если А, то В» истинно независимо от того, являетсяА истинным или ложным и связано оно по смыслу с В или нет.
Например, истинным считаются высказывания: «Если на Солнце есть жизнь, то дважды два равно четыре», «Если Волга - озеро, то Токио - большая деревня» и т.п. Условное высказывание истинно также тогда, когда А ложно, и при этом опять-таки безразлично, истинно В или нет и связано оно по содержанию с А или нет. К истинным относятся высказывания: «Если Солнце - куб, то Земля - треугольник», «Если дважды два равно пять, то Токио - маленький город» и т.п.
В обычном рассуждении все эти высказывания вряд ли будут рассматриваться как имеющие смысл и еще в меньшей степени как истинные.
Хотя импликация полезна для многих целей, она не совсем согласуется с обычным пониманием условной связи. Импликация охватывает многие важные черты логического поведения условного высказывания, но она не является вместе с тем достаточно адекватным его описанием.
В последние полвека были предприняты энергичные попытки реформировать теорию импликации. При этом речь шла не об отказе от описанного понятия импликации, а о введении наряду с ним другого понятия, учитывающего не только истинностные значения высказываний, но и связь их по содержанию.
С импликацией тесно связана эквивалентность, называемая иногда «двойной импликацией».
Эквивалентность - сложное высказывание «Л, если и только если В», образованное из высказываний Ли В и разлагающееся на две импликации: «если А, то В», и «если В, то А». Например: «Треугольник является равносторонним, если и только если он является равноугольным». Термином «эквивалентность» обозначается и связка «..., если и только если...», с помощью которой из двух высказываний образуется данное сложное высказывание. Вместо «если и только если» для этой цели могут использоваться «в том и только в том случае, когда», «тогда и только тогда, когда» и т.п.
Если логические связки определяются в терминах истины и лжи, эквивалентность истинна тогда и только тогда, когда оба составляющих ее высказывания имеют одно и то же истинностное значение, т.е. когда они оба истинны или оба ложны. Соответственно эквивалентность является ложной, когда одно из входящих в нее высказываний истинно, а другое ложно.
2.1. Составные высказывания
Из элементарных высказываний можно строить более сложные (составные ) высказывания, используя связки И, ИЛИ, НЕ.
Примеры. Забор красный И забор деревянный.
Коля старше, чем Петя ИЛИ Коля старше, чем Федя
Забор НЕ красный.
Смысл этих высказываний понятен.
Высказывание с И содержит два элементарных высказывания. Составное высказывание с И истинно тогда и только тогда, когда истинны оба эти элементарные высказывания. Если хоть одно из них ложно, - составное высказывание ложно.
Высказывание с ИЛИ тоже содержит два элементарных высказывания. Составное высказывание с ИЛИ истинно тогда и только тогда, когда истинно хотя бы одно из этих элементарных высказываний. Если оба эти высказывания ложны, - составное высказывание ложно.
Высказывание с НЕ содержит одно элементарное высказывание (в русском языке НЕ часто ставится в середину этого высказывания). Составное высказывание с НЕ истинно, если исходное элементарное высказывание ложно и, наоборот, если исходное высказывание истинно, то составное высказывание с НЕ ложно.
Составные высказывания можно строить не только из элементарных высказываний, но и из других составных высказываний. В этом построение составных высказываний похоже на построение алгебраических выражений. Например, понятно, что означает такое высказывание (хотя оно написано не на русском языке, а с использованием скобок:)
(Коля старше, чем Петя ИЛИ Коля старше, чем Федя) И (Коля НЕ старше, чем Ваня)
Здесь 3 элементарных высказывания.
2.2. Логические значения. Логические операции.
Мы уже знаем, что каждому высказыванию можно приписать одно из двух логических значений – истина (часто обозначается: 1 ) или ложь (часто обозначается: 0 ). Слова И, ИЛИ, НЕ задают операции над логическими значениями (логические операции ). Действительно, например, составное высказывание с И истинно тогда и только тогда, когда истинны оба его элементарные высказывания. Если хоть одно из них ложно, - составное высказывание ложно. Здесь нам не важно, каковы были исходные высказывания. Истинность составного высказывания зависит только от логического (иногда говорят - истинностного ) значения исходных высказываний.
Так как логических значений всего два, то эти операции можно описать таблицами.
У операций И, ИЛИ, НЕ есть «научные» названия (даже несколько для каждой операции 🙂 и специальные обозначения (в примерах A, B обозначают какие-то конкретные логические значения):
НЕ: отрицание, инверсия. Обозначение: ¬ (например, ¬А);
И: конъюнкция, логическое умножение.
Обозначается /\ (например, А /\ В) либо & (например, А & В);
ИЛИ: дизъюнкция, логическое сложение .
Обозначается \/ (например, А \/ В).
В математике используются и другие логические операции.
Каждая логическая операция может быть задана своей таблицей. Вот еще два примера логических операций:
1) следование (импликация) ; обозначается → (например, А → В); см. таб. 4. Выражение А → В истинно если A ложно ИЛИ B истинно. То есть, А → В означает то же самое, что и (¬А) \/ В.
2) тождество (эквивалетность); обозначается ≡ (например, A ≡ B); см. таб 5. Выражение A ≡ B истинно тогда и только тогда, когда значения A и B совпадают (либо они оба истинны, либо они оба ложны).
2.3. Логические выражения. Таблицы истинности.
Логические операции играют для логических значений ту же роль, что и арифметические операции для чисел. Аналогично построению алгебраических выражений, с помощью логических операций можно строить логические выражения. Как и алгебраические выражения, логические выражения могут включать константы (логические значений 1 и 0) и переменные. Если в логическом значении есть переменные, оно задает функцию (логическую функцию; синоним: булеву функцию). Значение такой функции при заданном наборе значений аргументов вычисляется подстановкой этих значений в выражение вместо переменных.
Для каждого логического выражения можно составить таблицу истинности , которая описывает, какое значение принимает соответствующая логическая функция (синоним: принимает выражение ) при каждом допустимом наборе значений переменных. Вот таблицы истинности для выражений x \/ y (таблица 6), x → y (таблица 7) и (x → y) /\ (y → z) (таблица 8).
2.4. Эквивалентные выражения.
Два логических выражения, содержащих переменные, называются равносильными (эквивалентными ), если значения этих выражений совпадают при любых значениях переменных. Так, выражения А → В и (¬А) \/ В равносильны, а А/\В и А \/ В – нет (значения выражений разные, например, при А = 1, В = 0).
Эквивалентные выражения имеют одинаковые таблицы истинности, а у неээквивалентных выражений таблицы истинности различны.
2.5. Приоритеты логических операций.
При записи логических выражений, как и при записи алгебраических выражений, иногда можно не писать скобки При этом соблюдаются следующие договоренности о старшинстве (приоритете) логических операций, первыми указаны операции, которые выполняются в первую очередь:
отрицание (инверсия),
конъюнкция (логическое умножение),
дизъюнкция (логическое сложение),
импликация (следование),
тождество.
Таким образом, ¬А \/ В \/ С \/ D означает то же, что и ((¬А) \/ В)\/ (С \/ D).
Возможна запись А \/ В \/ С вместо (А \/ В) \/ С. То же относится и к конъюнкции: возможна запись А /\ В /\ С вместо (А /\ В) /\ С.
Логика высказываний , называемая также пропозициональной логикой - раздел математики и логики, изучающий логические формы сложных высказываний, построенных из простых или элементарных высказываний с помощью логических операций.
Логика высказываний отвлекается от содержательной нагрузки высказываний и изучает их истинностное значение, то есть является ли высказывание истинным или ложным.
Рисунок сверху - иллюстрация явления, известного как "Парадокс лжеца". При этом, на взгляд автора проекта, такие парадоксы возможны только в средах, несвободных от политических заморочек, где на ком-то могут априори поставить клеймо лжеца. В естественном многослойном мире на предмет "истины" или "лжи" оцениваются только отдельно взятые высказывания . И далее на этом уроке вам представится возможность самим оценить на этот предмет немало высказываний (а затем посмотреть правильные ответы). В том числе сложных высказываний, в которых более простые связаны между собой знаками логических операций. Но прежде рассмотрим сами эти операции над высказываниями.
Логика высказываний применяется в информатике и программировании в виде объявления логических переменных и присвоения им логических значений "ложь" или "истина", от которых зависит ход дальнейшего исполнения программы. В небольших программах, где задействована лишь одна логическая переменная, этой логической переменной часто даётся имя, например, "флаг" ("flag") и подразумевается, что "флаг поднят", когда значение этой переменной - "истина" и "флаг опущен", когда значение этой переменной - "ложь". В программах большого объёма, в которых несколько или даже очень много логических переменных, от профессионалов требуется придумывать имена логических переменных, имеющих форму высказываний и смысловую нагрузку, отличающую их от других логических переменных и понятных другим профессионалам, которые будут читать текст этой программы.
Так, может быть объявлена логическая переменная с именем "ПользовательЗарегистрирован" (или его англоязычный аналог), имеющая форму высказывания, которой может быть присвоено логическое значение "истина" при выполнении условий, что данные для регистрации отправлены пользователем и эти данные программой признаны годными. В дальнейших вычислениях значения переменных могут меняться в зависимости от того, какое логическое значение ("истина" или "ложь") имеет переменная "ПользовательЗарегистрирован". В других случах переменной, например, с именем "ДоДняХОсталосьБолееТрёхДней", может быть присвоено значение "Истина" до некоторого блока вычислений, а в ходе дальнейшего исполнения программы это значение может сохраняться или меняться на "ложь" и от значения этой переменной зависит ход дальнейшего исполнения программы.
Если в программе используются несколько логических переменных, имена которых имеют форму высказываний, и из них строятся более сложные высказывания, то намного проще разрабатывать программу, если перед её разработкой записать все операции с высказываний в виде формул, применяемых в логике высказываний, чем мы в ходе этого урока и займёмся.
Для математических высказываний всегда можно сделать выбор между двумя различными альтернативами "истина" и "ложь", а для высказываний, сделанных на "словесном" языке, понятия "истинности" и "ложности" несколько более расплывчаты. Однако, например, такие словесные формы, как "Иди домой" и "Идёт ли дождь?", не являются высказываниями. Поэтому понятно, что высказываниями являются такие словесные формы, в которых что-либо утверждается . Не являются высказываниями вопросительные или восклицательные предложения, обращения, а также пожелания или требования. Их невозможно оценить значениями "истина" и "ложь".
Высказывания же, напротив, можно рассмотривать как величину, которая может принимать два значения: "истина" и "ложь".
Например, даны суждения: "собака - животное", "Париж - столица Италии", "3
Первое из этих высказываний может быть оценено символом "истина", второе - "ложь", третье - "истина" и четвёртое - "ложь". Такая трактовка высказываний составляет предмет алгебры высказываний. Будем обозначать высказывания большими латинскими буквами A , B , ..., а их значения, то есть истину и ложь, соответственно И и Л . В обычной речи употребляются связи между высказываниями "и", "или" и другие.
Эти связи позволяют, соединяя между собой различные высказывания, образовывать новые высказывания - сложные высказывания . Например, связка "и". Пусть даны высказывания: "π больше 3" и высказывание "π меньше 4". Можно организовывать новое - сложное высказывание "π больше 3 и π меньше 4". Высказывание "если π иррационально, то π ² тоже иррационально" получается связыванием двух высказываний связкой "если - то". Наконец, мы можем получить из какого-либо высказывания новое - сложное высказывание - отрицая первоначальное высказывание.
Рассматривая высказывания как величины, принимающие значения И и Л , мы определим далее логические операции над высказываниями , которые позволяют из данных высказываний получать новые - сложные высказывания.
Пусть даны два произвольных высказывания A и B .
1 . Первая логическая операция над этими высказываниями - конъюнкция - представляет собой образование нового высказывания, которое будем обозначать A ∧ B и которое истинно тогда и только тогда, когда A и B истинны. В обычной речи этой операции соответствует соединение высказываний связкой "и".
Таблица истинности для конъюнкции:
| A | B | A ∧ B |
| И | И | И |
| И | Л | Л |
| Л | И | Л |
| Л | Л | Л |
2 . Вторая логическая операция над высказываниями A и B - дизъюнкция, выражаемая в виде A ∨ B , определяется следующим образом: оно истинно тогда и только тогда, когда хотя бы одно из первоначальных высказываний истинно. В обычной речи эта операция соответствует соединению высказываний связкой "или". Однако здесь мы имеем не разделительное "или", которое понимается в смысле "либо-либо", когда A и B не могут быть оба истинны. В определении логики высказываний A ∨ B истинно и при истинности лишь одного из высказываний, и при истинности обоих высказываний A и B .
Таблица истинности для дизъюнкции:
| A | B | A ∨ B |
| И | И | И |
| И | Л | И |
| Л | И | И |
| Л | Л | Л |
3 . Третья логическая операция над высказываниями A и B , выражаемая в виде A → B ; полученное таким образом высказывание ложно тогда и только тогда, когда A истинно, а B ложно. A называется посылкой , B - следствием , а высказывание A → B - следованием , называемая также импликацией. В обычной речи эта операция соответствует связке "если - то": "если A , то B ". Но в определении логики высказываний это высказывание всегда истинно независимо от того, истинно или ложно высказывание B . Это обстоятельство можно кратко сформулировать так: "из ложного следует всё, что угодно". В свою очередь, если A истинно, а B ложно, то всё высказывание A → B ложно. Оно будет истинным тогда и только тогда, когда и A , и B истинны. Кратко это можно сформулировать так: "из истинного не может следовать ложное".
Таблица истинности для следования (импликации):
| A | B | A → B |
| И | И | И |
| И | Л | Л |
| Л | И | И |
| Л | Л | И |
4 . Четвёртая логическая операция над высказываниями, точнее над одним высказыванием, называется отрицанием высказывания A и обозначается ~ A (можно встретить также употребление не символа ~, а символа ¬, а также верхнего надчёркивания над A ). ~ A есть высказывание, которое ложно, когда A истинно, и истинно, когда A ложно.
Таблица истинности для отрицания:
| A | ~ A |
| Л | И |
| И | Л |
5 . И, наконец, пятая логическая операция над высказываниями называется эквивалентностью и обозначается A ↔ B . Полученное таким образом высказывание A ↔ B есть высказывание истинное тогда и только тогда, когда A и B оба истинны или оба ложны.
Таблица истинности для эквивалентности:
| A | B | A → B | B → A | A ↔ B |
| И | И | И | И | И |
| И | Л | Л | И | Л |
| Л | И | И | Л | Л |
| Л | Л | И | И | И |
В большинстве языков программирования есть специальные символы для обозначения логических значений высказываний, записываются они почти во всех языках как true (истина) и false (ложь).
Подытожим вышесказанное. Логика высказываний изучает связи, которые полностью определяются тем, каким образом одни высказывания строятся из других, называемых элементарными. Элементарные высказывания при этом рассматриваются как целые, не разложимые на части.
Систематизируем в таблице ниже названия, обозначения и смысл логических операций над высказываниями (они нам вскоре вновь понадобятся для решения примеров).
| Связка | Обозначение | Название операции |
| не | отрицание | |
| и | конъюнкция | |
| или | дизъюнкция | |
| если..., то... | импликация | |
| тогда и только тогда | эквивалентность |
Для логических операций верны законы алгебры логики , которые можно использовать для упрощения логических выражений. При этом следует отметить, что в логике высказываний отвлекаются от смыслового содержания высказывания и ограничиваются рассмотрением его с той позиции, что оно либо истинно, либо ложно.
Пример 1.
1) (2 = 2) И (7 = 7) ;
2) Не(15 ;
3) ("Сосна" = "Дуб") ИЛИ ("Вишня" = "Клён") ;
4) Не("Сосна" = "Дуб") ;
5) (Не(15 20) ;
6) ("Глаза даны, чтобы видеть") И ("Под третьим этажом находится второй этаж") ;
7) (6/2 = 3) ИЛИ (7*5 = 20) .
1) Значение высказывания в первых скобках равно "истина", значение выражения во вторых скобках - также истина. Оба высказывания соединены логической операцией "И" (смотрим правила для этой операции выше), поэтому логическое значение всего данного высказывания - "истина".
2) Значение высказывания в скобках - "ложь". Перед этим зтим высказыванием стоит логическая операция отрицания, поэтому логическое значение всего данного высказывания - "истина".
3) Значение высказывания в первых скобках - "ложь", значение высказывания во вторых скобках - также "ложь". Высказывания соединены логической операцией "ИЛИ" и ни одно из высказываний не имеет значения "истина". Поэтому логическое значение всего данного высказывания - "ложь".
4) Значение высказывания в скобках - "ложь". Перед этим высказыванием стоит логическая операция отрицания. Поэтому логическое значение всего данного высказывания - "истина".
5) В первых скобках отрицается высказывание во внутренних скобках. Это высказывание во внутренних скобках имеет значение "ложь", следовательно, его отрицание будет иметь логическое значение "истина". Высказывание во вторых скобках имеет значение "ложь". Два этих высказывания соединены логической операцией "И", то есть получается "истина И ложь". Следовательно, логическое значение всего данного высказывания - "ложь".
6) Значение высказывания в первых скобках - "истина", значение высказывания во вторых скобках - также "истина". Два этих высказывания соединены логической операцией "И", то есть получается "истина И истина". Следовательно, логическое значение всего данного высказывания - "истина".
7) Значение высказывания в первых скобках - "истина". Значение высказывания во вторых скобках - "ложь". Два этих высказывания соединены логической операцией "ИЛИ", то есть получается "истина ИЛИ ложь". Следовательно, логическое значение всего данного высказывания - "истина".
Пример 2. Запишите с помощью логических операций следующие сложные высказывания:
1) "Пользователь не зарегистрирован";
2) "Сегодня воскресенье и некоторые сотрудники находятся на работе";
3) "Пользователь зарегистрирован тогда и только тогда, когда отправленные пользователем данные признаны годными".
1) p - одиночное высказывание "Пользователь зарегистрирован", логическая операция: ;
2) p - одиночное высказывание "Сегодня воскресенье", q - "Некоторые сотрудники находятся на работе", логическая операция: ;
3) p - одиночное высказывание "Пользователь зарегистрирован", q - "Отправленные пользователем данные признаны годными", логическая операция: .
Пример 3. Вычислите логические значения следующих высказываний:
1) ("В минуте 70 секунд") ИЛИ ("Работающие часы показывают время") ;
2) (28 > 7) И (300/5 = 60) ;
3) ("Телевизор - электрический прибор") И ("Стекло - дерево") ;
4) Не((300 > 100) ИЛИ ("Жажду можно утолить водой")) ;
5) (75 < 81) → (88 = 88) .
Пример 4. Запишите с помощью логических операций следующие сложные высказывания и вычислите их логические значения:
1) "Если часы неправильно показывают время, то можно невовремя прийти на занятия";
2) "В зеркале можно увидеть своё отражение и Париж - столица США";
Пример 5. Определите логическое значение выражения
(p → q ) ↔ (r → s ) ,
p = "278 > 5" ,
q = "Яблоко = Апельсин" ,
p = "0 = 9" ,
s = "Шапка покрывает голову" .
Понятие логической формы сложного высказывания уточняется с помощью понятия формулы логики высказываний .
В примерах 1 и 2 мы учились записывать с помощью логических операций сложные высказывания. Вообще-то они называются формулами логики высказываний.
Для обозначения высказываний, как и упомянутом примере, будем продолжать использовать буквы
p , q , r , ..., p 1 , q 1 , r 1 , ...
Эти буквы будут играть роль переменных, принимающих в качестве значений истинностные значения "истина" и "ложь". Эти переменные называются также пропозициональными переменными. Мы будем далее называть их элементарными формулами или атомами .
Для построения формул логики высказываний кроме указанных выше букв используются знаки логических операций
~, ∧, ∨, →, ↔,
а также символы, обеспечивающие возможность однозначного прочтения формул - левая и правая скобки.
Понятие формулы логики высказываний определим следуюшим образом:
1) элементарные формулы (атомы) являются формулами логики высказываний;
2) если A и B - формулы логики высказываний, то ~A , (A ∧ B ) , (A ∨ B ) , (A → B ) , (A ↔ B ) тоже являются формулами логики высказываний;
3) только те выражения являются формулами логики высказываний, для которых это следует из 1) и 2).
Определение формулы логики высказываний содержит перечисление правил образования этих формул. Согласно определению, всякая формула логики высказываний либо есть атом, либо образуется из атомов в результате последовательного применения правила 2).
Пример 6. Пусть p - одиночное высказывание (атом) "Все рациональные числа являются действительными", q - "Некоторые действительные числа - рациональные числа", r - "некоторые рациональные числа являются действительными". Переведите в форму словесных высказываний следующие формулы логики высказываний:
6) 
.
1) "нет действительных чисел, которые являются рациональными";
2) "если не все рациональные числа являются действительными, то нет рациональных чисел, являющихся действительными";
3) "если все рациональные числа являются действительными, то некоторые действительные числа - рациональные числа и некоторые рациональные числа являются действительными";
4) "все действительные числа - рациональные числа и некоторые действительные числа - рациональные числа и некоторые рациональные числа являются действительными числами";
5) "все рациональные числа являются действительными тогда и только тогда, когда не имеет место быть, что не все рациональные числа являются действительными";
6) "не имеет места быть, что не имеет место быть, что не все рациональные числа являются действительными и нет действительных чисел, которые являются рациональными или нет рациональных чисел, которые являются действительными".
Пример 7.
Составьте таблицу истинности для формулы
логики высказываний 
, которую в
таблице можно обозначить f
.
Решение. Составление таблицы истинности начинаем с записи значений ("истина" или "ложь") для одиночных высказываний (атомов) p , q и r . Все возможные значения записываются в восемь строк таблицы. Далее, определяя значения операции импликации, и продвигаясь вправо по таблице, помним, что значение равно "лжи" тогда, когда из "истины" следует "ложь".
| p | q | r | f | ||||
| И | И | И | И | И | И | И | И |
| И | И | Л | И | И | И | Л | И |
| И | Л | И | И | Л | Л | Л | Л |
| И | Л | Л | И | Л | Л | И | И |
| Л | И | И | Л | И | Л | И | И |
| Л | И | Л | Л | И | Л | И | Л |
| Л | Л | И | И | И | И | И | И |
| Л | Л | Л | И | И | И | Л | И |
Заметим, что никакой атом не имеет вида ~A , (A ∧ B ) , (A ∨ B ) , (A → B ) , (A ↔ B ) . Такой вид имеют сложные формулы.
Число скобок в формулах логики высказываний можно уменьшить, если принять, что
1) в сложной формуле будем опускать внешнюю пару скобок;
2) упорядочим знаки логических операций "по старшинству":
↔, →, ∨, ∧, ~ .
В этом списке знак ↔ имеет самую большую область действия, а знак ~ - самую маленькую. Под областью действия знака операции понимаются те части формулы логики высказываний, к которым применяется (на которые действует) рассматриваемое вхождение этого знака. Таким образом, можно опускать во всякой формуле те пары скобок, которые можно восстановить, учитывая "порядок старшинства". А при восстановлении скобок сначала расставляются все скобки, относящиеся ко всем вхождениям знака ~ (при этом мы продвигаемся слева направо), затем ко всем вхождениям знака ∧ и так далее.
Пример 8. Восстановите скобки в формуле логики высказываний B ↔ ~ C ∨ D ∧ A .
Решение. Скобки восстанавливаются пошагово следующим образом:
B ↔ (~ C ) ∨ D ∧ A
B ↔ (~ C ) ∨ (D ∧ A )
B ↔ ((~ C ) ∨ (D ∧ A ))
(B ↔ ((~ C ) ∨ (D ∧ A )))
Не всякая формула логики высказываний может быть записана без скобок. Например, в формулах А → (B → C ) и ~ (A → B ) дальнейшее исключение скобок невозможно.
Логические тавтологии (или просто тавтологии) - это такие формулы логики высказываний, что если буквы произвольным образом заменить высказываниями (истинными или ложными), то в результате всегда получится истинное высказывание.
Так как истинность или ложность сложных высказываний зависит лишь от значений, а не от содержания высказываний, каждому из которых соответствует определённая буква, то проверку того, является ли данное высказывание тавтологией, можно подставить следующим способом. В исследуемом выражении на место букв подставляются значения 1 и 0 (соответственно "истина" и "ложь") всеми возможными способами и с использованием логических операций вычисляются логические значения выражений. Если все эти значения равны 1, то исследуемое выражение есть тавтология, а если хотя бы одна подстановка даёт 0, то это не тавтология.
Таким образом, формула логики высказываний, которая принимает значение "истина" при любом распределении значений входящих в эту формулу атомов, называется тождественно истинной формулой или тавтологией .
Противоположный смысл имеет логическое противоречие. Если все значения высказываний равны 0, то выражение есть логическое противоречие.
Таким образом, формула логики высказываний, которая принимает значение "ложь" при любом распределении значений входящих в эту формулу атомов, называется тождественно ложной формулой или противоречием .
Кроме тавтологий и логических противоречий существуют такие формулы логики высказываний, которые не являются ни тавтологиями, ни противоречиями.
Пример 9. Составьте таблицу истинности для формулы логики высказываний и определите, является ли она тавтологией, противоречием или ни тем, ни другим.
Решение. Составляем таблицу истинности:
| И | И | И | И | И |
| И | Л | Л | Л | И |
| Л | И | Л | И | И |
| Л | Л | Л | Л | И |
В значениях импликации не встречаем строку, в которой из "истины" следует "ложь". Все значения исходного высказывания равны "истине". Следовательно, данная формула логики высказываний является тавтологией.
