На головну

Поняття булевої функції

  1. Help імя_M-функції
  2. I. Конституційний лад РФ: поняття, структура і базові характеристики.
  3. I. Поняття відповідальності за порушення зобов'язання
  4. III.1. Поняття грошового обігу. Готівковий і безготівковий грошовий обіг
  5. IV. Громадянське суспільство: поняття, структура, основні конституційні початку.
  6. Sf 30. Поняття "суспільство". Основні філософські концепції

Булеві функції отримали свою назву на ім'я чудового англійського математика Джорджа Буля (1815-1864), який першим почав застосовувати математичні методи в логіці.

Булеві функції від одного аргументу. Визначення 9.1. Булевой функцією від одного аргументу називається функція f , Задана на безлічі з двох елементів і приймаюча значення в тому ж двоелементною безлічі. Елементи двоелементною безлічі будемо позначати 0 і 1. Таким чином, f : {0,1} ® {0,1}. Неважко перерахувати всі булеві функції від одного аргументу:

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

Складена таблиця означає, що, наприклад, булева функція f2 на аргументах 0 і 1 діє таким чином: f2 (0) = 1 і f2 (1) = 1.

Булеві функції від двох аргументів. Визначення 9.2. Булевой функцією від двох аргументів називається функція g, Задана на множині {0,1} '{0,1} і приймаюча значення в двоелементною множині {0,1}. Іншими словами, булева функція від двох аргументів зіставляє будь впорядкованої парі, складеної з елементів 0 і 1 (а таких упорядкованих пар буде чотири), або 0, або 1. Перерахуємо всі можливі булеві функції від двох аргументів у формі такої таблиці:

  X
  Y
g0
· g1
 ® ' g2
x g3
' g4
y g5
+ g6
U g7
? g8
« g9
y' g10
  g11
x' g12
® g13
| g14
g15

Визначення 10.1. Булевой функцією від п аргументів називається функція f , Задана на множині {0,1}n і приймає значення в двоелементною множині {0,1}. Іншими словами, булева функція від п аргументів зіставляє кожному впорядкованому набору довжини п, складеним з елементів 0 і 1, або 0, або 1. Булева функція f від п аргументів x1, ..., xn позначається так: f (x1, ..., xn).

Дві булеві функції від п аргументів f (x1, ...,xn) І g (x1, ...,xn) Називаються рівними, якщо будь-яким однаковим набором значень аргументів x1, .., xn обидві ці функції зіставляють однакові елементи з множини {0, 1}, т. е. f (a1, ..., an) = g(a1, ..., an) Для будь-яких елементів a1, ..., an I {0,1}.

Визначення 10.2. суперпозицією булевих функцій  в булеву функцію f(x1, ...,xn) Називається нова булева функція, що виходить з функції f (x1, ..., xn) Підстановкою замість (всіх або деяких) аргументів x1, ..., xn функцій g1, ..., gn відповідно  отримана функція  залежить від m1 + m2 + ... + mn аргументів.

Наведемо ще одну процедуру, яку можна проробляти з булевими функціями. Зафіксувавши один з аргументів булевої функції f (x1, ..., xn) Від п аргументів, т. е. надавши цьому аргументу яке-небудь конкретне постійне значення (з двоелементною безлічі {0, 1}), отримаємо функцію від n -1 Аргументів. Так, фіксуючи в функції f (x1, ..., xn) k-й аргумент можемо отримати дві нові булеві функції від n -1 Аргументів.

теорема 10.3 (Про число булевих функцій від п аргументів). число різних

булевих функцій від п аргументів одно 22n.

Вираз булевих функцій через кон'юнкцію, диз'юнкцію і заперечення.У нас вже виникали питання щодо висловлення одних булевих функцій через інші, і на деякі з них ми вже дали відповідь. Як буде показано нижче, існують такі булеві функції (вже добре відомі нам), через які виражаються все (взагалі все, від будь-якого числа аргументів!) Булеві функції. Цим чудовим властивістю володіють взяті разом, диз'юнкція і заперечення. Перш ніж сформулювати і довести основну теорему цього пункту, звернемося до наступної важливої ??лемме.

Лемма 10.4 (Про розкладанні функції по змінній). Для довільної булевої функції f (x1, ..., xn ) справедливі такі формули, звані формулами розкладання цієї функції по змінній x1 :

теорема 10.5 (Про подання булевих функцій через кон'юнкцію, диз'юнкцію і заперечення). Будь-яка булева функція f (x1, ..., xn) може бути представлена ??у вигляді суперпозиції кон'юнкції, диз'юнкції і заперечення; причому знак заперечення варто тільки безпосередньо біля змінної і не варто ні перед однією з внутрішніх дужок. До до а із а т е л ь с т в о вестимемо методом математичної індукції по числу п аргументів функції f




Два властивості логічного слідування. Дотримання і равносильность формул. | Повні системи булевих функцій.

моделювання середовища | Модель коливальні системи | Кінетичні і структурні моделі в хімії | Математичні моделі в біології | Моделі в економіці | Генерування випадкових чисел розподілених по експонентному, нормальному і довільно заданому закону розподілу. | Характеристики послідовності випадкових чисел | Формула Літтла | Висловлювання і логічні операції над ними. | Логічне слідування формул алгебри висловлювань. Посилки і слідства. |

© um.co.ua - учбові матеріали та реферати