Лингвофорум

Начался семестр, приступил к изучению учебников логики.

Ниче не понятно на самом деле. Какая-то страшная философия, какой глубины даже у нас гуманитариев не наблюдалось ваще. Притом, что курс логики я таки проходил когда-то, хотя и достаточно примитивный, для лингвистов.

Вопрос: что примерно значит конструктивная индукция? Что такое неконструктивная индукция?

Цитата: RawonaMкурс логики я таки проходил когда-то

Ты его тут вроде бы даже вёл...

Цитата: Bhudh от марта 10, 2011, 23:58

Цитироватькурс логики я таки проходил когда-то

Ты его тут вроде бы даже вёл...

Ну начинал. Может вскоре продолжу

Так я не понял, никто тут не знает логику?

А на других языках неужели ничего не нагуглилось?

Да в общем-то не нагуглилось, но вот вы меня подтолкнули погуглить еще и теперь я понял, что просто неправильно понял термин. Не конструктивная, а структурная индукция дэс. А это уже гуглится неплохо

Сохраню тут ссылку на список терминов, чтоб не вляпываться снова.
http://www.cs.huji.ac.il/~udiboker/logic/english_hebrew_lexicon.html

Цитировать(wiki/ru) Структурная_индукция

Структурная индукция — метод доказательства, который используется в математической логике (например, в доказательстве теоремы Лося об ультрапроизведениях, информатике, теории графов, и некоторых других областях математики. Это — обобщение математической индукции. Структурная рекурсия — метод рекурсии, имеющий те же самые отношения к структурной индукции как обычные рекурсии к обычной математической индукции.

Является ли записью этого предожения: Для любого числа между 0 и 1, которое не 0 и не 1, его квадрат меньше него.
?

Цитата: RawonaM от марта 13, 2011, 22:56
Является ли записью этого предожения: Для любого числа между 0 и 1, которое не 0 и не 1, его квадрат меньше него.
?

Это даже нельзя назвать правильно составленной формулой.
Должно быть что-то вроде

Цитата: Gerbarius от марта 13, 2011, 23:37

ЦитироватьЯвляется ли записью этого предожения: Для любого числа между 0 и 1, которое не 0 и не 1, его квадрат меньше него.
?

Это даже нельзя назвать правильно составленной формулой.

Сорри, пропустил х. Надо так:

Что тут неправильно составлено?

Цитата: Gerbarius от марта 13, 2011, 23:37

А зачем вы закрутили? Ведь проще можно:
Да и скобок у вас как-то не хватает...

Цитата: RawonaM от марта 13, 2011, 23:41
А зачем вы закрутили? Ведь проще можно:
Да и скобок у вас как-то не хватает...

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

Цитата: RawonaM от марта 13, 2011, 23:41
Сорри, пропустил х. Надо так:

Что тут неправильно составлено?

Тут записано другое высказывание, причём ложное. Ложность можно показать так. Возьмём . При таком высказывание будет очевидно ложным, но импликация будет истинной, так как ложна её посылка. Импликация будет тем самым ложной, так как её посылка истинна, а заключение ложно.
В общем, означает вовсе не то, что лежит на отрезке и при том не равно ни 0, ни 1 (для этого следовало использовать конъюнкцию), а то, что или не лежит на отрезке , или оно не равно ни 0, ни 1, или и то и другое вместе.

Цитата: Gerbarius от марта 14, 2011, 00:47
Но ведь и вы и в своём первоначальном варианте закрутили будь здоров. 

Это не мой вариант, это задание из книги

Цитата: Gerbarius от марта 14, 2011, 00:47
Насчёт скобок. Все скобки обычно никогда и не пишут. Для восстановления недостающих скобок пользуются некоторыми соглашениями, подобными тем, которые используются при записи обычных арифметических формул. Но, конечно, вы всегда можете выписывать все скобки явно.

А какие общепринятые приоритеты? Импликация первее?

Цитата: Gerbarius от марта 14, 2011, 00:47
Тут записано другое высказывание, причём ложное. Ложность можно показать так. Возьмём . При таком высказывание будет очевидно ложным, но импликация будет истинной, так как ложна её посылка. Импликация будет тем самым ложной, так как её посылка истинна, а заключение ложно.

Действительно. Спасибо, а то мой парсер запутался

Цитата: RawonaM от марта 14, 2011, 08:30
А какие общепринятые приоритеты? Импликация первее?

Попробую объяснить. В следующих примерах под можно понимать любые формулы, заключёные в скобки.
Кванторы и отрицание считаются младше остальных логических связок. То есть, например, означает , а не .
Аналогично, означает , а не .
Дальше идут конъюнкция и дизъюнкция. Потом уже идёт импликация. То есть означает , а не .
У конъюнкции и дизъюнкции обычно также разные приоритеты, но как раз здесь общепринятых соглашений нет. Поэтому в группах, где встречаются и конъюнкции и дизъюнкции скобки как правило ставят. Например, не пишут , а пишут или или .
В группах из нескольких конъюнкций или дизъюнкций скобки обычно не пишут, так как эти операции ассоциативны. То есть, например, вместо или обычно пишут просто .
В группах из нескольких импликаций скобки как правило ставят. То есть явно пишут или , а не .  Последняя запись, кстати, обычно понимается как , но я не уверен, что все без исключения придерживаются именно такого соглашения. Так как импликация неассоциативна, то скобки в таких случаях лучше ставить во избежание возможных недоразумений.

Спасибо.
Плохо это, диалекты в логике. Надо чтобы 100% однозначно было, иначе будет лингвистика.

Цитата: RawonaM от марта 14, 2011, 12:03
Плохо это, диалекты в логике. Надо чтобы 100% однозначно было, иначе будет лингвистика.

Это диалекты не логики, а записи. В самой логике везде подразумеваются скобки, и всё однозначно.
Что касается приоритета конъюнкции и дизъюнкции, то обычно у конъюнкции он больше.
Конъюнкцию кроме "∧ " ещё обозначают как "∙" (умножение), а дизъюнкцию кроме "∨" — как "+" (сложение). И приоритеты у них соответствуют: A∨B∧C = A+B∙C = A+(B∙C) = A∨(B∧C).

Застрял на одном вопросе.

Допустим B — выражение логики пропозиций, записаное в польской нотации.

Заменим каждую атомную пропозицию на -1, бинарный оператор на +1, а оператор отрицания на 0.

Нужно доказать, что B правильная формула iff после замены сумма получается -1 и сумма любых начальных компонентов неотрицательная.

Понятно вообще? Кому-нибудь по зубам?

В одну сторону я могу доказать, это если дана формула и нужно доказать, что эти условия соблюдаются. Делается структурной индукцией.
Вторую сторону нам подсказали, что нужно делать индукцией на длину строки. Так как я с такой индукцией не знаком, даже не представляю, что можно тут поделать.

Индукция по длине строки - это ж обычная математическая (или натуральная) индукция.
Под строкой здесь можно понимать последовательность чисел, получающуюся после замены каждой компоненты формулы на число.
Здесь индукцию можно применить в следующей форме.
1) Доказываем, что свойство верно для строки длины 1.
Так как единственная строка длины 1, которая удовлетворяет заданному условию, состоит из -1, то она соответствует выражению, состоящему из единственного атома, то есть правильной формуле.
2) Допустим, что свойство верно для всех строк длины , где . Покажем, что оно верно и для строк длины . Рассмотрим какую-нибудь строку длины , которая удовлетворяет условию. Здесь возможны три случая в зависимости от числа, которое стоит на первом месте.
а) На первом месте стоит -1. Строка не удовлетворяет условию, что сумма любых начальных элементов неотрицательна. Таким образом этот случай невозможен.
б) На первом месте стоит 0. Тогда, как можно заметить, остаток строки удовлетворяет заданному условию. А значит по индуктивному предположению он соответствует некоторой правильной формуле . Тогда вся строка соответствует выражению , то есть также правильной формуле.
в) На первом месте стоит +1. Будем считать суммы начальных отрезков. Как можно заметить из того, что сумма всех элементов равна -1, и из того, что начальный элемент равен +1, одна из "промежуточных сумм" должна быть равна 0. То есть всю строку можно представить в виде , где . Далее можно заметить, что обе подстроки и удовлетворяют заданному условию, а значит, по индуктивному предположению соответствуют некоторым правильным формулам и . соответствует некоторой бинарной связке . Таким образом вся строка соответствует выражению вида , то есть также правильной формуле.
Это завершает доказательство.

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

