Вопросы по дискретной математике

1. Элементы математической логики. Операции над высказываниями.

Базовыми понятиями математической логики являются высказывания.

Высказывание – предложение, которое может быть либо положительным, либо отрицательным.

Каждому истинному высказыванию соответствует 1, отрицательному 0.

- функция истинности

Операции над высказываниями

1. Отрицание. Отрицанием высказывания Р является новое высказывание, обозначаемое , которое считается истинным, если высказывание Р ложно и ложно, если Р истинно.

P
0	1
1	0

2. Конъюнкция – высказывание, которое считается истинным, если истинны оба высказывания и ложным во всех остальных случаях.

P	Q	P˄Q
1	1	1
1	0	0
0	1	0
0	0	0

2. Дизъюнкция – высказывание, которое истинно в тех случаях, если истинно хотя бы одно из высказываний P и Q и ложно в другом случае.

P	Q	P˅Q
1	1	1
1	0	1
0	1	1
0	0	0

2. Импликация – высказывание, которое ложно лишь в том случае, если P-истинно, а Q-ложно.

P	Q	P=>Q
1	1	1
1	0	0
0	1	1
0	0	1

2. Эквивалентность – высказывание, которое истинно в том и только том случае, если P и Q одновременно истинны или одновременно ложны.

P	Q	P<=>Q
1	1	1
1	0	0
0	1	0
0	0	1

2. Формулы алгебры высказываний. Закон исключенного третьего. Логическое следование.

Формула F(х1,х2, …, хn) алгебры высказываний называется тавтологией, если её значение истинности равно 1 при любых значениях истинности для х1,х2, …, хn.

Закон исключённого третьего

1	0	1
0	1	1

α

Две формулы F(х1,х2, …, хn) и Н(х1,х2, …, хn) называются равносильными, если при любых значениях переменных х1,х2, …, хn логические значения высказываний F и Н совпадают.

F Н

Логическое следование

Формула Н(х1,х2, …, хn) является логическим следствием формул F1(х1,х2, …, хn), …, Fs(х1,х2, …, хn) если она превращается в истинное высказывание при замене х1,х2, …, хn любыми конкретными высказываниями А1,А2, …, Аn такими, что Fs(А1,А2, …, Аn) истинно.

F1, F2, …, Fs |= H

3. Предикаты. Логические операции над предикатами.

Предложение, в которое входят переменные и которое при замене переменных возможными для них значениями становится высказыванием, называется предикатом, или высказывательной формой.

При задании предиката должно указываться множество значений, которое принимает переменная. Это множество называется областью определения Х.

Если предикат содержит лишь 1 переменную, то он называется одноместным. Если n переменных, то n-местным.

Подмножество множества Х, состоящее из тех значений переменных, при которых данный предикат превращается в истинное высказывание, называется областью истинности предиката.

Два предиката с одной и той же областью определения Х называются равносильными, если они имеют одинаковые множества истинности.

PQ:

Пусть P и Q – два предиката с общей областью определения Х.

Q является следствием Р (Q<=P), если область истинности предиката Р является частью области истинности предиката Q.

P=>Q

Логические операции над предикатами

1. Отрицанием предиката Р с областью определения Х называется предикат с той же областью определения, который превращается в истинное высказывание для тех и только тех значениях хХ, при которых Р ложно.

2. Конъюнкцией предикатов Р и Q, определённых на множествах Х1 и Х2, называется предикат Р˄Q с областью определения Х=Х1Х2, который превращается в истинное высказывание для тех и только тех значениях хХ, при которых оба исходных предиката являются истинными высказываниями.

3. Дизъюнкцией предикатов Р и Q, имеющих соответствующие области определения Х1 и Х2, называется предикат Р˅Q с областью определения Х=Х1Х2, который превращается в истинное высказывание для тех и только тех значениях хХ, при которых хотя бы одно из высказываний Р и Q истинно.

4. Элементы теории множеств.

Множеством называется совокупность определённых вполне различаемых объектов, рассматриваемых как единое целое.

Отдельные объекты, которые образуют множество, называются элементами множества.

Множество обозначается Х ={ х1,х2, …, хn, …}

Используются следующие обозначения:

1. хХ – элемент х принадлежит множеству Х.

2. хХ – элемент х не принадлежит множеству Х.

3. Квантр произвольности .

4. Квантр существования .

5. Квантр существования и единственности ! .

6. Следствие .

7. Эквивалентность .

Множество называется конечным, если число его элементов конечно.

Х ={ х1,х2, …, хn}

Число элементов в конечном множестве Х называется мощностью этого множества. |Х|

Пустое множество – множество, не содержащее ни одного элемента. Ø

Два множества называются равными, если они состоят из одних и тех же элементов, т.е. представляют собой одно и то же множество.

Операция равенства множеств обладает следующим им свойствами:

1) рефлексивность. X=X

2) симметричность.

3) транзитивность.

Множество Х является подмножеством мноества Y, если любой элемент множества Х принадлежит и множеству Y.

Операция отношения множества к подмножеству обладает следующими свойствами:

1) рефлексивность.

2) транзитивность.

3) пустое множество является подмножеством любого множества.

Счетное множество - такое множество А, все элементы которого могут быть занумированны в последовательность так, чтобы при этом каждый элемент полуил лишь один номер n и каждое натуральное число nбыло бы дано только одному элементу множества.

Множество, эквивалентное множеству натуральных чисел, является счетным множеством.

5. Операции над множествами.

Операции над множествами рассматриваются для получения новых множеств Объединением множеств А и В называется множество, состоящее из всех тех элементов, которые принадлежат хотя бы одному из множеств А, В (рис. 1):

 

Пересечением А и В называется множество, состоящее из всех тех и только тех элементов, которые принадлежат одновременно как множеству А, так и множеству В (рис. 2):

 

Разностью А и В называется множество всех тех и только тех элементов А, которые не содержатся в В (рис. 3):

 

Симметрической разностью  А и В называется множество элементов этих множеств, которые принадлежат либо только множеству А, либо только множеству В (рис. 4):

 

Абсолютным дополнением множества А называется множество всех тех элементов, которые не принадлежат множеству А (рис. 5):