рефераты конспекты курсовые дипломные лекции шпоры

Раздел Образование
/
Функции алгебры логики

Реферат Курсовая Конспект

Выберите учебное заведение

Функции алгебры логики

Функции алгебры логики - раздел Образование, Логические операции Понятие Булевой Функции, Способы Ее Задания. Функция ...

Понятие булевой функции, способы ее задания. Функция , определенная на множестве и принимающая значения из множества {0,1} называется функцией алгебры логики или булевой функцией. Набор символов переменных (х₁, ... , х₂) обозначается через или , а множество тех же символов переменных - через xⁿ. Множество всех булевых функций, зависящих от переменных х₁, ... , х_n, обозначается через Р₂(хⁿ). Обычно полагают, что . Булева функция , принимающая значение 1 (соответственно 0) на всех наборах нулей и единиц: , (соответственно ) называется константой 1 (константой 0). Константы являются нуль – местными булевыми функциями.

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

Если булева функция и формула имеют одну и ту же таблицу истинности, то говорят, что формула представляет функцию .

Булеву функцию можно также однозначно представить перечислением всех наборов, на которых она принимает значение 0, либо перечислением всех наборов, на которых она принимает значение 1.

Пример 5. Значение функции задано вектором (x, y, z ) = 00010111. Соответствующая ей таблица истинности имеет вид:

Таблица 11

x	y	z

Здесь (0, 0, 0)=(0, 0, 1)=(0, 1, 0)=(1, 0, 0)=0

или (0, 1, 1) =(1, 0, 1) =(1, 1, 0) =(1, 1, 1)=1.

Если задать либо первый, либо второй набор f (x, y, z), то функция будет задана однозначно.

Булеву функцию можно задать и с помощью единичного n – мерного куба. В связи с введением нового понятия следует привести несколько определений.

Набор , где , называется булевым или двоичным набором (вектором). Элементы набора часто называют компонентами или координатами. Кратко набор обозначают через или . Число n называют длиной набора . Весом набора называют число координат, равных 1.

Соседними называют векторы, различающиеся только в одной координате.

Противоположными – векторы, отличающиеся во всех координатах.

Множество двоичных наборов длины n образует n – мерный булев (или двоичный) куб. который называют также единичным n – мерным кубом и обозначают Вⁿ или .

Наборы называют вершинами куба Вⁿ. Каждой вершине n – мерного единичного куба можно приписать конкретное значение 0 или 1, которое принимает булева функция при соответствующем наборе аргументов (векторов ). Если значение функции равно 0, то точка не рисуется (выкалывается). Если же значение функции равно 1, то точка рисуется – выделяется полужирно. Такой n – мерный куб будет однозначно задавать любую булеву функцию . Например, для двух переменных геометрическая интерпретация булевой функции будет на плоскости иметь вид квадрата или «двумерного куба» (рис. 2а), а для трех переменных – трехмерного куба – куба в пространстве (рис. 2б).

Рис. 2а

Булевы функции одной и двух переменных. Всего существует различных булевых функций от n переменных.

При n=1 существует четыре различные булевы функции, при n=2 – 16 булевых функций. Таблицы истинности булевых функций одной или двух переменных приведенных в таблице 12 и в таблице 13.

Таблица 12

x	₁	₂	₃	₄

Функции ₁ и ₄ называются соответственно (тождественным) нулем и (тождественной) единицей.

Функция ₂ называется тождественной функцией и обозначается через х.

Функция ₃ называется отрицанием х, обозначается .

Таблица 13

x	y	₁ 0	₂	₃	₄x	₅	₆y	₇




₈	₉	₁₀~	₁₁	₁₂	₁₃	₁₄	₁₅ │	₁₆ 1

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Логические операции

ВВЕДЕНИЕ... М В Ломоносовговорил Математику уже затем учить надо что она ум в порядок... В настоящее время никто не будет спорить с утверждением что во всякой науке ровно столько науки сколько в ней...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Функции алгебры логики

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Понятие высказывания. Составные высказывания
Математическая логика представляет собой формальный математический аппарат, изучающий различные способы логических рассуждений. Простейшую из формальных логических теорий называют алгеброй высказыв

Таблицы истинности
Каждая формула алгебры высказываний обладает свойством превращаться в высказывание при фиксации в ней значений всех высказывательных переменных, т.е. если мы зафиксируем в формуле значения всех выс

Формулы алгебры логики
Формулы алгебры логики обозначаются большими буквами латинского алфавита A, B, C, D, … . Буквы, обозначающие высказывания, логические связки и скобки, составляют алфавит языков логических высказыва

Законы алгебры логики
Ключом к решению примеров на равносильные преобразования и упрощение формул являются основные равносильности булевой алгебры. Успешное решение примеров зависит от умелого, эффективного применения с

Равносильные преобразования
Первым шагом при решении примеров на эквивалентные преобразования является переход к булевым операциям с помощью формул: 1)

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

Минимизация нормальных форм
Как было изложено выше, любая булева функция может быть представлена в виде ДНФ и КНФ. Среди этих форм найдутся такие, которые содержат меньшее число переменных, чем исходная. Дизъюнктивна

К полиному Жегалкина
Указанная выше единственность представления булевой функции полиномом Жегалкина позволяет применять разнообразные методы построения соответствующих данной функции полиномиальных выражений, заботясь

Диаграммы Эйлера-Венна
Чтобы наглядно изображать множества, английский математик Джон Венн (1834-1923) предложил использовать замкнутые фигуры на плоскости. Намного раньше Эйлер (1707-1783) для изображения отношений межд

Законы теории множеств
Приведем основные тождества так называемой алгебры множеств (будем предполагать, что используемые в тождествах множества A, B, C являются подмножествами универсального множества U). Коммут

Высказываниями
Существует тесная связь между множествами – с одной стороны, и высказываниями – с другой, а также между операциями над множествами, с одной стороны, и операциями образования составных высказываний

Соотношение между высказываниями и соответствующими им множествами истинности
Мы рассмотрели такие множества истинности составных высказываний, которые образованы посредством связок V, Λ, Ø. Все остальные связки можно определить через эти три основные

Бинарные отношения
В повседневной жизни нам постоянно приходится сталкиваться с понятием «отношения». Отношения – один из способов задания взаимосвязей между элементами множества. Унарные (одноместные) отнош

Замыкания отношений
Если отношение на множестве M не обладает тем или иным свойством, то его можно попытаться продолжить до отношения R*, которое будет им обладать. Для этого необходимо присое

Отображения и функции
Пусть заданы два множества А и В. Если для каждого элемента указан элемент , с кото

Кванторы
Функциональная природа предиката влечет за собой введение ещё одного понятия – квантора. (quantum – от лат. «сколько») Кванторные операции можно рассматривать как обобщение операци

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