Логика алгебраһы

булева алгебра менән бутамаҫҡа.

Логика алгебраһы
Кем хөрмәтенә аталған	Джордж Буль[d]
Өйрәнеү объекты	Буль алгебраһы һәм булева функция[d]
Логика алгебраһы Викимилектә

Логика алгебраһы (әйтеүҙәр алгебраһы) —математик логиканың әйтеүҙәр өҫтөндә логик операциялар өйрәнелгән бүлеге. Йышыраҡ әйтеүҙәр тик ысын йәки ялған булырға мөмкин тип фаразлана, йәғни, мәҫәлән, өсәрле логиканан айырмалы рәүештә, бинар йәки икеле тип аталған логика ҡулланыла.

Инглиз математигы һәм логиғы, үҙенең логик тәғлимәтенең нигеҙенә алгебра һәм логика араһындағы оҡшашлыҡты һалған Дж. Буль логика алгебраһына нигеҙ һалыусы булып тора. Логика алгебраһы математик логиканың, күләме яғынан ҡаралған төшөнсәләр менән операцияларҙа логик һығымталарға алгебраик символика ҡулланыла башлаған беренсе системаһы була.

Буль үҙенең алдына логик мәсьәләләрҙе алгебрала ҡулланылған ысулдар ярҙамында сығарыу бурысын ҡуя. Теләһә ниндәй фекерҙе ул символдар менән, алгебра закондарына оҡшаш логик закондар ғәмәлдә булған тигеҙләмә күренешендә күрһәтергә тырыша.

Аҙаҡ Джевонс Уильям Стенли, Шрёдер Эрнст, Порецкий Платон Сергеевич, Пирс Чарльз Сандерс, әйтеүҙәр иҫәпләмәһе теорияһын эшләүсе Фреге Готлоб, логик әйтеүҙәр менән операцияларҙа формалләштереү ысулын ҡулланыу өлкәһендә уңышҡа өлгәшкән Гильберт Давид логика алгебраһын камиллаштырыу өҫтөндә эшләйҙәр.

Уайтхед Альфред Норт менән бергә математик логикаға хәҙерге күренеш биргән Рассел Бертран; кластар иҫәпләмәһен артабан үҫтергән һәм логик ҡушыу операцияһы теорияһын байтаҡ ябайлаштырыуға өлгәшкән Жегалкин Иван Иванович; логика алгебраһы фәнен төшөнсәләр менән күләм операцияларын өйрәнеү сиктәренән алыҫ сығарған Гливенко Валерий Иванович үҙ өлөштәрен индерәләр.

Логика алгебраһы хәҙерге тасуирланышында әйтеүҙәр, йәғни бер генә сифат — ысынлыҡ ҡиммәте (ысын, ялған) менән характерланыусы һөйләмдәр менән ғәмәлдәрҙе тикшереү менән шөғөлләнә.

Классик логика алгебраһында әйтеү бер үк ваҡытта ике ысынлыҡ ҡиммәтенең тик бер ҡиммәтенә генә эйә: «ысын» йәки «ялған» ғына була ала.

Логика алгебраһы шулай уҡ әйтеү — функцияға ингән үҙгәреүсәнгә ниндәй ҡиммәт бирелеүгә бәйле «ысын» йәки «ялған» ҡиммәттәре ҡабул иткән әйтеү — функцияларҙы тикшерә.

Билдәләмә

Әйтеүҙәр логика алгебраһы таянып эш иткән база элементтар булып торалар.

Әйтеүҙәр {B, $\lnot$, $\land$ күмәклегендә төҙөләләр, $\lor$, 0, 1}, бында B — элементтары өҫтөндә өс операция:

$\lnot$ кире ҡағыу (унар операция),

$\land$ конъюнкция (бинар операция),

$\lor$ дизъюнкция (бинар операция), билдәләнгән, буш булмаған күмәклек, ә логик ноль 0 һәм логик берәмек 1 — константалар.

Шулай уҡ ошондай атамалар ҡулланыла:

• Дизъю́нкт — бер йәки күберәк литералдарҙың дизъюнкцияһы булып торған пропозициональ формула, (мәҫәлән $x_{1}\lor \neg x_{2}\lor x_{4}$).
• Конъюнкт — бер йәки күберәк литералдарҙың конъюнкцияһы булып торған пропозициональ формула, (мәҫәлән $x_{1}\land \neg x_{2}\land x_{4}$).

Кире ҡағыу унар операцияһы формулалар тексында операнд алдындағы ($\lnot x$) тамғаһы йәки операнд өҫтөндәге һыҙыҡ (${\bar {x}}$ (был ыҡсымыраҡ, ләкин дөйөм алғанда ныҡ күренеп тормай) күренешендә яҙыла.

Аксиомалар

1. ${\bar {\bar {x}}}=x$, кире ҡағыуҙың инволютивлығы, икеләтә кире ҡағыуҙы ғәмәлдән сығарыу законы
2. $x\lor {\bar {x}}=1$
3. $\ x\lor 1=1$
4. $\ x\lor x=x$
5. $\ x\lor 0=x$
6. $\ x\land {\bar {x}}=0$
7. $\ x\land x=x$
8. $\ x\land 0=0$
9. $\ x\land 1=x$

Логик операциялар

Бындай алгебраик системаның иң ябай һәм киң ҡулланылған миҫалы бары тик ике элементтан торған B күмәклеген ҡулланып төҙөлә:

B = { Ялған, Ысын }

Ҡағиҙә булараҡ, математик аңлатмаларҙа Ялған логик нуль, ә Ысын —логик берәмек менән тиңләштерелә, ә кире ҡағыу операцияһы (түгел), конъюнкция (һәм) һәм дизъюнкция беҙгә ғәҙәти булған мәғәнәлә билдәләнәләр. Бирелгән B күмәклегендә дүрт унар һәм ун алты бинар бәйләнеш бирергә мөмкин икәнен еңел күрһәтеп була, һәм улар бөтәһе лә өс һайланған операциялар суперпозицияһы (операциялар композицияһы) аша алынырға мөмкин.

Был математик инструментарийға таянып, әйтеүҙәр логикаһы әйтеүҙәрҙе һәм предикаттарҙы өйрәнә. Шулай уҡ эквиваленция $\leftrightarrow$ («шул саҡта һәм шул саҡта ғына, әгәр»), импликация $\rightarrow$ ("шуға күрә "), ике модуле буйынса ҡушыу $\oplus$ («йәки тигәнде юҡҡа сығарыу»), Шеффер штрихы $\mid$, Пирс уғы $\downarrow$ һәм башҡалар кеүек өҫтәлмә операциялар индерелә.

Әйтеүҙәр логикаһы компьютерҙар яһағанда төп математик инструмент булып хеҙмәт итә. Ул бик еңел битлы логикаға үҙгәртелә: әйтеүҙең ысынлығы бер бит (0 — ЯЛҒАН, 1 — ЫСЫН) менән тамғалана; ул саҡта $\neg$ операцияһы берҙән алыу; $\lor$ —модулле булмаған ҡушыу; & — ҡабатлау; $\leftrightarrow$ — тигеҙлек; $\oplus$ — тура мәғәнәһендә ике модуле буйынса ҡушыу (Йәки тигәнде юҡҡа сығарыу— XOR); $\mid$ — сумманың 1-ҙән артмауы (йәғни A $\mid$ B = (A + B) <= 1) мәғәнәһен ала.

Аҙаҡ Буль алгебраһы әйтеүҙәр логикаһынан, әйтеүҙәр логикаһы өсөн характерлы булған аксиомалар индереү юлы менән, дөйөмләштерелә. Был, мәҫәлән, кубиттар логикаһын, өслөклө логиканы (әйтеүҙең ысынлығының өс варианты: «ысын», «ялған» һәм «билдәһеҙ» булған), комплекслы логиканы һәм башҡаларҙы ҡарарға мөмкинлек бирә.

Логик операциялар үҙсәнлектәре

1. Коммутативлыҡ: $x\circ y=y\circ x,\circ \in \{\land ,\lor ,\oplus ,\sim ,\mid ,\downarrow \}$.
2. Идемпотентлыҡ: $x\circ x=x,\circ \in \{\land ,\lor \}$.
3. Ассоциативлыҡ: $(x\circ y)\circ z=x\circ (y\circ z),\circ \in \{\land ,\lor ,\oplus ,\sim \}$.
4. Конъюнкцияның һәм дизъюнкцияның дизъюнкцияға, конъюнкцияға һәм ике модуле буйынса ҡушыуға ҡарата ярашлы рәүештә дистрибутивлығы:
   • $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\oplus z)=(x\land y)\oplus (x\land z)$.
5. де Морган закондары:
   • ${\overline {x\land y}}={\bar {x}}\lor {\bar {y}}$,
   • ${\overline {x\lor y}}={\bar {x}}\land {\bar {y}}$.
6. Йотолоу закондары:
   • $x\land (x\lor y)=x$,
   • $x\lor (x\land y)=x$.
7. Башҡалар (1):
   • $x\land {\bar {x}}=x\land 0=x\oplus x=0$.
   • $x\lor {\bar {x}}=x\lor 1=x\sim x=x\rightarrow x=1$.
   • $x\lor x=x\land x=x\land 1=x\lor 0=x\oplus 0=x$.
   • $x\oplus 1=x\rightarrow 0=x\sim 0=x\mid x=x\downarrow x={\bar {x}}$.
   • ${\bar {\bar {x}}}=x$, кире ҡағыуҙың инволютивлығы, икеләтә кире ҡағыуҙы ғәмәлдән сығарыу законы.
8. Башҡалар (2):
   • $x\oplus y=x\land {\bar {y}}\lor {\bar {x}}\land y=(x\lor y)\land ({\bar {x}}\lor {\bar {y}})$.
   • $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)$.
   • $x\rightarrow y={\bar {x}}\lor y=x\land y\oplus x\oplus 1$.
   • $x\lor y=x\oplus y\oplus x\land y$.
9. Башҡалар (3) (де Мо́рган закондарын тултырыу):
   • $x\mid y={\overline {x\land y}}={\bar {x}}\lor {\bar {y}}$.
   • $x\downarrow y={\overline {x\lor y}}={\bar {x}}\land {\bar {y}}$.

Логик функцияларҙы ябайлаштырыу ысулдары бар: мәҫәлән, Карно картаһы, Куайн - Мак-Класки ысулы.

Тарихы

«Логика алгебраһы» фәне үҙенең булыуы менән инглиз математигы Джордж Булға бурыслы, ул әйтеүҙәр логикаһын тикшерә. Рәсәйҙә логика алгебраһы буйынса беренсе курс Порецкий Платон Сергеевич] тарафынан Ҡаҙан дәүләт университетында уҡыла.