Простые вопросы и задачи по логике

[epros]

caxap в сообщении #408210 писал(а):

а в чём разница? Например, конкретно между $A\to\text{\bf Л}$ и $A\to\perp$? Разве оба не равны $\neg A$?

Если $\text{\bf Л}$ - константа (пропозициональная) - как Вы утверждали выше, то ни в чём. Просто в языке теории может не быть пропозициональных констант. Например, в языке арифметики Пеано нельзя записать $0=1 \leftrightarrow \text{\bf Л}$ , а вот $\neg 0=1$ - записать можно.

caxap в сообщении #408210 писал(а):

В Верещагине--Шене пишут, например, $\neg (A\land B)\leftrightarrow \neg A\lor \neg B$. Но (лично мне) логичней кажется писать $=$, т.к. в той же книжке пишется, что $\neg,\land,...$ -- это просто функции типа $\mathbb B^k\to \mathbb B$.

Как у Шеня - правильно, а со знаком $=$ - неправильно. Ещё раз: символ $=$ ставится между термами теории. Например, в арифметике Пеано: $(1 + 0) \times (1 + 1) = 1 + 1$. А $\neg (A\land B)$ и $\neg A\lor \neg B$ - это не термы, а формулы.

caxap в сообщении #408210 писал(а):

Есть символ эквивалентности "внутри" формулы, то есть функция $\leftrigtharrow : \mathbb B^2\to\mathbb B$. А есть "внешний" символ, когда мы говорим, что формула такая-то равна такой-то (в смысле, если подставить вместо $A,B,...$ любые булевые переменные (правда, ложь) и выполнить все указанные функции в формулах, то мы слева и справа получим одно и то же булевое значение (правда или ложь).

Не улавливаю тонких различий смысла. Если мы говорим, что $\leftrightarrow$ - это бинарная функция $\mathbb B^2\to\mathbb B$ (такая, что она равна "истина" тогда и только тогда, когда аргументы равны), то утверждение $A \leftrightarrow B$ как раз и означает, что "мы получим слева и справа одно и то же булево значение" (какие бы значения переменных мы ни подставили в формулы $A$ и $B$).

[caxap]

Проверьте, пожалуйста.

9. Легко понять, что любая формула, составленная только с помощью связок $\land$ и $\lor$, задаёт монотонную булеву функцию (в том смысле, что от увеличения значения любого из аргументов значение функции может только возрасти или остаться прежним). Покажите, что любая монотонная булева функция может быть выражена формулой, содержащей только $\land$ и $\lor$.

(Маленький вопрос)

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

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

Первую часть (которую "легко понять") я доказал по индукции.
Лемма. Функции $\land$ и $\lor$ неубывающие (проверить можно в лоб).
База индукции. $(p\land q)$ и $(p\lor q)$, где $p,q$ -- пропозициональные переменные, задают неубывающие функции (по лемме).
Индукционный шаг. Из известных формул $A,B$ (задающих неубывающие функции) можно получить новые $(A\land B)$ или $(A\lor B)$. Пусть мы меняем аргумент, входящий в $A$ с нуля на единицу, тогда $A$ может либо не измениться, либо стать единицей. По лемме вся формула может только возрасти.

В обратную сторону. Пусть существует неуб. функция $f$, не выражающаяся через $\land,\lor$. Напишем её ДНФ. По предположению, в ней есть переменная $p$, входящая с отрицанием. Пусть она входит в конъюнкт $K$. Существует такой набор $P=(p_1,...,p_n)$ значений переменных, что $f(P)=1$, причём это значение полностью определяется конъюнктом $K=1$, т. е. все остальные конъюнкты равны нулю.

Иначе зачем бы тогда $K$ был нужен? Если при любом наборе значений переменных $K$ равен единице, только если есть другой конъюнкт, равный единице, то можно было бы убрать $K$ из ДНФ -- функция бы осталась та же. Предположим, мы убрали все такие лишние конъюнкты и опять нашли $K$, в котором некоторая переменная (пусть $p$) входит с отрицанием (если такого конъюнкта нет, то функция выражается через $\land,\lor$).

Возьмём этот набор $P$ и увеличим $p$ (с нуля на единицу), тогда $\neg p$, весь конъюнкт $K$ и вся функция $f$ станут равными нулю. Итого: мы увеличили значение переменной, а функция уменьшилась.

[caxap]

10. Пусть $\varphi\to\psi$ -- тавтология. Покажите, что найдётся формула $\tau$, которая включает в себя только общие для $\varphi$ и $\psi$ переменные, для которой формулы $(\varphi\to\tau)$ и $(\tau\to\psi)$ являются тавтологиями.

Тут я даже не знаю, с чего начать

По задаче 9: А как быть с константными функциями (обоими)? Если имеется НЕ, то можно $0=p\land \neg p$, $1=p\lor \neg p$. А без отрицания не выходит ничего придумать...

Применив моё доказательство к $p\lor \neg p$ нашёл ошибку:

caxap в сообщении #431857 писал(а):

Возьмём этот набор $P$ и увеличим $p$ (с нуля на единицу), тогда $\neg p$, весь конъюнкт $K$ и вся функция $f$ станут равными нулю. Итого: мы увеличили значение переменной, а функция уменьшилась.

Вся функция стать нулю не обязана. Спутал ДНФ с КНФ.

-- 06 апр 2011, 21:04 --

Так. Пусть функцию $f(p_1,...,p_n)\equiv 0$ можно выразить через $\land,\lor$. Но $\land,\lor$ сохраняют единицу, т. е. $f(1,...,1)=1$. Противоречие. Аналогично доказываем невыразимость $f(p_1,...,p_n)\equiv 1$ (при $p_i=0$ она обязана быть нулём).

Предположим, авторы в "любую монотонную функцию" константы не включили. А вообще утверждение задачи верно (обратное которое)? Может я зря мучаюсь?

[Xaositect]

caxap в сообщении #431857 писал(а):

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

Эта терминология широко применяется при изучении упорядоченных множеств: там говорят о монотонных (неубывающих) и антимонотонных (невозрастающих) функциях.

caxap в сообщении #431857 писал(а):

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

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

Про константы вы правильно заметили. $[\vee,\wedge] = M_{01}$, т.е. константы получить нельзя. Откуда у Вас эта задача? Мб там формула определяется так, что любая константа - формула.

Если не брать константы, то ваша идея сработает, но ИМХО Вам для этого все-таки придется определять совершенную ДНФ для функции. Легче явно построить эту ДНФ на основе множества "нижних единиц" - таких наборов, что функция равна на нем 1, а на всех меньших - 0. каждой нижней единице соответствует конъюнкция без отрицаний, равная 1 на этом наборе и всех бОльших.

[caxap]

Xaositect в сообщении #431977 писал(а):

$[\vee,\wedge] = M_{01}$

А что такое $M_{01}$?

Xaositect в сообщении #431977 писал(а):

Линейные функции в зарубежной литературе чаще называют аффинными.

А это название откуда появилось? (Что, нельзя было просто новое слово придумать?)

Xaositect в сообщении #431977 писал(а):

Откуда у Вас эта задача?

Верещагин, Шень "Языки и исчисления". (Вообще, я изначально хотел изучать логику по Колмогорову--Драгалину, но осилил только начало.)

Xaositect в сообщении #431977 писал(а):

Если не брать константы, то ваша идея сработает

Но я же просто в конце спутал ДНФ с КНФ. Если мы сделаем конъюнкт $K$ равным нулю, то вся функция может не изменится, а может даже возрасти.
Вторую часть вашего абзаца я не очень понял. Попробую сейчас переварить...

[Xaositect]

caxap в сообщении #432106 писал(а):

А это название откуда появилось? (Что, нельзя было просто новое слово придумать?)

А это совершенно логичное название. Это аффинное преобразование над конечным полем $GF(2)$

-- Чт апр 07, 2011 15:27:48 --

caxap в сообщении #432106 писал(а):

А что такое $M_{01}$?

$M_{01}$ - класс всех монотонных функций, сохраняющих $0$ и $1$: $f(0,\dots,0) = 0$ и $f(1,\dots,1) = 1$.

-- Чт апр 07, 2011 15:34:27 --

caxap в сообщении #432106 писал(а):

Верещагин, Шень "Языки и исчисления". (Вообще, я изначально хотел изучать логику по Колмогорову--Драгалину, но осилил только начало.)

Ну значит Верещагин и Шень немного ошиблись.

[caxap]

Про метод с "нижними единицами" так и не понял, точнее -- как построить из них ДНФ. Пусть $\{P_i\}$ -- множество нижних единиц монотонной функции $f:\mathbb B^n\to\mathbb B$. Каждой н. е. $P=(p_1,...,p_n)$, у которой только $p_{k_1},...,p_{k_m}$ равны единицам, соответствует один конъюнкт $p_{k_1} p_{k_2} ... p_{k_m}$. Дизъюнкция конъюнктов от всех $P_i$ даст некоторую формулу. А вдруг в этой формуле есть другие конъюнкты, не связанные с н. е.?

(Оффтоп)

А можно как-нибудь от противного доказать (как у меня было)? Т. е. предположим, что ДНФ монотонной функции содержит отрицание. Пусть это $\neg p$ в конъюнкте $K$. Можно попытаться найти такой набор, в котором $p=0$ и на котором функция равна единице, причём эта единица определяется только $K$ (остальные конъюнкты нулевые). Увеличиваем $p$ и получаем противоречие с монотонностью (главное, чтобы остальные конъюнкты не увеличились от этого).

(Детский вопрос)

Для доказательства теорем (в частности, теорем из мат. логики) используется мат. логика. Замкнутого круга нигде не получается?

[Xaositect]

caxap в сообщении #432197 писал(а):

Дизъюнкция конъюнктов от всех $P_i$ даст некоторую формулу. А вдруг в этой формуле есть другие конъюнкты, не связанные с н. е.?

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

caxap в сообщении #432197 писал(а):

А можно как-нибудь от противного доказать (как у меня было)?

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

-- Чт апр 07, 2011 20:20:53 --

caxap в сообщении #432197 писал(а):

Для доказательства теорем (в частности, теорем из мат. логики) используется мат. логика. Замкнутого круга нигде не получается?

До теоремы Гёделя доберетесь - вернитесь к этому вопросу. Точнее, придется разобраться с ним по пути к теореме Гёделя.