Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Минимальные термы





Выражение вида x 1 s 1Ù…Ù xnsn, которое присутствует в следствии 2 теоремы о разложении булевой функции по переменным, имеет большое значение в теории булевых функций и носит специальное название: минимальный терм, или совершенный одночлен, или конституанта единицы, или, наиболее коротко, минтерм. Нетрудно видеть, что минтерм – это реализация булевой функции n переменных, которая имеет значение 1 ровно на одном наборе значений переменных, а именно на наборе (s 1,…, sn). Отсюда и из следствия 2 непосредственно следует

СЛЕДСТВИЕ 3 [к теореме о разложении булевой функции по переменным] Любую булеву функцию, кроме 0, можно представить как дизъюнкцию некоторых минтермов.

Ясно, что при фиксированном n имеется ровно 2 n различных минтермов. Обычно минтерм обозначают mi, где i Î0..(2 n –1), i называется номером минтерма, или прямо указывают булевский вектор (s 1,…, sn), на котором минтерм принимает значение 1. Из структуры формулы, задающей минтерм, непосредственно следует, что двоичное представление номера минтерма задает тот набор значений (в установленном порядке), на котором минтерм принимает значение 1.

Говорят, что система булевых функций ортогональна, если их конъюнкция есть тождественный ноль. Нетрудно видеть, что имеет место следующая

ЛЕММА 1 Любое множество из двух или более различных минтермов ортогонально.

Говорят, что система булевых функций выполнима, если их дизъюнкция не есть тождественный ноль. Нетрудно видеть, что имеет место следующая

ЛЕММА 2 Любое множество минтермов выполнимо.

Двойственным к минтерму является макстерм — булева функция, которая принимает значение 0 на единственном наборе значений переменных. Ясно, что макстерм реализуется формулой x 1 s 1Ú…Ú xnsn. Используя принцип двойственности, на макстермы нетрудно распространить все наблюдения, которые сделаны для минтермов.

 

Date: 2015-07-23; view: 568; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.01 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию