Решение составим сокращенные таблицы истинности обеих формул
 Скачать 1.5 Mb.
|
|
Практическое занятие № 1 Построение таблиц истинности Пример. Проверьте, будут ли эквивалентны следующие формулы: и составлением таблиц истинности. Решение: составим сокращенные таблицы истинности обеих формул: Поскольку полученные столбцы не совпадают, формулы не эквивалентны. Задания для самостоятельного выполнения: Проверьте составлением таблиц истинности, будут ли эквивалентны формулы. a. b. c. d. e. f. g. h. i. j. k. l. m. n. o. p. q. r. s. t. u. Практическое занятие № 2 Упрощение формул логики с помощью равносильных преобразований Пример. Доказать равносильность, используя основные законы логических операций: . Решение. Задания для самостоятельного выполнения: Упростите формулу, используя равносильные преобразования a. b. c. d. e. f. g. h. i. j. k. l. m. n. o. p. q. r. s. t. u. Практическое занятие № 3 Представление булевой функции в виде СДНФ и СКНФ. Пример. Для функции , заданной своими истинностными значениями, запишите: СДНФ и СКНФ. Решение: СКНФ строится по нулевым наборам, СДНФ – по единичным наборам (см. таблицу). Таблица СКНФ СДНФ. Задания для самостоятельного выполнения: Для функции, заданной своими истинностными значениями, запишите: СДНФ и СКНФ. а. b. c. e. f. g h. i. j. k. l. m. n. o. p. q. r. s. t. u. Практическое занятие № 4 Представление булевой функции в виде МДНФ. Пример 1. Пусть дана функция от трех переменных . Найти её МДНФ методом неопределённых коэффициентов. Решение: Построим таблицу истинности для данной функции. Она будет иметь следующий вид: В ДНФ общего вида такой функции будет 26 неопределенных коэффициентов. Для обозначения этих коэффициентов будем использовать букву К с нижним индексом, указывающим конъюнкцию, перед которой стоит этот коэффициент. С учетом всех принятых обозначений ДНФ общего вида запишется так:
ДНФ(0,0,1): ДНФ(0,1,0): ДНФ(0,1,1): ДНФ(1,0,0): ДНФ(1,0,1): ДНФ(1,1,0): ДНФ(1,1,1):
В каждом уравнении полученной системы имеется по два коэффициента, которые могут быть приравнены к 1. Отсюда вытекает неоднозначность решения задачи. Учитывая то, что в каждом уравнении следует выбрать лишь один коэффициент, получим следующие два решения: Первое: Второе: Остальные коэффициенты в обоих случаях приравниваем к нулю.
МДНФ1 и МДНФ2 Пример 2. Пусть функция от трех переменных задана в виде . Построить её СокрДНФ. Решение: Для нахождения СокрДНФ необходимо построить СДНФ. Для данной функции СДНФ будет иметь вид: Используя законы склеивания (- склеивание; или - полное склеивание, или - неполное склеивание) выполним всевозможные склеивания, т.е. будем склеивать первую конъюнкцию со второй, третьей, четвертой, затем вторую с третьей и четвертой, и наконец, третью с четвертой. Тогда Теперь выполняя всевозможные поглощения ( - поглощение, где A и B - элементарные конъюнкции), получим: Поскольку преобразования больше невозможны, последняя формула является СокрДНФ. Пример 3. Пусть функция имеет следующие значения: . Найти МДНФ функции методом Куайна. Решение: Для данной функции запишем её СДНФ: . Построим СокрДНФ:
Используя сокращённую и совершенную ДНФ, построим таблицу Куайна. В верхней строке запишем дизъюнкты совершенной ДНФ, в левом столбце запишем дизъюнкты сокращённой ДНФ. В тех ячейках, где дизъюнкта сокращённой ДНФ покрывает дизъюнкту совершенной ДНФ, ставим 1. Ввиду наличия единственной единицы в столбцах 1 и 2, конъюнкции и являются ядровыми. Таким образом, единицы ядра находятся в столбцах: 1, 2, 3 и 5. Ни одна из единиц 4–го столбца не покрывается ядром. Тем самым, обе остальные конъюнкции входят в ДНФ Куайна, которая в данном случае совпадает с Сокращенной ДНФ. Для построения МДНФ достаточно иметь одну единицу в 4–ом столбце, это равносильно удалению из СокрДНФ любой из конъюнкций: или . При этом получаются две минимальные ДНФ: и . Пример 4. Для функции заданной следующим образом построить МДНФ с помощью карт Карно. Решение: Значения функции перечислены в порядке естественного увеличения наборов значений переменных, рассматриваемых как четырехразрядные двоичные числа. Изобразим карту Карно для данной функции, проставляя в ней только единичные значения. Рисунок 1 Разобьем единицы по группам, как показано на рисунке 1. Тогда соответствующая этому разбиению: МДНФ1 Очевидно, что ДНФ той же сложности будет получена, если разбить единицы на группы так, как показано на рис. 2 Рисунок 2 Соответствующая этому разбиению МДНФ2 = Для разбиения, показанного на рисунке 3, МДНФ имеет ту же сложность и равна: МДНФ3 = Рисунок 3 Задания для самостоятельного выполнения: 1. Пусть дана функция от трех переменных . Найти её МДНФ методом неопределённых коэффициентов. а. b. c. e. f. g. h. i. j. k l. m. n. o. p. q. r. s. t. u. 2. Пусть дана функция от четырёх переменных . Построить её СокрДНФ. a. b. c. d. e. f. g. h. i. j. k. l. m. n. o. p. q. r. s. t. 3. Пусть дана функция от четырёх переменных . Найти МДНФ функции методом Куайна. а. b. c. e. f. g. h. i. j. k. l. m. n. o. p. q. r. s. t. u. w. 4. Для функции от четырёх переменных построить МДНФ с помощью карт Карно. Практическое занятие № 5 Проверка булевой функции на принадлежность классам T0, T1, S, L, M; проверка множества булевых функций на полноту. Пример 1. Определите к каким классам относится функция следующего вида: Решение: Запишем значения функции в таблицу истинности. Т.к. , то (класс функций, сохраняющих ноль). Т.к. , то (класс функций, сохраняющих единицу). Т.к. , то (класс самодвойственных функций). Рассмотрим наборы: и . Заметим, что . Т.к. , но , то (класс монотонных функций). Найдем полином Жегалкина: Т.к. в полиноме Жегалкина имеются нелинейные слагаемые, то (класс линейных функций). Пример 2. Определите, является ли полной система функций? Образует ли она базис? . Решение: построим таблицы истинности для функций системы F . Найдем полином Жегалкина для функций и : Оформим в виде таблицы принадлежность функций из F классам Поста: Т.к. в системе F имеются функции: не сохраняющая ноль, не сохраняющая единицу, не самодвойственная, немонотонная и нелинейная, то по теореме Поста о полноте система F является полной. В то же время базиса она не образует, т.к. из неё может быть удалена функция , и при этом оставшаяся система будет полной. Задания для самостоятельного выполнения: 1. Определите к каким классам относится функция следующего вида: а. b. c. e. f. g. h. i. j. k l. m. n. o. p. q. r. s. t. u. 2. Определите, является ли полной система функций? Образует ли она базис? a. b. c. d. e. f. g. h. i. j. k. l. m. n. o. p. q. r. s. t. u. Практическое занятие № 6 Решение задач на выполнение теоретико–множественных операций и на подсчет количества элементов с использованием формулы количества элементов в объединении нескольких конечных множеств. Пример 1. Даны множества: , - полуинтервал на числовой оси, - отрезок на числовой оси. Найти: , , , , , , , , , , , , . Изобразить на плоскости: , , . Найти , считая универсальным множеством множество всех вещественных чисел. Решение: Объединением двух множеств A и B называется множество, состоящее из всех элементов, являющихся элементами хотя бы одного из множеств A или B, поэтому: Пересечением двух множеств A и B называется множество элементов, принадлежащих одновременно и A, и B, поэтому: – пустое множество Относительным дополнением множества B до множества A называется множество тех элементов A, которые не являются элементами B, поэтому Симметрической разностью двух множеств A и B называется объединение двух разностей и , а абсолютным дополнением множества A называется множество всех элементов, не принадлежащих A, поэтому: Декартовым (прямым) произведением двух множеств A и B называется множество всех упорядоченных пар таких, что и , поэтому: Пример 2. Для заданного семейства множеств где Г – заданное индексное множество, найдите объединение и пересечение всех множеств семейства, т.е. и (по всем возможным индексам ). , где для всякого вещественного индекса k множество Решение: рассмотрим множества для некоторых фиксированных индексов k. При множество – центр вещественной плоскости. При и – ромб в центре вещественной плоскости с диагоналями, равными 1 и направленными вдоль осей координат. При и – ромб с диагоналями, равными 4 и т. д.. При увеличении абсолютной величины индекса k диагонали ромба, расположенного в центре вещественной плоскости, увеличиваются и при ромб занимает всю вещественную плоскость. Таким образом, объединение по всем вещественным индексам k равно – вся вещественная плоскость, а пересечение по всем вещественным индексам k равно – центр вещественной плоскости. Пример 3. Докажите тождество, используя только определения операций над множествами: Решение: (1) Пусть , тогда . Отсюда следует, что 1) и или 2) и . В первом случае из того, что следует, что х принадлежит также объединению множества А с любым другим множеством, в том числе и множеством В, т.е. . Но в то же время и, следовательно, х принадлежит также объединению с любым другим множеством, в том числе и множеством , т.е. . Таким образом, и , т.е. . Анало гично во втором случае: из того, что следует, что х принадлежит также и . И в то же время, поскольку , то х принадлежит также объединению , с любым другим множеством, в том числе и множеством , т.е. . И также как в первом случае имеем: и , тем самым . (2) Пусть теперь . Тогда и , отсюда и . Следовательно, если, то, т.е. . Если же , то и значит . Таким образом, , что равносильно тому, что . Из (1) и (2) сле дует справедливость тождества. Пример 4. Докажите тождество, используя диаграммы Эйлера-Венна. A B C AB A B C A B C AC A B C 1) 2) 3) 4) 5) A B C BC (AB)(BC) (AB)(BC)(AC) Решение: Изобразим диаграмму для левой части тождества по шагам: 5) A B C (AB)(BC)(AC) 1) A B C AB 2) A B C BC 3) A B C AC 4) A B C (AB)(BC) Теперь диаграмму правой части по шагам: Ввиду того, что заштрихованные области, полученные на последнем шаге для левой и правой части тождества, одинаковы, можно заключить, что исходное выражение верно. Пример 5. На предприятии работает 67 человек. Из них 48 не знают английский, 35 – немецкий, 27 – оба языка. Сколько человек не знают английский и немецкий? Решение: Для решения используем диаграммы Эйлера-Венна. Построим диаграмму, на которой изобразим прямоугольник, соответствующий общему числу работающих (67) и две пересекающиеся области А (48) и В (35) человек (знающие английский и немецкий языки). На диаграмме общая часть двух этих областей соответствует 27 – количеству работающих, которые знают оба языка. Требуется найти область прямоугольника, не входящую ни в область А, ни в область В. Данная область будет равна: . U=67 В=35 А=48 АВ=27 |