русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Булевы функции

Существует не более чем  различных булевых функций п переменных. К этому выводу легко прийти, пользуясь простыми комбинаторными рассуждениями, и вспомнив, что на каждом из 2n наборов функции могут принимать два значения.
Рассмотрим наиболее употребляемые булевы функции одной и двух переменных. Функции одной переменной представлены в табл. 1.3, где
f0 (x) = 0 — тождественный ноль (константа 0);
f1 (х) = х — тождественная функция;
f2 (х) =  — отрицание х (инверсия);
f3 (х) = 1 — тождественная единица (константа 1).
Функции двух переменных представлены в табл. 1.4.
Наиболее часто употребляются следующие:
f0 (x1, x2) = 0 — тождественный ноль (константа 0);
f1 (x1, x2) = — конъюнкция.
f3 (x1, x2)=x1 — повторение х1;
f5 (x1, x2) = x2 — повторение х2,

Вместо знака “•” иногда упо­требляется знак & или . Эту функцию часто называют логическим произведением или логическим умножением;

Таблица 1.3 – Функции одной  переменной

x

f1

f2

f3

f4

0

0

0

1

1

1

0

1

0

1

Таблица 1.4 – Функции двух переменных

x1

x2

f0

f1

f2

f3

f4

f5

f6

0

0

0

0

0

0

0

0

0

0

1

0

0

0

0

1

1

1

1

0

0

0

1

1

0

0

1

1

1

0

1

0

1

0

1

0

f7

f8

f9

f10

f11

f12

f13

f14

f15

0

1

1

1

1

1

1

1

1

1

0

0

0

0

1

1

1

1

1

0

0

1

1

0

0

1

1

1

0

1

0

1

0

1

0

1

 

f0 (x1, x2) = 0 — тождественный ноль (константа 0);
f1 (x1, x2) = — конъюнкция.
f2 (x1, x2)=x1 — повторение х1;
f4 (x1, x2)=x1 —запрет  х2= x1, x2 ;
f3 (x1, x2) = x2 — повторение х1,
f5 (x1, x2) = x2 — повторение х2,
f6 (x1, x2) =  — сложение по модулю 2 или сумма mod 2;
f7 (x1, x2 )=  — дизъюнкция (логическое ИЛИ);
f8 (x1, x2) =  — функция Вебба (стрелка Пирса);
f9 (x1, x2) = x1 ~ x2 — эквивалентность;
f13 (x1, x2 )= — импликация;
f14 (x1, x2) = x1 / x2 — штрих Шеффера;
f15 (x1, x2) = 1 — тождественная единица (константа 1).
Рассмотренные простейшие булевы функции позволяют строить новые булевы функции с помощью обобщенной операции, называемой операцией суперпозиции. Фактически операция суперпозиции заключается в подстановке вместо аргументов других булевых функций (в частности аргументов). Например, из функции f1 (x1, x2) c помощью подстановки x1=f3 (x4, x8), х2 = x3 вместо аргументов х1 и x2 соответственно получаем функцию f1 (f3 (х3, x4), x3). Последняя от переменных x1иx2 уже не зависит.
Операция суперпозиции позволяет увидеть качественный переход от п = 1 к п = 2. Действительно, суперпозиция функций одного аргумента порождает функции одного аргумента. Суперпозиция функций двух аргументов дает возможность строить функции любого числа аргументов (в приведенном примере построена функция трех переменных).
Суперпозиция булевых функций представляется в виде логических формул. Однако следует отметить:

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

Очевидно, среди схем, реализующих данную функцию, есть наиболее простая. Поиск логической формулы, соответствующей этой схеме, представляет большой практический интерес, а преобразование формул булевых функций основано на использовании соотношений булевой алгебры.
Для булевой алгебры определены одна одноместная (унарная) операция “отрицание”, две двухместные (бинарные) операции конъюнкция и дизъюнкция (обозначаются “•”, “” соответственно).

Просмотров: 6205

Вернуться в оглавление:Цифровые автоматы




Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Полезен материал? Поделись:

Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.