Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Булева алгебра




Пример 1.

Составить таблицу истинности функции трех переменных, заданной формулой:

 

 

Существуют такие наборы логических функций (операций), с помощью которых можно выразить любые другие логические функции.

Функционально полной системой (базисом) называют набор логических функций при помощи которого можно выразить любые другие логические функции.

Примеры функционально полных систем логических функций:

и другие.

Основополагающим и наиболее хорошо изученным является базис {&, v, -}.

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

Теорема 1. Всякая логическая функция может быть представлена булевой формулой, т.е. как суперпозиция дизъюнкции, конъюнкции и отрицания.

Следовательно система булевых функций (операций) {&, v, -} функционально полна.

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

Система операций булевой алгебры { &, v, - } функционально полна. Это означает, что переход от табличного задания любой логической функции к формуле булевой алгебры, или булевой формуле, всегда возможен.

Переход от табличного задания логической функции к булевой формуле осуществляется в 3 этапа:

1. для каждого набора значений переменных х1, х2,..., хn на котором функция f(х1, х2,..., хn) равна 1, выписываются конъюнкции всех переменных;

2. над теми переменными, которые на этом наборе равны 0, ставятся отрицания;

3. все такие конъюнкции соединяются знаками дизъюнкции.

Полученная таким образом формула называется совершенной дизъюнктивной нормальной формой (СДНФ) логической функции f(х1, х2,..., хn).

Для каждой функции СДНФ единственна (с точностью до перестановок переменных или конъюнкций).




Поделиться с друзьями:


Дата добавления: 2014-01-05; Просмотров: 415; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.011 сек.