ГОУ СПО ТПСК № 57
Самостоятельная работа по информатике
По теме: «Алгебра логики. Основные логические операции. Сложные высказывания »
Выполнила студентка группы 1ИС-01
Ткаченко Ирина
Проверил: Монастырёва Галина Анатольевна
Г. Москва
Г.
Первые четыре из приведенных ниже законов являются основными законами алгебры высказываний. Закон тождества:
А = А
Всякое понятие и суждение тождественно самому себе. Закон тождества означает, что в процессе рассуждения нельзя подменять одну мысль другой, одно понятие другим. При нарушении этого закона возможны логические ошибки.
Закон не противоречия, нельзя чтоб выражение противоречило само себе:
А & А = 1.
Не могут быть одновременно истинными суждение и его отрицание. То есть если высказывание А истинно, то его отрицание не А должно быть ложным (и наоборот). Тогда их произведение будет всегда ложным:
A & A = 0.
Именно это равенство часто используется при упрощении сложных логических выражений. Иногда этот закон формулируется так: два противоречащих друг другу высказывания не могут быть одновременно истинными.
Закон исключенного третьего:
A v A = l.
В один и тот же момент времени высказывание может быть либо истинным, либо ложным, третьего не дано. Истинно либо А, либо не А.
Закон исключенного третьего не является законом, признаваемым всеми логиками в качестве универсального закона логики. Этот закон применяется там, где познание имеет дело с жесткой ситуацией: ибо истина ложь. Там же, где встречается неопределенность (например, в рассуждениях о будущем), закон исключенного третьего часто не может быть применен.
В логике из-за ее формальности нет возможности получить форму такого ссылающегося самого на себя высказывания. Это еще раз подтверждает мысль о том, что с помощью алгебры логики нельзя выразить все возможные мысли и доводы.
А =>!А => A.
Если отрицать дважды некоторое высказывание, то в результате поучается исходное высказывание.
Свойства констант:
0 =! 1 = 0
Отрицание лжи есть истина отрицание истины есть ложь;
А v 0 = A; A &0 = 0; A v 1 = 1; A &1 = A.
Законы идемпотентности:
A v A = A A & A = A
Отсутствие коэффициентов, степеней.
Законы коммутативности:
A v B = B v A;
A & B = B & A.
Операнды А и В в операциях дизъюнкции и конъюнкции можно менять местами.
Законы ассоциативности:
А v (В v С) = (В v S) v С;
A & (B & С) = (A & B) & C.
Если в выражении используется только операция дизъюнкции или только операция конъюнкции, то можно пренебрегать скобками или произвольно их расставлять. Законы дистрибутивности:
A v (B & C) = (A v B) & (A v C) A & (B v Q) = (A & B) v(A & Q)
Дистрибутивность дизъюнкции относительно дизъюнкции дистрибутивность конъюнкции относительно конъюнкции.
Закон дистрибутивности конъюнкции относительно дизъюнкции аналогичен дистрибутивному закону в алгебре, а закон дистрибутивности дизъюнкции относительно конъюнкции аналога не имеет, он справедлив только в логике. Поэтому необходимо его доказать. Доказательство удобнее всего провести с помощью таблицы истинности:
Законы поглощения:
A v (A & B) = A;
A & (A v B) = A.
Проведите доказательство законов поглощения самостоятельно.
Законы де Моргана:
A v В = А & В А & B = A v B
Отрицание вариантов вместе, отрицание одновременной
Истинности.
Операций импликации и эквивалентности иногда нет среди логических операций конкретного компьютера или транслятора с языка программирования. Однако для решения многих задач эти операции необходимы. Существуют правила замены данных операций на последовательности операций отрицания, дизъюнкции и конъюнкции.
Так, заменить операцию импликации можно в соответствии со следующим правилом:
А => В =! A v В,
Для замены операции эквивалентности существует два правила:
A <=> B = (! A &! B) v (A & B);
А <=> В = (! A v В) & (A v! В).
Программирование построения таблиц истинности
В большинстве языков высокого уровня имеются логические операции NOT, AND, OR, XOR, реализующие операции!, &, v, ^.
В языке Паскаль логические операции применяются к величинам типа boolean, которые могут принимать всего два значения: true истина, false ложь (false < true). Результат операции также будет иметь тип boolean. Однако в языке Бейсик переменных логического типа нет, поэтому программирование логических операций имеет свои особенности: результат логической операции записывается в двух байтах (слове) памяти, причем логическому нулю (значению ложь соответствует слово &В0000000000000000, т. е. десятичный ноль, а-логической единице соответствует слово &В111111111111111, т. е. целое десятичное число -1.
Ложь false 0
Истина true -1
Примечание. Для того чтобы на языке Бейсик получить таблицу истинности в привычном виде (0 ложь, 1 истина), при выводе значений выражений в операторе PRINT следует использовать знак
инусr>
Программа построения таблицы истинности логических операций
А & В, A v В, А:
| Паскаль. program logop(output); var A,B: boolean; begin for A:=false to true do for B:=false to true do writeln(A:7, B:7, (A and B):7, (A or B);7, (not A):7); readln end. | Бейсик. 10 for A=0 to -1 step -1 20 for B=0 to -1 step -1 30 print -A, -B, - (A and B),- (A or B), -(not A) 40 next В 50 next A 60 end |