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

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

Логические формулы. Булева алгебра

Логические формулы. Булева алгебра - раздел Математика, ДИСМАТ. ВВЕДЕНИЕ. ПРЕДМЕТ ДИСКРЕТНОЙ МАТЕМАТИКИ "задание Функций Непосредственно Таблицей Удобно Лишь При Небольшом Числ...

"Задание функций непосредственно таблицей удобно лишь при небольшом числе переменных. Другим средством представления функций является суперпозиция, символическим (аналитическим) выражением которой служат формулы. Применение формул связано с использованием функциональных знаков - символов булевых функций. Некоторые из них уже встречались. Применение формул позволяет представить функции большого числа переменных суперпозициями

функций меньшего числа переменных, прежде всего через функции 1 и 2 переменных.

Формулы алгебры логики (пропозициональные формулы)

- формулы, построенные из знаков переменных и знаков функциональных операций с соблюдением определенных правил построения формул.

Поскольку мы будем рассматривать формулы, использующие исключительно одноместные и двуместные операции, приведем соответствующее индуктивное определение:

1) булевы константы 0, 1 - формулы;

2) переменные X,Y,Z и т.д. - формулы;

3) если F и G - формулы, то- формулы, гдезнак унарной операции (функции) отрицания, а знак некоторой

бинарной функциональной операции; F и G называются подформулами.

Согласно этому определениюформулы: переменные, связанные знаками функциональных операций

- также формулы, поскольку- формулы, и

суть функциональные знаки. Однако для сокращения формул принято использовать следующую иерархию (частичный порядок) функциональных символов. 'Знаксвязывает теснее знака , знак - теснее знаков, а последние - теснее знака равенства

=, связывающего равные формулы. Символически:

Кроме того, знак конъюнкции можно опускать подобно знаку умножения в алгебре; знак отрицания , отнесенный к отдельной

переменной удобнее записывать как надстрочное отрицание . Это соглашение, а также ассоциативность операцийпозволяют

устранять излишние скобки, в том числе, внешние. Например, выражение

может быть записано короче:

Формулам естественным образом соответствуют функции: знакам переменных - булевы переменные, а подформулам, соединенным функциональными знаками - булевы функции. При этом каждая формула

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

приведенное выше равенство, предлагает две разные

записи одной и той же функции. Другие примеры встречались при

определении функции. Мы приходим к следующему понятию.

, Эквивалентные (равносильные) формулы -формулы, представляющие одну и ту же функцию.

Проверить равенство двух булевых функций,

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

Прежде всего приведем равенства для формул, содержащих

операции конъюнкции, дизъюнкции и отрицания (X, Y,Z - логические переменные^.

! Конъюнкцию, дизъюнкцию и отрицание можно рассматривать как алгебраические операции над булевыми функциями. Свойства 1-2 выражают коммутативность, свойства 3-4 - ассоциативность^операций

; свойства 5-6 - взаимную дистрибутивность этих операций, что дает возможность раскрывать скобки в формулах. Свойства 7-8 -устранение кратности; свойства 9-10 называют правилами поглощения!они являются следствиями остальных свойств, что показано нижед Свойства 11-12 - законы де Моргана. Свойство 13

называют законом исключенного третьего; свойство 14 - законом противоречия. Свойства 15-20 характеризуют основные операции над переменной и константами 0 и 1. Свойство 21 - снятие двойного отрицания.|

Совокупность всех булевых функций с тремя данными

операциями есть алгебра. Она называется алгеброй

булевых функций, алгеброй логики, а также булевой алгеброй.Сравнивая свойства 1-21 для булевых функций со свойствами 1-21 §1 главы 1 для алгебры множеств, приходим к следующему результату.

Соотношение между булевой алгеброй и алгеброй Кантораесть изоморфизм, порождаемый соответствием между подмножествами

конечного п -элементного множества М и п -мерными булевыми векторами вместе с соответствием между операциями объединения, пересечения, дополнения для множеств и операциями дизъюнкции, конъюнкции и отрицания для векторов. При этом соответствии сохраняются все свойства операций, их определяющие.

Вследствие описанного изоморфизма всякую алгебру, которая обладает свойствами 1-21, называют булевой алгеброй. Кроме алгебры Кантора и алгебры логических функций, булевой алгеброй является, например, алгебра случайных событий в теории вероятностей.

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

, константам 0 и 1. Некоторые рассмотренные выше функции выражаются через

и эти выражения тоже представляют эквивалентности:

Для функций справедливы также

соотношения:

Важнейшее свойство равенства булевых функций состоит в том,

что если в суперпозициизаменить какую-либо

функциюна равную ей, то это не повлияет на результат Указанная

процедура представляет правило замены подформул.

С другой стороны, если в формуле, выражающей равенство

(эквивалентность формул) двух булевых функций заменить какую-либо переменную X на произвольную формулу, то полученные формулы

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

равенство между ними сохраняется:. Подчеркнем, что должны

одновременно заменяться все вхожденияпеременной X , Так, из равенства (13) получается равенство , верное для любой

формулы F . Однако частичная заменауже не дает верного

равенства.

Правильная подстановка и замена подформул приводит к новым эквивалентным соотношениям.

Несколько следствий основных равенств:

1) поглощение:а) свойство 9:; (*) Доказательство:= [в силу свойства 18]==

