Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


јкс≥оми та закони булевоњ алгебри




 

Ѕулева алгебра базуЇтьс€ на де€ких акс≥омах, ≥з €ких вивод€тьс€ основн≥ закони дл€ перетворенн€ вираз≥в, що м≥ст€ть булев≥ зм≥нн≥. ќбірунтуванн€ цих акс≥ом п≥дтверджуЇтьс€ таблиц€ми ≥стинност≥ дл€ роз≠гл€дуваних операц≥й.  ожна акс≥ома подана у двох формах: конТюнктивн≥й ≥ дизТюнктивн≥й, що випливаЇ ≥з принципу двоњстост≥ лог≥чних операц≥й, зг≥дно €кого операц≥њ конТюнкц≥њ ≥ дизТюнкц≥њ допускають взаЇмну зам≥ну, €кщо одночасно пом≥н€ти лог≥чну 1 на 0, а 0 на 1; знак Ú на Ù, а знак Ù на Ú.

јкс≥оми конТюнкц≥њ, дизТюнкц≥њ ≥ запереченн€:

1. ; 1. 0 Ù 0 = 0; 1. 0 Ú 0 = 0;

2. . 2. 0 Ù 1 = 0; 2. 0 Ú 1 = 1;

3. 1 Ù 0 = 0; 3. 1 Ú 0 = 1;

4. 1 Ù 1 = 1; 4. 1 Ú 1 = 1;

«акони булевоњ алгебри випливають ≥з акс≥ом ≥ також мають дв≥ форми вираженн€: дл€ конТюнкц≥њ ≥ дл€ дизТюнкц≥њ.

 омутативн≥ закони

а) ; б) .

—получн≥ закони

а) ; б) .

–озпод≥льн≥ закони

а) ; б)

«акони поглинанн€

а) ; б) .

«акони склеюванн€

а) ; б) .

«акон подв≥йного запереченн€

.

«акони де ћоргана

а) ; б)

або п≥сл€ ≥нвертуванн€ л≥вих ≥ правих частин:

в) ; г) .

«ауважимо, що закони де ћоргана Ї д≥йсними дл€ будь-€коњ к≥лькост≥ зм≥нних:

; .

«акони ≥демпотентност≥

а) ; б) .

«акони ун≥версальноњ множини

а) ; б) .

«акони нульовоњ множини

а) ; б) .

«акони доповненн€

а) ; б) .

ѕравильн≥сть наведених закон≥в легко доводитьс€ за допомогою викладених вище акс≥ом або шл€хом побудови таблиц≥ ≥стинност≥.

ƒоведемо, наприклад, справедлив≥сть розпод≥льного закону (випадок б):

—початку виконаЇмо доведенн€ скориставшись акс≥омами:

.

ƒоведемо шл€хом побудови таблиц≥ ≥стинност≥. ƒл€ цього побудуЇмо таблиц≥ ≥стинност≥ дл€ вираз≥в, €к≥ знаход€тьс€ в л≥в≥й ≥ прав≥й частинах р≥вност≥. –езультати обчислень наведено в табл. 9.

“аблиц€ 9

               
               
               
               
               
               
               
               

—п≥впаданн€ значень у вид≥лених стовпц€х табл. 9 доводить справедлив≥сть р≥вност≥.

јналог≥чно можна довести ≥нш≥ закони.

≤з комутативного ≥ асоц≥ативного закон≥в дл€ дизТюнкц≥њ (конТюнкц≥њ) випливаЇ, що дизТюнкц≥€ (конТюнкц≥€) дек≥лькох зм≥нних може виконуватись посл≥довно, причому пор€док обчисленн€ дизТюнкц≥њ не впливаЇ на результат. ÷е даЇ можлив≥сть сформулювати так≥ правила:

1. якщо в лог≥чному добутку (конТюнкц≥њ), що м≥стить не менше двох сп≥вмножник≥в, один ≥з сп≥вмножник≥в дор≥внюЇ нулю, то лог≥чний добуток дор≥внюЇ нулю.

2. якщо в лог≥чному добутку, що м≥стить не менше двох сп≥вмножник≥в, Ї сп≥вмножник, €кий дор≥внюЇ одиниц≥, то цей сп≥вмножник можна вилучити.

3. якщо в лог≥чн≥й сум≥ (дизТюнкц≥њ), що м≥стить не менше двох доданк≥в, Ї доданок, €кий дор≥внюЇ нулю, то цей доданок можна вилучити.

4. якщо в лог≥чн≥й сум≥, один ≥з доданк≥в дор≥внюЇ одиниц≥, то ц€ сума дор≥внюЇ одиниц≥.

ѕриклад 2. а) ƒовести, що ћаЇмо

б). ƒовести, що . ћаЇмо

в) ƒовести, що . ћаЇмо

г) ƒовести, що . ћаЇмо

.

ƒвоњст≥сть

ќзначенн€ 1. Ћог≥чна функц≥€ називаЇтьс€ двоњстою до функц≥њ , €кщо .

ќзначенн€ 2. ‘ункц≥€, двоњста сама до себе, тобто , називаЇтьс€ самодвоњстою.

ѕравило побудови двоњстоњ функц≥њ. ƒл€ запису функц≥њ , двоњстоњ до функц≥њ , треба у функц≥њ всюди 0 зам≥нити на 1, 1 Ц на 0, знак Ù Ц на Ú, а знак Ú Ц на Ù. Ќаведене правило побудови двоњстих функц≥й називаЇтьс€ принципом двоњстост≥.

ѕриклад 3. Ќехай, задано лог≥чну функц≥ю . ѕобудувати функц≥ю двоњсту до заданоњ.

–озвТ€занн€. а) ¬иход€чи з означенн€ двоњстост≥ та застосувавши правило де ћоргана два рази, одержимо

.

б) —користавшись правилом побудови двоњстих функц≥й (принципом двоњстост≥) зразу одержимо, що .

Ћегко переконатись, що таблиц€ ≥стинност≥ двоњстоњ функц≥њ одержуЇтьс€ з таблиц≥ ≥стинност≥ дл€ функц≥њ шл€хом ≥нвертуванн€ (зам≥ною значень 0 на 1 та 1 на 0) значень функц≥њ й записом стовпчика ≥нвертованих значень функц≥њ у зворотному пор€дку (див. два останн≥ стовпц≥ табл. 10)

“аблиц€ 10

x y z    
                         
                         
                         
                         
                         
                         
                         
                         

Ќа п≥дстав≥ закон≥в де ћоргана можна вивести таке твердженн€: €кщо функц≥€ двоњста до функц≥њ , то справедлива тотожн≥сть

.

“аким чином, запереченн€ функц≥њ можна знайти або за допомогою закону де ћоргана, або зам≥ною в функц≥њ двоњстоњ до заданоњ значенн€ вс≥х зм≥нних на протилежн≥ Ц на на , де .

Ћог≥чна функц≥€ Ї самодвоњстою (непарною), €кщо на кожн≥й пар≥ протилежних набор≥в вона приймаЇ протилежн≥ значенн€, тобто

або .

ƒл€ двох зм≥нних такими функц≥€ми Ї: .

ѕриклад 4.  ористуючись таблицею ≥стинност≥ ви€снити чи Ї функц≥€ самодвоњстою.

–озвТ€занн€. ƒл€ побудови двоњстоњ функц≥њ скористаЇмось правилом побудови двоњстих функц≥й. јнал≥зуючи таблицю ≥стинност≥ (табл.11) легко переконатись, що побудована функц≥€ не Ї самодвоњстою, тобто: , .

“аблиц€ 11

x y  
                 
                 
                 
                 




ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-11-05; ћы поможем в написании ваших работ!; просмотров: 1342 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

¬елико ли, мало ли дело, его надо делать. © Ќеизвестно
==> читать все изречени€...

2277 - | 1948 -


© 2015-2024 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.027 с.