Курс лекций Часть II учебное пособие рпк «Политехник» Волгоград 2006




НазваниеКурс лекций Часть II учебное пособие рпк «Политехник» Волгоград 2006
страница1/21
Дата27.04.2013
Размер1.74 Mb.
ТипУчебное пособие
  1   2   3   4   5   6   7   8   9   ...   21


Федеральное агентство по образованию

Волжский политехнический институт (филиал)

Волгоградского государственного технического университета


Н. Д. Бовда


Дискретная математика

Курс лекций

Часть II

Учебное пособие


РПК «Политехник»

Волгоград 2006

УДК 519.1

Рецензенты:

Заместитель директора по научной работе ВГИ ВолГУ

доктор физ.-мат. наук, профессор В.В.Горяйнов

Зав.кафедрой прикладной математики и информатики ВГИ ВолГУ

доктор техн. наук, доцент И.Ю.Мирецкий

Бовда Н. Д.

ДИСКРЕТНая МАТЕМАТИКа. Курс лекций. Часть II: учебное пособие / ВолгГТУ – Волгоград, 2006г. – 91 с.

ISBN 5-230-


Содержит теоретические сведения по темам: «Алгебра двузначной логики» и «Минимизация булевых функций».

Предназначено для студентов 1-го курса направления 552800 «Информатика и вычислительная техника», изучающих курс «Дискретная математика».

Библиография - 10 назв.

Табл. – 37


Печатается по решению редакционно-издательского совета Волгоградского государственного технического университета

ISBN 5-230-

©Волгоградский

государственный

технический

университет, 2006

ОГЛАВЛЕНИЕ

lЗадачи и упражнения 73

lСписок литературы 83






  1. Алгебра двузначной логики

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


Алгебра логики возникла в середине 19 века в трудах английского математика и логика Джорджа Буля. Её создание обусловлено стремлением разработать математический аппарат для решения традиционных логических задач, в которых требуется выяснить истинность или ложность тех или иных высказываний или правильность умозаключений. В настоящее время алгебра логики применяется для описания работы дискретных управляющих систем, таких, как контактные схемы, схемы из функциональных элементов, логические сети и др.. Интерес к алгебре логики, связанный с развитием вычислительной техники, привел к многим новым достижениям в этой науке.

Под высказыванием в алгебре логики понимают любое предложение, которое может быть оценено как «истинное» или «ложное». Сопоставим значению «истина» символ «1», а значению «ложь» – символ «0». Таким образом, алгебра логики оперирует на множестве всех высказываний со значениями из двухэлементного множества Е={0, 1}. Обозначим множество всех высказываний – U. Элементы множества U будем обозначать строчными латинскими буквами a, b, c,…, a1, b1, c1, a2, b2, c2,…. Произвольные высказывания, которые могут принимать любое значение из множества U, будем называть переменными высказываниями или пропозициональными переменными, и обозначать символами x, y, z, x1, y1, z1, x2, y2, z2,….

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

Из нескольких высказываний с помощью логических связок можно составить новые, более сложные высказывания, которые в свою очередь могут быть либо истинными, либо ложными. Истинность таких составных высказываний естественно зависит от истинности составляющих их высказываний. И эта зависимость, в силу однозначной определенности логических операций, также имеет функциональный характер. Таким образом, составные высказывания можно рассматривать как функции от простых высказываний. Назовем их истинностными функциями. Итак, сигнатура алгебры логики построена – это множество всех истинностных функций (или логических операций). Обозначим это множество Р2.

Теперь формально, алгебра логики задается двумя множествами: U и Р2, где U – это множество всех высказываний, принимающих значения «истина» или «ложь», или любое другое множество, элементы которого могут принимать одно их двух значений или находиться в одном из двух состояний. Например, множество переключателей, каждый из которых может быть «включен» или «выключен», или множество электрических сигналов, поступающих на вход некоторого устройства, –«сигнал есть» или «сигнала нет» и т.п..

А множество Р2 – это множество всех таких функций, которые принимают «истинностные» значения 0 или 1, если аргументы их пробегают те же значения. Алгебра логики занимается изучением свойств этих функций.

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

Если f(x1,x2,…,xn) – истинностная функция от n аргументов, т.е. f(x1,x2,…,xn) Р2, то она определяет отображение f: ® E2. Нетрудно подсчитать число всех таких отображений.

      1. Число всех функций алгебры логики от n переменных равно 22n.

