§ 26. Алгебра логікі

Працэсар камп’ютара выконвае арыфметычныя і лагічныя аперацыі над двайковымі кодамі.

Для таго каб мець уяўленне пра будову камп’ютара, неабходна пазнаёміцца не толькі з арыфметычнымі, але і з асноўнымі лагічнымі элементамі, якія ляжаць у аснове яго пабудовы.

Для разумення прынцыпу работы такіх элементаў разгледзім асноўныя паняцці алгебры логікі.

Аналогію паміж алгебрай і логікай паклаў у аснову свайго лагічнага вучэння заснавальнік алгебры логікі англійскі матэматык і логік Д. Буль (1815—1864).

Любое выказванне Буль запісваў з дапамогай сімвалаў распрацаванай ім мовы і атрымліваў «ураўненні», праўдзівасць ці непраўдзівасць якіх можна было даказаць, зыходзячы з пэўных лагічных законаў.

Сучасная алгебра логікі з’яўляецца раздзелам матэматычнай логікі і вывучае лагічныя аперацыі над выказваннямі з пункту гледжання іх праўдзівага значэння.

Праўдзівасць ці непраўдзівасць выказванняў залежыць ад праўдзівасці і непраўдзівасці зыходных (простых) выказванняў і сэнсу лагічных аперацый над выказваннямі (прыклад 26.1). Такім чынам, вызначэнне праўдзівасці некаторага лагічнага выразу — гэта вызначэнне значэння некаторай лагічнай функцыі.

Спосабы задання лагічнай функцыі:

1) слоўнае апісанне;

2) табліца праўдзівасці;

3) формула, запісаная з дапамогай літар, знакаў лагічных аперацый і дужак;

4)  кімбінацыйная схема, складзеная з лагічных элементаў;

5)  каардынатны спосаб (карта Карно);

6)  дыяграма Вена (Эйлера).

(Разгледзьце прыклад 26.2.)

Вобласці ўжывання алгебры логікі:

1) у якасці сродку алгарытмічнага апісання ў мовах праграміравання для вызначэння лагічных умоў;

2) для фарміравання лагічных выказванняў у матэматычнай логіцы, лінгвістыцы, тэорыі штучнага інтэлекту;

3) у распрацоўцы і апісанні дыскрэтных тэхнічных сістэм;
пры аналізе і сінтэзе лагічных устройстваў.

Разгледзім асноўныя лагічныя аперацыі — варыянты абазначэння (прыклад 26.3), табліцы праўдзівасці і лагічныя элементы для кожнай з лагічных аперацый (прыклады 26.4 — 26.9).

Лагічнае адмаўленне, або інверсія (лац. inversion — пераварочванне), — лагічная аперацыя, якая змяняе значэнне зыходнага выказвання на супрацьлеглае.

Інверсія — унарная лагічная аперацыя, г. зн. выконваецца адносна аднаго выказвання (прыклад 26.4).

Лагічныя аперацыі, якія выконваюцца адносна як мінімум двух выказванняў, называюцца бінарнымі. Разгледзім асноўныя з іх.

Лагічнае множанне, або кан’юнкцыя (лац. conjunctio — злучэнне), — аперацыя, якая злучае два ці больш выказванняў пры дапамозе лагічнай звязкі І. Вынік аперацыі можа быць праўдзівым толькі ў тым выпадку, калі адначасова праўдзівыя зыходныя выказванні (прыклад 26.5).

Лагічнае складанне, або дыз’юнкцыя (лац. disjunction — раздзяленне), — аперацыя, якая злучае два ці больш выказванняў пры дапамозе лагічнай звязкі АБО. Вынік аперацыі будзе праўдзівым, калі праўдзівае хоць бы адно з зыходных выказванняў (прыклад 26.6).

Дыз’юнкцыя строгая (складанне па модулі два) — аперацыя, якая злучае два выказванні (A і B) пры дапамозе лагічнай звязкі АБО, ужытай у выключальным сэнсе, і чытаецца: «Або A, або B». Вынік аперацыі будзе праўдзівым, калі праўдзівае толькі адно з зыходных выказванняў (прыклад 26.7).

Лагічная паслядоўнасць, або імплікацыя (лац. implisito — цесна звязваю), — аперацыя, якая злучае два выказванні (A і B), з якіх першае з’яўляецца ўмовай, а другое — вынікам з гэтай умовы. Чытаецца: "Калі A, то B", "A цягне за сабой B", "З A вынікае B". Вынік аперацыі непраўдзівы толькі тады, калі перадумова ёсць праўда, а вынік — няпраўда (прыклад 26.8).

