Горбатов В.А. Фундаментальные Основы Дискретной Математики. Информационная Математика

Подождите немного. Документ загружается.

§1.11. Задачи и упражнения

1.73. Установить зависимость между дополнительным и обратным кодами

числа х в системе с натуральным основанием 5 и естественным множеством

цифр.

1.74. Записать в полулогарифмической форме в двоичной системе счисле

ния с цифрами О, 1 следующие числа: 75.5; —0.25; 0.125; —1000. По условию

мантисса должна быть нормализованной.

1.75. Установить, для каких чисел х (х ие предполагается меиыпим еди

ницы) дополнительный код этих чисел совпадает с записью самого числа. Ана

логично, для обратного кода (по предположению х < 0).

1.76. Перевести дополнительный кодб. 1124 вобычную запись. Аналогичная

задача для обратного кода 7.770045.

1.77. Найти сумму двух чисел 0.1101 и 0.0010 в двоичной системе с цифрами

0,1, построив предварительно правила сложения в одном разряде. Порядки чисел

одинаковы.

1.78. Найти произведение чисел 0,3302 и 0,1102 в четверичной системе с

естественным множеством цифр. Предварительно построить таблицу умножения

для этой системы.

1.79. Найти сумму и произведение чисел 0.210ДД0 и 0.000009 в системе

счисления с S = 11 и естественным множеством цифр: 0, 1, 2, ..9, Д, где ко

личественный эквивалент пифры Д равен 10. Условная запись пифры с количе

ственным эквивалентом 10 есть Д. Предварительно построить таблицы сложения

и умножения в одиннадцатиричной системе счисления.

1.80. Используя дополнительный код, иайти в двоичной системе с цифрами

0, 1 сумму чисел 0.1101 и —0.1000. Результат суммирования перевести в обыч

ную запись.

1.81. Используя обратный код, иайти в троичной системе с цифрами 0, 1, 2

сумму чисел 0.2210 и —0.1122. Результат перевести в обычную запись.

1.82. Найти сумму чисел —0.0011 и 0.1001 в обратном коде в двоичной си

стеме счисления с цифрами 0, 1.

1.83. Найти в семиричной системе счисления в дополнительном коде сумму

двух чисел: 0.00065 и —0.01125.

1.84. Найти произведение чисел З1 • 0.201 и —З5 • 0,102 в троичной системе

счисления с цифрами 0, 1, 2. Результат перевести в обычную запись.

1.85. Найти сумму чисел —7-1 х 0.11066 и —7° х 0.11055 в дополнительном

коде в системе счисления с 5 = 7 и естественным множеством цифр. Результат

нормализовать.

1.86. Найти сумму двоичных чисел — 21 -0.1001 и 2° -0.1102 в обратном коде

в системе с цифрами 0, 1; результат нормализовать.

1.87. Найти частное для чисел 0.0111 и 0.1100, ограничиваясь четырьмя

цифрами частного. Результат перевести в десятичную запись.

1.88. Найти четыре цифры частного чисел 0.0442 и —0.4343 в системе счи

сления с основанием 5 и естественным множеством цифр. Результат перевести

в десятичную запись.

1.89. Найти частное от деления 4 • 0.1101 на 4* - 0.3301. Подсчитать при

поиске мантиссы частного пять цифр. Результат перевести в двоичную запись с

цифрами 0, 1.

1.90. Найти частное от деления 21 -0.1101 на —2* -0.1001. Результат деления

мантисс должен содержать пять разрядов и быть нормализованным.

1.91. Определить правила сложения и умножения одного разряда для тро

ичной системы с симметрическим множеством цифр. Используя эти правила,

Гл. 1. Основы многосортных множеств

найти сумму и произведение чисел 0.1101 и 0.1101. В этой записи цифра 1

соответствует количественному эквиваленту, равному —1.

1.92. Установить правила сложения и умножения в системе счисления с

основанием 6 и асимметрическим множеством цифр, смешенным в отрицатель

ную сторону. Найти сумму и произведение чисел —0.3012 и 0.1102. Черточка

над цифрой означает, что она отрицательна.

1.93. Определить правила сложения в двоичной системе счисления с ци

фрами 1, 0, 1. Найти сумму чисел 0.11011 и 0.11101.

1.94. Сколькими способами можно закодировать десять десятичных цифр

двоичными тетрадами?

1.95. Сколькими способами можно осуществить кодирование из предшест

вующей задачи, если потребовать еще взаимно однозначное соответствие цифр

и тетрад?

1.96. Найти сумму чисел 5764 и 2433 в коде прямого замещения и в коде с

избытком 3.

1.97. Найти сумму чнсел —79 и —981 в коде с избытком 3.

1.98. Установить правила сложения в коде с избытком 6. Сложить, используя

эти правила, числа 203 н 479.

1.99. Доказать утверждение: если все веса в двоично-десятичном кодирова

нии pi неотрицательны, то все они строго положительны.

1.100. Доказать, что единственным совершенным кодом является код с ве

сами 2 4 2 1.

1.101. Доказать утверждение: если в весомозиачном коде есть два одинако

вых веса, то их сумма ие превышает 9 (веса предполагаются положительными).

1.102. Доказать утверждение: код с положительными весами ие может иметь

вес, больший 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. В системе модулей gi = 2, д>з = 3, дз = 5 некоторое чнсло имеет код

в остатках вида 010. Определить это число.

1.109. В системе модулей qi = 7, дг = 8 заданы числа х и у своими кодами

в остатках 31 и 03 соответственно. Установить, что больше: х или у.

1.110. Записать алгоритм перевода кодов в остатках в десятичную запись

числа.

1.111. Найти способ определения знака числа в коде в остатках.

1.112. Найти способ сравнения чисел по величине в коде в остатках.

1.113. Установить правила деления для кода в остатках.

§1.12. Комментарии

§ 1.12. Еоммеитарни

Официально теория множеств была признана в 1897 г. на Первом междуна

родном конгрессе математиков, иа котором Адамар и Гурвиц привели многочи

сленные примеры применения этой теории в математическом анализе. Теория

множеств явилась основой создания алгебраических систем, имеющих большое

практическое применение при разработке математического обеспечения ЭВМ.

Большой вклад в развитие теории алгебраических систем внесли А.И. Маль

цев, Г. Биркгоф. Особенно бурное развитие получила теория моделей, сигнатура

которых обладает свойством симметричности (симметричных моделей). Этот

класс моделей позволяет эффективно рассматривать исследуемый объект как чер

ный ящик. Элементы (конструктивные или функциональные) объекта образуют

носитель модели, а ее сигнатура определяет их взаимосвязь. Для оптимального

задания моделей этого класса было предложено понятие мографа [8], спустя три

года оно вновь было “введено” во Франции и идентифицировано термином ги

перграф [34].

Алгебраические понятия весьма эффективны при проектировании сложных

систем управления, ЭВМ, вычислительных систем н сетей ЭВМ, банков данных

и пакетов прикладных программ.

Для углубления знаний по многосортным множествам рекомендуем работы

[11, 12, 14-16, 23, 34].

Математика, оперируя со строками своих

символов, имея дело с формальными исти

нами, тем ие меиее, может получить бес

конечно важные результаты, относящиеся к

описанию физической Вселенной.

К. Пирсон

Глава 2

МАТЕМАТИЧЕСКАЯ ЛОГИКА

§ 2.1. Логика высказываний

Высказыванием называется повествовательное предложение, о

котором можно сказать в данный момент, что оно истинно или

ложно, но не то и другое одновременно. Истинность или лож

ность предложения есть истинное значение высказывания. Со

поставим каждому высказыванию переменную, равную 1, если

высказывание истинно, и равную 0, если оно ложно. Если Р и

Q — некоторые высказывания, то можно образовать высказыва

ния “Р или Q", “Р и Q", “не Р ”, введя операции дизъюнкции

(V), конъюнкции (к) и отрицания ( ). Действия этих операций

