Высказывания и логические связки
Содержание статьи
Высказывания и логические связки
Многие математические понятия удобно записывать в виде выражений, содержащих некоторые логические символы. Так, символ , называеый квантором общности, используется вместо слов: «для любого», «для всех», «каково бы ни было…» и т.д., а символ — квантор существования — вместо слов «существует», «найдется хотя бы один …», «имеется» и т.д.
Основной объект математической логики — высказывание. Высказыванием называется повествовательное предложение, которое может быть классифицировано либо как истинное, либо как ложное, но не как и то и другое вместе.
Содержание высказывания несущественно: лишь бы это предложение могло быть либо истинным, либо ложным. При этом вовсе не обязательно указывать способ проверки истинности. Главное, что высказывание не может быть истинным и ложным одновременно. Если высказывание истинно, будем говорить, что его значение истинности — истина (или (от английского true); если ложно, то значение истинности — ложь (от false).
Высказывания в математической логике обычно обозначаются прописными латинскими буквами: , , и т.д. Для того чтобы из высказываний получать новые высказывания, применяются специальные операции — логические связка. Рассмотрим пять основных логических связок. Сначала дадим неформальное объяснение. Однако оно чревато неточностями, поэтому дадим логическим операциям также строгое определение. Определить высказывание — значит указать, в каких случаях оно истинно, а в каких ложно.
Отрицание — это высказывание, которое получается из данного высказывания с помощью слова «не». Отрицание можно обозначать по-разному: , , .
Простое добавление слова «не» к высказыванию чаще всего будет противоречить языковым нормам. Поэтому в конкретных случаях требуется «перевод» полученного высказывания на русский язык. Пусть, например, = «Завтра пойдет дождь». Что значит «Не (Завтра пойдет дождь)»: «Дождь пойдет не завтра», «Завтра пойдет не дождь» или «Завтра не пойдет дождь»? Здравый смысл подсказывает, что отрицанием высказывания является третье предложение. Чтобы определить точно, дадим формальное определение отрицания.
Отрицанием высказывания называется такое высказывание, которое принимает значение (ложно), если высказывание истинно, и значение (истинно), если высказывание ложно. В нашем примере этому условию удовлетворяет только третье предложение. Итак, = «Завтра не пойдет дождь».
Дизъюнкция — это высказывание, которое получается из двухданных высказываний и с помощью союза «или». Дизъюнкция обозначается .
Дизъюнкция строится с помощью неисключающего «или». Таким
образом, дизъюнкция истинна, когда истинно по крайней мере
одно из высказываний и или оба вместе. Другими словами,дизъюнкция
ложна в том и только в том случае, когда оба высказывания ложны.
Конъюнкция — это высказывание, которое получается из двух данных высказываний и спомощью союза «и». Конъюнкция обозначается . Конъюнкция справедлива в том и только в том случае, когда оба высказывания истинны.
Импликацияобразуется из высказываний и с помощью слов «если… то…». Получается высказывание вида «если то ». Напомним, что. математическая. логика. носит формальный характер, содержанием высказываний она не, занимается.
На примере импликации хорошо видна разница между обычным языком и языком логики. В обычном языке сложное предложение «если , то » предполагает между и отношение посылки и следствия или же причины и обусловленного ею действия. В логике импликация связывает любые два высказывания.
Импликация обозначается , при этом говорят: «влечет » или «при условии, что », «, если », «есть достаточное условие для », «есть необходимое условие для ».
Договорились, что импликация ложна в том и только в том случае, когда высказывание истинно, а высказывание ложно. Такое определение подсказано здравым смыслом: разумно считать импликацию истинной, если истинно, независимо от значения ; если оба участника импликации ложны, импликация, естественно, также истинна. В единственном случае, когда «предпосылка» импликации истинна, а «вывод» ложен, импликация считается ложной.
Эквиваленция образуется из высказываний и с помощью слов «…тогда и только тогда, когда…»:
Утверждение «тогда и только тогда, когда » не означает в логике, что составляющие высказывания и имеют одно и то же значение или один и тот же смысл.
Эквиваленция обозначается . Синонимы для эквиваленции: «если , то , и если , то », « в том и только в том случае, когда », «И есть необходимое и достаточное условие для », « есть необходимое и достаточное условие для ». Разумное определение эквиваленции: эквиваленция истинна в том и только в том случае, когда высказывания и имеют одинаковое значение истинности (либо оба истинны, либо оба ложны).
Новые высказывания (отрицание, дизъюнкция, конъюнкция, импликация и эквиваленция) образуются из существующих высказываний с помощью операций, или логических связок, имеющих те же названия.
В логике, как и в арифметике, операции делятся по старшинству. Это позволяет при записи сложных высказываний избегать большого количества скобок. Порядок выполнения операций таков: приоритет имеет отрицание, затем на одном уровне — дизъюнкция и конъюнкция, следующая связка — импликация и, наконец, самая последняя — эквиваленция.
Контрольные вопросы к теме:
1. Понятия доказательного рассуждения и правдоподобного рассуждения.
2. Метод математической индукции.
3. Обобщение, специализация, аналогия.
4. Понятие логической связки.
5. Отрицание, дизъюнкция и конъюнкция.
6. Понятия импликации и эквиваленции.
Источник
Электронная библиотека
Определение. Под высказыванием принято понимать языковое предложение, о котором имеет смысл говорить, что оно истинно или ложно в данный момент времени.
Высказывания чаще всего обозначают маленькими латинскими буквами a, b, c, х1, х2, …
В логике высказываний интересуются не содержанием, а истинностью или ложностью высказываний. Истинностные значения — истина и ложь — будем обозначать И и Л соответственно. Множество {И, Л} называется множеством истинностных значений.
Определение. Высказывание называют простым (элементарным), если оно рассматривается как некое неделимое целое (аналогично элементу множества). Сложным (составным) называется высказывание, составленное из простых с помощью логических связок.
В естественном языке роль связок при составлении сложных предложений из простых играют следующие грамматические средства: союзы «и», «или», «не»; слова «если …, то», «либо … либо», «тогда и только тогда, когда» и др. В логике высказываний логические связки, используемые для составления сложных высказываний, обязаны быть определены точно. Рассмотрим логические связки (операции) над высказываниями, при которых истинностные значения составных высказываний определяются только истинностными значениями составляющих высказываний, а не их смыслом.
В дальнейшем значению «истина» будем ставить в соответствие 1, а «ложь» — 0. Каждой логической операции ставится в соответствие таблица истинности. Таблица истинности выражает значения истинности высказываний в зависимости от значений элементарных высказываний. В дальнейшем буден использовать таблицу истинности для установления истинностных значений сложных высказываний при данных значениях входящих в него элементарных высказываний.
Определение. Отрицанием высказывания является новое высказывание, истинное только тогда, когда исходное высказывание ложно (табл. 2.13).
Таблица 2.1 Таблица истинности для отрицания
номер набора | a | |
1 | ||
1 | 1 |
Отрицание обозначается через и читается как «не а», «неверно, что а».
Пример 15.
А — «Степан любит танцевать».
Тогда — «Не верно, что Степан любит танцевать».
Определение. Конъюнкцией двух высказываний является новое высказывание, которое истинно только тогда, когда оба исходных высказывания истинны (табл. 2.2).
Конъюнкция обозначается или a&b и читается как «a и b», «a, но b», «a, а b».
Таблица 2.2 Таблица истинности для конъюнкции
номер набора | a | b | aÙb |
1 | 1 | ||
2 | 1 | ||
3 | 1 | 1 | 1 |
Пример 16.
а — «Степан любит танцевать», b — «Степан любит петь».
Тогда — «Степан любит танцевать и петь».
Определение. Дизъюнкцией двух высказываний является новое высказывание, которое ложно только тогда, когда оба исходных высказывания ложны (табл. 2.3).
Дизъюнкция обозначается через и читается как «a или b».
Таблица 2.3 Таблица истинности для дизъюнкции
номер набора | a | b | aÚb |
1 | 1 | 1 | |
2 | 1 | 1 | |
3 | 1 | 1 | 1 |
Пример 17.
а — «Степан любит танцевать», b — «Степан любит петь».
Тогда — «Степан любит танцевать или петь».
Определение. Импликацией двух высказываний является новое высказывание, которое ложно только тогда, когда первое истинно, а второе — ложно (табл. 2.4).
Импликация обозначается a® b и читается как «если a, то b»; « из а следует b». При этом a называется посылкой или условием, b — следствием или заключением.
Таблица 2.4 Таблица истинности для импликации
номер набора | a | b | a®b |
1 | |||
1 | 1 | 1 | |
2 | 1 | ||
3 | 1 | 1 | 1 |
Пример 18.
а — «Степан любит танцевать», b — «Степан любит петь».
Тогда — «Если Степан любит танцевать, то он любит петь».
Определение.
Эквиваленцией (или эквивалентностью) двух высказываний является новое высказывание, которое считается истинным, когда оба высказывания либо одновременно истинны, либо одновременно ложны, и ложным во всех остальных случаях (табл. 2.5).
Таблица 2.5 Таблица истинности для эквивалентности
номер набора | a | b | a»b |
1 | |||
1 | 1 | ||
2 | 1 | ||
3 | 1 | 1 | 1 |
Эквивалентность обозначается a» b и читается как «a эквивалентно b».
Пример 19.
а — «Степан любит танцевать», b — «Степан любит петь».
Тогда — «Для того, чтобы Степан любил танцевать, необходимо и достаточно, чтобы он любил петь».
Сведем все сказанное выше в единую таблицу и введем в рассмотрение еще три операции: сумма по модулю два, штрих Шеффера, стрелка Пирса (табл. 2.6).
Таблица 2.6 Краткие сведения о логических операциях
Обозначения логической операции | Другие обозначения логической операции | Набор истинностных значений, отвечающих данной логической операции | Названия логической операции и связки | Как читается выражение, приведенное в первом столбце |
a | 10 | отрицание | неверно, что а; не а | |
a b | a & b a×b ab min(a; b) | 0001 | конъюнкция, логическое умножение, логическое «и» | a и b |
a b | a+b max(a; b) | 0111 | дизъюнкция, логическое сложение, логическое «или» | а или b |
a® b | ab ab | 1101 | импликация, логическое следование | если а, то b; а имплицирует b; а влечет b |
a » b | a b a « b a b | 1001 | эквиваленция, эквивалентность, равнозначность, тождественность | а тогда и только тогда, когда b; а эквивалентно b |
a b | a+ b a D b | 0110 | сумма по модулю два, разделительная дизъюнкция, разделительное «или» | а плюс b; либо а, либо b |
а|b | 1110 | штрих Шеффера, антиконъюнкция | неверно, что а и b; а штрих Шеффера b | |
a b | a o b | 1000 | стрелка Пирса, антидизъюнкция, функция Вебба, функция Даггера | ни а, ни b; а стрелка Пирса b |
Источник
Логические связки
Логические связки, или логические операции — это символические конструкции логических языков (см. Язык формализованный), используемые для образования сложных высказываний (формул) из элементарных высказываний (см. Высказывание). Логическими связками называют также соответствующие этим символам союзы естественного языка (см. Язык). Обычно используются пять общеизвестных логических связок:
Из указанных логических связок отрицание называется одноместной (унарной) связкой; другие называются двухместными (бинарными) связками. В принципе, логические связки могут быть сколь угодно местными, но на практике более, чем бинарные, используются очень редко. В классической логике (см. Логика) любые многоместные логические связки выразимы через перечисленные. Некоторый практический смысл даёт также использование тернарной логической связки, называемой условной дизъюнкцией, связывающей три высказывания A, B и C и означающей, что «A в случае B, и C в случае не-B» или формально: (B ⊃ A) & (¬ B ⊃ C). Классическая логика рассматривает логические связки экстенсионально (игнорируя содержательный смысл связываемых ими высказываний) как функции истинности, определяемые истинностными значениями связываемых ими высказываний. При двух имеющих место в этой логике истинностных значениях 1 (истинно) и 0 (ложно) высказывания A и B могут иметь четыре возможных набора упорядоченных истинностных значений: (1, 1), (1, 0), (0, 1), (0, 0). Пропозициональная истинностная функция ставит в соответствие каждому перечисленному набору одно из значений истинности — 1 или 0. Всего таких функций 16. Конъюнкция приписывает выражению A & B значение 1 только в случае, когда как A, так и B истинны, то есть оба имеют значение 1, в остальных случаях значение A & B равно 0. Дизъюнкция Α ∨ B, напротив, ложна только в одном случае, когда ложны как A, так и B. Импликация A ⊃ B является ложной только при истинном (антецеденте) A и ложном (консеквенте) B. В остальных случаях A ⊃ B принимает значение 1. Из четырёх одноместных функций интерес представляет только отрицание, меняющее значение высказывания на противоположное: когда A — истинно, ¬ A — ложно, и наоборот. Все другие унарные и бинарные классические функции могут быть выражены через представленные. Когда принятая в соответствующей семантике система логических связок позволяет дать определение всех остальных, её называют функционально полной. К полным системам в классической логике относятся, в частности, конъюнкция и отрицание; дизъюнкция и отрицание; импликация и отрицание. Конъюнкция и дизъюнкция определимы друг через друга за счёт эквивалентностей (A & B) ≡ ¬ (¬ A∨ ¬ B) и (A ∨ B) ≡ ¬ (¬ A & ¬ B), именуемых законами де Моргана, а также: (Α ⊃ Β) ≡ (¬ Α ∨ B), (A & B) ≡ ¬ (A ⊃ ¬ B), (Α ∨ B) ≡ (A ⊃ B) ⊃ A). Любая эквивалентность вида A ≡ B имеет силу только тогда, когда общезначима (всегда истинна) конъюнкция (A ⊃ B) & (B ⊃ A). Функции антидизъюнкция и антиконъюнкция, определимые соответственно как ¬ (A ∨ B) и ¬ (A & B), также представляют каждая в отдельности функционально полную систему связок. Это последнее обстоятельство было известно уже Ч. С. Пирсу (неопубликованная при его жизни работа 1880 года) и было переоткрыто X. Шеффером. Используя антидизъюнкцию как единственную логическую связку, Шеффер в 1913 построил полное исчисление высказываний. Антидизъюнкцию обозначают A∣B и называют штрихом Шеффера, читая данное выражение, как «не-A и не-B». Ж. Нико употребил то же обозначение для антиконъюнкции («Неверно, что одновременно A и B») и с помощью только этой связки в 1917 сформулировал полное исчисление высказываний с одной (всего!) аксиомой и одним правилом вывода. Таким образом, штрихом Шеффера называют по сути саму вертикальную черту, которая у разных авторов может обозначать как антидизъюнкцию, так и антиконъюнкцию. Экстенсиональность логических связок придаёт им однозначность, упрощает проблему построения логических исчислений, даёт возможность решать для последних метатеоретические проблемы непротиворечивости, разрешимости, полноты. Однако в некоторых случаях истинностно-функциональная трактовка связок приводит к значительному несоответствию с тем, как они понимаются в естественном языке. Так, указанная истинностная интерпретация импликации вынуждает признавать верными предложения вида «Если A, то B» даже в том случае, когда между высказываниями A и B (и, соответственно, событиями, о которых в них идёт речь) нет никакой реальной связи. Достаточно, чтобы A было ложным или B — истинным. Поэтому из двух предложений: «Если A, то B» и «Если B, то A», по крайней мере одно приходится признавать верным, что плохо сообразуется с обычным употреблением условной связки. Импликацию в данном случае специально называют «материальной», отличая её тем самым от условного союза, предполагающего, что между антецедентом и консеквентом истинного условного высказывания имеется действительная связь. При этом материальная импликация может прекрасно использоваться во многих контекстах, например, математических, когда при этом не забывают о её специфических особенностях. В некоторых случаях, однако, именно контекст не позволяет трактовать условный союз как материальную импликацию, предполагая взаимосвязь высказываний. Для анализа таких контекстов приходится строить специальные неклассические логики (например, релевантные логики), в язык которых вместо материальной импликации (или наряду с ней) вводятся другие импликации, которые понимаются интенсионально (содержательно) и верность которых не может быть обоснована истинностно-функционально. Интенсионально могут трактоваться также и другие логические связки. |
Источник
Логические связки логики высказываний
Мы поможем в написании ваших работ! Мы поможем в написании ваших работ! Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ? |
В алгебре предикатов не существенен конкретный смысл высказываний, а только их значения ( ). АЛГЕБРА ВЫСКАЗЫВАНИЙ Алгеброй высказыванийназывается множество , на котором определены логические операции отрицания, конъюнкции, дизъюнкции, импликации и эквивалентности. Отрицаниемвысказывания называется высказывание , которое истинно, если ложно, и ложно, если истинно: Отрицание по определению — унарная операция. В естественном языке данной логической операции соответствует отрицание, которое может иметь разные синтаксические выражения. Пример 1 Пусть высказывание «У Ивана есть время». Тогда высказывание можно представить такими повествовательными предложениями: «Не верно, что у Ивана есть время»; «Не правда, что у Ивана есть время»; «У Ивана нет времени».∎ Конъюнкцией (логическим произведением) высказываний и называют высказывание , которое истинно, если оба высказывания и — истинны, и ложно, если хотя бы одно с них — ложное: Эта логическая операция соответствует союзу «и» естественного языка: « и ». Пример 2 Записатьформулой алгебры высказываний предложение естественного языка: «6 делится на 3 и 10 больше 5». Выполнение.Введем атомы: : «6 делится на 3»; : «10 больше 5». Тогда заданное предложение естественного языка можно представить формулой алгебры высказываний . Так как и , то и , то есть высказывание «6 делится на 3 и 10 больше 5» — истинно.∎ Дизъюнкцией высказываний и называют высказывание , которое истинно, если хотя бы одно из высказываний или — истинно, и ложно, если оба высказывания — ложные: Эта логическая операция соответствует союзу «или» естественного языка: « или ». Пример 3 Записатьформулой алгебры высказываний повествовательное предложение естественного языка: «6 делится на 3 или 10 больше 15». Выполнение. Введем атомы: : «6 делится на 3»; : «10 больше 15». Тогда заданное предложение естественного языка можно представить формулой алгебры высказываний . Так как и , то , то есть высказывание «6 делится на 3 или 10 больше 15» — истинно.∎ Импликацией двух высказываний и называют высказывание , которое ложно, если высказывание — истинно, а высказывание — ложно, и ложное в остальных случаях: Эта логическая операция в естественном языке представлена такими оборотами: «если , то », « — достаточное основание для », « потому что », « — условие для выполнения », « тянет ». В импликации высказывание называется посылкой(условием), — заключением (выводом). Пример 4 Высказывание «Если натуральное число 16 делится на 4, то оно четное» можно представить формулой , где атом Натуральное число 16 делится на 4», а атом : «Натуральное число 16 четное». Так как , , то , то есть высказывание «Если натуральное число 16 делится на 4, то оно четное» истинно.∎ Пример 5 Высказывание «Если натуральное число 32 делится на 8, то оно нечетное» можно представить формулой , где атом : «Натуральное число 32 делится на 8», а атом : «Натуральное число 32 нечетное». Так как , , то , то есть высказывание «Если натуральное число 32 делится на 8, то оно нечетное» ложно.∎ Пример 6 Высказывание «Если натуральное число 32 делится на 7, то оно четное» можно представить формулой , где атом : «Натуральное число 32 делится на 7», а атом : «Натуральное число 32 четное». Так как , , то , то есть высказывание «Если натуральное число 32 делится на 7, то оно четное» истинно.∎ Эквивалентностью двух высказываний и называют высказывание , которое истинно, если высказывание и имеют одинаковые истинностные значения, и ложно, если эти значения разные. В естественном языке эквивалентности соответствуют «тогда и только тогда», «эквивалентно», «все равно что….», «тождественно» и т. п. Пример 2 Высказывание «Изучение информатики будет успешным тогда и только тогда, когда будет усвоена математическая логика» можно представить формулой , где атом : «Изучение информатики успешное», а атом : «Математическая логика усвоена».∎ Выражения , , , — это атомы (первичные, элементарные формулы) логики высказываний. Сложные формулы логики высказываний (молекулы) создаются с атомов с помощью логических операций отрицания, конъюнкции, дизъюнкции, импликации и эквивалентности. Правильно построенная формула алгебры высказываний определяется рекурсивно следующим образом: · Атом — формула; · Если и — формулы, то , , , , — также формулы; · Никаких формул, кроме порожденных формул указанными выше правилами, не существует. Если формула содержит атомы , то будем обозначать ее как . Пример 2 .∎ Приписывание истинностных значений атомам, входящих в высказывание называется интерпретацией высказывания. Для высказывания, содержащего атомов, существует интерпретаций. Операции алгебры логики на множестве и алгебры высказываний на множестве одинаковы, а между множествами и можно установить взаимно-однозначное соответствие (биекцию). Это означает, что алгебры логики и высказываний изоморфны. Это значит, что все определения, теоремы, выводы алгебры логики справедливы и в алгебре высказываний (после соответствующих переформулировок). При этом: · атомы алгебры высказываний соответствуют логическим переменным алгебры логики; · истинностные значения высказываний F и T соответствуют логическим значениям 0 и 1; · формулы алгебры высказываний соответствуют формулам алгебры логики; · интерпретации высказывания алгебры высказываний соответствуют словам алгебры логики и т. д. Это дает возможность, например, вычисление значения формулы алгебры высказываний, привести к вычислению логичного значения соответствующего выражения алгебры логики Пример 2 Задана формула алгебры высказываний . Вычислить истинностное значение этой формулы с использованием соответствующей формулы алгебры логики если , , . Выполнение. Сопоставим атомам , , логические переменные , , соответственно. По условию , , Соответствующая заданной формуле алгебры высказываний формула алгебры логики имеет вид: . Вычисление по формуле. 1) ; 2) ; 3) ; 4) ; 5) ; 6) . Ответ: .∎ ПРАКТИЧЕСКОЕ ЗАНЯТИЕ 1 Упражнение 1. Среди следующих предложений естественного языка выделить высказывания, определить, истинные они, или ложные. 1) Река Днепр впадает в Черное море. 2) Любой человек имеет брата. 3) Пейте томатный сок! 4) Ни один человек не весит больше 10000 кг. 5) Существует человек младше своего отца. 6) Где твоя чашка? 7) . 8) Для любых действительных чисел . 9) . 10)Любое действительное число . 11) . 12)При . 13)Не существует при котором . Выполнение. 1) Да, это высказывание, оно истинно. 2) Да, высказывание ложно. 3) Нет, это восклицательное предложение. 4) Да, высказывание истинно. 5) Да, оно ложно. 6) Нет, это вопросительное предложение. 7) Да, высказывание ложное. 8) Да, высказывание истинно. 9) Да, высказывание ложно, . 10) Да, высказывание ложно. 11) Нет, не высказывание. Это алгебраическое выражение. 12) Да, высказывание истинно. 13) Да, высказывание истинно. Упражнение 2. Записать формулами алгебры высказываний такие высказывания. 1) 45 кратное 3 и 42 кратное 3. 2) 45 кратное 3 и 12 не кратное 3; 3) и ; 4) ; 5) Если число 212 делится на 3 и 4, то оно делится и на 12; 6) Число 212 — трехзначное число, которое делится на 3 и 4. Выполнение. 1) Атомы: : «45 кратное 3»; : «42 кратное 3». Формула логики высказываний: . Так как и , то (заданное высказывание истинно). 2) Атомы: : «45 кратное 3»; : «12 кратное 3». Формула логики высказывания: . Так как и , то (заданное высказывание ложно). 3) Атомы: : « »; : « ». Формула логики высказывания . Так как и , то . 4) Атом : « ». Формула логики высказываний (атомарная формула). Так как , то заданное высказывание истинно. 5) Атомы: : «число 212 делится на 3»; : «число 212 делится на 4», : «число 212 делится на 12». Формула логики высказываний: . Так как , , , то . 6) Атомы: : «число 212 делится на 3»; : «число 212 делится на 4», : «212 — трехзначное число». Формула логики высказывание . Так как , , , то . УПРАЖНЕНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ Какие из утверждений — высказывания? 1) Нью-Йорк — столица Канады; 2) Лондон — город на правом берегу Дона; 3) Студент физико-математического факультета; 5) 5 — логическое значение; . |
Источник