Текст книги "Математический аппарат инженера"

Автор книги: Виталий Сигорский

сообщить о нарушении

Текущая страница: 6 (всего у книги 8 страниц)

– 78 -

соответственно P(A₁) = 0,7; P(A₂) = 0,8; P(A₃) = 0,9. Отказ в работе хотя бы одного из блоков приводит к отказу всего устройства, причем отказы блоков происходят независимо. Тогда вероятность безотказной работы устройства P(A) = P(A₁)P(A₂)P(A₃) = 0,7 · 0,8 · 0,9 = 0,504.

8. Условная вероятность. Если события А и В зависимы, то как указывалось в (7), после наступления одного из них, например А, вероятность другого будет отличаться от его вероятности P(B), вычисленной без учета наступления события А. Вероятность события В при условии, что уже произошло событие А, называют условной вероятностью и обозначают через P_A(B) или P(B/A). Поэтому формула для вероятности одновременного наступления двух зависимых событий должна быть записана в виде:

P(A ∩ B) = P(A)P_A(B).

Например, вероятность вынуть два белых шара из урны, в которой находятся 2 белых и 3 черных шара (предполагается, что вынутый шар не возвращается в урну) равна произведению вероятности вынуть белый шар первый раз (событие А) на вероятность вынуть белый шар второй раз (событие В) при условии, что первым был белый шар (произошло событие А)б т.е. P(A ∩ B) = 2/5 · 1/4 = 1/10. Если вынутый шар возвращается в урну, то А и В независимы и P(A ∩ B) = 2/5 · 2/5 = 4/25. Из приведенной выше формулы следует выражение

которое часто рассматривается как определение условной вероятности, если каким-либо способом определены P(A ∩ B) и P(A). Ясно, что для независимых событий P_A(B) совпадает с P(B).

Вероятность одновременного наступления нескольких зависимых событий выражается формулой

P(A₁, A₂, ... , A_n) = P(A₁)P_A1 (A₂)

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

Здесь – условная вероятность события A_i, вычисленная при условии, что произошли события A₁, A₂,..., A_i-1.

9. Объединение событий. Простая формула для вероятности появления одного из несовместных событий (6) нуждается в обобщении, если события совместны. Пусть из n равновозможных исходов событию А благоприятствуют m_A исходов, а событию B – m_B исходов. Так как множества совместных событий пересекаются, то сумма m_A + m_B, кроме исходов, благоприятствующих появлению

– 79 -

одного из событий А или В, дважды учитывает m_AB исходов, благоприятствующих одновременному появлению А и В. Поэтому из общего числа исходов n появлению событий А или В (или обоих вместе) будут благоприятствовать m_A + m_B – m_AB исходов, на основании чего имеем

Эта формула получена из каких-либо ограничений относительно характера событий А и В:

для зависимых событий

P(A ∪ B) = P(A) + P(B) -P(A)P_A(B),

для независимых событий

P(A ∪ B) = P(A) + P(B) -P(A)(B).

10. Независимость и несовместность. При использовании приведенных соотношений необходимо четко понимать смысл таких свойств событий, как независимость и несовместностью. Условиями независимости событий можно рассматривать каждое из соотношений

P(A ∩ B) = P(A) + P(B); P_A(B) = P(B)

Так, при бросании двух игральных костей вероятности событий А(дубль) и В(меньше 6 очков) равны соответственно P(A) = 6/36 = 1/6 и P(B) = 10/36 = 5/18. Одновременному появлению этих событий соответствует подмножество A ∩ B = {(1,1),(2,2)} и его вероятность P(A ∩ B) = 2/36=1/18. Так как P(A ∩ B) B≠ P(A)P(B), то рассматриваемые события являются зависимыми. С другой стороны, событие В при условии наступления события А определяется как подмножество {(1,1),(2,2)} основного множества {(1,1),(2,2), (3,3),(4,4}{(5,5),(6,6)}, и P_A(B) = 2/6 = 1/3, т.е. не совпадает с P(B)= 5/18. По соответствующим формулам имеем:

P(A ∩ B) = P(A)P_A(B) = 1/6 · 1/3 = 1/18;

P(A ∪ B) = P(A) + P(B) – P(A)P_A(B) = 1/6 + 5/18 -1/6 · 1/3 = 7/18.

Очевидно, те же результаты получим, если пример В в качестве дополнительного условия для А. Так как множество {(1,1),(1,2),

– 80 -

(1,3),(1,4),(2,1),(2,2),(2,3),(3,1),(3,2),(4,1)}, соответствующее событию В, служит основным для события А, то

P_B(A) = 2/10 = 1/5,

и следовательно получаем:

P(A ∩ B) = P(B)P_B(A)= 5/18 · 1/5 = 1/18;

P(A ∪ B) = P*A) + P(B) – P(B)P_B(A) = 1/6+5/18-5/18· 1/5=7/18.

