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

 (A v B)& C = (A& C) v (B& C); — для логического сложения

 (A& B) v C = (A v C)& (B v C). — для логического умножения:

Определяет правило выноса общего высказывания за скобку.

В обычной алгебре:

(a + b) * c = a * c + b * c.

5. Закон общей инверсии (законы де Моргана):

 = & ; — для логического сложения

 = v — для логического умножения:

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

( от латинских слов idem — тот же самый и potens —сильный; дословно — равносильный):

A v A = A; — для логического сложения:

A& A = A. — для логического умножения

Закон означает отсутствие показателей степени.

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

A v 1 = 1, A v 0 = A; — для логического сложения:

A& 1 = A, A& 0 = 0. — для логического умножения:

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

A& = 0.

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

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

A v = 1.

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

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

A v (A& B) = A; — для логического сложения:

A& (A v B) = A. — для логического умножения

Закон исключения (склеивания):

 (A& B) v ( & B) = B; — для логического сложения:

 (A v B)& (  v B) = B. — для логического умножения:

Закон контрапозиции (правило перевертывания):

(A Û B) = (BÛ A).

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

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

ОСНОВНЫЕ ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ

Закон                     Для ИЛИ               Для И

Переместительный                           

Сочетательный                

Распределительный          

Правила де Моргана                           

Идемпотенции                                        

Поглощения                                      

Склеивания                              

Операция переменной с ее инверсией                          

Операция с константами            

Двойного отрицания   

Практическая часть.

Пример 1. Упростите следующие формулы, используя законы склеивания:

• а)
• б)
• в)
• г)

· д)
Ответ: а) b•c; б) a; в) c•(a v b) v a•b (Указание: повторить четвертое логическое слагаемое 3 раза); г) a v c.

Пример 2. Упростите следующие формулы, используя законы поглощения:

• а)
• б)
• в)
• г)

Ответ:   а) a; б) a•b; в) a; г) a•b;

 

УРОК №9-10

Тема: Составление таблиц истинности.

Цели:

1. Обучающие:
1. Научить доказывать равносильность логических выражений, используя таблицы истинности
2. Закрепить навыки нахождения значений логических выражений посредством построения таблиц истинности
2. Развивающие:
1. Развивать память
2. Развивать речь учащихся
3. Воспитательные:
1. Воспитывать самостоятельность.

Теоретическая часть.

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

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

(0, 0), (0, 1), (1, 0), (1, 1).

Если формула содержит три переменные, то возможных наборов значений переменных восемь:

(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1).

Количество наборов для формулы с четырьмя переменными равно шестнадцати и т.д.

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

1. Составим таблицу истинности для формулы , которая содержит две переменные x и y. В первых двух столбцах таблицы запишем четыре возможных пары значений этих переменных, в последующих столбцах — значения промежуточных формул и в последнем столбце — значение формулы. В результате получим таблицу:

Переменные  Промежуточные логические формулы                   Формула

                     

0        0      1     0          0          1          1                     1

0        1      1     1          1          0          1                     1

1        0      0     0          1          0          0                     1

1        1      0     0          1          0          0                     1

Из таблицы видно, что при всех наборах значений переменных x и y формула принимает значение 1, то есть является тождественно истинной.

Практическая часть.

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

• а)
• б)
• в)
• г)
• д)
• е)
• ж)
• з)
• и)
• к)

Ответ: а) a v c; б) ; в) ; г) a v c; д) a•(c v b•d); е) ; ж) ; з) ; и) a•(b v c•d); к) .

УРОК №11-12

Тема: Упрощение логических формул.

Цели:

· Закрепить навыки упрощения логических выражений, используя логические законы

· Развивать логическое мышление

· Воспитывать умение слушать учителя и одноклассников

 

Теоретическая часть.

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

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

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

Покажем на примерах некоторые приемы и способы, применяемые при упрощении логических формул:

1)
(законы алгебры логики применяются в следующей последовательности: правило де Моргана, сочетательный закон, правило операций переменной с её инверсией и правило операций с константами);

2)
(применяется правило де Моргана, выносится за скобки общий множитель, используется правило операций переменной с её инверсией);

3)
(повторяется второй сомножитель, что разрешено законом идемпотенции; затем комбинируются два первых и два последних сомножителя и используется закон склеивания);

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

5)
(сначаладобиваемся, чтобы знак отрицания стоял только перед отдельными переменными, а не перед их комбинациями, для этого дважды применяем правило де Моргана; затем используем закон двойного отрицания);

6)
(выносятся за скобки общие множители; применяется правило операций с константами);

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

 

УРОК №13

⇐ Предыдущая1234567Следующая ⇒

Поделиться: