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

[caxap]

13а (Верещагин--Шень, Языки и исчисления). Покажите, что можно построить схему размера $O(2^m)$ c $2^m$ выходами, реализующую все $2^m$ возможных конъюнктов длины $m$ (для каждого -- свой выход).

(Пояснения)

Под схемой понимается некоторая "электрическая" схема из логических элементов, составляющих базис (напр. $\neg,\lor,\land$) и реализующая некоторую функцию $\mathbb B^n\to\mathbb B^m, \mathbb B=\{0,1\}$. Размер схемы -- число элементов в ней.

В указании сказано, что такую схему можно построить индуктивно. А можно без индукции? Вот так: при $m=2$ требуется 2 "НЕ" и 4 "И" ("И" стоят на выходах, а две "НЕ" нужны для получения отрицаний входных сигналов $p,q$: мы будем иметь сигналы $p,q,\neg p,\neg q$, из которых конъюнкциями построим все 4 выхода). Аналогично можно построить и для любого $m$: будет $m$ "НЕ" и $2^m$ "И". Но $m+2^m=O(2^m)$, напр. $m+2^m\leq 2\cdot 2^m$, $\forall m\ge 2$.

Вопрос. Почему Modus Ponens является не аксиомой, а правилом вывода? Почему нельзя просто добавить аксиому $A\land (A\to B)\to B$?

[Maslov]

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

Вопрос. Почему Modus Ponens является не аксиомой, а правилом вывода? Почему нельзя просто добавить аксиому $A\land (A\to B)\to B$?

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

[Xaositect]

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

13а (Верещагин--Шень, Языки и исчисления). Покажите, что можно построить схему размера $O(2^m)$ c $2^m$ выходами, реализующую все $2^m$ возможных конъюнктов длины $m$ (для каждого -- свой выход).

(Пояснения)

Под схемой понимается некоторая "электрическая" схема из логических элементов, составляющих базис (напр. $\neg,\lor,\land$) и реализующая некоторую функцию $\mathbb B^n\to\mathbb B^m, \mathbb B=\{0,1\}$. Размер схемы -- число элементов в ней.

В указании сказано, что такую схему можно построить индуктивно. А можно без индукции? Вот так: при $m=2$ требуется 2 "НЕ" и 4 "И" ("И" стоят на выходах, а две "НЕ" нужны для получения отрицаний входных сигналов $p,q$: мы будем иметь сигналы $p,q,\neg p,\neg q$, из которых конъюнкциями построим все 4 выхода). Аналогично можно построить и для любого $m$: будет $m$ "НЕ" и $2^m$ "И". Но $m+2^m=O(2^m)$, напр. $m+2^m\leq 2\cdot 2^m$, $\forall m\ge 2$.

Ну если тупо считать, то получится не $2^m$ конъюнкций, а $(m-1)2^m$. Тут существенно как раз то, что схема имеет структуру дерева.

Цитата:

Вопрос. Почему Modus Ponens является не аксиомой, а правилом вывода? Почему нельзя просто добавить аксиому $A\land (A\to B)\to B$?

Потому что тогда у нас не будет правил вывода, а значит, кроме аксиом вообще теорем не будет.

[caxap]

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

Если нет правила вывода, то нет и возможности перейти от двух формул к третьей.

Понял. Извиняюсь за глупый вопрос.

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

Ну если тупо считать, то получится не $2^m$ конъюнкций, а $(m-1)2^m$

Тут не понял. Пусть $m=2$, каждый вход $p,q$ разветвляем на два провода, один из которых пускаем через отрицание. Получаем сигналы $p,q,\neg p,\neg q$. На выходах (их 4) ставим конъюнкции, к которым подаём сигналы $(p,q)$, $(p,\neg q)$, $(\neg p, q)$, $(\neg p,\neg q)$. Получили то, что требуется. Размер схемы -- $2+4=6$.
При $m=3$ полностью аналогично: разветвляем каждый вход $p_i$, получаем сигналы $p_i,\neg p_i$, на каждом из $2^m=8$ выходах ставим конъюнкцию и на каждую конъюнкцию подаём уникальную тройку сигналов.
В общем случае также получаем размер схемы $m+2^m=O(2^m),~\forall m\ge 2$.

[Xaositect]

У конъюнкции два входа

[caxap]

Ой, я туплю Размер у такой схемы получается $m+(m-1)2^m\neq O(2^m)$ (чтобы реализовать $m$-входовую конъюнкцию, требуется $m-1$ двухвходовых).

