2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Полная система связок?
Сообщение18.01.2017, 20:13 


03/06/12
2745
Здравствуйте! В книге Верещагин, Шень Языки и исчисления, на стр. 21 есть такое место:
Изображение
что-то я не пойму, они там утверждают полноту системы связок, состоящей из одной связки $\operatorname{notand}$ или что?

 Профиль  
                  
 
 Re: Полная система связок?
Сообщение18.01.2017, 20:17 


11/08/16

312
Sinoid в сообщении #1185707 писал(а):
утверждают полноту системы связок, состоящей из одной связки
Да. Из операции 'штрих Шеффера'.

 Профиль  
                  
 
 Re: Полная система связок?
Сообщение20.01.2017, 20:01 


03/06/12
2745
Это получается, $(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)$, верно?

 Профиль  
                  
 
 Re: Полная система связок?
Сообщение20.01.2017, 20:35 


11/08/16

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

 Профиль  
                  
 
 Re: Полная система связок?
Сообщение20.01.2017, 20:39 
Заслуженный участник


27/04/09
28128
Кстати, можно аксиоматизировать логику высказываний одной аксиомой $$(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 ищется, но мне лень читать, она ещё всё-таки и древняя.

 Профиль  
                  
 
 Re: Полная система связок?
Сообщение20.01.2017, 20:49 


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

 Профиль  
                  
 
 Re: Полная система связок?
Сообщение20.01.2017, 20:55 


11/08/16

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

 Профиль  
                  
 
 Re: Полная система связок?
Сообщение20.01.2017, 21:00 
Заслуженный участник


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

(Оффтоп)

knizhnik в сообщении #1186223 писал(а):
Все - тавтологии, в исчислении высказываний нетавтологий нет.
?? $P$.

 Профиль  
                  
 
 Re: Полная система связок?
Сообщение20.01.2017, 21:17 


11/08/16

312

(Оффтоп)

arseniiv в сообщении #1186224 писал(а):
Если же мы рассматриваем аксиоматическую теорию, и добавили связку $\mid$, то да, никак существенно иначе, чем добавить формулу вида $a\mid b\leftrightarrow\ldots$, не сделать.
arseniiv в сообщении #1186224 писал(а):
knizhnik в сообщении #1186223 писал(а):
Все - тавтологии, в исчислении высказываний нетавтологий нет.
?? $P$
Если же мы рассматриваем аксиоматическую теорию, то никаких $P$ не может быть ни в виде аксиом, ни в виде теорем. Могут быть только тавтологии. Все остальное в лучшем случае принадлежит языку ИВ, но язык ИВ - не ИВ.

 Профиль  
                  
 
 Re: Полная система связок?
Сообщение20.01.2017, 21:28 
Заслуженный участник


27/04/09
28128

(Оффтоп)

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

 Профиль  
                  
 
 Re: Полная система связок?
Сообщение21.01.2017, 19:43 


03/06/12
2745
Что-то вы все заговорили такими словами... Слушайте, я еще до вас не дорос, давайте попробуем изъясняться более простыми словами. Вот как в этой книге определяется связка $\leftrightarrow$:
Изображение
т.е. связка $\leftrightarrow$ сама по себе не является тавтологией, эта связка лишь может входить в тавтологию, а может и входить не в тавтологию. Но в случае теоремы на рисунке даны формулы и словом оговорено, что эти формулы являются тавтологией и все ясно. А вот, например, на стр. 20 есть такое место:
Изображение
что я тут вижу? Я здесь вижу формулу со связкой $\leftrightarrow$, но нигде не оговорено, что эта формула есть тавтология. Если следовать букве учебника, то эта запись означает $((p\rightarrow q)\rightarrow(\neg p\vee q))\wedge((\neg p\vee q)\rightarrow(p\rightarrow q))$, но не то, что эта формула является тавтологией. Так а что тогда проверять?

 Профиль  
                  
 
 Re: Полная система связок?
Сообщение21.01.2017, 21:59 
Заслуженный участник


27/04/09
28128
Sinoid в сообщении #1186376 писал(а):
т.е. связка $\leftrightarrow$ сама по себе не является тавтологией
так как это связка, а не формула, и потому не может быть тавтологией, как и не тавтологией. :-)

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

 Профиль  
                  
 
 Re: Полная система связок?
Сообщение22.01.2017, 18:50 


03/06/12
2745
arseniiv в сообщении #1186408 писал(а):
«А тавтология (что то же самое, что А является логическим следствием пустого множества формул)».

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

 Профиль  
                  
 
 Re: Полная система связок?
Сообщение23.01.2017, 21:23 
Супермодератор
Аватара пользователя


20/11/12
5728
 i  Мнение knizhnik о соотношении математики и CS выделено в отдельную тему

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 14 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Vladimir Pliassov


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group