Таблицы истинности и таблицы решений

Табличный способ представления БФ является одним из самых удобных.

Таблицей истинности (ТИ) называется таблица, в левой части которой расположены наборы значений аргументов в порядке возрастания их номеров (наборы таких значений соответствуют числам записанных в двоичной системе счисления – таким образом, последующий набор значений аргументов ТИ можно получить добавлением единицы к младшему разряду предыдущего набора), а в правой части указаны значения БФ для каждого из наборов. Например, табл. 1.4 является ТИ для БФ вида Очевидно, что табл. 1.1, 1.2 также являются ТИ для БФ вида

Таблица 1.4

С помощью ТИ очень просто представить БФ в СДНФ или СКНФ.

Для получения СДНФ из ТИ отбираются все входные наборы, для которых . Далее, для каждого из таких наборов составляются произведения, которые затем суммируются. Для получения СКНФ из ТИ отбираются все входные наборы, для которых . Далее, для каждого из таких наборов составляются суммы инверсий переменных, которые затем перемножаются.

СДНФ и СКНФ для БФ, заданной табл. 1.4, соответствуют СДНФ и СКНФ, рассмотренным в разделе 1.2.

Рассмотрим пример. Для формульно заданной БФ следующего вида

табл. 1.5. является ТИ.

Рассматривая строки табл. 1.5 с номерами 2, 10, 13-16, получаем СДНФ:

Рассматривая строки табл. 1.5 с номерами 1, 3-9, 11-12, получаем СКНФ:

Таблица 1.5

Таблицей решений (ТР) называется таблица, в которой некоторым наборам значений аргументов из множества сопоставлены значения функции из множества . Таким образом, принципиальным отличием ТР от ТИ является то, что количество наборов значений аргументов в общем случае не равно . В силу этого, наборы значений аргументов могут располагаться в ТР в произвольном порядке. Когда значение переменной для данного набора аргументов не влияет на значение функции, в соответствующем месте ТР ставится символ «–». Табл. 1.6 является ТР.

Таблица 1.6

№ строки
		–
	–
			–

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

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

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

Проанализируем табл. 1.6. Каждая из первых трех строк ТР из-за безразличных значений переменных , и соответственно может быть записана в виде двух строк (табл. 1.7).

Таблица 1.7

№ строки

Из табл. 1.7 видно, что четвертая строка «покрывается» первой, ее можно без последствий исключить. Частично перекрывают друг друга также вторая и третья строки (комбинация 111), поэтому в силу того, что эти строки еще содержат уникальные комбинации 011 и 110, данную избыточность можно устранить, заменив вторую и третью строки входными наборами 011, 110 и 111. Из табл. 1.7 также можно заключить, что исходная ТР непротиворечива (противоречивой ТР была бы в случае, например, в четвертой строке). Из табл. 1.7 также видно, что данная ТР не является полностью определенной – значения БФ не определены для входных наборов 001, 100, 101. Рассмотрим различные способы доопределения ТР.

Может быть принято решение о том, что на незаданных наборах входных переменных . В данном случае происходит доопределение нулями. В результате подобного доопределения табл. 1.6 преобразуется в табл. 1.8.

В соответствии с правилом построения СДНФ по ТИ получаем:

Таблица 1.8 Таблица 1.9

	–				–
Иначе		Иначе

Может быть принято решение о том, что на незаданных наборах входных переменных . В данном случае происходит доопределение единицами. В результате подобного доопределения табл. 1.6 преобразуется в табл. 1.9.

В соответствии с правилом построения СКНФ по ТИ получаем:

.

Может быть принято решение о том, что на незаданных наборах входных переменных значения безразличны. В данном случае происходит безразличное доопределение. Так как в этом случае появляется возможность выбрать значения функции таким образом, чтобы получившаяся БФ была как можно более простой (минимальной), то правило «Иначе» в этом случае применять нецелесообразно и незаданные входные наборы следует записать в таблицу в явном виде (табл. 1.10). Безразличные значения БФ будем обозначать символом d.

Таблица 1.10

	–
			d
			d
			d

В следующей главе будет показано, как использовать данную информацию для минимизации БФ с помощью карт Карно.