Файл: Архаров В.И. Арифметические и логические основы цифровых вычислительных машин учеб. пособие.pdf

Во второй строке свободная комбинация х -В у + z обведена рамкой.

Комбинации в колонке х + у -f z, не отмеченные рамкой, яв­ ляются неопределенными, и их в расчет можно не принимать, так как в этих строках уже использовались конституенты, обращающие Д в нуль. Одинаковые комбинации переменных, обведенные рамкой, достаточно записать один раз.

Рассмотренные минимизирующие карты соответствуют разло­ жению функции на конституенты нуля. Пользуясь теми же прави­ лами, можно составить минимизирующую карту разложения функ­

Вминимизирующей карте разложения функции на конституенты

1вычеркиваются строчки, соответствующие значениям Д = 0, по­ скольку для этих строк произведения соответствующих конституентов на Д будут равны нулю. Остальные правила пользования кар­ той остаются теми же.

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

f(x, у , z) = xyz-\-xyz-{-xyz-\-xyz.

Определим значения функции Д и составим минимизирующую карту (табл. 6-9):

Т а б л и ц а 6-9

(см. таблицу 6-10).

154

Вопросы и задачи для самопроверки

1.Возможно ли применение алгоритма Куайна к переключательной функции» заданной в ДНФ?

2.Какие трудности возникают при работе с диаграммами Вейча в случае большого числа переменных?

3.Что такое импликанта переключательной функции?

4.В чем состоит усовершенствование алгоритма Куайна, предложенное МакКласки?

5.Опишите процесс заполнения импликантной таблицы.

6. Является ли представление функции с СДНФ единственным?

7.В чем состоит трудность построения МДНФ функций большого числа пе­ ременных?

8. Каким образом заполняется диаграмма Вейча при задании исходной функ­

ции в ДНФ?

11*

Глава седьмая

ИСЧИСЛЕНИЕ П Р ЕД И КАТО В

§ 1. ОСНОВНЫЕ понятия л о г и к и ПРЕДИКАТОВ

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

Для обозначения таких функций обычно применяют латинские буквы, что позволяет по форме записи отличать предикат (неодно­ родную логическую функцию) от сложного высказывания (одно­ родной логической функции), n-местный предикат можно записать в следующем виде:

Подобный предикат представляет собой переменное высказыва­ ние, истинность или ложность которого определяется набором зна­ чений предметных переменных х х, х 2, хп. Если предикат р не яв­ ляется тождественно истинным или тождественно ложным, то на одних наборах значений предметных переменных он принимает значение «истина», а на других значение «ложно».

О п р е д е л е н и е , п-местным предикатом, определенным на множествах

М г, М 2, . . . , М п,

называется выражение, содержащее предметные переменные данных множеств и обращающееся в высказывание при замене последних лю­ быми элементами множеств М х, М 2, . . . , М п соответственно. Множества М х, М 2, . . . , М п называются базисными множествами предиката, их элементы — аргументами предиката соответст­ венно первыми, вторыми, . . . , п-ми. п-местный предикат [п>- 2], все базисные множества которого совпадают, называется однород­

156

(х1; х 2, , хп) есть «истина», то говорят, что аргументы Ху, х 2, . . .

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

Два «-местных предиката, определенные на одних и тех же мно­ жествах Му, М 2, . . . , М п, называются равносильными, если зна­ чения их для любых аргументов совпадают, иначе говоря, если они удовлетворяются одними и теми же аргументами. Например, если х переменное, принимающее значение в множестве действительных чисел, то одноместные предикаты х > 2 и х — 2>-0 равносильны.

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

Пример 1. Пусть мы имеем предикаты

(7.1)

Из этих предикатов, за счет применения какой-нибудь операции

Наличие предметных переменных в предикате позволяет ввести ряд новых операций, специфических для исчисления предикатов. Построение указанных операций осуществляется с помощью так называемых кванторов. Применяются кванторы двух видов: кван­ тор общности и квантор существования.

Квантор общности — это оператор, приводящий в соответствие любому заданному одноместному предикату у = Р (х) такую дву­ значную логическую переменную г, которая принимает значение

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

Квантор существования — это оператор, приводящий в соот­ ветствие любому одноместному предикату у — Р (х) такую двузнач­ ную логическую переменную г, которая принимает значение «О»

157

Здесь подразумевается, что объекты, о которых идет речь, принадлежат той или иной фиксированной предметной области М.

Это обстоятельство позволяет считать кванторы общности и сущест­ вования обобщенной конъюнкцией и обобщенной дизъюнкцией.

Использование операций исчисления высказываний и операций

Кванторы у и з можно применять к многоместным предикатам. Однократное применение квантора к одной из п переменных «-мест­ ного предиката порождает (п— 1) местный предикат. Это позволяет рассмотреть операции кванторов у , g над многоместными преди­ катами. В этом случае с помощью кванторов для каждого предиката можно построить новые предикаты с меньшим числом свободных переменных.

§ 2. ТОЖДЕСТВЕННЫЕ ПРЕОБРАЗОВАНИЯ В ИСЧИСЛЕНИИ ПРЕДИКАТОВ

Большое значение имеет тот факт, что над формулами исчисления предикатов можно осуществлять тождественные преобразования в соответствии с простыми и обозримыми правилами; в этом заклю­ чается оперативная функция, выполняемая исчислением.

х т\ в таком случае будем говорить, что их и и2 эквивалентны и обо­ значать это так: их экв и 2.

Это легко усматривается из эквивалентности формул алгебры логики:

A i f \ A 2f \ A z, А Х/\( А2У А 3), И 1Д Л 2)У(Т11Л^з)-

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

158