2020-07-12
537
В число функций алгебры логики, подсчитываемых с помощью теоремы 1, входят как функции, существенно зависящие от всех n аргументов, так и функции, для которых часть из этих аргументов являются фиктивными.
| 
| 
| 
| 
|
| 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 |
Пример 1-1. Для n=1 согласно теореме 1 имеем 
= 4 различные функции:
В этом случае только функции 
и 
существенно зависят от 
, а для функций 
и 
этот единственный аргумент является фиктивным.
Теорема 2. Число всех функций алгебры логики, существенно зависящих от n аргументов, определяется следующим рекуррентным соотношением:
. (1- 2)
В этом соотношении 
- число функций алгебры логики, существенно зависящих от 
аргументов.
Рассмотрим ФАЛ, которые играют большую роль в построении теории функций алгебры логики и ее приложениях. Эти функции мы будем называть в дальнейшем элементарными (таблица 1).
Система B 
образует булеву алгебру ФАЛ от n переменных (алгебру булевых функций, алгебру Буля), где 
- носитель алгебры Буля.
Рассмотренные элементарные ФАЛ позволяют строить новые функции алгебры логики двумя основными путями:
|
|
|
1) перенумерация аргументов;
2) подстановка в функцию новых функций вместо аргументов.
Функцию, полученную из функций 
путем применения (возможно многократного) этих двух правил будем называть суперпозицией функций 
.
Имея, например, элементарные функции отрицания, дизъюнкции, эквивалентности и импликации, можно составить следующие новые функции алгебры логики, являющиеся суперпозициями этих функций:
|
9. (A 
B) – (C 
D) = (A – C) 
(B – D);
(A 
(B 
C)) 
((A 
B) C);
a ~ (b | c) = ((a +b) 
c) + (a – c).
10. (A – B) + (B – A) = A +B;
P – Q = A C, если P = A – (B – C), Q = (A – B) – C;
(a ~ b) – (a | b) = (a 
a) 
(b 
b).
11. ((A 
) (
C)) ((
B) 
(B 
)) = 0;
(A – (B – C)) 
(A (B C));
(b 
(a c)) 
((b 
c) a) = b 
a.
12. (A B) + (C D) = A + B + C + D, если A B = C D;
(A – B) – C = (A – C) – (B – C);
(a 
) 
((
c) b) = a b.
13. ((A C) + (B D)) ((A + B) (C + D));
((A +B) – C) = (A – (B C)) (B – (A C));
(a | b) 
(b c) = b c.
14. ((
C) (
) (A 
)) ((
B) (B C)) = 0;
(A + B) – C) = (A – C) – (B – C);
(a 
) (( c) b) = a b.
15. P = (A – B) – C, Q = A – (B – C), если P Q;
(A – B) (B – C) (C – A) = (A B C) + (A B C);
(a b c) ~ (a b c) = (a b) (b 
c) (c 
a).
16. ((A C) + (B D)) ((A + B) (C + D));
(( A) C) (
B) = B C;
((a + b) – c) | ((a – b) + c) = a (b c).
17. (C B) ( ) ( C) ( B) (A 
) = 1;
(A B) C = A (B C), если C A;
(a ~ b) ((a c) (c d)) = (b – a) – c.
18. A – (B 
C) = (A – B) (A – C);
P Q, если P = (A – B) – C, Q = A – (B – C);
((a | b) (b c)) 
(c ~ d) = (d – c) – b.
19. (A – (B C)) (B– (A C)) (C– (A B)) = A + B + C + (A 
B C);
((A B) – C) ((A B C) – (A B C));
(a – b) – c = (a ~ b) 
(b c).
20. A + B = ( B) + (A );
(A B) (B C) (A C) = (A B) (B C) (A C);
|
b = + (b | c).
Предисловие.
|
|
|
Функции алгебры логики (ФАЛ) представляют собой один из важных и сложных разделов булевой алгебры, изучаемой по дисциплине «Дискретная математика».
Практикум включает в себя разбор пяти тем по ФАЛ:
1. элементарные логические операции;
2. тождественные преобразования равносильностей;
3. аналитические формы представления;
4. основные классы;
5. полные системы, критерии полноты.
При раскрытии указанных тем сжатое изложение необходимого теоретического материала сопровождается подробным решением типовых задач.
Сбалансированное количество определений, теорем и формул в предлагаемых методах решения задач позволяет рассматривать последние больше как методы мышления, призванными вырабатывать соответствующую математическую культуру у решателя.
Предлагаемые в заданиях к практическим занятиям и выполнению расчётно-графических работ задачи подбирались с целью наиболее полного и широкого охвата изучаемого раздела.
Такой подход позволяет изучающему в дальнейшем самостоятельно и углубленно освоить методы решения разнообразных задач при многоплановой интерпретации ФАЛ: в теории конечных автоматов, программировании, компьютерном моделировании.
Пособие преследует цель овладения практическими навыками решения задач на языке функций алгебры логики, что представляет наибольшие трудности у изучающих дискретную математику.
Как и принято в учебной литературе, большинство теоретических результатов приведено без указания авторов (за исключением задач), так как такие ссылки затрудняли бы чтение пособия. Однако вся использованная литература указана в списке литературы, приведенном в конце пособия.
|
7. 8. 9.
 | ||
 | ||
 | ||
10. 11. 12.
13. 14. 15.
16. 17. 18.
| |||
 | |||
УДК 519.1 (07)
К17
Рецензенты: А.Г. Ицков, канд. физ. – мат. наук, доц.;
Т.Ю. Нистюк, канд. техн. наук, доц.
Калядин Н.И. Практикум по дискретной математике (часть III. Функ К17 ции алгебры логики): Учеб. - метод. пособие. - Ижевск:Изд-во ИжГТУ,
2006. - 40с.
Практикум содержит краткие теоретические сведения (определения, утверждения, решения типовых примеров) по одному из важных и сложных разделов булевой алгебры в дисциплине «Дискретная математика» - функции алгебры логики.
Теоретический материал справочного характера тем не менее позволяет охватить большое разнообразие задач по функциям алгебры логики, ориентирует на углублённое изучение различных методов их решения, обеспечивает возможность овладения практическими навыками решения задач в процессе самостоятельной работы над курсом.
Предназначен для студентов и преподавателей технических вузов, изучающих дискретную математику.
СПИСОК ЛИТЕРАТУРЫ.
1. Акимов. О.Е. Дискретная математика: логика, группы, графы – 2-е изд., доп. – М.: Лаборатория базовых знаний, 2003. – 376с.
2. Белоусов А.И., Ткачев С.Б. Дискретная математика: Учеб. для вузов – М.: Изд-во МГТУ им. Н.Э. Баумана, 2004. – 744с.
3. Гаврилов Г.П., Сапоженко А.А., Сборник задач по дискретной математике. – М.: Наука, 1977. – 368с.
4. Гиндикин С.Г, Алгебра логики в задачах. – М.: Наука, 1972. – 288с.
5. Горбатов В.А. Дискретная математика: Учеб. для студентов втузов. – М.: ООО “Изд-во АСТ”: ООО “Изд-во Астрель”, 2003. – 447c.
6. Кузнецов О.П. Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988. – 480с.
|
|
|
7. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М.: Наука, 1975. – 240с.
8. Нефедов В.Н., Осипова В.А. Курс дискретной математики. Учеб. пособие. – М.: Изд-во МАИ, 1992 – 264с.
9. Поспелов Д.А. Логические методы анализа и синтеза схем. – М.: “Энергия”, 1968. – 228с.
10. Рояк М.Э., Рояк С.Х. Математическая логика (Методические указания, часть 1) – Новосибирск: Изд-во НГТУ, 1998. -61с.
11. Судоплатов С.В., Овчинникова Е.В. Дискретная математика: Учебник. – М.: ИНФРА – М; Новосибирск: Изд-во НГТУ, 2005. – 384с.
12. Яблонский С.В. Введение в дискретную математику: Учеб. пособие для вузов. – М.: Высш. шк.; 2003. – 384с.
13. Яблонский С.В., Гаврилов Г.П., Кудрявцев В.Б., Функции алгебры логики и классы Поста. – М.:Наука, 1966. - 118с.
* Задачи взяты из книги [1].
* Задачи взяты из учебника [5].
* Задачи взяты из книги [4].
* Задачи взяты из учебника [10].
1. + - сложение по модулю 2. 2. – разность
