Конъюнкция и дизъюнкция - правила и примеры решения в математике

Общие сведения

Булева алгебра — раздел математического анализа, изучающий истинность логических утверждений. Ее открыл Д. Буль в ХIХ веке. Алгебра логики получила практическое применение только в ХХ веке при проектировании различных элементов персонального компьютера. Дисциплина доказывает истинность или ложность тождеств логического типа математическим путем с применением специальных таблиц.

Следует отметить, что логическое тождество является определенной функцией, принимающей значения 0 или 1 в зависимости от ее элементов. В алгебре логики значения имеют следующие названия: 0 — ЛОЖЬ (FALSE) и 1 — ИСТИНА (TRUE).

Операторы сравнения

Для формирования логических условий применяются соответствующие знаки. К ним относятся следующие: более (>), менее (<), более либо равно (>=), менее или равно (<=), равно (==) и не равно (==!). Чтобы понять их смысловое значение, нужно разобрать примеры на практике:

1. >: 5>4.
2. <: 3<9.
3. >=: 5>=5 и 6>=8.
4. <=: 3<=3 и 6<=11.
5. <> <>

Следует отметить, что в этих примерах получается истинное значение, поскольку условие выполняется. Однако в информатике при построении алгоритмов используются методы ветвления. Они представляют собой такую конструкцию: ЕСЛИ (a>b), ТО a+b. ИНАЧЕ (a*b). Читается запись следующим образом: в том случае, когда значение а больше b, нужно сложить оба числа, а иначе (a<b) — их перемножить.

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

Логические операции

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

1. Конъюнкция.
2. Дизъюнкция.
3. Инверсия.

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

Функция конъюнкции

Конъюнкция — операция логического умножения, которая будет истинным при достоверности каждого выражения. Ее обозначение — символ конъюнктора «&". Записывается следующим образом: S&T, где S и T — логические тождества или конкретные значения. Операция имеет такие особенности: только при равенстве всех элементов 1 значение выражения является истинным, а в других случаях — ложью. Для проверки необходимо составить таблицу значений логического тождества:

Таблица 1. Значение функции в зависимости от логических переменных.

Из таблицы 1 видно, что выражение S&T принимает только TRUE при всех истинных значениях переменных. Если рассматривать алгебру, то можно провести аналогию между логическим и обыкновенным умножениями. Например, произведение двух чисел S*T, которые для удобства сравнения принимают значения 0 или 1.

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

Информация о дизъюнкции

В булевой алгебре операция логического сложения называется дизъюнкцией. Обозначается она символом, который называется дизъюнктором (V или I). Логическое тождество, содержащее два элемента, имеет такой вид: SVT. Операция имеет только ложное значение при равенстве S и T нулю. Для нее нужно также строить специальную таблицу:

Таблица 2. Истинность операции дизъюнкции SVT.

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

Если рассмотреть результаты в последнем случае, то можно сделать вывод о схожести сложения и дизъюнкции. Однако в последней строке алгебраической суммы есть некоторое несоответствие — 2. Это показывает, какое переполнение разряда происходит в булевой алгебре. В последней происходит переход с одного разряда в другой.

Булево отрицание

В алгебре логики применяется также операция отрицания, которую также называют инверсией. Суть ее заключается в том, что при истинном значении выражения под знаком инверсии получается ложный результат, а при ложном — истина. Обозначается она символом инверсии «¬", а записывается в таком виде ¬(S). Для демонстрации операции необходимо ознакомиться с таблицей:

Таблица 3. Истинность ¬(S).

Следует отметить, что операция инверсии функции прибавляет к искомому выражению частицу «НЕ». Очень часто используется при построении логических условий. В алгоритмах и языках программирования отрицание записывается в виде комбинации следующих символов: «<!» (не меньше), «=!» (не равно) и «>!» (не больше).

Например, если необходимо указывать несколько тождеств логического вида, то при помощи отрицания можно использовать только одно. Для примера необходимо написать, что число не равно 0: (t<0)&(t>0). При использовании логического отрицания условие выглядит короче: t=!0.

Приоритеты вычислений

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

1. Написать выражение: S&T|S|[¬(S|T)].
2. Определить последовательность вычислений: [¬(S|T)], S&T, [S&T]|S и [S&T|S]v[¬(S|T)].
3. Составить обобщенную таблицу.

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

1. ¬(0)=1.
2. ¬(1)=0.
3. ¬(¬(0))=0.
4. ¬(¬(1))=1.
5. ¬(S&T)=¬(S)&¬(T).
6. S&(S|T)=S|T.

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

Примеры решений

В первом простом примере требуется составить таблицу булевского типа для выражения S&(S|T)|T&S|¬(T&S).

Решать задание нужно по такому алгоритму:

1. Упрощение выражения: S|T|T&S|¬(T&S).
2. Порядок операций: первая — ¬(T&S), вторая — T&S, третья — совокупность первой и второй, четвертая — включает третью и один элемент, стоящий впереди и пятая — к полученному результату в четвертой прибавить первый элемент.
3. Составление таблицы:

Следующий пример будет сложнее, поскольку выражение ¬ { ¬[ ¬((S|0)&¬(T|S)& ¬(S&(T&S)) ]& ¬(S&S) } следует упростить, а затем составить таблицу. Задача решается по такой методике:

1. Упрощение: ¬{ ¬[ ¬((S|0)&¬(T|S)& ¬(S&(T&S)) ]& ¬(S&S)}=¬{ ¬[1]&¬(S)}=1&S.
2. Составление таблицы:

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

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