Спасибо, Gerbarius! Я тут уже начал кое что строить, ваша помощь очень существенна. Сейчас попробую вникнуть.

Цитата: Gerbarius от марта 20, 2011, 16:00
По-русски всё-таки обычно говорят о логике или исчислении высказываний . Вместо атомных пропозиций лучше говорить атомарное высказывание или просто атом.

Спасибо, буду знать

Да... Жениаль. Я бы до завтра до этого вряд ли дошел скорее всего. Благодарю!

Все-таки рекурсия интересная штука.

Пытаюсь разобраться в дебрях логических символов...

В чем разница между и ?

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

Эти утверждения не эквивалентны?

Нашел объяснение тут:

(wiki/en) Entailment#Syntactic_consequence

ЦитироватьSyntactic consequence

A formula A is a syntactic consequence[3][4][5][6] within some formal system FS of a set Г of formulas if there is a formal proof in FS of A from the set Г.

   

Syntactic consequence does not depend on any interpretation of the formal system.[7]

Semantic consequence

A formula A is a semantic consequence of a set of statements Г

   

if and only if no interpretation makes all members of Г true and A false.[8] Or, in other words, the set of the interpretations that make all members of Г true is a subset of the set of the interpretations that make A true.

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

(wiki/en) Propositional_logic#Soundness_and_completeness_of_the_rules

ЦитироватьSoundness
    If the set of wffs S syntactically entails wff , then S semantically entails
Completeness
    If the set of wffs S semantically entails wff , then S syntactically entails

Получается, что система sound and complete (как это по-русски) iff


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

Хм...

Например:

Верно или нет?

Ведь синтаксически следует же!

Но никак не:

Ибо нет и одной такой модели.

Равонам, ну так отношения и задаются совершенно по-разному и независимо друг от друга. С чего бы им вдруг быть автоматически эквивалетными? Эквивалентность, конечно, может иметь место для какой-то конкретной формальной системы, для которой задана какая-то конкретная интерпретация. Но эту эквивалетность в любом случае нужно доказывать.

Цитата: RawonaM от апреля  2, 2011, 12:41
Таким образом нет разницы между и в обычной логике высказываний. Правильно?

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

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

Цитата: RawonaM от апреля  2, 2011, 13:17
Хм...

Например:

Верно или нет?

Ведь синтаксически следует же!

Это так.

Цитата: RawonaM от апреля  2, 2011, 13:17
Но никак не:

Ибо нет и одной такой модели.

А вот здесь вы не правы, поскольку формула принимает значение истина при всех значениях p, когда принимает значение истина, тривиальным образом, так как формула тождественно ложна.