переключательние функції

Основні поняття і визначення

Будемо розглядати тільки функції кінцевого числа аргументів. Розглянемо безліч векторів X =, координати ко

торих можуть приймати лише два значення - 0 або 1. Тоді безліч X складається з 2 n різних векторів. Порівняємо кожному вектору з X символи 0 або 1, тобто зробимо однозначне відображення множини X на безліч Y =.

Визначення 1.1.1. Функцією алгебри логіки, або перемикач-

ної функцією, називається функція, що дає однозначне відображення X в Y [1].

З цього визначення випливає, що функція f (x 1, .... X n) називається перемикальної, якщо вона, так само як і її аргументи, може приймати тільки значення з двобуквеного алфавіту, наприклад, 0 і 1.

Оскільки аргументи перемикальної функції можуть приймати тільки два значення, то область визначення будь-перемикача функції конечна. Сукупність значень аргументів називається набором і позначається a 1. ..., a i. ..., a n. де a i дорівнює 0 або 1 (i = 1, ..., n). Кожен набір може бути представлений n-розрядних двійковим числом, а кількість двійкових n-розрядних чисел дорівнює 2 n. Тому будь-яка переклю-

чательно функція може бути визначена на 2 n наборах.

Наприклад, переключательние функції двох аргументів визначені на чотирьох наборах (00, 01, 10, 11), а переключательние функції трьох аргументів - на восьми. Таким чином, перемикальна функція може бути задана таблицею, в якій перераховані всі можливі значення аргументів функції (набори) і відповідні цим наборам значення функції. Така таблиця називається таблицею істинності перемикальної функції. Приклад перемикальної функції трьох аргументів наведено в табл. 1.1.

Таблиця 1.1 Таблиця значень перемикача функції

1,1,1,1,1 - тридцять перший набір.

Набір, що містить всі одиниці (1,1, ..., 1), називають одиничним набором.

Переключательная функція n аргументів визначена на 2 n наборах, на яких вона може набувати значень 0 або 1. Тому у відповідність кожної комутаційної функції можна поставити 2 n-розрядний

двійковечисло. Кількість 2 n-розрядних двійкових чисел дорівнює 2 2 n. та-

ким чином, число різних перемикачів функцій n аргументів

звичайно і так само 2 + 2 n.

Припишемо кожної комутаційної функції номер, рівний двійковому числу, освіченій значеннями перемикача функції на всіх наборах. Цей номер записується зліва направо, починаючи зі значення функції на нульовому наборі. Наприклад, двійкове число, утворене значеннями функції з табл. 1.1, 00111010 (2). одно 58 в десятковій системі числення і функцію можна визначити таким чином:

f (x 1, x 2, x 3) = f 58 (x 1, x 2, x 3).

Приклад 1.1. Скласти таблицю істинності для перемикача функції номер 23805 чотирьох аргументів.

Рішення. Переключательная функція чотирьох аргументів визначається на 2 4 = 16 наборах (табл. 1.2). Для отримання значень функцій представимо число 23805 в двійковій системі числення: 23805 (10) = = 101110011111101 (2). Отримане двійкове число має 15 двійкових розрядів, і для подання перемикальної функції необхідно доповнити отриманий код до 16-розрядної: 0101110011111101.

Таблиця 1.2 Таблиця перемикальної функції f 23805 (x 1, x 2, x 3, x 4)

Визначення 1.1.2. Якщо дві переключательние функції f (x 1. ..., x n)

і φ (x 1. ..., x n) одного і того ж числа аргументів беруть на всіх можливих наборах значень аргументів однакові значення, то функції f і φ називаються рівними.

Факт рівності функцій f і φ записується так:

f (x 1. ..., x n) = φ (x 1. ..., x n).

Визначення 1.1.3. Переключательная функція f (x 1. ... x i-1, x i, x i + 1. ..., x n) істотно залежить від аргументу x i. якщо має місце співвідношення

f (x 1. ... x i-1. 0, x i + 1. ..., x n) ≠ f (x 1. ... x i-1. 1, x i + 1. ..., x n).

В іншому випадку говорять, що від аргументу x i функція залежить неістотно і x i є її фіктивним аргументом. Переключательная функція не зміниться, якщо до її аргументів дописати будь-яке число фіктивних аргументів або закреслити ті аргументи, які є фіктивними.

1.1. Переключательние функції одного і двох аргументів

1.2.1.Переключательние функції одного аргументу.

Існує чотири переключательние функції одного аргументу, які наведені в табл. 1.3.

Функція f 0 (x) тотожно дорівнює нулю. Вона називається константою нуль і позначається f 0 (x) = 0.

Функція f 1 (x) повторює значення аргументу і тому тотожно дорівнює змінної x.

Функція f 2 (x) приймає значення, протилежні значенням аргументу: якщо x = 0, то f 2 (x) = 1; якщо x = 1, то f 2 (x) = 0. Цю функцію називають інверсією x або запереченням x і вводять для неї спеціальне позначення

Функція f 3 (x) тотожно дорівнює одиниці. Вона називається кон-

Стант одиниця і позначається f 3 (x) = 1.

1.2.2. Переключательние функції двох аргументів. Існує шістнадцять різних перемикачів функцій двох аргументів, кожна з яких визначена на чотирьох наборах. Ці функції представлені в табл. 1.4.

У число шістнадцяти переключательних функцій входять функції, розглянуті в п.1.2.1:

Переключательние функції двох аргументів

Заборона по y

Заборона по x

Сума по модулю 2 (логічна нерівнозначність)

Логічне додавання (диз'юнкція)

Операція Пірса (стрілка Пірса)

Еквівалентність (логічна рівнозначність)

Імплікація від y до x

Імплікація від x до y

Операція Шеффера (штрих Шеффера)

Розглянемо деякі переключательние функції двох аргументів. Функція f 1 (x, y) називається кон'юнкція, або логічним множенням. Таблиця істинності цієї функції збігається з таблицею множення двох однорозрядних двійкових чисел. Можна ввести функцію n аргументів, відповідну твору n однорозрядних двійкових чисел. Така перемикальна функція дорівнює одиниці тоді і тільки тоді, коли всі її аргументи дорівнюють одиниці. Для кон'юнкції справедливі на-

x 0 = 0; x 1 = x; x x = x;

x y = y x; x x = 0.

Функція f 7 (x, y) називається диз'юнкція або логічним складанням. Ця функція дорівнює нулю тільки в тому випадку, коли всі її аргументи дорівнюють нулю. Можна ввести функцію n аргументів, відповідну логічного складання n однорозрядних двійкових чисел. така перемикача

кові функція дорівнює нулю тоді і тільки тоді, коли всі її аргументи дорівнюють нулю. Для кон'юнкції справедливі наступні співвідношення:

x 0 = x; x 1 = 1; x x = x;

x y = y x; x x = 1.

Таблиця істинності функції f 6 (x, y) збігається з таблицею додавання двох однорозрядних двійкових чисел по модулю два. Можна ввести функцію n аргументів, відповідну сумі по модулю два n однорозрядних двійкових чисел. Така перемикальна функція визначається наступною умовою: вона дорівнює одиниці, якщо число аргументів, рівних одиниці, непарній, і дорівнює нулю, якщо число таких аргументів парне. Наведемо деякі співвідношення для суми по модулю два:

x 0 = x; x 1 = x; x x = 0;

x x x = x; x y = y x.

Розглянуті шістнадцять функцій двох аргументів (будемо називати їх елементарними) дозволяють будувати нові переключательние функції наступним чином:

• шляхом перенумерации аргументів;

• шляхом підстановки в функцію нових функцій замість аргументів. Функцію, отриману з функцій f 1. f 2. ..., f k шляхом застосування

(Можливо багаторазового) цих двох правил, будемо називати суперпозицией функцій f 1. f 2. ..., f k. Наприклад, маючи елементарні функції інверсії, кон'юнкції, диз'юнкції, імплікації, заборони, додавання за модулем два, можна скласти нову Переключательная функцію:

f (x, y, z) = ((x y) z) ((y → z) x).

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

Приклад 2.1. Представити у вигляді таблиці функцію f (x, y, z) = ((x y) z) ((y → z) x).

Рішення. Функцію f (x, y, z) будемо представляти послідовно, записуючи в стовпці табл. 1.5 проміжні результати, одержувані після виконання кожної операції: