АЛГЕБРА ЛОГИКИ

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

Основные законы алгебры логики Простейшими операциями в алгебре логики являются операции логического сложения ( ИЛИ, операция дизъюнкции, ) и логического умножения ( И, операция конъюнкции, ). Для алгебры логики выполняются следующие законы : Переместительный А В = В А, А В = В А Сочетательный ( А В ) С = А ( В С ), ( А В ) С = А ( В С ) Распределительный А ( В С ) = А В А С

Некоторые соотношения отрицания Наименьшим элементом алгебры логики является 0 ( ложь ), наибольшим элементом 1 ( истина ). В алгебре логики также вводится еще одна операция отрицания ( операция НЕ, инверсия, ) Справедливы такие соотношения : А А =1, А А =0, 0=1, 1=0 ( А )= А, ( А В )= А В, ( А В )= А В

Определение логической формулы С помощью логических переменных и символов логических операций любое высказывание можно формализовать, то есть заменить логической формулой. Определение логической формулы : 1) Всякая логическая переменная и символы истина (1) и ложь (0) формулы. 2) Если А и В формулы, то ¬ A, ( А В ), ( А v В ), ( А B), ( А В ) формулы. 3) Никаких других формул в алгебре логики нет.

Примеры Если я куплю яблоки или абрикосы, то я приготовлю фруктовый пирог. Если Игорь знает английский или немецкий язык, то он может стать переводчиком А v В C

Как показывает анализ формулы (A v B) C, при определённых сочетаниях значений переменных A, B и C она принимает значение истина, а при некоторых других сочетаниях значение ложь. Такие формулы называются выполнимыми. Некоторые формулы принимают значение истина при любых значениях истинности входящих в них переменных. Таковой будет, например, формула А v¬A, соответствующая высказыванию Этот треугольник прямоугольный или косоугольный. Эта формула истинна и тогда, когда треугольник прямоугольный, и тогда, когда треугольник не прямоугольный. Такие формулы называются тождественно истинными формулами или тавтологиями. Высказывания, которые формализуются тавтологиями, называются логически истинными высказываниями. В качестве другого примера рассмотрим формулу А ¬A, которой соответствует, например, высказывание Катя самая высокая девочка в классе, и в классе есть девочки выше Кати. Очевидно, что эта формула ложна, так как либо А, либо обязательно ложно. Такие формулы называются тождественно ложными формулами или противоречиями. Высказывания, которые формализуются противоречиями, называются логически ложными высказываниями. Если две формулы А и В одновременно, то есть при одинаковых наборах значений входящих в них переменных, принимают одинаковые значения, то они называются равносильными. Равносильность двух формул алгебры логики обозначается символом = или символом. Замена формулы другой, ей равносильной, называется равносильным преобразованием данной формулы.

Задания Даны простые высказывания : А = { Принтер устройство ввода информации }, В = { Процессор устройство обработки информации }, С = { Монитор устройство хранения информации }, D = { Клавиатура устройство ввода информации }. Определите истинность составных высказываний : a) (A B) (CvD); б ) ( А В )=>( В С ); в ) (AvB) (C D); г ) А В. а) (0*1)*(0+1)=0, б) (0*1) (0*1)=1, в) (0+1) (0*1)=0, г) 0 1=0

Задания Дано составное высказывание не ( не А и В ), где А и В простые высказывания. В каком случае данное высказывание будет ложным ? -(-1)*1=1, -(-0)*1=0, -(-1)*0=0, -(-0)*0=1

Задания Даны простые высказывания : А = {5>3}, В = {2=3} и С = {4<2}. Определите истинность составных высказываний a)(AvB) C (A C)v(B C); б ) (A B)vC (AvC) (A B). а) (1+0)*0 (1*0)+(0*0)=1, б) (1*0)+0 (1+0)*(1*0)=1