На головну

Булеві функції. Повнота і замкнутість. Теорема Поста про повноту.

  1. A) повідомляється про неможливість дати відповідь по суті поставленого питання в зв'язку з неприпустимістю розголошення зазначених відомостей
  2. D-постановка
  3. FCA - франко-перевізник (... із зазначенням місця поставки).
  4. L - постановка
  5. O розробка і постановка рекламних сувенірів, установки до них;
  6. Абстрактні машини Посту і Тьюринга
  7. Агіографія Стародавньої Русі. Своєрідність житія як типу тексту, його функції.

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

Булеві функції від n змінних  можуть бути задані за допомогою таблиці істинності, що містить  рядків і  стовпців.

приклад: Розглянемо таблицю істинності якоїсь булевої функції F, яка залежить від змінних .

Булева функція n змінних F однозначно визначається  - Розрядним булевим вектором її значень  (Тобто  - Таблиця істинності функції F). Наприклад, в цьому прикладі маємо  = (00100111).

Вже згадана булева функція F приймає значення 0 на наборах 000, 001, 011 і 100, а значення 1 - на наборах 010, 101, 110 і 111.

визначення: Безліч наборів, на яких функція F приймає значення 1, називається характеристичним і позначається через .

затвердження: Число булевих функцій від n змінних .

Булеві функції (функції алгебри логіки):

  1. функція (  ) - Дорівнює 0 (1) не залежно від значення аргументу;
  2. тотожна функція х - значення функції дорівнює значенню аргументу;
  3. функція заперечення (  )-Значення функції одно протилежного значення аргументу;
  4. кон'юнкція (  ) - Дорівнює 1, коли обидва аргументи рівні 1 - Логічне множення (І);
  5. диз'юнкція (  ) - Дорівнює 0, коли обидва аргументи рівні 0 - Логічне додавання (АБО);
  6. сума по модулю два (  ) - Знайти звичайну суму і обчислити залишок від ділення на 2. Якщо парне, то «0», якщо непарна, то «1»;
  7. функція еквівалентності (  ) - Заперечення суми по модулю два (  ) Дорівнює 1, коли значення аргументів збігаються;
  8. функція імплікації (  ) - Дорівнює 0, коли  , В інших випадках 1 - Логічне слідування;
  1. стрілка Пірса (  ) - Заперечення  - Логічне АБО-НЕ
  2. штрих Шеффера (  ) - Заперечення  - Логічне І-НЕ

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

1)  володіє властивостями асоціативності:

2)  володіє властивостями коммутативности:

3) для кон'юнкції і диз'юнкції виконуються дистрибутивні закони:

4) Чи мають місце такі співвідношення між запереченням, кон'юнкція і диз'юнкція:

5) Виконуються такі властивості кон'юнкції і диз'юнкції:

Нехай є деяка система булевих функцій . замиканням цієї системи  називається мн-во функцій які можуть бути отримані їх даних, шляхом застосування всіляких підстановок. (Ex: )

Система функцій називається повної якщо її замикання збігається з мн-вом всіх булевих функцій (ex:  повні системи).

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

(Ex:  - Не замкнута;  -Замкнута;  -Замкнута, тому що )

Класи булевих функцій:

1)

2)

3)  S - клас самодвоїстих функцій (якщо  набору булевих функцій, визначається  ).

4) М - клас монотонних функцій. функція  називається монотонної, Якщо для будь-якої пари порівнюваних наборів  виконується умова:

5) L - клас лінійних функцій. функція виду  називається лінійної (Ex: )

затвердження: Всі 5 класів є замкнутими.

Доведемо замкнутість перших 4х класів:

  1. Розглянемо довільну пару функцій класу : ,  . Утворити суперпозицію підстановкою в  замість  . Знайдемо значення отриманої функції на нульовому наборі: , .
  2. Візьмемо довільні функції з класу : ,  . Утворити суперпозицію підстановкою в  замість  . Знайдемо значення отриманої функції на нульовому наборі: , .
  3. Розглянемо довільну пару порівнянних наборів:

,

Лемма1: якщо  , То з неї шляхом підстановки функцій  можна отримати константу.

Лемма2: якщо  то з неї шляхом підстановки констант 0 і 1 і функції x можна отримати функцію

Лемма3: якщо  , То з неї шляхом підстановки констант 0 і 1 і функцій  , А також, можливо, шляхом навішування заперечення над  , Можна отримати функцію

Теорема Поста про повноту: нехай  деяка система, ця система буде повною тоді і тільки тоді, коли вона не міститься ні в одному з 5 замкнутих класів. нехай  тоді

приклад:  система повна.

Док-во: (необхідність) Якщо система функцій V - повна, то вона  жодному з класів

Припустимо гидке. нехай  - Повна система:  приклад:

отримали протиріччя, тобто

(Достатність)  повна. нехай  повна.

Док-во достатності будемо проводити в три етапи.

I. Розглянемо функцію  Можливі два випадки:

1.  тоді  є константа 1, бо

Друга константа виходить з:

2.  . тоді  є  , бо

візьмемо  , Тому що ми маємо  , То в силу лемми1 з  ми можемо отримати константу. Отже, в обох випадках ми отримуємо константи 0 і 1.

II. Побудова за допомогою констант 0, 1 і функції  , функції  . Це здійснюється на основі леми 2.

III. побудова  за допомогою констант 0, 1 і функцій и  . Це здійснюється на основі леми 3.

Таким чином, ми реалізували функції  . Цим достатність доведена.




ПИТАННЯ 30 (1). | Мінімізація булевих функцій.

Системи звичайних лінійних диференціальних рівнянь з постійними коефіцієнтами | Поняття про фундаментальну системі рішень однорідної лінійної системи | Побудова загального рішення однорідної лінійної системи з фундаментальної системі рішень | Побудова фундаментальної системи рішення однорідної системи з постійними коефіцієнтами методом Ейлера | Структура загального рішення неоднорідною лінійної системи | Класифікація квазілінійних рівнянь з приватними похідними другого порядку в просторі. | ПИТАННЯ 28 (1). | Графи. Реалізація графів на площині. Дерева. | ПИТАННЯ 4 (2). | розміщення |

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