Общее условие несовместности событий выражается как

P(A ∩ B) = 0,

что соответствует A ∩ B = ∅. Так, в рассматриваемом примере A ∩ B = {(1,1),(2,2)} ≠ ∅, следовательно, события А и В совместны.

Независимые события А и В при ненулевых вероятностях P(A) и P(B) всегда совместны. Действительно, из соотношения P(A ∩ B) = P(A)(B) имеем P(A ∩ B) ≠ 0, а значит и A ∩ B ≠ ∅, что свидетельствует о совместности независимых событий. Однако совместность событий не обязательно влечет их независимость. Из условия A ∩ B ≠ ∅ при P(A ∩ B) ≠ 0 следует лишь, что P(A ∩ B) ≠ 0 и условная вероятность P_A(B) ≠ 0. Но может иметь место неравенство P_A(B) = P(B), что означает зависимость рассматриваемых совместных событий.

Зависимые события А и В при ненулевых вероятностей P(A) и P(B) могут быть как совместными, так и несовместными. В первом случае A ∩ B ≠ ∅, и поэтому условные вероятности P_A(B) и P_B(A) не равна нулю, т.е. одно из событий может наступить при условии, что произошло другое событие. Во втором случае A ∩ B = ∅, следовательно, условные вероятности зависимых и несовместных событий P_A(B) = P_B(A) = 0. Это значит, что пир наступлении события А событие В произойти уже не может, а наступлении события В не может произойти событие А. В то же время из несовместности событий (A ∩ B = ∅) следует их зависимость, что выражается равенством нулю условных вероятностей P_A(B) и P_B(A). Иначе говоря, если события А и В несовместны, то при наступлении одного из них другое произойти не может, т.е. несовместные событие не могут быть независимыми.

Несовместность совокупности событий A₁, A₂, ..., A_n, следует из их попарной несовместимости, т.е. из условия

A_i ∩ A_j = ∅ (i,j = 1,2,..., n; i ≠ j).

– 81 -

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

P(A_i ∩ A_j) = P(A_i)P(A_j) (i,j = 1,2,..., n; i ≠ j),

должны выполняться также аналогичные условия для любых сочетаний по 3, 4, ... , n событий. Например, для трех событий условие полной независимости выражается системой соотношений:

P(A₁ ∩ A₂) = P(A₁)P(A₂);

P(A₁ ∩ A₃) = P(A₁)P(A₃);

P(A₂ ∩ A₃) = P(A₂)P(A₃);

P(A₁ ∩ A₂ ∩ A₃) = P(A₁)P(A₂)P(A₃).

Невыполнение хотя бы одного из этих соотношений свидетельствовало бы о том, что события A₁, A₂ и A₃ в совокупности зависимы. На практике, однако, попарная независимость обычно влечет за собой и независимость в совокупности.

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

1. Какова вероятность угадать все шесть номеров (из 49) в спортлото?

2. Из урны, содержащей 8 белых и 12 черных шаров, вынимают один шар. Какова вероятность того, что он будет белым; что он будет черны?

3. Найдите на основе рассмотрения множества событий при бросании двух игральных костей (каждая кость имеет шесть равноправных граней, пронумерованных от 1 до 6) вероятность следующих событий:

а) на одной кости четыре очка, а на другой – меньше четырех;

б) на одной кости число очков вдвое больше, чем на другой;

в) сумма очков меньше пяти;

г) сумма очков больше восьми.

4. Какова вероятность открыть замок автоматической камеры хранения при случайном наборе цифр (замок открывается только при определенных значениях четырех десятичных цифр)?

5. Оцените вероятность того, что в группе из 23 студентов, по крайней мере, у двух студентов дни рождения совпадают.

6. Партия из 10 телевизоров принимается в магазине при условии, что случайно выбранные два из них окажутся исправными. Какова вероятность того, что магазин примет партию, содержащую 4 неисправных телевизора?

7. Два стрелка проводят по одному выстрелу, причем вероятности попадания в цель для них равны соответственно 0,8 и 0,9. Найдите вероятность поражения цели обоими стрелками и вероятность поражения цели хотя бы одни из них.

8. Исследуйте на независимость события А и В при следующих испытаниях:

а) из колоды в 52 карты выбирают одну: А – «туз»; В – «бубна»;

б) бросают две игральные кости: А – «одно очко на первой кости»; В – «четное число очков на второй кости»;

в) бросают три монеты: А – «выпало два герба»; В – «выпало три герба».

– 82 -

9. Исследуйте на несовместность события А и В при бросании игральной кости, если:

а) А – «четыре очка»; В – «четное число очков»;

б) А – «четное число очков»; В – «нечетное число очков».

10. Пять карточек, помеченные цифрами от 1 до 5, тщательно перетасовывают. Какова вероятность того, что:

а) трехзначное число, определяемое номерами трех извлеченных наугад карточек, окажется четным;

б) при случайной раскладке всех карт пять мест с номерами от 1 до 5 ни одна карточка не займет места, отмеченного ее номером;

в) при поочередном выборе всех карточек их номера будут появляться в возрастающим порядке.

11. Из 30 выстрелов по цели отмечено 25 попаданий. Найти относительную частоту попаданий в цель.

Данный текст я (w_cat) набираю руками, опечатки LibreOffice Writer, как положено, выделяет красной волнистой, но если «опечатанное» слово совпадает с существующим в словаре (базе) то опечатку я не замечу и не исправлю, вычислите вероятность такой ошибки :).

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

Великолепный обзор основных идей и методов современной математики дан в трехтомной монографии «Математика, ее содержание, методы и значение», написанной выдающимися советскими математиками и вышедшей в издательстве АН СССР в 1956 г. под редакцией академиков А.Д. Александрова, А.Н. Колмогорова и М.А Лаврентьева. Эта книга является, пожалуй, лучшим образцом сочетания глубины, строгости и доступности изложения. Можно только пожалеть, что изданная сравнительно небольшим тиражом она стала библиографической редкостью.

Аналогичным по содержанию, но более популярным и кратким является сборник статей видных американских ученых «Математика в современном мире» (М. «Мир», 1967). Обращают на себя внимание прекрасно выполненные иллюстрации, которые помогают уяснить смысл сложных математических понятий. Живо и доступно написана книга Дж. Кемени, Дж. Снелла и Дж. Томпсона «Введение в конечную математику» (М. Изд. иностр. лит., 1963), в которой изложение идей и методов современной математики переплетается с большим количеством примеров из жизни, техники, экономики, биологии. Большое удовольствие может доставить читателю увлекательная и остроумная книга У.У. Сойера «Прелюдия к математике» (М. «Просвещение», 1965), которая аннотирована автором как «рассказ о некоторых любопытных и удивительных областях математики с предварительным анализом математического склада ума и целей математики».

Интересна и полезна для инженеров книга французских математиков Р. Фора, А Кофмана и М. Дени-Папена «Современная математика» (М., «Мир», 1966). По словам акад. А.Н. Колмогорова, под редакцией которого издан перевод этой книги, особенно ценной в ней является «достаточно стройная и в то же время простая система основных понятий». Сами авторы представляют ее как справочник по современной математике. Специально на инженеров рассчитаны книга Т. Кармана и М Био «Математические методы в инженером деле» (М., Гостехиздат, 1946), коллективная работа под ред. Э.Ф. Беккенбаха «Современная математика для инженеров» (М., Изд. иностр. лит., 1958), А. Анго «Математика для электро– и радиоинженеров» (М., «Наука», 1965). Математические теории и методы в этих книгах рассматриваются в тесной связи с конкретными прикладными задачами.

Имеется много фундаментальных монографий, содержание которых выходит за пределы программы высших технических учебных заведений по математике, но весьма полезных для инженеров. Среди них, прежде всего, необходимо назвать вышедший многими изданиями пятитомный «Курс высшей математики» В.И. Смирнова. Следует также обратить внимание на

