Полная система связок?

[Sinoid]

Здравствуйте! В книге Верещагин, Шень Языки и исчисления, на стр. 21 есть такое место:

что-то я не пойму, они там утверждают полноту системы связок, состоящей из одной связки $\operatorname{notand}$ или что?

[knizhnik]

Sinoid в сообщении #1185707 писал(а):

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

Да. Из операции 'штрих Шеффера'.

[Sinoid]

Это получается, $(p \operatorname{notand} p) \cong \neg p $, откуда $p \wedge q \cong \neg (p \operatorname{notand} q) \cong (p \operatorname{notand} q) \operatorname{notand} (p \operatorname{notand} q)$, верно?

[knizhnik]

Верно. Вы же понимаете, да? Вы правильно все понимаете.

[arseniiv]

Кстати, можно аксиоматизировать логику высказываний одной аксиомой

$$(A \mid (B\mid C)) \mid ((D \mid (D\mid D)) \mid ((E\mid B) \mid ((A\mid E) \mid (A\mid E))))$$

(Ж. Никод, 1917) ($\mathbin{\mid}\equiv\mathrm{notand}$) (если набрано правильно). Так пока и не понял, как он её получил, и ещё у него правило вывода — не наивно переведённый MP $\frac{A,\; A\mid (B\mid B)}B$, а $\frac{A,\; A\mid (B\mid C)}C$. Не знаю, существует ли подобная единственная (видимо, более длинная) аксиома, если использовать MP.

Вообще та его статья Nicod J. A Reduction in the Number of the Primitive Propositions of Logic ищется, но мне лень читать, она ещё всё-таки и древняя.

[Sinoid]

А вот в книге связка $\operatorname{notand}$ задается эквивалентностью (написано "задаваемую эквивалентностью") они ведь хотели написать "задаваемую тавтологией" ?

[knizhnik]

Все - тавтологии, в исчислении высказываний нетавтологий нет. Но между тем связка задается именно эквиваленцией, то есть с помощью нее. Иногда еще используют знак $\stackrel{def}{\leftrightarrow}$, что означает "эквивалентно по определению".

[arseniiv]

Если $a\mid b$ понимается просто как сокращение, то никаких эквиваленций не нужно, надо просто сказать: «то-то — сокращение этого-то». Если же мы рассматриваем аксиоматическую теорию, и добавили связку $\mid$, то да, никак существенно иначе, чем добавить формулу вида $a\mid b\leftrightarrow\ldots$, не сделать.

(Оффтоп)

knizhnik в сообщении #1186223 писал(а):

Все - тавтологии, в исчислении высказываний нетавтологий нет.

?? $P$.

[knizhnik]

(Оффтоп)

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

Если же мы рассматриваем аксиоматическую теорию, и добавили связку $\mid$, то да, никак существенно иначе, чем добавить формулу вида $a\mid b\leftrightarrow\ldots$, не сделать.

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

knizhnik в сообщении #1186223 писал(а):

Все - тавтологии, в исчислении высказываний нетавтологий нет.

?? $P$

Если же мы рассматриваем аксиоматическую теорию, то никаких $P$ не может быть ни в виде аксиом, ни в виде теорем. Могут быть только тавтологии. Все остальное в лучшем случае принадлежит языку ИВ, но язык ИВ - не ИВ.

[arseniiv]

(Оффтоп)

Действительно, прочитал неаккуратно. Пускай тогда меня смутило словоупотребление «в исчислении высказываний … нет». Если вот «в исчислении высказываний … не выводится» или «среди аксиом исчисления высказываний … нет» — сразу понятно, что имеется в виду, а чего не.

[Sinoid]

Что-то вы все заговорили такими словами... Слушайте, я еще до вас не дорос, давайте попробуем изъясняться более простыми словами. Вот как в этой книге определяется связка $\leftrightarrow$:

т.е. связка $\leftrightarrow$ сама по себе не является тавтологией, эта связка лишь может входить в тавтологию, а может и входить не в тавтологию. Но в случае теоремы на рисунке даны формулы и словом оговорено, что эти формулы являются тавтологией и все ясно. А вот, например, на стр. 20 есть такое место:

что я тут вижу? Я здесь вижу формулу со связкой $\leftrightarrow$, но нигде не оговорено, что эта формула есть тавтология. Если следовать букве учебника, то эта запись означает $((p\rightarrow q)\rightarrow(\neg p\vee q))\wedge((\neg p\vee q)\rightarrow(p\rightarrow q))$, но не то, что эта формула является тавтологией. Так а что тогда проверять?

[arseniiv]

Sinoid в сообщении #1186376 писал(а):

т.е. связка $\leftrightarrow$ сама по себе не является тавтологией

так как это связка, а не формула, и потому не может быть тавтологией, как и не тавтологией.

Sinoid в сообщении #1186376 писал(а):

Так а что тогда проверять?

Всё-таки тут подразумевается, что это тавтология, и что это действительно надо показать. Мы же пишем часто в обычных математических текстах «А» вместо «А является логическим следствием чего-то там в контексте», в том числе «А тавтология (что то же самое, что А является логическим следствием пустого множества формул)».

[Sinoid]

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

«А тавтология (что то же самое, что А является логическим следствием пустого множества формул)».

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

[Deggial]

Мнение knizhnik о соотношении математики и CS выделено в отдельную тему