Методичка заоч МЛ_ ИВТ_2евысш2015
.pdf1
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Брянский государственный технический университет
“Утверждаю”
Ректор БГТУ О.Н. Федонин
“___”_________ 2015 г.
МАТЕМАТИКА
КОНТРОЛЬНЫЕ ЗАДАНИЯ
ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ И ТЕОРИИ АЛГОРИТМОВ
Методические указания для студентов 2 курса 2-е высшее образование
специальности 230100 «Информатика и вычислительная техника»,
Брянск 2015
2
ПРЕДИСЛОВИЕ
Студенты БГТУ заочной формы обучения специальностей, связанных с информатикой, изучают курс математической логики и теории алгоритмов. При этом у них возникает потребность в методических указаниях, содержащих не только контрольные задания, но и краткие теоретические сведения к ним, а также примеры решения наиболее сложных задач, что облегчило бы заочникам выполнение контрольных работ.
Эту задачу и призвана решить данная работа.
Структура данных указаний такова: для каждого из заданий контрольных работ № 1 и № 2 сначала даются краткие теоретические сведения, затем формулируется постановка задачи, дается пример решения типовой задачи. После этого приводятся все варианты контрольных заданий (номера вариантов между студентами распределяет лично преподаватель).
Контрольная работа № 1.
Задание 1.
СТАНДАРТНЫЕ ФОРМЫ БУЛЕВЫХ ФУНКЦИЙ
Булевы функции (далее для краткости БФ) можно представлять в самых разных видах благодаря наличию многочисленных логических тождеств.
Приведем несколько важнейших логических тождеств:
1. x = x .
2. |
xÚ y |
= x × y |
– первое правило де Моргана. |
|
|
|
= x Ú y |
|
|
3. |
xy |
– второе правило де Моргана. |
4.( xÚy)z =xzÚyz – раскрытие скобок.
5.x ~ y = xy Ú x × y – выражение эквиваленции через основные логи-
ческие операции.
6. x Dy = xy Ú xy – выражение исключающего «или» через основные логические операции.
7. x Þ y = x Ú y – выражение импликации через основные логические операции.
8. x ~ y = xDy – отрицание эквиваленции (отсюда ясно, что и наоборот, xDy = x ~ y ).
3
9.x Þ y = x × y – отрицание импликации.
10.xÚx=x, x×x=x.
11.xÚx =1, x×x =0.
12. xÚ1=1, x×1=x
13. xÚ0=x, x×0=0
Пользуясь этими тождествами, можно проводить самые разные преобразования БФ. Однако при этом надо иметь какую-то цель, а не просто заменять одно выражение другим.
Потребности математической логики привели к трём конкретным целям:
а) Совершенная дизъюнктивная нормальная форма (СДНФ) – это дизъюнкция нескольких элементарных конъюнкций (ЭК) вида
xi1 × xi2 × ...× xik , где отрицания могут стоять на любых местах.
СДНФ обладает наибольшей логической простотой, так как ясно показывает все возможные случаи, когда истинна данная БФ.
Приводить данную формулу к виду СДНФ лучше всего с помощью следующего алгоритма:
Шаг 1. Добиться, чтобы в формуле остались только дизъюнкции, конъюнкции и отрицания аргументов (применяя тождества № 2–9) . Шаг 2. Добиться, чтобы конъюнкции выполнялись раньше дизъюнкций (раскрыть скобки по тождеству 4).
Шаг 3. Сделать все ЭК правильными, применяя тождества 11 и 13. Шаг 4.Сделать все ЭК полными, применяя тождество 12; а именно,
если в ЭК отсутствует переменная x, то домножить ее на 1=xÚx . При возникновении скобок вернуться к шагу 2.
Шаг 5. Ликвидировать одинаковые элементарные конъюнкции, применяя тождество 10.
ПРИМЕР. Преобразовать в СДНФ по алгоритму формулу
(xÞy)(z+x).
Решение. Применяем алгоритм по шагам:
1. Добьемся, чтобы в формуле остались только дизъюнкции, конъюнкции и отрицания аргументов: (x Þ y)(z + x) =(x Ú y)(zx Ú zx).
4
2.Добьемся, чтобы конъюнкции выполнялись раньше дизъюнкций (раскроем скобки): (x Ú y)(zxÚzx) = x ×zxÚ yzxÚxzx Ú yzx .
3.Делаем все элементарные конъюнкции правильными:
x×zxÚ yzxÚxzx Ú yzx =0Úxyz Úxz Úxyz = xyz Úxz Úxyz
4.Делаем все элементарные конъюнкции полными:
xyz Úxz Úxyz = xyz Úx(y Ú y)z Úxyz = xyz ÚxyzÚx × yz Úxyz
5. Ликвидируем одинаковые элементарные конъюнкции: xyz Ú xyzÚ x × yz Ú xyz = xyz Ú xyzÚ x × yz .
Получили СДНФ, задача решена.
б) Совершенная конъюнктивная нормальная форма (СКНФ) – это двойственное к СДНФ выражение, то есть конъюнкция нескольких
элементарных дизъюнкций. Например, выражение ( x Ú y )( y Ú z ) является СКНФ.
Легко понять, что получить СКНФ для данной БФ f можно с помощью понятия двойственности.
Определение : Пусть дана БФ f(x1, … ,xn). Двойственной к ней называется БФ f*, заданная формулой
f *(x1,..., xn ) = f (x1..., xn )
Если f*=f, то БФ называется самодвойственной.
Для получения СКНФ для заданной БФ f применяется следующий трехшаговый алгоритм:
1. Найти двойственную f* к данной БФ.
2. Привести f* к виду СДНФ.
3. Еще раз взять двойственную БФ: (f*)*= f = СКНФ.
ПРИМЕР. Преобразовать в СКНФ с помощью двойственности БФ
f=(xÞy)(z+x).
РЕШЕНИЕ. 1. Находим двойственную БФ:
f* =( x Þ y )( z + x ) =( x Þ y )Ú( z + x ) = x × y Ú z × x Ú z × x .
2. Преобразуем ее к СДНФ:
5
f * = x × y( z Ú z ) Ú z × x( y Ú y ) Ú z × x( y Ú y ) =
xyzÚxyz Úxyz Úxy×z ÚxyzÚx × yz =x × yzÚxyz ÚxyzÚxy×z Úxyz
– получили СДНФ.
3. Еще раз берем двойственную БФ:
(f*)*= f =( x Ú y Ú z )( x Ú y Ú z )( x Ú y Ú z )( x Ú y Ú z )( x Ú y Ú z )
– получили СКНФ.
в) Многочлен Жегалкина – это композиция сложений и умножений, а точнее выражение вида a + å xi1 xi2 ...xik , где суммирование ведет-
ся по некоторому множеству различных наборов (i1, i2,…, ik), в которых ни один индекс не повторяется.
Например, многочленами Жегалкина являются x+y+1, xy+z,
xyz+y+1, но не являются xxy+y, xz+zx+1 и т.п.
Любую БФ можно привести к виду многочлена Жегалкина, и притом единственным образом. Чтобы практически это сделать, достаточно перейти к трем основным логическим операциям (аналогично шагу 1 преобразования формулы в СДНФ), а затем применить два новых тождества:
14.x = x + 1 .
15.xÚy =xy+x+y.
Теперь, раскрыв скобки и приведя подобные члены по тождеству
16. x+x = 0,
мы получим многочлен Жегалкина.
ПРИМЕР. Преобразовать к виду многочлена Жегалкина БФ
f=(xÞy)(z~x).
РЕШЕНИЕ. f = ( x Ú y )( z D x ) = ( x y + x + y )( z + x + 1 ) =
= (( x + 1 ) y + x + 1 + y )( z + x + 1 ) = ( xy + x + 1 )( z + x + 1 ) =
= x y z + x z + z + x x y + x x + x + x y + x + 1 = x y z + x z + x + 1
– получили многочлен Жегалкина.
Степень многочлена Жегалкина – это наибольшее число множителей в его членах. Например, xyz+x+1 – многочлен Жегалкина степени 3. Многочлен Жегалкина степени 1 или 0 называется линейной функцией. Так, функции x+1 и x+y+ z – линейны.
6
Всякая композиция линейных функций также линейна.
Задание 1 контрольной работы № 1.
Данную формулу преобразовать к виду: а) СДНФ с помощью алгоритма; б) СКНФ с помощью двойственности; в) многочлена Жегалкина;
Отметим, что в ответах пунктов а) и б) необходимо СТРОГО соблюдать следующий порядок записи:
Переменные всегда писать в порядке x, y, z, t.
При записи нескольких ЭК в ответе соблюдать следующий порядок:
1)сначала ЭК, содержащие x , а затем – содержащие x.
2)внутри каждой из этих групп сначала ЭК, содержащие y , а затем – содержащие y.
3)внутри каждой из этих групп сначала ЭК, содержащие z , а затем – содержащие z.
4)внутри каждой из этих групп сначала ЭК, содержащие t , а затем – содержащие t.
Отметим, что в примере преобразования формулы в СДНФ этот порядок НЕ соблюден (то есть нужно еще переставить местами члены!), а вот в примере преобразования формулы в СКНФ этот порядок строго соблюден. Приводим варианты к заданию 1:
Вар |
|
f |
|
|
|
|
|
201 |
(x ~ y )(z |
~ t ) |
|||||
203 |
(x ~ y )(z |
~ t ) |
|||||
205 |
(x ~ y )(z |
~ t ) |
|||||
207 |
(x ~ y )(z |
~ t ) |
|||||
209 |
(x ~ y )(z |
|
|
|
) |
||
~ t |
|||||||
211 |
(x ~ y )(z |
|
|
|
|
) |
|
~ t |
|||||||
213 |
(x |
Þ y )(z |
~ t ) |
||||
215 |
(x |
Þ y )(z |
~ t ) |
||||
217 |
(x |
Þ y )(z |
~ t ) |
||||
219 |
(x |
Þ y )(z |
~ t ) |
Вар |
|
f |
|
|
|
|
|
202 |
(x |
~ y )(z ~ t ) |
|||||
204 |
(x |
~ y )(z ~ t ) |
|||||
206 |
(x |
~ y )(z ~ t |
) |
||||
208 |
(x |
~ y )(z ~ t |
) |
||||
210 |
(x |
~ y )(z ~ t |
) |
||||
212 |
(x |
~ y )(z ~ t |
) |
||||
214 |
(x |
Þ y )(z |
~ t ) |
||||
216 |
(x |
Þ y )(z |
~ t ) |
||||
218 |
(x |
Þ y )(z |
|
|
|
) |
|
~ t |
|||||||
220 |
(x |
Þ y )(z |
|
|
|
|
) |
~ t |
7
Задание 2.
МИНИМИЗАЦИЯ БУЛЕВЫХ ФУНКЦИЙ
Длиной ДНФ называется общее количество переменных, входящих в ее запись. ДНФ минимальной длины, тождественно равная данной функции, называется ее минимальной ДНФ (МДНФ).
Для практической минимизации ДНФ с небольшим числом переменных (3-4) вполне достаточно следующих двух приемов:
а) Прием склейки. Это действие, обратное к шагу 4 алгоритма преобразования формулы в СДНФ. А именно, если удалось выделить множитель вида x Ú x , то, заменив его единицей в силу тождества 12, мы существенно уменьшим длину ДНФ.
ПРИМЕР. Действуя по формулам xy Ú xy = x( y Ú y ) = x ×1 = x , то есть применив склейку по переменной y, мы уменьшили длину ДНФ с 4 до 1 и, безусловно, получили МДНФ.
б) Когда склеек больше нет (получена так называемая тупиковая ДНФ), могут помочь два сокращающих логических тождества:
19.xÚ xy = x – закон поглощения,
20.x Ú xy = x Ú y – закон сокращения.
ПРИМЕРЫ. 1) xy Ú xyz = xy – по закону поглощения;
2) xy Ú xyz = x( y Ú yz ) = x( y Ú z ) = xy Ú xz – по закону сокра-
щения. Мы уменьшили длину ДНФ с 5 до 4. Интуитивно ясно, что полученная ДНФ является минимальной (хотя строго доказать это не так просто).
Задание 2 контрольной работы № 1
а) Дана двоичная строка, представляющая собой столбец значений БФ f в ее таблице истинности.
Получить по этой строке СДНФ и привести ее к минимальной ДНФ. Для приведения СДНФ к минимальной применять на первом этапе процедуру склейки, а на втором – сокращающие логические тождества 19 и 20.
Приводим варианты к заданию 2(а):
Вар |
Cтолбец f |
Вар |
Cтолбец f |
201 |
0011001100111111 |
202 |
0101010101011111 |
203 |
0000001111111111 |
204 |
0000010111111111 |
205 |
0011001101110111 |
206 |
0011011100110111 |
207 |
0001000111111111 |
208 |
0000000000001111 |
209 |
0000000000110011 |
210 |
0000000001010101 |
8
211 |
0000001100000011 |
212 |
0000010100000101 |
213 |
0001000100010001 |
214 |
1100110011001111 |
215 |
1010101010101111 |
216 |
1111111100000011 |
217 |
1111111100000101 |
218 |
1100110011011101 |
219 |
1100110111001101 |
220 |
1111111100010001 |
б) Дана СДНФ в виде формулы. Привести ее к минимальной ДНФ. Для этого следует сначала привести данную формулу к какой-нибудь ДНФ, применив шаги 1 и 2 алгоритма преобразования формулы в СДНФ. После чего действуем точно так же, как в задании 1 контрольной работы № 2, то есть применяем склейки и сокращающие логические тождества.
Пример. Преобразовать к МДНФ формулу xy +( x Þ yzt ) . Решение. Приведем формулу к ДНФ:
xy +( x Þ yzt ) = xy ×( x Þ yzt )Ú xy ×( x Þ yzt ) =
= xy × x × yzt Ú( x Ú y )×( x Ú yzt ) = xy ×( y Ú z Ú t ) Ú( x Ú yx Ú x × yzt ) = xy × z Ú xy × t Ú x Ú yx Ú x × yzt – получили ДНФ.
Применяем закон поглощения и получаем ДНФ xy × z Ú xy × t Ú x . Применяем дважды закон сокращения и получаем ДНФ
y × z Ú y × t Ú x . По всем признакам она является минимальной ДНФ, длина ее равна l=5 и уменьшить длину не представляется возможным.
Если в Вашем варианте встретилась такая ситуация, сдавайте работу преподавателю – он точно определит, получена ли минимальная ДНФ или возможно еще её уменьшить.
Приводим варианты к заданию 2(б):
Вар |
Формула |
Вар |
Формула |
201 |
(x~y)+(yÚz) |
202 |
xzÞ(y+xz) |
203 |
(x+y)~(yÞz) |
204 |
(x~y)Þyz |
205 |
(x+y)Þ(y+z) |
206 |
(x+y)Úyz |
207 |
(x~y) Þ(y+z) |
208 |
xyÞ(x+z) |
209 |
(x+y)Ú(yz) |
210 |
yz+(xÚz) |
211 |
( x ~y)Þ(y+z) |
212 |
yz~(xÞz) |
213 |
( x ~z)+(yÚz) |
214 |
yzÞ(x+z) |
215 |
( x ~y)~(yÞz) |
216 |
yzÞ(x+z) |
217 |
( x +z)Þ(y~z) |
218 |
(yz~x)Þz |
219 |
(x+y)~(y+ z ) |
220 |
(y+x)~xz |
9
Контрольная работа № 2.
ПОЛНОТА СИСТЕМ БУЛЕВЫХ ФУНКЦИЙ
Сначала нам необходимо ввести важное понятие: МОНОТОННЫЕ БФ.
Определение. БФ f называется монотонной если a £ bÞ f(a) £ f(b) для всех двоичных наборов a и b длины n.
Двоичные наборы сравниваются не так, как двоичные числа, а по ВСЕМ битам. То есть a £ b Û ai £ bi для всех i от 1 до n.
Примеры: 1) a=01010
b=11011
Пройдя по всем битам, видим, что ai£bi , поэтому a £ b. 2) a = 010011
b = 110010
Видим, что в первом бите ai < bi , но в шестом бите ai > bi , поэтому a и b – несравнимые наборы.
Чтобы проверить монотонность функции по определению, следует в таблице истинности пересмотреть все пары сравнимых наборов a и b. Если хотя бы один раз a<b, но f(a)>f(b), то функция немонотонна. Если же такого сочетания найти не удалось, но функция монотонна.
Пример:
1) f ( x) = x .
Составляем таблицу истинности:
|
x |
f |
a |
0 |
1 |
b |
1 |
0 |
Видим, что a<b , но f(a)>f(b). Поэтому отрицание не монотонно.
2) f(х,у)=хÚу.
Составляем таблицу истинности:
x |
y |
f |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
Cделав пять проверок, мы не смогли найти ситуацию, когда a<b , но f(a)>f(b). Поэтому дизъюнкция монотонна.
Аналогично проверяется, что и конъюнкция монотонна.
10
Легко доказать, что всякая композиция дизъюнкций и конъюнкций также монотонна.
Пример: f = xyzÚyt – монотонна, так как является композицией дизъюнкций и конъюнкций. Составлять таблицу истинности не нужно.
ПРОБЛЕМА ПОЛНОТЫ СИСТЕМ БФ.
Напомним два факта:
1)всякая БФ может быть представлена в виде композиции дизъюнкции, конъюнкции и отрицания (например, СДНФ).
2)любая БФ может быть представлена в виде композиции сложения, умножения и константы (многочлен Жегалкина).
Обобщим эти два факта:
Определение: системы БФ {j1, j2,…,jn} называется полной, если любая БФ может быть представлена в виде их композиции.
Факты 1 и 2 показывают нам, что система {xÚy, xy} полна; система {x+y, xy, 0, 1} также полна.
Проблема полноты состоит в том, чтобы для любой заданной системы БФ выяснить, полна она или нет.
Эта проблема тесно связана с вопросом элементной базы логических схем: из каких стандартных логических элементов можно собрать любую схему.
Легко привести примеры НЕПОЛНЫХ систем.
Пример 1. Полна ли система {xÚy, xy} ? Так как любая композиция дизъюнкций и конъюнкций монотонна, то ни какую немонотонную БФ нельзя представить в виде композиции дизъюнкций и конъюнкций. Система неполна.
Пример 2. Полна ли система {x+y, x+y+z, 1} ? Так как все эти функции линейны (многочлены Жегалкина 1-й или 0-й степени), то любая их композиция также линейна, поэтому ни одна нелинейная БФ не может быть через них выражена. Система неполна.
Примеры 1 и 2 можно обобщить, введя важнейшее понятие.
ФУНКЦИОНАЛЬНО ЗАМКНУТЫЕ КЛАССЫ Определение. Множество БФ называются функционально замкнутым классом (ФЗК), если любая композиция функций из этого класса снова принадлежит ему же.