Буль алгебраһы

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

Буль алгебраһы тип ике бинар операцияһы $\land$ (конъюнкция аналогы), $\lor$ (дизъюнкция аналогы), бер унар операцияһы $\lnot$ (инҡар итеү аналогы) һәм ике айырылып торған элементтары: 0 (йәки Ялған) һәм 1 (йәки дөрөҫлөк) булған буш булмаған A күмәклеге атала, бында A күмәклегенең теләһә ниндәй a, b һәм c элементтары өсөн түбәндәге аксиомалар дөрөҫ:

$a\lor (b\lor c)=(a\lor b)\lor c$	$a\land (b\land c)=(a\land b)\land c$	ассоциативлыҡ
$a\lor b=b\lor a$	$a\land b=b\land a$	коммутативлыҡ
$a\lor (a\land b)=a$	$a\land (a\lor b)=a$	йотолоу закондары
$a\lor (b\land c)=(a\lor b)\land (a\lor c)$	$a\land (b\lor c)=(a\land b)\lor (a\land c)$	дистрибутивлыҡ
$a\lor \lnot a=1$	$a\land \lnot a=0$	өҫтәлмәлек

· + ¯ нотацияһында  

${\begin{aligned}&a+(b+c)=(a+b)+c&a(bc)=(ab)c\\&a+b=b+a&ab=ba\\&a+ab=a&a(a+b)=a\\&a+bc=(a+b)(a+c)&a(b+c)=ab+ac\\&a+{\bar {a}}=1&a{\bar {a}}=0\end{aligned}}$

Тәүге өс аксиома (A, $\land$, $\lor$) рәшәткә булыуын аңлата. Шулай итеп, Буль алгебраһына, һуңғы ике аксиома үтәлгән дистрибутив рәшәткә тигән билдәләмә бирергә мөмкин. Һуңғыһынан алдағы аксиоманан башҡа бөтә аксиомалар үтәлгән структура псевдобуль алгебра тип атала. Джордж Буль хөрмәтенә аталған.

Ҡайһы бер үҙсәнлектәре

Аксиомаларҙан күренеүенсә, иң бәләкәй элемент булып 0 тора, иң ҙур элемент 1, ә теләһә ниндәй a элементының өҫтәмәһе ¬a бер мәғәнәле билдәләнә. A күмәклегенән бөтә a һәм b өсөн түбәндәге тигеҙлектәр дөрөҫ:

$a\lor a=a$	$a\land a=a$
$a\lor 0=a$	$a\land 1=a$
$a\lor 1=1$	$a\land 0=0$
$\lnot 0=1$	$\lnot 1=0$	0-дең өҫтәлмәһе 1 һәм киреһенсә
$\lnot (a\lor b)=\lnot a\land \lnot b$	$\lnot (a\land b)=\lnot a\lor \lnot b$	де Морган закондары
$\lnot \lnot a=a$.		инҡар итеүҙең инволютивлығы, Икеләтә инҡар итеү законын бөтөрөү.

Төп тождестволар

Был бүлектә юғарыла тасуирланған үҙсәнлектәр һәм аксиомалар, тағы ла бер нисәү өҫтәлеп, ҡабатлана.

Юғарыла тасуирланған үҙсәнлектәр һәм аксиомаларҙың йыйылма таблицаһы:

