Логики 0, 1 и 2 порядков.

[tolstopuz]

Vladimir Pliassov в сообщении #1728103 писал(а):

иначе не было бы исчисления (синтаксическое понятие) высказываний (семантическое понятие).

Ну вот, цитату вы наконец-то прочитали, а учебник - нет. И опять начали фантазировать.

Vladimir Pliassov в сообщении #1728103 писал(а):

И в выражении "формула высказывания"

Нет такого выражения.

[Vladimir Pliassov]

tolstopuz в сообщении #1727949 писал(а):

mihaild в сообщении #1727948 писал(а):

А это теорема о полноте

Да, это фактически часть доказательства теоремы о полноте. И эта часть полностью закрывает вопрос ТС.

Вчера понял, что Вы сказали!

Я, оказывается, пытался доказать теорему Гёделя! Вот ее формулировки, которые я нашел.

Любая семантически тавтологичная (общезначимая) формула классического исчисления высказываний является синтаксически доказуемой (выводимой из аксиом),

и наоборот:

Любая синтаксически непротиворечивая теория (множество формул) имеет модель.

Не знаю, удовлетворительны ли эти формулировки, но смысл, по-моему, ясен.

Теперь мне не надо ее доказывать, но я хотел бы обратить на нее внимание изучающих логику: как я полагаю,

истинность высказывания можно понимать как то, что соответствующая ему формула выводима, а ложность как то, что выводимо отрицание соответствующей ему формулы

(Это еще одна, пока что последняя формулировка, учитывая замечание

tolstopuz в сообщении #1728124 писал(а):

Vladimir Pliassov в сообщении #1728103 писал(а):

И в выражении "формула высказывания"

Нет такого выражения.

)

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

[mihaild]

Vladimir Pliassov в сообщении #1728194 писал(а):

истинность высказывания можно понимать как то, что соответствующая ему формула выводима, а ложность как то, что выводимо отрицание соответствующей ему формулы

Нет, нельзя. Во-первых, что еще такое "формула, соответствующая высказыванию"? И что вообще такое "высказывание"?
Для примера, определение формулы (из любого стандартного учебника): 1) переменная - это формула; 2) если $\phi$ и $\psi$ - формулы, то $(\phi \wedge \psi)$, $(\phi \vee \psi)$, $(\neg \phi)$, $(\phi \rightarrow \psi)$ - формулы; 3) множество формул - минимальное множество, удовлетворяющее свойствам 1 и 2 [тут надо доказать, что такое существует, но это легко].
Во-вторых, то, что множества общезначимых и выводимых формул совпадают - это нетривиальная теорема (даже две). Существование этой теоремы - не повод смешивать два в общем случае разных понятия. Более того, такое смешение сделает формулирование этих теорем невозможным.

В названии темы почему-то есть упоминание логики 2го порядка; вот там никакого аналога теоремы о полноте нет, а есть обратное утверждение - любая эффективная (т.е. проверяемая алгоритмически) система вывода в логике 2го порядка неполна в стандартной семантике.

[dgwuqtj]

Vladimir Pliassov в сообщении #1728194 писал(а):

импликация "из того, что сахар сладкий, следует, что дважды два пять" (при определенных условиях) может называться истинной

Так эта импликация как раз ложная.

[Vladimir Pliassov]

mihaild в сообщении #1728195 писал(а):

В названии темы почему-то есть упоминание логики 2го порядка; вот там никакого аналога теоремы о полноте нет, а есть обратное утверждение - любая эффективная (т.е. проверяемая алгоритмически) система вывода в логике 2го порядка неполна в стандартной семантике.

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

Как я понял, для логики 2-го порядка теорема Гёделя о полноте не выполняется. Но выполняется ли она для логики нулевого порядка?

dgwuqtj в сообщении #1728197 писал(а):

Vladimir Pliassov в сообщении #1728194 писал(а):

импликация "из того, что сахар сладкий, следует, что дважды два пять" (при определенных условиях) может называться истинной

