2014 dxdy logo

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

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



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


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

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



Начать новую тему Ответить на тему
 
 приоритет логических операций
Сообщение11.06.2014, 12:29 
Аватара пользователя


14/10/13
321
Существует ли более-менее общепринятое соглашение о порядке выполнения исключающего "или" и штриха Шеффера? То есть как надо действовать, например, в формуле $x \oplus y \mid z$ — слева направо или в смысле $x \oplus (y \mid z)$?

 Профиль  
                  
 
 Re: приоритет логических операций
Сообщение11.06.2014, 12:50 
Заслуженный участник
Аватара пользователя


21/12/05
5477
Новосибирск
Сомневаюсь, что он есть, а если и есть, то кто же помнит? Поставьте лучше скобки.

 Профиль  
                  
 
 Re: приоритет логических операций
Сообщение11.06.2014, 12:55 
Аватара пользователя


14/10/13
321
bot в сообщении #874250 писал(а):
Сомневаюсь, что он есть, а если и есть, то кто же помнит? Поставьте лучше скобки.

Я-то поставил бы. Я бы непременно поставил. Беда в том, что мне дали готовую формулу: $(xy\vee x\overline{z}) \oplus x \mid y$, и она мне не нравится. Зачем-то дизъюнкция в скобке, а потом скобки ни одной.

 Профиль  
                  
 
 Re: приоритет логических операций
Сообщение11.06.2014, 13:11 
Заслуженный участник
Аватара пользователя


19/12/10
1539
Обычно полагают, что XOR имеет более низкий приоритет чем штрих Шеффера.
То есть формулу $(xy\vee x\overline{z}) \oplus x \mid y$
Нужно понимать как $(xy\vee x\overline{z}) \oplus (x \mid y)$

 Профиль  
                  
 
 Re: приоритет логических операций
Сообщение11.06.2014, 13:12 
Аватара пользователя


14/10/13
321
whitefox в сообщении #874255 писал(а):
Обычно полагают, что XOR имеет более низкий приоритет чем штрих Шеффера.
То есть формулу $(xy\vee x\overline{z}) \oplus x \mid y$
Нужно понимать как $(xy\vee x\overline{z}) \oplus (x \mid y)$
Ага, спасибо. А где написано это?

 Профиль  
                  
 
 Re: приоритет логических операций
Сообщение11.06.2014, 13:15 
Заслуженный участник
Аватара пользователя


19/12/10
1539
Навскидку не скажу, но именно так понимается эквивалентная формула
$(xy\vee x\overline{z}) \oplus \overline{xy}$

 Профиль  
                  
 
 Re: приоритет логических операций
Сообщение11.06.2014, 14:02 
Заслуженный участник
Аватара пользователя


21/12/05
5477
Новосибирск
А какой предпочтение здесь?

$x | y = \overline{xy}$

$x| y =\overline{x}\vee \overline{y}$

 Профиль  
                  
 
 Re: приоритет логических операций
Сообщение11.06.2014, 14:06 
Аватара пользователя


14/10/13
321
bot в сообщении #874261 писал(а):
А какой предпочтение здесь?

$x | y = \overline{xy}$

$x| y =\overline{x}\vee \overline{y}$

Это к кому вопрос? И смысл вопроса мне как-то не того.

 Профиль  
                  
 
 Re: приоритет логических операций
Сообщение11.06.2014, 14:21 
Заслуженный участник
Аватара пользователя


21/12/05
5477
Новосибирск
Дык, если предпочесть второе, то скобки ставить надо.

 Профиль  
                  
 
 Re: приоритет логических операций
Сообщение11.06.2014, 15:43 
Аватара пользователя


14/10/13
321
bot в сообщении #874263 писал(а):
Дык, если предпочесть второе, то скобки ставить надо.

Эээ, не понял, из чего это следует. Мало ли там что через что выражается.

 Профиль  
                  
 
 Re: приоритет логических операций
Сообщение12.06.2014, 08:14 
Заслуженный участник
Аватара пользователя


19/12/10
1539
bot в сообщении #874261 писал(а):
А какой предпочтение здесь?

$x | y = \overline{xy}$

$x| y =\overline{x}\vee \overline{y}$
Первое.
Это NAND.
В этом случае штрих Шеффера выражается при помощи двух связок,
а во втором — трёх.

popolznev в сообщении #874256 писал(а):
А где написано это?
Вот, например, как Клини в "Математической логике" определяет
приоритеты связок в порядке возрастания (сам Клини говорит об убывании "ранга"):
$\sim,\supset,\&,\vee,\neg$

Обратите внимание, что по Клини дизъюнкция имеет более высокий
приоритет чем конъюнкция (при этом ссылается на Гильберта).
Сейчас более распространён обратный порядок.

В этом перечне нет ни XOR ни штриха Шеффера.
Но так как XOR эквивалентен отрицанию эквиваленции,
а штрих Шеффера эквивалентен отрицанию конъюнкции,
то логично приписать этим связкам те же приоритеты, что и их отрицаниям.

 Профиль  
                  
 
 Re: приоритет логических операций
Сообщение12.06.2014, 16:23 
Заслуженный участник
Аватара пользователя


21/12/05
5477
Новосибирск
whitefox в сообщении #874461 писал(а):
В этом перечне нет ни XOR ни штриха Шеффера.

Ну на нет и суда нет. Стало быть все наши измышлизмы на тему, что логично, а что нелогично, останется пустым трёпом. У каждого своя логика или даже ... две.
whitefox в сообщении #874461 писал(а):
Первое.
Это NAND.
В этом случае штрих Шеффера выражается при помощи двух связок,
а во втором — трёх.

Не убедили. Во втором случае одна операция над переменными под знаками отрицаний. Чем же это хуже? Отрицание как бы и не в счёт ... Имеет право на жизнь такая логика?

Судя по имеющимся скобкам в стартовом сообщении операция XOR выполняется раньше дизъюнкции, во всяком случае автор задачи так полагает, иначе скобок бы не ставил. В таком случае есть разница, ставить или нет скобки в выражении $A\oplus (x\vee y)$

И правильно, что никакого приоритета здесь не установлено.

 Профиль  
                  
 
 Re: приоритет логических операций
Сообщение12.06.2014, 16:51 
Заслуженный участник


23/07/08
7195
Харьков

(Оффтоп)

Цитата:
В АЛГОЛе 60 семнадцать различных операций, и как-то было остроумно замечено, что если вы найдете человека, который сможет вам сказать, старшинство какой из операций $\equiv$ или $\supset$ выше, значит, вы нашли человека, написавшего соответствующую часть компилятора.
(Д.Баррон, Введение в языки программирования)

 Профиль  
                  
 
 Re: приоритет логических операций
Сообщение14.06.2014, 09:59 
Заслуженный участник
Аватара пользователя


19/12/10
1539
bot в сообщении #874617 писал(а):
Ну на нет и суда нет. Стало быть все наши измышлизмы на тему, что логично, а что нелогично, останется пустым трёпом. У каждого своя логика или даже ... две.

Разумеется, расстановка приоритетов относится целиком на совесть автора. И даже в случае конъюнкции и дизъюнкции разные авторы решают этот вопрос по разному. Но, всё же, существует более употребительная и менее употребительная практика. Имхо, приоритет штриха Шеффера над XOR как раз и является более употребительной практикой. Фактически, обратный порядок мне ни разу не встречался, но не берусь утверждать, что его никто не использует.

И, вообще, чтобы формула понималась однозначно лучше приводить её в польской записи. Тогда и необходимость в скобках отпадает, и не нужно заморачиваться с приоритетами.

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

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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