$a\lor b=b\lor a$	$a\land b=b\land a$	1 коммутативлыҡ, урын алмаштырыу үҙсәнлеге
$a\lor (b\lor c)=(a\lor b)\lor c$	$a\land (b\land c)=(a\land b)\land c$	2 ассоциативлыҡ, төркөмләү үҙсәнлеге
3.1 дизъюнкцияға ҡарата конъюнкция $a\lor (b\land c)=(a\lor b)\land (a\lor c)$	3.2 конъюнкцияға ҡарата дизъюнкция $a\land (b\lor c)=(a\land b)\lor (a\land c)$	3 дистрибутивлыҡ, таратыу үҙсәнлеге
$a\lor \lnot a=1$	$a\land \lnot a=0$	4 комплементлыҡ, өҫтәмәлек (инҡар итеү үҙсәнлектәре)
$\lnot (a\lor b)=\lnot a\land \lnot b$	$\lnot (a\land b)=\lnot a\lor \lnot b$	5 де Морган закондары
$a\lor (a\land b)=a$	$a\land (a\lor b)=a$	6 йотоу закондары
$a\lor (\lnot a\land b)=a\lor b$	$a\land (\lnot a\lor b)=a\land b$	7 Блейк-Порецкий законы
$a\lor a=a$	$a\land a=a$	8 Идемпотентлыҡ
$\lnot \lnot a=a$		9 инҡар итеүҙең инволютивлығы, Икеләтә инҡар итеү законын бөтөрөү
$a\lor 0=a$	$a\land 1=a$	10 константалар үҙсәнлектәре
$a\lor 1=1$	$a\land 0=0$
0-дең өҫтәмәһе 1 $\lnot 0=1$	1-ҙең өҫтәмәһе 0 $\lnot 1=0$
$(a\lor b)\land (\lnot a\lor b)=b$	$(a\land b)\lor (\lnot a\land b)=b$	11 Көйләнеү

Шулай уҡ ҡарағыҙ: Логика алгебраһы#Логик операциялар үҙсәнлектәре

Миҫалдары

• Иң ябай тривиаль булмаған Буль алгебраһы бөтәһе ике элементтан тора, 0 һәм 1, ә унда ғәмәлдәр түбәндәге таблица менән бирелә:

∧ 0 1 0 0 0 1 0 1

∨ 0 1 0 0 1 1 1 1

a 0 1 ¬a 1 0

Был Буль алгебраһы йышыраҡ логикала ҡулланыла, сөнки ул классик фекер иҫәпләмәһенең теүәл моделы булып тора. Был осраҡта 0 Ялған, 1 — дөрөҫлөк тип атала. Буль операциялары һәм үҙгәреүсәндәр ингән аңлатмаларҙың фекер формалары булалар.

• Был күмәклектең бөтә аҫкүмәклектәре күмәклеге S ∨ := ∪ (берекмә), ∧ := ∩ (киҫелеш) һәм өҫтәлмәлек унар операцияларына ҡарата Буль алгебраһын төҙөй. Бында иң бәләкәй элемент — буш күмәклек, ә иң ҙуры — бөтә S.
• Бирелгән $m$ квадраттарҙан азат натураль һанының $U$ бөтә натураль бүлеүселәре күмәклеген ҡарайыҡ. $U$ күмәклегендә ике бинар операция бирәйек: иң ҙур уртаҡ бүлеүсене табыу (конъюнкция аналогы) һәм иң бәләкәй уртаҡ бүленеүсене табыу (дизъюнкция аналогы); $d$ бүлеүсеһенә $m/d$ бүлеүсеһен ярашлы ҡуйыусы бер урынлы операция инҡар итеү ролен уйнай. Килеп сыҡҡан структура Буль алгебраһы була; унда Буль нуленең һәм берәмегенең аналогтары булып ярашлы рәүештә 1 һәм $m$ һандары тора. Юғарыла килтерелгән Буль алгебраһының дөйөм аксиомаларын һәм үҙсәнлектәрен $U$ күмәклеге өсөн ҡулланыу күп кенә файҙалы һәм бик үк күренеп тормаған теоретик-һанлы тождестволар бирә.
• Ниндәй ҙә булһа фекер иҫәпләмәһенең Линденбаум — Тарский алгебраһы (был иҫәпләмәлә ярашлы операциялар менән тиң көслөлөккә ҡарата бөтә раҫлауҙарҙың факторкүмәклеге) Буль алгебраһы була. Был осраҡта иҫәпләмәләр формулаларының дөрөҫлөк баһаһы булып Линденбаум — Тарский алгебраһының ике элементлы Буль алгебраһына гомоморфизмы тора.
• Әгәр R — ирекле ҡулса булһа, ул саҡта унда үҙәк идемпотенттар күмәклеген ошолай билдәләргә мөмкин:
  A = { e ∈ R : e² = e, ex = xe, ∀x ∈ R },
  ул саҡта A күмәклеге e ∨ f := e + f − ef һәм e ∧ f := ef операциялары менән Буль алгебраһы була.

Ҡапма-ҡаршылыҡ ҡағиҙәһе

Буль алгебраларында ҡапма-ҡаршылыҡлы раҫлауҙар бар, улар йә бер үк ваҡытта дөрөҫ, йәки бер үк ваҡытта дөрөҫ түгел. Атап әйткәндә, әгәр ниндәйҙер Буль алгебраһында дөрөҫ булған формулала, бөтә конъюнкцияларҙы дизъюнкцияларға, 0-де 1-гә, ≤ -ҙе >-ға һәм киреһенсә йәки <-ҙе ≥ -гә һәм киреһенсә алмаштырғанда, шулай уҡ был Буль алгебраһында дөрөҫ булған формула килеп сыға. Был аксиомаларҙың бындай алмаштырыуҙарға ҡарата симметриялығынан килеп сыға.

Буль алгебраларының вәкилдәре

Теләһә ниндәй сикле Буль алгебра ниндәйҙер күмәклектең бөтә аҫкүмәклектәре Буль алгебраһына изоморфлы икәнен иҫбат итергә мөмкин. Ошонан, теләһә ниндәй сикле Буль алгебрала элементтар һаны икенең дәрәжәһе булыуы килеп сыға.

Стоун теоремаһы, теләһә ниндәй сикле Буль алгебра ниндәйҙер компактлы тулыһынса бәйле булмаған Хаусдорф топологик арауығының бөтә асыҡ-йомоҡ күмәклектәренең Буль алгебраһына изоморфлы.

Аксиомалаштырыу

1933 йылда америка математигы Хантингтон Буль алгебралары өсөн түбәндәге аксиомалаштырыуҙы тәҡдим итә:

1. Коммутативлыҡ аксиомаһы: x + y = y + x.
2. Ассоциативлыҡ аксиомаһы: (x + y) + z = x + (y + z).
3. Хантингтон тигеҙләмәһе: n(n(x) + y) + n(n(x) + n(y)) = x.

Бында Хантингтондың тамғалауҙары ҡулланылған: + дизъюнкцияны аңлата, n — инҡар итеүҙе.

Герберт Роббинс шундай һорау ҡуя: түбәндәгесә яҙылған һуңғы аксиоманы ҡыҫҡартып буламы, йәғни түбәндә яҙылған аксиомалар менән билдәләнгән структура Буль алгебраһы буламы?

Роббинс алгебраһын аксиомалаштырыу:

1. Коммутативлыҡ аксиомаһы: x + y = y + x.
2. Ассоциативлыҡ аксиомаһы: (x + y) + z = x + (y + z).
3. Роббинс тигеҙләмәһе: n(n(x + y) + n(x + n(y))) = x.

Был һорау 1930-сы йылдарҙан алып асыҡ ҡала һәм Тарскийҙың һәм уның уҡыусыларының яратҡан һорауы була.

1996 йылда Вильям МакКьюн, уға тиклем алынған ҡайһы бер һөҙөмтәләрҙе ҡулланып, был һорауға ыңғай яуап бирә. Шулай итеп, теләһә ниндәй Роббинс алгебраһы Буль алгебраһы була.

Шулай уҡ ҡарағыҙ

• Логика алгебраһы
• Буль функцияһы
• Битовые операции

Әҙәбиәт

• Владимиров Д. А. Булевы алгебры. — М.: «Наука», 1969. — 320 с.
• Кузнецов О. П. Дискретная математика для инженера. — СПб.: Лань, 2007. — 394 с.
• Иванов Б. Н. Дискретная математика. Алгоритмы и программы. Расширенный курс. — М.: «Известия», 2011. — 512 с.(недоступная ссылка)
• Гуров С.И. Булевы алгебры, упорядоченные множества, решетки: Определения, свойства, примеры. — М.: Либроком, 2013. — 352 с.