Тогда индуктивно: пусть $s_m$ -- размер схемы при $m$ входах. Тогда $s_2=6$, $s_m=s_{m-1}+2^{m+1}+1$ ($m$-й вход раздваиваем и одна ветвь идёт через отрицание; чтобы скомбинировать со схемой для $(m-1)$ потребуется ещё $2\cdot 2^m$ конъюнкций), откуда $s_m=2^{m+2}+m-12=O(2^m),\ \forall m\ge 2$. Так?

[cyb12]

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

Тогда индуктивно: пусть $s_m$ -- размер схемы при $m$ входах. Тогда $s_2=6$, $s_m=s_{m-1}+2^{m+1}+1$ ($m$-й вход раздваиваем и одна ветвь идёт через отрицание; чтобы скомбинировать со схемой для $(m-1)$ потребуется ещё $2\cdot 2^m$ конъюнкций), откуда $s_m=2^{m+2}+m-12=O(2^m),\ \forall m\ge 2$. Так?

Так

Кстати, при $m\to \infty$ схемная сложность такой системы асимптотически есть $2^m$ (без константы) . Соответствующая схема строится из двух схем для системы всех конъюнкций порядка $\frac n2$ от первой и второй половины переменных, которые строятся по совершенной ДНФ, а затем все пары выходов из разных схем конъюнктируются. При этом сложность такой схемы не больше, чем $2^n+O(n\cdot 2^{n/2}).$

[caxap]

Спасибо.

[caxap]

В Верещагине--Шене в разделе про интуиционистскую логику употребляется символ $\perp$ как заведомо ложное утверждение (тогда, например $\neg A$ эквивалентно $A\to \perp$). А в чём тогда разница между ложью {\bf Л} и $\perp$? (Я так понимаю, $\neg A=A\to\text{\bf Л}$ тоже верно.)

P. S. Как отделять "внешние" символы эквивалентности и следования (когда мы пишем, например, что такая-то формула эквивалентна такой-то) и "внутренние" (которые в самих формулах). Выше я написал $\neg A=A\to\text{\bf Л}$, употребив $=$ -- так можно? (То есть результат применения функции $\neg$ к $A$ такой же, как $\to$ к $A$ и $\text{\bf Л}$. Но нигде не видел, чтобы псиали равно: пишут $\equiv$, $\sim$,... смысла и разницы я не уловил...)

И вообще, в чём разница между $=$ и $\leftrightarrow$?

[Xaositect]

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

В Верещагине--Шене в разделе про интуиционистскую логику употребляется символ $\perp$ как заведомо ложное утверждение (тогда, например $\neg A$ эквивалентно $A\to \perp$). А в чём тогда разница между ложью {\bf Л} и $\perp$? (Я так понимаю, $\neg A=A\to\text{\bf Л}$ тоже верно.)

$\perp$ - это синтаксический элемент, буква. $\text{\bf Л}$ - это объект семантический, истинностное значение.

Цитата:

P. S. Как отделять "внешние" символы эквивалентности и следования (когда мы пишем, например, что такая-то формула эквивалентна такой-то) и "внутренние" (которые в самих формулах). Выше я написал $\neg A=A\to\text{\bf Л}$, употребив $=$ -- так можно? (То есть результат применения функции $\neg$ к $A$ такой же, как $\to$ к $A$ и $\text{\bf Л}$. Но нигде не видел, чтобы псиали равно: пишут $\equiv$, $\sim$,... смысла и разницы я не уловил...)

И вообще, в чём разница между $=$ и $\leftrightarrow$?

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

[epros]

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

В Верещагине--Шене в разделе про интуиционистскую логику употребляется символ $\perp$ как заведомо ложное утверждение (тогда, например $\neg A$ эквивалентно $A\to \perp$). А в чём тогда разница между ложью {\bf Л} и $\perp$? (Я так понимаю, $\neg A=A\to\text{\bf Л}$ тоже верно.)

А что такое {\bf Л}? Пропозициональная переменная? Символ $\perp$ обозначает пропозициональную константу. Семантически, $\perp$ соответствует утверждению, ложному независимо ни от какого контекста и условий задачи, а вот просто "ложное" утверждение может оказаться истинным в другом контексте. Например, утверждение $\exists n ~ 2 \times n = 1$ ложно в контексте арифметики натуральных чисел, но истинно в контексе арифметики рациональных чисел.

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

