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

[creative]

Джеймс Андерсон в своей книге "Дискретная математика и комбинаторика" (ISBN 5-8459-0498-6) в разделе 1.4. (Аксиоматические системы: умозаключения и доказательства) на странице 36 пишет:

Цитата:

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

Далее на странице 38 этого же раздела приводит пример:

Цитата:

Рассмотрим умозаключение:

$(p \rightarrow q \wedge q \rightarrow r) \rightarrow p \vee r$

Если заключение ложно, то и $p$ и $r$ — оба ложны. Однако, если $q$ ложно, то $p \rightarrow q$ и $q \rightarrow r$ — оба истинны. Поскольку обе посылки истинны, а заключение ложно, то умозаключение неправильно.

Тут он применил доказательство от обратного, о оно (reductio ad absurdum) в свою очередь является правилом вывода.

Таким образом он доказал ложность умозаключения используя правила вывода, хотя перед этим он сказал, что правила вывода не позволяют доказать ложность умозаключения.

P.S. Может я напутал, так как он постоянно употребляет слова утверждения и умозаключения и я мог смешать их смысл. На форуме ссылку постить нельзя, поэтому достаточно набрать ISBN книги и на сайте вильямс (или просто скачать где-нибудь эту книжку) можно найти отрывок из книги, где содержатся именно эти страницы.

[maxmatem]

Цитата:

о оно (reductio ad absurdum) в свою очередь является правилом вывода.

А с чего вы это взяли? это у него в книге написано?

[creative]

maxmatem в сообщении #389572 писал(а):

А с чего вы это взяли? это у него в книге написано?

Да, правила вывода перечислены на 41 странице, среди них reductio ad absurdum. И ещё в вики написано, что это правило вывода.

[Chifu]

creative писал(а):

$(p \rightarrow q \wedge q \rightarrow r) \rightarrow p \vee r$
Если заключение ложно, то и $p$ и $r$ — оба ложны. Однако, если $q$ ложно, то $p \rightarrow q$ и $q \rightarrow r$ — оба истинны. Поскольку обе посылки истинны, а заключение ложно, то умозаключение неправильно.

По-моему: если p, q, r ложно, то утверждение ложно, во всех остальных случаях истинно - это и есть исчерпывание таблицы истинности.

[creative]

Chifu в сообщении #389662 писал(а):

creative писал(а):

$(p \rightarrow q \wedge q \rightarrow r) \rightarrow p \vee r$
Если заключение ложно, то и $p$ и $r$ — оба ложны. Однако, если $q$ ложно, то $p \rightarrow q$ и $q \rightarrow r$ — оба истинны. Поскольку обе посылки истинны, а заключение ложно, то умозаключение неправильно.

По-моему: если $p, q, r$ ложно, то утверждение ложно, во всех остальных случаях истинно - это и есть исчерпывание таблицы истинности.

Предпложение, что умозаключение ложно, а в данном случае оно ложно тогда и только тогда, когда $p$ и $r$ ложны относится к использованию правила вывода reductio ad absurdum . А выбор из двух вариантов истинности или ложности $q$ это уже использование таблицы истинности в каком-то смысле (хотя не уверен).

Предположим, что из-за перебора $q$ (истинно или ложно) можно считать, что мы используем таблицу истинности, но ответ на главный вопрос (в названии темы) остается невыясненным.

Хочется видеть прямое доказательство для всех случаев, что правила вывода не позволяют доказать ложность умозаключения.

[Chifu]

creative писал(а):

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

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

[Chifu]

Chifu в сообщении #389696 писал(а):

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

Посмотрел я книжку, на стр. 36 имеется ввиду, что используя правила вывода мы стремимся исчерпать таблицу истинности (или только ту часть, которая нас интересует), можно сразу построить таблицу истинности, но она громоздкая, а рассуждения типа стр. 38 позволяют исследовать выборки из таблицы истинности и исследовать структуру таблицы истинности (или только той части, которая нас интересует), что иногда бывает проще построения таблицы истинности. Логический вывод не протипоставляется таблице истинности, а являются разной записью одного и того же. Естесственно, что исчерпывающим логическим выводом можно доказать истинность или ложность утверждения, но для этого может понадобиться цепочка рассуждений. Метод таблицы истинности один и тот же для всех утверждений, а общего метода для построения исчерпывающего логического вывода только той части таблицы истинности которая нас интересует, нет, есть общий метод исчерпывающего логического вывода, но он тоже громоздкий.
PS: Я не преподаватель логики, препод может короче и безошибочнее объяснить.

[arseniiv]

А разве нельзя доказать вместо ложности $A$ истинность $\neg A$?

[Chifu]

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

А разве нельзя доказать вместо ложности $A$ истинность $\neg A$?

Я оказывается про другое думал когда отвечал, мне переформулировать надо. :)

[creative]

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

[Chifu]

creative в сообщении #389796 писал(а):

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

Чтобы понять, вам надо внимательно прочитать, а то вы берёте предложение со стр. 36, пропускаете пример на стр. 37, где объясняется, почему так. А потом берёте пример на стр. 38, который объясняет другое предложение и говорите, что не понимаете о чём речь.
Правила вывода - это фактически правила переписывания, вы уверены, что в любом случае переписывая утверждение вы сможете доказать правильность умозаключения, по-моему в логике даже есть специальная теорема, что могут существовать такие теоремы которые нельзя доказать логическим выводом? А таблица истинности даёт исчерпывающую информацию для заключения об истинности или ложности умозаключения. И для истинности предложения на стр. 36 достаточно, чтобы нельзя было доказать ложность некоторых умозаключений, а не вообще всех, если бы так было, то зачем тогда нужны правила вывода.
Пример на стр стр. 38 простой и приведён для иллюстрации "метода, альтернативного методу таблицы истинности", т.е. он должен показать альтернативность метода методу таблицы истинности.

[Maslov]

creative в сообщении #389563 писал(а):

Джеймс Андерсон в своей книге "Дискретная математика и комбинаторика" (ISBN 5-8459-0498-6) в разделе 1.4. (Аксиоматические системы: умозаключения и доказательства) на странице 36 пишет:

Цитата:
Однако, при помощи таблиц истинности мы можем доказать ложность утверждения, чего правила вывода сделать не позволяют.

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

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

Chifu в сообщении #390023 писал(а):

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

В формальной арифметике действительно есть истинные невыводимые формулы, но к исчислению высказываний это не относится.
Исчисление высказываний полно: формула $F$ выводима в формализованном исчислении высказываний тогда и только тогда, когда она является тавтологией алгебры высказываний ($\vdash F \Leftrightarrow ~\models F$).

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

А разве нельзя доказать вместо ложности $A$ истинность $\neg A$?

В общем случае, нельзя. Исчисление высказываний не является абсолютно полным, т. е. существуют формулы $F$ такие, что ни $F$, ни $ \lnot F$ не являются теоремами исчисления высказываний.

[arseniiv]

Maslov в сообщении #390121 писал(а):

В общем случае, нельзя. Исчисление высказываний не является абсолютно полным, т. е. существуют формулы $F$ такие, что ни $F$, ни $ \lnot F$ не являются теоремами исчисления высказываний.

А я думал, тут под ложностью понималось то, что формула — противоречие.

[Chifu]

Maslov писал(а):

Скорее всего, имеется в виду, что с помощью таблиц истинности можно показать, что высказывание не является ни тавтологией, ни противоречием. Формальным выводом это сделать в общем случае невозможно.
Исчисление высказываний полно: формула $F$ выводима в формализованном исчислении высказываний тогда и только тогда, когда она является тавтологией алгебры высказываний ($\vdash F \Leftrightarrow ~\models F$).

Спасибо. Можно ли назвать таблицу истинности металогическим методом?

[Maslov]

Chifu в сообщении #390173 писал(а):

Можно ли назвать таблицу истинности металогическим методом?

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