[выносим X за скобки] == [в силу свойств 17,18] =

б) свойство 10: ;

Доказательство: [раскрываем скобки]

2) склеивание: ;

Доказательство ; [выносим X за скобки]

Доказательство' [заменяем X на левую часть

равенства (*)] == [выносим Y за скобки из двух

последних слагаемых] == [в силу свойства 13]

Обратитевнимание, что равенства 7-10, 13-18 и указанные следствия содержат в правой части меньше символов (более короткие

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

Возникают естественные вопросы

(1) можно ли суперпозициями функций одной-двух переменных выразить любуюфункцию большего числа переменных;

(2) как это сделать, если это возможно. Ответ на эти вопросы - в следующем разделе.

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

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

ДИСМАТ. ВВЕДЕНИЕ. ПРЕДМЕТ ДИСКРЕТНОЙ МАТЕМАТИКИ

На сайте allrefs.net читайте: "ДИСМАТ. ВВЕДЕНИЕ. ПРЕДМЕТ ДИСКРЕТНОЙ МАТЕМАТИКИ"

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

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

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

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

Элементамимножества: записьобозначает принадлежность
элемента а множеству А , записьобозначает, что элемент b не принадлежит А . Множество

Порождающей процедуры
Простейший пример - задание последовательности элементов множества формулой, содержащей параметр: Задавая раз

Суперпозиция функций
Соответствием G между множествами А и В называется подмножество. Если

Бинарные отношения
Начнем с примеров. Натуральные числа могут быть полными квадратами, как 4, 81, 144, или не быть ими, как 5, 30, 48. Это свойство, или признак числа можно трактовать как принадлежн

Отношения порядка
Важный тип бинарных отношений - отношения порядка. Отношение строгого порядка -бинарное отношение, являющееся антирефлексивным, антисимметричным и транзитивным: обозначени

Свойства бинарных операций
Ассоциативной бинарной операциейназывается операция, если она обладает свойством . Ассоциативность ' п

Алгебры
Алгебра - не только математическая дисциплина. Тот же термин обозначает вполне определенную структуру. Алгебройназывается множество М вместе с заданной на нем систе

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

Булева функция (логическая функция, функция алгебры
^логики)- это функция одной или нескольких переменных I, где

Дизъюнктивные нормальные формы
I Важным примером эквивалентности является разложение булевой функции по переменной- представление функции

Замкнутые классы булевых функций
Выше показано, что любая функция может быть выражена в виде ДНФ, те. формулой, использующей функциональные знаки &,v,-> и символы переменных Еще один интересный пример дает система

I §2. Предполные классы
Здесь мы рассмотрим 5 замкнутых классов, играющих особую роль в вопросе о функциональной полноте Они называются предполными. причина будет выявлена ниже. 1) Класс

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

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги