Основные понятия и определения
Не вдаваясь в глубины, разберемся с терминологией. Итак, булева алгебра предполагает наличие:
высказываний;
логических операций;
функций и законов.
Высказывания – любые утвердительные выражения, которые не могут быть истолкованы двузначно.
Они записываются в виде чисел (5 > 3) или формулируются привычными словами (слон – самое большое млекопитающее). При этом фраза «у жирафа нет шеи» также имеет право на существование, только булева алгебра определит её как «ложь».
Все высказывания должны носить однозначный характер, но они могут быть элементарными и составными. Последние используют логические связки. Т. е. в алгебре суждений составные высказывания образуются сложением элементарных посредством логических операций.
Чтобы определиться с термином «логика высказываний», необходимо четко понимать, что же такое «высказывание».
Итак, высказывание представляет собой предложение, выстроенное грамматически правильно, и являющееся ложным или истинным. Данное понятие должно выражать определенный смысл. Например, выражение «канарейка есть птица» включает такие составные части: «канарейка» и «птица».
Именно поэтому одним из ключевых, исходных понятий логики и являются высказывания. Эти понятия должны описывать конкретную ситуацию, в которой будет либо утверждение чего-то, либо отрицание.
Истинным принято считать высказывание, если прослеживается соответствие реальности ситуации при ее описывании. Сами по себе «ложь» и «истина» определяют истинность высказываний.
|
|
|
Логика высказываний складывается из простых и сложных выражений. Так, простым считается высказывание, не включающее в свой состав другие выражения. А к сложным относятся выражения, которые получены из простых, логически связанных между собой высказываний.
Классическая логика высказываний может быть представлена общей теорией дедукции. Это именно та часть логики, в которой описываются не зависящие от структуры высказываний логические связи простых выражений.
Логика высказываний направлена на решение такой центральной задачи, как разделение правильных и неправильных схем рассуждения и систематизация первых. Чтобы получить правильный результат, необходимо сосредоточить свое внимание на специальных символах, которые могут представить ту или иную форму. Отсюда и обозначается интерес к таким незначительным на первый взгляд словам, как «или», «и» и т.д.
Операции булевой алгебры
Мы уже помним, что операции в алгебре суждений – логические. Подобно тому, как алгебра чисел использует арифметические операции для сложения, вычитания или сравнения чисел, элементы математической логики позволяют составить сложные высказывания, дать отрицание или вычислить конечный результат.
|
|
|
Логические операции для формализации и простоты записываютсяформулами, привычными для нас в арифметике. Свойства булевой алгебры дают возможность записывать уравнения и вычислять неизвестные. Логические операции обычно записывают с помощью таблицы истинности. Её столбцы определяют элементы вычислений и операцию, которая над ними производится, а строки показывают результат вычислений.
Основные логические действия
Самыми распространенными в булевой алгебре операциями являются отрицание (НЕ) и логические Ии ИЛИ.
Так можно описать практически все действия в алгебре суждений. Изучим подробнее каждую из трех операций.
Отрицание (не) применяется только к одному элементу (операнду(объект математической операции, величина, на базе которой выполняется какая-либо операция)). Поэтому операцию отрицания называют унарной. Для записи понятия «не А» используют такие символы: A, неAили !A.
В табличной форме это выглядит так: 
Для функции отрицания характерно такое утверждение: если А истинно, то A – ложно. Например, «Луна вращается вокруг Земли» – истина; «Земля вращается вокруг Луны» – ложь.
|
|
|
Логическое умножение
Логическое И называют операцией конъюнкции.
Что это значит?
Во-первых, что применить ее можно к двум операндам, т. е. И – бинарная операция.
Во-вторых, что только в случае истинности обоих операндов (и А, и Б) истинно и само выражение. Пословица «Терпение и труд все перетрут» предполагает, что только оба фактора помогут человеку справиться со сложностями.
Для записи используются символы: A∧Б, A⋅Б или A&Б.
Конъюнкция – сложное высказывание, получаемое путем соединения двух простых выражений с помощью слова «И». Истинность конъюнкции подтверждается достоверностью всех высказываний, входящих в ее структуру. В случае, когда хоть один из ее членов ложный, вся конъюнкция имеет признак «ложь».
Конъюнкция аналогична умножению в арифметике. Иногда так и говорят – логическое умножение. Если перемножить элементы таблицы по строкам, мы получим результат, аналогичный логическому размышлению.
 |
Таблица истинности операции логического И:
Логическое сложение
Дизъюнкцией называют операцию логического ИЛИ. Она принимает значение истинности тогда, когда хотя бы одно из высказываний истинно (А или Б). Записывается это так: A∨Б, A+Б или A||Б.
|
|
|
Дизъюнкция подобна арифметическому сложению. Операция логического сложения имеет только одно ограничение: 1+1=1. Но мы же помним, что в цифровом формате математическая логика ограничена 0 и 1 (где 1 – истина, 0 - ложь).
Например, утверждение «в музее можно увидеть шедевр или встретить интересного собеседника» означает, что можно посмотреть произведения искусства, а можно познакомиться с интересным человеком. В то же время, не исключен вариант одновременного свершения обоих событий.
Таблица истинности операции логического ИЛИ:
 |
Помимо основных логических операций математическая логика и теория алгоритмов использует производные. Под производными понимаются исключающее ИЛИ, импликация и эквивалентность.
Исключающее ИЛИᴓ
| А | В | А XOR В |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Импликация,или логическое следование – это высказывание, в котором одно действие является условием, а другое – следствием его выполнения. Иными словами, это предложение с предлогами «если... то».
«Любишь кататься, люби и саночки возить».
Т. е. для катания необходимо затянуть санки на горку. Если же нет желания съехать с горы, то и санки таскать не приходится.
Записывается это так:
A→Б или A⇒Б.
При определении импликации существует утверждение, что основание высказывания не может быть истинным при ложном следствии. Другими словами, данное понятие предполагает зависимость истинности или ложности выражения от значения его составляющих и способов их связей.
Несмотря на то, что импликация достаточно полезна для некоторых целей, она не очень согласуется с пониманием условной связи в общем виде. Так, при охватывании многих важных черт логического поведения высказывания данное понятие не может являться его адекватным описанием.
| А | В | А=> В |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Эквивалентность предполагает, что результирующее действие наступает только в том случае, когда истиной являются оба операнда. Например, ночь сменяется днем тогда (и только тогда), когда солнце встает из-за горизонта. На языке математической логики это утверждение записывается так: A≡Б, A⇔Б, A==Б.
| А | В | А<=> В |
| 0 | 0 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 1 | 1 |
Последовательность операций
Последовательность операций имеет немаловажное значение. Собственно, как и для алгебры, существует приоритетность функций, которые использует булева алгебра. Формулы могут упрощаться только при условии соблюдения значимости операций. Ранжируя от самых значимых до незначительных, получим такую последовательность:
1. Отрицание.
2. Конъюнкция.
3. Дизъюнкция, исключающее ИЛИ.
4. Импликация, эквивалентность.
Как видим, только отрицание и конъюнкция не имеют равных приоритетов. А приоритет дизъюнкции и исключающего ИЛИ равны, так же как и приоритеты импликации и эквивалентности.
Функции и законы
Итак, мы уже знаем, какие логические операции использует булева алгебра.
Функцииописывают все свойства элементов математической логики и позволяют упрощать сложные составные условия задач.
Ассоциативность означает, что в высказываниях типа «и А, и Б, и В» последовательность перечисления операндов не играет роли.
Формулой это запишется так:
(A∧Б)∧В=A∧(Б∧В)=A∧Б∧В,
(A∨Б)∨В=A∨(Б∨В)=A∨Б∨В.
 |
Как видим, это свойственно не только конъюнкции, но и дизъюнкции.
Коммутативность утверждает, что результат конъюнкции или дизъюнкции не зависит от того, какой элемент рассматривался вначале:
A∧Б=Б∧A;
A∨Б=Б∨A.
Дистрибутивность позволяет раскрывать скобки в сложных логических выражениях. Правила схожи с раскрытием скобок при умножении и сложении в алгебре:
A∧(Б∨В)=A∧Б∨A∧В;
A∨Б∧В=(A∨Б)∧(A∨В).
Свойства единицы и нуля, которые могут быть одним из операндов, также аналогичны алгебраическим умножению на ноль или единицу и сложению с единицей:
A∧0=0,
A∧1=A;
A∨0=A,
A∨1=1.
Идемпотентность говорит нам о том, что если относительно двух равных операндов результат операции оказывается аналогичным, то можно «выбросить» лишние усложняющие ход рассуждений операнды. И конъюнкция, и дизъюнкция являются идемпотентными операциями.
Б∧Б=Б;
Б∨Б=Б.
Поглощение также позволяет нам упрощать уравнения. Поглощение утверждает, что когда к выражению с одним операндом применяется другая операция с этим же элементом, результатом оказывается операнд из поглощающей операции.
A∧Б∨Б=Б;
(A∨Б)∧Б=Б.
Дата добавления: 2018-06-01; просмотров: 400; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!