Составим критериальную таблицу для другой полной системы функций из Р2: {0, 1, x1x2, x1Åx2}.
Составим критериальную таблицу для другой полной системы функций из Р2: {0, 1, x1x2, x1Åx2}. - раздел Образование, УСМАНОВА Зинира Масгутовна
Т0
Т...
Т0
Т1
L
M
S
+
-
+
+
-
-
+
+
+
-
x1x2
+
+
-
+
-
x1Åx2
+
-
+
-
-
Согласно критериальной таблице, полной является и система {1, x1x2, x1Åx2}. Константа 0 введена в эту систему для удобства, тогда мы можем записать полином Жегалкина в виде, где аравны 0, если члены хх...х, в полиноме отсутствуют.
4. Выясним, полна ли система . Составим критериальную таблицу, очевидно . Чтобы показать, что , достаточно найти одну функцию и . Возьмем , удовлетворяющую требуемым условиям. Если f ST0, то f(0, ..., 0) = 1, f(1, ..., 1)=0, следовательно, fM, fT1. Рассмотрим функцию h = x1x2x2x3x1x3=1, набор ее значений (11101000), hST0, но hL. Следовательно, критериальная таблица имеет вид:
Т0
Т1
L
M
S
LT1
-
+
+
-
-
ST0
-
-
-
+
-
и А – полная система функций.
Определение.Система функций {f1, ..., fs, ...} называется базисом в Р2,если она полна в Р2, но любая ее подсистема не будет полной. Например, система функций {x1&x2, 0, 1, x1x2x3} – базис.
УСМАНОВА Зинира Масгутовна
Дискретная математика
Функции алгебры логики
Учебное пособие
Редактор Г.Р. Орлова
Редакционно – издательский комплекс УГАТУ
450000, Уфа-центр, ул. К. Маркса, 12
Содержание
Введение ………………………………………………………...............3
1. Элементы комбинаторики ……………………………………...
Полные системы
1. P2 – полная система.
2. Система M={x1&x2, x1Úx2,
Теорема Жегалкина
Каждая функция из может быть представлена в виде полинома Жегалкина единственны
Теорема о достаточности четырех функций.
Из любой полной в Р2 системы функций можно выделить полную подсистему, состоящую не более чем из четырех функций.
Доказательство. Пусть {f
Задачи и упражнения по функциям алгебры логики
При оперировании с функциями алгебры логики бывают полезны следующие эквивалентности (большинство из них называют обычно основными эквивалентностями алгебры логики). Построив таблицу для соответств
Минимизация нормальных форм
Минимальной ДНФ (МДНФ) функции f(x1, ... ,xn) называется ДНФ, реализующая функцию f и содержащая минимальное число символов пе
Алгоритм Квайна построения сокращенной ДНФ.
1. Получить СДНФ функции f.
2. Провести все операции неполного склеивания.
3. Провести все операции поглощения.
Пример 1. Построим сокращенную
Метод Блейка
Метод Блейка для построения сокращенной ДНФ из произвольной ДНФ состоит в применении правил обобщенного склеивания и поглощения. Подразумевается, что правила применяются слева направо. На первом эт
Построение всех тупиковых ДНФ.
Пусть f(x1, …, xn) есть функция алгебры логики.
1. Построим СДНФ функции f, и пусть P1, P2, …,P
Минимизация частично определенных функций
Пусть функция f(x1,…,xn) частично (не всюду) определена. Если f не определена на p наборах из 0 и 1, то существует 2p возм
Метод минимизирующих карт Карно
При построении сокращенных ДНФ для функций, зависящих от небольшого числа (не более 4) переменных, используется метод карт Карно. Построение карт Карно основано на свойствах булева
Задачи по алгебре высказываний
1.Записать следующие высказывания в виде пропозициональных форм, употребляя пропозициональные буквы для обозначения атомарных высказываний, т.е. таких высказываний, которые не пост
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов