02Глава21-22 (561019)

Файл №561019 02Глава21-22 (Полезная книга)02Глава21-22 (561019)2015-11-25СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Глава 2. Основы алгебры логики.

§1. Функции алгебры логики и их основные свойства.

Рассмотрим набор < x1, x2,…, xn>, где xi принимает значения 0 или 1: . Число различных наборов такого вида при 1≤i≤n конечно и равно 2n.

Два различных набора < x1, x2,…, xn> и < y1, y2,…, yn>, где xi и yi принимают значения 0 или 1, называются сравнимыми, если для любого i выполняется соотношение xi ≥ yi (или xi ≤ yi ), и несравнимыми во всех остальных случаях.

Функция f(x1, x2,…, xn) называется булевой или переключательной функцией, если она, так же как и ее аргументы, может принимать только два значения: 0 и 1.

Если две булевых функции f1(x1 x2… xn) и f2(x1 x2… xn) принимают на всех возможных наборах значений аргументов одинаковые значения, то функции f1 и f2 называются равными:

f1(x1 x2 … xn) = f2(x1 x2 … xn).

Функция f(x1 x2… xi-1 xi xi+1… xn) существенно зависит от аргумента xi, если имеет место соотношение:

f(x1 x2… xi-1 1 xi+1… xn) ≠f(x1 x2… xi-1 0 xi+1… xn).

В противном случае говорят, что от xi функция зависит несущественно и xi является ее фиктивным аргументом.

Теорема. Число различных функций алгебры логики, зависящих от n аргументов, конечно и равно 2n.

Для доказательства составляем таблицу значений произвольной функции n параметров (табл.1).

Таблица 1.


x1 x2 … xn f1(x1 x2 … xn)


0 0 . . . 0 α1

0 0 . . . 1 α2

. . . . . . . . . . .

1 1 . . . 0 α2n-1

1 1 . . . 1 α2n

Задавая тот или иной двоичный набор < α1 α2 … α2n >, будем описывать одну из возможных функций. Но число таких наборов = . Теорема доказана.

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

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

An= - Cnn-1 An-1- Cnn-1 An-1- Cnn-2 An-2-…- Cn1 A1- A0.

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

Пример. При n=0:

f0=0, f1=1, A0=2.

При n=1 (табл.2) f1 и f2 зависят от x существенно, а для f0 и f3 аргумент x является фиктивным.

Таблица 2.


x f0(x) f1(x) f2(x) f3(x)


0 0 0 1 1

1 0 1 0 1

При n=2:

A2= - C21 A1- A0=10.

При n=3:

A3= - C32 A2- C31 A1- A0=218.

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

x1 x2 xn-1 xn

0 0 … 0 0 0-й набор

0 0 … 0 1 1-й набор

… … … … … ……..

1 1 … 1 1 (2n-1)–й набор.

Обычно при задании таблицы наборы идут в порядке возрастания номеров.

Пример. n=0: две функции, существенно не зависящие ни от одного переменного, - константа 0 и 1.

Для n=1 функции сведены в табл.3.

Таблица 3.


x 0 1 Название функции

f0(x) 0 0 Константа 0

f1(x) 0 1 Переменная x

f2(x) 1 0 Инверсия x, не x

f3(x) 1 1 Константа 1.

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

Для n=2 переключательные функции приведены в табл.4.

Таблица 4.


x 0 0 1 1 Обозначение Название


y 0 1 0 1 функции функции


f0(xy) 0 0 0 0 0 Константа нуль

f1(xy) 0 0 0 1 xy, xΛy Логическое произведе-

ние, конъюнкция, Λ

f2(xy) 0 0 1 0 xΔy Функция запрета по y

f3(xy) 0 0 1 1 x Переменная x

f4(xy) 0 1 0 0 yΔx Функция запрета по x

f5(xy) 0 1 0 1 y Переменная y

f6(xy) 0 1 1 0 x y, y x Функция суммы по мо-

дулю 2, логическая не-

равнозначность

f7(xy) 0 1 1 1 x+y, x y Логическая сумма,

дизъюнкция,

f8(xy) 1 0 0 0 x↓y Операция (стрелка)

Пирса, операция Вебба

f9(xy) 1 0 0 1 x~y Логическая

равнозначность

f10(xy) 1 0 1 0 Инверсия y, не y

f11(xy) 1 0 1 1 y→x Импликация от y к x

f12(xy) 1 1 0 0 Инверсия x, не x

f13(xy) 1 1 0 1 x→y Импликация от x к y

f14(xy) 1 1 1 0 x | y Операция (штрих)

Шеффера

f15(xy) 1 1 1 1 1 Константа единица

При n=2, A2=10, функции f0, f3, f5, f10, f12 и f15 имеют фиктивные аргументы.

Основные соотношения алгебры логики для функций Λ, и инверсии.

  1. Основные законы алгебры логики:

а) ассоциативный (сочетательный) закон

(xy)z=x(yz)=xyz;

(x+y)+z=x+(y+z)=x+y+z;

б) коммутативный (переместительный) закон:

xy=yx;

x+y=y+x;

в) дистрибутивный (распределительный) закон:

(x+y)z=xz+yz;

(x+y)(y+z)=xz+y.

  1. Основные соотношения для инверсии:

  1. Основные соотношения для дизъюнкции:

  1. Основные соотношения для конъюнкции:

  1. Основные соотношения для системы функций:

а) операция поглощения:

x+xy=x;

x(x+y)=x;

б) операция склеивания:

в) формулы де Моргана:

Диаграммы Венна.

Наглядная интерпретация основных соотношений булевых переменных представлена на диаграммах Венна.

Класс булевых переменных определяется как класс, включающий все области внутри квадрата (рис.1).

рис.1.

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

Здесь 0 представлен как класс, совсем не имеющий точек, а 1 – как класс всех точек квадрата.

А+В – наименьшая область, содержащая одновременно А и В.

АВ – наибольшая область, содержащаяся одновременно и в А, и в В. Диаграм-мы Венна для элементарных булевых функций изображены на рис.2:

а) б) в) г) д) рис.2.

§2. Формы записи булевых функций.

Табличная запись.

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

  1. порядок записи букв в таблице совпадает с порядком аргументов в записи функции;

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

000…00 – нулевой набор;

000 …01 – 1-й набор;

. . . . . . . . . . . . . . . . . . .

111 … 11 - (2n-1)–й набор.

Функция, записанная в табличном виде, имеет индекс, равный двоичному числу, образованному значениями этой функции, записанными слева направо, начиная со значения на нулевом наборе.

Пример. Запись функции f248(АВС) = приведена в табл.5.

Таблица 5.


A B C B↓C


0 0 0 1 0 1

0 0 1 0 1 1

0 1 0 0 1 1

0 1 1 0 1 1

1 0 0 1 0 1

1 0 1 0 1 0

1 1 0 0 1 0

1 1 1 0 1 0

При задании булевых функций при 3≤n≤10 иногда используют прямоугольные таблицы, т.е. те же таблицы соответствия, но в несколько ином начертании, позволяющем получить более компактную запись. Для функции от n переменных такая таблица имеет строк и столбцов, где - целая часть числа n/2.

Пример. Запись функции f(ABCD)=[(C→D)~B] [A |0] дана в табл.6.

Пример. Запись функции f(ABCD)= приведена в табл.7.

Таблица 6. Таблица 7.


CD BC

А

AB 00 01 10 11 00 01 10 11

00 1 1 1 1 0 1 1 1 1

01 1 1 1 1 1 1 0 0 0

10 0 0 1 0

11 1 1 0 1

Аналитическая запись.

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

Пример. - элементарные произведения, - эти произведения не являются элементарными.

Число переменных, образующих элементарное произведение, называется длиной или рангом элементарного произведения.

Пример. - ранг 3.

Минтермом или конституентой единицы n переменных называется элементарное произведение ранга n.

Аналогичные определения существует и для булевых сумм.

Пример. - элементарная сумма ранга 2; не является элементарной суммой.

Макстермом или конституентой нуля n переменных называется элементарная булева сумма ранга n.

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

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

Пример. =m5.

Характеристики

Тип файла
Документ
Размер
7,14 Mb
Тип материала
Высшее учебное заведение

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

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

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

Список файлов книги

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6418
Авторов
на СтудИзбе
307
Средний доход
с одного платного файла
Обучение Подробнее