Задачи по математической логике.

[Sdy]

Имеется несколько задач, которые я решил, но хотелось бы удостовериться, в том что решены они правильно. Ответов и указаний к ним к сожалению нет, а к двум из этих задач мой "интуитивный" ответ разошелся с тем, который я получил строгими рассуждениями.
Задачи взяты из изучаемой мною книги Terence Tao, Analysis I, Appendix A.
Истинность утверждения $X$ я записываю как $X=1$.(В силу того что в моей голове $1$ плотно проассоциирована с $true$, a $0$ - c $false$.) Если это грубость - я всё поправлю.
Сначала я привожу оригинальный текст, затем мой перевод условия.
Задача 1.
Suppose that you have shown that whether X is true, then Y is true, and whenever X is false, then Y is false. Have you now demonstrated that $X$$\Leftrightarrow$$Y$?
Пусть $(X = 1 \Rightarrow Y = 1) \wedge (X = 0 \Rightarrow Y = 0)$. Доказать, что $X \Leftrightarrow Y$.
Решение.
Пойдем от противного.
Пусть $Y=0 \Rightarrow X=1$. Но мы знаем, что как только $X=1$, так сразу $Y=1$. Значит $Y=0 \Rightarrow X=0$.
Пусть $Y=1 \Rightarrow X=0$. Но мы знаем, что как только $X=0$, так сразу $Y=0$. Значит $Y=1 \Rightarrow X=1$.
Значит $X \Leftrightarrow Y$.$\triangle$

Задача 2.
Suppose you know that X is true iff Y is true and Y is true iff Z is true. Is it enough to show that $X \Leftrightarrow Y \Leftrightarrow Z$?
$X \Leftrightarrow Y \wedge Y \Leftrightarrow Z $. Верно ли, что $X \Leftrightarrow Y \Leftrightarrow Z$?.
Решение.
Нужно доказать, что $X \Leftrightarrow Z$. Но $(X = 1 \Rightarrow Y = 1) \wedge (Y = 1 \Rightarrow Z = 1)$. Значит $X = 1 \Rightarrow Z = 1$. Также выводим, что $(X = 0 \Rightarrow Z = 0) \wedge (Z = 0 \Rightarrow X = 0) \wedge (Z = 1 \Rightarrow X = 1)$. Значит $X \Leftrightarrow Y \Leftrightarrow Z$.$\triangle$

Задача 3.
Suppose you know that whenever X is true, then Y is true; that whenever Y is true, then Z is true, and whenever Z is true, then X is true. Is it enough to say that
$X \Leftrightarrow Y \Leftrightarrow Z$?
$(X = 1 \Rightarrow Y = 1) \wedge (Y = 1 \Rightarrow Z = 1) \wedge (Z = 1 \Rightarrow X = 1)$. Верно ли, что $X \Leftrightarrow Y \Leftrightarrow Z$?
Решение.
$((Y = 1 \Rightarrow Z = 1) \wedge (Z = 1 \Rightarrow X = 1)) \Rightarrow (Y = 1 \Rightarrow X = 1)$. Таким же образом устанавливаю, что $Z = 1 \Rightarrow Y = 1$ и $X = 1 \Rightarrow Z = 1$.
Тогда докажем, что $X = 0 \Rightarrow Y = 0$. От противного - пусть $Y = 1$. Но тогда бы и $X$ было равно $1$. Противоречие. Таким же образом доказываем, что $Y = 0 \Rightarrow X = 0$. Но тогда $X \Leftrightarrow Y$. Также доказываю и что $X \Leftrightarrow Z$ и $Z \Leftrightarrow Y$.
Значит все три утверждения логически эквивалентны. $\triangle$

[arseniiv]

Ну вроде содержательно всё прекрасно. Есть ли тут смысл настаивать на каких-то других обозначениях, не думаю; места для путаницы связок языка, к которому принадлежат сами $X, Y, Z$, и языка, на котором мы обсуждаем первый, тут я не заметил, так что про это можно ничего не говорить.

Sdy в сообщении #1413657 писал(а):

$X \Leftrightarrow Y \wedge Y \Leftrightarrow Z $

Деталь: обычно $\Leftrightarrow$ связывает слабее, чем $\wedge$ (как правило, приоритеты такие: ${\leftrightarrow},{\to},{\wedge},{\vee},{\neg}$). Конечно, на решении это никак не сказалось.

Про интуитивные ответы: можно ещё для начала убедиться в контрапозиции: если $X\to Y$ верно, то $\neg Y\to\neg X$ тоже верно. Так можно получить возможно более интуитивно согласующиеся доказательства для 2 и 3.

[Sdy]

arseniiv, спасибо за ответ.

arseniiv в сообщении #1413661 писал(а):

Деталь: обычно $\Leftrightarrow$ связывает слабее, чем $\wedge$

Забыл-таки и там добавить скобки.

arseniiv в сообщении #1413661 писал(а):

если $X\to Y$ верно, то $\neg Y\to\neg X$ тоже верно.

Хорошо, проделаю это для тренировки после того как в книге об этом будет рассказано. Вроде как уже в следующем параграфе.

[beroal]

Для тех, кто не читал эту книгу: в ней какой-то сплав из таблиц истинности и правил вывода, причём всё записано на естественном языке. Импликация объясняется после первого упражнения.

Цитата:

Exercise A.1.3. Suppose that you have shown that whenever $X$ is true, then $Y$ is true, and whenever $X$ is false, then $Y$ is false. Have you now demonstrated that $X$ and $Y$ are logically equivalent? Explain.

Цитата:

Допустим, вы показали, что если $X$ истинно, то $Y$ истинно, и если $X$ ложно, то $Y$ ложно. Показали ли вы, что $X$ и $Y$ логически эквивалентны? Объясните.

Раз уж вы решили работать по этой книге, надо следовать определениям автора. Смотрите, что он пишет:

Цитата:

…мы говорим, что «$X$ истинно тогда и только тогда, когда $Y$ истинно», если, когда $X$ истинно, $Y$ тоже должно быть таковым, и, когда $Y$ истинно, $X$ тоже должно быть таковым (то есть $X$ и $Y$ «одинаково истинны»). То же самое можно сказать другими способами: «$X$ и $Y$ — логически эквивалентные утверждения», или «$X$ истинно т. и т. т., когда $Y$ истинно», или «$X\iff Y$».

То есть в задаче уже дано то, что если $X$ истинно, то $Y$ истинно. Это часть определения логической эквивалентности. Осталось показать, что если $Y$ истинно, то $X$ истинно. Честно говоря, я плохо представляю, какое именно доказательство ожидал увидеть автор. Наверное, гипотетический вывод и потом от противного. Допустим, что $Y$ истинно. Допустим, что $X$ ложно. Тогда по условию…

Остальные упражнения не смотрел.

[arseniiv]

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

С другой стороны маленькая доля не сразу очевидных мест классической логики на самом деле следствие того, что мы специально выбрали её в некотором смысле наиболее простой из логик вообще. Например закон Пирса, если бы на нём чаще останавливалось внимание в книгах, скорее всего приводил бы тоже к куче тем на форуме. А из задач этой темы в интуиционистской, к примеру, логике 2 осталось бы истинным, но не 1: $\neg X\to\neg Y$ влечёт $\neg\neg Y\to\neg\neg X$, но не обязательно $Y\to X$, так что мы не будем иметь $X\leftrightarrow Y$, хотя будем иметь $\neg X\leftrightarrow\neg Y$.

3 тоже осталось бы истинным, и кстати я прозевал более прозрачное доказательство, чем у ТС: не будем ничего дополнительно предполагать; раз $X\to Y, Y\to Z$, то $X\to Z$, ну а вместе с $Z\to X$ это даст $X\leftrightarrow Z$, и аналогично с двумя остальными парами. Вообще рассмотрим граф, вершины которого — какие-то высказывания, и есть дуга $u\to v$, если верна импликация $u\to v$. Тогда если граф сильно связный, все эти высказывания эквивалентны. Это показывается аналогично: любой путь по транзитивности импликации даёт нам следствие для любой упорядоченной пары вершин. Теперь задачу 2 можно будет при желании убить этим же зонтиком, раскрыв сначала все данные эквивалентности в пары импликаций.

[beroal]

arseniiv в сообщении #1413885 писал(а):

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

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

[arseniiv]

М-м, такое название частей должно быть более подходящим.

[Sdy]

beroal, спасибо за ответ.
Я решил сам ввести импликацию для этих задач вследствие того, что мне хотелось бы работать с этими заданиями с точки зрения космополита.

beroal в сообщении #1413868 писал(а):

уже дано то, что если $X$ истинно, то $Y$ истинно

Просто ведь это и есть определение импликации на естественном языке. "Если ..., то ...". Так почему бы не воспользоваться вместо русского (английского) языка здесь языком математики, понятным всем?
Я просто не очень понял, почему она вообще идёт отдельным разделом, ведь он фактически использует её в определении конъюнкции, дизъюнкции, только формулируя в виде связки естественного языка.
В принципе, как правильно заметил arseniiv, данный раздел с логикой на данный момент мне нужен для лучшего понимания происходящего в анализе. Просто я начал с аксиоматики Пеано и в соседней теме mihaild указал мне на то что я не понимаю, как работает аксиома подстановки для одной из аксиом Пеано. А Тао на этом моменте отослал в дополнение. Вот и разбираюсь с ним.

[beroal]

Sdy в сообщении #1414012 писал(а):

Я просто не очень понял, почему она вообще идёт отдельным разделом, ведь он фактически использует её в определении конъюнкции, дизъюнкции, только формулируя в виде связки естественного языка.

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

• Проще всего сказать, что логические связки — это слова непонятного языка для создания грамматических конструкций, и дать правила вывода, которые позволяют выводить математические утверждения и косвенно задают смысл логических связок.
• Однако многие авторы идут традиционным путём, то есть доказывают правила вывода из таблиц истинности. Таблицы истинности у Terence Tao описаны на естественном языке. Поскольку таблицы истинности описывают операции на булевом множестве, а операция — это функция, а функция — это математическое понятие, то, чтобы доказать правила вывода, надо уже иметь какую-то часть математики. Так и возникает цикличность определений. Я даже видел книгу, где автор строил основания математики в 2 этажа: сначала неформальная импликация, потом таблицы истинности, потом формальная импликация. По-моему, это извращение.

[Sdy]

Хотел бы уточнить. Несмотря на то что до того как я немного залез в математическую логику неоднократно эти правила мною применялись без каких либо вопросов, как только посмотрел на них формально, немного запутался.
1.Корректность доказательства от противного.
Пусть имеется утверждение, имеющее вид $A \Rightarrow B$. При доказательстве от противного мы предполагаем, что данное утверждение неверно. Но в силу определения импликации утверждение неверно только если $A = 0 \wedge B = 1$. Тогда мы и предполагаем это. Приходим к противоречию, но тогда импликация должна быть верна.
И вот тут у меня заскок. Импликация верна в трёх случаях
1.$A = 0 \wedge B = 0$.
2.$A = 0 \wedge B = 1$.
3.$A = 1 \wedge B = 1$.
Правильно ли я понимаю, что мы отметаем остальные случае кроме третьего в силу того что при доказательстве утверждения нам обычно дано, что $A$ - верно? Ну, там при таких-то $x$ верно то-то. Или из того что сходится, следует то-то. То есть мы предполагаем, что в условиях теоремы $A$ - верно, и тогда остается только третий вариант?

2.Закон контрапозиции.
(Я же правильно понял, что его так и называют используя русский язык? По крайне мере так мне говорит Google. Звучит просто непривычно.)
Необходимо доказать, что $(P \Rightarrow Q) \Leftrightarrow (\sim Q \Rightarrow \sim P)$.
Доказательство.
1.$\Rightarrow$. Если $P \Rightarrow Q$ неверно, то $P = 1 \wedge Q = 0$. Но тогда и $\sim Q \Rightarrow \sim P$ неверно. Если же оно верно, тогда возможны три ситуации:
1.1.$P = 0 \wedge Q = 0$. Но тогда и $\sim Q \Rightarrow \sim P$ верно.
1.2.$P = 1 \wedge Q = 1$.
1.3.$P = 0 \wedge Q = 1$.
В обоих случаях также видно, что в силу определения импликации условие теоремы выполнено.
2.Обратно доказывают точно также.
Таким образом получаю, что закон контрапозиции верен и я могу его использовать в доказательстве утверждений.$\triangle$.
Тут вопросов не возникло, на случай если я заблуждаюсь (в книге об этом было оговорено кратко) привел полное рассуждение.

-- 09.09.2019, 20:52 --

beroal, спасибо за ответ.
Вот таким образом я для себя пока их и определил.

beroal в сообщении #1414015 писал(а):

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

[epros]

Sdy в сообщении #1414233 писал(а):

Правильно ли я понимаю, что мы отметаем остальные случае кроме третьего в силу того что при доказательстве утверждения нам обычно дано, что $A$ - верно?

Как раз при таком доказательстве мы ничего не отметаем. Импликация верна в любом из трёх указанных случаев.

Вы путаете импликацию с логической выводимостью. А в классической логике это разные вещи (и по-моему это - её большая проблема).

Sdy в сообщении #1414233 писал(а):

2.Закон контрапозиции.
(Я же правильно понял, что его так и называют используя русский язык? По крайне мере так мне говорит Google. Звучит просто непривычно.)
Необходимо доказать, что $(P \Rightarrow Q) \Leftrightarrow (\sim Q \Rightarrow \sim P)$.

Я привык называть законом контрапозиции $(P \to Q) \to (\neg Q \to \neg P)$. Потому что это закон не только в классической логике, но и, например, в конструктивной. Обратное: $(\neg Q \to \neg P) \to (P \to Q)$ - в конструктивной логике не всегда верно, а потому так не называется.

Sdy в сообщении #1414233 писал(а):

Доказательство.

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

Доказательства такого рода нужны тогда, когда у Вас есть какие-то аксиомы, из которых двузначность логики отнюдь не очевидна.

[beroal]

Sdy в сообщении #1414233 писал(а):

Правильно ли я понимаю, что мы отметаем остальные случае кроме третьего в силу того что при доказательстве утверждения нам обычно дано, что $A$ - верно?

Если я правильно понял, вы с помощью доказательства от противного хотите доказать импликацию. Тогда любой из этих трёх вариантов может быть истинен. Какая разница какой? Если ваши $A$ и $B$ содержат индивидную переменную $x$, то какой вариант истинен может даже зависеть от значения $x$.

epros в сообщении #1414248 писал(а):

Если Вы уж решились опираться на двузначность логики, то зачем эти пляски с бубнами?

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

[arseniiv]

Про доказательство от противного: тут изложена какая-то частная схема, и в общем случае мы доказываем не импликацию (и потому наверно выходит странный результат из трёх альтернатив, когда ожидалась одна), а произвольное $A$, и для этого предполагаем, что оно неверно, что-то отсюда выводим и приходим к противоречию. Чтобы обосновать этот способ через истинностные значения, надо показать, что если из $\neg A$ логически следует противоречие, то $A$ тождественно истинно, то есть что если при $\neg A = 1$ всегда ложное утверждение ${} = 1$ (никогда), то $A = 1$. То есть если из $A = 0$ мы получили невозможное, $A = 1$ — и это вполне очевидно из двузначности логики.

Более общая схема, работающая и в конструктивных случаях — из $A\to\bot$ (где $\bot$ — противоречие) получить $\neg A$ (тогда из $\neg A\to\bot$ мы получим $\neg\neg A$, классически эквивалентное $A$), и часто $A\to\bot$ просто принимается за определение $\neg A$.

[beroal]

arseniiv в сообщении #1414286 писал(а):

Чтобы обосновать этот способ через истинностные значения, надо показать, что если из $\neg A$ логически следует противоречие, то $A$ тождественно истинно, то есть что если при $\neg A = 1$ всегда ложное утверждение ${} = 1$ (никогда), то $A = 1$. То есть если из $A = 0$ мы получили невозможное, $A = 1$ — и это вполне очевидно из двузначности логики.

Я бы сказал так. Допустим, мы доказали $\lnot A\implies 0$. Это может быть истинным, только если $\lnot A=0$. Следовательно, $A=1$.

[epros]

arseniiv в сообщении #1414286 писал(а):

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

Вообще не увидел там какой-то схемы. По-моему, просто рассмотрели значения истинности импликации при всех четырёх комбинациях значений аргументов и убедились, что она истинна в трёх случаях. Все прочие слова (в том числе, про доказательство от противного) лишние.