Лекции, шпаргалки, информация по предметам, статьи, лабораторные, тех.задания


Кафедра ИС(АВТ)

Основы дискретной математики - вопрос 1

Лекции(шпаргалка) по основам дискретной математики для кафедры Информационных систем (ИС), факультет Автоматики и вычислительной техники (АВТ).

Вопрос 1

1 Булевы функции

Пусть имеется несколько простых высказываний х1, x2,.... хn, каждое из которых может быть либо ложным, либо истинным, т.е. принимает символические значения 0 или

1. Всю совокупность этих высказываний можно рассматривать как кортеж (х1, х2,.... хn).

Предположим, что над этими высказываниями произвели некоторую совокупность логических операций, в результате чего получили новое высказывание (у, которое также может быть ложным или истинным, т.е. принимать значения О или 1. При этом каждой комбинации значений х1, х2,..., хn будет соответствовать определенное значение q E {О, 1}. Следовательно, эту совокупность логических операций можно рассматривать как отображение f множества значений кортежа (x1,, х2,..., хn) на множество значений q: f: (x1, x2,...,xn)->{0,1}. Если это отображение является однозначным, то оно определяет функцию q=f(x1,x2,..,xn) которую называют булевой функцией. Как следует из сказанного, у булевых функций как аргументы, так и сами функции могут принимать только два различных значения, обозначаемых 0 и 1.

Приняты три способа задания булевых функций:
I. Таблица истинности, указывающая значения истинности составного высказывания q в зависимости от значений истинности исходных высказываний. В левой часта таблицы в лексико-графическом порядке перечисляются все возможные комбинации значений истинности исходных высказываний x1, x2,...,xn..
Поясним сказанное. Каждая из конкретных комбинаций аргументов функции назншается набором. Лексико - графический порядок - это такой порядок, который совпадает с порядком возрастания наборов, рассматриваемых как N - значные двоичные числа. Иными словами, в таблице истинности наборы следует записывать 'в виде последовательности N - значных двоичных чисел, соответствующих естественной возрастающей последовательности десятичных чисел 0,1.2, 3, ... и т.д. В правой части таблицы истинности представляются значения истинности составного высказывания q для всех наборов. Если имеется N исходных высказываний, то число строк таблицы (т.е. наборов) будет равно 2^n.

2. Формула, указывающая в явном виде последовательность логических операций, производимых над высказываниями x1, x2,...,xn, -и имеющая вид соотношения (3.2).

3. Комбинационная схема, выполняющая данную логическую функцию. Очевидно, что кроме функций, рассмотренных в п.п.3.4 - 3.7, могут существовать н другие булевы функции. Число различных булевых функций от конечного числа логических переменных является конечным. Действительно, образуем всевозможные булевы функции от Алогических переменных х1, х2,..., xn. Любая упорядоченная совокупность 111 символических значений этих переменных является набором. Нетрудно рассчитать, что всего для N переменных можно получить 2^N различных наборов. Пусть f(x1, X2, ..., хn - булева функция. Каждому из наборов соответствует ее определенное символическое значение (0 или 1), так что булева функция может рассматриваться как набор п = 2^N своих значений. Различные булевы функции будут отличаться значениями логических переменных в этом наборе, т.е. в столбце, задающем f в таблице истинности. Поскольку каждая такая переменная, т.е. элемент этого столбца, может принимать только два значения, а число элементов столбца есть п, то число различных булевых функций от N аргументов определяется формулой B(N)=2^N, где n=2^N. При N= 0 существуют две различных булевых функции -это константы 0 и 1. При N = 1 можно получить 2=4 различных булевых функций, а именно, константы 0 и 1, саму функцию х и ее отрицание. При N = 3 имеется 256 булевых функций, при N = 4 их число равно 65536, и т.д.
При N = 1 число различных булевых функций равно 24 = 16. В таблице 3.1 приведены эти функции с их условными обозначениями. Будем считать, что в столбце, задающем значения функции f, младший разряд находится в верхней строке и старшинство разрядов растет по мере перемещения к нижней строке. При этом номер набора, описывающего f, увеличивается слева направо от 0000 до 1111 (т.е. от 0 до 7 в десятичной форме).

x(+)y (ОТР) - сумма по модулю 2;
х | у = х/\у (ОТР)- отрицание конъюнкции, или функция Шеффера (штрих Шеф-фера);
х|vу =xvy (ОТР)- отрицание дизъюнкции, или функция (стрелка) Пирса (функ-ция Вебба);
х<->у = х(+)у (ОТР) - равнозначность (логическая эквивалентность);
х->y, y->х - функции запрета. Диаграммы Эйлера-Венна ряда булевых функций двух переменных приведены на рис.3.11

Рис.3.11. Диаграммы Эйлера-Венна некоторых булевых функций Итак, значение булевой функции f как результат выполнения логических операций над двоичными переменными - аргументами (X1, х2, ..., хn) зависит от значений этих аргументов. Задать булеву функцию - значит указать значения, которые принимает эта функция (т.е. О или 1) при всех возможных комбинациях значений аргументов, т.е. задать ее таблицу истинности.
Если известно, какие значения принимает функция на всех наборах аргументов, то ее называют полностью определенное. Если же на некоторых наборах значения функции не заданы, то она называется недоопределенной или неполностью (частично) определенной, а комбинации аргументов, для которых функция не определена, - запрещенными наборами. Значения функции на запрещенных наборах можно задать по своему усмотрению (доопределить функцию). Этот прием может быть использован при минимизации булевых функций.

Обсудить вопрос в студенческом форуме

 

Сайт содержит информацию о учебном заведении и студенческой общине и не является официальным