Шпаргалка (1076938), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Пример. Рассмотрим набор букв (алфавит) и множество слов в этом алфавите, которое обозначим М. На множестве М зададим бинарную операцию * следующим образом: для любых слов u иvиз мн-ва М определим и * v = uv, то есть слово и * v получено приписыванием к слову и слова v. Тогда (М, *) - полугруппа. Доб. к мн-ву М пустое слово е, тогда ({М, е}, *) - моноид.

Теорема 2.5. Нейтральный элемент в моноиде - единственен.

Доказательство. Пусть (М, *) - моноид; е, f - два нейтральных элемента в (М, *). Тогда е = е*f = f по определению.

Определение 2.6. Пусть (М, *, е) - моноид. Элемент b называется обратным к элементу а, если а*b=b*а=е. Элемент а в этом случае называют обратимым элементом; элемент b обозначают а ^-1.

Заметим, что, если * - операция сложения, то вместо а ^-1 пишут — а и называют этот элемент противоположным к элементу а. Например, в моноиде (Z, +,0) любой элемент z имеет противоположный элемент — z, то есть на множестве Z определена унарная опера­ция: f(z) = —z. В моноиде (Z, ∙, 1) обратимы только два элемента: 1 и -1.

Теорема 2.7. Пусть (М, *,е) - моноид. Тогда:

1. для любого элемента а М обратный элемент, если он существует, - единственен;

2. элемент е - обратим и е ^-1 = е;

3. обратный элемент a ^-1 к элементу а, если он существует, обратим и (а ^-1) ^-1 = а;

4. если а, b - обратимые элементы в М, то (а * b) ^-1 = b ^-1 * a ^-1.

Доказательство. 1) Предположим b₁, b₂ - обратные элементы к элементу а М. Тогда

b₁ = b₁ * e = b₁ * (a * b₂) = (b₁ * a) * b₂ = e * b₂ = b₂.

Утверждения 2) и 3) - очевидны.

4) Так как (а * b) * (b ^-1 * а ^-1) = а * (b * (b ^-1 * b ^-1)) = а * ((b * b ^-1) * a ^-1) = а * (е * a ^-1) = а * a ^-1 = е, то 4) доказано.

Определение 2.8. Алгебраической системой называют непустое множество с семейством операций и отношений, заданных на нем.

Мы уже рассматривали примеры алгебраических систем: полугруппы, моноиды, линейно или частично упорядоченные множества, множества с отношением эквивалентности. Пример более богатой структуры: (Z, +, ∙, 0,1, ≤).Здесь определены две бинарные операции: + и ∙ ; две 0-арные операции: выделены 0 и 1 ; определено также отношение порядка ≤

Рассмотрим три основных способа построения новых алгебраических из уже имеющихся.

Определение 2.9. Пусть М - алгебраическая система, N является подмножеством мно­жества М, N ≠ Ø. N называется подсистемой алгебраической системы М, если

1. N замкнута относительно всех операций, определенных на N: для любой n-арной опера­ции f(a₁,..., а_п), определенной на множестве М, и любого набора элементов {m₁,..., т_п} из множества N элемент f(m₁,..., т_п) N;

2. для любого отношения S, заданного на множестве М в данной алгебраической системе, определено сужение S_N этого отношения на подмножестве N: если n₁, n₂ N, то n₁ S_N n₂ тогда и только тогда, когда n₁ S_n2

Заметим, что, если алгебраическая система имеет специальное название: моноид, группа, кольцо, поле, то подсистема называется соответственно: подмоноид, подгруппа, подкольцо, подполе.

13. Отношения на множестве. Отношения порядка. Определение и примеры.

14. Отношение эквивалентности. Определение и примеры.

Определение 1.31. Пусть {X₁, X₂,... ,Х_п} - непустые множества. Тогда п-местным отношением, заданным на декартовом произведении Х₁ × Х₂ × ... × Х_п, называют под­множество S Х₁ × Х₂ × ... × Х_п,. При этом, если (х₁,₂,..., х_п) S, то говорят, что элементы {х₁, x₂,..., х_п} множества X связаны отношением S; если же (х₁,₂,..., х_п) S то говорят, что элементы {х₁, x₂ ,..., х_п} не связаны отношением S.

Определение 1.32. Пусть α - бинарное отношение на X × Y, β - бинарное отношение на Y × Z. Тогда композицией отнтшенип α и β называется бинарное отношение, обозна­чаемое α о β, на X × Z, определенное следующим образом: х(а о β)y тогда и только тогда, когда существует такой элемент у Y, что хαу и yβz.

Для композиции отношений выполняется свойство ассоциативности, то есть (α о β) о γ = α о (β о γ) для любых бинарных отношений α, β,γ - Заметим, однако, что для произвольных бинарных отношений α и β не выполняется коммутативность то есть α о β ≠ β о α.

Определение 1.33. Бинарным отношением на множестве X называется бинарное от­ношение на X × X.

Примеры.

1)Пусть X = R. Тогда на этом множестве можно определить следующее бинарное отно­шение α: хαу тогда и только тогда, когда х² = у² (х и у - элементы множества R.)

2) Пусть X = N. Тогда на множестве N определим следующем образом бинарное отноше­ние <:

п₁ ≤ n₂ тогда и только тогда, когда (n₂ — n₁) N {0} .

3) Пусть X = N. Тогда на множестве N определим следующем образом бинарное отноше­ние <:

п₁ < п₂ тогда и только тогда, когда (п₂ — п₁) N.

Далее сформулируем определения основных свойств бинарных отношений: рефлексив­ности, транзитивности, симметричности и антисимметричности. С помощью этих свойств выделяются два важнейших вида бинарных отношений: отношение порядка и отношение эквивалентности.

Определение 1.34. Бинарное отношение α на множестве X называется рефлексивным, если для любого элемента х из множества X выполняется отношение хαх.

Определение 1.35. Бинарное отношение α на множестве X называется транзитивным, если для любых элементов х, у, z из множества X таких, что хαу и yαz, следует, что xαz.

Определение 1.36. Бинарное отношение α называется симметричным, если для любых элементов x, у из множества X таких, что хαу, следует, что уαх.

Определение 1.37. Бинарное отношение α на множестве X называется антисиммет­ричным, если для любых элементов х, у из множества X таких, что хαу и уαх, следует, что x = у.

Примеры.

1. Отношение = на любом множестве X является рефлексивным, транзитивным и симметричным.

2. Отношение ≤ на множестве N является рефлексивным, транзитивным и антисимметричным.

1. Отношение < на множестве N является транзитивным, но не является рефлексивным, симметричным и антисимметричным.

2. Пусть X - произвольное непустое множество. Тогда на множестве 2^X (множество всех подмножеств множества X) рассмотрим бинарное отношение (Х₁ Х₂). Это бинарное отношение будет рефлексивным, транзитивным и антисимметричным.

Определение 1.38. Бинарное отношение α на множестве X называется отношением по­рядка, если оно рефлексивно, транзитивно и антисимметрично. При этом, если для любых элементов х, у из множества X справедливо либо хαу, либо уαх, то α называют линейным порядком, а пару (X, α) (множество X с линейным порядком α) - линейно упорядоченным множеством; в противном случае α - частичный порядок, а (Х,α) - частично упорядо­ченное множество.

Примеры.

1. (N, ≤), (R, ≤) - линейно упорядоченные множества.

2. {2^А, ) - частично упорядоченное множество, если |А| > 1. Если же |А| = 1, то (2^A, ) - линейно упорядоченное множество.

Определение 1.39. Бинарное отношение α на множестве X называется отношением эквивалентности, если оно рефлексивно, транзитивно и симметрично.

Примеры.

1. Отношение α на множестве R такое, что хαу тогда и только тогда, когда х² = у², является отношением эквивалентности.

2. Отношение = на N, R и на любом множестве X является отношением эквивалентности.

Определение 1.40. Пусть α - отношение эквивалентности на множестве X, х - произ­вольный элемент множества X. Тогда классом эквивалентности (смежности) элемента х по отношению эквивалентности α называется множество [х]_α = {у X | хαу}.

15. Определение графа. Виды графов. Подграфы. Операции над графами.

16 . Изоморфизм. Помеченные и непомеченные графы. Матрицы, ассоциативные с помеченными графами.

Определение графа

Пусть задано конечное множество V , которое будем называть мно­жеством вершин. Некоторые из этих вершин соединим ребрами, т.е. выделим в множестве V⁽²⁾ всех двухэлементных подмножеств множе­ства V некоторое подмножество Е, которое и будем называть множе­ством ребер графа. Итак, граф - это пара (V, Е), где V - конечное множество, а Е V⁽²⁾. Более подробно множества V и Е обознача­ются как VG и EG соответственно. Число card(VG) вершин графа G называют его порядком и обозначают через |G|.

Говорят, что две вершины u и v смежны, если множество {u,v} явля­ется ребром, и не смежны в противном случае. Если е = {u,v} - ребро, то вершины и и v называют его концами и говорят, что ребро е со­единяет вершины u и v, Такое ребро обозначается символом uv. Два ребра называются смежными, если они имеют общий конец. Вершина о и ребро е называются инцидентными, если и является концом ребра е (т.е. е = uv) и не инцидентными в противном случае.

Множество всех вершин графа G, смежных с некоторой вершиной v, называется окружением вершины v и обозначается через N_G(v) или N(v).

Рис.1

Графы удобно изображать в виде рисунков, состоящих из точек (вер­шины графа) и линий, соединяющих некоторые из этих точек (ребра графа). Приведем примеры некоторых графов специального вида. Граф G называется полным, если любые две его вершины смежны, т.е. EG = (VG)⁽²⁾. Полный граф порядка п обозначим К_п, число ребер в нем рав­но С_n² = п(п — 1)/2. На рис.1, а изображен полный граф К₅. Граф называется пустым , если в нем нет ребер. Пустой граф порядка п обозначим О_n. На рис.1 б,в показаны также простые циклы С_п для n = 3,4 , а на рис.1 г, д - простые цепи Р_п для п = 4,5. Очевидно, что К₂ = Р₂ и К₃ = С₃.

Рис.2

На рис.2, а,б приведены два изображения простого цикла С₅ , а также колее W_n для п = 3,4 (в,г).

К расивыми примерами являются графы пяти платановых тел (т.е. правильных многогранников): тетраэдра, куба, октаэдра, додекаэдра, икосаэдра.

Напомним, что разбиением множества S называется представление его в виде объединения подмножеств, никакие два из которых не пе­ресекаются. Граф называется двудольным, если существует разбиение множества его вершин на части (доли) такие, что концы каждого ре­бра принадлежат разным частям. Если при этом любые две вершины, входящие в разные доли, смежны, то граф, доли которого состоят из р и q вершин, обозначается символом K_p,q . При р = 1 получаем звезду К_1,q. Легко проверить, что K_1,1 = К₂ = P₂ , K_1,2 = Р₃. На рис. 3 изображены звезда K_1,5 и двудольный граф K_3,3. Как видно из определения, граф - это алгебраическая система с одним отношением специального вида. Следовательно, к графам применимы понятия гомоморфизма, изоморфизма и автоморфизма. В част­ности, два графа G и Н называются изоморфными, если существует биекция φ: VG → VH такая, что две вершины u,v VG соединены ребром тогда и только тогда, когда их образы φ(и), φ(v) соединены ребром в H. В этом случае пишем G H, Например, граф К_3,3 на рис.3 изоморфен графу "а" на рис.4, а графы "б" и "в" на этом же рис. 4 не изоморфны. В некоторых ситуациях все же приходится различать изоморфные графы, и тогда полезно понятие помеченного графа. Граф порядка п называется помеченным, если его вершинам присвоены не­которые метки, например, номера 1,2,... , п. Отождествим каждую из вершин графа с ее номером и определим равенство помеченных гра­фов G и Н одного и того же порядка: G = Н тогда, когда EG = EH. Различные помеченные графы могут быть изоморфны между собой.

Для произвольного графа G определяется дополнительный граф : множество вершин у него то же самое, что и у графа G, a E = V⁽²⁾ \ EG, т.е. две вершины в смежны тогда и только тогда, когда они не являются смежными в G. Граф, изоморфный своему дополнению, называется самодополнительным. Например, K₁,P₄,C₅ - самодополни­тельные графы.

И ногда приведенное выше определение графа недостаточно и при­ходится рассматривать более общие объекты, в которых две вершины могут быть соединены более чем одним ребром. Так возникает понятие "мультиграф". Дальнейшее обобщение состоит в том, что кроме крат­ных ребер допускаются еще и петли, т.е. ребра, соединяющие вершину саму с собой. Такой объект называется псевдографом. Изучаются так­же ориентируемые графы: это пара, состоящая из множества вершин V и из нек. подмнож. А декартова квадрата V² (вместо V⁽²⁾), Если а = (u,v) А, то а изобр. дугой со стрелкой; и назыв. началом, а v - концом этой дуги.

Определение 2.10. Пусть М и N - алгебраические системы с одинаковым набором опе­раций и без отношений. Тогда декартово произведение М × N будет такой же алгебраи­ческой структурой, если для любой k-арной операции f(a₁,..., a_k), определенной на мно­жествах М и N, на множестве М × N следующим образом определим операцию:

f((m₁, n₁), . . . , (m_k, n_k)) = (f(m₁, . . . ,m_k), f(n₁, . . . , n_k)).

Аналогично опеделяются операции на произведении п алгебраических систем.

Определение 2.11. Пусть М - алгебраическая система, в которой нет отношений. Пред­положим, что на М можно задать отношение эквивалентности ~, согласованное с опе­рациями на М, а именно: для любой n-арной операции f(a₁,... ,а_п), определенной в ал­гебраической системе М и любых элементов из М таких, что m₁ ~ т₁’,..., т_п ~ т_п’ выполняется отношение f(m₁,..., т_п) ~ f(rn₁’,..., т_п’). Тогда множество классов эквива­лентности (М/ ~) превращается в алгебраическую систему с теми же операциями, что действуют на множестве М :

f([m₁]_~ , [m₂]_~, . . . , [m₂]_~) = [f(m₁,m₂, . . . ,m_n)]_~.

Такая алгебраическая система называется фактор-системой алгебраической системы М по отношению эквивалентности ~.

Пример. Всем с детства известна алгебраическая система, где множество М = {чет, нечет}; задана бинарная операция + : чет + чет = нечет + нечет = чет, чет + нечет = нечет + чет = нечет; выделен нулевой элемент: 0 = чет. Такая алгебраическая система фактически яв­ляется фактор-системой алгебраической системы (Z, +, 0) по отношению эквивалентности ~:

z₁ ~ z₂ тогда и только тогда, когда z₁ - z₂ делится нацело на 2.

Определение 2.12. Группой называется множество G с бинарной операцией, обознача­емой обычно ∙, удовлетворяющей трем условиям:

1)операция ∙ - ассоциативна;

2)существует единичный элемент е такой, что g • е = е • g = g для любого g G;

3)все элементы множества G обратимы, то есть для любого g G найдется такой элемент g ^-1 G, что g ∙ g ^-1 = g ^-1 ∙ g = е.

Итак, группа - это моноид, в котором каждый элемент обратим. Заметим, что группа G называется абелевой, если операция ∙ коммутативна.