задаются таблицами истинности (табл. 2.1-2.3), каждой строке

которых взаимно однозначно соответствуют набор значений соста

вляющих высказываний и соответствующее значение составного

высказывания.

Таблица 2.1 Таблица 2.2 Таблица 2.3

PVQ

0 - 0 0

0 1 1

1 0 1

PLQ

0 0 0

1 0 0

______

0 1

1 О

Операции дизъюнкции, конъюнкции и отрицания читаются

соответственно как “или”, “и” и “не”.

Приведем основные законы, определяющие эти операции:

закон идемпотентности дизъюнкции и конъюнкции

а V а = о, а к а = а] (2.1)

закон коммутативности дизъюнкции и конъюнкции

aV b = bVa, a k b = bka; (2.2)

закон ассоциативности дизъюнкции и конъюнкции

a V(bVc) = (aVb) V с,

a k (b к с) = (akb) к с;

§2.1. Логика высказываний 95

закон дистрибутивности конъюнкции относительно дизъ

юнкции и дизъюнкции относительно конъюнкции

a k. (6V с) = o&4Vflfcc1),

(2.4а)

а V Ь к с = (а V Ь) к (а V с);

(2.46)

закон двойного отрицания

а — а;

(2.5)

законы де Моргана

аУ b = a k b, а & 6 = а V Ь;

(2.6)

законы склеивания

akbV a kb = о, (а V b) к (а V 6) = о; (2.7)

законы поглощения

а V a k b = о, a k (а V Ь) = о;

(2.8)

законы Порецкого

аУакЬ = aV b, а к (о V Ь) = о & Ь; (2.9)

законы, определяющие действия с константами 0 и 1,

aVO = а, а& 0 = 0, a V l = l,

(2.10)

а &; 1 = a, oV5=l, а&о = 0.

Всякое высказывание, построенное с помощью операций V,

к , , имеет некоторое истинное значение, зависящее от значений

составляющих высказываний. Любое высказывание / может быть

задано в виде таблицы истинности. Бели значение высказыва

ния / зависит от п составляющих высказываний xi, 12, ..., хп, то

таблица истинности содержит 2П строк. Составляющее высказы

вание х,- будем называть атомарным высказыванием или просто

переменной х,-, рассматривая при этом сложное высказывание как

функцию f от п переменных.

Рассмотрим, например, устройство, фиксирующее принятие некоторой ре

золюции “комитетом трех”. Каждый член комитета при одобрении резолюции

нажимает свою кнопку; если большинство членов согласны, то резолюция при

нимается, что фиксируется регистрирующим прибором. Устройство реализует

высказывание }{х\, хз, х3), таблица истинности которого имеет вид табл. 2.4.

Таблица 2.4

Х2

Хз

/( Х1,Х2,Хз)

Х2 Хз

f(Xl,X2,X 3)

0 0

0 1

0 0 0

0 1

0 1 0

0 1

1 1 1

') Скобки в выражении a Sib V a Sic не ставим, так как конъюнкция Si как

мультипликативная операция более старшая по отношению к дизъюнкции (яв

ляющейся аддитивной операцией) и выполняется в первую очередь.

Гл. 2. Математическая логика

Исчисление высказываний можно построить, используя соот

ветствующие таблицы истинности. При этом очевидно, что алгебра

высказываний изоморфна алгебре Буля (М, V, &, ), элементы

носителя которой принимают значения 0 или 1, а сигнатура V,

&, обладает свойствами операций дистрибутивных решеток с до

полнениями. Алгебра Буля простейшая в классе булевых алгебр;

она является двухэлементной булевой алгеброй. Алгебру высказы

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

формально рассмотрев предельный случай решеток — двухэле

ментную решетку, в которой

a U 6 = Ь при а < 6. Эта решетка

преобразуется в булеву алгебру, если положить о = 6, 6 = о. Од

ним из элементов двухэлементной булевой алгебры является 0, так

как булева алгебра является решеткой с дополнениями, поэтому

вторым элементом этой алгебры является 1.

Согласно теоремам 1.2 и 1.5 каждое высказывание и соответ

ствующую ему булеву функцию /(x i, х2, ..., хп) можно предста-

Для рассматриваемого примера /(хi, х2, хз) может быть пред

ставлена в виде

f(xi, Х2, Х3) = XjX2X3 V Ж1Х2Х3 V Х!Х 2Х3 V ХхХ2Х3.

В дальнейшем представление булевой функции /(xj, х2, • . хп)

в виде дизъюнкции конституент будем называть совершенной

дизъюнктивной нормальной формой функции /(х 1, х2, . . х„).

Переменную или ее отрицание будем называть первичным

термом.

Количество первичных термов, которые образуют форму, за

дающую булеву функцию /(х 1, ж2, ■ • •, *п), называется сложно

стью L(f) этой формы.

Сложность совершенной ДНФ функции /(xj, х2, хз) голосова

ния равна 12. Уменьшим сложность этой функции, используя

основные тождества алгебры Буля. Согласно свойствам идемпо

тентности дизъюнкции имеем

/(х х , Х2, х 3) = X1X2X3 V X 1X2X3VX 1X2X3VX 1X 2X 3VX1X2X3VX 1X2X3.

Используя свойства коммутативности, ассоциативности и дистри

бутивности, получаем

/(х 1, х2, х3) = (xi V xj)x2x3 V (х2 V x2)xix3 V (х3 V x3)xix2.

Окончательно имеем

вить в виде дизъюнкции конституент & xf', где

/(х 1, х2, хз) = х2хз V xix3 V xix2 = х3(х2 V xi) V хгх2.

§2.1. Логика высказываний

В результате получаем сложность L(f) функции /(®i, х2, ®з),

равную 5.

Функции fa(x 1, х2, ®п) и fp(®1, ®2, ®п) называются

равными, если на каждом двоичном наборе (<7i, <72) • • ч ^п)

fa{& 1) ^2, • • •! <*п) = ®2, • • •, <7п)-

Количество бит (binary unit — двоичная единица), необходи

мое для задания булевой функции /(®i, ®2, . . ®п) в виде таблицы

истинности, равно п • 2П. Это количество можно уменьшить в п

раз, если использовать двумерную таблицу Вейча. Для этого пред

ставим исходное пространство Рп размерности п в виде декартова

произведения пространств РП1, Р„, размерности ni, п2 соответ

ственно, где ni + «2 = п.

В двумерной таблице, каждой строке которой взаимно одно

значно соответствует точка пространства РП1, каждому столбцу —

точка пространства РП2, на пересечении строки и столбца запи

сывается значение булевой функции /(®i, *2> • • •, хп) в соответст

вующей точке пространства Рп.

Пример 2.1. Построим таблицу Вейча для неполностью заданной булевой

функции f(xi, i 2, . . ij), задавая двоичные наборы (<Ti, <rj, ..., <rs) десятич-

ными эквивалентами 53 <*> ' 2п -‘:

1=1 ч Г 1 иа [0, 6], [5, 29], [2, 10],

/(*!,«,...,*s)=|0 иа[3)11]| [18)31].

Булева функция /( х i, Х2, ■■■, xs) задана интервалами, слева в квадратной

скобке указан минимальный, справа — максимальный элементы. Единичная

область этой функции включает интервалы, содержащие соответствующие точки:

[0, 6] = {0, 2, 4, 6}, [5, 29] = {5, 13, 21, 29}, [2, 10] = {2, 10}.

Нулевая область включает точки, образующие указанные интервалы:

[3, 11] = {3, 11}, [18, 31] = {18, 19, 22, 23, 26, 27, 30, 31}.

Мощность единичной области равна 9, нулевой области — 10, в остальных

13 точках булева функция f(xi, х2, ..., xs) ие определена.

Задание булевой функции называется противоречивым, если пересечение

единичной и нулевой области непусто.

Представим исходное множество Ps — {xi, xj, ..., xs} в виде декартова про

изведения Pt — {x i, хг} и Рз = (хз, Х4, Xj}:

Ps — Pi х Рз;

нижний индекс у идентификатора пространства Р указывает размерность про

странства.

При таком разбиении переменных Xi, х2, ...,xs таблица Вейча для заданной

функции имеет вид табл. 2.5.

Таблица 2.5

Ti&2

Х3Х4Х5

0 1 2 3 4 5 6

1 1 0 1 1 1

1 0

0 0 1 0 0

0 0 1

0 0

4 В. А. Горбатов

Гл. 2. Математическая логика

§ 2.2. Разложение Шеннона.

Декомпозиция булевых функций

Рассмотрим разложение булевой функции /(х i, х2, ..., хп) по

к переменным (для определенности по х\, х2, хк) — разло

жение Шеннона.

Теорема 2.1. Любая функция f(x i, х2, ..., хп), не равная

тождественно нулю, представима в виде разложения Шеннона

/(ж 1, х2, ..., xk, xk+i, • . жп) —

= w, V •••> **+1» •■•» *я),

где а,- = 0, 1; i = 1, ..., к, x?j = {§” £ I J ’

Используя метод полной индукции, покажем, что ж?' = 1 «

х,- = <т,- (табл. 2.6).

Подставим произвольно вместо первых к переменных их зна

чения: xi = сг*, х2 = а2, . . хк = сг£. Тог

да левая часть доказываемой формулы

равна / (ctJ , а*2, ..., ^ ,x fc+1, . . жп). Пра

вая часть представляет собой дизъюнкцию

Таблица 2.6

<r;

0 = 1

0 1

1 0

1 = 0

1 1

ч *к):

2 конъюнкций вида x*lx%3.. . x£*/(oi,

<j2,. . ак, xjt+i,..., хп), которые этой под

становкой разбиваются на два класса. К

первому классу относится конъюнкция, у

которой набор (<Ti, <72, ..., <7fc) совпадает с набором (о^,

К Г ‘> 2Т 2‘ - • * 2*, . • ОЪ, Хк+1, . . , * я ) =

—■ 1 ‘ 1 ' ■ • • ' 1 /(^1) ' ' •> Xfc-fl, • • •! Хп) =

= /(0"i, <72, . . ., <7j., Xfc+ b . . ., Хп).

Эта конъюнкция равна левой части формулы. Ко второму клас

су относится 2fc_1 конъюнкций, у каждой из которых хотя бы в

одной переменной х;, г G {1, 2, ..., к), а* ф сг,-. Следовательно,

каждая из них равна нулю. Тогда согласно закону, характеризую

щему действия с константами: а V 0 = о, получаем, что левая и

правая части формул равны при любой подстановке переменных

xi, х2, • •., хк.

Следствие. Предельное разложение Шеннона (к = п) бу

левой функции /(х 1, х2, ..., жп), не равной 0, имеет вид

f(x 1, х2, . . жп) —

V кх?.

V(<Tlt<T2,.■•,»»)) *-1

(2.11)

§ 2.2. Разложение Шеннона. Декомпозиция булевых функций 99

Предельное разложение Шеннона булевой функции f(x 1,

i2,. . хп) является ее совершенной дизъюнктивной нормальной

формой.

В алгебре Буля справедлив принцип двойственности, посколь

ку, как было показано в гл. 1, она является дистрибутивной решет

кой с дополнением. Согласно этому принципу имеем следующие

двойственные разложения Шеннона булевой функции /(xi,x2,...

..., I*, xjfc+i,..., xn) по k переменным:

f{xi, I 2, . . ., Xfc, . . ., I n) =

k _

= V -/(«Ti, (72, ..., ffjt, IJt+1, ..., I„).

Согласно закону двойного отрицания f(x\, i 2, ..., xn) = f(xi,

*2) • • ч xn) имеем

/( ®i, 12, • • ч Xfc, Xfc+li • • •, Xn) =

= /(x i, x2i • • ч Xfc, %k+1, • • ч Xn) =

к _

= w, V *2, **+1 , •••, *n) =

