Эквивалентные преобразования логических выражений логические уравнения практическая

Преобразование логических выражений

Цель урока:

• Формирование умений преобразования логических выражений с помощью логических законов и правил преобразования.
• Развитие умений преодолевать трудности при решении логических задач.
• Воспитание воли и настойчивости для достижения конечных результатов.

Ход урока:

1. Организационный момент.

2. Проверка домашнего задания.

3. Практическая работа.

Даёт задание по корточкам упростить логические выражения. Отвечает на возникшие вопросы, направляет работу учащихся, проверяет правильность выполненных заданий.

Основные законы логики

• Закон исключения третьего

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

Свойства констант

Законы алгебры логики

А Ú В=В Ú А А&В=В&А

А Ú (В Ú С)= (А Ú В) Ú С

А Ú (В & С)= (А Ú В) &(AÚ С)

А & (В Ú С)= (А & В) Ú(A&С)

А Ú (А & В)=А А & (А Ú В)=А

• Законы де Моргана

Ø(А ÚВ)= Ø А&ØВ Ø(А &В)= Ø А Ú ØВ

Правила замены операций

АÞ В = ØА Ú B АÞ В = Ø BÞ A

• Эквивалентности

АÛВ = (А&B) Ú (ØA& ØB)

АÛВ = (А Ú Ø B) Ú (ØA Ú B)

АÛВ = (А Þ B) & (B Þ A)

Ответы для проверки:

1.Упростите логические выражения:

а) ;

b) ;

2. Какая из формул является тождественно истинной, а какая тождественно ложной? a) ;(тождественно ложная логическая формула)

b) (Тождественно истинная логическая формула)

3. Какие два из четырёх высказываний эквивалентны?

Ответ:

4. Домашнее задание. Итог урока

Задачи для домашнего решения:

Лабораторно-практическая работа на тему «Преобразование логических выражений»

Обращаем Ваше внимание, что в соответствии с Федеральным законом N 273-ФЗ «Об образовании в Российской Федерации» в организациях, осуществляющих образовательную деятельность, организовывается обучение и воспитание обучающихся с ОВЗ как совместно с другими обучающимися, так и в отдельных классах или группах.

Практическая работа № 16

«Преобразование логических выражений»

Цель работы: изучить основы алгебры логики

Образовательные результаты, заявленные во ФГОС третьего поколения:

— формулировать задачи логического характера и применять средства математической логики для их решения.

— основные принципы математической логики, теории множеств и теории алгоритмов;

— формулы алгебры высказываний;

— методы минимизации алгебраических преобразований.

Краткие теоретические и учебно-методические материалы по теме практической работы

Алгебра логики – это раздел математики, изучающий высказывания, рассматриваемые со стороны их логических значений (истинности или ложности) и логических операций над ними.

Логическое высказывание – это любое повествовательное предложение, в отношении которого можно однозначно сказать, истинно оно или ложно.

Пример 1. «3 – простое число» является высказыванием, поскольку оно истинно.

Не всякое предложение является логическим высказыванием.

Пример 2. Предложение «Давайте пойдем в кино» не является высказыванием.

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

Высказывательная форма – это повествовательное предложение, которое прямо или косвенно содержит хотя бы одну переменную и становится высказыванием, когда все переменные замещаются своими значениями.

Пример 3. «x+2>5» — высказывательная форма, которая при x>3 является истинной, иначе ложной.

Алгебра логики рассматривает любое высказывание только с одной точки зрения – является ли оно истинным или ложным. Слова и словосочетания «не», «и», «или», «если. то», «тогда и только тогда» и другие позволяют из уже заданных высказываний строить новые высказывания. Такие слова и словосочетания называются логическими связками.

Высказывания, образованные из других высказываний с помощью логических связок, называются составными (сложными). Высказывания, которые не являются составными, называются элементарными (простыми).

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

Чтобы обращаться к логическим высказываниям, им назначают имена.

Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение (таблица1.1).

Таблица 1.1 — Основные логические операции

Операция, выражаемая словом «не», называется отрицанием и обозначается чертой над высказыванием (или знаком ¬). Высказывание ¬А истинно, когда A ложно, и ложно, когда A истинно.

Операция, выражаемая связкой «и», называется конъюнкцией (лат. conjunctio – соединение) или логическим умножением и обозначается точкой « • » (может также обозначаться знаками или &). Высказывание А • В истинно тогда и только тогда, когда оба высказывания А и В истинны.

Операция, выражаемая связкой «или» (в неисключающем смысле этого слова), называется дизъюнкцией (лат. disjunctio – разделение) или логическим сложением и обозначается знаком (или плюсом). Высказывание А В ложно тогда и только тогда, когда оба высказывания А и В ложны.

Операция, выражаемая связками «если …, то», «из … следует», «. влечет …», называется импликацией(лат. implico – тесно связаны) и обозначается знаком → . Высказывание А→В ложно тогда и только тогда, когда А истинно, а В ложно.

Операция, выражаемая связками «тогда и только тогда», «необходимо и достаточно», «. равносильно …», называется эквиваленцией или двойной импликацией и обозначается знаком ↔ или

. Высказывание А↔В истинно тогда и только тогда, когда значения А и В совпадают.

Операция, выражаемая связками «Либо … либо», называется исключающее ИЛИ или сложением по модулю 2 и обозначается XOR или . Высказывание А В истинно тогда и только тогда, когда значения А и В не совпадают.

Импликацию можно выразить через дизъюнкцию и отрицание: .

Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию: .

Исключающее ИЛИ можно выразить через отрицание, дизъюнкцию и конъюнкцию: .

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

Порядок выполнения логических операций задается круглыми скобками. Приоритет выполнения: отрицание, конъюнкция, дизъюнкция, исключающее или, импликация и эквиваленция.

Логическая формула — это символическая запись высказывания, состоящая из логических величин (констант или переменных), объединенных логическими операциями (связками).

Логическая функция — это функция логических переменных, которая может принимать только два значения: 0 или 1. В свою очередь, сама логическая переменная (аргумент логической функции) тоже может принимать только два значения: 0 или 1.

Пример 4. – логическая функция двух переменных A и B.

Значения логической функции для разных сочетаний значений входных переменных – или, как это иначе называют, наборов входных переменных – обычно задаются специальной таблицей. Такая таблица называется таблицей истинности.

Приведем таблицу истинности основных логических операций (таблица 1.2)

Пример 5. Составить таблицу истинности для формулы И–НЕ, которую можно записать так: .

1. Определить количество строк:

На входе два простых высказывания: А и В, поэтому n=2 и количество строк =2 2 +1=5.

2. Определить количество столбцов:

Выражение состоит из двух простых выражений (A и B) и двух логических операций (1 инверсия, 1 конъюнкция), т.е. количество столбцов таблицы истинности = 4.

3. Заполнить столбцы с учетом таблиц истинности логических операций (таблица 1.3).

Таблица 1.3. Таблица истинности для логической операции

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

Существует три базовых логических элемента, которые реализуют три основные логические операции :

логический элемент «И» – логическое умножение – конъюнктор;

логический элемент «ИЛИ» – логическое сложение – дизъюнктор;

логический элемент «НЕ» – инверсию – инвертор.

Алгоритм построения логических схем.

Определить число логических переменных.

Определить количество логических операций и их порядок.

Изобразить для каждой логической операции соответствующий ей логический элемент.

Соединить логические элементы в порядке выполнения логических операций.

Пример 6. По заданной логической функции построить логическую схему.

Число логических переменных = 2 (A и B).

Количество операций = 5 (2 инверсии, 2 конъюнкции, 1 дизъюнкция). Сначала выполняются операции инверсии, затем конъюнкции, в последнюю очередь операция дизъюнкции.

Схема будет содержать 2 инвертора, 2 конъюнктора и 1 дизъюнктор.

Построение надо начинать с логической операции, которая должна выполняться последней. В данном случае такой операцией является логическое сложение, следовательно, на выходе должен быть дизъюнктор. На него сигналы подаются с двух конъюнкторов, на которые, в свою очередь, подаются один входной сигнал нормальный и один инвертированный (с инверторов).

Логические законы и правила преобразования логических выражений

Если две формулы А и В одновременно, то есть при одинаковых наборах значений входящих в них переменных, принимают одинаковые значения, то они называются равносильными.

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

1. Закон двойного отрицания: ;

2. Переместительный (коммутативный) закон:

для логического сложения: ;

для логического умножения: ;

3. Сочетательный (ассоциативный) закон:

для логического сложения: ;

для логического умножения: ;

4. Распределительный (дистрибутивный) закон:

для логического сложения: ;

для логического умножения: ;

5. Законы де Моргана:

для логического сложения: ;

для логического умножения: ;

6. Закон идемпотентности:

для логического сложения: ;

для логического умножения: ;

7. Законы исключения констант:

для логического сложения: ;

для логического умножения: ;

8. Закон противоречия: ;

9. Закон исключения третьего: ;

10. Закон поглощения:

для логического сложения: ;

для логического умножения: ;

11. Правило исключения импликации: ;

12. Правило исключения эквиваленции: .

Справедливость этих законов можно доказать составив таблицу истинности выражений в правой и левой части и сравнив соответствующие значения.

Основываясь на законах, можно выполнять упрощение сложных логических выражений. Такой процесс замены сложной логической функции более простой, но равносильной ей, называется минимизацией функции.

Пример 7. Упростить логическое выражение .

Согласно закону де Моргана: .

Согласно сочетательному закону: .

Согласно закону противоречия и закону идемпотентности: .

Согласно закону исключения 0:

Окончательно получаем /

Задания для практического занятия:

1. Составить таблицу истинности логического выражения

2. Построить логическую схему функции

3. Упростить логическое выражение

4. Определить, являются ли два высказывания эквивалентными A & ¬(¬B v C) и A & B & ¬C

5. Определить истинность или ложность высказываний (¬(X

1. Составить таблицу истинности логического выражения

2. Построить логическую схему функции

3. Упростить логическое выражение

4. Определить, являются ли два высказывания эквивалентными ¬(¬ A & B v A & ( B v ¬ C )) и ¬ B & (¬ A v C )

5. Определить истинность или ложность высказываний (¬(X

1. Составить таблицу истинности логического выражения

2. Построить логическую схему функции

3. Упростить логическое выражение

4. Определить, являются ли два высказывания эквивалентными ¬ C v ¬ B v ¬( A v ¬ C ) и ¬ A & B v ¬ C & B

5. Определить истинность или ложность высказываний X>1 & (¬(X

1. Составить таблицу истинности логического выражения

2. Построить логическую схему функции

3. Упростить логическое выражение

4. Определить, являются ли два высказывания эквивалентными ¬(А v ¬В) v ¬ B & C и ¬ A & ( B ∨ C )

5. Определить истинность или ложность высказываний ¬((X>2) v (X 4) при X=1

1. Составить таблицу истинности логического выражения .

2. Построить логическую схему функции

3. Упростить логическое выражение

4. Определить, являются ли два высказывания эквивалентными

5. Определить истинность или ложность высказываний X>1 & (¬(X

Что такое высказывание (приведите пример)?

Что такое составное высказывание (приведите пример)?

Укажите приоритеты выполнения логических операций.

Составьте таблицу истинности для следующих операций: отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция.

Изобразите функциональные элементы: конъюнктор, дизъюнктор, инвертор.

Какие логические выражения называются равносильными?

Информатика. 10 класс

Конспект урока

Информатика, 10 класс. Урок № 12.

Тема — Преобразование логических выражений

Перечень вопросов, рассматриваемых в теме: основные законы алгебры логики, преобразование логических выражений, логические функции, построение логического выражения с данной таблицей истинности и его упрощение, дизъюнктивная и конъюнктивная нормальная форма, совершенная дизъюнктивная нормальная форма (СДНФ), совершенная конъюнктивная нормальная форма (СКНФ).

Глоссарий по теме: основные законы алгебры логики, логические функции, дизъюнктивная и конъюнктивная нормальная форма, совершенная дизъюнктивная нормальная форма (СДНФ), совершенная конъюнктивная нормальная форма (СКНФ)

Основная литература по теме урока:

Л. Л. Босова, А. Ю. Босова. Информатика. Базовый уровень: учебник для 10 класса

— М.: БИНОМ. Лаборатория знаний, 2017 (с.197—209)

Открытые электронные ресурсы по теме:

Теоретический материал для самостоятельного изучения.

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

Основные законы алгебры логики

Справедливость законов можно доказать построением таблиц истинности.

Пример 1. Упростим логическое выражение

Последовательно применим дистрибутивный закон и закон исключенного третьего:

В общем случае можно предложить следующую последовательность действий:

1. Заменить операции строгая дизъюнкция, импликация, эквиваленция на их выражения через операции конъюнкция, дизъюнкция, инверсия;
2. Раскрыть отрицания сложных выражений по законам де Моргана.
3. Используя законы алгебры логики, упростить выражение.

Пример 2. Упростим логическое выражение .

Здесь последовательно использованы замена операции импликация, закон де Моргана, распределительный закон, закон противоречия и операция с константой, закон идемпотентности и поглощения.

Аналогичные законы выполняются для операции объединения, пересечения и дополнения множеств. Например:

Пример 3. На числовой прямой даны отрезки B = [2;12] и C = [7;18]. Каким должен быть отрезок A, чтобы предикат становился истинным высказыванием при любых значениях x.

Преобразуем исходное выражение, избавившись от импликации:

A, B, C — множества. Для них можно записать (U — универсальное множество).

Будем считать, что.

Тогда , причем это минимально возможное множество А.

Так как множество B — это отрезок [2;12], а множество — это промежутки и, то пересечением этих множеств будет служить промежуток . В качестве ответа мы можем взять этот промежуток, а также любой другой, его включающий.

Пример 4. Для какого наименьшего неотрицательного целого десятичного числа а выражение

тождественно истинно (т. е. принимает значение 1 при любом неотрицательном целом значении десятичной переменной х)? Здесь & — поразрядная конъюнкция двух неотрицательных целых десятичных чисел.

Перепишем исходное выражение в наших обозначениях и преобразуем его:

Рассмотрим предикат . В числе 28₁₀=11100₂ 4-й, 3-й и 2-й биты содержат единицы, а 1-й и 0-й — нули. Следовательно, множеством истинности этого предиката являются такие числа х, у которых хотя бы один из битов с номерами 4, 3 или 2 содержит единицу. Если и 4-й, и 3-й, и 2-й биты числа х нулевые, то высказывание будет ложным.

Рассмотрим предикат . В числе 45₁₀=101101₂ 5-й, 3-й, 2-й и 0-й биты содержат единицы, 4-й и 1-й — нули. Следовательно, множеством истинности этого предиката являются такие числа х, у которых хотя бы один из битов с номерами 5, 3, 2 или 0 содержит единицу. Если и 5-й, и 3-й, и 2-й, и 0-й биты числа х нулевые, то высказывание будет ложным.

Рассмотрим предикат . В числе 17₁₀=10001₂ 3-й, 2-й и 1-й биты содержат нули, 4-й и 0-й — единицы. Побитовая конъюнкция 17 и х будет равна 0, если в числе х 4-й и 0-й биты будут содержать нули. Множество истинности этого предиката — все х с нулями в 4-м и 0-м битах.

По условию задачи надо, чтобы .

Запишем это выражение для рассмотренных множеств истинности:

Так как , примем .

Объединением множеств M и N являются все двоичные числа, у которых хотя бы один из битов с номерами 5, 4, 3, 2, 0 содержит единицу. Пересечением этого множества с множеством K будут все двоичные числа, у которых биты с номерами 4 и 0 будут заняты нулями, т.е. такие двоичные числа, у которых хотя бы один из битов с номерами 5, 3, 2 содержит 1. Все эти числа образуют множество А.

Искомое число a должно быть таким, чтобы при любом неотрицательном целом значении переменной х: , и, кроме того, оно должно быть минимальным из возможных. Этим условиям удовлетворяет число 101100₂ = 44₁₀.

Значение любого логического выражения определяется значениями входящих в него логических переменных. Тем самым логическое выражение может рассматриваться как способ задания логической функции.

Совокупность значений n аргументов удобно интерпретировать как строку нулей и единиц длины n. Существует ровно различных двоичных строк длины n. Так как на каждой такой строке некая функция может принимать значение 0 или 1, общее количество различных булевых функций от n аргументов равно .

Для n=2 существует 16 различных логических функций. Рассмотрим их подробнее.