– 83 -

трехтомное пособие Г. Джеффриса и Б. Свирлс «Методы математической физики» (М., «Мир», 1969/70).

Из общих курсов прикладной математики можно указать: Я.Б. Зельдович, А.Д. Мышкис «Элементы прикладной математики» (М., «Наука», 1972); В.А. Иванов, Б.К Чемоданов, В.С. Медведев «Математические основы теории автоматического регулирования» (М., «Высшая школа», 1971); И.А. Большаков, Л.С. Гуткин, Б.Р. Левин, Р.Л. Стратонович «Математические основы современной радиоэлектроники» (М., «Советское радио», 1968); Г.Т. Марков, Е.Н. Васильев «Математические методы прикладной электродинамики» (М., «Советское радио», 1970); Ю.М. Коршунов «Математические основы кибернетики» (М., «Энергия», 1972); В.Г. Лапа «Математические основы кибернетики» (Киев, «Вища школа», 1971); Н. Бейли «Математика в биологии и медицине» (М., «Мир», 1970).

Вопросы математического образования инженеров в современных условиях обсуждаются в сборнике статей видных советских математиков «Математическое образование сегодня» (М., «Знание», 1974).

Среди справочников, пожалуй, наиболее близок к современным потребностям инженера «Справочник по математике для научных работников и инженеров» Г. Корна и Т. Корн (М., «Наука», 1968). Он широко охватывает материал классических и новых разделов математики, являющихся необходимым орудием для инженеров-исследователей. Много внимания уделяется связи рассматриваемых математических вопросов с прикладными задачами. Разумеется, не нуждаются в рекомендации «Справочник по высшей математике» М.Я. Выгодского и «Справочник по математике» И.Н. Бронштейна и К.А, Семендяева, выдержавшие по несколько изданий и широко используемые инженерами и учащимися.

Глава 2

Множества

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

Н. Н. Лузин

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

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

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

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

– 85 -

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

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

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

1. Алгебра множеств

1. Свойства операций над множествами. Операции над множествами, сформулированные в (1.2.7), как и операции над числами, обладают некоторыми свойствами (табл. 1). Эти свойства выражаются совокупностью тождеств, справедливых независимо от конкретного содержания входящих в них множеств, являющихся подмножествами некоторого универсума U.

Тождества (1а)-(3а) выражают соответственно коммутативный, ассоциативный и дистрибутивный законы для объединения, а тождества (1б)-(3б) – те же законы для пересечения. Соотношения (4а)-(7а) определяют свойства пустого множества ∅ и универсума U относительно объединения, а соотношения (4б) – (7б) – относительно пересечения.

Выражения (8а) и (8б), называемые законами идемпотентности, позволяют записывать формулы с множества без коэффициентов и показателей степени. Зависимости (9а) и (9б) представляют законы поглощения, а (10а) и (10б) – теоремы де Моргана.

– 82 -

Таблица 1

Основные свойства операций над множествами

1 а) A ∪ B = B ∪ A

1 б) A ∩ B = B ∩ A

2 а) A ∪ (B∪ C)=(A∪ B)∪ C

2 б) A ∩ (B∩ C)=(A∩ B)∩ C

3 а) A∪ (B∩ C)=(A∪ B) ∩ (A∪ C)

3 б) A∩ (B∪ C)=(A∩ B) ∪ (A∩ C)

4 а) A ∪ ∅ = A

4б) A ∩ U = A

5 а) A ∪ A̅ = U

5 б) A ∩ A̅ = ∅

6а) A ∪ U = U

6 б) A ∩ ∅ = ∅

7 а) ∅̅ = U

7 б) U̅ = ∅

8а) A ∪ A = A

8 б) A ∩ A = A

9 а) A ∪ (A ∩ B) = A

9 б) A ∩ (A ∪ B) = A

10 а)

10 б)

11) если A ∪ B =U и A ∩ B = ∅, то B = A̅

12) A̅ = U A

13) A̿ = A

14) A B = A ∩ B̅

15) A + B = (A ∩ B̅) ∪ (A̅ ∩ B)

16) A + B = B + A

17) (A + B) + C = A + (B + C)

18) A + ∅ = ∅ + A = A

19) A ⊂ B, если и только если A ∩ B = A или A ∪ B = B или A ∩ B̅ = ∅

20) A = B, если и только если (A ∩ B̅ ) ∪ (A̅ ∩ B ) = ∅

Соотношения (11)-(20) отражают свойства дополнения, разности, дизъюнктивной суммы, включения равенства.

2. Принцип двойственности. Первые десять свойств в табл. 1 представлены парами двойственных (дуальных) соотношений, одно из которых получается заменой в другом символов: ∪ на ∩ и ∩ на ∪, а также ∅ на U и U на ∅. Соответствующие пары символов ∪, ∩ и ∅, U называются двойственными (дуальными) символами.

При замене в любой теореме входящих в нее символов дуальными получим новое предложение, которое также является теоремой (принцип двойственности или дуальности). Тождества (11) и (12) не изменяются при замене символов дуальными, поэтому их называют самодвойственными.

Принцип дуальности можно распространить на разность и дизьюктивную сумму, если использовать тождества (14) и (15). Аналогично

– 87 -

в соответствии ...........

– !!!!!!!!!!!!!!!!!!!!! -

– Продолжение следует... -

– Содержание продолжения -

...

2. Отношения

3. Отображения и функции

4. Отношение эквивалентности

5. Отношение порядка

6. Отношение толерантности

7. Законы композиции

8. Примеры алгебраических систем

9. Пространства

10. Комбинаторика

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

Глава 3. Матрицы

1. Действия над матрицами

2. Определители

3. Обращение матриц

4. Линейные уравнения

5. Дифференциальные уравнения

6. Функции от матриц

7. Матричные преобразования

8. Пространство переменных состояния

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

Глава 4. Графы

1. Деревья

2. Анатомия графов

3. Полюсные графы

4. Многополюсные компоненты

5. Системы координат

6. Неоднородный координатный базис

7. Сокращенный координатный базис

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

Глава 5

Логика

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

П.С. Новиков

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

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

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

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

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

– 503 -

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

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

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

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

1. Логические функции

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

Чтобы различать элементы области значений функции, их необходимо как-то отметить. Удобнее всего элементы перенумеровать числами от 1 до k или обозначить какими-нибудь символами (например, буквами). Перечень всех символов, соответствующих области значений, называют алфавитом, а сами символы – буквами этого алфавита (буквами могут служить как собственно буквы латинского, русского или другого алфавита, так и порядковые числа или любые другие символы).

– 504 -

Логические функции могут зависеть от одной, двух и, вообще, любого числа переменных (аргументов) x₁, x₂, ..., x_n. В отличие от самой функции, аргументы могут принимать значения из элементов как конечных, так и бесконечных множеств.

В теоретико-множественном смысле логическая функция n переменных y = f(x₁, x₂, ..., x_n) представляет собой отображение множества наборов (n-мерных векторов, кортежей, последовательностей) вида (x₁, x₂, ..., x_n), являющегося областью ее определения, на множестве ее значений N = {α₁, α₂, ..., α_n}. Логическую функцию можно также рассматривать как операцию, заданную законом композиции X₁, X₂, ..., X_n где – множества, на которых определены аргументы x₁ ∈ X₁, x₂ ∈ X₂, ..., x_n ∈ X_n.

2. Однородные функции. Если аргументы принимают значения из того же множества, что и сама функция, то ее называют однородной функцией. В этом случае X₁ = Х₂ = ... = Х_n = N и однородная функция, рассматриваемая как закон композиции Nⁿ → N определяет некоторую п-местную операцию на конечном множестве N.

Областью определения однородной функции у = f(х₁, х₂, ..., x_n) служит множество наборов (х₁, х₂, ..., x_n), называемых словами, где каждый из аргументов х₁, х₂, ..., x_n замещается буквами k-ичного алфавита {0, 1, ..., k -1}. Количество n букв в данном слове определяет его длину.

Очевидно, число всевозможных слов длины n в k-ичном алфавите равно kⁿ. Так как каждому такому слову имеется возможность предписать одно из k значений множества N, то общее количество однородных функций от n переменных выражается числом k^(kn).

Если буквами алфавита служат числа от 0 до k - 1, то каждое слово (х₁, х₂, ..., x_n) символически представляется упорядоченной последовательностью n таких чисел и рассматривается как запись n-разрядного числа в позиционной системе счисления с основанием k, т. е. x₁k^{n -1} + x₂k^{n –2} + … + x_{n -1}k¹ + x_nk⁰ = q. Числа q = 0, 1, ..., kⁿ – 1 служат номерами слов и тем самым на множестве всех слов вводится естественная упорядоченность (отношение строгого порядка). Аналогично номерами функций можно считать kⁿ -разрядные числа в той же системе счисления.

Различные слова длины n в данном алфавите образуются как n-перестановки с повторениями (2. 10. 1). Так, в трехзначном алфавите {0, 1, 2} словами длины 4 будут все четырехразрядные числа с основанием k = 3, т. е. 0000, 0001, 0002, 0010, 0011, ..., 2221, 2222, которые соответствуют десятичным числам от 0 до 80 = 2 · З³+ 2 · З²+ 2 · З¹ + 2 · 3⁰. Поставив каждому такому четырехразрядному числу в соответствие одну из букв алфавита {0, 1, 2}, получим некоторую функцию четырех переменных

– 505 -

f_i(х₁, х₂, x₃, x₄), причем количество таких функций выражается огромным числом 3⁸¹.

Пусть алфавит состоит из трех букв русского алфавита {о, п, т}. Множество пятибуквенных слов в этом алфавите состоит из 3⁵ = 243 элементов. Наряду с такими имеющими прямой смысл словами, как «топот» и «потоп», оно также включает все другие 5-перестановки, например: «ооппт», «поппп», «тттоп» и др.

Примерами однородных логических функций двух переменных могут служить операции сложения и умножения одноразрядных m-значных чисел по модулю т (2. 8. 7), внутренние операции поля Галуа (2. 8. 9) с четырехзначным алфавитом {0, 1, А, В} и т. п.

3. Табличное задание функций. Как и бинарный закон композиции (2. 7. 2), однородная функция двух переменных может быть задана таблицей соответствия (матрицей), строки и столбцы которой соответствуют буквам алфавита. Таким способом представлялись функции одной и двух переменных в (1. 5. 2),(1. 5. 8) и (1. 5. 10). Для представления функций трех и большего числа переменных потребовались бы трехмерные и, вообще, n-мерные таблицы. Этого можно избежать, если столбцы матрицы поставить в соответствие не буквам алфавита, а словам, т. е. образовать kⁿ столбцов. Для каждой функции отводится строка, клетки которой заполняются буквами из данного алфавита. Матрица всех функций n переменных в k-значном алфавите содержит k^kn строк и называется общей таблицей соответствия. Например, для k = 3 и n = 2 такая матрица имеет вид:

Номера столбцов определяются расположенными над ними n-разрядными числами с основанием k, каждое из которых читается сверху вниз. Номера функций отождествляются с kⁿ-разрядными числами, которые соответствуют строкам матрицы в той же системе счисления.

4. Двузначные однородные функции. Наиболее простым и в то же время важнейшим классом однородных функций являются двузначные (булевы) функции, частично рассмотренные в (1.5. 2) и последующих пунктах.

– 506 -

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

Число всевозможных булевых функций n переменных v = 2ⁿбыстро возрастает с увеличением n (при n = 3 оно равно 256, а при n = 5 превышает 4 миллиарда). Но функции одной и двух переменных еще можно перечислить и подробно исследовать, так как их количество сравнительно невелико (v = 4 при п = 1 и v = 16 при n = 2).

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

x

|

0

1

|

y

–

|

–

–

|

–

y₀

|

0

0

|

0

y₁

|

0

1

|

x

y₂

|

1

0

|

x̅

y₃

|

1

1

|

1

Две функции у₀ = 0 и у₃ = 1 представляют собой функции-константы (тождественный нуль и тождественная единица), таккакони не изменяют своих значений при изменении аргумента. Функция y₁ = х повторяет значения переменной х и потому просто совпадает с ней.

Единственной нетривиальной функцией является у₂ = x̅ , называемая отрицанием или инверсией ( x̅ читается «не х»). Она равна 1, когда аргумент принимает значение 0, и равна 0 при аргументе 1.

– !!!!!!!!!!!!!!!!!!!!! -