Алгарытм пабудовы табліц праўдзівасці лагічных выразаў

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

булева алгебра

Алгебра логікі грунтуецца на простых лагічных выразах, якія звязваюцца паміж сабой аперацыямі, ствараючы пры гэтым складаныя выразы. Варта адзначыць, што булева алгебра змяшчае дзве бінарныя аперацыі: множанне і складанне (конъюнкция і дизъюнкция адпаведна); адну Унарный - інверсія. Усе простыя выразы (элементы складанага лагічнага выразы) прымаюць адно з двух значэнняў: «1» або «0», «ісціна» або «хлусня», «+» або «-» адпаведна.

Алгебра логікі грунтуецца на некалькіх даволі простых аксіомах:

• асацыятыўнасці;
• коммутативности;
• паглынання;
• дыстрыбутыўнага;
• дадатковасці.

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

Правілы складання табліцы

Пабудова табліц праўдзівасці лагічных выразаў дапамагае вырашыць шматлікія лагічныя задачы і знайсці рашэнне складаных грувасткіх прыкладаў. Варта адзначыць, што ёсць некаторыя правілы іх складання.

Для таго каб правільна скласці лагічную табліцу, неабходна для пачатку вызначыцца з колькасцю радкоў. Як гэта зрабіць? Палічыце колькасць зменных, якія ўваходзяць у склад складанага выказвання, і скарыстайцеся простай формулай: А = 2 у ступені n. А - гэта колькасць радкоў у якая складаецца табліцы праўдзівасці, n - гэта колькасць зменных, якія ўваходзяць у складанае лагічны выраз.

Прыклад: складанае выраз складаецца з трох розных зменных (А, В і С), значыць, двойку неабходна ўзвесці ў трэцюю ступень. У якая складаецца табліцы праўдзівасці ў нас будзе восем радкоў. Дадайце адзін радок для загалоўкі слупкоў.

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

Наступным этапам мы падлічваем колькасць аперацый. Атрыманы лік - гэтая колькасць слупкоў у нашай табліцы. Абавязкова дадайце яшчэ такая колькасць слупкоў, колькі зменных змяшчаецца ў вашым выразе, для запаўнення магчымых камбінацый зменных.

Далей неабходна запоўніць шапку нашай табліцы. Ніжэй вы бачыце прыклад гэтага.

Зараз пераходзіце да запаўнення магчымых камбінацый. Для двух зменных яны будуць наступныя: 00, 01, 10, 11. Для трох зменных: 000, 001, 010, 011, 100, 101, 110, 111.

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

прыклад

Зараз мы разгледзім прыклад пабудовы табліцы праўдзівасці лагічнага выразы: інверсія А + У * А.

1. Падлік зменных: 2. Колькасць радкоў: 4 + 1 = 5.
2. Парадак выканання дзеянняў: першая інверсія, другая конъюнкция, трэцяя дизъюнкция.
3. Колькасць слупкоў: 3 + 2 = 5.
4. Прыступаем да напісанні і запаўненні табліцы.

Як правіла, заданне гучыць такім чынам: «колькі камбінацый задавальняе ўмове F = 0» або «у якіх спалучэннях F = 1». На першы пытанне адказ - 1, на другі - 00, 01, 11.

Уважліва чытайце заданне, якое вам даецца. Вы можаце правільна вырашыць задачу, але памыліцца ў напісанні адказу. Яшчэ раз звяртаем вашу ўвагу на парадак выканання дзеянняў:

• адмаўленне;
• множанне;
• складанне.

задача

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

Даны чатыры значэння ліку А: 1) 7, 2) 6, 3) 5, 4) 4. Для якога з іх выказванне «інверсія (А менш 6) + (А менш 5)» з'яўляецца ілжывым?

Наш першы слупок будзе запоўнены значэннямі 7, 6, 5, 4 абавязкова ў гэтай паслядоўнасці. У наступным слупку мы павінны адказаць на пытанне: "А менш 6?" Трэці слупок запаўняем аналагічна, толькі цяпер адказваем на пытанне: "А менш 5?"

Вызначаемся з паслядоўнасцю аперацый. Ўспамінаем, што адмаўленне мае прыярытэт перад дизъюнкцией. Значыць, наступны слупок мы запаўняем значэннямі, якія адпавядаюць умове ня (А менш 6). Чацвёрты будзе адказваць на галоўнае пытанне нашай задачы. Ніжэй вы бачыце прыклад запаўнення табліцы.

Звярніце ўвагу на тое, што ў нас маюцца нумары адказаў, ілжывым выраз будзе пры значэнні А = 5, гэта трэці варыянт адказу.