Итак, мы познакомились с понятием логического выражения и увидели, каким образом его строить по высказыванию на русском языке. Следующий шаг – изучение преобразований логических выражений.
Логические выражения, зависящие от одних и тех же логических переменных, называются равносильными, если на любом наборе значений переменных они принимают одинаковое значение (`0` или `1`). В дальнейшем для обозначения равносильности логических выражений мы будем использовать знак равенства.<
это некоторые стандартные преобразования логических выражений, при которых сохраняется равносильность. Начнём с самых простых законов:
1) Законы поглощения констант
x `vv` 0 = x, x & 1 = x;
2) Законы поглощения переменных
x `vv` 1 = 1, x & 0 = 0;
3) Законы идемпотентности
x & x = х, x `vv` x = х;
4) Закон двойного отрицания
$$ \stackrel{=}{\mathrm{x}}$$ = x;
5) Закон противоречия
x & $$ \stackrel{-}{\mathrm{x}}$$ = 0;
6) Закон исключённого третьего
x `vv` $$ \stackrel{-}{\mathrm{x}}$$ = 1;
Приведённые законы ещё называют аксиомами алгебры логики. Истинность этих и всех последующих законов легко можно установить, построив таблицу истинности для левого и правого логического выражения.
Переходим к группе законов, которые практически аналогичны законам алгебры чисел.
7) Законы коммутативности
x & y = y & x,
x `vv` y = y `vv` x;
Здесь стоит сделать замечание, что помимо конъюнкции и дизъюнкции свойством коммутативности также обладают эквивалентность и строгая дизъюнкция. Импликация – единственная из изучаемых операций, которая имеет два операнда и не обладает свойством коммутативности.
8) Законы ассоциативности
(x & y) & z = x & (y & z),
(x`vv`y) `vv` z = x `vv` (y `vv` z);
9) Законы дистрибутивности
x & (y `vv` z) = (x & y) `vv` (x & z),
x `vv` (y & z) = (x `vv` y) & (x `vv` z);
Первый из законов дистрибутивности аналогичен закону дистрибутивности в алгебре чисел, если конъюнкцию считать умножением, а дизъюнкцию – сложением. Второй же закон дистрибутивности отличается от алгебры чисел, поэтому рекомендуется обратить на него особое внимание и в дальнейшем использовать при решении задач на упрощение выражений.
Кроме аксиом и алгебраических свойств операций ещё существуют особые законы алгебры логики.
10) Законы де Моргана
$$\style{font-family:'Courier New'}{\overline{\mathrm x\&\mathrm y}=\overline{\mathrm x}\vee\overline{\mathrm y},}$$
$$\style{font-family:'Courier New'}{\overline{\mathrm x\vee\mathrm y}=\overline{\mathrm x}\;\&\;\overline{\mathrm y};}$$
11) Загоны поглощения (не путать с аксиомами поглощения переменных нулём или единицей)
x `vv` (x & y) = x;
x & (x `vv` y) = x.
Рассмотрим пример доказательства первого закона де Моргана при помощи построения таблицы истинности.
|
`x` |
`Y` |
`x&y` |
`bar(x&y)` |
`barx` | `bary` |
`barx vv bary` |
|
`0` |
`0` |
`0` |
`1` |
`1` |
`1` |
`1` |
|
`0` |
`1` |
`0` |
`1` |
`1` |
`0` |
`1` |
|
`1` |
`0` |
`0` |
`1` |
`0` |
`1` |
`1` |
|
`1` |
`1` |
`1` |
`0` |
`0` |
`0` |
`0` |
Так как результирующие столбцы совпали, то выражения, стоящие в левой и правой частях закона, равносильны.
В алгебре при решении задач на упрощение выражений большой популярностью пользовалась операция вынесения общего множителя за скобки. В алгебре логики эта операция также является легитимной, благодаря законам дистрибутивности и закону поглощения константы `1`. Продемонстрируем этот приём на простом примере: докажем первый закон поглощения, не используя таблицу истинности.
Наше начальное выражение: x `vv` (x & y). Выносим `x` за скобки и получаем следующее выражение:
x &(1 `vv` y). Используем закон поглощения переменной константой `1` и получаем следующее выражение: x & 1. И теперь используем закон поглощения константы и получаем просто x.
В заключение, следует сказать несколько слов об операции импликации. Как уже отмечалось выше, импликация не обладает свойством коммутативности. Её операнды неравноправны, поэтому каждый из них имеет уникальное название. Левый операнд импликации называется посылкой, а правый – следствием. Из таблицы истинности импликации следует, что она истинна, когда истинно следствие, либо ложна посылка. Единственный случай, когда импликация ложна – это случай истинной посылки и ложного следствия. Таким образом, мы подошли к последнему закону алгебры логики, который бывает полезен при упрощении выражений.
12) Закон преобразования импликации
`"x" -> "y" = bar("x") vv "y"`
Необходимо ещё отметить, что в сложных логических выражениях у операций есть порядок приоритетов.
1) Отрицание
2) Конъюнкция
3) Дизъюнкция, строгая дизъюнкция, эквивалентность
4) Импликация
С помощью тождественных преобразований максимально упростить следующее логическое выражение:
`bar C vv` (`A` & `С`) `vv` (`bar(A vv C vv bar(B)`)
Максимально упростить, это значит довести выражение до такого вида, когда невозможно применить ни один из законов алгебры логики, которые сокращают длину выражения.
Для того, чтобы не запутаться, можно использовать общую стратегию упрощения логических выражений.
1) Избавиться от операций импликации.
2) Продвинуть отрицание вглубь выражения. То есть применять законы де Моргана, и закон двойного отрицания пока знак отрицания не будет стоять только над переменными (но не над операциями).
После пункта 2 наступает относительная свобода действий. Можно использовать тождества поглощения или раскрывать скобки.
В нашей задаче операция импликации отсутствует, поэтому первый пункт мы пропускаем. Переходим к пункту 2. Применяем два раза второй закон де Моргана (для дизъюнкции) и закон двойного отрицания к правой скобке и получаем следующее логическое выражение:
`bar C vv ` (`A` & `C`) `vv` (`bar A` & `bar C` & `B`)
Если теперь внимательно посмотреть на выражение, то очевидно, что к первому и третьему слагаемому можно применить первый закон поглощения, так как отрицание переменной `C` является первым слагаемым и входит в третье в качестве множителя.
Поскольку дизъюнкцию ещё называют логическим сложением, её операнды называют слагаемыми, аналогично конъюнкция – это логическое умножение, и её операнды называют множителями.
После применения первого закона поглощения получается следующее логическое выражение:
`bar C` `vv` (`A` & `C`)
Применим второй (нестандартный для алгебры) закон дистрибутивности. Получаем:
(`bar C vv A`) & (`bar C vv C`)
Ко второй скобке применяем закон исключённого третьего, превращаем её в единицу, а затем применяем закон поглощения константы `1` и в итоге получаем выражение: `bar C vv A`, которое упростить уже нельзя.
Для лучшего понимания, рекомендуется выписать исходное логическое выражение, последовательно применить к нему все описанные действия и сравнить свой результат с приведённым в конце решения задачи.
Обратите внимание, что исходное логическое выражение зависело от трёх переменных (`A, B, C`) , в то время как упрощённое в итоге зависит от двух логических переменных (`A` и `C`). При этом выражения всё равно остаются равносильными! Это происходит потому, что в процессе упрощения применялись законы поглощения. Аналогичный результат мог бы получиться, если в процессе упрощения выражения используются законы поглощения переменных константами. Исчезновение переменной при упрощении означает, что в исходном выражении она является несущественной.
Укажите значения переменных `K`, `L`, `M`, `N`, при которых логическое выражение `(L vv M) ^^ (¬ K -> M) ^^ ¬ N ^^ ¬ M` истинно.
Будем следовать стратегии, описанной в предыдущем примере. Первым делом избавляемся от операции импликации. Получаем следующее выражение:
`(L vv M) ^^ ( K vv M) ^^ ¬ N ^^ ¬ M`
Отрицание вглубь продвигать не надо. Теперь раскроем скобки. Для упрощения условимся операцию конъюнкции никак не обозначать (по аналогии с алгеброй чисел).
`(LK vv LM vv MK vv M) ( ¬ N) ( ¬ M)`
В первой скобке можно применить тождество поглощения, и «съесть» второе и третье слагаемое, которые содержат M в качестве множителя. Получается такое выражение:
`(LK vv M) ( ¬ N) ( ¬ M)`
Выполнив оставшиеся операции умножения, получим следующий результат:
` LK¬ N¬ M`
Получили одну конъюнкцию. Следовательно, существует всего один набор значений переменных, при котором получится значение «1»: `L=1`, `K=1`, `N=0`, `M=0`.
Сколько решений имеет уравнение:
`(((K¬L¬N) (¬L -> M))` \/ `((¬K` \/ `L` \/ `N) (¬L¬M))) (K`\/`N)=1`
Исходное выражение достаточно сложное, поэтому будем его упрощать. Первым делом избавимся от импликаций, получим:
`(((K¬L¬N) (L`\/ `M))` \/ `((¬K` \/ `L` \/ `N) (¬L¬M))) (K`\/`N) = 1`
Теперь раскроем скобки. Для упрощения условимся не записывать слагаемые, куда одновременно входят некоторая переменная и её отрицание (они всё равно равны нулю):
`(K¬L¬NM` \/ `¬K¬L¬M` \/ `N¬L¬M) (K`\/`N) = 1`
Продолжаем раскрытие скобок. Получаем:
`K¬L¬NM` \/ `¬K¬L¬MN` \/ `KN¬L¬M` \/ `N¬L¬M = 1`
Ко второму, третьему и четвёртому слагаемому можно применить тождество поглощения. В итоге получится:
`K¬L¬NM` \/ `N¬L¬M = 1`
На этом упрощение закончено, теперь будем анализировать. Дизъюнкция равна единице, если хотя бы одно из слагаемых равно единице. Первое слагаемое равно единице на единственном наборе переменных: (`K=1`, `L=0`, `N=0`, `M=1`). Второе слагаемое равно единице на двух наборах: (`N=1`, `L=0`, `M=0`, `K` – любое (или `0` или `1`)). Соответственно, уравнение имеет три различных решения.
В нарушении правил обмена валюты подозреваются четыре работника банка - Антипов (`A`), Борисов (`B`), Цветков (`C`) и Дмитриев (`D`). Известно, что:
1) Если `А` нарушил, то и `В` нарушил правила обмена валюты.
2) Если `B` нарушил, то и `C` нарушил или `A` не нарушал.
3) Если `D` не нарушил, то `A` нарушил, а `C` не нарушал.
4) Если `D` нарушил, то и `A` нарушил.
Кто из подозреваемых нарушил правила обмена валюты?
Чтобы решить эту задачу, необходимо провести процесс формализации условия, сформировать единое логическое выражение и провести его упрощение. Выделим из условия четыре простых высказывания: «`A` нарушил правила», «`B` нарушил правила», «`C` нарушил правила», и «`D` нарушил правила». Обозначим их соответственно буквами `A`, `B`, `C`, `D`. Тогда высказывания из условия формализуются следующим образом (конъюнкция не обозначается никак):
1) `A -> B`;
2) `B -> C` \/ `¬A`;
3) `¬D -> A¬ C`;
4) `D -> A`.
Нам известно, что выполняются все 4 высказывания, следовательно, нужно объединить их знаками конъюнкции и найти наборы, при которых получившееся общее высказывание будет истинным. Эти наборы и покажут нам, какие возможны ситуации (правила обмена нарушил тот, у кого переменная в итоговом наборе имеет значение «1»).
Итак, строим логическое выражение:
`(A -> B)( B -> C` \/ `¬A)( ¬D -> A¬C)( D -> A)`.
Теперь будем его упрощать. По алгоритму первым делом избавляемся от операции импликации. Получаем следующее выражение:
`(¬A` \/ `B)( ¬B` \/ `C` \/ `¬A)( D` \/ `A¬C)( ¬D` \/ `A)`.
Раскрываем скобки. Первую перемножаем со второй, а третью с четвёртой.
`(¬A¬B` \/ `¬AC` \/ `¬A` \/ `BC` \/ `B¬A) ( DA` \/ `A¬C¬D` \/ `A¬C)`.
Напомним, что слагаемые, равные нулю по причине того, что в них входит сразу и переменная и её отрицание, мы не записываем. В первой скобке теперь можно применить тождество поглощения, и «съесть» все слагаемые, имеющие в своём составе `A` с отрицанием. Во второй скобке можно также применить тождество поглощения, и «съесть» второе слагаемое. В итоге получаем:
`( ¬A` \/ `BC ) ( DA` \/ `A¬C)`.
При раскрытии оставшихся скобок три из четырёх слагаемых окажутся равными нулю, а последнее будет выглядеть следующим образом: `ABCD`. Из этого следует, что все четверо работников банка нарушили правило обмена валюты. (Только в этой ситуации предположения из условия задачи одновременно выполняются).
Правила обмена валюты нарушили все.
Известно, что обе надписи на дверях либо истинны, либо ложны одновременно. Надпись на первой двери – "Клад за другой дверью", на второй двери – "Клада за этой дверью нет, а за другой – есть". Где находится клад?
По сути нас интересуют два простых высказывания: «Клад есть за первой дверью» и «Клад есть за второй дверью». Обозначим первое из них буквой `A`, а второе буквой `B`. Тогда изначальные предположения формализуются следующим образом:
1) `B`;
2) `¬BA`.
В этой задаче в отличие от предыдущей у нас две возможные ситуации относительно комбинирования начальных предположений – они либо оба истинны, либо оба ложны. Предположим, что они оба истинны, тогда при их перемножении получится тождественный ноль, что означает невозможность данной ситуации.
Предположим, что оба высказывания ложны, тогда необходимо перед перемножением на каждое из них «навесить» отрицание (рассматривать истинность противоположных высказываний) В итоге получится следующее логическое выражение:
`¬B ¬(¬BA)`.
Упрощаем его по алгоритму: отрицание продвигаем вглубь, применяя тождество Де Моргана. Получаем:
`¬B (B` \/ `¬A)`.
Раскроем скобки. Первое слагаемое сокращается, а второе выглядит следующим образом: `¬B¬A`.
Полученный результат означает, что условия задачи выполняются, только в случае, когда оба высказывания ложны, а это означает, что клада нет ни за одной дверью. Не повезло нам `J`.
Клада нет ни за одной дверью.
В заключение приведём общую схему решения текстовых логических задач, которую мы уже применяли на практике при разборе примеров.
1) Выделить из условия задачи элементарные (простые) высказывания и обозначить их буквами.
2) Записать условие задачи на языке алгебры логики, соединив простые высказывания в сложные с помощью логических операций.
3) Составить единое логическое выражение для всех требований задачи (возможно не одно).
4) Используя законы алгебры логики попытаться упростить полученное выражение и вычислить все его значения либо построить таблицу истинности для рассматриваемого выражения (Таблицу можно строить, если в выражении не более трёх логических переменных).
5) Выбрать решение — набор значений простых высказываний, при котором построенное логическое выражение является истинным;
6) Проверить, удовлетворяет ли полученное решение условию задачи.
Среди задач алгебры логики часто встречаются задачи на определение количества решений систем логических уравнений. Рассмотрим примеры некоторых их них.
Найдите количество решений системы уравнений:
`(x2-=x1)+x2&x3+ not x2& not x3=1`
`(x3-=x1)+x3&x4+ not x3& not x4=1`
`…`
`(x9-=x1)+x9 & x10+ not x9 & not x10=1`
`(x10 -= x1)=0`
где `x1 … x10` - неизвестные логические величины
Упростим исходные уравнения, заметив, что, `(x2&x3+ not x2& notx3=(x2-=x3)`. Исходную систему запишем в виде:
`(x2-=x1)+(x2-=x3)=1`
`(x3-=x1)+(x3-=x4)=1`
`…`
`(x9-=x1)+(x9-=x10)=1`
`(x10&x1)=0`
В первом уравнении используются три переменных `x1`, `x2` и `x3`. Значения `x1` и `x2` могут быть выбраны произвольно четырьмя способами:
|
`bb(x1)` |
`bb(x2)` |
`bb(x3)` |
|
`0` |
`0` |
`0` |
|
`0` |
`0` |
`1` |
|
`0` |
`1` |
`1` |
|
`1` |
`0` |
`0` |
|
`1` |
`1` |
`0` |
|
`1` |
`1` |
`1` |
Если `x2=x1`, то значение `x3` может быть любое (эти строки выделены серым цветом), а при `x2!=x1` получаем только один вариант: `x3=x2`.
Таким образом, при подключении первого уравнения число решений увеличивается на количество строк в таблице, для которых значения `x1` и `x2` (последней рассмотренной переменной) равны. В данном случае таких строк две, получаем 6 решений. Более того, в новой таблице снова осталось всего две строки (верхняя и нижняя), где `x3=x1`. Как следует из второго уравнения, именно эти (и только эти) строки на следующем шаге “раздваиваются”, дают по два решения. Таким образом, при подключении к системе очередного уравнения число решений увеличивается на `2`. Для двух уравнений получим 8 решений, для трёх - 10, а для восьми - 20 решений.
Остается учесть последнее (особое) уравнение, `(x10-=x1)=0`. Это означает, что `x10!=1`. Из анализа таблицы видно, что есть всего две строки (верхняя и нижняя), где первая и последняя переменные равны. Поэтому из полученных 20 решений нужно отбросить эти два, не удовлетворяющие последнему уравнению. В итоге исходная система имеет 18 решений.
Найдите количество решений системы уравнений:
`not x1+x2=1`
`not x2+x3=1`
`…`
`not x9+x10=1`
где `x1 … x10` - неизвестные логические величины
`(not x1 + x2)&( not x2 + x3) &…&(not x9 + x10)=1`
однако это не упрощает решения.
Можно заметить, что первое уравнение зависит только от `x1` и `x2`, а каждое новое уравнение добавляет по одной новой переменной. Поэтому можно решать систему последовательно с помощью построения таблицы. Первое уравнение, `not x1+x2=1`, обращается в истинное равенство в трех случаях:
| `bb(x1)` | `bb(x2)` |
| `0` | `0` |
| `0` | `1` |
| `1` | `1` |
Подключив второе уравнение, `not x2+x3=1`, заметим, что допустимые значения `x3` зависят от ранее выбранного значения `x2`: если `x2=0`, то `x3` может принимать любое значение (`0` или `1`), а если `x2=1`, то `x3=1`. Соответствующая таблица выглядят так:
|
`bb(x1)` |
`bb(x2)` |
`bb(x3)` |
|
`0` |
`0` |
`0` |
|
`1` |
||
|
`0` |
`1` |
`1` |
|
`1` |
`1` |
`1` |
Легко заметить, что при добавлении очередного уравнения верхняя строка таблицы дает два решения (они выделены серы м цветом), а остальные строки - по одному. Поэтому количество решений увеличивается на `1`. Таким образом, система из трёх уравнений имеет 5 решений, из четырех - 6, а исходная система из девяти уравнений - 11 решений.
11 решений.
Заметим, что часто перед решением больших систем логических уравнений сначала удобно упростить исходную систему с помощью законов алгебры логики, а также воспользоваться заменой переменных, если это возможно.
Подобно предыдущему заданию, теперь мы вновь перейдём к изучению программирования и применим полученные знания по алгебре логики на практике.
В прошлом задании мы работали с числовыми типами переменных и учили арифметику, теперь познакомимся с логическим типом переменных, который называется Boolean. Переменные этого типа имеют всего два значения – true и false (соответственно, «истина» и «ложь»). Подобно числовым переменным им можно присваивать значения при помощи оператора присваивания. При этом необходимо строго соблюдать правило совместимости типов. То есть логическим переменным нельзя присваивать числовые значения, а числовым – логические.
В языке Паскаль помимо арифметических операций ещё существует `6` операций сравнения: больше» `(>)`, «больше или равно» `(> =)`, «меньше» `(<)`, «меньше или равно» `(< =)`, «равно» `(=)`, и «не равно» `(<>)`. Операция «не равно» записывается, как последовательность знаков «меньше» и «больше». Результатом каждой из этих операций является логическое значение true или false. Например, операция `5 > 2` выдаст значение true, а операция `x<>3` выдаст значение true, если переменная `X` имеет любое значение, кроме `3`. Сравнивать можно не только числа (причём как целые, так и вещественные), но и логические значения. При этом считается, что значение true больше, чем значение false. При сравнении обязательно соблюдать правило совместимости типов, то есть можно сравнивать числа между собой (причём в отличие от оператора присваивания, здесь никаких ограничений нет). Можно сравнивать между собой логические значения. Но нельзя сравнивать логическое значение с числом любого типа.
Помимо операций сравнения, в паскале существуют четыре логические операции, абсолютно аналогичные операциям алгебры логики.
1) Операция AND (в алгебре логики – «конъюнкция»)
2) Операция OR (в алгебре логики – «дизъюнкция»)
3) Операция XOR (в алгебре логики – «строгая дизъюнкция»)
4) Операция NOT (в алгебре логики – «отрицание»)
Все операнды этих операций должны быть логического типа, а никак не числового. Причём, операции AND, OR и XOR имеют по `2` операнда, а операция NOT – один операнд, который записывается справа от названия операции (аналогично обозначению операции NOT при помощи `¬` в алгебре логики)
Теперь у нас есть достаточно много операций и нужно расставить их по приоритету выполнения. В Паскале есть четыре приоритета операций:
1) Операция not;
2) Операции группы умножения: *, /, div, mod, and;
3) Операции группы сложения: +, – , or, xor;
4) Операции группы сравнения: >, <, <=, >=, =, <>.
Операции одного приоритета выполняются слева направо. Операции в круглых скобках имеют более высокий приоритет, чем вне скобок.
Теперь рассмотрим несколько примеров задач на использование логического типа.
Записать на Паскале логическое выражение истинное при выполнении указанного условия и ложное в противном случае. Результат вычисления данного выражения присвоить переменной F.
Числовая переменная X имеет значение на отрезке [–1,1].
F:=abs(X)<=1;
Числовая переменная X имеет значение на отрезке [2,7].
F:=(X>=2)and(X<=7).
Обратите внимание на скобки. Они обязательны, поскольку операции сравнения имеют более низкий приоритет, чем операция and.
Числовая переменная X имеет значение на одном из 2 отрезков: [–10, 3] или [10, 20].
F:=(X>=-10)and(X<=3)or(X>=10)and(X<=20).
Логические переменные A и B имеют различные значения.
F:=A<>B.
По крайней мере 2 из логических переменных A, B и C имеют значение true.
F:=A and B or A and C or B and C.
:
Алгебра логики является частью активно развивающейся сегодня науки – дискретной математики. Дискретная математика – это тот раз-дел математики, где не используется понятие непрерывности.
1) Состоящий из отдельных частей.
2) Изменяющийся между несколькими стабильными состояниями.
3) Существующий лишь в отдельных точках.
Для того, чтобы лучше понять этот термин, рассмотрим следующий пример. Мы знаем, что график некоторой функции (например, `y=x^2`) является непрерывной линией (параболой), если аргумент функции принимает все значения из множества действительных чисел. А теперь представим, что `x` может принимать только значения из множества целых чисел. В этом случае график будет представлять собой бесконечное количество отдельных точек, располагающихся на координатной плоскости в определённом порядке. В расположении точек будет угадываться парабола, но непрерывной линии мы не увидим. Вместо неё мы увидим дискретную структуру.
В прошлом задании мы говорили о представлении чисел в компьютере, и знаем, что каждое число представляется в виде определённой последовательности значений битов. В каждом бите может храниться ноль или единица. То есть, по сути, представление чисел (в будущем мы увидим, что не только чисел, а вообще любых данных) в компьютере является дискретной структурой. Поэтому, изучение дискретных структур – важная часть информатики. В этом задании мы будем изучать наиболее простую дискретную структуру, которая называется высказыванием.
Высказывание – это повествовательное предложение, в отношении которого можно судить о его истинности либо ложности.
Например, предложение: «Я – твой друг» является высказыванием, а предложение: «Положи это сюда!» высказыванием не является, поскольку не является повествовательным предложением.
Истинность или ложность каждого высказывания зависит от трактовки его содержания. Например, высказывание: «Город Москва – столица России» является истинным, а высказывание: «Город Санкт-Петербург стоит на реке Лене» является ложным.
Высказывание называется простым, если никакая его часть сама по себе не является высказыванием.
Высказывание: «Эта шляпа – красная» является простым, в то время как высказывание: «Если прямая пересекает одну из двух параллельных прямых, то она пересекает и вторую» является примером сложного высказывания, которое, по сути, состоит из трёх простых: «две прямые параллельны», «прямая пересекает одну из двух прямых», «прямая пересекает другую прямую». В сложном высказывании простые высказывания соединяются при помощи логических связок. В рассмотренном выше примере логической связкой является союз «если то».
Алгебра логики изучает структуру сложных логических высказываний и способы установления их истинности при помощи алгебраических методов. Причём, конкретное содержание высказываний предметом изучения алгебры логики не является, и, соответственно, интересовать нас в дальнейшем не будет.
В прошлом задании при изучении основ программирования мы столкнулись с понятиями констант и переменных. Константа – это некоторое конкретное значение, а переменная – это объект, который может менять свои значения и которому можно присваивать различные значения. Этими же понятиями пользуется и алгебра логики, чтобы абстрагироваться от конкретных содержаний высказываний. Будем считать, что любое простое высказывание – это есть константа. И введём понятие переменной в алгебре логики.
Переменной в алгебре логики называется объект, имеющий уникальное имя, и значением которого может являться любое простое высказывание.
В отличие от языков программирования в алгебре логики нет ограничений при именовании переменных. Переменные могут иметь абсолютно любые имена, но чаще всего их обозначают заглавными или строчными латинскими буквами (`A, B, C, x, y, z, s`), либо последовательностью, состоящей из заглавной или строчной латинской буквы и целого числа (`A1, A2, A4, A10000000`). Ещё одно отличие от языков программирования заключается в том, что после присвоения переменной высказывания можно говорить об её истинности либо ложности. То есть существует два понятия «значение логической переменной». С одной стороны – это конкретное высказывание, а с другой стороны – это истина, либо ложь.
Логическим выражением называется объект, состоящий из логических переменных и логических операций и имеющий значение истина, либо ложь. Процесс построения логического выражения по сложному высказыванию называется формализацией высказывания.
В процессе формализации нужно сделать следующие действия: выделить из сложного высказывания простые и превратить их в логические переменные. Затем каждая логическая связка превращается в логическую операцию. В описанных действиях остаётся два непонятных момента. Первый – что такое логическая операция, и второй – каким образом логические связки превращаются в логические операции. Будем последовательно отвечать на эти вопросы.
Для того чтобы определить операцию, необходимо указать количество операндов (объектов, над которыми выполняется операция) их тип и результат выполнения операции. Логические операции чаще всего имеют два операнда, как и математические. Однако мы также будем изучать операции, которые имеют всего один операнд. Независимо от количества операнды должны быть логического типа, то есть иметь значение истина, либо ложь. Результатом логической операции также является логическое значение – истина или ложь. Для того чтобы немного сократить запись, условимся в дальнейшем логическое значение «истина» обозначать единичкой `(1)`, а логическое значение – «ложь» – нулём `(0)`.
Очевидно, что если у операции два операнда, и значением каждого является `0` или `1`, то существует всего четыре набора значений операндов `(00, 01, 10, 11)`. Для каждого из наборов необходимо определить значение логической операции. Удобно это представлять в виде таблицы. Таблицы соответствия значений логических операций набору значений операндов называются таблицами истинности.
