Игошин Математическая логика и теория алгоритмов (1019110), страница 23
Текст из файла (страница 23)
любое подмножество прямого произведения А х В. Если р — бинарное отношение и записано (х, у) е р, то говорят, что х и у связаны отношением р, или х находится с у в отношении р, или для хи у выполняется отношение р. Вместо записи (х, у) е р используют также запись хру. Бинарное отношениег" а А х В называется функцией, заданной на множестве А и принимающей значения в множестве В (или отображением множества А в В), если: а) для любого х в А найдется у в В, такой, что (х, у) е у"; б) для любых х е А, уь у, е В из того, что (х, у,) е,г и (х, уз) е Х следует, что у, = уь Другими словами, Г— функция, если для любого х е А существует единственный у е В, такой, что (х, у) е 1".
Этот единственный элемент у называется значением функцииу для аргумента х и обозначается г(х). Если (х, у) а г, то используется запись у =у(х). Множество А называется областью определения функции г,  — областью ее изменения. То, что /" есть функция (отображение) из А в В, записывают в виде~": А — » В или А» В. Функция у": А — » В называется иньективной (или взаимног однозначной), если для любых х„х, е А из равенства г(х,) = Дхз) непременно вытекает равенство аргументов х, = хз. Функция /: А — » В называется еюръективной (или отображением А на В), если для любого у в В найдется хотя бы один х в А, такой, что у = г(х). Функция г": А — » В называется биективной (или биекцией), если она одновременно инъективна и сюръективна.
Понятие п-ариого отношения. Обобщением понятия упорядоченной пары элементов является понятие кортежа (упорядоченного набора) объектов. Кортеж и объектов а„ан ..., а„обозначается (аь аь ..., а.). Два кортежа (а„..., а„) и (Ьн ..., Ь„) называют равными и пишут (аь „., а„) = (Ьь ..., Ь,), если и только если а, = = Ь„..., а„= Ь„. Прямым произведением и множеств Аь ..., А„называется множество А, х ... х А„= ((хь ..., х„): х, е Аь ..., х„е А„).
92 Если А, = ... = А„= А, то прямое произведение А х ... х А называют и-й прямой степенью множества А и обозначают А". При этом будем считать, что А' = А. Таким образом, п-арным отношением между элементами множеств Аь ..., А„называется любое подмножество прямого произведения А, х ... х А„, Функцией и аргументов, заданной на множестве А и принимающей значения в множестве В, называется такое (и+ 1)-арное отношение7'~ А" х В, что: а) для любых х„..., х„в А найдется у е В, такой, что (хь ..., х„, у) е /', б) для любых хь ..., А,У,га Визтого, что(хь ...,Хп,У)е,7и(хь ...,хп,г) в„т следует, что у = г. Другими словами, у — функция, если для любых хп ..., х„е А существует единственный элемент у в В, такой, что (хь ..., х„, у) е 7: Аналогично тому, как это делалось для функции одного аргумента, для функции и аргументов также вводятся понятия инъективности, сюръективности, биективности.
и 9. Булевы функции от одного и двух аргументов Булевы функции получили свое название по имени замечательного английского математика Джорджа Буля (1815 — 1864), который первым начал применять математические методы в логике. Происхождение булевых функций. В конце э 1 отмечалось, что каждое из определений 1.1, 1.3, 1.5, 1.7, 1.9 операций над высказываниями (отрицания, конъюнкции, дизъюнкции, импликации, эквивалентности) можно рассматривать как определение некоторого действия над символами 0 и 1, т.е.
как определение некоторой функции, заданной на двухэлементном множестве (О, 1) и принимающей значения в том же множестве. Символом 0 обозначалось любое ложное высказывание, а символом 1 — любое ис~инное. Например, отрицание представляет собой в этом смысле Функцию одного аргумента Ях), которая принимает следующие значения: ЯО) = 1, у;(1) = 0; конъюнкция представляет собой ФУнкцию двух аргументов 8,(х, у), принимающую следующие значения: я,(0, 0) = О, 8,(0, !) = О, 8,(1, 0) = О, 8,(1, 1) = 1 и т.д. В э 2 эта мысль была развита дальше: отмечено, что каждая формула алгебры высказываний Г(ХО Х,, ..., Х„) от и пропозициональных пеРеменных Хп Хп ..., Х„опРеделает по сУществУ некоторую функцию от и аргументов, сопоставляющую любому набо- РУ длины и, составленному из элементов двухэлементного множества (О, Ц, единственный элемент того же множества.
Этот элемент является логическим значением того составного высказывания, в которое превращается данная формула, если вместо всех ее пропозициональных переменных подставить конкретные высказывания, имеющие соответствующие значения истинности.
Легко понять, что высказывания (точнее, их содержание) здесь ни при чем. Функция, о которой идет речь, определяется структурой 93 формулы Г и определениями 1.1, 1.3, !.5, 1.7, 1.9, которые понимаются как определения действий над символами О, 1 — элементами двухэлементного множества (О, 1). В связи с этим естественно рассмотреть функции, заданные на лвухэлементном множестве (О, 1) и принимающие значения в нем же безотносительно к формулам алгебры высказываний, т.е. сами по себе. Тогда функции, определяемые таблицами в определениях 1,1, 1.3, 1.5, 1.7, 1.9, а также функции, определяемые формулами алгебры высказываний, будут служить примерами таких функций.
Такие функции, заданные и принимающие значения в двух- элементном множестве, появляющиеся в алгебре высказываний, носят название функций алгебры логики или булевых функций. Введя понятие булевой функции, мы окончательно отрываемся от того содержательного смысла, который имели в виду в алгебре высказываний: пропозициональные переменные служили там обозначениями для высказываний языка.
Теперь же остались только два символа 0 и 1 и понятие булевой функции. Чтобы еще более оттенить это обстоятельство, обозначим переменные, пробегающие множество (О, 1), малыми буквами латинского алфавита х, у, г, и, о, ..., х„х,, ..., х„, ... и будем называть их булевыми. В этой главе изучим некоторые свойства булевых функций и посмотрим, как эти функции могут применяться в алгебре высказываний и в теории релейно-контактных схем. Булевы функции от одного аргумента. Олределение 9.1.
Булевой 4ункцией от одного аргумента называется функция Г', заданная на множестве из двух элементов и принимающая значения в том же двухэлементном множестве. Элементы двухэлементного множества будем обозначать 0 и 1. Таким образом, 1': (О, 1) — > (О, 1). Нетрудно перечислить все булевы функции от одного аргумента: Составленная таблица означает, что, например, булева функция /г на аргументах 0 и 1 действует следующим образом: 1г(О) = 1 наг(1) = О. Всего имеется четыре различных булевых функций от одного аргумента: 1о(х) = 0 — функция, тождественно равная 0 (тождественный нуль); Х(х) = х — тождественная функция; Л(х) = х — функция, называемая отрицанием; Я~(х) = 1 — функция, тождественно равная 1 (тождественная единица).
Булевы функции от двух аргументов. Определение 9.2. Булевой функцией от двух аргументов называется функция е, заданная на множестве (О, 1) х (О, 1) и принимающая значения в двухэлементном множестве (О, 1). Другими словами, булева функция от двух аргументов сопоставляет любой упорядоченной паре, составленной из элементов 0 и ! (а таких упорядоченных пар будет четыре), либо О, либо 1. Перечислим все возможные булевы функции от двух аргументов в форме следующей таблицы: Заметим: функции пронумерованы так, что номер функции, записанный в двоичной системе счисления, дает последовательность значений соответствующей функции. Например, двоичная запись числа 13 имеет вид: 1101.
Соответствующая функция яп(х, у) принимает следующие значения: «ц(0, 0) = 1, яц(0, 1) = 1, бп(1, 0) = О, вц(! 1) = 1. Многие из перечисленных функций имеют названия и специальные обозначения. Приведем их, сгруппировав функции в пары по тому принципу, что каждая функция из пары является отрицанием другой функции этой пары. Первые две функции, которые рассматриваются, яь(х, у) = 0 и вц(х у) = 1 — тождественный ноль и тождественная единица. Далее, функция х,(х, у) называется конъюнкцией и обозначается х .
у (или ху). Таким образом, я,(х, у) = х у. Конъюнкция принимает значение ! в том и только в том случае, когда оба ее аргумента принимают значение 1. Отрицание конъюнкции, функция яи(х, у), называется штрихом Шеффера и обозначается х ~ у. Таким образом, яи(х, у) = (х . У)' = х ~ у. Эта функция принимает значение 0 в том и только в том случае, когда функция я,(х, у) пРинимает значение 1, т.е. в случае, когда оба ее аргумента принимают значение !. Функция я7(х, у) называется дизьюнкцией и обозначается х гу. Таким образом, е7(х, у) = х г у.
Функция яь(х, у), являющаяся отрицанием функции я7(х, у), носит название стрелка Пирса (или функция Вебба) и обозначается х ч у. Итак, я8(х, у) = (х г у)' = х ч, у. Функция яц(х, у) называется импликацией и обозначается х — > у, т. е ~ц(х, у) = х — ь у. Аргумент х в этой функции называется посыл- 95 кой импликации, а аргумент у — ее следствием. Отрицанием импликации является функция е2(х, у) = (х -+ у)'. Специального названия она не имеет. Функция еп(х, у) называется антиимпликацией или обратной импликацией, потому что представляет собой импликацию с посылкой у и следствием х.
Таким образом, «п(х, у) = у -+ х. Ее отрицанием является функция е1(х, у) = (у — ь х)', не имеющая названия. Функция яь(х, у) называется эквивалентностью и обозначается х<-+у, так что я(х, у) =х++у. Она принимает значение 1 тогда и только тогда, когда оба ее аргумента принимают одинаковые значения. Функция яъ(х, у), являющаяся отрицанием функции я9(х, у), называется сложением по модулю два, или суммой Жегалкина, и обозначается х+ у. Наконец остаются еще две пары функций. В первую пару входят функции яз(х, у) и яп(х, у). Первая из них принимает всегда те же самые значения, что и ее первый аргумент, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
