Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
Топ:
Техника безопасности при работе на пароконвектомате: К обслуживанию пароконвектомата допускаются лица, прошедшие технический минимум по эксплуатации оборудования...
Основы обеспечения единства измерений: Обеспечение единства измерений - деятельность метрологических служб, направленная на достижение...
Интересное:
Искусственное повышение поверхности территории: Варианты искусственного повышения поверхности территории необходимо выбирать на основе анализа следующих характеристик защищаемой территории...
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Национальное богатство страны и его составляющие: для оценки элементов национального богатства используются...
Дисциплины:
2017-11-22 | 301 |
5.00
из
|
Заказать работу |
|
|
(АЛГЕБРЫ ЛОГИКИ).
ТАБЛИЦЫ ИСТИННОСТИ ЭТИХ ОПЕРАЦИЙ.
1. «НЕ» - х
0 1
1 0
2. х1 х2 «ИЛИ»
х1 х2 | х1 х2 |
0 0 | |
0 1 | |
1 0 | |
1 1 |
3. Конъюкция х1& х2 «И»
х1 х2 | х1& х2 |
0 0 | |
0 1 | |
1 0 | |
1 1 |
4. Импликация х1® х2 «ЕСЛИ ТО»
х1 х2 | х1® х2 |
0 0 | |
0 1 | |
1 0 | |
1 1 |
5. Эквиваленция х1 ~ х2 «ТОГДА И ТОЛЬКО ТОГДА»
х1 х2 | х1 ~ х2 |
0 0 | |
0 1 | |
1 0 | |
1 1 |
ПРЕДСТАВЛЕНИЕ ФУНКЦИИ В АЛГЕБРЕ БУЛЯ.
Функция трех переменных:
x1 | x2 | x3 | f |
Кроме табличного задания алгебры логики применяются различные аналитические методы. К ним относятся – дизъюктивная и коньюктивная форма. Для представления в дизъюктивной соверш. норм. форме (ДСНФ) вводится фар-кая функция единицы, которая соответствует конституентам, в которых функция принимает значение = 1.
Единичная функция записывается,как элементарная конъюнкция, содержащая n – переменных и называется минитермом. Алгоритм представления функции алгебры логики в виде ДСНФ записывается в виде:
1) Выбрать в таблице функции все наборы аргументов, на которых функция обращ. в единицу
2) Вычислить конъюкцию, соответствующей этим наборам аргументам. При этом аргумент xi входит в данный набор как 1, он вписывается без изменения в конъюнкцию, соответствующую данному набору. Если хi входит как 0,то в конъюнкцию вписывается его отриц.
3) Все полученные конъюнкции соединены между собой знаками дизъюнкции.
Для примера запишем ДСНФ
f(х1,х2, х3) = 1 2 3 1 x2 3 1 2 x3 x1 2 3 x1 2 x3
x1 x2 3
Для представления функции алгебры логики в КСНФ вводится хар-кая
|
функция О,которая соответствует набору, на котором функция принимает значение О. Функция нуля записывается как элементарная дизъюнкция, содержащая n-переменных и называется макситермом.
Алгоритм построения КСНФ:
1) Выбрать в таблице функции все наборы аргументов, на которых функция обращается в О.
2) Выписать дизъюнкции, соответствующие этим наборам. При этом если хi входит как О, он вписывается без изменений в дизъюнкцию, если хi входит как 1, то в дизъюнкцию вписывается его отрицание.
Для примера запишем КНФ
f(х1,х2, х3) = (x1 x2 3) & ( 1 2 3)
По аналогии с теорией множеств при минимизации:
ДСНФ ® ДНФ
КСНФ ® КНФ
ДНФ,КНФ – обозначения для сокращения макситермами и минитермами. Номера мини- и макситермов являются дес-ными экв-ми соответствующего набора, на котором функция принимает 1 или 0 соответственно, то есть
(ДСНФ) f(х1,х2,х3) = m0 m2 m3 m4 m5 m6
(КСНФ) f(х1,х2,х3) = m1 & m7
Согласно теореме Шеннона функция в ДСНФ имеет вид:
f(х1,…,хk) = f(d1,…,dk) & x1d1* x2d2… xkdk
Функция трех переменных задана таблично:
x1 | x2 | x3 | f |
f(х1,х2, х3) = 1 2 3 1 x2 3 1x2 x3 x1 x2 x3 (ДСНФ)
Выясним каково количество возможных булевых функций к-значных.
Если мы имеем к переменных, то из них можно составить m=2к комбинаций, а так как для каждой комбинации может быть задана своя функция, то общее число возможных функций V=2m=22^k
Теорема:
Алгебра множеств с к-порожденными множествами изоморфна к-значной алгебре Буля.
Доказательство:
Изоморфизм строится следующим образом:
j (Мi)=xi - для алгебры множеств
j (fi)=yi - для алгебры Буля
Тогда согласно представлению Булевых функций в ДСНФ и представлению функций от порождающих множеств в СНФК следует следующее:
fj(Mi) = Mvdv ;
yj(xi) = xvdv ;
Основным следствием этой теоремы является возможность применения всех методов минимизации из теории множеств для алгебры Буля.
|
Метод Квайна для функции Буля:
0 0 0
0 1 0 0х0
0 1 1 х11
1 1 1
Строим таблицу Квайна:
0х0 | ||||
х11 |
Y(x1, x2, x3) = 1 3 x2x3
Минимизация по методу Карно:
х1 х2х3 | ||||
f(x1, x2, x3) = 1 3 x2x3
|
|
Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!