P. S. Как отделять "внешние" символы эквивалентности и следования (когда мы пишем, например, что такая-то формула эквивалентна такой-то) и "внутренние" (которые в самих формулах).

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

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

И вообще, в чём разница между $=$ и $\leftrightarrow$?

Символ $=$ обычно обозначает стандартное бинарное отношение эквиваленции, т.е. он ставится между термами теории. А символ $\leftrightarrow$ - это логическая связка, означающая то же самое, что конъюнкция между двумя импликациями, т.е. он ставится уже между двумя формулами теории.

[caxap]

$\text{\bf Л}$ -- это константа, "ложь". Булево множество $\mathbb B=\{\text{правда},\text{ложь}\}=:\{\text{\bf П},\text{\bf Л}\}$.

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

- это синтаксический элемент, буква. - это объект семантический, истинностное значение.

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

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

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

Не можете кратко рассказать про них?

----
Вот как мне записать, что $\neg A$ -- то же, что $A\to\perp$? Равно (равенство значений двух функций)? $\leftrightarrow$ (тогда и только того, когда)? Или левые символы типа $\equiv$, $\sim$,...

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

-- 02 фев 2011, 14:50 --

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

Что его нет в алфавите той теории, об эквивалентности формул которой мы говорим? Дык, значит он есть в алфавите другой теории - той, в рамках которой мы говорим об эквивалентности формул первой теории.

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

-- 02 фев 2011, 15:05 --

Функция $\leftrightarrow: \mathbb B^2\to\mathbb B$ равна истине, если оба аргумента равны. С отношением $=$ тоже естественным образом связана функция, которая равна истине, если оба аргумента равны (только эти аргументы уже не обязаны принадлежать $\mathbb B$, $4=4$ тоже истина). Вот я и спрашивал: в чём тогда разница между $A\leftrightarrow B$ и $A = B$, если $A,B\in\mathbb B$?

[Xaositect]

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

Так вот, $\perp$ - это символ, пропозициональная константа, а $\textbf{Л}$ - это элемент множества $\mathbb{B}$ истинностных значений, которое используется для классической интерпретации формул как логических функций. Со связками тут путаница, потому что они в тексте обозначают как семантические объекты - функторы, так и семантические - функции.
Можно сказать, что на семантическом уровне формуле $A\to \perp$ соотвествует функция алгебры логики $N(A) = A\to\textbf{Л}$. И тут опять надо заметить, что в формуле $A$ - это просто символ, а в функции это аргумент, пробегающий множество $\mathbb{B}$.
Сначала это может показаться ненужным дублированием и усложнением, но потом становится понятно, почему это удобно. Теорему Геделя без понимания этого разделения понять невозможно, ИМХО. Да и уже в интуиционизме понятие интерпретации отличается от классического. Там формуле $A\to \perp$ будет соответствовать не булева функция, а функция, зависящая от шкалы Крипке и заданного значения $A$ на этой шкале.

[caxap]

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

Сначала это может показаться ненужным дублированием и усложнением

Так и кажется. Ладно, буду надеяться на просветление рано или поздно.

Спасибо за ответы.

[Xaositect]

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

Не можете кратко рассказать про них?

У нас есть алфавит, в котором есть переменные, константы, связки и скобки. Среди связок у нас есть одна, которая называется эквиваленцией, и которой на семантическом уровне соответствует функция $E(A,B) = \begin{cases}1,A=B\\0,A\neq B\end{cases}$. Это эквивалентность равенства на множестве $\mathbb{B}$ и ее синтаксическое отражение.
А еще у нас есть множество формул, на котором нам хочется ввести отношения эквивалентности. Собственно, зачем мы изучаем логику? Мы хотим знать, какие формулы и утверждения следуют из других и какие равносильны. Вот это понятие равносильности опять же можно вводить на двух уровнях и в них уже есть существенное отличие.
Первое понятие - это семантическая эквивалентность, которая означает, что формулы в любой интерпретации имеют одинаковое значение.
Второе понятие - это дедуктивная эквивалентность, которая означает, что одну формулу можно привести к другой путем некоторых вполне определенных манипуляций с символами.
Так вот, логическая теория - это попытка выразить первое, семантическое понятие эквивалентности с помощью второго, т.е. с помощью простых манипуляций с символами. И если в исчислении высказываний тут все хорошо, то, допустим, эквивалентность на стандартной модели арифметики никакой теорией, которую можно записать конечным количеством символов без ссылки на эту самую стандартную модель, не описывается.