В группе G можно решить любое уравнение вида а∙х = b или х∙а = b (a,b G). Решением первого уравнения будет х = а ^-1∙b, а второго - х = b ∙ а ^-1. Если операция в группе - сложение, то рассмотренные выше уравнения имеют вид: а + х = b или х + а = b; соответ­ственно решениями будут х = (-а) + b или х=b+(-а), где (-а) - противоположный (обратный) элемент к элементу а.

Примеры.

1. Алгебраические системы (Z, +, 0), (R, +, 0) являются абелевыми группами по сложению.

2. Множество всех невырожденных матриц размера п х п над R относительно обычной операции умножения матриц является группой, которую обозначают GL_n(R).

1. Множество SL_n(R) = {А GL_n(R) | detA = 1} - группа относительно обычной операции умножения матриц, являющаяся подгруппой группы GL_n(R). Такая группа называ­ется специальной линейной группой.

2. Алгебраическая система ({е},-|е∙е = е) является группой, состоящей только из одного единичного элемента. Такая группа называется единичной. Заметим, что в любой группе есть единичная подгруппа.

3. Алгебраическая система ({1,-1} | 1,-1 Z, ∙) - группа из двух элементов относительно обычной операции умножения на Z.

4. Пусть X = {1,2,..., n}. Тогда алгебраическая система (BiX^X,o) является группой всех биективных отображений множества X на себя относительно операции композиции.

Такую группу называют группой подстановок на множестве X. Рассмотрим ее более подробно. Пусть σ ВiХ^X и σ(1) = i₁, σ(2) = i₂,..., σ(п) = i_n. Отображение σ назовем подстановкой и обозначим (i₁, i₂,..., i_n). Подстановка е = (1, 2,..., п), называемая тождественной подстановкой, будет нейтральным элементом, или единицей в группе под­становок на множестве X. Для любого элемента а = (i₁, i₂,..., i_n) из группы подстановок определен обратный элемент σ ^-1 так, что у⁻¹(i_j) = j, (j {1, 2,…, n}).

Группу подстановок на множестве из п элементов обозначают S_n. Таким образом, BiX^X = S_n. Известен порядок этой конечной группы: |S_n| = |ВiХ^X| = п!. Если п > 3, то группа S_n не является абелевой группой.

17. Деревья. Планарность графов.

Деревья

Деревом называется связный граф, не содержащий циклов. Любой граф без циклов называется ациклическим или лесом. Следующая тео­рема характеризует и дает эквивалентные определения дереву.

Теорема 1. Для (п, т)-графа G следующие условия эквивалентны:

а) G - дерево;

б) G - связный граф и т = п - 1;

в) G - ациклический граф и т = п - 1;

г) любые две несовпадающие вершины графа G соединяет единственная простая цепь.

Следствие. В любом дереве порядка п ≥ 2 имеется не менее двух концевых вершин.

Пусть Н - остовной подграф произвольного графа G. Если на каждой области связности графа G графом H порождается дерево, то Н назы­вается остовом или каркасом графа G. Очевидно, что в любом графе существует остов: разрушая в каждой компоненте циклы, т.е. удаляя лишние ребра, придем к остову.

Теорема 2. Число ребер произвольного графа G, которые необхо­димо удалить для получения остова, не зависит от последовательно­сти их удаления и равно m(G) - |G| + k(G), где m(G) и k(G) - число ребер и число компонент графа G соответственно.

Примеры.

1. Пусть на множестве R задано отношение α: хαу тогда и только тогда, когда х² = у². Тогда [1]_α = {1,-1}.

2. В любом множестве X с отношением эквивалентности =: [х]₌ = {х} для любого эле­мента х множества X.

Теорема 1.41. Пусть α отношение эквивалентности на множестве X, X ≠ Ø. Тогда:

1. [х]_а ≠ Ø для любого элемента х множества X;

2. для любых элементов х и у из множества X таких, что [х]_а [у]_а ≠ Ø_; следует, что [х]_а = [у]_а

3)

Доказательство. 1) Отношение α - рефлексивно, следовательно, для любого х из множе­ства X выполняется хαх. Таким образом х [x]_α и [x]_α ≠ Ø.

3) Так как х [х]_α, то , следовательно

2) Пусть [х]_α [у]_α ≠ Ø. Тогда найдется такой элемент z множества X, что xαz и yαz. Пусть t - произвольный элемент из класса [х]_α Тогда xαt и xαz, следовательно, выполняется tαz (мы воспользовались транзитивностью и симметричностю). Аналогично, так как tαz и yαz, то tαy. Таким образом [х]_α [у]_α. Точно также доказывается, что [у]_α [х]_а , и свойство 2) доказано.

Определение 1.42. Пусть α - отношение эквивалентности на множестве X. Фактор-множеством множества X по отношению эквивалентности α называется множество, обозначаемое Х/α, элементами которого являются классы эквивалентности [х]_α множества X по отношению эквивалентности α.

Определение 1.43. Пусть α - отношение эквивалентности на множестве X. Множество X' (X' X) называется системой различных представителей по отношению эквива­лентности α, если для любого х из множества X выполняется условие: |Х' [х]_α | = 1.

Заметим, что можно выбирать различные системы представителей по отношению эквивалентности α на множестве X, однако количество элементов в каждой такой системе одно и тоже. Справедлива следующая теорема, которую мы сформулируем без доказательства.

Теорема 1.44. Если α - отношение эквивалентности на множестве X, X' - система различных представителей по отношению эквивалентности α на множестве X, то существует биективное отображение φ : Х/α → X'. В частности, если Х/α -конечное множество, то |Х/α| = |Х'| .

Отношение эквивалентности на множестве обычно обозначают знаком ~.

Пример. На множестве Z рассмотрим следующее отношение эквивалентности: z₁ ~ z₂ тогда и только тогда, когда z₁ — z₂ делится нацело на 2. Тогда множество Z разбивается на два непересекающихся класса эквивалентности:

[0]_~ = {0,±2,±4,...,±2n,...},

[1]_~ = {±1,±3,...,±(2n+1),...}.

Любая система различных представителей в этом случае содержит 2 элемента. Напри­мер, {0,1} и {4,-5} - системы различных представителей множества Z по отношению эквивалентности ~.

Подграфы

Граф Н называется подграфом графа G, если VH VG, ЕН EG. Подграф Н называется остовным подграфом (или фактором), если VH = VG. Если множество ребер U = ЕН совпадет с множеством всех ребер графа G, оба конца которых принадлежат VH, то Н называется подграфом, порожденным множеством U. На рис.5 изображены граф G и три его подграфа H₁, Н₂ и H₃, среди которых H₃ является остовным, a Н₂ - порожденным.

Важный класс подграфов составляют подграфы, полученные в резуль­тате удаления вершины v VG. Граф G_v = G - v получается из графа G в результате удаления вершины v и всех инцидентных ей ребер. С графами G_v связана знаменитая гипотеза.

Операции над графами

Удаление вершины или ребра - это пример операций, уменьшающих число элементов графа. Рассмотрим теперь операции над графами, уве­личивающими число вершин или ребер. Такова, например, операция добавления ребра е = uv, если вершины u и v графа G не являются смежными. В результате получается граф G + е, у которого эти вер­шины уже соединены ребром.

Г раф H называется объединением (или наложением) графов F и G, если VH = VF VG и ЕН = EF EG (рис.6). В этой ситуации пишут H=F G

О бъединение F G называется дизъюнктным, если VF VG = Ø.

Пусть G_i m (V_i, E_i) (i = 1, 2)- два графа. Произведением G₁ G₂ = G называется граф, для которого VG = V₁ V₂ - декартово произведе­ние множеств вершин исходных графов, a EG определяется следующим образом: вершины (и₁ , и₂) и (w₁ , w₂) смежны в графе G тогда и только тогда, когда или и₁₌w₁ , а и₂ и w₂ смежны в G₂ , или и₂₌w₂ , а и₁ и w₁ смежны в G₁ (см. рис.7).

Рис. 7

Очевидно, что |G₁ G₂ | = |G₁| |G₂ |, |E(G₁ G₂ )| = |G₁ | |EG₂ | + |G₂ | |EG₁ |

С помощью операции произведения вводится рекуррентным образом важный класс графов – п-мерные кубы Q_n: Q₁=K₂; Q_n=K₂ Q_n-1 (n>l).

Граф Q_n имеет порядок 2^п, вершины его можно представить (0,1)-векторами длины п таким образом, что две вершины будут смежны тогда и только тогда , когда соответствующие векторы различаются ровно в одной координате.

Матрицы, ассоциированные с графом

В этом параграфе и далее (i,j)-й элемент матрицы М обозначает­ся M_ij. Пусть G - помеченный граф порядка п, VG = {1,2,... ,п}. Определим п n - матрицу А = A(G), положив

A(G) называется матрицей смежности графа G. Это симметрическая матрица с нулями на главной диагонали.

Теорема. Графы изоморфны тогда и только тогда, когда их ма­трицы смежности получаются друг из друга одинаковыми переста­новками строк и столбцов.

Так как при такой перестановке строк и столбцов не меняется ранг, характеристический многочлен и корни характеристического многочле­на, то имеет смысл для графа G определить ранг - rankG, как ранг матрицы A(G), характеристический полином графа и спектр графа как множество всех корней характеристического полинома (корни ве­щественны в силу симметричности матрицы A(G)).

Если спектры двух графов различны, то они не изоморфны. Обрат­ное, однако, не верно, как показывает пример неизоморфных графов K_1,4 и С₄ O₁, у которых один и тот же характеристический полином х³(x² - 4).

Вторая из матриц В = B(G) графа G называется матрицей Кирхго­фа

Сумма элементов в каждой строке и в каждом столбце матрицы B(G) равна 0. Теорема остается справедливой и для матрицы Кирхгофа.

18. Высказывание. Операции над высказываниями. Булева алгебра высказываний.

Алгебра высказываний.

Основным понятием в этом параграфе является высказывание. В определении, которое следует далее, мы используем интуитивные представления о том, что есть истина и что - ложь.

Определение 3.1. Высказывание - это повествовательное предложение, о котором мож­но сказать, истинно оно или ложно.

Рассмотрим следующие предложения.

1. 2 + 2 = 4.

2. Для любого х из R выполняется неравенство х² + 1 < 0.

3. Город Москва является столицей России.

4. Если x R, то x² - 1 < 0.

5. Длина отрезка меньше площади треугольника.

Предложения 1) и 3) - истинные высказывания; 2) - ложное высказывание; предложения 4) и 5) не являются высказываниями.

Пусть А - множество всех высказываний, Е₂ = {0,1}. Определим отображение â : А —> Е₂ следующим образом: â = 0, если a - ложное высказывание; â = 1, если а - истинное высказывание. При этом â назовем значением истинности высказывания а.

Определение 3.2. Выск-ия а и b будем называть равносильными и писать а ≡ b, если â = .

Заметим, что это определение - естественно, так как при рассмотрении высказываний нас не интересует содержательная часть, заключенная в предложении, а интересует только значение его истинности.

На множестве всех высказываний с помощью значений истинности определим следующие операции, которые называют логическими.

Определение 3.3. Отрицанием высказывания а называется высказывание, обозначае­мое , определяемое следующей таблицей:

Очевидно, что = а. Сформулированное равенство называют законом двойного отрица­ния.

Характеристики

Список файлов ответов (шпаргалок)