Методика преподавания раздела "Основы логики" в профильных курсах информатики

Тема. Булева алгебра.  ДНФ. Основные законы и правила  преобразования логических выражений.

Цель урока. Познакомить учащихся с основными законами булевой алгебры и научить их применять эти законы.

Ход урока

I. Проверка и обсуждение домашнего задания и самостоятельной работы.

II. Объяснение нового материала

Существуют наборы логических функций, с помощью которых можно выразить любые другие логические функции. Такие наборы называются функционально полными наборами или базисами. Наиболее известный и изученный базис - набор "И", "ИЛИ", "НЕ". Множество всех логических функций, на котором определены эти три операции называется булевой алгеброй; операции и формулы булевой алгебры также часто называют булевыми. (В 1847 году английский математик Джордж Буль разработал алгебру логики).

Любую функцию алгебры логики можно представить только через три операции: конъюнкцию, дизъюнкцию и инверсию. Это происходит посредством представления логической формулы либо в дизъюнктивно-нормальной, либо в конъюнктивно-нормальной форме.

Дизъюнктивно-нормальной формой (ДНФ) формулы алгебры высказываний называется формула, если она представлены в виде дизъюнкции конъюнкций элементарных высказываний и их отрицаний.

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

A → B = ¬A + B

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

A ≡ B = (¬A + B) · (¬B + A).

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

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

Метод перехода: Для каждого набора значений переменных х₁, ..., х_n на котором функция f (х₁, ..., х_n) равна 1, выписывается конъюнкция всех переменных; над теми переменными, которые в этом наборе равны 0, ставятся отрицания; все такие конъюнкции соединяются знаками дизъюнкции.

Полученная формула называется  дизъюнктивной нормальной формой (ДНФ) логической функции f (х₁, ..., х_n).

Например                   

Y = ¬A · ¬B · ¬C + ¬A · ¬B · C + A · ¬B · ¬C + A · ¬B · C

ДНФ обычно весьма громоздкая формула. Упрощение формул в булевой алгебре производится на основе эквивалентных преобразований, опирающихся на основные законы булевой алгебры:

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

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

Используя законы булевой алгебры, упростим логическое выражение, которое мы получили в предыдущем примере:

Y = ¬A · ¬B · ¬C + ¬A · ¬B · C + A · ¬B · ¬C + A · ¬B · C = ¬А · ¬В · (¬С + С) + А · ¬В · (¬С + С) = ¬А · ¬В + А · ¬В = ¬В · (¬А + А) = ¬В

Пример: упростим логическое выражение, обозначенное В

Воспользуемся законом де Моргана для логического сложения и законом двойного отрицания:
.
Согласно распределительному закону для логического сложения:
.
Выполним операцию над переменной А и ее инверсией, а также операцию с константой 1 и получим

III. Закрепление материала

2. По таблице истинности составить формулы для Y1 и Y2 и упростить их:

Ответ: Y1 = ¬C

Y2 = ¬B · (¬A +¬C)

IV. Домашнее задание

1. §3.5;

2.  конспект;

3. №3.6;

4. по таблице истинности составить формулы для Y1 и Y2 и упростить их:

На главную  Уроки