оол. Лабораторная работа 2 алгебра логики время выполнения 4 часа. Цель работы Изучить основы алгебры логики
 Скачать 185.27 Kb.
|
ЛАБОРАТОРНАЯ РАБОТА № 2 АЛГЕБРА ЛОГИКИ Время выполнения – 4 часа. Цель работы Изучить основы алгебры логики. Задачи лабораторной работы В результате прохождения занятия студент должен: 1) знать: – определения основных понятий (простое и сложное высказывания, логические операции, логические выражения, логическая функция); – порядок выполнения логических операций; – алгоритм построения таблиц истинности; – схемы базовых логических элементов; – законы логики и правила преобразования логических выражений; 2) уметь: – применять загоны логики для упрощения логических выражений; – строить таблицы истинности; – строить логические схемы сложных выражений. Общие теоретические сведения Логической основой компьютера является алгебра логики, которая рассматривает логические операции над высказываниями. Алгебра логики – это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними. Логическое высказывание – это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно. Пример: «3 – простое число» является высказыванием, поскольку оно истинно. Не всякое предложение является логическим высказыванием. Пример: предложение «Давайте пойдем в кино» не является логическим высказыванием. Вопросительные и побудительные предложения логическими высказываниями не являются. Высказывательная форма – это повествовательное предложение, которое прямо или косвенно содержит хотя бы одну переменную и становится высказыванием, когда все переменные замещаются своими значениями. Пример. «x+2>5» – высказывательная форма, которая при x>3 является истинной, иначе ложной. Алгебра логики рассматривает любое высказывание только с одной точки зрения – является ли оно истинным или ложным. Слова и словосочетания «не», «и», «или», «если..., то», «тогда и только тогда» и другие позволяют из уже заданных высказываний строить новые высказывания. Такие слова и словосочетания называются логическими связками. Высказывания, образованные из других высказываний с помощью логических связок, называются составными (сложными). Высказывания, которые не являются составными, называются элементарными (простыми). Пример. Высказывание «Число 6 делится на 2» - простое высказывание. Высказывание «Число 6 делится на 2, и число 6 делится на 3» - составное высказывание, образованное из двух простых с помощью логической связки «и». Истинность или ложность составных высказываний зависит от истинности или ложности элементарных высказываний, из которых они состоят. Чтобы обращаться к логическим высказываниям, им назначают имена. Пример. Обозначим через А простое высказывание «число 6 делится на 2», а через В простое высказывание «число 6 делится на 3». Тогда составное высказывание «Число 6 делится на 2, и число 6 делится на 3» можно записать как «А и В». Здесь «и» – логическая связка, А, В – логические переменные, которые могут принимать только два значения – «истина» или «ложь», обозначаемые, соответственно, «1» и «0». Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение (табл. 1). Таблица 1. Основные логические операции Обозначение операции Читается Название операции Альтернативные обозначения ¬ НЕ Отрицание (инверсия) Черта сверху И Конъюнкция (логическое умножение) ∙ & ИЛИ Дизъюнкция (логическое сложение) + → Если … то Импликация ↔ Тогда и только тогда Эквиваленция XOR Либо …либо Исключающее ИЛИ (сложение по модулю 2) НЕ Операция, выражаемая словом «не», называется отрицанием и обозначается чертой над высказыванием (или знаком ¬). Высказывание ¬А истинно, когда A ложно, и ложно, когда A истинно. Пример. Пусть А=«Сегодня пасмурно», тогда ¬А=«Сегодня не пасмурно». И Операция, выражаемая связкой «и», называется конъюнкцией (лат. conjunctio – соединение) или логическим умножением и обозначается знаком (может также обозначаться знаком & или точкой « · »). Высказывание А В истинно тогда и только тогда, когда оба высказывания А и В истинны. Пример. Высказывание «Число 6 делится на 2, и число 6 делится на 3» - истинно, а высказывание «Число 6 делится на 2, и число 6 больше 10» - ложно. ИЛИ Операция, выражаемая связкой «или» (в неисключающем смысле этого слова), называется дизъюнкцией (лат. disjunctio – разделение) или логическим сложением и обозначается знаком (или плюсом). Высказывание А В ложно тогда и только тогда, когда оба высказывания А и В ложны. Пример. Высказывание «Число 6 делится на 2 или число 6 больше 10» - истинно, а высказывание «Число 6 делится на 5 или число 6 больше 10» - ложно. ЕСЛИ … ТО Операция, выражаемая связками «если …, то», «из … следует», «... влечет …», называется импликацией (лат. implico – тесно связаны) и обозначается знаком → . Высказывание А→В ложно тогда и только тогда, когда А истинно, а В ложно. Пример. Высказывание «если студент сдал все экзамены на «отлично», то он получит стипендию». Очевидно, эту импликацию следует признать ложной лишь в том случае, когда студент сдал на «отлично» все экзамены, но стипендии не получил. В остальных случаях, когда не все экзамены сданы на «отлично» и стипендия получена (например, в силу того, что студент проживает в малообеспеченной семье) либо когда экзамены вообще не сданы и о стипендии не может быть и речи, импликацию можно признать истинной. РАВНОСИЛЬНО Операция, выражаемая связками «тогда и только тогда», «необходимо и достаточно», «... равносильно …», называется эквиваленцией или двойной импликацией и обозначается знаком ↔ или . Высказывание А↔В истинно тогда и только тогда, когда значения А и В совпадают. Пример. Высказывание «Число является четным тогда и только тогда, когда оно делится без остатка на 2» является истинным, а высказывание «Число является нечетным тогда и только тогда, когда оно делится без остатка на 2» - ложно. ЛИБО … ЛИБО Операция, выражаемая связками «Либо … либо», называется исключающее ИЛИ или сложением по модулю 2 и обозначается XOR или . Высказывание АВ истинно тогда и только тогда, когда значения А и В не совпадают. Пример. Высказывание «Число 6 либо нечетно либо делится без остатка на 2» является истинным, а высказывание «Либо число 6 четно либо число 6 делится на 3» – ложно, так как истинны оба высказывания входящие в него. Замечание. Импликацию можно выразить через дизъюнкцию и отрицание: A → B= ¬ A ∨ B Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию: A ↔ B=(¬A∨B )∧(¬B∨A) Исключающее ИЛИ можно выразить через отрицание, дизъюнкцию и конъюнкцию: A XOR B=(¬A∧B)∨(¬B&A ) Вывод. Операций отрицания, дизъюнкции и конъюнкции достаточно, чтобы описывать и обрабатывать логические высказывания. Порядок выполнения логических операций задается круглыми скобками. Но для уменьшения числа скобок договорились считать, что сначала выполняется операция отрицания («не»), затем конъюнкция («и»), после конъюнкции – дизъюнкция («или») и исключающего или и в последнюю очередь – импликация и эквиваленция. С помощью логических переменных и символов логических операций любое высказывание можно формализовать, то есть заменить логической формулой (логическим выражением). Логическая формула – это символическая запись высказывания, состоящая из логических величин (констант или переменных), объединенных логическими операциями (связками). Логическая функция – это функция логических переменных, которая может принимать только два значения: 0 или 1. В свою очередь, сама логическая переменная (аргумент логической функции) тоже может принимать только два значения: 0 или 1. Пример. F (A,B )=A&B∨A – логическая функция двух переменных A и B. Значения логической функции для разных сочетаний значений входных переменных – или, как это иначе называют, наборов входных переменных – обычно задаются специальной таблицей. Такая таблица называется таблицей истинности. Приведем таблицу истинности основных логических операций (табл. 2) Таблица 2. A B ¬ A A &B A∨ B A → B A ↔ B A X O R B 1 1 0 1 1 1 1 0 1 0 0 0 1 0 0 1 0 1 1 0 1 1 0 1 0 0 1 0 0 1 1 0 Опираясь на данные таблицы истинности основных логических операций можно составлять таблицы истинности для более сложных формул. Алгоритм построения таблиц истинности для сложных выражений: 1. Определить количество строк: – количество строк = 2 n + строка для заголовка, – n - количество простых высказываний. 2. Определить количество столбцов: количество столбцов = количество переменных + количество логических операций; – определить количество переменных (простых выражений); – определить количество логических операций и последовательность их выполнения. 3. Заполнить столбцы результатами выполнения логических операций в обозначенной последовательности с учетом таблиц истинности основных логических операций. Пример. Составить таблицу истинности для формулы И–НЕ, которую можно записать так: ¬( A&B) 1. Определить количество строк: На входе два простых высказывания: А и В, поэтому n=2 и количество строк =2 2 +1=5. 2. Определить количество столбцов: Выражение состоит из двух простых выражений (A и B) и двух логических операций (1 инверсия, 1 конъюнкция), т.е. количество столбцов таблицы истинности = 4. 3. Заполнить столбцы с учетом таблиц истинности логических операций (табл. 3). Таблица 3. Таблица истинности для логической операции ¬( A&B) A B A &B ¬( A&B) 1 1 1 0 1 0 0 1 0 1 0 1 0 0 0 1 Подобным образом можно составить таблицу истинности для формулы ИЛИ–НЕ, которую можно записать так: ¬( A∨B ) Таблица 4. Таблица истинности для логической операции ¬( A∨B ) A B A∨ B ¬( A∨B ) 1 1 1 0 1 0 1 0 0 1 1 0 0 0 0 1 Примечание: И–НЕ называют также «штрих Шеффера» (обозначают | ) или «антиконъюнкция»; ИЛИ–НЕ называют также «стрелка Пирса» (обозначают ↓) или «антидизъюнкция». Пример. Составить таблицу истинности логического выражения C = ¬ A &B ∨ A & ¬ B Решение: 1. Определить количество строк: На входе два простых высказывания: А и В, поэтому n=2 и количество строк=2 2 +1= 5. 2. Определить количество столбцов: Выражение состоит из двух простых выражений (A и B) и пяти логических операций (2 инверсии, 2 конъюнкции, 1 дизъюнкция), т.е. количество столбцов таблицы истинности = 7. Сначала выполняются операции инверсии, затем конъюнкции, в последнюю очередь операция дизъюнкции. 3. Заполнить столбцы с учетом таблиц истинности логических операций (табл. 5). Таблица 5. Таблица истинности для логической операции C = ¬ A &B ∨ A & ¬ B A B ¬ A ¬ B ¬ A &B A & ¬ B C 1 1 0 0 0 0 0 1 0 0 1 0 1 1 0 1 1 0 1 0 1 0 0 1 1 0 0 0 Логические формулы можно также представлять с помощью языка логических схем. Существует три базовых логических элемента, которые реализуют три основные логические операции: логический элемент «И» – логическое умножение – конъюнктор; логический элемент «ИЛИ» – логическое сложение – дизъюнктор; логический элемент «НЕ» – инверсию – инвертор. конъюнктор дизъюнктор инвертор Поскольку любая логическая операция может быть представлена в виде комбинации трех основных, любые устройства компьютера, производящие обработку или хранение информации, могут быть собраны из базовых логических элементов, как из “кирпичиков”. Логические элементы компьютера оперируют с сигналами, представляющими собой электрические импульсы. Есть импульс – логический смысл сигнала – 1, нет импульса – 0. На входы логического элемента поступают сигналы-значения аргументов, на выходе появляется сигнал-значение функции. Преобразование сигнала логическим элементом задается таблицей состояний, которая фактически является таблицей истинности, B & A A & B B A A 1 B A A соответствующей логической функции, только представлена в форме логических схем. В такой форме удобно изображать цепочки логических операций и производить их вычисления. Алгоритм построения логических схем. 1. Определить число логических переменных. 2. Определить количество логических операций и их порядок. 3. Изобразить для каждой логической операции соответствующий ей логический элемент. 4. Соединить логические элементы в порядке выполнения логических операций. Пример. По заданной логической функции F (A,B )=¬A&B∨A&¬B построить логическую схему. Решение. 1. Число логических переменных = 2 (A и B). 2. Количество операций = 5 (2 инверсии, 2 конъюнкции, 1 дизъюнкция). Сначала выполняются операции инверсии, затем конъюнкции, в последнюю очередь операция дизъюнкции. 3. Схема будет содержать 2 инвертора, 2 конъюнктора и 1 дизъюнктор. 4. Построение надо начинать с логической операции, которая должна выполняться последней. В данном случае такой операцией является логическое сложение, следовательно, на выходе должен быть дизъюнктор. На него сигналы подаются с двух конъюнкторов, на которые, в свою очередь, подаются один входной сигнал нормальный и один инвертированный (с инверторов). Задания 1. Составить таблицу истинности логического выражения C. Варианты задания: № варианта C 1 (¬( A&B ))↔( A∨¬B ) XOR A 2 ( A&B)↔(¬A&B) XOR B 3 ( A&B)↔(¬B →¬A ) XOR A 4 ¬( A∨B )↔(¬A&¬B ) XOR B 5 ( A∨ B)↔¬( A&¬B ) XOR B 6 ¬( A&B)↔(¬ A∨B ) XOR A 7 ¬( A→ B)↔(¬ A∨B ) XOR A 8 (¬ A&B )↔(¬B→ A ) XOR B 9 ( A∨¬B)↔ ¬(B&A ) XOR A 10 (¬ B&A )↔( A→¬B ) XOR B 11 (¬ A∨¬B )↔ (¬B&A ) XOR A 12 (¬ B→¬A)↔( A∨B) XOR B 13 ¬( B∨ A)↔(¬A→ B ) XOR A 14 (¬( A&B))↔(¬A→ B) XOR B 15 (¬ A→¬B )↔(B&A ) XOR B 16 (¬ A∨¬B )↔ ( B∨¬A) XOR A 2. Построить логическую схему функции F(A,B). Варианты задания: № варианта F(A,B) 1 ¬ (A & B) ∨ (¬(B ∨ A)) 2 ¬ (A ∨ B) & (A & ¬B) 3 ¬ (A ∨ B) & (A ∨ ¬B) 4 ¬ ((¬A ∨ B) & (¬B ∨ A)) 5 (¬A ∨ B) & (¬B ∨ ¬A) 6 (¬A ∨ B) & ¬(A ∨ ¬B) 7 ¬ (¬A & ¬B) ∨ (A ∨ B) 8 (¬A ∨ B) ∨ ¬(A & B) 9 (A & B) ∨ ((A ∨ B) ∨ ¬A) 10 ¬ ((¬A ∨ B) & A) & ¬B 11 ¬ (A ∨ ¬B) ∨ ¬(A ∨ B) 12 ¬ A & ¬B ∨ ¬(A ∨ B) 13 ¬ A ∨ B ∨ ¬(¬B ∨ A) 14 (¬A & ¬B) ∨ (¬A & B) 15 (¬A & B) ∨ (A & ¬B) 16 ¬ (A & (B ∨ A) ∨ ¬B) 3. Составить таблицу истинности и логическую схему для функции X. № варианта D 1 X = ¬(¬A ∨ B) ∨ A ∨ ¬B & C 2 X = ¬(C ∨ B) & A ∨ ¬B∨ ¬C 3 X = A ∨ ¬B & A ∨ (¬A ∨ C) 4 X = ¬(¬A & ¬B) ∨ (A ∨ ¬B) & C 5 X = ¬A ∨ (B ∨ A ∨ ¬B) & C 6 X = ¬A ∨ B ∨ C ∨ ¬B & A 7 X = ¬(¬A ∨ B ∨ C) ∨ ¬B ∨ ¬C 8 X = ¬(C ∨ B) & A ∨ ¬B & A 9 X = ¬(¬A ∨ B) ∨ A ∨ ¬B & ¬C 10 X = ¬C ∨ A ∨ A ∨ ¬B & C 11 X = ¬(¬A ∨ B) & C ∨ ¬B ∨ A 12 X = ¬A ∨ C & A ∨ ¬B & ¬C 13 X = ¬(¬A ∨ B) ∨ A ∨ ¬B ∨ C 14 X = ¬(A ∨ B) & C ∨ ¬B & B 15 X = ¬(¬B & A) ∨ A ∨ ¬B ∨ C 16 X = ¬(¬A ∨ C) ∨ A ∨ ¬A & ¬B 4. Определить, являются ли два высказывания эквивалентными. 1 А & (¬А ∨ B) A∨В 2 ¬(X∨¬Y) ∨¬Y & Z ¬X & (Y∨Z) 3 А & (В ∨ С) (A ∨ В) & (A ∨ С) 4 ¬(¬A & B ∨ A & (B ∨ ¬C)) ¬B & (¬A ∨ C) 5 ¬ (A & B) & ¬C ¬A ∨ B ∨ ¬C 6 ¬ (¬A ∨ B) ∨ ¬C (A & ¬B) ∨ ¬C 7 ¬(A ∨ ¬ B ∨ C) ¬A & B & ¬C 8 A ∨ (¬A & В) A & B 9 A & ¬ (¬B ∨ C) A & B & ¬C 10 A ∨ (В & С) (А & В) ∨ (А & С) 11 ¬ (A & B) & ¬C (¬A ∨ ¬B) & ¬C 12 ¬ (¬A ∨ B) ∨ ¬C ¬A ∨ B ∨ ¬C 13 ¬ C ∨ ¬ B ∨ ¬ (A ∨ ¬ C) ¬ A & B ∨ ¬ C & B 14 ¬(A ∨ ¬ B ∨ C) A & ¬B & C 15 ¬ C ∨ ¬ B ∨ ¬ (A ∨ ¬ C) ¬ A & ¬ B ∨ ¬ C 16 A & ¬ (¬B ∨ C) A & ¬B & ¬C 5. Определить истинность или ложность высказываний. 1 (X>4) & ¬ (X>1) & (X>4) при Х=1 2 X>1 & (¬ (X<5) & (X<3)) при Х=2 3 ¬((X>3) & (X<3)) & (X<1) при Х=3 4 (X>4) & ¬(X>1) & (X>4) при Х=4 5 (¬(X < 5) & (X < 3)) & (¬ (X< 2) & (X < 1)) при Х=1 6 ¬(¬(X>2) & (X>3)) при Х=2 7 (X>4) ∨ ¬(X>1) ∨ (X>4) при Х=3 8 ¬((X>2) ∨ (X<2)) ∨ (X>4) при Х=4 9 (X>4) ∨ ¬(X>1) ∨ (X>4) при Х=1 10 ¬((X>3) ∨ (X<3)) ∨ (X<1) при Х=2 11 (¬(X < 5) ∨ (X < 3)) & (¬ (X< 2) ∨ (X < 1)) при Х=3 12 X>1 & (¬ (X<5) ∨ (X<3)) при Х=4 13 ¬((X>2) ∨ (X<2)) ∨ (X>4) при Х=1 14 X>1 & (¬ (X<5) ∨ (X<3)) при Х=2 15 ¬(¬(X>2) ∨ (X>3)) при Х=3 16 ¬((X>3) ∨ (X<3)) ∨ (X<1) при Х=4 Контрольные вопросы 1. Что такое логическое высказывание? Приведите примеры истинных и ложных высказываний. 2. Что такое составное логическое высказывание (приведите примеры)? 3. Как называются и как обозначаются следующие логические операции: ИЛИ, НЕ, И, ЕСЛИ … ТО, ТОГДА И ТОЛЬКО ТОГДА, ЛИБО …ЛИБО? 4. Укажите приоритеты выполнения логических операций. 5. Составьте таблицу истинности для следующих операций: отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция, исключающее или. 6. Изобразите функциональные элементы: конъюнктор, дизъюнктор, инвертор. 7. По поисковым запросам было найдено определенное количество страниц. По запросу «Информатика или Алгебра» найдено 7300 страниц, по запросу «Информатика» – 4800, по запросу «Алгебра» – 4500. Какое количество страниц будет найдено по запросу Информатика & Алгебра? 8. Для каких значений числа X приведенное логическое высказывание ((X<5)→(X<3)) & ((X< 2)→(X<1)) будет истинно? |