Дати визначення булевої функції. Функції одного та двох аргументів

Мулевими функціями, називають такі функції, в яких всі аргументи як і самі функції можуть приймати лише два значення. Зазвичай це (0,1).(істина, неправда)

22. Булева функція трьох аргументів.

23. Принципи побудови таблиці істинності булевої функції.

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

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

24. Навести закони булевої алгебри.

Асоціативність

Х(уз)=(ху)з

Х+(у+з)=(х+у)+з

Комутативність

Ху=ух

Х+у=у+х

Дистрибутивність

Х(у+з)=ху+хз

Х+(уз)=(х+у)(х+з)

Ідемпотентність

Хх=х

Х+х=х

Закони для нуля, одиниці та заперечення

Х+0=Х, х+(-х)=1, х*1=х, х*(-х)=0

Правило де-Моргана

25. Дати визначення СДНФ. Принципи побудови СДНФ по булевій функції.

Досконалою диз’юнктивною нормальною формою(ДДНФ) мулевої функції називається формула, що зображена у вигляді диз’юнкції конституант одиниці даної функції.

Алгоритм переходу від формули до ДДНФ:

1) Виключити константи, використовуючи закони дій з константами.

2) Опустити знаки заперечення безпосередньо на змінні, використовуючи закони де Моргана.

3) Використовуючи дистрибутивний закон, розкрити дужки. До одержаних елементарних кон’юнкцій застосувати закони ідемпотентності й протиріччя, спросити їх і звести подібні.результати виконання вказаних дій є одержання ДНФ мулевої функції.

4) Побудувати конституанти одиниці функції введенням у кожну елементарну кон’юнкцію відсутніх змінних, використовуючи закон виключеного третього.

5) За допомогою дистрибутивного закону розкрити дужки і звести подібні, використовуючи закон ідемпотентності. Одержана формула відповідає ДДНФ функції.

26. Дати визначення СДНФ. Принципи побудови СДНФ по таблиці істинності.

Досконалою диз’юнктивною нормальною формою(ДДНФ) мулевої функції називається формула, що зображена у вигляді диз’юнкції конституант одиниці даної функції.

Алгоритм переходу від таблиці істинності до ДДНФ:

1) Виділити всі інтерпретації, на яких значення функції дорівнює одиниці.

2) Записати конституанти одиниці виду х1*х2…*х3, що відповідають відзначеним інтерпретаціями.

3) Одержати ДДНФ функції за допомогою з’єднання операцією диз’юнкції записаних конституант одиниці.

27. Навіщо та яким чином будуються карти Карно.

Карти Карно дозволяють виконувати операції склеювання та поглинання графічно.

Карта Карно для ДНФ є аналогом таблиці істинності, зображеній у спеціальній формі. Кожній конституанті одиниці відповідає одна комірка таблиці. Значення змінних розташовані так, щоб сусідні рядки і стовпці таблиці відрізняються значенням тільки однієї змінної.

Для конкретної мулевої функції карта Карно заповнюється таким чином. У клітках, що відповідають інтерпретаціям, на яких функція дорівнює одиниці, записують одиниці. Ці клітки відповідають конституантам одиниці, що присутні у ДДНФ функції. В інші клітки записують нулі.

28. Навести основні та похідні операції булевої алгебри.

.

29. Дати визначення СКНФ. Принципи побудови СКНФ по булевій функції.

Досконалою кон’юнктивною нормальною формою (ДКНФ) функцыъ називається формула, що зображена у вигляді кон’юнкції конституант нуля даної функції

Алгоритм переходу від формули до ДКНФ:

1) Виключити константи, використовуючи закони дій з константами

2) Опустити знаки заперечення безпосередньо на змінні, використовуючи закони де_Моргана.

3) За допомогою використання дистрибутивного закону, звести функцію до виду кон’юнкції елементарних диз’юнкцій. До одержаних елементарних диз’юнкцій застосувати закони ідемпотентності й виключення третього, спростити їх і звести подібні. Результатом виконання вказаних дій є одержання КНФ мулевої функції.

4) Побудувати конституанти нуля функції введення у кожну елементарну диз’юнкцію відсутніх змінних, використовуючи закон протиріччя.

5) За допомогою дистрибутивного закону звести функцію до виду кон’юнкції конституант нуля і спростити формулу, використовуючи закон ідемпотентності. Одержана формула є ДКНФ функції.

 

30. Дати визначення СКНФ. Принципи побудови СКНФ по таблиці істинності.

Досконалою кон’юнктивною нормальною формою (ДКНФ) функцыъ називається формула, що зображена у вигляді кон’юнкції конституант нуля даної функції

Алгоритм переходу від таблиці істинності до ДКНФ:

1) Виділити всі інтерпретації, на яких значення функції дорівнює нулю.

2) Записати конституанти нуля виду х1+х2…+х3, що відповідають виділеним інтерпретаціям.

3) Записавши кон’юнкцію конституент нуля, одержати ДКНФ функції.