Ћекции.ќрг


ѕоиск:




 атегории:

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

 

 

 

 


—уществуют следующие способы задани€ множеств




1. ѕеречислением элементов множества. Ќапример: ј = {1, 3, 5, 7,9} - конечное множество; ¬ = {1, 2,..., n,...} - бесконечное множество.

2. ”казанием свойств элементов множества. ƒл€ этого способа пользуютс€ следующим форматом записи: ј = { а| указание свойства элементов}. «десь а €вл€етс€ элементом множества A, а ј.

ѕример 1.7.

’= { х | х=2к, где k= 1,2,3,...}.

ј = { а | а Ч простое число}

¬= { b|b2-1=0, b- действительное число}

”ниверсальным множеством называетс€ такое множество U, что все рассматриваемые в данной задаче множества €вл€ютс€ его подмножествами.

ƒл€ нагл€дного представлени€ множеств и отношений между ними используютс€ диаграммы ¬енна (иногда их называют кругами Ёйлера или диаграммами Ёйлера - ¬енна).

”ниверсальное множество изображают в виде пр€моугольника, а множества, вход€щие в универсальное множество, - в виде кругов внутри пр€моугольника; элементу множества соответствует точка внутри круга.

— помощью диаграмм ¬енна удобно иллюстрировать операции над множествами.

ќперации над множествами

–ассмотрим основные операции над множествами.

ƒл€ множеств определены следующие операции: объединение, пересечение, дополнение.

ќбъединением множеств ј и ¬ (записываетс€ јÈ¬) называетс€ множество, состо€щее из элементов как одного, так и второго множества. Ќапример, ј и ¬ Ч множества точек, принадлежащих неко≠торым двум кругам, имеющим общие точки, тогда объединением јÈ¬ будет фигура, состо€ща€ из общих точек.

ѕересечением множеств ј и ¬ (записываетс€ јÇ¬) называетс€ множество, состо€щее из элементов, принадлежащих как одному, так и второму множеству одновременно.

–ис. 3.1. ќперации над множествами

ƒополнением множества ј до ¬ называетс€ множество, состо€щее из элементов множества ¬, не принадлежащих ј. ƒополнение обо≠значаетс€ ј = ¬-ј (рис. 3.1).

ќсновы логики

 ак было отмечено ранее, информатика Ч прикладна€ наука, наход€ща€с€ на стыке многих наук. ¬месте с тем она опираетс€ на спектр разделов такой фундаментальной науки, как математика. Ќаи≠более важное прикладное значение дл€ информатики имеют булева(€) алгебра, используема€ в разработке алгоритмов программ и в синте≠зе цифровых устройств, теори€ множеств и теори€ графов, исполь≠зуемые в описании различных структур.

јппарат алгебры логики (булевой алгебры) создан в 1854 г. ƒж. Ѕулем как попытка изучени€ логики мышлени€ математиче≠скими методами.

ќсновное пон€тие булевой алгебры Ч выказывание. ѕод простым высказыванием понимаетс€ повествовательное предложение, о кото≠ром можно сказать, истинно оно или ложно (третьего не дано). ¬ы≠сказывани€ обозначаютс€ латинскими буквами и могут принимать одно из двух значений: Ћќ∆№ (обозначим 0) или »—“»Ќј (обозна≠чим 1). Ќапример, содержание высказывани€ ј: Ђдважды два равно четыремї истинно ј = 1, а высказывание ¬: Ђтри больше п€тиї все≠гда есть Ћќ∆№. ¬ дальнейшем нас не будет интересовать содержа≠тельна€ часть высказываний, а только их истинность. ƒва высказы≠вани€ ј и ¬ называютс€ равносильными, если они имеют одинаковые значени€ истинности, записываетс€ ј = ¬.

јппарат булевой алгебры, как илюба€ друга€ формальна€ ма≠тематическа€ система, состоит из трех множеств: элементов, опе≠раций над ними и аксиом.

Ёлементы. —хемы вычислительных устройств можно условно разделить на три группы: исполнительные, информационные и уп≠равл€ющие. ѕервые производ€т обработку информации, представ≠ленной в бинарной форме; вторые служат дл€ передачи бинарной формы информации; третьи выполн€ют управл€ющие функции, генериру€ соответствующие сигналы. ¬о всех случа€х в тех или иных точках логических схем сигналы двух различных уровней могут представл€тьс€ бинарными символами {0,1} или логически≠ми значени€ми {»стина (True), Ћожь (False)}. ѕоэтому множество элементов булевой алгебры выбираетс€ бинарным ¬ - {0,1}, а сама алгебра называетс€ бинарной, или переключательной. ≈е элемен≠ты называютс€ константами, или логическими 0 и 1, которым в р€де случаев соответствуют бинарные цифры, в других случа€х Ч логи≠ческие значени€, соответственно ложь (False) и истина (True). ¬ дальнейшем дл€ обозначени€ булевых переменных будем исполь≠зовать буквы латинского алфавита Ч х, у, г... Ќабор переменных х, у, z... может рассматриватьс€ как n-разр€дный двоичный код, раз≠р€дами которого €вл€ютс€ эти переменные.

ќперации. ќсновными, или базовыми, операци€ми булевой ал≠гебры служат (табл. 3.1): » (AND), »Ћ» (OR) и Ќ≈ (NOT). ќпе≠раци€ » называетс€ логическим умножением, или конъюнкцией, и обозначаетс€ знаком умножени€ {Х, Ù}. ќпераци€ »Ћ» называетс€ логическим сложением, или дизъюнкцией, иобозначаетс€ знаком сложени€ {+, Ú}. ќпераци€ Ќ≈ называетс€ логическим отрицани≠ем, или инверсией (дополнением), и обозначаетс€ знаком , }.

“аблица 3.1 Ѕазовые логические операции

ќпераци€ Ќазвание операции ќбозначение операции
» (AND) Ћогическое умножение Ч конъюнкци€ Ù Х
»Ћ» (OR) Ћогическое сложение Ч дизъюнкци€ + Ú
≈—Ћ» (TO) »мпликаци€, следование Þ, Ѓ
Ќ≈ (NOT) Ћогическое отрицание Ч инверси€ Ч,
       

ѕри выполнении операций примен€ютс€ отношение эквивалент≠ности Ђ=ї и скобки Ђ()ї, которые определ€ют пор€док выполне≠ни€ операций. ≈сли скобок нет, то операции выполн€ютс€ в следу≠ющей последовательности: логическое отрицание, логическое умножение и логическое сложение.

—ложное высказывание можно построить из простых с помощью логических операций: отрицани€, конъюнкции, дизъюнкции, импликации и логических выражений, представл€ющих собой комбинации логи≠ческих операций. –ассмотрим их подробней.

ќперацией отрицани€ ј называют высказывание Ā (или -ј, го≠вор€т не ј), которое истинно тогда, когда ј ложно, и ложно тогда, когда ј истинно. Ќапример, если событие ј состоит в том, что Ђзав≠тра будет снегї, то Ā Ђзавтра Ќ≈ будет снегаї, истинность одного утверждени€ автоматически означает ложность второго. ќтрица≠ние - унарна€ (т.е. дл€ одного операнда) логическа€ операци€. ≈й соответствует €зыкова€ конструкци€, использующа€ частицу Ќ≈.

Ёто правило можно записать в виде следующей таблицы:

ј Ā
   
   

“ака€ таблица называетс€ таблицей истинности.

 онъюнкцией (логическим умножением) двух высказываний ј и ¬ €вл€етс€ новое высказывание —, которое истинно только тогда, ког≠да истинны оба высказывани€, записываетс€ — = ј Ù ¬ или — = ј & ¬ (при этом говор€т — равно ј и ¬). ѕримером такой операции может быть следующа€: пусть высказывание ј состоит в том, что Ђвысота шкафа меньше высоты двериї, событие ¬ Ђширина шкафа меньше ширины двериї, событие — Ђшкаф можно внести в дверь, если ши≠рина шкафа меньше ширины двери » высота шкафа меньше высо≠ты двериї, т.е. данна€ операци€ примен€етс€, если два высказыва≠ни€ св€зываютс€ союзом ».

“аблица истинности этой операции, как следует из определени€, имеет вид

ј ¬ ј&¬
     
     
     
     

ƒизъюнкцией (логическим сложением) двух высказываний ј и ¬ €вл€етс€ новое высказывание —, которое истинно, если истинно хот€ бы одно высказывание. «аписываетс€ — = A Ú ¬ (при этом говор€т: — равно ј »Ћ» ¬). ѕример такой операции следующий: пусть вы≠сказывание ј состоит в том, что Ђстудент может добиратьс€ домой на автобусеї, событие ¬ Ђстудент может добиратьс€ домой на трол≠лейбусеї, событие — Ђстудент добралс€ домой на автобусе »Ћ» трол≠лейбусеї, т.е. данна€ операци€ примен€етс€, если два высказывани€ св€зываютс€ союзом »Ћ».

