![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Entry tags:
Проект "логика для чайников". Параграф 43
Свойства логических операций (две алгебры)
Алгебра логики, булева алгебра – очень удачные термины не только формально, но и по сходству с обычной, школьной алгеброй. Здесь тоже есть свои законы перестановки, раскрытия скобок, приведения подобных членов и тому подобные вещи.
Эти законы в самой сложной форме и чаще всего применяются при разработке компьютерных микросхем, реже и проще – в программировании. В обычных логических рассуждениях могут пригодиться самые простые.
Как уже говорилось, можно переставлять местами операнды операций И, ИЛИ, XOR и передвигать скобки:
a И b = b И a
a И (b И c) = (a И b) И c
Похоже на законы перестановки слагаемый и передвигание скобок в обычной алгебре.
Так же можно “выносить за скобки”:
(x И y) ИЛИ (x И z) = x И (y ИЛИ z)
Сравните:
xy + xz = x(y + z)
То же самое относится к операции XOR:
(x И y) XOR (x И z) = x И (y XOR z)
Получается, что операция И играет роль умножения, а операции ИЛИ, XOR – роль сложения.
Но есть и отличия. Например, в логике можно и вот так:
(x ИЛИ y) И (x ИЛИ z) = x ИЛИ (y И z)
Сравните:
(x + y) (x + z) = x + (yz)
Последнее равенство, конечно же, неправильное, так что сходство между логической алгеброй и обычной – не совсем полное.
Зная эти законы, можно выводить новые формулы. Например, можно доказать, что x ИЛИ (x И y) = x:
x ИЛИ (x И y) = (x И true) ИЛИ (x И y) = x И (true ИЛИ y) = x И true = x
Поясню переходы.
Первое равенство использует закон поглощения: x = x И true.
Второе равенство – это вынесение x за скобки.
Третье равенство – закон поглощения true ИЛИ y = true.
Четвертое равенство – закон поглощения x ИЛИ true = x.
По аналогии с обычной алгеброй в логике вводят разные сокращения для удобства. Например, в обычной алгебре не пишут “плюс”, “минус”, а применяют значки “+”, “-“. В логике есть значки “~” (НЕ), “&” (И), \/ (ИЛИ), Е (XOR).
В обычной алгебре знак умножения часто не пишут: xy + z. В алгебре логики часто опускают знак логического И: xy ⊕ z.
В обычной алгебре у операций имеются приоритеты, что позволяет обходиться без лишних скобок. В алгебре логики – то же самое. Причем, приоритеты расставляются по тому же принципу: сначала “НЕ” (в обычной алгебре наивысший приоритет у операции смены знака), потом “И” (в обычной алгебре средний приоритет имеют умножение и деление), потом ИЛИ, XOR (в обычной алгебре наименьший приоритет у сложения и вычитания).
Например, в алгебре логики можно написать вот так: ~x \/ xz (z \/ ~y).
В обычной алгебре это могло бы выглядеть так: -x + xz (z + -y).
Некоторые логические законы поглощения похожи на обычную алгебру. Сравните:
x + 0 = x ---- x \/ false = x
x + 0 = x ---- x ⊕ false = x
x * 0 = 0 ---- x & false = false
x * 1 = x ---- x & true = x
Но не всегда, в алгебре логики таких сокращений больше, а некоторые отличаются:
x + 1 = ? ---- x \/ true = true
x + x = 2x ---- x \/ x = x
x * x = x2 ---- x & x = x
Самое “неприятное” отличие, пожалуй, связано с операцией отрицания: когда она стоит перед скобками, то скобки раскрываются иначе:
-(x + y) = -x + -y
-(x * y) = -x * -y
~(x & y) = ~x \/ ~y
~(x \/ y) = ~x & ~y
~(x ⊕ y) = true ⊕ x ⊕ y
Третья и четвертая формулы называются законами Де Моргана.
Что из всего перечисленного есть смысл запоминать? В принципе, можно ничего не запоминать, есть справочник:
http://psi-logic.shadanakar.org/bool/bool6.htm
Хуже всего с законами поглощения: их много, и они почти все важны. Наверное, есть смысл не запоминать их, а научиться быстренько выводить “в уме”.
Если вы не собираетесь вдаваться в программирование и схемотехнику, но предполагаете применять логику в жизни, подчас для сложных рассуждений, тогда я бы порекомендовал запомнить только следующие шесть формул:
~~x = x
~(x & y) = ~x \/ ~y
~(x \/ y) = ~x & ~y
x & (y \/ z) = xy \/ xz
x & ~x = false
x \/ ~x = true
Плюс то, что можно переставлять местами операнды операций &, \/, ⊕, и передвигать для них скобки. Я думаю, это такой разумный минимум, все остальное пригождается реже, и можно освежить в памяти по справочнику.
Алгебра логики, булева алгебра – очень удачные термины не только формально, но и по сходству с обычной, школьной алгеброй. Здесь тоже есть свои законы перестановки, раскрытия скобок, приведения подобных членов и тому подобные вещи.
Эти законы в самой сложной форме и чаще всего применяются при разработке компьютерных микросхем, реже и проще – в программировании. В обычных логических рассуждениях могут пригодиться самые простые.
Как уже говорилось, можно переставлять местами операнды операций И, ИЛИ, XOR и передвигать скобки:
a И b = b И a
a И (b И c) = (a И b) И c
Похоже на законы перестановки слагаемый и передвигание скобок в обычной алгебре.
Так же можно “выносить за скобки”:
(x И y) ИЛИ (x И z) = x И (y ИЛИ z)
Сравните:
xy + xz = x(y + z)
То же самое относится к операции XOR:
(x И y) XOR (x И z) = x И (y XOR z)
Получается, что операция И играет роль умножения, а операции ИЛИ, XOR – роль сложения.
Но есть и отличия. Например, в логике можно и вот так:
(x ИЛИ y) И (x ИЛИ z) = x ИЛИ (y И z)
Сравните:
(x + y) (x + z) = x + (yz)
Последнее равенство, конечно же, неправильное, так что сходство между логической алгеброй и обычной – не совсем полное.
Зная эти законы, можно выводить новые формулы. Например, можно доказать, что x ИЛИ (x И y) = x:
x ИЛИ (x И y) = (x И true) ИЛИ (x И y) = x И (true ИЛИ y) = x И true = x
Поясню переходы.
Первое равенство использует закон поглощения: x = x И true.
Второе равенство – это вынесение x за скобки.
Третье равенство – закон поглощения true ИЛИ y = true.
Четвертое равенство – закон поглощения x ИЛИ true = x.
По аналогии с обычной алгеброй в логике вводят разные сокращения для удобства. Например, в обычной алгебре не пишут “плюс”, “минус”, а применяют значки “+”, “-“. В логике есть значки “~” (НЕ), “&” (И), \/ (ИЛИ), Е (XOR).
В обычной алгебре знак умножения часто не пишут: xy + z. В алгебре логики часто опускают знак логического И: xy ⊕ z.
В обычной алгебре у операций имеются приоритеты, что позволяет обходиться без лишних скобок. В алгебре логики – то же самое. Причем, приоритеты расставляются по тому же принципу: сначала “НЕ” (в обычной алгебре наивысший приоритет у операции смены знака), потом “И” (в обычной алгебре средний приоритет имеют умножение и деление), потом ИЛИ, XOR (в обычной алгебре наименьший приоритет у сложения и вычитания).
Например, в алгебре логики можно написать вот так: ~x \/ xz (z \/ ~y).
В обычной алгебре это могло бы выглядеть так: -x + xz (z + -y).
Некоторые логические законы поглощения похожи на обычную алгебру. Сравните:
x + 0 = x ---- x \/ false = x
x + 0 = x ---- x ⊕ false = x
x * 0 = 0 ---- x & false = false
x * 1 = x ---- x & true = x
Но не всегда, в алгебре логики таких сокращений больше, а некоторые отличаются:
x + 1 = ? ---- x \/ true = true
x + x = 2x ---- x \/ x = x
x * x = x2 ---- x & x = x
Самое “неприятное” отличие, пожалуй, связано с операцией отрицания: когда она стоит перед скобками, то скобки раскрываются иначе:
-(x + y) = -x + -y
-(x * y) = -x * -y
~(x & y) = ~x \/ ~y
~(x \/ y) = ~x & ~y
~(x ⊕ y) = true ⊕ x ⊕ y
Третья и четвертая формулы называются законами Де Моргана.
Что из всего перечисленного есть смысл запоминать? В принципе, можно ничего не запоминать, есть справочник:
http://psi-logic.shadanakar.org/bool/bool6.htm
Хуже всего с законами поглощения: их много, и они почти все важны. Наверное, есть смысл не запоминать их, а научиться быстренько выводить “в уме”.
Если вы не собираетесь вдаваться в программирование и схемотехнику, но предполагаете применять логику в жизни, подчас для сложных рассуждений, тогда я бы порекомендовал запомнить только следующие шесть формул:
~~x = x
~(x & y) = ~x \/ ~y
~(x \/ y) = ~x & ~y
x & (y \/ z) = xy \/ xz
x & ~x = false
x \/ ~x = true
Плюс то, что можно переставлять местами операнды операций &, \/, ⊕, и передвигать для них скобки. Я думаю, это такой разумный минимум, все остальное пригождается реже, и можно освежить в памяти по справочнику.
no subject
А знаешь, что можно работать с обычными числами, но вместо плюса искать максимум, а вместо умножения максимум?
no subject
x \/ y = max(x,y)
x & y = min(x,y)
если истинность выражать числами 0, 1
no subject
no subject
no subject
no subject
no subject