Так эта импликация как раз ложная.

Я написал: "(при определенных условиях)" , здесь я имел в виду, например, пару условий "сахар не сладкий"$=\top$ и $(2\times 2\not=5)=\top$ (но есть еще две пары условий, при которых эта импликация истинна).

[mihaild]

Vladimir Pliassov в сообщении #1728206 писал(а):

Но выполняется ли она для логики нулевого порядка?

Это название, хотя, вроде бы, и употребляется, но довольно нестандартное. Обычно говорят "исчисление высказываний".
Полнота - это свойство пары объектов: рассматриваемого класса моделей, и дедуктивной системы. Классическое исчисление высказываний (с аксиомами Гильберта и modus ponens) полно относительно классических же моделей (приписывающих каждой переменной значение $\top$ или $\bot$).

(Оффтоп)

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

[Vladimir Pliassov]

mihaild в сообщении #1728476 писал(а):

Полнота - это свойство пары объектов: рассматриваемого класса моделей, и дедуктивной системы. Классическое исчисление высказываний (с аксиомами Гильберта и modus ponens) полно относительно классических же моделей (приписывающих каждой переменной значение $\top$ или $\bot$).

Стараюсь разобраться в этом. Выкладываю свой опыт знакомства с синтаксисом (в оформлении которого мне помог ИИ). Ваши задания надеюсь выполнить немного позже.

Попытка конструктивного обоснования законов де Моргана $\neg (P \land Q)\vdash \neg P \lor \neg Q$ и $\neg (P \lor Q)\vdash \neg P \land \neg Q$

(в отличие от неконструктивных доказательств Генцена и Гильберта)

На чем основана попытка? В качестве метатеоретического фундамента мы принимаем наши базовые интуитивные представления о союзах "и", "или", "если ... , то ...". Эти представления необходимы здесь как инструмент конструирования правил оперирования символами и содержательного размышления о них.

Базовые синтаксические допущения (Аксиоматика):

1). Ограничение сигнатуры (алфавита): Мы работаем в строго замкнутой системе, состоящей из двух атомарных высказываний $A, B$ и их отрицаний $\neg A, \neg B$. Появление любых посторонних переменных исключено.

2). Правило исключённого третьего для выбора: Любой элемент алфавита или их синтаксическая комбинация в рамках некоторого рассуждения может быть либо «выбран» (включён в контур рассуждения), либо «не выбран» (исключён из него). Третьего состояния не существует.

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

4). Определение конъюнкции ($\land$): Синтаксическая сборка, требующая обязательного одновременного выбора обоих входящих в неё операндов.

5). Определение нестрогой дизъюнкции ($\lor $): Синтаксическая сборка, означающая выбор хотя бы одного из входящих в неё операндов (первого, второго или обоих вместе).

6). Определение строгой дизъюнкции ($\oplus $): Операция, предписывающая выбор строго одного из указанных компонентов при обязательном исключении остальных.

Поставим задачей составить непротиворечивый набор условий для некоторого рассуждения.

1.

Вывод нестрогой дизъюнкции из отрицания конъюнкции

Пусть нам даны высказывания $A, B$ и их отрицания $\neg A, \neg B$. Составим из них четыре возможные конъюнкции:

1) $\neg A\wedge \neg B$,

2) $\neg A\wedge B$,

3) $A\wedge \neg B$,

4) $A\wedge B$.

Построим наше обоснование на выборе или не выборе высказываний из этого множества.

Поскольку любые две из наших конъюнкций синтаксически противоречат друг другу (то есть их совместный выбор требовал бы одновременного выбора некоторого элемента сигнатуры и его отрицания, что запрещено правилом 3).), в рамках одного рассуждения мы можем выбрать только какую-то одну из них, например, $A\wedge \neg B$. Отказ от её выбора (что на верхнем уровне синтаксиса является посылкой рассуждения и записывается как отрицание всей конъюнкции) математически эквивалентен переходу к строгой дизъюнкции трех оставшихся вариантов:

$$(A\wedge \neg B)\oplus [(\neg A\wedge \neg B)\oplus (\neg A\wedge B)\oplus (A\wedge B)]$$

Пусть мы не выбрали конъюнкцию $A\wedge \neg B$. Тогда мы должны выбрать одну из конъюнкций $(\neg A\wedge \neg B), (\neg A\wedge B), (A\wedge B)$.

Проведем анализ структуры этих оставшихся вариантов:

Если выбор падет на $\neg A\wedge \neg B$, мы гарантированно выбираем входящий в его состав операнд $\neg A$. Если выбор падет на $A\wedge B$, мы гарантированно выбираем входящий в его состав операнд $B$. Если выбор падет на $\neg A\wedge B$, мы выбираем как $\neg A$, так и $B$ вместе.

Таким образом, синтаксический выбор одной из этих трех конъюнкций в любом возможном исходе гарантирует нам выбор либо $\neg A$, либо $B$, либо их совместной комбинации. Согласно нашему базовому определению, такая структура тождественно записывается как нестрогая дизъюнкция $\neg A\vee B$.

Что же касается отрицаний $\neg A$ и $B$, то есть высказываний $A$ и $\neg B$, то о них нельзя сказать того же: в составе конъюнкции $\neg A\wedge B$ нет ни $A$, ни$\neg B$.

Таким образом, на основе комбинаторного анализа общих элементов нами конструктивно обоснована выводимость $\neg (A\land \neg B)\vdash \neg A\lor B$. Подставив по стандартному правилу синтаксической подстановки метапеременную $P$ вместо $\neg A$ (откуда $A \equiv \neg P$) и метапеременную $Q$ вместо $B$, мы получаем первый закон де Моргана в его классическом виде:

$$\neg (P\land Q)\vdash \neg P\lor \neg Q$$

2.

Вывод конъюнкции из отрицания дизъюнкции

Теперь из имеющихся в нашей замкнутой системе четырех высказываний $A, B$ и их отрицаний $\neg A, \neg B$ составим полный базис из четырех возможных дизъюнкций:

1) $\neg A\vee \neg B$,

2) $\neg A\vee B$,

3) $A\vee \neg B$,

4) $A\vee B$.

Поставим задачу составить условия для нового рассуждения. Откажемся от выбора (положим отрицание на верхнем уровне синтаксиса) одной из этих дизъюнкций, например, дизъюнкции 2) ($\neg A\vee B$), тогда в рамках нашей модели мы синтаксически обязаны выбрать остальные три дизъюнкции одновременно. То есть наша посылка $\neg(\neg A\vee B)$ эквивалентна требованию консенсуса (совместного выполнения) дизъюнкций 1), 3) и 4).

Теперь запустим процедуру синтаксического поиска такой конъюнкции, которая была бы одновременно "согласна" с каждой из этих трех выбранных дизъюнкций (то есть была бы структурно совместима и не противоречила ни одной из этих дизъюнкций)). Чтобы быть "согласной" с дизъюнкцией 1) ($\neg A\vee \neg B$), искомая конъюнкция должна содержать в себе либо $\neg A$, либо $\neg B$. Чтобы быть "согласной" с дизъюнкцией 3) ($A\vee \neg B$), она должна содержать в себе либо $A$, либо $\neg B$. Чтобы быть "согласной" с дизъюнкцией 4) ($A\vee B$), она должна содержать в себе либо $A$, либо $B$.

Пропустим все четыре конъюнкции нашей модели через этот тройной синтаксический фильтр. Единственной конъюнкцией, которая удовлетворяет требованиям всех трех дизъюнкций одновременно, является $A\wedge \neg B$. В самом деле, дизъюнкция 1) "согласна" с ней за счет операнда $\neg B$. Дизъюнкция 3) согласна с ней за счет обоих операндов $A$ и $\neg B$. Дизъюнкция 4) "согласна" с ней за счет операнда $A$.

При этом в нашей системе нет больше ни одной конъюнкции, с которой были бы одновременно "согласны" все эти три дизъюнкции. Мы получили строгое, взаимно-однозначное соответствие.

Таким образом, методом синтаксического консенсуса нами конструктивно обоснована формула: $\neg (\neg A\lor B)\vdash A\land \neg B$. Применяя к полученной структуре то же стандартное правило синтаксической подстановки (заменяя $\neg A$ на метапеременную $P$, а $B$ на метапеременную $Q$), мы окончательно выводим второй закон де Моргана в его классическом виде:

$$\neg (P\lor Q)\vdash \neg P\land \neg Q$$

[mihaild]

Vladimir Pliassov в сообщении #1728711 писал(а):

Выкладываю свой опыт знакомства с синтаксисом

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

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

Vladimir Pliassov в сообщении #1728711 писал(а):

Попытка конструктивного обоснования законов де Моргана $\neg (P \land Q)\vdash \neg P \lor \neg Q$ и $\neg (P \lor Q)\vdash \neg P \land \neg Q$

Vladimir Pliassov в сообщении #1728711 писал(а):

Мы работаем в строго замкнутой системе, состоящей из двух атомарных высказываний $A, B$ и их отрицаний $\neg A, \neg B$. Появление любых посторонних переменных исключено.

И дальше можно не читать, потому что в том, что Вы пытаетесь доказать, есть другие переменные.

[Vladimir Pliassov]

mihaild в сообщении #1728717 писал(а):

И дальше можно не читать, потому что в том, что Вы пытаетесь доказать, есть другие переменные.

Какие другие переменные? Разве их не две?

[mihaild]

Vladimir Pliassov в сообщении #1728724 писал(а):

Какие другие переменные?

Vladimir Pliassov в сообщении #1728711 писал(а):

$\neg (P \land Q)\vdash \neg P \lor \neg Q$

Вижу тут $P$ и $Q$, не вижу $A$ и $B$.
Ну и я бы сказал, что законы де Моргана - логические, $\neg (A \wedge B) \rightarrow (\neg A \vee \neg B)$. А что это означает, что $\neg (A \wedge B) \vdash \neg A \vee \neg B$ - получается по теореме о дедукции, её нет смысла доказывать для каждой импликации отдельно.

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

[tolstopuz]

Vladimir Pliassov в сообщении #1728711 писал(а):

$$(A\wedge \neg B)\oplus [(\neg A\wedge \neg B)\oplus (\neg A\wedge B)\oplus (A\wedge B)]$$

Попробуйте посчитать $\top \oplus [\top \oplus \top \oplus \bot]$.

[Vladimir Pliassov]

tolstopuz в сообщении #1728761 писал(а):

Попробуйте посчитать $\top \oplus [\top \oplus \top \oplus \bot]$.

$$\top \oplus [\top \oplus \top \oplus \bot]\equiv \top \oplus [\top \oplus (\top \oplus \bot)]\equiv \top \oplus [\top \oplus (\top)]\equiv \top \oplus [\top \oplus \top]\equiv \top \oplus [\bot]\equiv \top \oplus \bot\equiv \top $$

.
Но в моем рассуждении ложной полагается первая конъюнкция тавтологии

$$(A\wedge \neg B)\oplus [(\neg A\wedge \neg B)\oplus (\neg A\wedge B)\oplus (A\wedge B)]$$

и на этом оно строится: пусть первая конъюнкция ложная, тогда одна из остальных (из тех, которые в квадратных скобках) истинная, и независимо от того, какая из них истинная, дизъюнкция $\neg A\vee B$ истинная.

Таким образом,

(семантически:) из ложности конъюнкции $A\wedge \neg B$ следует истинность дизъюнкции $\neg A\vee B$, --

другими словами,

(синтаксически:) из отрицания конъюнкции $A\wedge \neg B$ выводится дизъюнкция $\neg A\vee B$:

$$\neg (A\wedge \neg B)\vdash \neg A\vee B$$

[tolstopuz]

Vladimir Pliassov в сообщении #1728806 писал(а):

и на этом оно строится: пусть первая конъюнкция ложная, тогда одна из остальных (из тех, которые в квадратных скобках) истинная, и независимо от того, какая из них истинная, дизъюнкция $\neg A\vee B$ истинная.

Тогда попробуйте посчитать $\bot \oplus [\top \oplus \top \oplus \top]$.

-- добавлено через 14 минут --

Vladimir Pliassov в сообщении #1728711 писал(а):

на основе комбинаторного анализа общих элементов нами конструктивно обоснована выводимость $\neg (A\land \neg B)\vdash \neg A\lor B$.

Что такое выводимость?

[Vladimir Pliassov]

mihaild в сообщении #1728726 писал(а):

Вижу тут $P$ и $Q$, не вижу $A$ и $B$.

$A$ и $B$ это переменные ( буквы объектного языка), а $P$ и $Q$ --метапеременные (буквы метаязыка).

mihaild в сообщении #1728726 писал(а):

Ну и я бы сказал, что законы де Моргана - логические, $\neg (A \wedge B) \rightarrow (\neg A \vee \neg B)$. А что это означает, что $\neg (A \wedge B) \vdash \neg A \vee \neg B$ - получается по теореме о дедукции, её нет смысла доказывать для каждой импликации отдельно.

Да, конечно, но это интересно и, по-моему, очень полезно.

(Оффтоп)

mihaild в сообщении #1728726 писал(а):

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

Я не претендую на Ваши ответы, хотя очень их ценю и всегда ценил.

Не знаю, помните ли Вы, но несколько лет назад я писал, что иду своим путем и буду благодарен, если мне помогут на этом пути. Вы настоятельно рекомендуете мне читать учебники, однако я так устроен, что мне легче дойти самому, чем понять из учебника. Когда я начинаю читать учебник, то почти сразу же натыкаюсь на что-то непонятное и прежде чем идти дальше, стараюсь понять. Недавно я написал, что читаю "Логику" Клини, и это была правда. Но как только я дошел до закона Пирса $((P\to Q)\to P)\to P$, то стал думать, как его можно вывести, на том чтение и кончилось.

Можно посмотреть и так, что мне надо сначала подготовиться к чтению учебника, а потом уже читать, понимая, о чем идет речь.

tolstopuz в сообщении #1728903 писал(а):

Тогда попробуйте посчитать $\bot \oplus [\top \oplus \top \oplus \top]$.

Результат будет тот же -- $\top$, потому что

$$(A\wedge \neg B)\oplus [(\neg A\wedge \neg B)\oplus (\neg A\wedge B)\oplus (A\wedge B)]$$

это тавтология.

tolstopuz в сообщении #1728903 писал(а):

Что такое выводимость?

Цитата:

Если существует вывод данной формулы $B$ из $A_1, \cdots , A_m$, то говорим, что $B$ выводима из $A_1, \cdots , A_m$, и пишем $A_1, \cdots , A_m\vdash B$.
"Логика" Клини http://lib.ysu.am/open_books/258082.pdf, стр.50

[tolstopuz]

Vladimir Pliassov в сообщении #1729003 писал(а):

tolstopuz в сообщении #1728903 писал(а):

Тогда попробуйте посчитать $\bot \oplus [\top \oplus \top \oplus \top]$.

Результат будет тот же -- $\top$,

И как же это согласуется с вашим предыдущим

Vladimir Pliassov в сообщении #1728711 писал(а):

6). Определение строгой дизъюнкции ($\oplus $): Операция, предписывающая выбор строго одного из указанных компонентов при обязательном исключении остальных.

Vladimir Pliassov в сообщении #1729003 писал(а):

tolstopuz в сообщении #1728903 писал(а):

Что такое выводимость?

Если существует вывод данной формулы

И что же такое вывод?