Алгебра логики
Алгебра логики (алгебра высказываний) — раздел математической логики, в котором изучаются логические операции над высказываниями[1]. Чаще всего предполагается, что высказывания могут быть только истинными или ложными, то есть используется так называемая бинарная или двоичная логика, в отличие от, например, троичной логики.
Содержание
Определение
Базовыми элементами, которыми оперирует алгебра логики, являются высказывания.
Высказывания строятся над множеством {B, <math>\lnot</math>, <math>\land</math>, <math>\lor</math>, 0, 1}, где B — непустое множество, над элементами которого определены три операции:
- <math>\lnot</math> отрицание (унарная операция),
- <math>\land</math> конъюнкция (бинарная),
- <math>\lor</math> дизъюнкция (бинарная),
а логический ноль 0 и логическая единица 1 — константы.
Так же используются названия
- Дизъю́нкт — пропозициональная формула, являющаяся дизъюнкцией одного или более литералов (например <math>x_1 \lor \neg x_2 \lor x_4</math>).
- Конъюнкт — пропозициональная формула, являющаяся конъюнкцией одного или более литералов (например <math>x_1 \land \neg x_2 \land x_4</math>).
Унарная операция отрицания в тексте формул оформляется либо в виде значка перед операндом (<math>\lnot x</math>) либо в виде черты над операндом (<math>\bar x</math>), что компактнее, но в целом менее заметно.
Аксиомы
- <math>\bar {\bar x}=x</math>, инволютивность отрицания, закон снятия двойного отрицания
- <math>x\lor\bar x=1</math>
- <math>\ x\lor1=1</math>
- <math>\ x\lor x=x</math>
- <math>\ x\lor0=x</math>
- <math>\ x\land\bar x=0</math>
- <math>\ x\land x=x</math>
- <math>\ x\land0=0</math>
- <math>\ x\land1=x</math>
Логические операции
Простейший и наиболее широко применяемый пример такой алгебраической системы строится с использованием множества B, состоящего всего из двух элементов:
- B = { Ложь, Истина }
Как правило, в математических выражениях Ложь отождествляется с логическим нулём, а Истина — с логической единицей, а операции отрицания (НЕ), конъюнкции (И) и дизъюнкции (ИЛИ) определяются в привычном нам понимании. Легко показать, что на данном множестве B можно задать четыре унарные и шестнадцать бинарных отношений и все они могут быть получены через суперпозицию трёх выбранных операций.
Опираясь на этот математический инструментарий, логика высказываний изучает высказывания и предикаты. Также вводятся дополнительные операции, такие как эквиваленция <math>\leftrightarrow</math> («тогда и только тогда, когда»), импликация <math>\rightarrow</math> («следовательно»), сложение по модулю два <math>\oplus</math> («исключающее или»), штрих Шеффера <math>\mid</math>, стрелка Пирса <math>\downarrow</math> и другие.
Логика высказываний послужила основным математическим инструментом при создании компьютеров. Она легко преобразуется в битовую логику: истинность высказывания обозначается одним битом (0 — ЛОЖЬ, 1 — ИСТИНА); тогда операция <math>\neg</math> приобретает смысл вычитания из единицы; <math>\lor</math> — немодульного сложения; & — умножения; <math>\leftrightarrow</math> — равенства; <math>\oplus</math> — в буквальном смысле сложения по модулю 2 (исключающее Или — XOR); <math>\mid</math> — непревосходства суммы над 1 (то есть A <math>\mid</math> B = (A + B) <= 1).
Впоследствии булева алгебра была обобщена от логики высказываний путём введения характерных для логики высказываний аксиом. Это позволило рассматривать, например, логику кубитов, тройственную логику (когда есть три варианта истинности высказывания: «истина», «ложь» и «не определено»), комплексную логику и др.
Свойства логических операций
- Коммутативность: <math>x\circ y = y\circ x ,\circ\in \{ \land, \lor, \oplus, \sim, \mid, \downarrow \}</math>.
- Идемпотентность: <math>x\circ x=x, \circ\in \{\land, \lor \}</math>.
- Ассоциативность: <math>(x\circ y)\circ z = x\circ(y\circ z), \circ\in \{\land, \lor, \oplus, \sim \}</math>.
- Дистрибутивность конъюнкций и дизъюнкции относительно дизъюнкции, конъюнкции и суммы по модулю два соответственно:
- <math>x\land (y\lor z) = (x\land y)\lor (x\land z)</math>,
- <math>x\lor (y\land z) = (x\lor y)\land (x\lor z)</math>,
- <math>x\land (y\oplus z) = (x\land y)\oplus (x\land z)</math>.
- Законы де Мо́ргана:
- <math>\overline{x\land y} = \bar x \lor \bar y</math>,
- <math>\overline{x\lor y} = \bar x\land \bar y</math>.
- Законы поглощения:
- <math>x\land (x\lor y) = x</math>,
- <math>x\lor (x\land y) = x</math>.
- Другие (1):
- <math>x\land \bar x = x\land 0 = x\oplus x = 0</math>.
- <math>x\lor \bar x = x\lor 1 = x\sim x = x\rightarrow x = 1</math>.
- <math>x\lor x = x\land x = x\land 1 = x\lor 0 = x\oplus 0 = x</math>.
- <math>x\oplus 1 = x\rightarrow 0 = x\sim 0 = x\mid x = x\downarrow x = \bar x</math>.
- <math>\bar{\bar x} = x</math>, инволютивность отрицания, закон снятия двойного отрицания.
- Другие (2):
- <math>x\oplus y = x\land \bar y \lor \bar x\land y = (x\lor y)\land (\bar x\lor \bar y)</math>.
- <math>x\sim y = \overline{x\oplus y} = 1\oplus x\oplus y = x\land y\lor \bar x \land \bar y = (x\lor \bar y)\land (\bar x\lor y)</math>.
- <math>x\rightarrow y = \bar x \lor y = x\land y\oplus x\oplus 1</math>.
- <math>x \lor y = x \oplus y \oplus x\land y</math>.
- Другие (3) (Дополнение законов де Мо́ргана):
- <math>x\mid y = \overline {x\land y} = \bar x \lor \bar y</math>.
- <math>x\downarrow y = \overline {x\lor y}= \bar x\land \bar y</math>.
Существуют методы упрощения логической функции: например, Карта Карно, метод Куайна - Мак-Класки
История
Своим существованием наука «алгебра логики» обязана английскому математику Джорджу Булю, который исследовал логику высказываний. Первый в России курс по алгебре логики был прочитан П. С. Порецким в Казанском государственном университете.
См. также
Напишите отзыв о статье "Алгебра логики"
Примечания
- ↑ Алгебра логики // Большая советская энциклопедия : [в 30 т.] / гл. ред. А. М. Прохоров. — 3-е изд. — М. : Советская энциклопедия, 1969—1978.</span>
</ol>
<imagemap>: неверное или отсутствующее изображение |
Для улучшения этой статьи желательно?:
|
| ||||||||||||||
Отрывок, характеризующий Алгебра логики
«Пуф пуф» – поднимались два дыма, толкаясь и сливаясь; и «бум бум» – подтверждали звуки то, что видел глаз.Пьер оглядывался на первый дым, который он оставил округлым плотным мячиком, и уже на месте его были шары дыма, тянущегося в сторону, и пуф… (с остановкой) пуф пуф – зарождались еще три, еще четыре, и на каждый, с теми же расстановками, бум… бум бум бум – отвечали красивые, твердые, верные звуки. Казалось то, что дымы эти бежали, то, что они стояли, и мимо них бежали леса, поля и блестящие штыки. С левой стороны, по полям и кустам, беспрестанно зарождались эти большие дымы с своими торжественными отголосками, и ближе еще, по низам и лесам, вспыхивали маленькие, не успевавшие округляться дымки ружей и точно так же давали свои маленькие отголоски. Трах та та тах – трещали ружья хотя и часто, но неправильно и бедно в сравнении с орудийными выстрелами.
Пьеру захотелось быть там, где были эти дымы, эти блестящие штыки и пушки, это движение, эти звуки. Он оглянулся на Кутузова и на его свиту, чтобы сверить свое впечатление с другими. Все точно так же, как и он, и, как ему казалось, с тем же чувством смотрели вперед, на поле сражения. На всех лицах светилась теперь та скрытая теплота (chaleur latente) чувства, которое Пьер замечал вчера и которое он понял совершенно после своего разговора с князем Андреем.
– Поезжай, голубчик, поезжай, Христос с тобой, – говорил Кутузов, не спуская глаз с поля сражения, генералу, стоявшему подле него.
Выслушав приказание, генерал этот прошел мимо Пьера, к сходу с кургана.
– К переправе! – холодно и строго сказал генерал в ответ на вопрос одного из штабных, куда он едет. «И я, и я», – подумал Пьер и пошел по направлению за генералом.
Генерал садился на лошадь, которую подал ему казак. Пьер подошел к своему берейтору, державшему лошадей. Спросив, которая посмирнее, Пьер взлез на лошадь, схватился за гриву, прижал каблуки вывернутых ног к животу лошади и, чувствуя, что очки его спадают и что он не в силах отвести рук от гривы и поводьев, поскакал за генералом, возбуждая улыбки штабных, с кургана смотревших на него.
Генерал, за которым скакал Пьер, спустившись под гору, круто повернул влево, и Пьер, потеряв его из вида, вскакал в ряды пехотных солдат, шедших впереди его. Он пытался выехать из них то вправо, то влево; но везде были солдаты, с одинаково озабоченными лицами, занятыми каким то невидным, но, очевидно, важным делом. Все с одинаково недовольно вопросительным взглядом смотрели на этого толстого человека в белой шляпе, неизвестно для чего топчущего их своею лошадью.
– Чего ездит посерёд батальона! – крикнул на него один. Другой толконул прикладом его лошадь, и Пьер, прижавшись к луке и едва удерживая шарахнувшуюся лошадь, выскакал вперед солдат, где было просторнее.
Впереди его был мост, а у моста, стреляя, стояли другие солдаты. Пьер подъехал к ним. Сам того не зная, Пьер заехал к мосту через Колочу, который был между Горками и Бородиным и который в первом действии сражения (заняв Бородино) атаковали французы. Пьер видел, что впереди его был мост и что с обеих сторон моста и на лугу, в тех рядах лежащего сена, которые он заметил вчера, в дыму что то делали солдаты; но, несмотря на неумолкающую стрельбу, происходившую в этом месте, он никак не думал, что тут то и было поле сражения. Он не слыхал звуков пуль, визжавших со всех сторон, и снарядов, перелетавших через него, не видал неприятеля, бывшего на той стороне реки, и долго не видал убитых и раненых, хотя многие падали недалеко от него. С улыбкой, не сходившей с его лица, он оглядывался вокруг себя.
– Что ездит этот перед линией? – опять крикнул на него кто то.
– Влево, вправо возьми, – кричали ему. Пьер взял вправо и неожиданно съехался с знакомым ему адъютантом генерала Раевского. Адъютант этот сердито взглянул на Пьера, очевидно, сбираясь тоже крикнуть на него, но, узнав его, кивнул ему головой.
– Вы как тут? – проговорил он и поскакал дальше.
Пьер, чувствуя себя не на своем месте и без дела, боясь опять помешать кому нибудь, поскакал за адъютантом.
– Это здесь, что же? Можно мне с вами? – спрашивал он.
– Сейчас, сейчас, – отвечал адъютант и, подскакав к толстому полковнику, стоявшему на лугу, что то передал ему и тогда уже обратился к Пьеру.
– Вы зачем сюда попали, граф? – сказал он ему с улыбкой. – Все любопытствуете?
– Да, да, – сказал Пьер. Но адъютант, повернув лошадь, ехал дальше.
– Здесь то слава богу, – сказал адъютант, – но на левом фланге у Багратиона ужасная жарня идет.
– Неужели? – спросил Пьер. – Это где же?
– Да вот поедемте со мной на курган, от нас видно. А у нас на батарее еще сносно, – сказал адъютант. – Что ж, едете?
– Да, я с вами, – сказал Пьер, глядя вокруг себя и отыскивая глазами своего берейтора. Тут только в первый раз Пьер увидал раненых, бредущих пешком и несомых на носилках. На том самом лужке с пахучими рядами сена, по которому он проезжал вчера, поперек рядов, неловко подвернув голову, неподвижно лежал один солдат с свалившимся кивером. – А этого отчего не подняли? – начал было Пьер; но, увидав строгое лицо адъютанта, оглянувшегося в ту же сторону, он замолчал.
Пьер не нашел своего берейтора и вместе с адъютантом низом поехал по лощине к кургану Раевского. Лошадь Пьера отставала от адъютанта и равномерно встряхивала его.