= ^ Л У ХГ V / ( a l> a 2, <7fc, Xjfc+1, . . . , X „ ) j . (2 .1 2 )

V(<ri,(T2,...,<rk) \«= 1 У

Таким образом, любая булева функция /(xi, 12, • ••, хп), не

равная тождественно 1, представима в виде выражения (2.12).

При к = п двойственное предельное разложение имеет вид

/(х 1, х2, ..., х„) = к ( v .

M(TU(T2,...,<T„)) V - 1 /

Двойственное предельное разложение Шеннона булевой функ

ции /(х 1, х2, . . х„) является ее совершенной конъюнктивной нор

мальной формой.

Пример 2.2. Построим совершенные ДНФ и КНФ булевой функции

f(xj, хз), заданной таблицей истинности (табл. 2.7).

Таблица 2.7

Х2

Хз

f(xi,x 2,x3)

Х2

Хз

f(x 1 ,Х2 ,Хз)

0 0

1 1 0 0 0

0 1 0

1 1

1 0

1 1 1 0 0

1 1 0 1 1 1

100

Гл. 2. Математическая логика

Совершенные ДНФ и КНФ этой функции имеют соответственно вид

/(*li *2, *з) = 11*2*3 V *1*2*3 V *1?2*3 V *1*2*3,

/(*1, *2, *з) = (*l V *2 V *з)(*1 V *2 V *з)(*1 V *2 V *з)(*1 V *2 V *з).

Далее будет рассмотрена теория ДНФ, из которой на основании

принципа двойственности легко построить теорию КНФ.

Будем называть булевы функции /(* i, х2, ..., zjt, arjt+i, ...

..., хп) в выражениях (2.10) и (2.12) остаточными мультипли

кативными и аддитивными функциями соответственно.

Укажем на важную связь между разложениями Шеннона и таб

лицами Вейча.

Представим исходное пространство Рп(Х ) в виде декартова

произведения пространств Рк{Ха) и Р3(Хь), Ха U Хь = Х,ХаГ\

ПХь = 0, k + s = n:

Рп(Х) = Рк(Ха) х Р,(Хь).

Каждой строке таблицы Вейча взаимно однозначно сопоста

вим точку пространства Рк(Ха), столбцу — точку пространства

Р3 (Хь) и рассмотрим разложение Шеннона булевой функции f(x ai,

ха2,..., хак, Xbt, хь2, ..., хь,) по первым к переменным. Тогда,

очевидно, i-я строка таблицы Вейча, идентифицируемая конъюнк

цией ЖаГ1 & ха22 &... & ха1к, соответствует остаточной функции

/ (*^ai) 0Я2 , . . ., (Так , Xbx, Xf,2 , . . ., ХЬ,)-

Будем называть разложение Шеннона булевой функции f(X)

строчным, если разложение осуществляется по переменным, со

ответствующим строкам таблицы Вейча.

Аналогично определяется столбцевое разложение Шеннона

булевой функции f(x): j -й столбец таблицы Вейча, идентифици

руемый конъюнкцией х^1 & х ^ &.. .& х^ ‘, соответствует оста

точной функции

f(xai) ха2 t • • •) ) Vbt) ^62 1 • • ч &bs)-

Найденная связь позволяет сводить исследование булевых

функций к анализу функций от меньшего числа переменных путем

построения декомпозиции исходных булевых функций.

Декомпозицией булевой функции /(zj, х2, ..., хп) называется

посет, носителем которого являются терминальные {z;} и функ

циональные {/, Fi, <pj, ...} переменные, сигнатурой — отношение

включения одной переменной в качестве аргумента другой.

Теорема 2.2. Булева функция /(xj, х2, ..., хп) декомпози

руема, если найдется разбиение ее переменных {xai, z„2, ...

• • •) xak}, {xbi, хъ2> • • •) хь,} такое, что при объединении строк

или столбцов в соответствующей таблице Вейча не образу

ется противоречивого задания, при котором

[log2 Na\ < к или [log2 Nb] < s,