5)Мажорит и пороговые ф-и и их элементы

6) Ф-я полнота Булевых ф-й

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

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

Перечислим предполные классы булевых функций!

1) булевы функции, сохраняющие константу 0;

f (0, ..., 0) = 0.

2) булевы функции, сохраняющие константу 1;

f (1, 1, ..., 1) = 1.

3) самодвойственные булевы функции; те функции которые на противоположных наборах принимают противоположные значения

f (х₁, ..., х_n)= .

4) линейные булевы функции;

К линейным булевым функциям относят такие булевы функции, которые представимы в виде

f (х₁, ..., х_n)=,

где , a —операция “сумма по mod 2”.

5) монотонные булевы функции.

Булева функция f {х₁, ..., x_n) называется монотонной, если для любых двух наборов и , таких, что имеет место неравенство .

7)Метод Петрика

Метод используется для нахождения всех минимальных покры­тий конституент единицы и позволяет получить все тупиковые ДНФ по импликантной матрице. Суть метода заключается в следующем. По импликантной матрице строится так называемое конъюнктивное представление мипликантной матрицы. Для этого все простые импли-канты обозначаются разными буквами (обычно прописными латин­скими). После этого, для каждого i-го столбца импликантной матрицы строится дизъюнкция всех букв, обозначающих строки матрицы, пере­сечение которых с i-м столбцом отмечено крестиком. Конъюнктив­ное представление импликантной матрицы образуется как конъюнк­ция построенных дизъюнкций для всех столбцов матрицы. К конъюнк­тивному представлению матрицы могут быть применены все соотношения булевой алгебры с целью его упрощения. После раскры­тия скобок и выполнения всех возможных поглощений получается дизъюнкция конъюнкций, каждая из которых содержит все импликанты тупиковой ДНФ.

8) Особенности синтеза комбинационных схем

Комбінаційною схемою (КС) називається схема з логічних (перемикачевих) елементів, яка реалізує булеву функцію або сукупність булевих функцій.

Система функцій, що реалізується вибраною для синтезу схем сукупністю логічних елементів, завжди повинна бути функціонально повною, тобто допускати реалізацію будь-якої булевої функції на основі принципу суперпозиції. Якщо в якості системи функцій вибрані функції І, АБО, НЕ, то вважають, що реалізовано булевий базис. Проектування КС у булевому базисі найпростіше, бо методи мінімізації булевих функцій в основному орієнтовані на нього. Тому, як правило, на першому етапі КС проектується у булевому базисі з подальшим переходом у заданий базис. Якщо вибрано функції НЕ - І або НЕ - АБО, то вважають, що реалізується універсальний або монофункціональний базис. Для зручності проектування у різних системах елементів, можлива реалізація і змішаного базису.

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