“аблица истинности такой операции следующа€:

ј ¬ AÚB
     
     
     
     

»мпликацией двух высказываний ј (ј называетс€ посылкой) и ¬ (¬ называетс€ заключением) €вл€етс€ новое высказывание —, кото≠рое ложно только тогда, когда посылка истинна, а заключение лож≠но, записываетс€ — = ј Ѓ ¬ (при этом говор€т: из ј следует ¬). ѕримером такой операции может быть любое рассуждение типа: если произошло событие ј, то произойдет событие ¬, Ђесли идет дождь, то на небе тучиї. ќчевидно, операци€ не симметрична, т.е. из ¬ Ѓ ј не всегда истинно, в нашем примере Ђесли на небе тучи, то идет дождьї не всегда истинно.

“аблица истинности импликации следующа€:

ј ¬ ј→¬
     
     
     
     

»мпликаци€ имеет следующие свойства:

ј→¬ ¹ ¬ → ј

ј→ ј= 1

0 →ј= 1

1 → ј = ј

ј→ 1 = 1

ј→ 0 = ј

Ёквиваленцией двух высказываний ј и ¬ €вл€етс€ новое выска≠зывание —, которое истинно только тогда, когда оба высказывани€ имеют одинаковые значени€ истинности, записываетс€ — = ј Ђ¬ (— = ј º ¬). ѕримером такой операции может быть любое выска≠зывание типа: событие ј равносильно событию ¬.

“аблица истинности:

ј ¬ ј↔¬
     
     
     
     

Ёквиваленци€ имеет следующие свойства:

ј↔ ¬ = ¬ ↔ ј

ј ↔ = ↔Ā

ј↔ 1 = ј

ј ↔ 0 = Ā

— помощью логических операций из простых высказываний (ло≠гических переменных и констант) можно построить логические вы≠ражени€, которые также называютс€ булевскими функци€ми. Ќапри≠мер, — = ((A Ú ¬) → ¬) Ú ј.

„тобы избежать большого количества скобок в булевских функ≠ци€х, прин€то следующее соглашение о старшинстве операций.

ѕервыми выполн€ютс€ операции в скобках, затем операции в следующем пор€дке: отрицание, конъюнкци€ и дизъюнкци€ слева направо, импликаци€, эквиваленци€.

«ависимости между логическими операци€ми

ќперации не €вл€ютс€ независимыми; одни из них могут быть выражены через другие. ћожно доказать с помощью таблиц истин≠ности следующие равносильности:

«аконы алгебры логики

1. «акон двойного отрицани€

2. коммутативный закон дл€ конъюнкции

3. коммутативный закон дл€ дизъюнкции

4. ассоциативный закон дл€ конъюнкции

5. ассоциативный закон дл€ дизъюнкции

6. дистрибутивные законы

7.

8. законы де ћоргана

9.

10. закон идемпотенции дл€ конъюнкции

11. закон идемпотенции дл€ дизъюнкции

12. закон единицы дл€ конъюнкции

13. закон нул€ дл€ конъюнкции

14. закон единицы дл€ дизъюнкции

15. закон нул€ дл€ дизъюнкции

16. закон исключени€ третьего

17. закон противоречи€

18.

19.

20. законы поглощени€

21.

22.

23.

ќдну и ту же зависимость между логическими переменными можно выразить различными формулами. ѕоэтому важно иметь воз≠можность приводить формулы с помощью эквивалентных преобра≠зований к некоторому стандартному виду. —уществует несколько стандартных форм, к которым привод€тс€ логические выражени€ с помощью эквивалентных преобразований (формул 1-23).

ѕерва€ из них Ч дизъюнктивна€ нормальна€ форма (ƒЌ‘), имеет вид Al Ú A2 Ú... Ú An, где каждое из составл€ющих высказываний есть конъюнкци€ простых высказываний и их отрицаний, например:

¬ = (ј1 & ј2 & A3) Ú (ј4 & ј5).

¬тора€ - конъюнктивна€ нормальна€ форма ( Ќ‘), имеет вид ј1 Ù ј2 Ù... Ù An, где каждое из составл€ющих есть дизъюнк≠ци€ простых высказываний и их отрицаний, например:

¬ = (Al Úј2 ÚA3) & (ј4 Ú ј5) & ј6.





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


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


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

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

80% успеха - это по€витьс€ в нужном месте в нужное врем€. © ¬уди јллен
==> читать все изречени€...

1456 - | 1291 -


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

√ен: 0.04 с.