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

Краткие теоретические сведения

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

Множество можно задать, перечислив все его элементы: А = { a, b, c, d }, B = {1, 2, 3, 4}, либо с указанием его характеристического свойства:

С = { x / 2< x < 9, х – целое}, т.е. C = {3, 4, 5, 6, 7, 8}.

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

Универсальным множеством называется множество U всех элементов, рассматриваемых в конкретном задании.

Множество А включается во множество В, если каждый элемент множества А является элементом множества В.

Обозначение: . Читается «А подмножество В».

Пример.

Даны множества А = {7, 8, 10, 12}, В = {7, 12}.

Тогда .

Диаграмма Эйлера – Венна применяется для наглядного изображения множеств и их взаимного расположения. Универсальное множество U изображается в виде прямоугольника, а произвольные множества, подмножества универсального – в виде кругов или овалов.

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

 

 

Пример.

Даны множества А = {7, 8, 10, 12}, В = {9, 10, 11, 12}.

Тогда = {7, 8, 9, 10, 11, 12}

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

Пример.

Даны множества А = {7, 8, 10, 12}, В = {9, 10, 11, 12}.

Тогда = {10, 12}.

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

 

 

Пример.

Даны множества А = {7, 8, 10, 12}, В = {9, 10, 11, 12}.

Тогда А \ В = {7, 8}

Дополнением множества А до универсального множества называется множество \ А.

 

 

Пример.

Даны множества А = {7, 8, 10, 12}, U = {6, 7, 8, 9, 10, 11, 12}.

Тогда \ А = {6, 9, 11}.

Булеаном В (Х) множества Х называется множество всех подмножеств множества Х.

Пример.

Дано множество Х = { а, b }.

Тогда В (Х) = {{ Ø }, { а }, { b }, { а, b }}.

Разбиением R (Х) множества Х называется система его непустых непересекающихся подмножеств, объединение которых есть множество Х.

			U
	X

 

R (Х) = {X₁, X₂, X₃, X₄}.

Пример.

Дано множество Х = { а, b, c }.

Тогда R (Х) = {{ а }, { b, c }} или R (Х) = {{ а, b }, { c }} или R (Х) = {{ а, с }, { b }}.

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

Отрицанием (инверсией) высказывания Х называется высказывание, истинное тогда и только тогда, когда Х ложно.

Обозначение: . Читается «не Х» или «неверно, что Х».

Конъюнкцией двух высказываний Х и Y называется высказывание, истинное тогда и только тогда, когда истинны оба высказывания Х и Y.

Обозначение: . Читается «Х и Y».

Дизъюнкцией двух высказываний Х и Y называется высказывание, ложное тогда и только тогда, когда ложны оба высказывания Х и Y.

Обозначение: . Читается «Х или Y».

Импликацией двух высказываний Х и Y называется высказывание, ложное тогда и только тогда, когда Х – истинно, а Y - ложно.

Обозначение: . Читается «Х влечёт Y», «если Х, то Y».

Эквиваленцией двух высказываний Х и Y называется высказывание, истинное тогда и только тогда, когда истинные значения Х и Y одинаковы.

Обозначение: ; Х ~ Y. Читается «Х тогда и только тогда, когда Y», «Х эквивалентно Y».

Таблица истинности

 

X	Y
И	И	Л	И	И	И	И
И	Л	Л	Л	И	Л	Л
Л	И	И	Л	И	И	Л
Л	Л	И	Л	Л	И	И

(логические операции записаны в порядке убывания приоритета)

 

Решение типовых заданий

1. Группа туристов из 50 человек пробыла в Санкт – Петербурге 6 дней. За это время БДТ посетили 28 человек, Мариинский театр – 25, театр комедии – 26. И в БДТ и в Мариинском театре побывало 14 человек, и в БДТ и в театре комедии – 12, и в Мариинском театре и в театре комедии – 12. Все три театра посетили 5 человек. Сколько туристов не были ни в одном театре? Решить задачу, используя диаграмму Эйлера-Венна.

Решение.

Даны три множества Д, М, К – зрителей БДТ, Мариинского театра и театра комедии соответственно. Универсальное множество U – множество туристов группы. Пусть - количество элементов множества Х.

Запишем краткое условие задачи:

Нужно найти . Перенесем все данные на диаграмму Эйлера-Венна.

 

 

	Д7
		7 К

 

 

Количество туристов, которые побывали хотя бы в одном театре, равно

.

Количество туристов, не побывавших ни в одном театре, равно

.

Следовательно, не были ни в одном театре 4 туриста.

 

2. Задано универсальное множество U = {1,3,4, 5,6,7,8} и множества X = {1,3,5,7}, Y = {3,5,7,8}, Z = {1,4,7,8}. Построить булеан множества Z и любое разбиение множества X. Выполнить действия

Решение.

Построим булеан множества Z. Так как булеаном множества Х является множество всех его подмножеств, то в булеан включаем пустое множество, все одноэлементные подмножества, все двухэлементные подмножества, все трехэлементные подмножества множества Х и само множество Х:

{ Ø, {1}, {4}, {7}, {8}, {1,4}, {1,7}, {1,8}, {4,7}, {4,8}, {7,8}, {1,4,7}, {1,4,8}, {1,7,8}, {4,7,8}, {1,4,7,8}.

Для множества Х построим разбиение, состоящее из трех блоков, , например,

Определение разбиения выполняется: множества не пусты, не пересекаются ( =Ø, = Ø, Ø), их объединение равно множеству Х:

.

Таким образом, разбиение множества X: .

Выполним операции над множествами в следующем порядке:

{1,3,5,7} \ {3,5,7,8} = {1} (по определению операции разности множеств);

U \ Z = {1,3,4, 5,6,7,8} \ {1,4,7,8} = {3, 5,6} (по определению операции дополнения);

={1} {3, 5,6} = (по определению операции объединения множеств).

Следовательно, = .

 

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

.

Решение.

Для построения таблицы истинности для формулы воспользуемся таблицей истинности

X	Y
И	И	Л	И	И	И	И
И	Л	Л	Л	И	Л	Л
Л	И	И	Л	И	И	Л
Л	Л	И	Л	Л	И	И

(логические операции записаны в порядке убывания приоритета)

Учитывая приоритет логических операций, определим порядок действий:

 

А	В
И	И	Л	И	И	И	И	И
И	Л	Л	Л	И	И	Л	Л
Л	И	И	И	Л	Л	Л	И
Л	Л	И	И	И	И	Л	Л