. Аксиомы теоремы и тождества алгебры логики принцип подстановки принцип двойственности метод перебора

Работа добавлена на сайт TXTRef.ru: 2019-09-03

1. Аксиомы, теоремы и тождества алгебры логики, принцип подстановки, принцип двойственности, метод перебора

Аксиомы алгебры логики. В алгебре логики рассматри-

ваются переменные, которые могут принимать только два зна-

чения — 0 и 1. В дальнейшем переменные будем обозначать

латинскими буквами x,y,z,... . В алгебре логики определены

отношение эквивалентности (=) и три операции [5]: дизъюнк-

ция (операция ИЛИ), обозначаемая знаком V, конъюнкция (опе-

рация И), обозначаемая знаком & или точкой, которую можно

опускать (например, х ¦ у = х у), и отрицание (инверсия, опера-

ция НЕ), обозначаемое чертой над переменными или над эле-

ментами 0 и 1 (например, х, О, 1). Отношение эквивалентности

удовлетворяет следующим свойствам:

х = х — рефлексивность;

если х = у, то у = х — симметричность;

если х = у и у = z, то х = z — транзитивность.

Из отношения эквивалентности следует принцип подстанов-

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

Алгебра логики определяется следующей системой аксиом:

Аксиома A.1) является утверждением того, что в алгебре ло-

гики рассматриваются только двоичные переменные, аксиомы

A.2) - A.4) определяют операции дизъюнкции и конъюнкции, а

аксиома A.5) — операцию отрицания. Если в аксиомах A.2) -

A.5), заданных парами, произвести взаимную замену операций

дизъюнкции и конъюнкции, а также элементов 0 и 1, то из од-

ной аксиомы пары получится другая. Это свойство называется

принципом двойственности.

Теоремы и тождества алгебры логики. С помощью ак-

сиом алгебры логики можно доказать целый ряд теорем и то-

ждеств. Одним из эффективных методов доказательства теорем

является метод перебора всех значений переменных: если тео-

рема истинна, то с учетом A.2) - A.5) уравнение, формулирую-

щее утверждение теоремы, должно быть истинно при подстанов-

ке любых значений переменных в обе его части. Метод перебора

не слишком трудоемок, так как переменные могут иметь только

два значения: 0 и 1. Так, методом перебора легко убедиться в

справедливости следующих теорем:

мпотентные законы

коммунитативные законы

Ассоциативные законы

дистрибутивные законы

законы отрицания

Законы двойственности (де Моргана)

Все теоремы могут быть доказаны аналитически или методом

перебора. В табл. 1.1 приведено доказательство одного из тождеств

A.13) методом перебора.

Если в логическое выражение входят операции дизъюнкции и

конъюнкции, то следует соблюдать порядок выполнения операций:

сначала выполняется операция конъюнкции, а затем — операция

дизъюнкции. Этим устанавливается иерархия операций: конъюнкция

— старшая операция, дизъюнкция — младшая. В сложных логиче-

ских выражениях для задания порядка выполнения операций исполь-

зуются скобки.

2. Операция сумма по модулю два и ее свойства

Операция сумма по модулю два (исключающее ИЛИ, логи-

ческая неравнозначность) обозначается символом ф и опреде-

ляется соотношением

Легко убедиться, что х ф у = (ж V у) ¦ (х V у). Это выражение

также можно использовать для определения операции сумма по

модулю два. Очевидно, что х ф у = хф у. На основании аксиом

алгебры логики A.2) - A.5) можно показать, что

Из данных соотношений следует, что значение х ф у совпада-

ет со значением младшего разряда суммы двух двоичных чисел,

где хну — значения младших разрядов этих чисел. Соответственно этому значение г'-го разряда суммы двух двоичных чисел будет определяться значением х,- ф yi © z,-, где ж,- и у, — значения г'-х разрядов двоичных чисел, а г,- — перенос в г-й разряд из предыдущего г — 1-го разряда. Операция сумма по модулю два коммутативна, ассоциативна и дистрибутивна относительно операции конъюнкции, т.е.

Для операции сумма по модулю два справедливы также тождества

где хр = х для всех р (формула справедлива только для одной переменной, повторенной п раз).

Для упрощения выражений, содержащих операцию ф, полезны Тождества

Операция сумма по модулю два играет особо важную роль в теории переключательных функции.

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

ки, задающие в явном виде порядок их выполнения, руководствуясь правилами:

что следует из определения A.19) операции сумма по модулю два и иерархии операций конъюнкции и дизъюнкции. После приобретения практических навыков некоторые скобки можно будет опускать, чтобы излишне не усложнять аналитические выражения. Алгебра логики тесно связана с теорией множеств [5]. Вместо опе-

раций дизъюнкции, конъюнкции и отрицания в теории множеств используются операции объединения, пересечения и дополнения. Элементам 0 и 1 соответствуют пустое множество и множество,состоящее

из всех его элементов.

3. Позиционные системы счисления

Совокупность правил записи чисел называется системой

счисления. Наиболее часто используются позиционные системы, в которых целое положительное число записывается в виде последовательности символов en_i .. .ер .. .е^ео, а вес каждого символа ер равен qp, где q — основание системы счисления, ер = 0,1,...,д— 1. Тогда любое целое положительное число Е в системе счисления с основанием q можно записать в виде:

При вычислении суммы полагаем, что все значения ер и

qp представлены в привычной десятичной системе счисления. Максимальное n-разрядное число получается при ер = q — 1 для всех р = 0,1,..., п — 1:

Таким образом, существует qn различных n-разрядных чисел (с учетом нуля). В табл. 1.2 показан перевод 16 чисел из одной системы счисления в другую для наиболее часто используемых оснований q = 2,10,8,16.

Системы счисления с основаниями q = 2к при к = 2,3,4,...

жестко связаны с двоичной системой счисления (к — 1). Для перевода чисел из этих систем в двоичную запись достаточно цифры ер = 0,1,2,.. .,2к — 1 всех разрядов числа представить jfc-разрядным двоичным кодом. Не более сложно и взаимное преобразование чисел из одной системы счисления в другую. Для общения человека с ЭВМ наиболее удобна система счисления с основанием q = 16 (к = 4), что обусловлено большей компактностью записи чисел, чем в системах счисления с q = 8 (к = 3), при приемлемом для запоминания человеком числе различных цифр (символов), используемых для обозначения всех значений разрядов.

Для кодирования информации в электронных схемах широкое применение находит унитарный код, содержащий символ 1 только в одной позиции разрядного кода (в остальных позициях проставляются символы 0), т.е. для представления информации используется специальное двоичное ее кодирование. Так, например, числа от 0 до 7 можно записать с помощью унитарного кода:

Унитарный код чаще всего применяется для кодирования

нечисловой информации.

4. Переключательные функции

Любое логическое выражение, составленное из п переменных xn,...,Xj с помощью конечного числа операций алгебры логики, можно рассматривать как некоторую функцию п переменных. В соответствии с аксиомами A.1) - A.5) функция может принимать в зависимости от значений переменных хр = О или 1 только два значения: 0 и 1. Такие функции являются весьма удобным инструментом для описания, анализа и синтеза переключательных схем, выходные сигналы которых характеризуются лишь двумя уровнями напряжения: высоким A) и низким @). В связи с этим такие функции называются переключательными (термин "переключательная" обычно будем опускать, так как никакие другие функции рассматриваться не

будут).

Значительный интерес представляют следующие невыро-

жденные функции двух переменных х% и Xj, названия которым даны по используемым для их образования операциям алгебры логики:

Так как область определения любой функции п перемен-

