Элементарный курс математической логики учебное пособие для студентов всех специальностей Саратов 2011 удк 510. 6




НазваниеЭлементарный курс математической логики учебное пособие для студентов всех специальностей Саратов 2011 удк 510. 6
страница1/4
Дата02.05.2013
Размер0.68 Mb.
ТипУчебное пособие
  1   2   3   4


Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

Саратовский государственный технический университет


А.В.Серебряков


ЭЛЕМЕНТАРНЫЙ КУРС МАТЕМАТИЧЕСКОЙ ЛОГИКИ


Учебное пособие

для студентов всех специальностей



Саратов 2011

УДК 510.6

ББК 22.12

С 32


Рецензенты:

Кафедра вычислительного эксперимента в механике

Саратовского государственного унверситета

им. Н.Г.Чернышевского

Доктор физико-математических наук, профессор

В.Ю.Ольшанский


Одобрено

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

Саратовского государственного технического университета


Серебряков А.В.

С 32 Элементарный курс математической логики. Логические функции: учеб. пособие. Саратов: Сарат. гос. техн. ун-т, 2011. 32 с.

ISBN 978-5-7433-2368-5


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

Предназначается для студентов, обучающихся в технических вузах.


УДК 510.6

ББК 22.12


? Саратовский государственный

технический университет, 2011

ISBN 978-5-7433-2368-5 ? Серебряков А.В., 2011

ВВЕДЕНИЕ


В настоящем учебном пособии излагаются начальные понятия о множествах и функциях. Рассмотрены основные законы алгебры двузначных логических функций. Далее обсуждается применение логических функций в логике высказываний и предикатов. Каждый раздел заканчивается набором упражнений для самостоятельного решения. В списке литературы [1-13] приведены некоторые учебники и учебные пособия, изданные в последние годы, а также широко известные учебники прошлых лет издания.

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


1. НАЧАЛЬНЫЕ СВЕДЕНИЯ О МНОЖЕСТВАХ И ФУНКЦИЯХ


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


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

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



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

Для задания множества можно использовать следующие способы:

  1. перечислить все элементы, принадлежащие множеству;

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

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

Перечислением элементов можно задать только конечное множество, то есть множество, содержащее конечное число элементов.

Пример 1. Рассмотрим конечные множества, заданные перечислением элементов:

– множество всех букв латинского алфавита;

– множество всех арабских цифр;

– бинарное множество логических констант. ■

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

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



Пересечением множеств и (обозначается как ) называется множество всех тех и только тех элементов, которые принадлежат и :



Разностью множеств и (обозначается как ) называется множество всех тех и только тех элементов множества , которые не принадлежат :



Дополнением множества (обозначается как , или ) называется множество всех тех и только тех элементов, которые не принадлежат :

.

Иллюстрации данных операций в виде диаграмм Венна приведены на рис.1-4.

В заключение приведем некоторые тождества теории множеств:





(1)










1.2. Соответствие между множествами. Понятие функции


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

Пример 2. При записи шахматной партии используются множества

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

Можно построить декартово произведение произвольного числа множеств:

.

Упорядоченный набор элементов будем далее называть вектором. Компоненты будем называть проекциями вектора:

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

Используя понятие декартова произведения, определим соответствие между множествами как упорядоченную тройку множеств:

(2)

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



и область значений соответствия как множество

.

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

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

Пример 3. Расстояние точки на координатной плоскости от начала координат может быть задано функцией f: R2 R, которая представлена формулой


Упражнения


    1. Следующие множества задать перечислением их элементов:

1) A={x?R ? x3–3x2+2x = 0};

2) A={x?R ? x+1/x ? 2, x > 0};

3) A={x?N ? x2–3x–4 ? 0};

4) A={x?Z ? ¼ ? 2x < 5}.

1.2. Задать множества перечислением их элементов и найти , если:

1) – множество делителей числа 12; – множество корней уравнения ; – множество нечетных чисел таких, что

2) – множество четных чисел таких, что ; – множество делителей числа 21; – множество простых чисел, меньших 12.

1.3. Найти и изобразить эти множества на числовой прямой, если:

1)

2)

3)

1.4. Пусть – такие множества, что . Найдите множество , удовлетворяющее условиям .

1.5. Найти область определения для следующих функций f: RR

1) 2)

3) 4)

1.6. Используя определения операций над множествами, доказать данное тождество теории множеств. Проиллюстрировать доказательство с помощью диаграмм Венна.






















2. ЛОГИЧЕСКИЕ ФУНКЦИИ


2.1. Двузначные логические функции


Двузначной логической функцией n переменных называется любая функция

. (3)

В формуле (3) через B обозначено множество из двух логических значений: ложь (обозначается как 0), истина (обозначается как 1). Для логической функции число всех возможных наборов значений аргументов конечное, равное 2n. Это позволяет задавать логические функции в форме таблиц истинности. Так как для любого данного набора значений аргументов функция может принимать одно из двух значений из множества B, оказывается, что существует конечное число функций от n аргументов. Число таких функций равно .

Рассмотрим функции от одного аргумента (n=1), заданные в табл.1.

Таблица 1.

x

f0(x)

f1(x)

f2(x)

f3(x)

0

0

0

1

1

1

0

1

0

1

Приведем названия и обозначения для функций из табл.1:

f0(x)= 0 –логическая константа ложь; f1(x)= x –тождественная функция;

f2(x)= –отрицание (обозначается также );

f3(x) = 1 –логическая константа истина.

Рассмотрим теперь функции от двух аргументов (n=2). Таких функций будет 16. Для каждой из них можно задать 4 набора значений аргументов. Функции gi(x1,x2), i=0,…,15 приведены в табл.2.

Таблица 2.

x1

x2

g0

g1

g2

g3

g4

g5

g6

g7

g8

g9

g10

g11

g12

g13

g14

g15




0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

0

1

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

1

0

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1


Следует обратить внимание на правило перечисления наборов (x1,x2) в табл.2. Использован лексикографический порядок, который совпадает с порядком возрастания наборов, понимаемых как двоичные числа. В качестве столбца значений функции gi в табл.2 присутствует двоичная запись числа i. Зафиксировав лексикографический порядок перечисления наборов, мы можем представлять логические функции столбцами значений. Например,



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

Приведем названия и обозначения для некоторых функций из табл.2:

g0(x1,x2)=0 – логическая константа ложь,

g1(x1,x2)=x1&x2 – конъюнкция (обозначается также x1?x2 , x1x2 ,

произносится “x1 и x2”),

g6(x1,x2)=x1?x2 – сложение по модулю 2,

g7(x1,x2)=x1?x2 – дизъюнкция (произносится “x1 или x2”),

g8(x1,x2)=x1?x2 – стрелка Пирса,

g9(x1,x2)=x1~x2 – эквивалентность,

g13(x1,x2)=x1?x2 – импликация (произносится “если x1, то x2”),

g15(x1,x2)=1 – логическая константа истина.

Заметим, что некоторые функции зависят не от всех указанных аргументов. Так, например, функция g12(x1,x2) принимает значение, противоположное первому аргументу, независимо от значений второго аргумента, то есть g12(x1,x2)= . Переменная x2 играет для функции g12(x1,x2) роль несущественной (фиктивной) переменной.

Пусть теперь y1=f1(x1,…,xn),..., ym=fm(x1,…,xn) – логические функции n переменных, g(y1,…,ym) – логическая функция m переменных.


Тогда суперпозиция

g(f1(x1,…,xn),...,fm(x1,…,xn)) (4)

данных функций определяет новую логическую функцию n переменных. Выражение (4) принято называть логической формулой. Число аргументов для функций f1(x1,…,xn),..., fm(x1,…,xn) всегда можно сделать одинаковым за счет введения несущественных переменных.

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

Таблица 3.

x1

x2










0

0

1

1

0

1

1

1

1

0

0

0

1

1

0

1


Сравнивая табл.3 и табл.2, видим, что для всех наборов (x1,x2) выполняется равенство f(x1,x2) = g13(x1,x2). Значит, формулы и x1? x2 задают одну и ту же функцию – импликацию. Логические формулы, которые задают одну и ту же функцию, называются равносильными. ■

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

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

Приведем список равенств, выражающих равносильность некоторых логических формул:

– коммутативность;

(x?y)?z = x?(y?z), (x&y)&z = x&(y&z) – ассоциативность;

x?0 = x, x&0 = 0, x?1 = 1, x&1 = x; – свойства констант;

– двойное отрицание;

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

– закон противоречия;

– идемпотентность;

x&(y?z) = (x&y)?(x&z), x?(y&z) = (x?y)&(x?z) – дистрибутивность;

– правила де Моргана.

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

Пример 5. Докажем, что равенство выполняется тождественно, то есть для любого набора значений (x,y). Это будет означать равносильность логических формул из левой и правой частей равенства. Составим таблицу истинности, для удобства пронумеровав столбцы.

Таблица 4.
























1

2

3

4

5

6

7

0

0

0

1

1

1

1

0

1

1

0

1

0

0

1

0

1

0

0

1

0

1

1

1

0

0

0

0


Сравнивая содержимое столбцов 4 и 7 в табл.4, убеждаемся в тождественном выполнении данного равенства. ■

Между тождествами (5) и (1) обнаруживается аналогия, если установить соответствие между множествами и логическими функциями:


Таблица 5.

Множества

Логические функции




Æ

0

U

1

A?B

x?y

A?B

x&y






  1   2   3   4

Похожие:

Элементарный курс математической логики учебное пособие для студентов всех специальностей Саратов 2011 удк 510. 6 iconЭкологический мониторинг учебное пособие Санкт-Петербург 2002 удк 502: 55: 661. 510(075. 80)
Учебное пособие предназначено для студентов специальности 330200 «Инженерная защита окружающей среды» направления 656600 «Защита...
Элементарный курс математической логики учебное пособие для студентов всех специальностей Саратов 2011 удк 510. 6 iconУчебное пособие Иваново 2001 удк 658. 01 (075)
Учебное пособие предназначено для студентов специальностей 061100 и 060800
Элементарный курс математической логики учебное пособие для студентов всех специальностей Саратов 2011 удк 510. 6 iconУчебное пособие для студентов специальностей g 31 02 01 «География», н 33 01 01 02 02 «Геоэкология» Минск бгу 2003 удк 551. 4 (075. 8)
Учебное пособие для студентов специальностей g 31 02 01 «География», н 33 01 01 02 02 «Геоэкология»
Элементарный курс математической логики учебное пособие для студентов всех специальностей Саратов 2011 удк 510. 6 iconУчебное пособие по курсу «Физика» Для студентов бгуир всех специальностей и форм обучения
Учебное пособие предназначено для студентов бгуир всех специальностей и форм обучения
Элементарный курс математической логики учебное пособие для студентов всех специальностей Саратов 2011 удк 510. 6 iconТехнологии работы с правовыми базами данных учебное пособие 2-е изд., перераб и доп. Издательство
Учебное пособие предназначено для студентов специальностей «Юриспруденция», «Налоги и налогообложение» идругих специальностей и направлений,...
Элементарный курс математической логики учебное пособие для студентов всех специальностей Саратов 2011 удк 510. 6 iconУчебное пособие. Таганрог: Изд-во трту, 2005
Предлагаемое учебное пособие рекомендуется в качестве конспекта лекций по курсу «Логистика» для студентов экономических специальностей...
Элементарный курс математической логики учебное пособие для студентов всех специальностей Саратов 2011 удк 510. 6 iconУчебное пособие для студентов экономических специальностей псков Издательство ппи 2006 удк 51(091)(07)
Концепции современного естествознания: Учеб пособие для студентов экономических специальностей /А. Н. Верхозин, В. В. Однобоков /...
Элементарный курс математической логики учебное пособие для студентов всех специальностей Саратов 2011 удк 510. 6 iconУчебно-практическое пособие для студентов II курса всех специальностей Омск-2011
Учебно-практическое пособие предназначено для студентов II курса всех специальностей, изучающих учебную дисциплину «Иностранный язык»....
Элементарный курс математической логики учебное пособие для студентов всех специальностей Саратов 2011 удк 510. 6 iconУчебное пособие Уфа 2006 удк 51: 002 ббк 74. 58 Бикмухаметов И. Х. Колганов Е. А. Математика. Часть Предмет информатики. Информатизация общества. Работа на персональном компьютере. / Учебное пособие. Уфа:, 2006. с. Курс «Математика и информатика»
Учебное пособие предназначено для студентов, осваивающих учебную дисциплину с использованием дистанционных образовательных технологий,...
Элементарный курс математической логики учебное пособие для студентов всех специальностей Саратов 2011 удк 510. 6 iconУчебное пособие Рекомендовано Учебно-методическим советом Академии «Кокше» в качестве учебного пособия для студентов высших учебных заведений экономических специальностей
Учебное пособие предназначено для студентов высших учебных заведений, обучающихся по экономическим специальностям, магистрантов,...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница