новая папка 1 / 302204
.pdf292
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
«Липецкий государственный технический университет»
Кафедра высшей математики
МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ
Методические указания к самостоятельной работе
Составитель: И.А. Седых
Липецк Липецкий государственный технический университет
2014
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
«Липецкий государственный технический университет»
Кафедра высшей математики
МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ Методические указания к самостоятельной работе
Составитель: И.А. Седых
Липецк Липецкий государственный технический университет
2014
3
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
«Липецкий государственный технический университет»
Кафедра высшей математики
МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ Методические указания к самостоятельной работе
Составитель:
______________ И.А. Седых
Зав. кафедрой высшей математики |
______________А.М. Шмырин |
Липецк Липецкий государственный технический университет
2014
4
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
«Липецкий государственный технический университет»
Кафедра высшей математики
МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ Методические указания к самостоятельной работе
Составитель: И.А. Седых
Утверждаю к печати |
Проректор по учебной работе |
Объем 1,6 п.л. |
Ю.П. Качановский |
Тираж 100 экз. |
« »_________________2014 |
Липецк Липецкий государственный технический университет
2014
5
УДК 519(07) С 285
Рецензент д-р техн. наук, проф. А.М. Шмырин
С 285 Седых, И.А. Математическая логика и теория алгоритмов [Текст]: метод. указ. к самостоятельной работе./ И.А. Седых. – Липецк: Изд-во Липецкого государственного технического университета, 2014. – 25 с.
Методические указания составлены в соответствии с ФГОС-3 и предназначены для студентов направлений 010800.62 – «Механика и математическое моделирование», 220100.62 – «Системный анализ и управление» по дисциплинам «Дискретная математика», «Математическая логика и теория алгоритмов» и другим, связанным с математической логикой и теорией алгоритмов. Приведены краткие теоретические сведения по математической логике. Даны темы лабораторных работ. Методические указания содержат задания по традиционным разделам курса математической логики и теории алгоритмов.
Библиогр.: 5 назв.
© ФГБОУ ВПО «Липецкий государственный технический университет», 2014
6
Введение в математическую логику
Под высказыванием принято понимать предложение, о котором имеет смысл говорить, истинно оно или ложно. Будем обозначать высказывание большими латинскими буквами A, B, C, …, а их значения, то есть истину и ложь, соответственно И и Л.
Отрицанием высказывания А называется высказывание, истинное тогда и только тогда, когда высказывание А ложно. Отрицание A обозначается A
(или А, А ) и читается «не А».
Конъюнкцией 2-х высказываний А и В называется высказывание,
истинное тогда и только тогда, когда истинны оба высказывания. Конъюнкция высказываний А и В обозначается А В (или А&В) и читается как «А и В».
Дизъюнкцией 2-х высказываний А и В называется высказывание, ложное тогда и только тогда, когда оба высказывания ложны. Дизъюнкция высказываний А и В обозначается через А В и читается «А или В».
Импликацией 2-х высказываний А и В называется высказывание ложное тогда и только тогда, когда А истинно, а В ложно. Импликация высказываний А и В обозначается через A B (или A B, A B ) и читается «А влечёт В»
(или «если А, то В», «из А следует В»). Высказывание А называется посылкой импликации, а высказывание В – заключением импликации.
Эквивалентностью 2-х высказываний А и В называется высказывание, истинное тогда и только тогда, когда истинностные значения А и В совпадают.
Эквивалентность высказываний А и В обозначается через А ~ В и читается «А эквивалентно В».
Суммой по mod 2 (исключающим или) 2-х высказываний А и В называется высказывание, истинное тогда и только тогда, когда истинностные значения А и В различны. Сумма по mod 2 обозначаются А В (или А В ).
3
Всякое сложное высказывание, составленное из некоторых исходных высказываний посредством применения вышеперечисленных операций, будем называть формулой алгебры высказываний.
Булевой функцией f X 1 ,... X n называется произвольная функция f,
действующая из множества 0,1 n в множество 0,1 . Как аргументы булевой функции, так и сама функция принимает значения из множества 0,1 .
Пусть значению И соответствует 1, а значению Л – 0. Тогда каждой формуле логики высказываний F можно поставить в соответствие булеву функцию f.
Всякую булеву функцию от n переменных можно записать таблицей из
2n столбцов, в которой в каждом столбце записывают одно из значений списка переменных. Составим таблицу истинности для булевых функций, соответствующих основным логическим операциям:
|
X1 |
0 |
0 |
1 |
1 |
|
|
X 2 |
0 |
1 |
0 |
1 |
|
|
|
|
1 |
1 |
0 |
0 |
|
X 1 |
|||||
X 1 X 2 |
0 |
0 |
0 |
1 |
||
X 1 |
X 2 |
0 |
1 |
1 |
1 |
|
X 1 |
X 2 |
0 |
1 |
1 |
0 |
|
X1 X 2 |
1 |
1 |
0 |
1 |
||
X 1 |
~ X 2 |
1 |
0 |
0 |
1 |
Алгебра на множестве булевых функций с заданными на нем двумя операциями и называется алгеброй Жегалкина. Многочленом Жегалкина функции f X 1 ,... X n называется многочлен вида:
n |
n |
|
|
|
P X1 ,...X n a0 ai |
X i aij |
X i X j ... a12...n |
X1 X 2 |
... X n , |
i 1 |
i, j 1 |
|
|
|
|
i j |
|
|
|
где ai 0,1 . |
|
f1 ,..., f m называется полной, |
|
|
Система булевых функций |
если любая |
|||
булева функция может быть выражена через функции |
f1 ,..., f m |
с помощью |
||
суперпозиций. |
|
|
|
|
4
Теорема Поста. Для того чтобы система булевых функций f1 ,..., f m
была полной, необходимо и достаточно, чтобы для каждого из классов
T0 ,T1 , S, M , L нашлась функция из системы, не принадлежащая этому классу.
Для проверки полноты по этой теореме удобно использовать таблицу
Поста.
f |
|
T0 |
|
T1 |
|
L |
|
S |
M |
|
f1 |
|
+ |
|
– |
|
– |
|
+ |
– |
|
|
|
|
|
|
|
|
|
|
|
|
f m |
|
– |
|
+ |
|
– |
|
+ |
– |
|
Предикатом |
P X 1 ,..., X n |
называется |
функция, |
переменные которой |
принимают значения из некоторого множества М, а сама она принимает 2 значения: И или Л, то есть P X 1 ,..., X n : M n И , Л . Предикат от n аргументов называется n-местным предикатом. Высказывания считаются нульместными предикатами. Над предикатами можно производить обычные логические операции. В результате получаются новые предикаты.
Кроме операций логики высказываний, будем применять ещё операции
связывания квантором. |
|
|
Пусть P X – |
некоторый предикат, определённый на множестве М, то |
|
есть P : M И , Л . |
Тогда под выражением XP X будем подразумевать |
|
высказывание, истинное, когда P X истинно для каждого |
элемента Х из |
|
множества М, и ложное в противном случае: |
|
|
|
Л , если X 0 M , что P X 0 Л; |
|
XP X |
|
|
|
И, если X M P X И. |
|
Читается данное выражение: «для всех Х P X ». Это высказывание уже |
||
не зависит от Х. Символ X называется квантором общности. |
|
|
Пусть P X – некоторый предикат. Под выражением |
XP X будем |
понимать высказывание, истинное, когда существует элемент множества М, для которого P X истинно, и ложное в противоположном случае:
5
И, если X 0 M , что P X 0 И; |
|
XP X |
|
Л , если X M P X Л. |
|
Читается данное выражение так: «существует Х, такое число P X » или |
|
«существует Х, для которого P X ». Символ |
X называется квантором |
существования.
Операцию связывания квантором можно применять и к предикатам
большего числа переменных.
Задание 1
Для заданных булевых функций выполнить следующие задания:
1)найти таблицу истинности;
2)найти ДНФ, КНФ;
3)найти СДНФ, СКНФ;
4)найти многочлен Жегалкина.
1. |
6. |
a) b~b’(a b c’~c) |
a) b’(c~c c a) c’ |
b) c’ b(a c b) c |
b) c’ c~(c’ b b)’ c |
c) c b(c a) b’ c |
c) (b c b)’ c b c |
2. |
7. |
a) (a~b) a’ b’~b c |
a) c~(a~b~b a) a |
b) a b(a c’~b’ c) |
b) a’ a(a~a)’~a~c |
c) (a c b)’ c c’ b |
c) c c’(a’ a b) c |
3. |
8. |
a) (c a’ c a)’ b~a’ |
a) a’(c a’ b b) a’ |
b) c(b’ a~a)’~c’ b |
b) c b(a~a’ c b) |
c) (b b’ b a)’ a a |
c) b a(c’ c)’ a a |
4. |
9. |
a) c’(a b) a c’ b |
a) c a(c’ b~a) b |
b) c’(a’ b’ c) b a |
b) b a’~(c~c b a) |
c) c’ a(b a) a b |
c) b~(b’ c) a’ b c’ |
5. |
10. |
a) (c b a~a) a~c |
a) c b~(b’ c a)’ b |
b) (c c b)~a~a~a |
b) (b a’ c)’ c a’~b |
c) (c~b b)’ c c b’ |
c) b~(a~a’ a’ b) c |
6
11.
a)(a c a) c’ c a
b)c(c c c b)’ c
c)c b(c b c)’ a
12.
a)c b(a b a’~c)
b)b c’(a~a) c b
c)с(b’~с’ a)’ с с’
13.
a)a’~(a c)~c’ c b’
b)(a~a c) c b b
c)a’ c(c’~b’ a’ a)
14.
a)a b~(c~b a)’ c’
b)a~b’(c’ c) a b
c)(a’ a a) c a b’
15.
a)b’(a’ a c)’ b a
b)(b c~b)’ c a c
c)b’ b(c a) a’ c’
16.
a)b a(a c) b c
b)(a’ a’ b) c~a a
c)(b b) c b a b
17.
a)(c c a’ a) a’ c
b)b a’(a c’ b a)
c)(a~b b)’ a b’ b’
18.
a)c b(a a) b c
b)(b a a c) b b
c)b a(c~b’ c)’~c’
19.
a)c~b~(a b’~a’ b)
b)b(a’ b) c c’ a
c)c(a c c)’ a’ a
20.
a)(c’ c)’ a b a b
b)(a c a) b~a~a’
c)(c’ b b’~b)~c’ c
21.
a)c(a~c) c’~a a’
b)a(a a) c c a
c)a b(a b’~a c)’
22.
a)c(c’ b’ c’ c)~b
b)a(b’ b a) c’~a’
c)(c a) a b b a
23.
a)(c a b’ a)~c’ c
b)b(b~b) b b c
c)a b(a c c) c’
24.
a)(b c a c)’ a~a’
b)a c’(c’ a) b a’
c)c’(a’ a~b’ b) a
25.
a)(c a’ c b)’ b’~a
b)c(b’ a c)~c a
c)(c’ b a)~a a b
26.
a)(c a c c) c a’
b)b’~b’(c’ c’ a) b
c)c’~a’(a b c) a
27.
a)a(a b) a’ b c’
b)(c b)’ c~b a b
c)c’ b(a b’ c) c
28.
a)a(a b b) b’ c
b)a~(b’ c) a a’ b
c)c’ a(c a b)’ c’
29.
a)c(c’ a a’ c)’ b
b)a c(b’ b)’ c’ a’
c)(c’ c c) c~b’ c
30.
a)a~a(a a~a)’ b
b)(a a’ b) c b a
c)(c b b) c’~b b
7