Тема: Основные законы преобразования алгебры логики.
Цель:
ü рассмотреть
основные законы алгебры логики;
ü сформировать
у учащихся умение решать логические задачи с помощью алгебры логики.
План урока.
1.
Изучение нового материала. Законы алгебры
высказываний.
2.
Выполнение заданий на закрепление. Упрощение
сложных высказываний.
3.
Домашнее задание.
I. Изучение нового
материала. Законы алгебры высказываний
Алгебра высказываний или алгебра логики - раздел математической логики, изучающий логические операции над
высказываниями и правила преобразования сложных высказываний. При решении
многих логических задач часто приходится упрощать формулы, полученные при
формализации их условий. Упрощение формул в алгебре высказываний производится
на основе эквивалентных преобразований, опирающихся на основные логические
законы примерно так же, как это делается в обычной алгебре. В алгебре высказываний
логические законы выражаются в виде равенства эквивалентных логических формул.
Основные
законы алгебры высказываний.
Закон
тождества: А = А. Всякое понятие и суждение тождественно самому
себе. Закон тождества означает, что в процессе рассуждения
нельзя подменять одну мысль другой, одно понятие другим. При нарушении этого
закона возможны логические ошибки. Например, рассуждение:
«Правильно говорят, что язык до Киева доведет, а я купил вчера копченый язык,
значит, теперь смело могу идти в Киев» неверно, так как первое и второе слова
«язык» обозначают разные понятия. В рассуждении: «Движение вечно. Хождение в
школу - движение. Следовательно, хождение в школу вечно» слово «движение»
используется в двух разных смыслах (первое - в философском смысле - как атрибут
материи, второе - в обыденном смысле - как действие по перемещению в
пространстве), что приводит к ложному выводу.
Закон
непротиворечия: А И НЕ(А) = 0 (A*НЕ(А)=0). Не могут быть
одновременно истинными суждение и его отрицание. То есть,
если высказывание А - истинно, то его отрицание НЕ (А) должно быть ложным (и
наоборот). Тогда их произведение будет всегда ложным: Именно это равенство наиболее
часто используется при упрощении сложных логических выражений.
Иногда этот закон формулируется так: два противоречащих друг
другу высказывания не могут быть одновременно истинными. Примеры действия закона непротиворечия:
1. На Марсе есть жизнь, и жизни нет на Марсе.
2. Оля окончила среднюю школу, и Оля учится в X
классе.
Закон
исключенного третьего: А ИЛИ НЕ(А) = 1 (А+НЕ(А)=1). В один и тот же момент времени высказывание
может быть либо истинным, либо ложным, третьего не дано.
Истинно либо А, либо НЕ(А). Примеры действия закона исключенного
третьего:
1.
Число 12345 либо четное, либо нечетное, третьего не
дано.
2.
Предприятие работает либо убыточно, либо прибыльно.
3.
Эта жидкость является или не является кислотой.
Закон исключенного третьего не является законом, признаваемым
всеми логиками в качестве универсального закона логики. Этот закон применяется
там, где познание имеет дело с жесткой ситуацией: «либо - либо», «истина - ложь».
Там же, где встречается неопределенность (например, в рассуждениях о будущем), закон
исключенного третьего часто не может быть применен.
Рассмотрим следующее высказывание: «Это предложение ложно».
Оно не может быть истинным, потому что в нем утверждается,
что оно ложно. Но оно не может быть и ложным, потому что тогда оно было бы истинным.
Это высказывание не истинно и не ложно, а потому нарушается закон исключенного
третьего. Парадокс (греч. paradoxes - неожиданный,
странный) в этом примере возникает из-за того, что предложение ссылается само
на себя.
Другим известным парадоксом является задача о парикмахере: В
одном городе парикмахер стрижет волосы всем жителям, кроме тех. кто стрижет
себя сам. Кто стрижет волосы парикмахеру? В логике из-за ее формальности нет
возможности получить форму такого ссылающегося самого на себя высказывания. Это
еще раз подтверждает мысль о том, что с помощью алгебры логики нельзя выразить
все возможные мысли и доводы.
Закон
двойного отрицания: НЕ(НЕ(А)) = А. Если отрицать дважды некоторое высказывание,
то в результате получается исходное высказывание. Например, высказывание А = «Матроскин - кот» эквивалентно высказыванию А = «Неверно,
что Матроскин не кот».
Свойства
костант:
|
НЕ(0)=1
[ 0=1]
|
НЕ(1)=0
[ 1=0]
|
|
A V 0=A [A+0=A][A ИЛИ 0 = A]
|
A V 1 = 1
[A+1=1] [A ИЛИ 1 = 1]
|
|
A & 0=0 [
A * 0=0] [A И 0=0]
|
A & 1=1 [
A * 1=1] [A И 1=1]
|
Законы
идемпотентности:
ü A v A=A (идемпотентность
сложения)
ü A & A=A (идемпотентность
умножения)
Законы
де Моргана:
ü НЕ(А ИЛИ
В)=НЕ(А) И НЕ(В) {НЕ(А+В)=НЕ(А)*НЕ(В)}
ü A ИЛИ B=НЕ(НЕ(А)
И НЕ(В)) { A+B=НЕ(НЕ(А)*НЕ(В)) }
ü НЕ(А И
В)=НЕ(А) ИЛИ НЕ(В) {НЕ(А*В)=НЕ(А)+НЕ(В)}
ü A И
B=НЕ(НЕ(А)
ИЛИ НЕ(В)) { A*B=НЕ(НЕ(А)+НЕ(В))}
Закон
коммутативности:
ü А И В =В
И А {А
* В =В * А}
ü А ИЛИ В=В ИЛИ А{ А + В=В
+ А}
При
операциях логического умножения – «и» - и логического сложения – «или» - переменные
можно менять местами.
Закон
ассоциативности: если в логическом выражении используются только операции
логического умножения или только операции логического сложения, то можно
скобками пренебрегать или произвольно их расставлять.
ü (А И В)
И С=А И (В И С) ИЛИ (А * В) * С=А * (В * С)
ü (А ИЛИ
В) ИЛИ С=А ИЛИ (С ИЛИ В) ИЛИ (А + В) +
С=А + (С + В)
Закон
дистрибутивности: за скобки можно выносить как общие множители, так и общие
слагаемые.
ü (А И В)
ИЛИ (А И С)=А И ( В ИЛИ С) (дистрибутивность умножения относительно сложения;
в алгебре:ab+ac=a(b+c)) ИЛИ (А * В)
+ (А * С)=А * ( В + С)
ü (А ИЛИ
В) И (А ИЛИ С)=А ИЛИ (В И С) (дистрибутивность сложения относительно
умножения) ИЛИ (А + В) *
(А + С)=А + (В * С)
Правила
замены операций импликации.
ü А=>В
= НЕ (A) ИЛИ B
ü А
=> В = НЕ (В) => НЕ (А)
Правила
замены операций эквивалентности.
ü А
<=> В = (А & В) v (НЕ (А) & НЕ (В));
ü А
<=> В = (A v НЕ (В)) & (НЕ (A) v В)
ü А
<=> В = (А => В) & (В => А).
II.
Упрощение
сложных высказываний.
Упрощение сложных высказываний - это замена их на равносильные
на основе законов алгебры высказываний с целью получения высказываний более
простой формы. Рассмотрим примеры упрощений.
Пример 1. Требуется упростить: А &
В v A & НЕ (В).
По закону дистрибутивности и вынесем А за скобки:
А & В v А & НЕ (В) = А & (В v НЕ(В)) = А & 1 = А.
Пример 2. Требуется упростить: (A
v В) & (A v HE (В)).
Применим закон дистрибутивности:
(A v В) & (A v НЕ (В)) = A
v (В & НЕ (В)) = A v 0 = А.
Пример 3. Требуется упростить: НЕ(НЕ(Х)
ИЛИ НЕ(Y)).
Применим закон де Моргана:
НЕ(НЕ(Х) ν НЕ(У))=НЕ(НЕ(Х)) & НЕ(НЕ(У))=Х & У
III.
Домашнее
задание.
1)
Упростите логические выражения. Правильность
упрощения проверьте с помощью таблиц истинности для исходных и полученных
логических формул.
a) A v (НЕ(А)&.В);
б) А &(НЕ(A) v В);
в) (А v В)&( НЕ(В) v А)&(НЕ(С) v В)
г) (1 v (A =>B))v((A v C)&1)
2)
Работа с конспектом.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.