Доказательство: действительно, если x1,x2,…,xn – пропозициональные переменные, то значение каждого xi, где i =1,2,…,n, равно либо 0, либо 1. Каждый конкретный набор значений переменных x1,x2,…,xn для краткости назовем «энкой». Каждую «энку» можно рассматривать как последовательность длины n, состоящую из нулей и единиц. Число всевозможных таких последовательностей длины n равно 2n. Таким образом, значения каждой функции от n переменных определяются 2n наборами – «энками». При этом для каждой «энки» эти значения могут быть равны 0 или 1. Тем самым, значения самой функции можно рассматривать как последовательность длины 2n, состоящую из нулей и единиц. Различным функциям будут соответствовать различные последовательности длины 2n, и каждая последовательность такой длины будет задавать некоторую функцию. Поэтому общее число различных функций от n переменных равно числу последовательностей длины 2n из нулей и единиц и равно 22n.

Функция, принимающая значение, равное нулю на всех «энках», называется «противоречием».

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

«Энки», на которых функция принимает значение, равное единице, называются единичными «энками» или единичными наборами.

«Энки», на которых функция принимает значение, равное нулю, называются нулевыми «энками» или нулевыми наборами.
  1   2   3   4   5   6   7   8   9   ...   21

Похожие:

Курс лекций Часть II учебное пособие рпк «Политехник» Волгоград 2006 iconБюллетень новых поступлений февраль-май 2006 г
Конституция Российской Федерации и её развитие: Учеб пособ. Ч. 1 : Учебное пособие для студентов всех форм обучения и всех специальностей...
Курс лекций Часть II учебное пособие рпк «Политехник» Волгоград 2006 iconУчебное пособие рпк «Политехник»
Авторы: Е. Н. Ломкова, Л. И. Кухарева, (ч. I); Т. М. Мартиросова Л. П. Тарасова, Е. Д. Беришева (ч. II); А. А. Эпов, А. А. Казначеева,...
Курс лекций Часть II учебное пособие рпк «Политехник» Волгоград 2006 iconУчебное пособие рпк «Политехник»
С. С. Юхин; инженер технического отдела ООО «Управляющая компа- ния «Камышинский хбк»» Г. А. Новикова
Курс лекций Часть II учебное пособие рпк «Политехник» Волгоград 2006 iconУчебное пособие рпк «Политехник»
Рецензенты: д т н., профессор кафедры «Ткачество» мгту им. А. Н. Косыгина С. С. Юхин; инженер технического отдела ООО «Управляющая...
Курс лекций Часть II учебное пособие рпк «Политехник» Волгоград 2006 iconБюллетень новых поступлений за июнь-август 2006 г
Наукоемкие химические технологии 2004: X международная научно-техническая конференция = High-tech in chemical engineering 2004: X...
Курс лекций Часть II учебное пособие рпк «Политехник» Волгоград 2006 iconУчебное пособие Уфа 2006 удк 51: 002 ббк 74. 58 Бикмухаметов И. Х. Колганов Е. А. Математика. Часть Предмет информатики. Информатизация общества. Работа на персональном компьютере. / Учебное пособие. Уфа:, 2006. с. Курс «Математика и информатика»
Учебное пособие предназначено для студентов, осваивающих учебную дисциплину с использованием дистанционных образовательных технологий,...
Курс лекций Часть II учебное пособие рпк «Политехник» Волгоград 2006 iconМетодические указания к семинарам и практическим занятиям рпк «Политехник»
Основы философии. Методические указания к семинарам и практическим занятиям / Сост. В. В. Столяров; Волгоград гос техн ун-т. – Волгоград,...
Курс лекций Часть II учебное пособие рпк «Политехник» Волгоград 2006 iconБюллетень новых поступлений
Обработка записей средствами языка Паскаль [Текст] : учеб пособ. / Р. С. Богатырев [и др.]; Волггту. Волгоград : рпк "Политехник",...
Курс лекций Часть II учебное пособие рпк «Политехник» Волгоград 2006 iconУчебное пособие Часть 6 Рекомендовано учебно-методическим советом угаэс уфа-2006
Хамзина Р. Б. Английский язык: Учебное пособие в 6 частях. Часть / Р. Б. Хамзина. Уфа: Уфимск гос акад экономики и сервиса, 2006....
Курс лекций Часть II учебное пособие рпк «Политехник» Волгоград 2006 iconКраткий курс лекций по медицинской микробиологии, вирусологии и иммунологии Часть первая. Общая микробиология, вирусология и иммунология
Рудаков Н. В. Краткий курс лекций по медицинской микробиологии, вирусологии и иммунологии. В 2 частях: Учебное пособие. Омск, 2002....
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница