КАТЕГОРИИ: Архитектура-(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, входят как функции, существенно зависящие от всех п аргументов, так и функции, для которых часть из этих аргументов являются фиктивными. Теорема 2. Число всех функций алгебры логики, существенно зависящих от п аргументов, определяется следующим рекуррентным соотношением:
В этом соотношении Ai есть число функций алгебры логики, существенно зависящих от i аргументов. Правая часть соотношения есть разность между числом всех функций алгебры логики и суммой всех функций алгебры логики, зависящих существенно от любого числа аргументов, меньшего чем п. Справедливость приведенного соотношения очевидна. Рассмотрим одиннадцать функций, которые играют большую роль в построении теории функций алгебры логики и ее приложениях. Эти функции мы будем называть в дальнейшем элементарными. Рассмотрение множества элементарных функций алгебры логики начнем со случая п =0. В силу теоремы 1 в этом случае имеются только две функции, совпадающие с константами 0 и 1: Обе эти функции мы будем считать элементарными. Для п =1, согласно теореме 1, имеем 22 =4 различные функции, представленные в таблице 1.6. Таблица 1.6 –
В этом случае только функции f3 и f4 существенно зависят от х1, а для функций f1 и f2 этот единственный аргумент является фиктивным. Эти две функции определяются таблицей 1.7 Таблица 1.7 – Логические функции повторения и отрицания
Эти две функции мы также причислим к элементарным, будем их называть функциями повторения и отрицания и записывать следующим образом:
Найдем число функций алгебры логики, существенно зависящих от двух и трех переменных. Из примера (таблица 1.6) вытекает, что А0 =2 и А1 = 2. Применяя теорему 2, имеем:
В случае п = 2 в силу теоремы 2 имеем десять различных функций, существенно зависящих от аргументов х1 и х2. Из этих десяти функций к элементарным функциям будем относить следующие семь функций (таблица 1.8):
Таблица 1.8 – Элементарные логические функции двух переменных Функция f5, определяемая этой таблицей, носит название дизъюнкции х1 и х2 или логического сложения х1 и х2. Для ее обозначения применяются следующие символы:
Мы на протяжении всего дальнейшего изложения будем называть функцию f5 дизъюнкцией и обозначать дизъюнкцию х1 и х2 при помощи символа +. Функция f6 носит название конъюнкции или логического умножения х1 и х2. Для ее обозначения применяется символ Вместо этого символа часто применяют точку или вообще опускают всякий знак между х1 и х2, т. е.
В дальнейшем там, где это необходимо, будем употреблять для конъюнкции символ &, а в остальных случаях всякий знак между х1 и х2 будем опускать. Функция f7 носит название функции эквивалентности или функции равнозначности. Для ее обозначения применяются следующие два символа:
В дальнейшем будем называть эту функцию эквивалентностью х1 и х2. Для ее обозначения будем употреблять первый из двух вышеприведенных символов. Функция f8 носит название импликации х1 в х2. Она обозначается следующим образом:
Функция f9 носит название функции Вебба и обозначается следующим образом:
Функция f10 называется функцией Шеффера и обозначается следующим образом:
Функция f11 обычно называется функцией сложения по модулю два (реже ее называют функцией разноименности). Для ее обозначения употребляются символы
В дальнейшем будем употреблять для обозначения функции сложения по модулю первый символ . Функции конъюнкции и дизъюнкции обладают рядом свойств, аналогичных свойствам обычных операций умножения,и сложения. Легко убедиться в том, что для этих функций имеют место сочетательный:
переместительный:
и распределительный законы конъюнкции относительно дизъюнкции:
Кроме того, имеет место распределительный закон дизъюнкции относительно конъюнкции:
который не имеет места в обычной алгебре, так как если бы он существовал, то он бы имел следующий вид:
Проверим справедливость этого закона путем сравнения таблиц для функций, стоящих в левой и правой частях рассматриваемого соотношения. Совпадение построенных таблиц доказывает наше утверждение. Рассмотрим теперь ряд простых, но весьма важных соотношений:
Из (1.18) как следствие получаем: Как обобщение получены следующие формулы, обычно называемые формулами де Моргана:
Рассмотренные одиннадцать функций позволяют строить новые функции алгебры логики двумя основными путями: 1) путем перенумерации аргументов; 2) путем подстановки в функцию новых функций вместо аргументов. Функцию, полученную из функций f1, f2, …, fk и путем применения (возможно многократного) этих двух правил, будем называть суперпозицией функций f1, f2, …, fk.. Имея, например, элементарные функции отрицания, дизъюнкции, эквивалентности и импликации, можно составить другие функции алгебры логики, являющиеся суперпозициями этих функций. Используя таблицы состояния (истинности) можно задавать в них любую функцию.
Дата добавления: 2014-11-18; Просмотров: 735; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |