Суперпозиція функцій алгебри логіки
Головна | Про нас | Зворотній зв'язок
Суперпозиція - основна операція, яку можна виробляти над логічними функціями. Суперпозиція - це утворення нової функції з декількох вихідних.
Суворе визначення суперпозиції дається по індукції.
Визначення. Нехай - кінцева система логічних функцій. Функція називається елементарної суперпозицией або суперпозицією рангу 1 функцій системи. якщо вона отримана одним з наступних способів
а. З будь-якої функції перейменуванням якийсь із її змінних xij. буква xij замінюється деякою буквою y. В цьому випадку . Зокрема, буква y може збігатися з однією з змінних xis функції. Тоді говорять про ототожнення змінних xij і xis.
Приклад. Нехай. Тоді - це суперпозиції рангу 1;
б. Підстановкою деякої функції замість якогось аргументу xij однією з функцій.
Тоді. Ця функція залежить від аргументів xi1, ..., xij-1. xij + 1, ...,. xr1, ...,.
Приклад. В умовах попереднього прикладу функції. . . - це суперпозиції рангу 1.
Визначення. Суперпозиції рангу 1 утворюють клас. суперпозиций рангу 1. Суперпозиції рангу 1 функцій з безлічі утворюють клас, ..., суперпозиції рангу 1 функцій з безлічі утворюють клас суперпозиций рангу p + 1 функцій вихідної системи.
Визначення. Суперпозицією функцій з системи називається всяка функція, що входить в якійсь із класів. р = 0,1,2, .... З десь - вихідна система функцій (суперпозиції рангу нуль).
Приклад. Функції. . . . - це суперпозиції функції системи
Зауваження 1. Якщо функції і мають однакові таблиці істинності, відрізняючись тільки позначеннями змінних, то кожна з них є суперпозицією інший.
Зауваження 3. Якщо всі функції вихідної системи мають деяким властивістю, що успадковується всякої суперпозицией рангу 1, то цим властивістю володіють всі функції з системи, ..., системи, ..., все суперпозиції функцій з.
Зауваження 4. Описуючи правила побудови формули, ми неявно користувалися поняттям суперпозиції, адже будь-яка формула - це суперпозиція функцій x
y. і символів констант 0 і 1.
Приклади розв'язання задач.
Довести равносильности: (один із законів де Моргана);
Рішення. Складемо таблицю істинності деяких із зазначених функцій (табл. 7).