Булева алгебра и построение логических схем. Логические и битовые операции: AND, OR, NOT, XOR - таблицы значений
Математическая логика изучает методы и средства оперирования логическими формулами (выражениями). В этом уроке мы изучим обозначения, синтаксис (грамматику) и семантику (значение) различных логических выражений.
Высказывание и операции над высказыванием
Исходным (базовым) понятием является простое высказывание.
Под высказыванием обычно понимают всякое предположение, утверждающее что-либо о чем-либо. Если смысл, содержащийся в высказывании, соответствует действительности, то высказывание является истинным, иначе ложным.
Обычно элементарные высказывания обозначают строчными буквами латинского алфавита $a$, $b$, $c$, $x$, $y$ …, которые являются логическими переменными в логических формулах. Истинные значения обозначаются буквой И (True, T) или 1, а ложные – Л (False, F) или 0.
Унарные функции
$n = 1$ - количество аргументов. $k_n = 2^n = 2$ $k_ф = 2$
Бинарные функции
$n = 2$ - количество аргументов. $k_n = 2^2 = 4$ $k_ф = 2^4 = 16$
| $x$ | $y$ | $f_0$ | $f_1$ | $f_2$ | $f_3$ | $f_4$ | $f_5$ | $f_6$ | $f_7$ | $f_8$ | $f_9$ | $f_{10}$ | $f_{11}$ | $f_{12}$ | $f_{13}$ | $f_{14}$ | $f_{15}$ |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| const "0" | $x \land y$ | пер. $x$ | пер. $y$ | $x \xor y$ | $x \lor y$ | const "1" |
Номер функции совпадает с двоичной записью функции
- $f_1$ - коньюнкция. $x \& y$ - $x$ и $y$ - ${x} and {y}$ $x \&\& y$
- $f_7$ - дизъюнкция. $x | y$ - $x$ или $y$
- $f_{11}$ и $f_{13}$ - импликация (следование)
- $f_9$ - равнозначность, эквивалентность, равносильность. ${x} \equiv {y}$
- $f_6$ - равнозначность, эквивалентность, равносильность. ${x} \equiv {y}$
Из элементарных высказываний можно составить более сложные с помощью логических связок:
- $\lnot$ - логическое "не" (отрицание)
- $\land$ - логическое "и" (конъюнкция) - "и одновременно"
- $\lor$ - логическое "или" (дизъюнкция)
- $\Rightarrow$ - "логическое следствие" (импликация)
- $\equiv$ - "эквивалентность"
- круглых скобок (, ) - групировка операций.
- ...есть и другие (менее распространённые) связки...
Логические связки можно определить с помощью таблицы истинности. В левой части этой таблицы перечисляются все возможные комбинации значений логических переменных $x$ и $y$. В правой части – соответствующие им им значения выражений из переменных и логических связок.
| $x$ | $y$ | $\lnot x$ | $x \land y$ | $x \lor y$ | $x \Rightarrow y$ | $x \equiv y$ |
| 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 |
Связки имеют следующий приоритет: $\lnot \land \lor \Rightarrow \equiv$ (приоритет можно изменить с помощью скобок). Высказывания (формулы) из простых высказываний, связок и скобок, называют правильно построенными формулами или просто формулами.
Значение логических связок близко к соответствующим высказываниям на естественном языке. Например смысл связок $\lnot$ и $\land$ практически совпадает со смыслом слов «не» и «и». Однако имеются и некоторые различия. Так формула $x \lor y$ несколько шире, чем русское «$x$ или $y$». Выражение «$x$ или $y$» по смыслу это формула $x \land \lnot y \lor \lnot x \land y$ (исключающее или). Еще больше различий между семантикой формулы $x \Rightarrow y$ в логике высказываний и выражению «из $x$ следует $y$». В русском языке это выражение истинно, если истинны $x$ и $y$, т.е. предложение русского языка по смыслу совпадает с формулой $x \land y$. Логическое следствие истинно также, если $x$ и $y$ ложны или $x$ ложна, а $y$ истинна. Логическую формулу $x \Rightarrow y$ следует интерпретировать на естественном языке так: «Если $x$ истинна, то $y$ тоже истинна, а остальное неизвестно».
Таблица истинности - таблица в которой в левой части перечислены все возможные значения переменных, а в правой части значения функции. Для построения таблицы истинности выписываются все возможные значения аргументов, а потом поэтапно вычисляем значения.
Для любой формулы также можно написать таблицу истинности. Например:
| $x$ | $y$ | $\lnot x$ | $\lnot y \lor y$ | $\lnot x \land (\lnot y \lor y)$ | $\lnot x \land (\lnot y \lor y) \Rightarrow \lnot x$ |
| 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 |
Если формула содержит $n$ переменных, то в таблице истинности будет $2^n$ строк (в примере формула содержит 2 переменные и $2^2 = 4$ строки). Кроме того, данная формула истинна на любом наборе значений своих переменных (везде 1). Такие формулы называются тождественно истинными или тавтологиями. В противоположной ситуации, формула является тождественно ложной или невыполнимой. Если две разные формулы принимают одинаковые значения на любом наборе значений переменных, то такие формулы называют равносильными. Равносильные формулы обозначаются знаком равенства =.
Законы алгебры логики
В логике высказываний известно много общезначимых формул, которые также называются законами логики высказываний. Основными законами являются следующие:
- законы идемпотентности (повторение действия над объектом не изменяет его, латинский idem - «тот же
самый»
и potens - «способный»):
- $x \land x = x$
- $x \lor x = x$
- $x \land 1 = x$ - $x$ и Истина всегда будет $x$
- $x \lor 1 = 1$ - $x$ или Истина всегда будет Истина
- $x \land 0 = 0$
- $x \lor 0 = x$
- $x \land \lnot x = 0$ – закон противоречия
- $x \lor \lnot x = 1$ – закон исключения третьего
- $\lnot \lnot x = x$ – закон снятия двойного отрицания
- законы поглощения
- $x \land (y \lor x) = x$
- $x \lor (y \land x) = x$
Доказать эти и последующие законы можно с помощью построения таблиц истинности или
простейших логических рассуждений.
Следующая группа законов представляет взаимосвязь между логическими операциями:
- $(x \equiv y) = (x \Rightarrow y) \land (y \Rightarrow x)$
- $x \Rightarrow y = \lnot x \lor y$
- законы Де Моргана
- $\lnot(y \lor x) = \lnot y \land \lnot x$
- $\lnot(y \land x) = \lnot y \lor \lnot x$
Замечательным следствием приведенных выше законов является следующий факт. Любую логическую формулу можно заменить равносильной ей, но содержащую только две логические операции:
- конъюнкцию "и" и отрицание "не"
- дизъюнкцию "или" и отрицание "не"
Дальнейшее исключение логических операций, очевидно, невозможно, то есть приведенные пары представляют минимальный базис для построения правильно построенных формул. Однако существует операция, с помощью которой можно представить любую логическую связку. Эта операция получила название «штрих Шеффера» и определяется следующим образом:
| $x$ | $y$ | $x | y$ |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
На основании этого определения можно ввести следующие законы, выражающие взаимосвязь операции «штрих Шеффера» и других логических связок:
- $\lnot x = x | x$ - связка "не" через «штрих Шеффера»
- $x \land y = (x | y) | (x | y)$ - связка "и" через «штрих Шеффера»
Также следует отметить, что $x | y= \lnot (x \lor y)$.
К основным законам алгебры логики также относятся следующие:
- коммутативные законы (от перестановки мест результат не меняется)
- $x \land y = y \land x$
- $х \lor y = y \lor x$
- дистрибутивные законы (правила группировки)
- $x \land (y \lor z) = (x \land y) \lor (x \land z)$
- $x \lor (y \land z) = (x \lor y) \land (x \lor z)$
- ассоциативные законы
- $x \land (y \land z) = (x \land y) \land z$
- $x \lor (y \lor z) = (х \lor y) \lor z$
С помощью законов логики можно осуществлять равносильные преобразования. Такие преобразования используются для доказательств, приведения формул к заданному виду, упрощения формул.
Под сложностью формул обычно понимается количество символов, используемых для ее записи. То есть формула $\alpha$ проще формулы $\beta$, если $\alpha$ содержит меньше букв и логических операций. Например, для формулы $(\lnot (x \lor y) \Rightarrow x \lor y) \land y$ можно записать следующую цепочку преобразований, приводящих ее к более простому виду:
$(\lnot \lnot(x \lor y) \lor x \lor y) \land y = (x \lor y \lor x \lor y) \land y = (x \lor y) \land y = y$.
Операция XOR
Операция XOR - это операция "побитное не равно" или сложение по модулю 2 для отдельных битов, в логике обозначается $x \oplus y$.
| $x$ | $y$ | $x \oplus y$ | $x \oplus x$ | $y \oplus y$ |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 0 | 0 |
Задача "Повторные числа"
Входной файл содержит большое число чисел (целых или действительных) или строк, среди них все повторяются чётное число раз, и только одно - нечётное число раз. Вывести то, которое повторяется нечётное число раз.
Решение: завести переменную нужного типа, инициализировать её нулями, выполнять операцию XOR с каждым новым числом (строкой), в результате останется только число (строка), встречающаяся нечётное число раз.
{$APPTYPE CONSOLE}
var
N : integer; { Количество чисел во входном файле }
i : integer; { Счётчик цикла (1..N) }
X : int64; { Очередное число из входного файла }
Res : int64; { Результат }
begin
Reset(Input,'repeat.in');
Rewrite(Output,'repeat.out');
Read(N); { Читаем количество чисел из входного файла }
Res := 0; { Обнуляем результат }
for i:=1 to N do begin
Read(X); { Читаем очередное число X из входного файла }
Res := Res XOR X; { Выполняем операцию XOR }
end;
Writeln(Res); { Записываем результат в выходной файл }
end.
Вычисление значения логического выражения
Для вычисления значения логического выражения мы можем просто поставить (replace) переменные как значения, потом прогнать все операции с наибольшим приоритетом (логическое НЕ, затем И), затем в операциях с меньшим приоритетом (ИЛИ).