Составление таблиц истинности для логических схем

Для логических схем, представляющих собой соединение нескольких логических элементов, в левой части таблицы перечисляются все возможные комбинации входных сигналов, а в правой части - соответствующие значения на выходе логической схемы. Очевидно, что левые части таблицы будут одинаковыми для всех функций двух переменных, для всех функций трёх переменных и т.д. Традиционно комбинации сигналов в них располагают в порядке возрастания соответствующих двоичных кодов. На рис. 1.6 приведен пример логической схемы и таблица истинности, полностью описывающая ее работу.

Рис. 1.6. Логическая схема и соответствующая ей таблица истинности

Вероятность ошибки уменьшается, если не решать задачу "в лоб", а проанализировать её работу с точки зрения уже известных нам правил логического сложения, умножения и инверсии. Очевидно, что в рассматриваемой схеме осуществляется логическое сложение нескольких логических произведений [3]. Можно записать логическое выражение, соответствующее данной схеме:

(1.1)

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

Булево выражение в виде произведения сумм называется конъюнктивной нормальной формой (КНФ).

По правилу логического сложения выражение (1.1) имеет на выходе логическую 1 только в том случае, если равно 1 хотя бы одно из четырех произведений, входящих в сумму. По правилу логического умножения каждое произведение будет равно 1 только в том случае, когда все входящие в произведение переменные равны 1. Рассмотрим все эти возможности отдельно и по порядку.

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

· Произведение будет равно 1 только тогда, когда будет выполняться условие: и (т.е. ), и , и . От значения не вошедшей в данное произведение переменной произведение не зависит. Поэтому логические 1 будут в строках таблицы истинности, соответствующих полным произведениям , в которых и одновременно , а переменная перечисляется во всех двух возможных комбинациях: .

· Произведение будет равно 1 только тогда, когда будет выполняться условие: и (т.е. ), и , и . От значения не вошедшей в данное произведение переменной произведение не зависит. Поэтому логические 1 будут в строках таблицы истинности, соответствующих полным произведениям , в которых и одновременно , а переменная перечисляется во всех двух возможных комбинациях: .

· Произведение будет равно 1 только тогда, когда будет выполняться условие: и (т.е. ), (т.е. ), и и . Поэтому логическая 1, соответствующая данному полному произведению всех переменных, будет только в той строке таблицы истинности, где .

Анализ всех этих возможностей показывает, что они могут совпадать для нескольких произведений. Например, комбинация входных переменных 0011 встречается в произведениях и . А сочетание встречается даже в трех произведениях: и в и в , и в . Это говорит о том, что для данного логического выражения есть возможности минимизации. Правила минимизации рассматриваются в лекции 2.

Ключевые термины

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

Инверсия - операция НЕ- логическое действие, при котором появление хотя бы одного логического нуля на входе даёт логическую единицу на выходе.

Инвертор - логический элемент, реализующий операцию НЕ.

КНФ - конъюктивно-нормальная форма - представление логического выражения в виде произведения сумм.

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

Логическая схема - схема, состоящая из логических элементов.

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

Логический элемент - графическое представление элементарной логической функции.

Логическое отрицание - операция НЕ, инверсия - логическое действие, при котором происходит изменение состояния на противоположное.

Логическое сложение - операция ИЛИ, дизъюнкция - логическое действие, при котором появление хотя бы одной логической единицы на входе даёт логическую единицу на выходе.

Логическое умножение - операция И, конъюнкция - логическое действие, при котором появление хотя бы одного логического нуля на входе даёт логический нуль на выходе.

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

Краткие итоги

Любая цифровая вычислительная машина состоит из логических схем. Логические схемы, в свою очередь, состоят из логических элементов. Самыми простыми логическими элементами являются элементы И, ИЛИ и НЕ. Им соответствуют функции логического умножения, сложения и инверсии.

 

 

27. ДНФ. КНФ. Элементарная конъюнкция. Элементарная дизъюнкция.

Эквивалентные преобразования - преобразования, использующие эквивалентные соотношения и правило замены.

Два правила замены:

1. Правило подстановки формулы f вместо переменной х. При подстановке формулы f вместо переменной х все вхождения переменной х в исходное соотношение должны быть одновременно заменены формулой f.

2. Правило замены подформул. Если какая-либо формула f, описывающая функцию φ, содержит f₁ в качестве подформулы, то замена f₁ на эквивалентную f₂ (f1= f₂) не изменит функции φ.

Основные эквивалентные соотношения (законы) в булевой алгебре.

Ассоциативность конъюнкции и дизъюнкции:
	(1)

 

Коммутативность конъюнкции и дизъюнкции:
	(2)

 

Дистрибутивность конъюнкции относительно дизъюнкции:
	(3)

 

Дистрибутивность дизъюнкции относительно конъюнкции:
	(4)

 

Идемпотентность:
	(5)

 

Закон двойного отрицания:
	(6)

 

Свойства констант 0 и 1:
	(7)

 

Правила де Моргана:
	(8)

 

Закон противоречия:
	(9)

 

Закон исключенного третьего:
	(10)

 

Основные эквивалентные соотношения (1) – (10) отличаются тем, что они не выводимы друг из друга и этих соотношений достаточно для выполнения любых эквивалентных преобразований.

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

Поглощение:
	(11)

 

Склеивание:
	(12)

 

Обобщенное склеивание:
	(13)

 

(14)

Приведение к дизъюнктивной нормальной форме.

Элементарная конъюнкция - конъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза.

Дизъюнктивная нормальная форма (ДНФ) - формула, имеющая вид дизъюнкции элементарных конъюнкций.

Приведении формулы к ДНФ осуществляется в 4 этапа:

1. все отрицания «спустить» до переменных с помощью (6) и (8);

2. раскрыть скобки с помощью (1), (3), (4);

3. удалить лишние конъюнкции и повторения переменных в конъюнкциях с помощью (5), (9), (10);

4. удалить константы с помощью (7).

Процедура приведения ДНФ к СДНФ состоит в расщеплении (использовании (12) в обратную сторону) конъюнкций, которые содержат не все переменные.

Приведение к конъюнктивной нормальной форме.

Элементарная дизъюнкция - дизъюнкция переменных или их отрицаний, в которой каждая переменная встречается не более одного раза.

Конъюнктивная нормальная форма (КНФ) - конъюнкция элементарных дизъюнкций.

Пусть ДНФ F имеет вид F=k₁Úk₂Ú…Úk_m, где k_1,k_2,…,k_m - элементарные конъюнкции. Приведение ДНФ к КНФ состоит из двух шагов:

1. Применить к F правило двойного отрицания и привести к ДНФ k¢₁Ú k¢₂Ú…k¢_p где k¢₁Ú k¢₂Ú…k¢_p - элементарные конъюнкции. Тогда

2. С помощью правил де Моргана освободиться от второго отрицания и преобразовать отрицания элементарных конъюнкций в элементарные дизъюнкции D₁,D₂,…D_p Тогда

Совершенная КНФ (СКНФ) - КНФ, каждая элементарная дизъюнкция которой содержит все переменные.