Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Инфоурок / Математика / Другие методич. материалы / Методические рекомендации по выполнению практических работ по дисциплине "Элементы математической логики"

Методические рекомендации по выполнению практических работ по дисциплине "Элементы математической логики"

  • Математика

Поделитесь материалом с коллегами:

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ


БРАТСКИЙ ЦЕЛЛЮЛОЗНО-БУМАЖНЫЙ КОЛЛЕДЖ

ФЕДЕРАЛЬНОГО ГОСУДАРСТВЕННОГО БЮДЖЕТНОГО

ОБРАЗОВАТЕЛЬНОГО УЧРЕЖДЕНИЯ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«БРАТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»






Специальности 230401 «Информационные системы» (по отраслям),

230115 «Программирование в компьютерных системах»







МЕТОДИЧЕСКИЕ УКАЗАНИЯ

К ПРАКТИЧЕСКИМ РАБОТАМ



по дисциплине «Элементы математической логики»























Братск 2015



Составила (разработала)

Шевчук И.Н., преподаватель кафедры физико-математических и социально-гуманитарных дисциплин











Рассмотрено на заседании кафедры физико-математических и социально-гуманитарных дисциплин

«___________________20___г. _______________________

(Подпись зав. кафедрой)











Одобрено и утверждено редакционно-издательским советом



___________________

(Подпись председателя РС)





«____» ________________20___г. № _______________________







Содержание

Введение…………………………………………………………………………...5

1 Основы теории множеств…………………………….. ……………………….6

1.1 Общие понятия теории множеств. Операции над множествами……….6

1.2 Соответствия между множествами. Отображения………………………9

1.3 Мощность множества. Кортежи. Декартовы произведения…………...12

1.4 Отношения. Бинарные отношения и их свойства………………………13

1.5 Подстановки……………………………………………………………….16

1.6 Сравнения. Классы сравнений по модулю N. Решение сравнений……18

1.7 Упражнения……………………………………………………………….20

2 Понятия…………………………………………………………………………23

2.1 Понятия как форма мышления. ……………………………………….....23

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

2.3 Отношения между понятиями……………………………………………29

2.4 Определение понятий. Операции над понятиями………………………31

2.5 Деление понятий. Классификация……………………………………….35

2.6 Упражнения………………………………………………………………..38

3 Математическая логика……………………………………………………….42

3.1 Понятие высказывания. Основные логические операции……………...42

3.2 Формулы алгебры логики………………………………………………...47

3.3 Булевы функции…………………………………………………………..50

3.3.1 Нормальные формы…………………………………………………….50

3.3.2 СДНФ и СКНФ…………………………………………………………51

3.3.3Минимизация нормальных форм………………………………………52

3.4 Полнота функций…………………………………………………………55

4 Предикаты……………………………………………………………………...60

4.1 Логика предикатов………………………………………………………60

4.2 Построение отрицаний к предикатам…………………………………63

4.3 Упражнения……………………………………………………………..64

Заключение ………………………………………………………………………65

Список использованных источников…………………………………………..66

Приложение А……………………………………………………………………67

















































Введение

Данное методическое пособие содержит лекционный материал курса «Элементы математической логики» для студентов второго курса очного и заочного факультетов, а также подробно разобранные примеры и упражнения для самостоятельной работы.

В пособии особое внимание уделяется практическим задачам таких разделов как «Множества», «Понятия», «Математическая логика» и «Предикаты».

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







































1 Основы теории множеств



1.1 Общие понятия теории множеств. Операции над множествами



Совокупность элементов, объединенных некоторым признаком, свойством, составляет понятие множество. Например, множество книг в библиотеке, множество студентов в группе, множество натуральных чисел N и т.д.

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

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

Если такого номера для каждого элемента не существует, то такое множество называется бесконечным.

Бесконечное множество часто называют континуумом (например: совокупность точек на плоскости).

Если можно пересчитать все число элементов в счетном множестве, то эта сумма называется мощностью множества.

Множества задаются различными способами:

  1. С помощью перечисления всех его элементов.

{0,1,2,3,4,5,6,7,8,9}

  1. Алгоритмическая форма (в виде последовательности или фомул).

а) конечное

М={2;4;6;8} <=> М={m|2n;n-целое;1<=n<=4}

б) бесконечное

А={х| |х-1|<3}

Свойства счетных множеств

  1. Всякое подмножество счетного множества конечно или счетно

Подмножеством множества А называется множество А` все элементы которого принадлежат множеству А

Пример:

  1. Сумма конечного или счетного числа конечных или счетных множеств есть конечное или счетное множество.

  2. Множество всех рациональных чисел счетно.

  3. Алфавитом называется любое непустое множество.

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

Элементы множества под названием АЛФАВИТ называют буквами (символами).

Символом в данном алфавите любая конечная последовательность букв.

Для каждого множества А существуют множества, элементами которого являются только все его подмножества.

Такое подмножество называют семейством множеств А или булеаном. (обозначается В(А))

Будем называть вектором (кортежем) упорядоченный набор элементов и обозначать его , заметим, что в отличие от множества, элементы в векторе могут повторяться. Эти элементы называются координатами или проекциями.

Количество элементов в векторе называется его длиной, если в векторе 2 элемента, то двойка, если n элементов, то n-ка.

Теория множеств строится на основе систем аксиом.

  1. Аксиома существования: Существует по крайней мере одно множество.

  2. Аксиома объемности: Если множества А и В составлены из одних и тех же элементов, то они совпадают.

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

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

  5. Аксиома существования пустого множества: Существует множество не содержащее ни одного элемента.


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



  1. Включение (объединение)

Множество А входит (включено) в множество В, или А является подмножеством В.

Если всякий объект, обладающий свойством , также обладает свойством , то говорят, что свойство включает свойство , т.е.

  1. Сумма

Сумма множеств А и В есть множество С, включающее в себя все элементы множество А и В.

Объект входит во множество если он входит во множество А или во множество В.



  1. Пересечение (произведение)

Пересечением множество А и В называется новое множество С. Элементы множества С принадлежат множеству А (обладают его свойствами) и множеству В (обладают его свойствами).



  1. Вычитание (разность)

Разность множеств А и В есть множество С, элементы которого обладают свойствами множества А и не обладают свойствами множества В или принадлежат множеству А и не принадлежат множеству В.



  1. Дополнение

Если имеется некоторое универсальное множество (универсум) U и все рассматриваемые множества есть его подмножества, то дополнением называется такое множество, элементы которого не входят в А, но принадлежат U.

Графическое представление множеств

(Диаграммы Эйлера - Венна)



Рисунок 1 -



Рисунок 2 -





Рисунок 3 -







Рисунок 4 -





1.2 Соответствие между множествами. Отображения



Пусть даны два множества А={а1, а2, ...} и В={b1,b2,...}. Тогда пары (ai,bj) задают соответствие между множествами А и В, если указано правило R, по которому для элемента ai, множества А выбирается элемент bj из множества В. Например, соответствие между элементами множеств х R и у R задает точечное множество (xi; уj,) координат точек на плоскости.



hello_html_m1b933633.png

Рисунок 5 – Иллюстрация соответствия R – «вершина параболы»



hello_html_m213f7e53.png

Рисунок 6 – Задание отображения xRy с помощью метода координат

Пусть задано соответствие R между множествами А и В, т. е. R: (a; b), a A, b В. Для некоторого элемента а множества А поставлен в соответствие некоторый элемент b из множества В, который называется образом элемента а и записывается b = R(a). Тогда а = R-1(b)прообраз элемента b В, который обладает свойствами единственности и полноты:

каждому прообразу соответствует единственный образ;

образ должен быть полным, так же как полным должен быть и прообраз.

Например, если А — множество парабол, В — множество точек плоскости, a R — соответствие «вершина параболы», то R(a) — точка, являющаяся вершиной параболы a, a R-1(b) состоит из всех парабол аi с вершиной в точке b (рисунок 5).

Образ множества А при соответствии R называется множеством значений этого соответствия и обозначается R(A), если R(A) состоит из образов всех элементов множества А. Запись: R(A) = = {b|a A, b = R(a)}.

Прообраз множества В при некотором соответствии R называют областью определения этого соответствия и обозначают R-1(B), т.е. R-1(B) = {a|b В, а A: R(a) = b}; R-1 является обратным соответствием для R.

Так, для соответствия R, заданного точками координатной плоскости, областью определения является множество точек оси абсцисс, а множеством значений — проекции точек на ось ординат (рис. 6). Поэтому для некоторой точки М(х; у) у является образом, а х — прообразом при некотором соответствии R: Y= R(X), Х= R-1(Y). Соответствие между множествами X, YR удобно представить в виде точки на плоскости с помощью метода декартовых координат.

Пусть задано соответствие R и Y= R(X). Ему соответствует точка M с координатами (х; у) (рисунок 6). Тогда множество точек плоскости, выделяемое отображением R, будет графиком.

Задание отображений. Для описания соответствий между множествами используют понятие отображения (функции) одного множества на другое.

Для задания отображения необходимо указать:

множество, которое отображается (область определения данного отображения, часто обозначается D(f));

множество, в (на) которое отображается данная область определения (множество значений этого отображения, часто обозначается E(f));

закон или соответствие между этими множествами, по которому для элементов первого множества (прообразов, аргументов) выбраны элементы (образы) из второго множества. Приняты записи f: A В.

Везде при записи f: A В будем подразумевать, что отображение f определено всюду на А, т.е. А — полный прообраз отображения f, хотя для В такого свойства полноты подразумевать не будем. Запись f(A) означает, что это множество состоит из образов всех элементов множества A:f(A) = {f(a)|a А}. Очевидно, что f(A) В.

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

Для задания отображения множеств табличным способом принято строить таблицу, в которой первую строку составляют элементы области определения (прообразы вида а), а вторую строку—их образы, т. е. элементы вида у(х) при отображении у: а у (а), где а А (табл. 1). Такой способ удобен при достаточно малой мощности прообраза (не более 10). Но все же иногда такой способ задания функции является единственно возможным. Например, публикация в газете многотысячной армии победителей лотереи: аргументом является лотерейный номер, образом — приз.

Графическое представление отображения связано со стрелочными схемами (диаграммами или графами). На рисунке 7 показан пример графического задания отображения множества А = {а123 } в В = {b1,b2,b3,b4,b5}.

Таблица 1 – Табличное задание отображения

hello_html_m6ebf7ea.png



hello_html_76f7b33f.png

Рисунок 7 – Графическое задание инъективного отображения множества А в В



1.3 Мощность множества. Кортежи. Декартовы произведения



Основной характеристикой множеств является количество элементов, содержащихся в этом множестве.

Как известно, число элементов множества М называется его мощностью и обозначается |М|. Множества А и В называются эквивалентными, или равномощными, А ~ В, если между их элементами можно установить взаимно-однозначное соответствие (биекцию). Тогда | A| = |В|.

Если они конечны, то сравнивают их мощности, т.е. количество элементов этих множеств. Обозначим через А, В, С, D соответственно множества букв слов «крот», «корт», «кран» и «рот». Тогда |А| = |В| = |С| = 4, |D| = 3. Отсюда делаем вывод, что А, В и С имеют равные мощности, а мощность D меньше, чем, например, мощность A: |D| < |А|, так как 3 < 4. Множества А, В и С равномощны. Понятие «равномощные множества» не означает, что они обязательно равны. Например, среди перечисленных равномощных множеств А, В и С множества А и В равны, так как они состоят из одних и тех же элементов, а множества А и С различны. Говорят, что такие равномощные, но не равные множества эквивалентны между cобой.

Кортежи

В повседневной жизни и математике нам часто приходится иметь дело с упорядоченными множествами — кортежами. Слово кортеж переводится с французского cortege как торжественная процессия (например, свадебный кортеж). Треугольник АВС на плоскости задается кортежем из 6 чисел <х1, у1, х2, у2, x3, y3 > где А(х11), В(х2; у2), С(х3; у3) — координаты вершин. Слова в предложении, буквы в слове, предложения в тексте — все это примеры кортежей. Двоичный код является кортежем, состоящим из цифр 0 и 1.

Пусть А — конечное множество, состоящее из n элементов, f: А {1, 2, ..., n} — функция, задающая порядок на А, т.е. правило, по которому каждому элементу множества А ставится в соответствие натуральное число от 1 до n, причем одному числу из {1, 2, ..., n} соответствует один элемент из А.

Пару <A, f> назовем упорядоченным множеством, или перестановкой, из n элементов. Кортежем длины n из элементов множества А (или n-кой) называется упорядоченная последовательность <а1, а2, ..., аn> элементов этого множества, причем на первом месте стоит прообраз единицы: a1=f-1(1), a2=f-1(2), …, an=f-1(n), akA, k n.

Кортежи <а1, а2, ..., аk> и <b1, b2, ..., bn> называются равными, если они имеют одинаковую длину и их элементы с одинаковыми номерами совпадают, т.е. <а1, а2, ..., аk> и <b1, b2, ..., bn> , если (к = n) и для i ai=bi.

Например, равны кортежи <21, 22, 23, 24, 25> =<2, 4, 8, 16, 32>, так как оба кортежа длины 5 и равны все пары соответствующих элементов данных множеств, 21 =2, 22=4, 23=8, 24=16, 25=32.

Декартово произведение. Пусть заданы множества А1, А2, ..., Аn. Декартовым (прямым) произведением этих множеств называется множество А1× А2× ...× Аn , состоящее из всех кортежей <а12, ..., аn> длины к, в которых аk Аk, где 1 к <n. Поскольку для задания кортежа важен порядок, то порядок множителей важен и в декартовом произведении.

Например, декартовым произведением множеств А = {0,1} и В = {X, Y, Z} будет являться множество пар А × В = <(0; X), (0; Y), (0; Z), (1; X), (1; Y), (1; Z)>. Скобки для указания пар опускают там, где это не может привести к затруднениям: А × В = <0Х, 0У, 0Z, IX, 1Y, 1Z>.

Если А1 = А22=... = Аn = А, то пишут Аn = А×А×...×А и называют n декартовой степенью множества А.





1.4 Отношения. Бинарные отношения и их свойства

Квадратом множества А называется декартово произведение множества само на себя

Бинарным отношением Т в множестве А будем называть подмножество его квадрата


  1. Отношение выполняется для пар (6,8) (6,6)

  2. Отношение имеет общий делитель не равный 1. Выполняется для пар (6,4) (4,2) (8,8) но не выполняется для пар (5,4) (3,8)

  3. Любые элементы декартова произведения находятся в бинарном отношении, если , говорят, что связаны отношением Т.

  4. Областью значений (изменением бинарного отношения) называется множество , подчиненное условию


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










Рисунок 8 – График бинарного отношения














Рисунок 9 – График бинарного отношения


Бинарные отношения на плоскости можно отобразить с помощью графов. Элементы множества обозначаются вершинами графов. Если пара , то вершины а и в соединяются звеном.

Например:

(ав)(вс)(ас)(аа)







Рисунок 10 – Бинарное отношение, изображенное в виде графа


Отношения эквивалентности. Определим некоторые важные свойства бинарных отношений и рассмотрим бинарные отношения, которые обладают тремя из этих свойств и часто встречаются в математике. Такое бинарное отношение называется эквивалентностью.



СВОЙСТВА:

  1. 1.1 Пусть - бинарное отношение, - область его задания, тогда называется рефлексивным, если , граф таких отношений имеет вид петли при каждой вершине







Рисунок 11 – Петля при каждой вершине


1.2 называется антирефлексивным, если


2. 2.1 Отношение может быть симметричным, если

(изображается любым графом)

2.2 Антисимметричным, если (изображается ориентированным графом)


3. 3.1 Транзитивным. Отношение называется транзитивным, если (изображается транзитивным графом – все вершины пересекаются)

Если для бинарного отношения соблюдается три условия: рефлексивность, симметричность и транзитивность, то такое отношение называется эквивалентностью.







1.5 Подстановки



Определение подстановки

Рассмотрим множество Х=. Взаимно однозначное отображение φ множества Х на себя называется подстановкой. Подстановку φ удобно задавать в виде φ, где в 1-й строке указаны элементы множества Х в порядке возрастания номеров, а во 2-й строке – образы этих элементов под действием φ.

Пример 1.

Подстановка φдействует на множестве Х= следующим образом:

Произведение подстановок

Подстановки π и φ можно перемножать в соответствии с общим правилом композиции (π φ)(i))=π(φ(i)).

Пусть π= и φ= . Тогда произведение πφ= .

С помощью перестановки столбцов нужно добиться, чтобы 1-я строка в 1-й подстановке совпала со 2-й строкой 2-й подстановки:

. Тогда результатом перемножения подстановок π и φ будет .

Пример 2. Даны подстановки π= и φ=. Определим произведение πφ и φπ.

Произведение πφ= (переставили столбцы в 1-й подстановке) =.

Произведение φπ = (переставили столбцы в 1-й подстановке) =.

Мы видим, что πφ φπ, то есть результат произведения подстановок зависит от порядка множителей.

Обратная подстановка

Обозначим тождественную подстановку , которая оставляет все элементы множества Х=на месте, через е. Для каждой подстановки φ= можно указать такую обратную подстановкуφе. Для этого в подстановке φ надо поменять местами строки:. После этого перестановкой столбцов нужно упорядочить элементы в 1-й строке.

Пример 3. Определим обратную подстановку для подстановки φ=.

Обратная подстановка равна (поменяли местами строки подстановки φ)=.

Действительно, φ

и φ

Циклы

Подстановка вида i1i2, i2i3, i3i4,…,im-1im, imi1 (при этом все числа i1, i2, …,im различны) называется циклом длины m. Для циклов вводят специальное обозначение: .

Пример 4. Определим, как действует цикл (2 3 4 1).

Цикл (2 3 4 1) действует следующим образом: 23412.

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

Теорема. Каждую подстановку можно разложить в произведение независимых циклов. Это разложение единственно с точностью до порядка цикла.

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

Пример 5. Разложим подстановку в произведение независимых циклов.

Так как 1351, то получаем цикл (135). Цепочка 242 дает танспозицию (24). Так как 686, то получаем транспозицию (68). Элемент 7 остается на месте (7).

Тогда = (135) (24) (68) (7).

Знак подстановки

Элементы i и j (i1,i2,…,in) образую инверсию, если j>i и элемент j расположен левее элемента i.

Пример 6. Определим число инверсий в строке (53412).

Число 5 образует 4 инверсии (3,4,1,2). Число 4 образует 2 инверсии (1,2). Число 3 образует 2 инверсии (1,2). Тогда общее число инверсий в строке (53412) равно 4+2+2=8.

Знак подстановкиравен (-1)а, где а – число инверсий в строке.

Четные подстановки – это подстановки со знаком 1. Знак нечетных подстановок равен -1.

Пример 7. Определим знак подстановки из примера 6 .

Число инверсий в строке (34521876) равно а=2 (для 3)+2 (для 4)+2 (для 5)+1 (для 2)+0 (для 1)+2 (для 8)+1 (для 7) = 2+2+2+1+0+2+1=10.

Так как (-1)а = (-1)10 =1, то подстановка является четной подстановкой.





1.6 Сравнения. Классы вычетов по модулю N. Решение сравнений

Пусть п – положительное целое число. Говорят, что целые числа а и b сравнимы по модулю n (ab (mod n)), если разность a-b делится на n.

Пример 8. Покажем, что числа 27 и 2 сравнимы по модулю 5.

Так как 27 – 2 = 25 делится на 5, то 27 2 (mod 5).

Сравнение чисел по модулю п является отношением эквивалентности на множестве целых чисел. Поэтому множество целых чисел распадается на классы эквивалентности по модулю п. Множество таких классов обозначается Zn и называется множеством классов вычетов по модулю п.

Пример 9. Множество Z2 состоит из двух классов: попадают все четные числа. А класс содержит все нечетные числа.

Решение сравнений

Очень часто необходимо уметь находить решения сравнения axc(mod m).

Теорема. Если с делится на НОД (a,m), то сравнение axc(mod m) имеет конечное число решений по модулю m.

Эти решения задаются формулой , где =1,2,…,НОД , а для x0 существует такой y0, что (x0,y0) является решением уравнения

Пример 10. Найдем решение сравнения 4x≡6 (mod 18).

Здесь a = 4, c = 6, m =18.Так как с = 6 делится на НОД=НОД(4,18) = 2, то сравнение 4x≡6 (mod 18) имеет решение.

Число таких решений совпадает с НОД= НОД(4,18)=2, то есть имеется два решения.

Подберем решение уравнения. В уравнении 4х+18у=6 обе части уравнения можно сократить на 2. Тогда 2х+9у=3.

Так как нас устроит любое решение уравнения, то положим у=-1. Тогда 2х+9(-1)=3. Отсюда х0=6. Решения сравнения 6(mod 18) задаются формулой

При t=1получаем одно решение 6+9×1(mod 18) = 15(mod 18). При т=2 получаем другое решение 6+9×2 (mod 18) =6+18 (mod 18)6(mod 18).





1.7 Упражнения



1. Укажите множество действительных чисел, соответствующее записи:

а) А = {х|3х - 2 > 0}; в) Х= {х|-3 х < 9, х Z}; б) В = {x|x2 + х + 1 > 0}; г) М= {х|5 х 6, х N}; д) С={х|х2-5х+6 = 0}; е) У={х|х2-Зх-40}.

2. Опишите множество М точек плоскости, заданных характеристическим свойством:

а) Х={М||АМ| <4}

б) А = {М||МО| 5}

в) B={M||MK| = |MQ|};

г) Y= {М||АМ| = |ВМ| = |СМ|};

д) С={M||MK| + |МL|<6};

е) Z= {М||MQ| = |МР| = 3}.

3. Приведите по три примера конечных и бесконечных множеств.

4. Задайте характеристическим свойством множество:

а) всех параллелограммов;

б) всех прямоугольников;

в) всех квадратов;

г) всех равнобедренных треугольников;

д) всех ромбов;

е) всех прямоугольных треугольников.

5. Составьте различные новые слова из букв слова:

а) апельсин; б) норматив; в) стационар; г) ромашка; д) множества;

е) ратификация.

1. Представьте буквы новых слов в виде множеств и найдите мощность множеств, состоящих из кортежей длины n, где n > 5.

2. Какое слово, полученное из букв данного, имеет наибольшую длину?

6. На множестве U всех букв русского алфавита заданы множества А, В, С: А = {ё, к, л, м, н}; В = {к, о, з, ё, л}; С = {б, ы, ч, о, к}. Найдите следующие множества и изобразите их кругами Эйлера:

а) АВ; б) АВ; в) (АВ)С; г) ( AC)B; д) D = U\(ABC);

е) D= U\(АВС).

7. Докажите, используя определения и круги Эйлера:

а) АВ) = А; б) АВ) = А.

8. Даны отрезки А = [-4; 5], В = (2; 6], С = (5; 10]. Найдите следующие множества и изобразите их кругами Эйлера:

а) (AB)UC; б) (A В) U С; в) АВ; г) (A U В)\(А В);

д) (CВ)\(АВ); е) (A С)\(A B).

9. Определите мощность множества:

а) {{а}, а}; б) {0};

в) состоящего из букв слова «математика»;

г) состоящего из букв слова «перпендикулярные»;

д) состоящего из цифр числа 635252;

е) состоящего из цифр числа 1010111.

10. Найдите среди элементов множества В элементы, соответствующие элементам множества А, и укажите правило, по которому установлено это соответствие:

А = {спаниель, ромашка, минотавр, тарификация, карета, жеманство, соратница, коршун, весна};

В = {множества, ракета, стационар, шнурок, мошкара, норматив, ратификация, апельсин, навес}.

11. Выполните действия и определите мощность полученного

множества:

а) A = {5, 7, 9}{12, 15}, В = {5, 7, 9}{12, 15};

б) А = {5, 7, 9}{5, 57, 59}, В = {5, 7, 9}{5, 57, 59};

в) А = {х|х — звонкий согласный звук}, В = {х|х — глухой

согласный звук}, AB =? ;AB = ?;

г) {1, 2, 3}\{2, 3}; д) {1, 2, 3}\{4, 5}; е) {х2 + y2 1}\{x2 + y2 = 1}.

12. Даны множества А = {1, 2, 3}, B = {х, у, z}, С- { ; }.

Запишите декартовы произведения множеств:

а) А×В; б) В×А\ в) B× С; г) С×В; д) A × С; е) С×А

13. Объясните, будут ли выполнимы свойства отношений на заданном множестве людей и почему:

а) «быть знакомым»; б) «быть отцом»; в) «поздравлять с праздником»; г) «встречаться»; д) «быть другом»; е) «быть ровесником».





































2 Понятия



2.1 Понятия как форма мышления



Логика как наука возникла в трудах выдающегося древнегреческого мыслителя Аристотеля (384—322 до н.э.). Традиционная аристотелева логика называется классической или формальной и соответствует первому периоду развития этой науки. Она создана как орудие или метод исследования формальной правильности рассуждений в зависимости от логических операций, производимых в процессе мышления. Объектами изучения такой логики являются различные формы мышления - понятия, суждения, умозаключения, их виды и операции над ними, законы логики, доказательства и опровержения, гипотезы и т.д. Наряду с Аристотелем, тщательно разработавшим теорию дедуктивных умозаключений и доказательств, в классическую логику входит индуктивная логика, родоначальником которой является крупнейший английский философ и естествоиспытатель Фрэнсис Бэкон (1561 — 1626). Значительный вклад в развитие классической логики внес также великий французский философ и математик Рене Декарт (1596—1650).

Второй период развития логики как науки связан с работами знаменитого немецкого философа и математика Готфрида Вильгельма Лейбница (1646—1716), целью которого было создание «азбуки понятий» и применение логики для теоретического обоснования математики. С другой стороны, у Лейбница возникла идея придать рассуждениям вид вычислений. Для этого он хотел поставить символы в соответствие понятиям и получить верные выводы в рассуждениях с помощью некоторых алгебраических операций. Стремясь облегчить процесс мышления, он старался смотреть на классическую логику через призму математики.

Мечты Лейбница частично удалось воплотить в жизнь ирландскому математику и логику Джорджу Булю (1815 — 1864), который создал алгебру логики. В этой науке свои операции и законы похожи на привычные математические. В этом разделе математики, получившем название булева алгебра, буквами обозначают высказывания как элементы множества высказываний. С помощью логических операций из простых элементарных высказываний строят составные, определяют, истинны они или ложны, т.е. определяют их семантическую характеристику. Алгебра Буля — часть математической логики, в состав которой входят логика высказываний и логика предикатов. Математическая логика в отличие от традиционной изучает логические связи и отношения, лежащие в основе достоверных логических выводов. В математической логике для получения достоверных выводов выявляется их структура, и на этой основе строятся логические исчисления. Второй период развития логики связан с использованием различных математических символов, поэтому его называют символическим.

Наиболее характерной особенностью современного третьего периода развития логики является применение новых методов для исследования как традиционных, так и вновь выявленных логических проблем, связанных с появлением ЭВМ и информатизацией общества.

Кроме перечисленных, существует еще и диалектическая логика, отличающаяся от формальной своим специфическим подходом к мышлению. У ее истоков стояли немецкие философы Иммануил Кант 1724— 1804) и Георг Гегель (1770—1831). Особенностью диалектической логики является учет противоречивости мышления, основанный на законах диалектики.

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

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

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

В связи с тем, что понятия естественного языка многозначны, часто приходится уточнять их определения в информации разного вида. Так, «квадрат» может быть и геометрической фигурой (прямоугольником с равными сторонами), и второй степенью числа или алгебраического выражения. Например, плоскость R2 = R × R — декартово произведение двух прямых, а сам квадрат (фигура) — это квадрат (декартов) двух отрезков: [0, а] х [0, а].

Итак, понятие — это форма мышления, отражающая предметы в их существенных общих признаках. Каждый из признаков необходим для описания некоторого понятия, а все вместе они достаточны для того, чтобы с их помощью отличить данное понятие от других из общего множества однородных объектов.

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

Логические приемы формирования понятий. Для формирования понятий используются следующие мысленные логические приемы.

Анализ — мысленное расчленение объектов (явлений, процессов) на их составные части, выделение в них признаков.

Синтез — соединение частей или признаков в единое целое.

Сравнение — установление сходства или различия объектов по существенным или несущественным признакам.

Абстрагирование — выделение одних признаков и отвлечение от других (чаще всего — выделение существенных и отказ от несущественных признаков).

Обобщение — объединение однородных объектов в класс.

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

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

Логические характеристики понятий. Любое понятие имеет логическую структуру, включающую в себя объем и содержание — основные логические характеристики понятия.

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

Объем понятия есть множество всех предметов, которые мыслятся в данном понятии. Объем понятия «столицы государств» определяется перечислением всех столиц: Москва, Париж, Лондон, Пекин и т.д. Объем понятия «стороны горизонта» составляют восток, запад, север и юг.

Для краткой лаконичной записи взаимоотношений, взаимосвязей между различными понятиями будем использовать язык теории множеств и теории графов.

Пусть объем одного понятия входит в объем другого. Из двух понятий А и В назовем родовым понятием то из них (А), для которого объем больше, а видовым то (В), объем которого меньше: В А (рисунок 12, а).

hello_html_e4a4c6e.png

Рисунок 12 – Закон обратного отношения между объемом и содержанием понятия: а – соотношения между родовыми и видовыми понятиями; б - КИ

Закон обратного отношения между объемом и содержанием понятий. Взаимосвязь между логическими характеристиками понятия, его объемом и содержанием, выражает закон обратного отношения. Чем шире объем понятия, тем уже его содержание, и, наоборот, чем шире содержание, тем уже объем. Это значит, что чем меньше информации о предмете, заключенном в понятии, тем шире класс предметов, соответствующих этому понятию. Например, «игры» (И) — понятие более широкое, чем «компьютерные игры» (К). Поэтому объем понятия И шире, чем объем понятия К: К с И (рисунок 12, б).





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



В наших рассуждениях вообще, при изучении точных наук в частности, велика роль ограничений и обобщений понятий.

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

Все множество имеет больший объем, чем его подмножество, и, следовательно, его характеризует мало признаков (рассуждения вообще). Для его подмножества ограничивается объем, а значит, согласно закону обратного отношения между объемом и содержанием увеличивается количество признаков (рассуждений, связанных с изучением точных наук).

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

Эти взаимно-обратные переходы будем иллюстрировать кругами Эйлера. При этом все множество является родовым понятием, а его подмножество — видовым (рисунок 13).

hello_html_m5a7e7aea.png

Рисунок 13 – Схема взаимно-обратных переходов ограничения и обобщения понятий

hello_html_m308ad82b.png

Рисунок 14 - Схема взаимно-обратных переходов ограничения и обобщения

Тогда операция обобщения, заключающаяся в переходе от видового к родовому понятию, сопровождается отказом от отдельных существенных признаков понятия. Так, если общее понятие — наука (все множество различных наук), то одно из ее подмножеств — математика. В свою очередь математика разделяется на отдельные предметные области, одной из которых является геометрия — наука, изучающая пространственные фигуры и отношения между ними. Та часть геометрии, которая изучает фигуры и их отношения на плоскости, называется планиметрией. Совершим с перечисленными понятиями логические операции обобщения и ограничения и изобразим их с помощью кругов Эйлера. Как известно, ограничить — значит добавить признаки а, b, с, d, обобщить — отбросить признаки. Общим будет понятие наука, единичным — планиметрия. Обозначим прописными буквами видовые признаки понятия. Поставим в соответствие отдельным понятиям символы, соответствующие некоторым признакам: наука ), математика (а), геометрия (b), планиметрия (с) (рисунок 14).

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





2.3 Отношения между понятиями



Понятия, как и предметы или идеи, им соответствующие, находятся в определенных отношениях, взаимосвязях друг с другом.

Если содержания понятий имеют общие признаки, они называются сравнимыми. Например, телевидение и радио — понятия сравнимые, так как имеют общий признак — они являются средствами массовой информации. Компьютер и снегопад — далекие, несравнимые понятия.

Виды отношений между понятиями по объему удобно представить в виде графа, а взаимосвязи между его частями проиллюстрировать с помощью кругов Эйлера.

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

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

Так, доказав, что в данном прямоугольном треугольнике, имеющем стороны длиной 3, 4 и 5, квадрат гипотенузы равен сумме квадратов катетов, мы обобщаем этот вывод сначала на все прямоугольные треугольники со сторонами, пропорциональными этим числам («египетский треугольник» вида (Зk)2 + (4k)2 = (5k)2), а затем на произвольный прямоугольный треугольник, т.е. а2 + b2 = с2.

Рассматривая некоторое множество (1) (рис. 15), можно совершить операцию обобщения (перейти к предку (2) — «надмножество»), провести операцию ограничения и рассматривать частный случай (потомок (5) — «подмножество») или рассмотреть аналогичные понятия, расположенные на одном уровне (братья (3) и (4)).

Для понятия «параллелограмм» аналогичными, т.е.обладающими сходными свойствами, будет понятие «параллелепипед» (и в меньшей степени — «прямая призма»).

Обобщением понятия «параллелограмм» является многоугольник, а ограничением — виды параллелограмма, например ромб или прямоугольник (рисунок 16, а).





hello_html_402c2515.png

Рисунок 15 – Схема логических переходов к подмножеству, надмножеству и аналогичным понятиям



hello_html_me3ce226.png

Рисунок 16 – Примеры изображения логических операций для понятий: а – параллелограмм; б - прямоугольник



Действительно, обладают сходными свойствами:

противоположные равны и параллельны;

равны.

Аналогично, для понятия «прямоугольник» обобщением является параллелограмм, ограничением — квадрат. Сходными свойствами обладает прямоугольный параллелепипед (рисунок 16, б).

К перечисленным свойствам, рассмотренным для параллелограмма, мы добавим еще одно.

Справедливо утверждение:, где a,b,c- длины

сторон , а d – длина его диагонали.

Логические операции обобщения, ограничения, а также аналогия являются необходимым «мыслительным инструментарием» любого ученого. Владение этими операциями может пригодиться каждому человеку для переноса информации с одного объекта на другой. Особенно важны эти приемы для учащихся, так как помогают приобретать знания с меньшими затратами, используя не только память, но и логику. Мы применяем аналогию для сжатия представленной информации в тех случаях, когда записываем аналогичные определения в виде дроби.





2.4 Операции над понятиями. Определение понятий



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

Во-вторых, определения необходимы для тех понятий, которые употребляются в новом значении. Термины «сравнение», «масса», «вес», «соль», «угол», «рациональное» (число), «действие» и др. в научном понимании отличаются от бытового употребления.

В-третьих, точное определение понятий имеет большое значение в науке вообще, а в математике — в особенности, так как точность формулировок приучает к конкретности и однозначности мыслей. Точные формулировки облегчают и упрощают процесс доказательств не только в математике.

Итак, определение понятия — это логическая операция, спомощью которой раскрывается его содержание.

Представим виды определений в виде графа, не претендуя на исчерпывающую полноту (рисунок 17).

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

Еще нам понадобятся также индуктивные и аксиоматические определения. Индуктивные определения обязательно содержат базисные пункты, определяющие объекты, которые именуют определяемым термином, и индуктивные пункты, которые задают правила образования новых объектов, также именуемых этим термином.



hello_html_m5d69ba0.png

Рисунок 17 – Классификация видов определения понятия

В отличие от явных прямых определений неявные, косвенные, т. е. описательные, определения называют дескриптивными (от лат. descriptio — описание). Например, к дескриптивным определениям относится определение: «арифметической прогрессией называется последовательность чисел, в которой разность двух соседних чисел имеет одно и то же значение».

Самый распространенный способ определения понятий — классический — через ближайший род и видовые отличия. Род (родовой признак в дальнейшем будем обозначать В) указывает на тот круг предметов и понятий, из числа которых надо выделить опре- деляемое понятие. Видовыми отличиями (далее — С) называются признаки, существенные для данного понятия.

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

Очевидно, что А В. Приведем примеры.

Квадратом (А) называется прямоугольник (В) с равными сторонами (С).

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

Информатикой (А) называется наука (В), изучающая технологию сбора, хранения и переработки информации (С).

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

Сравнение используется для образной характеристики предмета через метафоры. Например, «Архитектура — окаменевшая музыка», «Лев — царь зверей», «Книги — величественные маяки в океане времени» (Ф.Ницше), «Слово — полководец человеческой мысли» (В.Маяковский).

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

Характеристика используется для указания отличительных признаков предмета: как единичного (характеристика студента Петрова), так и общего явления: «признаками волевых действий человека является преодоление им препятствий».

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

в нем закреплены наиболее важные результаты процесса познания;

оно является основой для понимания предмета или явления.





2.5 Деление понятий. Классификация



Делением понятия называется логическая операция, раскрывающая его объем. К делению понятия прибегают тогда, когда необходимо:

раскрыть весь объем понятия, т.е. выявить все компоненты, составляющие это понятие (так, рассматривая множества, мы делили их на виды в зависимости от мощности);

указать все формы проявления и развития понятия, а не только сущность самого явления или предмета, составляющего понятие;

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

К делению прибегают, когда понятие многозначно и требуется уточнить его отдельные значения. Ранее мы уточняли новое понятие «определение понятий», разделив его на виды. При делении необходимо выявить делимое понятие, основание деления, члены деления.

При делении по видовому признаку (рис. 18) объем делимого (родового) понятия А раскрывается через перечисление всех его видов В1, В2, ..., Вn по выбранному признаку — основанию деления. В основе деления лежит изменение этого признака. Члены деления — подмножества, соподчиненные группы (виды), А — делимое (родовое) понятие — все множество.

hello_html_m4389853c.png

Рисунок 18 – Классификация видов деления понятий

При дихотомическом делении — объем делимого понятия А делится на два противоречивых В и (см. рисунок 18). В основе лежит наличие или отсутствие признака, характеристического для В или . Таким образом, дихотомия также является делением по видовому признаку при n = 2.

Графически схема деления понятия может быть представлена или кругами Эйлера, или в виде графа-дерева. Основанием (корнем) такого дерева является само понятие А. Ветви дерева — члены деления.

Принцип дихотомического деления широко применяется в моделировании и конструировании ЭВМ, так как электронно-вычислительные машины «понимают» язык алгебры логики (булевой алгебры), построенный на основе дихотомического деления классов.

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



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

Например, в информатике осуществляется классификация команд алгоритмического языка (рисунок 19, б). Умение человека обобщать, ограничивать и классифицировать понятия характеризует системное мышление.

hello_html_m29f3e85a.png

Рисунок 19 - схема дихотомической классификации: а – бинарное дерево; б – команды алгоритмического языка



hello_html_58677a1d.png

Рисунок 20 – Понятие «антонимы»



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

Классификация бывает естественная, искусственная, рабочая, научная. В науке принято классифицировать объекты, начиная от общего понятия — всего множества, и рассматривая его подмножества согласно иерархии. Тогда от общего понятия к частному можно выстроить цепочку видовых понятий: классы подклассы семейства отряды роды виды или {виды} {роды} {отряды} {семейства} {подклассы} {классы} {общие понятия (типы)}.

Рассмотрим примеры классификаций из различных областей знаний.

Понятие «антонимы» встречается не только на уроках русского языка. Оно широко используется при построении дедуктивных умозаключений для формирования отрицания и будет часто применяться при изучении дискретной математики и математической статистики (рис. 20).

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

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





2.6 Упражнения



1. Определите, правильно ли произведена операция ограничения понятий (изобразите их кругами Эйлера):

а) персональный компьютер — монитор;

б) системный блок — дисковод;

в) Web-страничка — Internet;

г) язык программирования — Си+;

д) Си+ — Borland Pascal;

е) мышка — коврик.

2. Найдите общие понятия для следующих пар понятий (изобразите их кругами Эйлера):

а) монитор, системный блок — это...;

б) Pascal, Си+ — это...;

в) принтер, сканер — это...;

г) Windows, Unix, OS/2 — это...;

д) постановка задачи, составление алгоритма — это...;

е) клавиатура, мышь — это....

3. Исключите одно из понятий ряда так, чтобы оставшиеся понятия объединялись в некоторый ряд. Укажите этот ряд и изобразите кругами Эйлера:

а) дисковод, процессор, жесткий диск, принтер, звуковая карта;

б) сложение, вычитание, деление, переменная, умножение;

в) Pascal, Си+, Basic, Unix;

г) абак, арифмометр, ЭВМ, магнитофон, ПК;

д) прямоугольник, окружность, треугольник, куб, трапеция;

е) шахматы, нарды, шашки, баскетбол.

4. Правильно ли произведено обобщение понятий? Изобразите кругами Эйлера их отношения:

а) программный язык — английский язык;

б) микропроцессор — главная часть компьютера;

в) алгоритм — строгая определенность последовательных действий над задачей;

г) код — шифрованная информация;

д) кибернетика — наука об искусственном интеллекте;

е) Windows — операционная система.

5. Какая произведена операция — обобщения или ограничения:

а) частичное решение — общее решение;

б) число, делящееся на 6, — четное число;

в) деление — деление на 10;

г) системный блок — персональный компьютер;

д) алгоритм решения — постановка задачи;

е) несчетные множества — бесконечные множества?

6. Расположите понятия в порядке уменьшения объема (изобразите их кругами Эйлера):

а) программный язык, процедуры, библиотеки, Pascal;

б) системный блок, микропроцессор, материнская плата, микросхемы;

в) Тольятти, европейский город, город Самарской области, город России;

г) байт, килобайт, бит, мегабайт, гигабайт;

д) грамм, центнер, тонна, миллиграмм, килограмм;

е) контейнер, упаковка, пачка.

7. Определите, правильно ли изображены кругами Эйлера отношения между понятиями на рисунке 21. Если схема ошибочна, нарисуйте правильную:

а) А - время, Б - минута, В - секунда, Г - час, Д - сутки (рисунок 21, а); б) А — системный блок, Б — монитор, В — процессор, Г — принтер (рисунок 21, б); в) А — бит, Б — байт, В — килобайт, Г — мегабайт (рисунок 21, в); г) А — компьютер, Б — Pentium 333, В — Pentium 333/32 Mb, Г - Pentium 333/32 Mb/4,3 Gb (рисунок 21, г); д) А — абстрактное, Б — конкретное, В — положительное, Г — понятия (рисунок 21, д).

hello_html_4e3c9fb2.png

Рисунок 21 – Схемы к заданию 7 (а-д варианты)

8. Определите, правильно ли проведено обобщение понятий. Если допущена ошибка — исправьте (изобразите их кругами Эйлера):

а) группа, факультет, колледж, учебное заведение;

б) системный блок, материнская плата, процессор;

в) DOS, командная строка, команда, символ;

г) правильная дробь, десятичная дробь, дробь;

д) алгоритм, определение входных и выходных данных, математическая модель;

е) множество, конечное множество, пустое множество.

9. Определите, в каких из приведенных примеров производится деление понятия, а в каких — деление предмета:

а) запись алгоритма бывает словесной и графической;

б) граф состоит из ребер и вершин;

в) графы делятся на ориентированные и неориентированные;

г) дискеты бывают 3- или 5-дюймовые;

д) CD-ROM бывают пишущие и непишущие;

е) система бывает: линейная, иерархическая, сотовая,

кольцеобразная.































3 Математическая логика



3.1 Понятие высказывания. Основные логические операции



Алгебру логики иначе еще называют алгеброй высказываний, логикой высказываний. Алгебра логики начала формироваться в 19 веке в трудах английского математика Дж. Буля.

Прежде всего, благодаря труду английского логика Джорджа Буля «Математический анализ логики», был достигнут подлинный прогресс науки, называемый математической логикой. Он перенёс на логику законы и правила математических действий, ввёл логические операции, предложил способ записи высказываний в символической форме.

В трудах Джорджа Буля и О. де Моргана математическая логика представлена как своеобразная алгебра – алгебра логики (алгебра высказываний).

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

Джордж Буль (1815–1864) родился в Линкольне (Англия). Сын сапожного мастера. Окончил только начальную школу и дальнейшие знания приобретал самоучкой. С 1849 г. Буль – профессор математики в Куинс – колледже в Корке (Ирландия), где преподавал до конца жизни. Буля почти в равной степени интересовали логика, математический анализ, теория вероятностей, этика Б. Спинозы, философские работы Аристотеля и Цицерона. Он считается несомненным создателем современной символической (математической) логики.

Огастес де Морган (1806–1871) родился в Индии в семье полковника английских войск. Получил образование в Кембриджском университете. Был профессором математики Лондонского университета. Математику и логику де Морган назвал азами точного знания и выражал сожаление, что математики не более заботятся о логике, чем логики о математике. Сам он стремился сблизить обе науки, и его главной заслугой явилось построение логики по образу и подобию математических наук. Независимо от Дж. Буля он открыл основные идеи алгебры логики.

«Логика Буля» основывается на отношении эквивалентности, при котором правая часть равенства всегда содержит ровно столько же «истин», сколько и левая.

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

Примеры:

  1. НГТУ – крупнейший «вуз Новосибирска».

  2. «Снег зелёный».

  3. Р= «Чтобы подключиться к Интернету с домашнего компьютера, необходим модем и соответствующее ПО».

  4. Крокодилы летают очень низко.

«А ты любишь информатику?» – это предложение не является высказыванием.

Уравнение 2+х=4 не является высказыванием. Однако, всякий раз, придавая переменной х определенное числовое значение, будем получать высказывание. Используя частицу «не», а также союзы «и», «или», связки «если …., то…», «тогда и только тогда, когда…» и т. п., можно из одних высказываний строить другие высказывания.

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

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

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

Например: сумма углов в треугольнике – 180 градусов. Алгебра логики отвлекается и от смысловой содержательности высказывания. Она интересуется только одним свойством сложных высказываний: быть истинным (True – 1) или ложным (False – 0).

Логические операции

Простейшие связки

Составные высказывания будем получать из простых с помощью логических операций: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность, которые осуществляются при помощи логических связок: ¯ (¬); ; ; ; (~) .

Таблица 2 – Простейшие связки

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

Пусть даны два произвольных высказывания Х и У

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

Таблица 3 - Таблица истинности для отрицания

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

Таблица 4 - Таблица истинности для конъюнкций

Дизъюнкцией двух высказываний Х и У называется высказывание Х ∨ У, которое истинно, когда хотя бы одно из них истинно.

Таблица 5 - Таблица истинности дизъюнкций

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

Таблица 6 - Таблица истинности для импликации

Эквивалентностью высказываний Х и У называется высказывание Х ~У, которое истинно тогда и только тогда, когда Х и У оба истинны или ложны.

Таблица 7 -Таблица истинности для эквивалентности

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

Например, составными будут высказывания:

; Х; (Х∨У)∨

Их следует читать «изнутри наружу», подобно алгебраическим выражениям, в которых сначала группируются величины, в самые внутренние скобки, затем эти скобки в свою очередь группируются и т.д. Если скобок нет ,то операции надо выполнять в следующем порядке: конъюнкция, дизъюнкция, импликация, эквивалентность, отрицание. Каждое составное высказывание имеет свою таблицу истинности, которая может быть построена стандартным образом.

Другие связки

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

Таблица 8 – Другие связки

Штрих Шеффера, Х ⃒ У или антиконъюнкция, по определению (Х ⃒ У) = .

Таблица 9 - Таблица истинности штриха Шеффера

Стрелка Пирса, или антидизъюнкция, по определению Х ↓У = .

Таблица 10 - Таблица истинности стрелки Пирса

Сумма по модулю два, или антиэквивалентность, по определению Х⨁ У = .

Таблица 11 - Таблица истинности суммы по модулю два


Заметим, что таблицы истинности логических операций содержат , где n – число простых высказываний.





3.2 Формулы алгебры логики



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

Определение.

  1. Всякая буква есть формула.

  2. Если , - формулы, то формулами являются также , , , , .

  3. Символ является формулой тогда и только тогда, когда это следует из 1) и 2).

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

Часть формулы, которая сама является формулой, называется подформулой данной формулы.


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


Другими словами, тавтология – это тождественно - истинная формула.

Установить, является ли формула тавтологией, можно:

  • по таблице истинности,

  • используя свойства логических операций.

Из курса дискретной математики известны основные логические эквивалентности (свойства логических операций), которые являются примерами тавтологий.

Законы логики. Равносильные преобразования

1. Закон тождества:

А=А

2. Закон непротиворечия:

;

3. Закон исключения третьего:



4. Закон двойного отрицания:



5. Законы истины и лжи (свойства констант):

;

6. Законы идемпотентности:

;

7. Коммутативные законы:

;

8. Ассоциативные законы:

дизъюнкции

конъюнкции

9. Дистрибутивные законы:

1ый дистрибутивный закон

2ой дистрибутивный закон

10. Законы поглощения:

;

11. Законы де Моргана:

;

12. Закон импликации:



13. Закон эквивалентности:

;

14. Свойства сложения «по модулю два»:

;

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

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

1. Правило поглощения. Данное правило является следствием из дистрибутивного закона. Оно может быть записано в следующем виде:

.

2. Правило свертки. Правило является следствием из второго дистрибутивного закона. Запись правила:

а) ;

б) .

3. Правило расширения. Правило записывается в следующем виде:

.

4. Правило склеивания. Базируется на понятии соседних конъюнкций. Соседними называются конъюнкции, отличающиеся представлением одной переменной. Например, конъюнкции и , и являются попарно соседними. В первой паре конъюнкции отличаются представлением х2, а во второй – представлением х1. По этим переменным конъюнкции склеиваются.

Формулировка правила: две соседние конъюнкции склеиваются с образованием одной конъюнкции меньшего ранга; исчезает та переменная, по которой конъюнкция склеивается. , .

Здесь , и – любые буквы.


Примеры. 1. Доказать, что формула является тавтологией.

Доказательство. Допустим, что при некоторых значениях букв (то есть в некоторой интерпретации)

Приходим к противоречию, которое доказывает, что исходная формула – тавтология.


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

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

Допустим, что при некоторых значениях букв

Следовательно, исходная формула – тавтология.


3. Доказать, что формула является тавтологией.

Доказательство. Допустим, что при некоторых значениях букв


Следовательно, исходная формула – тавтология.


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




3.3 Булевы функции



3.3.1 Нормальные формы


Конъюнктивной нормальной формой (КНФ) данной формулы называется формула, равносильная данной и представленная в виде конъюнкции основных дизъюнкций. Например, (A+B) (A+C+B) (D+A).

Дизъюнктивной нормальной формой (ДНФ) данной формулы называется формула, равносильная данной и представленная в виде дизъюнкции основных конъюнкций. Например, AB+C+AC.

Теорема 1. Для того чтобы формула алгебры высказываний была тождественно истинной, необходимо и достаточно, чтобы ее КНФ содержала в каждой элементарной дизъюнкции некоторое высказывание и его отрицание.

Теорема 2. Для того чтобы формула алгебры высказываний была тождественно ложной, необходимо и достаточно, чтобы ее ДНФ содержала в каждой элементарной конъюнкции некоторое высказывание и его отрицание.



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

Многообразие формул, посредством которых может быть выражена любая логическая функция, определяет многообразие форм логических функций, т. е. способов их записи путем применения к переменным и их группам элементарных логических операций. Наиболее удобными для практического использования оказываются совершенные нормальные формы представления сложных логических функций. В алгебре логики доказывают, что любая логическая функция F (A, B, C,…, N) может быть представлена только одной совершенной дизъюнктивной нормальной формой (кроме константы нуль) или только одной совершенной конъюнктивной нормальной формой (кроме константы единица).

СДНФ логической функции следует находить в такой последовательности:

1) составить произведения переменных для строк таблицы истинности, в которых f равна 1. Если значение переменной ( X,Y,Z) в строке равно 0, то в произведении записывается отрицание этой переменной;

2) написать сумму произведений, для которых функция f равна 1. Полученная сумма и является СДНФ /

СКНФ логической функции, согласно, следует находить в такой последовательности:

1) составить логические суммы переменных для строк таблицы истинности, в которых функция f равна 0. Если значение переменной ( X,Y,Z) в строке равно 1, то в сумме записывается отрицание этой переменной;

2) написать логическое произведение составленных логических сумм. Полученное произведение и является СКНФ.

Пример 11. Построим СДНФ для функции, таблица истинности которой имеет вид:

Таблица 12 – Таблица истинности функция f

Функция принимает значения 1 на наборах 001, 010, 101. Набору 001 соответствует элементарная конъюнкция . Набору 010 соответствует эл. кон. . Набору 101 соответствует эл. кон. .

Получаем СДНФ f= .

Пример12. Построим СКНФ для той же функции.

Функция принимает значения 0 на наборах 000, 011, 100, 110 и 111. Набору 000 соответствует элементарная дизъюнкция Набору 011 соответствует эл. диз. . И т.д.

Получаем СКНФ f=.



3.3.3 Минимизация нормальных форм

Булеву функцию назовем импликантом булевой функции f , если для любых наборов из 0 и 1из равенства =1 следует равенство f =1.

Пример 13.

Для функции f из примера 1 функция ℊ= является импликантом. Действительно, функция ℊ=1только при x=0, y=1, z=0. Но и функция f при x=0, y=1, z=0 также принимает значение 1.

Пример 14.

Для функции f из примера 1 функция ℊ= не является импликантом. Действительно, функция ℊ=1при x=1, y=1, z=0. Но f (1,1,0)=0.

Сокращенная ДНФ функции f (сокр ДНФ) есть дизъюнкция всех простых импликантов функции f.

Алгоритм построения сокращенной ДНФ с помощью СКНФ выглядит следующим образом.

  1. По таблице истинности строим СКНФ функции.

  2. В СКНФ раскрываем скобки, удаляем дублирующие элементы(АА=А, АА=А) и элементы, которые содержат переменную вместе с ее отрицанием (А∧=0).

  3. Проводим поглощение (ААВ=А) и удаляем дублирующие элементы. Сокращенная ДНФ функции f получена.

Пример 15. Для функции f из примеров 1и 2 построить сокр. ДНФ.

СКНФ f=.

Раскроем скобки. Перемножение лучше начинать со скобок, которые отличаются всего одной переменной (например,. Поэтому поменяем местами 2-ю и 3-ю скобки.

.

Перемножим 1-ю и 2-ю скобки, а также 4-ю и 5-ю скобки.

(.

В 1-ой скобке слагаемое поглощает все слагаемые, содержащие , а слагаемое поглощает все слагаемые, содержащие . В 3-ей скобке слагаемое поглощает все слагаемые, содержащие , а слагаемое поглощает все слагаемые, содержащие .

Получим (. Перемножим 2-ю и 3-ю скобки, так как у них есть общий элемент .

Мы воспользовались правилом поглощения.

сокр. ДНФ f.

Получена сокращенная ДНФ функции f.

Если из дизъюнкции простых импликантов функции f нельзя отбросить ни одного слагаемого (иначе применяется таблица истинности), то говорят, что получена тупиковая ДНФ функции f.

Тупиковая ДНФ, содержащая минимальное число переменных или их отрицаний, называется минимальной ДНФ функции f.

Алгоритм построения тупиковых и минимальных ДНФ функции f выглядит следующим образом.

  1. По таблице истинности строится СДНФ функции f.

  2. Строим сокращенную ДНФ функции f.

  3. Занумеруем в любом порядке слагаемые сокр. ДНФ функции f.

  4. Составляем таблицу покрытий. Слагаемые СДНФ функции f пишем в 1-й строке, а слагаемые сокр. ДНФ функции f вместе с номерами – в 1-м столбце. Если слагаемое сокр. ДНФ целиком входит в слагаемое СДНФ, то на пересечении соответствующей строки и столбца пишем номер слагаемого сокр. ДНФ функции f.

  5. Составляем решеточное выражение. В каждом столбце числа соединяем знаком дизъюнкции и берем конъюнкцию этих дизъюнкций.

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

  7. Каждое слагаемое в полученном выражении соответствует тупиковой ДНФ функции f. Для восстановления тупиковой ДНФ надо взять дизъюнкции тех слагаемых, номера которых указаны в полученном выражении.

  8. Тупиковые ДНФ функции f с минимальным числом переменных или их отрицаний являются минимальными ДНФ функции f.

Пример 16. Построим тупиковую и минимальную ДНФ функции f из примеров 11 и 15.

СДНФ f= . Сокр. ДНФ функции f = =12 (занумеровали слагаемые).

Заполним таблицу покрытий.

Таблица 13 – Таблица покрытий

Поясним, как заполняется таблица. В 1-й строке указаны слагаемые СДНФ. В 1-м столбце указаны слагаемые сокр. ДНФ вместе с номерами. Если слагаемое сокращенной ДНФ целиком входит в слагаемое СДНФ, то на пересечении соответствующей строки и столбца пишем номер слагаемого сокр. ДНФ функции f.

Решеточное выражение равно 212. Упростим его: 12=12.

Получилось одно слагаемое. Ему соответствует∨ - тупиковая ДНФ функции f. Она содержит 5 переменных и их отрицаний.

Так как получена одна тупиковая ДНФ, то она является и минимальной ДНФ функции f.

Мы видим, что сокр. ДНФ функции f оказалась и тупиковой и минимальной ДНФ функции f. Но так бывает не всегда.



3.4 Полнота функций



Двойственные функции

При построении двойственной функции на место каждой переменной ставится ее отрицание и берется отрицание от всей функции.

Пример 17. Определим двойственную функцию для функции f(x,y)=xy.

Двойственная функция для функции f(x,y)=xy равна f*(x,y)=. Мы видим, что дизъюнкция является двойственной функцией для конъюнкции: (xy)*=x y.

Пример 18. Определим двойственную функцию для функции f=(0010).

Так как = (1101), то двойственная функция равна f*=(1011).

Теорема о суперпозиции двойственных функций. Функция, двойственная суперпозиции двойственных функций, равна суперпозиции двойственных функций: (f(f1,…,fn))*=f*(f*1,…,f*n).

Функция, совпадающая со своей двойственной функцией (f=f*), называется самодвойственной функцией. Класс самодвойственных функций обозначается буквой S.

Пример 19. Функция f*(x)=x является самодвойственной функцией. Действительно, f*(x)=.

Класс Т0

Функция f(x1,…,xn) принадлежит классу Т0, если f(0,…,0)=0.

Пример 20. Определим, принадлежит ли классу Т0 функция

Так как f(0,0)=00=0, то функция = принадлежит классу Т0.

Класс Т1

Функция f(x1,…,xn) принадлежит классу Т1, если f(1,…,1)=1.

Пример 21. Определим, принадлежит ли классу Т1 функция

Так как f(1,1)=11=1, то функция = принадлежит классу Т1.

Полином Жегалкина

Полиномом (многочленом) Жегалкина называется многочлен, являющийся суммой константы 0 или 1 и различных одночленов, в которые все переменные входят не выше, чем в первой степени.

Теорема Жегалкина. Любую булеву функцию можно представить единственным полиномом Жегалкина.

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

Рассмотрим левую сторону треугольника Паскаля. Единицам этой стороны соответствуют наборы значений переменных исходной функции. Соединив знаком ∧ переменные, значения которых в наборе равны 1, мы получим слагаемое в полиноме Жегалкина. Набору 000 соответствует слагаемое 1.

Пример 22. Построим полином Жегалкина для функции, заданной таблицей истинности:

Таблица 14 – Таблица истинности функция f

заполним таблицу15.

Таблица 15 – Дополненная таблица

Первые 4 столбца взяты из условия.

В 5-м столбце строится треугольник Паскаля. Верхняя строка такого треугольника есть строка значений исходной функции. В каждой строке, начиная со второй, любой элемент треугольника равен сумме по модулю 2 двух соседних элементов предыдущей строки. Элементы 2-й строки: 0+1=1, 1+0=1, 0+1=1, 1+1=0, 1+0=1, 0+0=0, 0+1=1. Аналогично для других строк.

В 6-м столбце указаны конъюнкции переменных, значения которых в одном из первых трех столбцов равны 1. Набору 000 соответствует 1.

Левая сторона треугольника Паскаля равна 01001010. Единицам этой строки соответствуют слагаемые z,x,xy из 6-го столбца. Поэтому полином Жегалкина функции (x,y,z) равен zxxy.

Класс линейных функций

Функция f(x1,…xn) полином Жегалкина которой имеет вид a0a1x1⨁…⨁anxn, называется линейной функцией.

Пример 23.Функция является линейной.

Пример 24. Определим, является ли линейной функция из примера 22.

Полином Жегалкина функции (x,y,z) равен zxxy и содержит нелинейное слагаемое xy. Поэтому функции (x,y,z) не является линейной функцией.

Теорема. Класс линейных функций замкнут относительно суперпозиции, то есть суперпозиция линейных функций является линейной функцией.

Класс линейных функций обозначается буквой L.

Монотонные функции

Функция f(x1,…xn) называется монотонной, если для всех наборов

Пример 25. Определим, является ли функция из примера 22 монотонной функцией.

Так как (1,0,0) (1,0,1), а f(1,0,0)=1> f(1,0,1)=0, то функция f не является монотонной.

Пример 26. Функция (x,y)=xy является монотонной функцией.

Теорема. Класс монотонных функций замкнут относительно суперпозиции, то есть суперпозиция монотонных функций является монотонной функцией.

Класс монотонных функций обозначается буквой М.

Теорема Поста

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

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

Если при проверке системы функций на полноту обнаружится, что все функции системы принадлежат одному из классов S, Т01 ,L, М, то такая система функций не полна. Если для каждого класса S, Т01 ,L, М можно указать функцию системы, не принадлежащую этому классу, то такая система функций полна.

Пример 27. Проверим систему функций на полноту.

Таблица 16 – Таблица проверки системы на полноту

Система функций не содержится целиком ни в одном из классов. Следовательно, - полная система функций (по теореме Поста).

Пример 28. Проверим штрих Шеффера на полноту.

Так как (0,0)=00=1, то функция (x,y)=x y не принадлежит классу Т0.

(1,1)=11=0. Поэтому (x,y)=x y не принадлежит классу Т1.

Так как (0,1)=01=1=10= (1,0), то функция (x,y)=x y не является самодвойственной функцией.

(0,0)(1,1), но (0,0)=00=1> (1,1)=11=0. Поэтому функция (x,y)=x y не является монотонной функцией.

Построим полином Жегалкина для штриха Шеффера.

Таблица 17 – Дополненная таблица

Полином Жегалкина функции (x,y)=x y равен 1 xy. Поэтому функция (x,y)=x y не является линейной функцией.

Из теоремы Поста следует, что штрих Шеффера образует полную систему функций.

Таблица 18 – Таблица проверки штриха Шеффера на полноту























4 Предикаты



4.1 Логика предикатов



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

Одноместный предикат P(x) – это произвольная функция переменной х, определенная на множестве М и принимающая значения на множестве .

При подстановке вместо х конкретного значения из множества М одноместный предикат превращается в высказывание.

Пример 29. Пусть М – это множество натуральных чисел. Одноместный предикат P(x)= «x – простое число». Тогда P(2)= «2 – простое число» истинно (1), а P(4)= «4 – простое число» ложно (0).

Те значения предиката, на которых предикат принимает истинное значение, образуют множество истинности предиката.

Так как предикаты принимают значения 1 или 0, то к предикатам применяются операции ,,,¬.

Кванторные операции

Пусть P(x) – одноместный предикат, определенный на множестве М.

Квантор общности превращает предикат P(x) в высказывание x P(x) = «для всякого х P(x) истинно».

Пример 30. В примере 19 х P(x) = « для всех натуральных х число х простое» - это ложное высказывание.

Квантор существования превращает предикат P(x) в высказывание х P(x) = «существует х такой, что P(x) истинно».

Пример 31. В примере 19 х P(x) = «существует натуральное число х такое, что х простое» истинно.

Пример 32. На множестве целых чисел задан двухместный предикат P(x,y)= «x делится на y». Тогда высказывание x y P(x,y) означает «для всякого x существует y такой, что x делится на y» и является истинным высказыванием.

А высказывание x y P(x,y) = « существует x такой, что для всякого y х делится на y» это ложное высказывание. Действительно, нет такого целого числа, которое делится на все (!) целые числа.

Алфавит логики предикатов

Алфавит логики предикатов состоит из следующих символов:

  1. предметные константы p,q,r,… (принимают значения 0 или 1);

  2. предметные переменные x,y,z,…, пробегающие значения некоторого множества М;

  3. функциональные переменные f,g,h,…;

  4. предикатные переменные P,Q,R,…;

  5. символы логических операций ,,→,¬;

  6. кванторные символы ,;

  7. запятая, скобки (левая, правая): , ( ).

Формулы логики предикатов

Вводится понятие терма.

  1. Всякая предметная константа есть терм.

  2. Всякая предметная переменная есть терм.

  3. Если t1,…,tn – термы, а f – функциональная переменная, то f (t1,…,tn) есть терм.

Определим понятие формулы.

  1. Если t1,…,tn – термы, – множество всех переменных в термах t1,…,tn , Р – предикатная переменная, то Р( t1,…,tn) – элементарная формула со свободными переменными х1,…хт.

  2. Если А – формула, то – формула. Свободные переменные формулы А являются свободными переменными формулы.

  3. Если А и В есть формулы, то (АВ), (АВ), (А→В) есть формулы. Их свободные переменные есть свободные переменные формул А и В.

  4. Если А(х) – формула с множеством свободных переменных , то выражения х А(х) и х А(х) есть формулы. Переменные в этих формулах свободны, а переменная х связана квантором.

При построении новых формул надо внимательно следить за тем, чтобы предметные переменные, свободные в одной формуле, были свободными и в других формулах. Тогда эти переменные будут свободными и в построенной формуле.

Формула без свободных переменных называется замкнутой.

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

Пример 33. Определим, является ли выражение x P(x,y)Q(x) формулой.

Так как в формуле x P(x,y) переменная х связана квантором, а в формулу Q(x) переменная входит свободно, то выражение x P(x,y)Q(x) не является формулой.

Равносильные формулы

Две формулы логики предикатов называются равносильными на области М, если они принимают одинаковые значения для всех значений переменных из области М. Равносильные формулы – это формулы, равносильные на любой области.

Примеры равносильных формул:

  1. х А(х)= у А(у);

  2. х А(х)= у А(у);

  3. х у А(х,у)= у х А(х,у);

  4. х у А(х,у)= у х А(х,у);

  5. ;

  6. ;

  7. х (А(х)Н)= х А(х)Н, где формула Н не содержит переменную х свободно;

  8. х (А(х)Н)= х А(х) Н, где формула Н не содержит переменную х свободно;

  9. х (А(х) ∨В(х))=∃ х А(х) ∨∃ х В(х);

  10. х (А(х) ∧В(х))=∀ х А(х) ∧∀В(х);

  11. х А(х) ∧∃ х В(х)=∃ х ∃ у(А(х) ∧В(у));

  12. х А(х) ∨∀ х В(х)=∀ х ∀ у(А(х) ∨В(у)).

Предваренная нормальная форма

Формула А логики предикатов задана в предваренной нормальной форме, если она имеет вид Q1x1Qnxn B(x1,…xn), где Qi – один из кванторов, (i=1,…,n), а B(x1,…xn) не содержит кванторов.

Теорема. Любую формулу логики предикатов можно привести к предваренной форме.

Пример 34. Приведем формулу ∨∃ х Q(х,у) к предваренной форме.

Так как ∨∃ х Q(х,у)= х ∨∃ х Q(х,у)= х (Р(х) Q(х,у)), то предваренная нормальная форма равна ) х (Р(х) Q(х,у)).

4.2 Построение отрицаний к предикатам



В разговорной речи для построения отрицания обычно перед сказуемым ставят частицу не. Например, 1а «Студент х учится на факультете программирования» имеет отрицание 16 «Студент х не учится на факультете программирования».

Утверждения 2а «Все выпускники колледжей продолжили образование в вузе» и 26 «Все выпускники колледжей не продолжили образование в вузе» не являются отрицанием друг друга, так как они оба ложны.

Пары утверждений За «Некоторые выпускники колледжей продолжили образование в вузе» и 36 «Некоторые выпускники колледжей не продолжили образование в вузе» тоже не служат отрицанием друг друга, так как они оба истинны.

Вторая и третья пары утверждений отличаются от первых тем, что содержат кванторные слова «все» и «некоторые». А при построении отрицаний для предложений, содержащих кванторы, прием введения отрицания не перед сказуемым не срабатывает. Можно воспользоваться другим, универсальным, приемом построения отрицаний предложений, содержащих кванторы, добавив общее отрицание неверно, что... Тогда во втором примере «Неверно, что все выпускники колледжей продолжили образование в вузе» совпадает по смыслу с утверждением «Некоторые выпускники колледжей не продолжили образование в вузе». Таким образом, отрицанием предложения 2а служит 36, а отрицанием 3а служит 26.

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

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

Для сложных высказываний, состоящих из простых, разделенных операциями конъюнкции и дизъюнкции, отрицание строится следующим образом: нужно все кванторы заменить на , и наоборот; все связки и ( ) заменить на или (), и наоборот; и взять отрицание утверждения.



4.3 Упражнения



1. Связывая переменные кванторами, превратите функции в высказывания: а) х — автор романа у; б) город х стоит на берегу у; в) река х впадает в у; г) студент х учится на факультете у в учебном заведении z; д) х — число сторон, а у — число диагоналей для многоугольника z; e) словарь перевода с языка х на язык у.

2. Пусть М= 3, Р3>, где S3(x, у, z) = И <=> х + у = z, а Р3(х, у, z) = И <=>х • у = z (И — истинность). Запишите формулу с одной свободной переменной х, истинную тогда и только тогда, когда

а) х = 1; б) х - 0; в) х - 2; г) х — четное; д) х — нечетное; е) х — простое число.

3. Даны предикаты P(Х): Х< 3, Q(Y): Y< 6. Составьте предикаты:

а) Р(Х) Q(Y); в) P(Х) Q(Y); д) Q(X) Р(Х);

б) Р(Х) Q(Y); г) Q(Y) Р(Х); е) Q(Х) P(Х).

4. Запишите кванторами, постройте отрицание определений:

а) натуральное число m называется делителем натурального числа n, если р N такое, что n = m • р. Говорят также, что n кратно m. Обозначение nm;

б) натуральное число m называется простым, если оно не имеет делителей, отличных от m и 1;

в) натуральные числа m и n называются взаимно простыми, если они не имеют общих (кроме 1) делителей;

г) рассмотрим отображение f: N×N N, где f(m, n) = = mах{р|nр, mр). Числоf(m, n) называется наибольшим общим делителем натуральных чисел m и n;

д) рассмотрим отображение g: N×N N, где g(m, n) = = min{p|pm, рn}. Число g(m, n) называется наименьшим общим кратным натуральных чисел m и n.








Заключение

В данных методических рекомендациях мы кратко изложили теоретический материал, вошедший в программу изучения дисциплины «Элементы математической логики» для специальностей 230401 «Информационные системы» (по отраслям) и 230115 «Программирование в компьютерных системах» по новым ФГОС.

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





































Список использованных источников


1 Гончарова Г.А., Мочалин А.А. Элементы дискретной математики: Учебное пособие. – М.: Форум: Инфра – М, 2005.

2 Спирина М.С. Дискретная математика: Учебник для студ. учреждений сред. проф.образования/ М.С. Спирина, П.А. Спирин. – М.: Издательский центр «Академия», 2004.

3 Просветов Г.И. Дискретная математика: Задачи и решения: Учебно - практическое пособие. 2 – е изд., доп. – М.: Издательство «Альфа – Пресс», 2009.

4 Конспект лекций по дискретной математике / Ю.И. Галушкина, А.Н. Марьямов. – М.: Айрис – пресс, 2007.

5 Тишин В.В. Дискретная математика в примерах и задачах. – СПб.:БХВ – Петербург, 2008.

6 Нефедов В.Н., Осипова В.А. Курс дискретной математики – М.: Изд-во МАИ, 1992

7 Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера – М.: Энергоатомиздат, 1988

8 Уилсон Р. Введение в теорию графов – М.: Мир, 1977


























Приложение А


Перечень математических символов и сокращений


Символы и обозначения


- включение;

- принадлежность элемента множеству;

- непринадлежность элемента множеству;

- объединение множеств;

- пересечение множеств;

- суммирование;

× - декартово произведение;

- квантор общности;

- квантор существования;

- мощность множества М;

- универсальное множество;

- объединение множеств;

- пересечение множеств ;

‹› - кортеж;

deg(A) - степень вершины А;

n! - факториал числа n, т.е. произведение натуральных чисел от 1 до n;

A\B - разность множеств А и В;

AB - симметрическая разность;

отрицание ;

&, ∙, ∧ - конъюнкция;

- дизъюнкция;

- строгая дизъюнкция, сумма по модулю два;

- частичный порядок;

- пустое множество;

- импликация;

, ≡ - эквиваленция;

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

- равносильность высказывательных форм;

- равно по определению;

- непосредственная выводимость;

- выводимость;

- деление нацело;

2M - булеан множества М;

- число размещений из по ;

- число сочетаний из по ;

Pn - число перестановок из элементов;

Bn - -я декартова степень множества В;

- множество натуральных чисел;

- множество целых чисел;

- множество рациональных чисел;

- множество действительных чисел;

- множество комплексных чисел;


Сокращения


ДНФ – дизъюнктивная нормальная форма;

ДСС – десятичная система счисления;

КНФ – конъюнктивная нормальная форма;

МЗР – младший значащий разряд;

ММИ – метод математической индукции;

ПСС – позиционная система счисления;

СДНФ – совершенная дизъюнктивная нормальная форма;

СКНФ – совершенная конъюнктивная нормальная форма.




Автор
Дата добавления 09.11.2016
Раздел Математика
Подраздел Другие методич. материалы
Просмотров46
Номер материала ДБ-336424
Получить свидетельство о публикации

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