Начальство вынесло приказ о рабочем воскресенье без предупреждения. Законно ли это? Могу я не выйти на работу?

Нет, это не законно, ни с предупреждением. ни без такового:
Статья 113. Запрещение работы в выходные и нерабочие праздничные дни. Исключительные случаи привлечения работников к работе в выходные и нерабочие праздничные дни
Работа в выходные и нерабочие праздничные дни запрещается, за исключением случаев, предусмотренных настоящим Кодексом.
Привлечение работников к работе в выходные и нерабочие праздничные дни производится с их письменного согласия в случае необходимости выполнения заранее непредвиденных работ, от срочного выполнения которых зависит в дальнейшем нормальная работа организации в целом или ее отдельных структурных подразделений, индивидуального предпринимателя.
Привлечение работников к работе в выходные и нерабочие праздничные дни без их согласия допускается в следующих случаях:
1) для предотвращения катастрофы, производственной аварии либо устранения последствий катастрофы, производственной аварии или стихийного бедствия;
2) для предотвращения несчастных случаев, уничтожения или порчи имущества работодателя, государственного или муниципального имущества;
3) для выполнения работ, необходимость которых обусловлена введением чрезвычайного или военного положения, а также неотложных работ в условиях чрезвычайных обстоятельств, то есть в случае бедствия или угрозы бедствия (пожары, наводнения, голод, землетрясения, эпидемии или эпизоотии) и в иных случаях, ставящих под угрозу жизнь или нормальные жизненные условия всего населения или его части.
Привлечение к работе в выходные и нерабочие праздничные дни творческих работников средств массовой информации, организаций кинематографии, теле- и видеосъемочных коллективов, театров, театральных и концертных организаций, цирков и иных лиц, участвующих в создании и (или) исполнении (экспонировании) произведений, в соответствии с перечнями работ, профессий, должностей этих работников, утверждаемыми Правительством Российской Федерации с учетом мнения Российской трехсторонней комиссии по регулированию социально-трудовых отношений, допускается в порядке, устанавливаемом коллективным договором, локальным нормативным актом, трудовым договором.
(в ред. Федерального закона от 28.02.2008 N 13-ФЗ)
В других случаях привлечение к работе в выходные и нерабочие праздничные дни допускается с письменного согласия работника и с учетом мнения выборного органа первичной профсоюзной организации.
В нерабочие праздничные дни допускается производство работ, приостановка которых невозможна по производственно-техническим условиям (непрерывно действующие организации) , работ, вызываемых необходимостью обслуживания населения, а также неотложных ремонтных и погрузочно-разгрузочных работ.
Привлечение к работе в выходные и нерабочие праздничные дни инвалидов, женщин, имеющих детей в возрасте до трех лет, допускается только при условии, если это не запрещено им по состоянию здоровья в соответствии с медицинским заключением, выданным в порядке, установленном федеральными законами и иными нормативными правовыми актами Российской Федерации. При этом инвалиды, женщины, имеющие детей в возрасте до трех лет, должны быть под роспись ознакомлены со своим правом отказаться от работы в выходной или нерабочий праздничный день.
Привлечение работников к работе в выходные и нерабочие праздничные дни производится по письменному распоряжению работодателя.

По закону должны предупредить минимум за 3 дня. В обычном варианте лучше выйти, либо, если есть особые обстоятельства, озвучить их. А лучше подтвердить документально -оплаченные билеты, заявка в ЗАГС, могла бы подойти справка о беременности, но этот вариант явно не для Вас.

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

конечно можешь!!!! но один раз, потом возможности не будет, у нас не америка вылетишь в один раз! и коллектив не поддержит и не надейся!