ных конечна BП точек), она может быть задана таблицей значений /(^t) = о,- = 0 или 1, которые она принимает в точках I/,-, где г = 0,1,..., 2П — 1. Такие таблицы называются таблицами истинности. Табл. 1.3, которая составлена в соответствии с аксиомами A.2) - A.5) для указанных выше функций двух переменных,представляет собой таблицу истинности, задающую эти функции. В предпоследнем столбце помещена функция, заданная в общем виде коэффициентами а{ = f(u{), где i = 0,1,2,3, а в последнем столбце — инверсная функция, заданная коэффициентами о, = f(fi)- Подставляя различные значения ai = 0 или 1, можно задать все 16 функций двух переменных B2 = 24 = 16). В частности, можно получить вырожденные функции:

называемые инверсиями переменных (в табл. 1.3 показаны вырожденные функции /о(*>) — константа нуль и f\{y) — константа единица).

Функция п переменных f(u) называется полностью определенной, если ее значения fiyi) = а,- = 0 или 1 заданы во всех 2™ точках щ области определения. Если же значение функции не задано хотя бы в одной точке щ, то она называется неполностью определенной. Не определенное в точке V{ значение функции будем задавать произвольным коэффициентом с,- = Ф (Ф — совмещенные символы 0 и 1, что указывает на неопределенность значения с,), т.е., если в точке i/, значение функции не

5. Принцип двойственности и закон двойственности. Теоремы разложения и связанные с ними тождества.

Алгебра логики обладает замечательным свойством, которое называется принципом двойственности: если имеет место тождество

8. Первичные термы, минтермы, макстермы и их свойства.

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

Первичные термы. Переменные хр и их инверсии хр называются первичными термами. Для первичных термов используется символическое обозначение

Для первичных термов справедливы следующие

соотношения:

Минтермы. Символическое обозначение A.62) переменных и их инверсий позволяет в общем виде записывать конъюнкцию любого числа аргументов.

9. . Совершенные нормальные формы представления функций: СДНФ, СКНФ в базисах И-НЕ и ИЛИ-НЕ.

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

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

Данная форма представления функции га переменных на-

зывается СКНФ.

10. Конъюнктивные термы. Минимизация переключательных функций. Определение МДНФ, МКНФ и МНФ в базисах И-НЕ и ИЛИ-НЕ.

11. Диаграммы Вейча, m-кубы, правила минимизации. Пример минимизации функции во всех базисах

12. Минимизация неполностью определенных функций. Комбинационные схемы. Совместная минимизация нескольких функций. Скобочные формы функций, порядок функций и КС.

13. Переходные процессы в КС. Синтез КС, свободных от состязаний.

14. Потенциальные и импульсные сигналы, операторные тождества.

15. Основная модель асинхронного потенциального автомата, функции переходов и выхода автомата.

16. Переходные процессы в АЛА (устойчивые и неустойчивые состояния автомата, три варианта переходов между внутренними состояниями). Шесть условий синтеза АПА.

17. Асинхронные потенциальные триггеры типа R-S, их синтез и анализ. Табличный метод отыскания функций возбуждения.

18.  Асинхронные потенциальные триггеры типа D-L и их синтез.

22. Синхронные триггеры типов J-K и Т: словесное описание и табличное задание их функции переходов, функции возбуждения.

24. Интегральные схемы ТТЛ серий

25. Интегральные схемы КМОП серий

20.Синхронные D-триггеры. Триггеры типов D/R и DIRS, их функции переходов.

19. Основная модель синхронного автомата. Функции переходов и выхода автомата. Переходные процессы

Другие работы

ntrgsteller-in Nme Vornme-Firm nschrift Wohno...


Kurzbeschreibung der Vernstltung bitte usf?hrliche rbeitsunterlgen beif?gen 3.2 Ist die Gesmtfinnzierung der Deutschen Tgeldquo; gesichert j nei...

Подробнее ...

180. Ацетилен ~ это вещество- с одной тройно...


Какое из ниже перечисленных веществ образуется при окислении этилена Этиленгликоль 12. Какой продукт образуется при взаимодействии CH4CL2 хлормет...

Подробнее ...

на тему- по направлению подготовки 100101 Гос...


3 Глава I Специфика организации курортно-оздоровительного туризма как одного из основных видов туризма……………………….1Основные понятия и определения к...

Подробнее ...

Вариант 1 Вариант 2


Упростите 2 ? 3b 2 3b. Упростите 7 3y 7 ? 3y. Упростите выражение . Упростите выражение .

Подробнее ...