Основные свойства операций над множествами

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

Элементы математической логики

Высказывания

Одним из исходных понятий математической логики является высказывание. Под высказыванием понимается повествовательное предложение, для которого имеет смысл понятие истинности, то есть которое является либо истинным, либо ложным (соответствующие значения обозначаются И и Л).

Примеры: «Волга впадает в Каспийское море», «2+2=4», «3∙5<20».

Не является высказыванием предложение «x>2», так как его истинностное значение зависит от того, какое значение принимает переменная x (это предикат).

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

- отрицание, обозначается . Высказывание  читается «неверно, что A»;

- конъюнкция, обозначается & или . Высказывание читается «A и B»;

- дизъюнкция, обозначается . Высказывание читается «A или B»;

- импликация, обозначается . Высказывание читается «A влечёт B» или «если A, то B»;

- эквиваленция, обозначается . Высказывание читается «A эквивалентно B».

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

Для логических операций определены таблицы истинности:

A	B
И	И	И	И	И	И	Л
И	Л	Л	И	Л	Л	Л
Л	И	Л	И	И	Л	И
Л	Л	Л	Л	И	И	И

 

Приведённые истинностные значения позволяют построить таблицу истинности для любой формулы.

Пример 1. Построить таблицу истинности для формулы .

a	b	c
И	И	И	Л	Л	Л	Л	И
И	И	Л	Л	Л	Л	Л	И
И	Л	И	Л	Л	Л	Л	И
И	Л	Л	И	Л	Л	И	Л
Л	И	И	И	И	И	И	И
Л	И	Л	И	И	И	И	И
Л	Л	И	И	Л	И	Л	И
Л	Л	Л	И	Л	И	И	Л

Пример 2. Построить таблицу истинности для формулы .

Определение. Формула называется тавтологией, если она принимает значение И при любом наборе истинностных значений входящих в неё элементарных высказываний.

Определение. Формулы A и B называются равносильными ( ), если они принимают одинаковые истинностные значения при любом наборе истинностных значений входящих в них элементарных высказываний.

Теорема 1. Формула является тавтологией тогда и только тогда, когда имеет место равносильность .

Доказательство:

Если , то истинностные значения формул A и B одинаковы при любом наборе истинностных значений входящих в них элементарных высказываний. Тогда формула  всегда принимает значение И, то есть является тавтологией. Аналогично доказывается обратное.

Определение. Формула B называется логическим следствием формул  ( ), если при любом наборе истинностных значений входящих в эти формулы элементарных высказываний, при которых все формулы  истинны, формула B также истинна. Формулы  при этом называются посылками, формула B – заключением логического следствия .

Пример 3. Доказать логическое следствие .

 

a	b	c
И	И	И	И	И	И
И	И	Л	И	Л
И	Л	И	Л	И
И	Л	Л	Л	И
Л	И	И	И	И	И
Л	И	Л	И	Л
Л	Л	И	И	И	И
Л	Л	Л	И	И	И

Логическое следствие можно доказывать методом от противного.

Пример 4. Доказать логическое следствие методом от противного.

Теорема 2. Логическое следствие  имеет место тогда и только тогда, когда формула  является тавтологией.

Тавтологии, логические равносильности, логические следствия называются законами логики.

Теорема 3. Имеют место следующие законы логики:

а) ;                            b) ;

c) ;                          d) ;

e) ;           f) ;

g) ;                    h)  (закон исключенного третьего);

i) ;   j) ;         k) ;     l) ;

m)    (закон контрапозиции);

n) ;        o)  (правило заключения);

o)  (закон силлогизма).

 

Предикаты и кванторы

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

Примеры: ,

Предикат называется n -местным, если он зависит от n переменных. Если значения придать всем переменным, то получится 0-местный предикат, - это высказывание. Над предикатами определены те же логические операции, что и над высказываниями. С их помощью можно строить новые предикаты.

Над предикатами определены операции навешивания кванторов. Рассматриваются два вида кванторов: квантор всеобщности и квантор существования . В формулах  и  подформула называется областью действия соответствующего квантора. Вхождения переменных в область действия квантора с той же переменной называются связанными; они связываются соответствующим квантором. Вхождения переменных, не являющихся связанными, называются свободными. Когда переменным в формуле придают определённые значения, эти значения принимают только свободные вхождения переменных.

Множества и отношения

Множества

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

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

Множество B называется подмножеством множества A, если каждый элемент множества B принадлежит множеству A.

Объединением множеств A и B называется множество, состоящее из элементов, принадлежащих хотя бы одному из множеств A или B.

Пересечением множеств A и B называется множество, состоящее из элементов, принадлежащих одновременно и множеству A, и  множеству B.

Разностью множеств A и B называется множество, состоящее из элементов, принадлежащих множеству A, и  не принадлежащих множеству B.

Дополнение множества A –то множество , состоящее из элементов универсального множества U, не принадлежащих множеству A.

Пример. Доказать равенство множеств  с помощью диаграмм.

Основные свойства операций над множествами

(учебник, стр.16)

 

Индукция и комбинаторика

---

Дата добавления: 2021-02-10; просмотров: 75; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!