mat_logika

1

1

1

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

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

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «ТАМБОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени Г.Р. ДЕРЖАВИНА»

ЗАДАЧНИК-ПРАКТИКУМ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ И ДИСКРЕТНОЙ МАТЕМАТИКЕ

Тамбов 2013

УДК 510.6:519.1 (076.1:076.5) ББК 22.12:22.176 Я73

315

Авторы:

Е.В. Малютина, Е.А. Плужникова, О.В. Филиппова, Ю.Г. Фомичева

Рецензенты:

доктор физико-математических наук, профессор С.М. Дзюба (Тамбовский государственный технический университет);

доктор физико-математических наук, профессор Е.С. Жуковский (Тамбовский государственный университет имени Г.Р. Державина)

315

Задачник-практикум по математической логике и дискретной математике : учебно-методическое пособие/ Е.В. Малютина, Е.А. Плужникова, О.В. Филиппова, Ю.Г. Фомичева; М-во обр. и науки РФ, ФГБОУ ВПО «Тамб. гос. ун-т им. Г.Р. Державина». Тамбов: Издательский дом ТГУ им. Г.Р. Державина, 2013. - 111 с.

В учебно-методическом пособии содержится теоретический материал, достаточ-

ное количество подробных решений типовых задач по математической логике и дис-

кретной математике, а также представлены задания для самостоятельного решения

с ответами.

Для студентов технических и математических специальностей дневного и заочного

отделения, а также тех, кто самостоятельно желает изучить математическую логику

и дискретную математику.

УДК 510.6:519.1 (076.1:076.5) ББК 22.12:22.176 Я73

c ФГБОУ ВПО «Тамбовский государственный университет имени Г.Р. Державина», 2013

MINISTRY OF EDUCATION AND SCIENCE

OF THE RUSSIAN FEDERATION

FEDERATIONAL STATE-FINANCED EDUCATIONAL INSTITUTION «TAMBOV STATE UNIVERSITY named after G.R. DERZHAVIN»

THE BOOK OF PROBLEMS AND WORKSHOP

ON MATHEMATICAL LOGIC AND

DISCRETE MATHEMATICS

It is allowed by Publishing council of TGU of a name G.R. Derzhavin as an educational and methodical grant for the students who are training in the directions of preparation 010100.62 – Mathematics, 010500.62 – Software and administration of information systems, 090900.62 – Information security, 230700.62 – Applied informatics.

Tambov 2012

UDK

BBK

0-30

Authors:

Е.V. Malyutina, Е.А. Pluzhnikova, О.V. Filippova, Y.G. Fomicheva. Reviewers:

Doctor of sciences in Physics and Mathematics, Professor S.M. Dzuba

(Tambov State Technical University);

Doctor of sciences in Physics and Mathematics, Professor E.S. Zhukovskiy

(Tambov State University named after G.R. Derzhavin).

0-30

The book of problems and workshop on mathematical logic and discrete mathematics: training manual/ Е.V. Malyutina [etc.]. Ministry of Education and Science РФ ФГБОУ ВПО «Tambov State University named after G.R. Derzhavin». Тambov: The publishing house of TSU named after G.R. Derzhavin, 2012. 111 p.

ISBN 978-5-89016-516-9

The training manual is concerned with the theory and with examples of mathematical logic and discrete mathematics. There are contains some exercises with responses.

For undergraduate students of technical and mathematical sciences of full-time and correspondence students and for all those who are interested in mathematical logic and discrete mathematics.

UDK

BBK

ISBN 978-5-89016-516-9 c «Tambov State University named after G.R. Derzhavin», 2012

Оглавление

Глава 1. Математическая логика . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

§ 1. Высказывания и операции над ними . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 § 2. Формулы алгебры высказываний. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .16 § 3. Равносильные преобразования формул алгебры логики . . . . . . . 18 § 4. Нормальные формы для формул алгебры высказываний . . . . . . 24 § 5. Функции алгебры логики. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .31

§ 6. Приложение алгебры логики к построению релейно-контактных схем . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

§ 7. Приложение алгебры высказываний к решению логических задач . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

5

Глава 1. Математическая логика

Математическая логика является наукой, в которой утверждения доказываются при помощи умозаключений, то есть путем использования законов человеческого мышления. Предметом изучения математической логики является изучение законов человеческого мышления. Логика (от греч. logos - мысль, разум) впервые возникла в Древней Греции в III в. до н.э., создателем логики считается греческий ученый Аристотель. Он создал формальную или аристотелевскую логику. Формальная логика просуществовала без изменения более двадцати веков. Затем формальную логику стали использовать математики при проведении доказательств. Математика развивалась с течением времени, и формальной логики стало недостаточно для использования в ней. Немецкий математик Лейбниц впервые предложил идею использования языка математики для записи логических умозаключений. Он предложил любые логические рассуждения заменить символами, связанными между собой по определенному закону, впоследствии идею Лейбница развил и реализовал на практике английский математик Буль. Он создал Булеву алгебру (или алгебру высказываний). Современная математическая логика представляет собой раздел математики, изучающий законы построения математических доказательств. Математическая логика в современном виде используется в теории алгоритмов, автоматике, математике, лингвистике, экономике, биологии.

§ 1. Высказывания и операции над ними

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

9

Глава 1. Математическая логика

Примеры.

1.Париж – столица Англии.

2.Карась – не рыба.

3.Число 24 делится на 6 и на 2.

4.Параллелограмм имеет четыре вершины.

5.Если человек успешно окончил среднюю школу, то он получил аттестат.

6.Да здравствуют победители школьных олимпиад!

Вприведенных примерах высказываниями являются предложения 1 – 5, не является высказыванием 6; 1 и 2 – ложные высказывания, 3, 4 и 5 – истинные.

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

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

Пусть на множестве всех высказываний задана функция f(x); где x – высказывание, которое может принимать значения 0 – «ложь» или 1 – «истина». Функция f(x) принимает значения на множестве {0; 1} и называется функцией истинности высказывания x:

Рассмотрим основные логические операции над высказываниями. Отрицанием высказывания x называется новое высказывание, обо-

значаемое x; которое принимает значение «истина», если x – ложно, и «ложь», если x – истина. Читается x – «не x» или «не верно, что x».

Пример 1. Пусть x – «река Волга впадает в Каспийское море», тогда x – «река Волга не впадает в Каспийское море».

Конъюнкцией (логическим умножением) двух высказываний x и y

называется новое высказывание, обозначаемое x y , которое принимает значение «истина» тогда и только тогда, когда истинны оба высказывания x и y , и значение «ложь» во всех остальных случаях. Читается x y – «x и y».

Пример 2. Пусть x – «число 6 делится на 2», y – «число 6 делится на 3», тогда x y – «число 6 делится на 2 и на 3».

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

Дизъюнкцией (логическим сложением) высказываний x и y называется новое высказывание, обозначаемое x y , которое принимает значение «ложь» тогда и только тогда, когда оба высказывания x и y ложны,

10

§ 1. Высказывания и операции над ними

и значение «истина» во всех остальных случаях. Читается x y – «x или y».

Пример 3. Пусть x – «число 7 меньше 15», y – «число 7 равно 15», тогда x y – «число 7 меньше или равно 15».

Легко доказать, что дизъюнкция высказывания и его отрицания всегда принимает значение «истина».

Импликацией (логическим следствием) высказываний x и y называется новое высказывание, обозначаемое x → y , которое является ложным, если x – истина и y – ложь, и истинным во всех остальных случаях. Читается x → y – «из x следует y» или «если x, то y». Высказывание x – «посылка», а y – «заключение» («следствие»).

Пример 4. Пусть x – «число 12 делится на 6», y – «число 12 делится на 3», тогда x → y – «если число 12 делится на 6, то оно делится на 3».

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

Эквиваленцией высказываний x и y называется новое высказывание, обозначаемое x ↔ y; которое принимает значение «истина», если оба высказывания x и y либо ложны, либо истинны одновременно, и значение «ложь» во всех остальных случаях. Читается x ↔ y – «x эквивалентно y», «x равносильно y», «x выполняется тогда и только тогда, когда выполняется y» или «для выполнения x необходимо и достаточно y». Оба высказывания x и y – это члены эквиваленции.

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

Пример 5. Пусть x – «в ABC \A = \C», y – « ABC – равнобедренный», тогда x ↔ y – «в ABC \A = \C тогда и только тогда, когда ABC – равнобедренный».

Логические значения всех выше перечисленных операций над выска-

зываниями можно задать при помощи следующей таблицы истинности.
	x	y				x y	x y	x → y	x ↔ y
				x
	1	1	0			1	1	1	1
	1	0	0			0	1	0	0
	0	1	1			0	1	1	0
	0	0	1			0	0	1	1
									11

Глава 1. Математическая логика

Упражнения

1.1. Среди следующих предложений выделите высказывания, установите истинны они или ложны:

1)Москва – столица России;

2)Луна есть спутник Марса;

3)студент Института математики, физики и информатики;

4)река Ангара впадает в озеро Байкал;

5)картины Пикассо слишком абстрактны;

6)математика – интересный предмет;

7)пейте томатный сок!;

8)который час?;

9)всякий человек имеет брата;

10)железо тяжелее свинца;

11)существует человек, который моложе своего отца;

12)ни один человек не весит более 1000 кг;

13)треугольник называется равносторонним, если все его стороны рав-

ны;

14)если в треугольнике все углы равны, то он равносторонний;

15)треугольник ABC подобен треугольнику A′B′C′;

16) для всех действительных чисел x и y верно равенство x+y = y +x;

17)23 < 5;

18)a > 0;

19)x2 − 7x + 12 = 0;

√ √

20) 3 + 2 7 − 28:

1.2.Приведите примеры предложений:

1)являющихся высказываниями;

2)не являющихся высказываниями.

1.3.Пусть a – высказывание «Студент Иванов изучает английский язык», b – высказывание «Студент Иванов успевает по математической логике». Дайте словесную формулировку высказываний:

1) a b;

2) a → b;

3) b ↔

a:

1.4.Составьте таблицу истинности для высказывания a b:

1.5.Является ли высказыванием следующее предложение: «Это предложение ложно»?

1.6.Верны ли утверждения:

1)сумма корней приведенного квадратного уравнения равна свободному члену;

2)сумма корней любого приведенного квадратного уравнения равна свободному члену;

3)существует приведенное квадратное уравнение, сумма корней которого равна свободному члену?

12