Документ (6). 1. Что представляют собой объекты изучения алгебры логики как научной дисциплины
 Скачать 18.32 Kb.
|
|
Практическое задание I. 1. Что представляют собой объекты изучения алгебры логики как научной дисциплины. Алгебра логики – это один из разделов математической логики, объектами которого являются высказывания, а также операции, выполняемые с ними. 2. Что называют простым высказыванием ? Простое высказывание – это любое утверждение (как на естественном, так и формальном языке), в котором: 1) выражается одна законченная (не делимая без потери смысла) мысль, 2) об истинности или ложности которого имеет смысл выносить суждение. 3. Что называют логическими переменными и константами, как их выражают в математической форме ? Логическим выражением называется комбинация логических переменных и констант, связанных элементарными базовыми логическими функциями(или логическими операциями). 1. Конъюнкция (логическое умножение) двух величин x и y. Она истинна только в том случае, когда истинны и x и y, т. е. x = у = И. Во всех других случаях функция ложна. 2. Дизъюнкция (логическое сложение) двух переменных x и y ложна только в случае x = y = Л, во всех случаях – истинна. Обозначают как: v, +, max, OR. 3. Импликация (логическое следование) двух переменных x и y означает правильный способ вывода величины y из x, логическое следование y из x, подчиненность y по отношению к x. 4. Эквивалентность двух x и y означает, что значения x и y одинаковы: x = y. 5. Сложение по модулю 2 (строгое, исключающее сложение). В отличие от нестрого логического сложения (дизъюнкции) данная функция ложна при x = y = И. 6. Функция Шеффера (штрих Шеффера, антиконъюнкция, НЕ-И) – функция, равная отрицанию конъюнкции. Функция ложна только в случае истинны обе ее переменные, т. е. x = y = И. Иначе функция истинна. 7. Функция Пирса (стрелка Пирса, функция Вебба, антидизъюнкция, НЕ-ИЛИ) – функция, равная отрицанию дизъюнкции. Функция истинна только в случае ложности обеих ее переменных, при x = y = Л. Иначе функция ложна. 4. Сколько констант существует в алгебре логики? Всего три (3) константы существует в алгебре логики 5. Какие из фраз и математических выражений нельзя считать высказыванием: а) x ³ у, б) “сегодня 1 января”, в) приказ “вольно!“ ? В) приказ «Вольно!»- данная фраза не предполагает оценки ее истинности, поэтому не может быть высказыванием. 6. Какие отображения называют логическими (булевыми) функциями ? Некоторая совокупность логических переменных (x1, x2,…, xn). Отображение f, которое сопоставляет каждому из возможных наборов значений логических переменных (x1, x2,…, xn) некоторое логическое значение (0 или 1), называют логической (булевой), функцией. По числу переменных n логические функции называют одноместными (n = 1), двухместными (n = 2) и т. д. 7. Как логическую функцию задают при помощи таблицы ? Дизьюкция-это логическое сложение (ИЛИ),возвращает значение ИСТИНА,если хотя бы один из аргументов имеет значение ИСТИНА или ЛОЖЬ,если все агрументы имеют значение ЛОЖЬ. Эквиваленция-это функция тождества,эквивалентность определяет результат сравнения двух простых логических выражений.Результатом эквивалентности является новое логическое выражение, которое будет истинным тогда и только тогда,когда оба исходных выражения одновременно истинны и ложны. 8. Какие логические функции называют двухместными? Двухместные функции (операции) образуют Алгебру логических функций, что означает достаточность их совокупности для представления любой логической функции. Т.е. любая логическая функция от конечного числа логических переменных может быть представлена с помощью двухместных функций в виде некоторого выражения и наоборот, любому правильно построенному из логических переменных и операций выражению будет отвечать некоторая логическая функция. По числу переменных n логические функции называют одноместными (n = 1), двухместными (n = 2) и т. д. 9. Что называют вектором истинности логической функции? Табличным называют способ задания логических функций, при котором все возможные наборы значений ее переменных, упорядоченные по возрастанию их порядковых номеров, располагают слева, а значения, которые принимает на них функция f, помещают в правом столбце, который называют вектором истинности функции. 10. Какие логические функции называют полностью определенными, а какие – частично определенными? Если логическая функция задана на всех возможных значениях ее переменных, то ее также называют полностью определенной. Состояние системы, описываемое данным набором переменных, физически не достижимо либо срабатывание соответствующей проектируемой системы не влияет на управляемый процесс, такие функции называют частично определенными. 11. Какие отображения называют элементарными логическими функциями? формульный способ задания, который практически реализуется, как и других математических дисциплинах, за счет использования выделенного ограниченного набора базовых функций, которые называют элементарными. 12. Какие существуют одноместные элементарные логические функции, не являющиеся константами? Одноместные функции, которые не являются константами. Обозначая переменную в них через х, получим два возможных вектора истинности: Функцию f1 называют тождественной. Обозначают: f1(х) = x. Тождественная функция сохраняет логическое значение переменной. Функцию f2 называют отрицанием (инверсией). Отрицание изменяет значение аргумента на противоположное 13. Каков смысл конъюнкции (логического умножения) и дизъюнкции (логического сложения) двух логических величин? Конъюнкция (логическое умножение) двух величин x и y. Она истинна только в том случае, когда истинны и x и y, т. е. x = у = И. Во всех других случаях функция ложна. Дизъюнкция (логическое сложение) двух переменных x и y ложна только в случае x = y = Л, во всех случаях – истинна. 14. Каков смысл логической функции “импликациия” (логическое следование)? Импликация (логическое следование) двух переменных x и y означает правильный способ вывода величины y из x, логическое следование y из x, подчиненность y по отношению к x 15. Каков смысл логических функций “эквивалентность” и“сложение по модулю 2 (строгое, исключающее сложение)”? Эквивалентность двух x и y означает, что значения x и y одинаковы: x = y. Сложение по модулю 2 (строгое, исключающее сложение). В отличие от нестрого логического сложения (дизъюнкции) данная функция ложна при x = y = И 16. Каков смысл логических функций Шеффера и Вебба? Функция Шеффера (штрих Шеффера, антиконъюнкция, НЕ-И) – функция, равная отрицанию конъюнкции. Функция ложна только в случае истинны обе ее переменные, т. е. x = y = И. Иначе функция истинна. Функция Вебба, антидизъюнкция, НЕ-ИЛИ) – функция, равная отрицанию дизъюнкции. Функция истинна только в случае ложности обеих ее переменных, при x = y = Л. Иначе функция ложна. 17. Какие символы называют логическими связками и какое существует соглашения о силе логических связок? Символы v,+,=, и тд обозначающие элементарные функции, называют логическими связками. Для упрощения общей структуры записей выражений, в которых, используются логические связки, общепринятыми являются следующие соглашения об их силе (если иное не задано скобками): 1) самая сильная связка, 2) вторая после отрицания, 3) равносильные, 4) самая слабая. 18 Какие функции называют пороговыми? Элементарными пороговыми называют такие функции одной или двух переменных, у которых значения в векторе истинности постоянны (все равны 0 либо все равны 1) на всех лексикографически упорядоченных наборах значений переменных, кроме одного из крайних - самого первого набора (0, 0, ..., 0) либо самого последнего - (1, 1, ..., 1) . На этом крайнем наборе функция ровно один раз (на всем векторе истинности) изменяет свое логическое значение (с 0 – на 1 или с 1 – на 0). 19. Какие отображения называют обобщенными пороговыми функциями? Обобщенными пороговыми называют следующие n-местные функции: 1) обобщенную конъюнкцию ( n x ), которая равна 1 при n x = (1, 1, ..., 1) и 0 на всех остальных наборах переменных; 2) обобщенную дизъюнкцию ( n x ), которая равна 0 при n x = (0, 0, ..., 0) и 1 на всех остальных наборах переменных; 3) обобщенную функцию Шеффера ( n x ), которая равна 0 при n x = (1, 1, ... , 1) и 1 на всех остальных наборах переменных; 4) обобщенную функцию Вебба ( n x ), которая равна 1 при n x = (0, 0, ... , 0) и 0 на всех остальных наборах переменных. 20. Записи какого вида называют логическими формулами? Логической формулой называют формальные записи следующего вида: а) символ x, где x понимается как логическая переменная; б) символ a, где a А понимается как логическая константа; в) F1, F2 – логические формулы; г) h(F1, …, Fn), где F1, …, Fn представляют собой логические формулы, а h обозначает обобщенную пороговую функцию. 21. Выяснить, будут ли задавать логические формулы следующие записи (В том случае, если будут - указать порядок выполнения действий, если не будут – указать, почему): а) z Ù Ú Øx; б) ØØz ® x; в) x Å (у Ø z); г) x Ú у | x Ù у; д) (x ¯ ØØу) | у Ù z? 22. Что понимают под функцией, реализуемой формулой? Каков простейший способ задания такой функции? Функцией, реализуемой формулой F, называют отображение значений логических переменных и констант, входящих в F, на множество значений E2. Обозначим ее f(F). Простейшим способом однозначного определения функции f(F) путем перечисления всех значений наборов ее переменных и соответствующих значений функции является таблица истинности. Так как она строится по заданной функции однозначно, то каждая формула F имеет единственную реализующую ее функцию f(F). 23. Что называют областью истинности функции? Множество наборов значений переменных (x, y, …), на которых функция f(x, y, …), реализующая формулу F(x, y, …), истинна (f(x, y, …) = 1), называют областью истинности формуы F(x, y, …). 24. Какова связь между логическими формулами и функциями? Логические формулы и функции следующим образом соотносятся друг с другом: 1) для конкретной формулы алгебры логики реализующая ее функция всегда определяется однозначно (т.е. ее вектор истинности функции в таблице истинности определяется единственным образом); 2) для функции, заданной, например, при помощи таблицы истинности, формула может быть построена неединственным образом (точнее - счетное множество формул). II. Практическое задание III. На основе лекционного материала подготовьте ответы на теоретические вопросы: 1. Какие логические формулы называют эквивалентными (равносильными)? Формулы F1 и F2 называют эквивалентными (равносильными), если совпадают (т.е. имеют одинаковые векторы истинности) функции f(F1) и f(F2), реализуемые ими. 2. Какими свойствами обладают векторы истинности функций у эквивалентных формул алгеброй логики? Наиболее употребительные на практике тавтологии с равенствами, которые задают правила для эквивалентных преобразований логических формул (не изменяющих их функций), называют законами алгебры логики. Рассмотрим их. 1. Коммутативные законы для элементарных функций сложения и умножения: x Ú y = y Ú x, x Ù y = y Ù x. 2. Ассоциативные законы сложения и умножения для тех же функций: (x Ú y) Ú z = x Ú (y Ú z) = x Ú y Ú z, (x Ù y) Ù z = x Ù (y Ù z) = x Ù y Ù z. 3. Дистрибутивные законы раскрытия скобок: x Ù (y Ú z) = x Ù y Ú x Ù z, x Ú y Ù z = (x Ú y) Ù (x Ú z) 4. Правила де Моргана внесения отрицания внутрь скобок: Ø(x Ù y) = Øx Ú Øу, Ø(x Ú y) = Øx Ù Øy. 5. Закон двойного отрицания:. ØØx = x 6. Идемпотентность (устранение дубликатов): х Úx = х, х.Ù х = х. 7. Правила поглощения: x Ú (x Ù у) = х, х Ù (х Ú у) = х. 8. Закон противоречия: х Ù.Ø х = 0. 9. Закон исключения третьего: х Ú Ø х = 1. 10. Операции с константами: x Ú 0 = х, , х Ú 1= 1, х Ù 0 = 0, хÙ 1 = 0 3. Какие формулы алгеброй логики называют тавтологиями, а какие - противоречиями? Тождественно истинные логические формулы называют тавтологиями. Тождественно ложными называют формулы, эквивалентные тождественному нулю. Это всегда ложные рассуждения. Их в логике также называют противоречиями. 4. Какие преобразования формул алгеброй логики называют эквивалентными? Эквивалентными называют такие преобразования формулы F1, при котором: 1) ее запись изменяется (обозначим ее новый вариант F2), но 2) но полученная новая формула F2 эквивалентна прежней F1, т. е. у реализуемых ими функций f(F1) и f(F2) векторы истинности совпадают. 5. Что называют законами алгебры логики? Наиболее употребительные на практике тавтологии с равенствами, которые задают правила для эквивалентных преобразований логических формул (не изменяющих их функций), называют законами алгебры логики. 6. Можно ли в законах алгебры логики менять местами правую и левую части? Справедливость законов, как и любых других равенств, сохраняется при перемене местами их правой и левой частей. 7. Что называют минимизацией формул ? Изменяются ли векторы истинности формул после их минимизации? Минимизацией формул называют такое эквивалентное сокращение их записи, при котором в ней уменьшается общее число символов переменных. 8. Что следует из того факта, что после минимизации логическая формула приведена к логическому значению а) 1 (И)? б) 0 (Л)? а) константа 1, в эом случае исходная формула – тавтология; б) константа 0, в эом случае исходная формула – противоречие. 9. Когда формулу называют дизъюнктивной нормальной формой (ДНФ), а когда - конъюнктивной нормальной формой (КНФ)? 1) дизъюнкция из конюънкций переменных либо их отрицаний (например Øx Ù Øу Ù z Ú y Ù Øz; x Ù y Ù z Ú Øx Ù Øz Ú Øу), этот вид формул называется дизъюнктивной нормальной формой (сокращенно – ДНФ); 2) конъюнкция из дизъюнкций переменных или их отрицаний (например, (Øx Ú Øу Ú z) Ù (y Ú Øz); (x Ú y Ú z) Ù (Øx ÚØz) Ù Øy) этот вид формул называется конъюнктивной нормальной формой (сокращенно – КНФ). 10. Что можно сказать о векторе истинности логической функции, если они приведены к ДНФ и КНФ и больше не допускают сокращений? В том случае, когда ДНФ и КНФ больше уже не допускают сокращений, то реализующие их функции обязательно содержат в векторе истинности и единичные, и нулевые значения, т.е. не являются константами. |