Главная » Просмотр файлов » Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике

Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 5

Файл №1055357 Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике) 5 страницаГ.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357) страница 52019-04-28СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

3. Формулы. Реализация булевых функций формулами. Пример 9. Локазать, что выражения й« = 1л) — «1(1у3гг и йз = (я Ч (1 у)) — «(я оо 1 у) не являются формулами над множеством логических связок (1, 3о, Ч, — «), но что, добавляя скобки, каждое из этих выражений можно превратить в формулу над указанным множеством связок. Р е ш е н и е. Лля доказательства того, что некоторое выражение й нг явллегпся формулой над каким-то фиксированным множеством Ф (функциональных символов и«или логических связок), достаточно выявить какое-либо свойство, присущее каждой формуле над заданным множеством Ф, но которым не обладает выражение й.

Утверждение о том, что любая формула над множеством Ф обладает выявленным свойством, обосновывается обычно по индукции по «сложности» формул (например, по числу связок или по числу функциональных символов, входящих в формулы). В выражении й« вЂ” — 1 я) — «1(1 у во я нарушено несколько свойств, присущих формулам над множеством (1, йо, Ч, -«): а) обе скобки, содержащиеся в йы не имеют парных им скобок; б) отсутствуют внешние скобки; в) не отделена скобками связка — «от остальных связок. Лобавляя скобки, выражение й«можно превратить, например, в формулу или ((1л) — «(1(1(уйг)))), или ((1 л) — «(1((1 у) 3гг))), или ((1 л) — «((1(1 у)) 3г г)). В выражении йг = (л Ч (1 у)) — «(я Уг1 и) не хватает только двух пар скобок: внешних и отделяющих связку 3о от связки 1.

Формула, соответствующая выражению йз, имеет вид ((л«7(1 у)) -«(я й (1 у))). Лля обоснования того, что оба выражения й«и йз не являются формулами над множеством связок (1, 3г, ~«, — «), достаточно, например, установить справедливость такого утверждения: всякая формула над множеством связок (1, оо, 'я', — «), отличная от формул вида л, у, ...., обладает парой внешних скобок. Показательство этого факта проведем по индукции — — по числу связок 1, ог, Ч, — «в формулах.

Базис индукции. Если в формуле й только одна связка, то с точностью до переименования переменных (с отождествлением) 24 Гас 1. Способы гадания и сводапва 41упкцпй алгебры логики формула й имеот один из следующих видов; й = (з х), й = (х8с у), й = (х Ч у) и й = (х — э у). Следовательно, базис индукции справедлив. Индуктивный шаг. Предположим, что доказываемое утверждение верно для формул, содержащих не более в связок (в > Ц, и установим его истинность для формул с числом связок, равным .в + 1. Имеем или й = ( 1 З), или й = (й 8с с), или й = (З 'о' ь), или й = = (Ж вЂ” > к), причем одна из подформул З или С в формулах трех последних видов может быть (с точностью до переименования переменных) формулой, равной х.

Очевидно, что индуктивный шаг также справедлив. П р и м е р 10. Построив таблицы функций, реализуемых формулами й= Их4у) — г ((уЮ (тчг)) ~ г)) и 'З = Ихчу) (х — э (у® 63 (х бс г)))), выяснить, эквивалентны ли эти формулы. Решение. Принимая во внимание тот факт, что функция т — > у обращается в 0 только на наборе (1, 0), а функция х ). у равна 1 а б л и ц а 1 5 лишь на набоРе (О, 0), мы можем УпРостить пропедуру построения таблипы функции воя(х, у, г), реализуемой формулой й. В самом деле, угя = 0 тогда и только тогда, когда х ).

у = 1 и (у Ю (х М г)) ~ г = О, т.е, когда х=у=О и (Оео(ОЧг)) ~г= = г ) г = г = О. Следовательно, сои = 0 только при х = у = 0 и г = 1 (табл. 1.5). Таблицу функции 1от(х, у, г), реализуемой формулой 21, будем строить шаг за шагом (табл. 1.6). Таблица 1.6 Сравнивая таблицы функций воя и сох, видим, что ря ф уьл. Значит, формулы й и З неэквивалентны.

Пример 11. Используя основные эквивалентности (см. и. 3 после задачи 1.20), установить эквивалентность формул й = (х ). у) э (хг — э Пх ~ (у г)) Ч (х у 9 г))) В = Их -э у) ~ (х ). 1у ))) '1 у Решение. Применяя основные эквивалентности 8,в), 9,а) и 9, б), получаем й = х Ч у Ч хгЧ (х(у г) Ч (ху 9 г)).

Используя затем основные эквивалентности 7,д), 4, а), 8,б) и 8, а), имеем й = (х Ч у) Ч Ч (х Ч у) Ч ((х Ч (у Юг)) Ч ((х ~у)ся Чхуг)). Палее применяем основ- у Д фрикции алгебры логики. Оиерация едвериозиции 25 ные эквивалентности 2, 7,в), 7,д), 1, 3 и 8,а): г« = х «7д 'и' з ««уя Н1«г Ч ' ' хз Ч дз '««хр ж Накопал, воспользовавшись правилом поглощения 5, а), приходим к соотношению й = х 'о' у ««г. Преобразуем теперь к такому же виду и формулу «л«.

Имеем Ж = (х ««д)х Ч уд ««у Ч я (здесь были использованы основные эквивалентности 8, в), 9, а), 9, б) и 4, а)). Па- лее, применяя основные эквивалентности 4, а), 7,.д) и 4, б), получаем З = хр ««' х о дз Ч у ««з. С помощью закона поглощения 5, а) последнее выражение преобразуется к такому: х «7д ««ж Тем самым эквивалент- ность формул Й и З доказана. 1.8. Выяснить., какие из нижеприводимых выражений являются формулами над множеством логических связок 8 = (1, 8е, «7, Ю, -, — «) .

Проверить, можно ли некоторые из приведенных ниже выражений (и какие), не являющиеся формулами над Я, превратить в формулы, добавляя скобки: 1) х — «хц 2) х«7(1у); 3) хб«(йу); 4) (х««д) — «(х~р(1з)): 5) (х е- у); 6) (х 8е) 1 х; 7) (х В (г)): 8) 1(т †« (( 1 х) ух у)); 9) (х у) 1у; 10) ((х — «(1у)) ((хь'(у3ег))вд)); 11) (1х — «у); 12) ((х 8е (1 х)) ' ' (х 9 (х — «х)) Ч (1 х)).

1.9. Выяснить, является ли выражение А формулой над множест- вом Ф. Проверить, можно ли, добавляя скобки, запятые и переменные (не обязательно все эти знаки), превратить некоторые из приведен- ных ниже выражений (и какие) в формулы над соответствующими множествами Ф: )А= цдбб( *И Ф=(7' 2) А =)х(~рцг, Ф = (60~, уб«); 3) А=( 0«(абб( "'(х)В =О" 4) А — уР«( (г«( „) 5(г«(1 д)) ф — (1 у(г) (г) 500) ое) А д<г)(д,«з«(х д уц«(х)) уц«х) ф (уб«д«г« ~,(з«). 6)А= '(Р'(д'(х '(аВ '"(дт ф (0 У«г) дбб 50«др(г«). 7) 4 5(г«(д«(г«(1) дбб(2 д«0«(х))) ф (1 2 д«г«5(г«диац). 8) Ае д (, (.' 5 (, (. д)'В.

ф — (1 д(з) 5(Ц „,(г>) дгР«) 9) А = дрц(И~ «(1 д,~з«(2, х, уц«(х)))), ф — (1 2 уц«д(г> 1,(г« ~р(з«). 10) А = 60«(х, д««г«(х, 1«ц(1))), Ф = (1, (Пг, 50«, дг«г«). 1.10. Выписать все подформулы формулы А над множеством Ф; 1) А = ((х д) — «((1д) — «(хь'я))), Ф = (1., ь, о — «); 2) А = (((х 3е д) де я) 6«((( 1х) 6« у) «7г)), Ф = ( 1, 3е, Ч, В, †«); 3) А = (~г«(д«г«(1, х)., Ь~з«(х, 1, дг«г«(д~г«(х, х)))), Ф (1 2 у«гг «г« 5(з« „,0« ).

[ц(([з«(й~г«(1 ) [з)(1, 0«(1)) <ц( В ф (1 У[з«РЦ 5(г«(1 53) [з)(1 П 53)) символом 51 указаны «пустые» места; 26 Гл, 1. Способы задания и сводапва функиид алгебры логики 3)А=~'Ь'(.— ) й'(хЙ )) =О' ~"' ~") где ~~ ~(П, П) = д~ц(П вЂ” > П) и уг 1(П, П) = Ь~ц(ПЙП) (здесь сим- волом П указаны те «пустые» места, которые характеризуют «ар- ность» соответствующих логических связок). 1.11. Выяснить, сколькими способами можно расставить скобки в выражении А, чтобы всякий раз получалась формула над множеством логических связок 11, Й, ч', 9, -ь, Ц, если: 1)А=1х9д — >х; 2)А=х — >х)х — ьх; 3) А=хддЙ 1х).г; 4) А=1х91у — ь1г; 5) А = 1 1 х .).

1 1 1 р; 6) А = х д 1 д 9 х 9 х 1 х, 1.12. Сложностью формулы над множеством связок Э = (1, Й, 'с, 9,, — ь, ~, Ц назовем число связок в ней. Индукцией по сложности формулы доказать, что в формуле: 1) ненулевой сложности содержится хотя бы одна пара скобок; 2) число левых скобок равно числу правых скобок; 3) нет двух связок, стоящих рядом; 4) нет двух символов переменных, стоящих рядом. 1.13. Индексом связки в формуле назовем разность между числом левых скобок, предшествующих рассматриваемой связке в данной формуле, и числом правых скобок, предшествующих этой связке.

До- казать, что всякая формула ненулевой сложности над множеством Ь (см. предьгцушую задачу): 1) содержит единственную связку индекса 1; 2) единственным образом представляется в каком-нибудь одном из видов (1 ге), (ЙЙЗ), (й Ч З), (Й 9 З), (Й З), .(хь — > З), (Й ~ З), (Й ь Ж), где Й и З --- формулы над множеством 9. 1.14. Рассмотрим бесскобочную (польскую) запись формул над множеством связок 9 = 11, Й, Ч, 9,, — ь, ), Ц: вместо (1 х), (хЙд), (хну), (х 9 у), (х — у), (х — > д), (х ) р), (х « у) будем писать 1х, Й хд, Ч ху, 9 хд, ху.

Характеристики

Тип файла
DJVU-файл
Размер
3,29 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6521
Авторов
на СтудИзбе
302
Средний доход
с одного платного файла
Обучение Подробнее