Раўназначнасць, або эквівалентнасць (лац. aequalis — роўны і valentis — які мае сілу), — аперацыя, якая дазваляе з двух выказванняў (A і B) атрымаць выказванне, якое чытаецца так: «A раўназначна B». Гэта аперацыя можа быць выяўлена звязкамі «тады і толькі тады», «неабходна і дастаткова», «раўнасільна». Аперацыя эквівалентнасці процілеглая строгай дыз’юнкцыі і мае вынік «праўда» тады і толькі тады, калі значэнні пераменных супадаюць (прыклад 26.9).

З дапамогай лагічных пераменных і лагічных аперацый любое састаўное лагічнае выказванне можна фармалізаваць, г. зн. замяніць лагічным выразам. Пры гэтым элементарныя выказванні, якія ўтвараюць састаўное выказванне, могуць быць абсалютна не звязаны па сэнсе (прыклад 26.10). Сэнс выказванняў не ўлічваецца, разглядаецца толькі іх праўдзівасць ці непраўдзівасць.

У лагічных выразах павінен выконвацца наступны парадак выканання аперацый (прыклад 26.11):

1) дзеянні ў дужках;

2) інверсія;

3)  кан’юнкцыя;

4) дыз’юнкцыя;

5) імплікацыя;

6) эквівалентнасць.

Значэнне лагічнага выразу можна вызначыць, пабудаваўшы табліцу праўдзівасці для гэтага выразу. Для пабудовы табліцы праўдзівасці неабходна выканаць наступныя дзеянні (прыклад 26.12):

1) падлічыць колькасць пераменных у выразе (n);

2) падлічыць лік лагічных аперацый у выразе (p);

3) вызначыць паслядоўнасць выканання лагічных аперацый у выразе з улікам дужак і прыярытэтаў;

4) вылічыць колькасць слупкоў у табліцы (n + p);

5) запоўніць шапку табліцы, уключыўшы ў яе пераменныя і аперацыі ў адпаведнасці з вызначанай у п. 3 паслядоўнасцю;

6) вылічыць колькасць радкоў у табліцы (m = 2n);

7) запісаць у табліцы ўсе магчымыя наборы значэнняў пераменных;

8) запоўніць табліцу па слупках, выконваючы лагічныя аперацыі ў адпаведнасці з вызначанай у п. 3 паслядоўнасцю.

Для пераўтварэння і спрашчэння формул у алгебры логікі выконваюцца эквівалентныя пераўтварэнні, якія абапіраюцца на асноўныя лагічныя законы (прыклад 26.13). Некаторыя з гэтых законаў фармулююцца і запісваюцца гэтак жа, як аналагічныя законы ў арыфметыцы і алгебры, іншыя выглядаюць нязвыкла.

Даказана, што для ўяўлення любой лагічнай функцыі дастаткова трох аперацый: кан’юнкцыі, дыз’юнкцыі і адмаўлення. Гэта значыць любую лагічную формулу можна шляхам пераўтварэнняў і спрашчэнняў прывесці да формулы, якая змяшчае толькі гэтыя тры асноўныя лагічныя аперацыі.

Прыклад 26.14. Спрасціць лагічны выраз  і пабудаваць лагічную схему, якая адпавядае выніку.

Выканаем эквівалентныя пераўтварэнні выразу ў адпаведнасці з законамі логікі:

1.  Імплікацыі.
2.  Дэ Моргана.
3.  Інвалюцыі.
4.  Дыстрыбутыўнасці.

1. Што вывучае алгебра логікі?

2. Якімі аб’ектамі аперыруе алгебра логікі?

3. Якія значэнні могуць прымаць аб’екты алгебры логікі?

4. Якімі спосабамі можна адлюстраваць лагічную функцыю?

5. Якая лагічная аперацыя з’яўляецца ўнарнай? Чаму? У чым яе сэнс?

6. У якім выпадку вынікам кан’юнкцыі будзе праўда?

7. У якім выпадку вынікам дыз’юнкцыі будзе няпраўда?

8. У чым розніца паміж дыз’юнкцыяй і строгай дыз’юнкцыяй?

9. Як выконваецца імплікацыя? Прывядзіце прыклады.

10. У якіх выпадках вынікам эквівалентнасці будзе праўда? Прывядзіце прыклады.

11.  У выглядзе якіх лагічных элементаў рэалізаваны лагічныя аперацыі: інверсія, кан’юнкцыя, дыз’юнкцыя, строгая дыз’юнкцыя, імплікацыя, эквівалентнасць?

12. Што такое лагічны выраз? У чым складецца фармалізацыя састаўнога лагічнага выказвання?

13. Па якіх правілах будуецца табліца праўдзівасці для лагічнага выразу?

14. Для чаго ў алгебры логікі выкарыстоўваюцца эквівалентныя пераўтварэнні лагічных формул?

15. Якія законы выкарыстоўваюцца пры эквівалентных пераўтварэннях лагічных формул?

16. Якіх лагічных аперацый дастаткова для выяўлення любой лагічнай функцыі?