Методическая разработка. Алгебра логики
методическая разработка по информатике и икт (9 класс)

Методическая разработка. Алгебра логики.

Цели
1) ознакомить учащихся с законами алгебры логики;
2)    развивать логическое мышление;
3)    воспитывать интерес к предмету.    

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

1.    Закон двойного отрицания:
         ¬ ¬ А = А;
2.    Переместительный (коммутативный) закон:
-    для логического сложения:
A + B = B + A;    
-    для логического умножения:
A ∙ B = B ∙A.
В обычной алгебре a+b=b+a, ab=ba.

3.    Сочетательный (ассоциативный) закон:
-    для логического сложения:
( A + B ) + C = A + ( B + C );    
-    для логического умножения:
( A ∙ B ) ∙ C = A ∙ ( B ∙C).
В обычной алгебре (a+b)+c=a+(b+c)=a+b+c,
                (ab)c=a(bc)=abc. 
4.    Распределительный (дистрибутивный) закон:
-    для логического сложения:
( A + B ) ∙ C = ( A ∙ C ) + (B ∙ C );
-    для логического умножения:
( A ∙ B ) + C = ( A + C ) ∙ ( B + C ).
В обычной алгебре (a+b)c=ac+bc.
5.    Закон общей инверсии (законы де Моргана):
-    для логического сложения:
     ¬ (A+B)= ¬A∙¬B;
-    для логического умножения:
¬(A∙B)=¬A+¬B.
6.    Закон равносильности (идемпотентности – от лат. слов idem – тот же самый и potens – сильный):
-    для логического сложения:
     A+A=A;
-    для логического умножения:
A∙A=A
7.    Законы исключения констант:
-    для логического сложения: 
     A+1=1, A+0=A;
-    для логического умножения:
A∙1=A, A∙0=0.
8.    Закон противоречия:
A∙¬A=0. 
Невозможно, чтобы противоречивые высказывания были истинны одновременно.
9.    Закон исключенного третьего:
A+¬A=1. Из двух противоречивых высказываний одно истинно.
10.     Закон поглощения:
-    для логического сложения:
     A+ (A∙B)=A;
-    для логического умножения:
A∙ (A+B)=A;
11.     Закон исключения (склеивания):
-    для логического сложения:
     (A∙B) + (A∙¬B)=A;
-    для логического умножения:
(A+B) ∙ (A+¬B)=A.
12.     Закон контрапозиции (правило перевертывания):
 ( А =>B ) = (¬ B => ¬A). 
        а) A B=¬A+B; 
        б) A B=(A∙B) + (¬A∙¬B)= (¬A+B) ∙ (A+¬B)


Таблицу, показывающую какие значения принимает сложное высказывание при всех сочетаниях (наборах) значений, входящих в него простых высказываний, называют таблицей истинности сложного высказывания.
    Сложные высказывания часто называют формулами логики высказываний.
Логические операции имеют следующий приоритет:
1.    Действия в скобках
2.    Инверсия
3.    Конъюнкция
4.    Дизъюнкция
5.    Импликация
6.    Эквивалентность

 Алгоритм построения ТИ.
1.    Подсчитать количество переменных n в формуле;
2.    Определить число строк в таблице m=2 в степени m;
3.    Подсчитать количество логических операций в формуле;
4.    Установить последовательность выполнения логических операций с учетом скобок и приоритетов;
5.    Определить количество столбцов в таблице: n+число операций;
6.    Выписать наборы входных переменных с учетом того, что они представляют собой натуральный ряд n-разрядных двоичных чисел от 0 до 2n-1;
7.    Провести заполнение ТИ по столбцам, выполняя логические операции в соответствии с установленной в п.4 последовательностью.

Пример: Для формулы F=A˅ (B˄B˅C) построить ТИ (таблицу истинности)

Дополнение.
Наборы входных переменных во избежание ошибок иногда рекомендуют перечислять следующим образом:
а) определить количество наборов входных переменных;
б) разделить колонку значений первой переменной пополам и заполнить верхнюю часть колонки 0, а нижнюю – 1;
в) разделить колонку значений второй переменной
г) продолжать деление колонок значение последующих переменных на 8, 16 и т.д. частей и заполнение их группами 0 или 1 до тех пор, пока группы 0 и 1 не будут состоять из одного символа.
Задание для закрепления новой темы.
Построить таблицы истинности для следующих формул:

1.F=A˅ B˅ (B˄B˅C)

                               _

2.F=C˅ A˅ (F˄B˅C)

              _               _

3.F=A˅ A˅ (B˄B˅C)