ОСНОВЫ МАТEМАТИЧEСКОЙ ЛОГИКИ 3

(x v y v z) ? (x v y v z) ?(x v y v z)(x v y v z )(x v y v z)(x v y v z)(x v y v z).
(х v y v z)(х v у v z)(x v у v z) (х v y v z)(x v y v z)(х v y v z)(x v y v z).
(х v y v z)(x v у v z) — СКНФ.
Всякая формула алгебры логики приводится к нормальной форме следующим путем:
1. С помощью законов де Моргана (20), (21) формула преобразуется к
такому виду, чтобы знаки отрицания относилась только к отдельным переменным.
2. На основании пepвого (14) или второго (15) дистрибутивного закона формула приводится к дизъюнкции конъюнкций или конъюнкции дизъюнкция.
3. Полученное выражение упрощают в соответствии с равносильностями (8), (3), (9),(2). Например:

(xy v yz)x v?(ху v уz)(х v v) ? (xy v yz)x v (xy v yz)v?xy v x yz v хуv v yzv — ДНФ
(xy v yz)xv ? (xy v yz)(x v v)? (x v yz)(y v yz)(x v v) ? (x v y)(x v z)
(у v у) (у v z) (х v v ) ? (х v у) (х v z) (y v z) (х v v) — КНФ.
Члены ДНФ (КНФ), представляющие собой элементарные конъюнкции (дизъюнкции) n-букв, называют минитермами (макстермами) n-ro ранга.
Так, в приведенном примере: xy - минитерм второго ранга, xyz - минитерм третьего ранга, а (х v у) - макстерм второго ранга.
Если исходная формула содержит другие операции, то они предварительно выражаются через &, v и ?. Например, с учетом (23), (25), (20), (21) и (3) приведем к ДНФ следующую формулу:
x ?(х ~ z)(y ?z) v х ? z ? х v (х v z)(x v z) (y v z) v x v z ?
? х (х v z) (x v z)(у v z) v xz ? х (xz v xz) ? (у v z) v хz ?
? (xxz v xxz)(y v z) v хz ? xz (y v z) v хz ? xyz v xzz v xz ? xyz v xz.
Любая формула алгебры логики может быть представлена в СДНФ или СКНФ с помощью равносильностей (5), (2) или (б), (3) и (15).
Для перехода от СДНФ к СКНФ требуется: а) образовать логическую сумму дизъюнктивных членов, не входящих в СДНФ; б) заменить аргументы их отрицаниями, знак конъюнкции — на знак дизъюнкции и знак дизъюнкции — на знак конъюнкции.
В практических приложениях поставленную задачу удобнее представить в виде таблицы соответствия, где наборам значений переменных соответствует истинностное значение функции. Рассмотрим способ получения аналитической формы непосредственно по таблице истинности для произвольной булевой функции. Для этого введем понятие конституенты.
Конституентой единицы называется функция f (х1,х2,…, xn), принимающая значение единицы только на единственном наборе.
Конституента единицы записывается как логическое произведение и различных булевых переменных, некоторые из которых могут быть с отрицаниями. Например из таблицы 2.4 (вторая строка) х1* х2* х3 — элементарное логическое произведение, являющееся конституентой единицы переменных х1,х2, x3 принимает значение 1 на единственном наборе 001. Если вспомнить, что дизъюнкция равна 1 (7), когда хотя бы одна из переменных принимает значение 1, то можно выразить любую булеву функцию как дизъюнкцию конституент единицы, соответствующих тем наборам, на которых функция равна 1. Из таблицы 2.4 находим:
Таблица 2.4 — Таблица истинности

х1 х2 х3 f1 f2
0
0
0
0
1
1
1
1 0
0
1
1
0
0
1
1 0
1
0
1
0
1
0
1 0

1
0
1
0
0
1 0
0
0
1
0
1
1
1

f1= х1 х2 х3 v х1 х2 х3 v х1 х2 х3 v х1 х2 х3
f2= х1 х2 х3 v х1 х2 х3 v х1 х2 х3 v х1 х2 х3

Получили значения функций в СДНФ.
Заметим, что наборы, на которых функция f принимает значение 1, называют единичными, остальные — нулевыми наборами.
Алгоритм перехода от табличного задания функции к записи этой функции в виде совершенной дизъюнктивной нормальной формы (СДНФ) формулируется следующим образом:
1. Выбрать в таблице задания функции все наборы аргументов, на которых функция обращается в единицу.
2. Выписать конъюнкции, соответствующие этим наборам аргументов. При этом, если аргумент х, входит в данный набор как 1, он записывается без изменения в конъюнкцию, соответствующую данному набору. Если же х входит в данный набор как 0, то в соответствующую конъюнкцию вписывается его отрицание.
3. Все полученные конъюнкции соединяются между собой знаками дизъюнкции.
Пример 2.2 Пуст функция f (х1,х2, x3 ) задана следующей таблицей:
0

х1 х2 х3 f (х1,х2, x3 ) х1 х2 х3 f (х1,х2, x3 )
0
0
0
0 0
0
1
1 0
1
0
1 0
0
0
1 1
1
1
1 0
0
1
1 0
1
0
1 1
0
1
0

Требуется получить для нее совершенную дизъюнктивную нормальную форму.
Для нахождения СНДФ выбираем из таблицы только те строки, в которых стоят наборы значений аргументов, обращающие функцию в единицу. Это четвертая, пятая и седьмая строки. Выписываем конъюнкции, соответствующие выбранным строкам:
х1 х2 х3 , х1 х2 х3 , х1 х2 х3
Соединяя зги конъюнкции знаками дизъюнкции, окончательно получаем:
f(х1, х2 ,х3 ) = х1 х2 х3 v х1 х2 х3 v х1 х2 х3
Нельзя ли вместо дизъюнкции использовать какую-либо другую функцию алгебры логики? Чтобы выполнялось соотношение, подобное СДНФ, необходимо, чтобы при обращении любой из характеристических функций в единицу все выражение обращалось в единицу, а при обращении всех характеристических функций в нуль все выражение также становилось равным нулю. Доказано [5], что этим условиям соответствует логическая операция сложения по модулю 2 и любая таблично заданная функция алгебры логики может быть представлена в виде полученном из СДНФ путем замены знака дизъюнкции знаком сложения по модулю 2. Такую форму представления функции называют полиномиальной совершенной нормальной формой (ПСНФ). Так, для функции примера 2.2, ПСНФ имеет следующий вид:
f(х1, х2 ,х3 ) = х1 х2 х3 х1 х2 х3 х1 х2 х3
Кроме представления функций алгебры логики в СНДФ, возможно представление ее другой форме, двойственной по отношению к СДНФ.
Конституентой нуля называется функция, принимающая значение 0 на единственном наборе. Конституента нуля записывается в виде элементарной дизъюнкции всех переменных. Каждому набору соответствует своя конституента нуля. Например, набору 011 переменных (четвертая строка таблицы 2.4) х1,x2,х3 соответствует конституента нуля (х1 v х2 v х3). СКНФ представляется как конъюнкция конституент нуля, соответствующих нулевым наборам функции:
f 1= (х1 v х2 v х3 ) (х1 v х2 v х3 ) (х1 v х2 v х3 ) (х1 v х2 v х3 )
f 2= (х1 v х2 v х3 ) (х1 v х2 v х3 ) (х1 v х2 v х3 ) (х1 v х2 v х3 )

Алгоритм построения СКНФ:
1. Выбрать в таблице задания функции все наборы аргументов, на которых функция обращается в нуль.
2. Выписать дизъюнкции, соответствующие этим набором аргументов. При этом, если аргумент хi, входит в данный набор как 0, он вписывается без изменения в дизъюнкцию, соответствующую данному набору. Если же хi, входит в данный набор как 1, то в соответствующую дизъюнкцию вписывается его отрицание.
3. Все полученные дизъюнкции соединяются между собой знаками конъюнкции.
Как следует из алгоритмов построения СДНФ и СКНФ, выбор той или иной формы аналитической записи определяется видом таблицы заданной функции. Если большинство значений данной функции нулевое, то выгодно записывать ее в СДНФ, в противном случае более экономную запись дает СКНФ.
Пример 2.3 Написать СКНФ для функции, заданной следующей таблицей:

х1 х2 х3 f (х1,х2, x3 ) х1 х2 х3 f (х1,х2, x3 )
0
0
0
0 0
0
1
1 0
1
0
1 0
1
1
0 1
1
1
1 0
0
1
1 0
1
0
1 1
1
1
0

f (х1,х2, x3 ) = (х1 v х2 v х3 ) (х1 v х2 v х3 ) (х1 v х2 v х3 )
Можно вместо конъюнкции использовать функцию эквивалентности [5], тогда для функции из примера 2.3 это представление получит следующий вид:
f (х1,х2, x3 ) = (х1 v х2 v х3 ) ~ (х1 v х2 v х3 ) ~ (х1 v х2 v х3 )
На основании (2.37) можно заменить конъюнкцию импликацией и отрицанием. Для этого достаточно вхождения в импликативные функции 41, всех аргументов хi, кроме хi, с отрицанием, если хi = 1, и без отрицания — в противоположном случае. Для хi, условия вхождения противоположны.
Пример 2.4 Пусть задана функция f (х1,х2, x3 х4) таблицей

х1 х2 х3 х4 f х1 х2 х3 х4 f
0
0
0
0
0
0
0
0 0
0
0
0
1
1
1
1 0
0
1
1
0
0
1
1 0
1
0
1
0
1
0
1 1
0
1
1
1
0
1
1 1
1
1
1
1
1
1
1 0
0
0
0
1
1
1
1 0
0
1
1
0
0
1
1 0
1
0
1
0
1
0
1 1
1
1
0
1
1
1
0
Записать эту функцию в импликативной форме
Составляем импликативные функции ?i :
?1 = х1 ?х2 ? х3 ? х4

?2 = х1 ?х2 ? х3? х4

?3 = х1 ?х2 ? х3? х4

?4 = х1 ?х2 ? х3? х4
Записываем функцию f (х1,х2, x3 х4) в форме:
f (х1,х2, x3 х4) = (х1 ? х2 ? x3 ? х4 )& (х1 ? х2 ? x3 ? х4 ) & (х1 ?х2 ?x3 ? х4 )& (х1 ?х2 ?x3 ? х4 )
После применения (2.37) получим:
f (х1,х2, x3 х4) = ? 1 ?[ ? 2 ? (? 3 ?? 4 )]
Рассмотренная импликативная форма записи является аналогом СКИФ. Аналогом СДНФ является вторая форма импликативной записи, основанная на том, что любая функция алгебры логики, кроме тождественного нуля, может быть представлена в следующей форме:

f (x1, х2,...,хn) = v х1 ?х2 ? хn (2.41)

где функции
? = х1 ?х2 ? хn
устроены так, что каждая такая функция обращается в единицу на наборе (х1 х2… хn), и равна нулю на всех остальных наборах. Дизъюнкция в (2.41) может быть заменена через импликацию и отрицание на основании первого тождества (2.37):
х1 v х2 ? х1 ? х3
Пример 2.5 Записать в форме (2.41) функцию f (х1,х2, x3 )

х1 х2 х3 f х1 х2 х3 f х1 х2 х3 f х1 х2 х3 f
0
0 0
0 0
1 0
0 0
0 1
1 0
1 0
0 1
1 0
0 0
1 1
1 1
1 1
1 0
1 0
0

Выписываем функции у, для наборов, на которых f = 1
? = х1 ?х2 ? х3
? = х1 ?х2 ? х3
На основании (2.41) получаем:
f (х1,х2, x3 ) = (х1 ?х2 ? х3 ) v (х1 ?х2 ? х3 )
или, применяя (2.37)
f (х1,х2, x3 ) = (х1 ?х2 ? х3 ) ? (х1 ?х2 ? х3 )
В дальнейшем в основном будет рассматриваться функционально полная система, состоящая из базисных логических функций отрицания, конъюнкции и дизъюнкции.
Пример 2.6 Даны восемь типов валов (рис. 2 1), каждый из которых имеет свою технологию обработки. Валы в произвольном порядке поступают по конвейеру. Робот обслуживает два токарных станка, один — с патроном для большого диаметра, другой — с патроном для малого диаметра. Робот должен выбрать, в какой станок осуществить загрузку детали и сообщить системе управления станка номер технологии.
Решение. Определим число датчиков робота и место их расположения. Очевидно, что для распознавания деталей достаточно четырех датчиков, обозначим их а, b, с, d . Каждый датчик настроен на два параметра: большой диаметр — a, b, с, d; малый диаметр— abсd.
Определим кодовую комбинацию состояний датчиков, которую можно поставить в соответствие каждому типоразмеру деталей. Все детали разобьем на симметричные и несимметричные. Для несимметричных деталей комбинация зависит от положения деталей на конвейере: деталь 1 имеет комбинацию abсd или abсd; деталь 2 — abсd; деталь 3 — abсd или abсd и т. д. Распределим детали по группам. Большой диаметр деталей — 2, 4, 8; малый диаметр деталей — 1, 7. Детали 3, 5, 6 могут быть загружены в патрон с большим и с малым диаметром. Пусть по требованиям технологических процессов они должны быть отнесены к группе большого диаметра.

Рисунок 2.1 — Типы валов
Сигнал управляющего устройства робота на загрузку станка с патроном большого диаметра обозначим Х1, меньшего — Х2, сигнал на поворот руки робота на 180 перед загрузкой несимметричных деталей в станок — Х3. Составим таблицу 2.5 соответствия требуемых управляющих сигналов в зависимости от показаний датчиков.
Запишем через констнтуенту единицы из таблицы 2.5 значения логических функций Х1,Х2,Хз в СДНФ.

Таблица 2.5 — Таблица соответствия управляющего устройства робота

Номер детали a b c d Х1 Х2 Х3
-
3
1
6
1
-
7
5
3
4
-

<< Пред. стр. 3 (из 7) След. >>

Список литературы по разделу