Реферат по дисциплине Дискретная математика на тему Функционально полные базисы булевых функций. Пять важнейших замкнутых класса T0, T1, S, L, M. Теорема Поста о функциональной полноте
 Скачать 150.12 Kb.
|
|
Министерство науки и высшего образования Российской Федерации федеральное государственное бюджетное образовательное учреждение высшего образования «Ковровская государственная технологическая академия имени В.А.Дегтярева» Кафедра «Экономики и гуманитарных наук» РЕФЕРАТ по дисциплине: «Дискретная математика» на тему: Функционально полные базисы булевых функций. Пять важнейших замкнутых класса: T0, T1, S, L, M. Теорема Поста о функциональной полноте. Примеры функционально полных базисов. Выполнил(а) : студент группы ЗЭ(БТ)-120 Федорова Т.А. Проверил: Марихов И.Н. Ковров 2022 Содержание Ведение ……………………………………………………………………………3 1.1. Понятие случайной величины…………………………………….………….4 1.2 виды распределения и функция дсв…………………………………...……..6 Заключение ………………………………………………………………...…….16 Список использованных источников………………………………..………….17 План: Полнота системы булевых функций. Классы булевых функций. Критерий Поста. Исследование систем булевых функций на полноту. Введение В современной цифровой вычислительной машине цифрами являются 0 и 1. Следовательно, команды, которые выполняет процессор, суть булевы функции. Ранее было доказано, что любая булева функция реализуется через конъюнкцию, дизъюнкцию и отрицание. Следовательно, можно построить нужный процессор, имея в распоряжении элементы, реализующие конъюнкцию, дизъюнкцию и отрицание. Попытаемся ответить на вопрос: существуют ли (и если существуют, то какие) другие системы булевых функций, обладающих тем свойством, что с их помощью можно выразить все другие функции. Цели:знать: способы задания элементарных булевых функций и их определение.уметь: использовать булевы функции для решения задач логического характера. развить способность: к решению задач, осуществлению поиска информации. Основные термины: классы булевых функций, полные системы функций, базис пространства булевых функций, теорема Поста, замкнутые классы. 1. ФУНКЦИОНАЛЬНО ПОЛНЫЕ БАЗИСЫ БУЛЕВЫХ ФУНКЦИЙ 1.1.ПОЛНОТА СИСТЕМЫ БУЛЕВЫХ ФУНКЦИЙ. Система F булевых функций называется функционально полной, если любая булева функция может быть представлена формулой над F, т.е. является суперпозицией булевых функций из F. Говорят, что функционально полная система F булевых функций образует базис пространства булевых функций. Базис Fназывается минимальным, если удаление из него любой функции превращает эту систему в неполную. Как известно, любая булева функция может быть представлена в дизъюнктивной нормальной форме и конъюнктивной нормальной форме. Значит, система булевых функций ,, согласно определению 2.1 является функционально полной. Базис ,, называется стандартным. В соответствии с законом де Моргана дизъюнкцию можно выразить через конъюнкцию и отрицание: x1 x2 x1 x2 . Следовательно, система функций , является функционально полной. Аналогично, в соответствии с законом де Моргана конъюнкцию можно выразить через дизъюнкцию и отрицание: x1 x2 x1 x2 . Следовательно, система функций , является функционально полной. Функционально полными также являются системы, состоящие только из одной функции: | (штрих Шеффера), (стрелка Пирса). Действительно, в первом случае  1 x1 x1 | x1 (см. таблицу);
x1 x2  x1 x2 x1 | x2 x | x2 | x | x2 ; 1 x1 x2 x1 x2 x1 | x2 x | x| x | x2 . 1 1 2 Во втором случае x1 x1 x1 (см. таблицу);
x1 x2 x1 x2 x1 x2 x x | x x2 ;  1 1 1 1 2 x1 x2 x1 x2 x1 x2 x x2 x x2 . Рассмотрим систему функций ,,1. Чтобы доказать ее полноту представим каждый элемент стандартного базиса формулой над базисом ,,1 x1 x1 1; x1 x2 x1 x2 x1 x2 . Докажите эти равносильности самостоятельно с помощью таблиц истинности. Базис ,,1 называется базисом Жегалкина. 1.2. Классы булевых функций. Критерий Поста. 2 1 1 Класс T0 функций, сохраняющих константу 0, т. е. таких функций 1 2 fx, x,...,x, что n f0,0,...,0 0 . Например, fx, x x x1 x2 .
Класс T1 функций, сохраняющих константу 1, т. е. таких 1 2 функций fx, x,...,x n , что f1,1,...,1 1. Например, fx, x x xx. 1 1 2 1 2
Так, например, функция f 0,1,1,1,0,0,1,1 сохраняет константу 0 и константу 1. Отрицание не сохраняет ни константу 0, ни константу 1. Функция f* называется двойственной по 1 2 отношению к функции f, если f* x, x,...,x 1 n fx, x,...,x.  1 2 n Так, функцией, двойственной к fx , x x x  1 1 2 2 2 , является функция 1 2 f* x, x xx , поскольку f* x, x x x x1 x2 fx, x. 1 1 1 2 2 2 Константа 0 является двойственной константе 1, т.к. 0 0 1, и наоборот. Стрелка Пирса есть двойственной к штриху Шеффера и наоборот, так как x x x x x x x | x . Эквиваленция двойственна сложению по модулю 2, так как x x x x x x . Отметим, что для получения таблицы истинности двойственной функции достаточно в таблице истинности исходной функции заменить значения всех переменных на противоположные, т.е. все единицы заменить на нули, а нули – на единицы. Функция fназывается самодвойственной, если она является двойственной самой себе, т.е. fx, x ,...,xn fx, x ,...,xn. 1 1 2 2 Функция самодвойственна тогда и только тогда, когда на взаимно противоположных наборах значений переменных она принимает противоположные значения. Так, функция f 0101 является самодвойственной, так как f0,0 0 f0,0 f1,1 1 0 , f0,1 1 f0,1 f1,0 0 1. Функция f 1001 (эквиваленция) не является самодвойственной, поскольку f0,0 1 f0,0 f1,1 1 0 . Класс Sсамодвойственных функций, т. е. таких функций  1 1 1 2 2 2  fx, x,...,x, что fx, x,...,x fx, x,...,x. nnn Класс Lлинейных функций, т.е. таких функций fx, x,...,x, 1 2 n которые могут быть представлены в виде fx, x,...,x 1 2 n c cx cx ... cx, где коэффициенты c, i 0;1;...;n принимают 0 1 1 2 2 nni значения 0 или 1. Класс Mмонотонных функций. На множестве наборов из нулей 1 i 2 и единиц Bn x, x,...,x| x0;1,i1;2;...;n введем частичный порядок n следующим образом: a,a,...,a b,b,...,b тогда и только тогда, когда a1 b1 , 1 2 n a2 b2 ,…, an bn. 1 2 n Определение 6.4. Функция fx, x ,...,xn называется 1 2 монотонной, если для любых двух элементов из Bn, таких, что a,a,...,a b,b,...,b следует, что fa,a,...,a fb,b,...,b. 1 2 n 1 2 n 1 2 n 1 2 n Так , функция f 0011 монотонна, поскольку f00 f01 f10 f11. Штрих Шеффера – немонотонная функция, так как 00 11, а f00 1 f11 0. Определение 6.5. Классы |