Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 18
Текст из файла (страница 18)
эых веса, то их сумма ие превышает 9 (кеса предполагаются положительнымн). 1.103. Доказать уткерждение: код с положительными весами ие кювет иметь зес, больший 8. 1.103. Устаназить пракила сложения и умножения для кода с избытком 5. Определить сумму и произведение чисел 87 и 56. 1.104. Выписать таблицы падоз с избытком ат 1 до 15. Убедиться з том, что только коды с вабытком, меньшим 7, удоэлегэорюот требоэаниюе едвистэениости, четности и упорялоченности, а свойству дополнительности удовлетворяет среди последних талька код с набытком 3. 1.105. Устаиоэпть празила сложения и умножения для кода Айкена — Эмери (код с весами (2, 4, 2, 1). Используя эти праэила, найти сумму и произэедешге чисел -401 н 587.
1.106. Устаноэить правила сложения для кода (2, 5, 2, 1). Найти сумму чисел 90 н 73. 1.107, Определить правила сложения для кода (3, 3, 2, 1) и найти сумму чисел 601 н — 670. 1.108. В системе модулей Ф = 2, дт = 3, дэ = 5 некоторое число имеет код з остатках вида 010. Определить юо числа. 1.109. В системе модулей 9~ = 7, дт = 8 заданы числа х и у своими кодами э остатках 31 и 03 соотзетстзюпю. Устанаэить, что больше: х илн у. 1.110.
Записать алгоритм переаодз кодов э остатках з десятичк0ю аапись числа. 1.111. Найтк способ определения анака числа э коде з остатках. 1.113. Найти способ срээиения чисел по зеличнне и коде з остатках. 1.113. Установить крапила деления для кода э остатках. Э 1.12. Еоммеихйрни Официально теория множестз была пужаиана э 1897 г. на Первом международном конгрессе математикоз, иа котором Адамар н Гуркин призели многочнсденные примеры применения этой теории э математическом анализе. Теория множестз явилась основой создания алгебраических систем, цмеюших большое практическое применение прк разработке математического обеспечения ЭВМ. Большой вклад э рааэитне теории алгебраических систем внесли А.И.
Мальцеэ, Г. Бнрпгоф. Особенно бурное рааэнтие получила теория моделей, снгнатура которых обладает свойством симметричности (симметричных моделей). Этот класс моделей к закаляет эф фектиэно рассматрнзать исследуемый обьект как чер. вый ящик. Элементы (конструктиэные или фуиэпиональные) объекта образуют носитель модели, а ее сигнатура апрелеляег нх взаимосвязь. Для оптимального задания моделей этого класса было предложено понятие моераеба (8), спустя три гола оно энозь было "введено" зо Франции н идентнфицироэано термином еа- нерераФ (341.
Алгебраическяе понятия весьма эффектизвы ири проектироэании сложных систем упраэления, ЭВМ, вычислительных систем н сетей ЭВМ, банков данных и пакетоз приклщппех программ. Для углубления знаний по многосоргным множестэам рекомендуем рабаты [11, 12, 14-16, 23, 34). 95 б 2.1. Логика высквзывомиа а=а; (2.5) (2.10) Ш Теблпде 2.1 О 1 1 О (2.Ц (2.2) (2.3) Мзтеметнкз, оперируя со сгрокемн сконх символов, имея дело с формзльпымн истиномп, тем не менее, монет получнть бесконечно конные результаты, стносяшнеся к опнсенпю фнзнческой Вселенной. К.
Персон Глава 2 МАТЕМАТИЧЕСКАЯ ЛОГИКА $ 2.1. Логика высказываний Высказыванием называется повествовательное предложение, о котором можно сказать в данный момент, что оно истинно нли ложно, но не хо и другое одновременно. Истинность или ложность предложения есть истинное значение высказывания. Сопоставим каждому высказыванию переменную, равную 1, если высказывание истинно, и равную О, если оно лолкно.
Если Р и ь) — некоторые высказывания, то можно образовать высказывания оР или Я", "Р и Я", "не Р", введя операции диэьюнкции (Ч), коньюнкции (й) и отприцания ( ). Действия этих операций задаются таблицами истинности (табл. 2.1-2.3), каждой строке которых взаимно однозначно соотвехствуюх набор значений составляющих высказываний и соответствующее значение сосхавного высказывания. Операции дизъюнкцни, конъюнкции и охрицания читаются соответсхвенно как "или", "но и "не". Нриведем основные законы, определяющие зти операции: эакон идемпотентпностпи диэьюнкции и конъюнкции аЧа=а, айа=а; закон коммутпатпивиости диэьюнкции и конъюнкции аЧЬссЬЧа, айЬсзЬйа; закон ассоциативности диэьюнкции и коньюнкции а Ч (ЬЧ с) = (аЧ6)Ч с, ай(Ьйс) = (айб) йс; эакон дистрибутивности конъюнкции отпносителъно диэьюнкции и диэьюнкции опьносипьельно конъюнкции а й (6 Ч с) = а й 6 Ч а й с 1), (2.4а) аЧбйс = (аЧ 6) й(аЧ с); (2.4б) закон двойного отрицани.я эаконы де )ЬУоргана аЧб= айЬ, айЬле аЧЬ; (2.6) эаконы склеивания айбЧайЬ= а, (аЧЬ) й(аЧЬ) = а; (27) эаконы поглощения амайЬ= а, ай(аЧ6) = а; (2.8) законы Персиково а Ч а й Ь = а Ч Ь, а й (а Ч Ь) = а й Ь; (2.9) законы, определяющие действия с констпантами О и 1, аЧО=а, айО=О, аЧ1=1, ай1= а, аЧЮш1, айа= О.
Всякое высказывание, построенное с помощью операций Ч, й,, имеет некоторое истинное значение, зависящее от значений составляющих высказываний. Любое высказывание у может быть задано в виде тпаблицы истинностпи. Если значение высказыва- ния у зависит от п составляющих высказываний яг, хт, ..., к„, то таблица истинности содержит 2" строк.
Составляющее высказы- вание х; будем называть атомарным высказыванием или просто переменной х;, рассматривая при атом сложное высказывание как функцию у ох п переменных. Рзссмотрше, непрнмер, устройсшо, фиксирующее прннятне некоторой ре- золюпнн "комнтетом трех". Кзвдьгй член комитета прн одобрения резолюпнн нзвпмеет свою кнопку; если большинство пленок соглесны, то революция прн- ннмеегся, что фпкснруегся регистрирующим прпбором. Устройство реелнзуег зыскезыкзпне У(зм лз, ле), теблнке нствнностн которого имеет кнд тебл. 2.4. Теблпде 2.4 ') Скобля к пыревеннн о й Ь и о й с не ставим, тзк кок конъюнкдня й кок мультяплнкотнзнея окерздня более стзршея по стношекню к днзъюнккнн (язлшощейся здднтнзной оперзппей) н кнотолняется и керкую очередь.
Гд. 2. Ма«земащическал логика Исчисление высказываний можно построить, используя соохветствующие таблицы истинности. При этом очевидно, что алгебра высказываний изоморфна алгебре Буля (М, Ч, ег, ), элементы носихеля которой принимают значения О или 1, а сигнахура Ч, 8г, обладает свойствами операций дисхрибутивных решеток с дополнениями. Алгебра Буля простейшая в классе булевых алгебр; она являехся двухзлементной булевой алгеброй. Алгебру высказываний и законы, определяющие ее сигнатуру, можно получить, формально рассмотрев предельный случай решеток — двухэлементную решетку, в которой а О 6 = 6 при а ( о.
Эха решехка преобразуется в булеву алгебру, если положихь а = 6, 6 = а. Одним из элементов двухэлеменхной булевой алгебры являехся О, так как булеза алгебра является решеткой с дополнениями, поэтому вторым элементом этой алгебры являехся 1. Согласно теоремам 1.2 и 1.б каждое высказывание и соответствующую ему булеву функцию у(х1, хт, ..., Х„) можно предста« вить в виде дизъюнкцни констнтуент Й хе', где з=1 е; (х;, ту!=1! ].х;, ст; = О. Для рассматриваемого примера у(хз, хз, хз) может быхь предсхавлена в виде ~(хз ! хэ! Хз) = хтхтхз Ч хзУтхз Ч хзхэУ3 Ч хзхтх3 В дальнейшем представление булевой функции у,(хз, хт, .. «х„) в виде дизъюнкцни конституент будем называть совершенной дизьюнкозиеной нормальной формой функции у(Х1, хт,..., х„).
Переменную или ее отрицание будем называть нереичнььк тверезом. Количество первичных термов, которые образуют форму, задающую булеву функцию У(хг, хт, ..., Х„), называется слохсностпью Цу) этой формы. Сложность совершенной ДНФ функции у(хз, хт, хз) голосования равна 12, Уменьшим сложность этой функции, используя основные хождества алгебры Буля. Согласно свойствам идемпотентностн днзъюнкцни имеем у(хз! хт, хз) = УзхтхзЧхзхтхзЧхтхтхзЧхгхэхзЧхгхтхзЧхзхтхз. Используя свойства коммутативносхи, ассоциативности и дистрибутивности, получаем ~(хз! хт, хз) = (хз Ч хт)хтхз Ч (хэ Ч Ут)хтхз Ч (хз Ч Уз)хтхт. Окончательно имеем з (х1! хэ! хз) хтхз Ч хзх3 Ч хзхт — х3(хт Ч х1) Ч хзхт ° 3 2.1.
Логика емсказмеаний В результате получаем сложность Ц() функции у(х хх хз) равную б. Функции у (хт, хт, ..., х„) и Уд(хз, хт, ..., х„) называются роекььми, если на каждом двоичном наборе (стз, оэ,..., о„) уз (о'1, зтт, ..., зт«) = уед(ст1, стт, .. «зт, ). Количество бит (ипату пп)1 — двоичная единица), необходи- мое для задания булевой функции у (хз, хт, ..., х„) в виде хаблицы нсхинности, равно тз 2". Это количества можно уменьшить в и раз, если использовать двумерную таблицу Вейча. Для этого пред- ставим исходное пространство Р„размерности и в виде декартова произведения пространств Р„,, Р размерности яз, тзт соответ- ственно, где я1 + ят = и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
