Символически отображение системы в параметрах бинарной логики (0,1) показано на рис. 1. 360 Базовыми понятиями МЛ являются высказывание, предикат, логические фун кции (операции), кванторы, логический базис, логические законы (законы алгеб ры логики). ф[5 ] Под высказыванием в алгебре логики понимается повествовательное предложе ние (суждение), которое характеризуется определенным значением истинности. В простейших случаях используются два значения истинности: «истинно» - «ложно», «да» - «нет», «1» - «О». Такая алгебра логики, в кото рой переменная может принимать только два значения истинно сти, называется бинарной алгеброй логики Буля (по имени создате ля алгебры логики). Функции бинарной алгебры логики приведены в табл. 1, где собраны формы записи и наименования функций, встречающие ся в различных литературных источниках. За основу при состав лении табл. 1 взята таблица, приведенная в [13]. Предикат - выражение, грамматически имеющее форму выс казывания, но содержащее переменные некоторых подмножеств, на которых они определены. При замене переменных элементами соответствующего под множества предикат обращается в высказывание. Обычно пере менная стоит в предикативной части предложения, лежащего в основе высказывания (например, «быть Х-вым карандашом», где X может принимать значения «красным», «синим» и т.д.), но в принципе это не обязательно (и возможны предикаты «X- река», где X - «Волга», «Днепр» и т.д.). Частным случаем предиката является пропозиционная функ ция - функция одной или нескольких переменных, принимающих значения в множестве, состоящем из двух элементов: «1» - «О». Применение переменных высказываний служит для выраже ния общности и позволяет формулировать законы алгебры логи ки для любых высказываний данного вида. Из одного или нескольких высказываний, или предикатов, можно образовать новые высказывания, или предикаты. Простые высказывания объединяются в сложные без учета смысла этих высказываний (предикатов) на основе определенных логических правил (операций, функций). 361 ON ы Таблица 1 Способ и форма j записи А " ~ Алгебраиче ская запись логического отношения аргументов с функцией 1 Двоичная форма запи си связи воздействия с результа- том Основные встречаю щиеся в литературе названия логической функции (операции. фактора) Логический аргумент Б 1 0 i 1 0 0 Первое логиче ское воз действие. Первая логиче ская пе ременная. Первый логиче ский аргумент В b i 0 1 0 Второе логиче ское воз действие. Вторая логиче ская пе ременная. Второй логиче ский элемент t F=0 _ 0 0 0 Тождест венный нуль. Тождест венно ложно 2 F = l i 1 I I Тождест венная единица. Тождест венно истинно Логическая операция 3 F=a j I 0 0 Утвер ждение первого аргумен та (пере менного воздейст вия). Повторе ние пер вого ар гумента (пере менного воздейст вия) 4 F=b j 0 1 0 Утвер ждение второго аргумен та (пере менного воздейст вия). Повторе ние вто рого ар гумента (пере менного воздейст вия) (функция, 5 1 F.= CKjb avb a^b i I 1 0 Дизъ юнкция. Логиче ская сумма. Объеди нение. Простая (неразде литель ная) дизъ юнкция фактор, отношение) 6 F,= anb алЬ a&b a-b axb 1 0 0 0 Конъ юнкция. Логиче ское произве дение. Перечис ление. Совпаде ние. 7 ~^ стЬ а-Ь а<г>Ь а=Ь i 0 0 1 Эквива лент ность. Равно знач ность. Матери альная эквива лент ность. Взаим ность 8 ^= 1 az)b a-^b a>b i 0 1 1 Импли кация. Следова ние. Матери альная импли кация. Общеут верди тельное суждение 9 F.= cfb (Kjb avb 0 0 0 I Функция Вэбба. Опера ция Пир са. Отрица ние дизъ юнкции. Обратная дизъ- юнкци Антидизъ юнкция Условное название логической функции ! Любое ложно Любое истинно Дом и на ция пер вой пе ремен ной Как а 1 Домина- ция вто рой пе ремен ной Как^ Сборка. Абстра гирова ние. Комби нация. Автоно мия. Констел ляция И/или. Или. Хотя бы Соеди ненное суждение Частное утверди тельное сужде ние. Реализо вание И И И Соли дарность. Компле- ментар- ность. Интер- депен- денция Как Селек ция. Специ фикация. Детер минация. Обратная антиим плика ция Если то только Обратная логиче ская сумма. Гетеро- фазис. Недизъ юнкция, Отрица ние ком бинации, автоно мии и т.д. Анти- констел- ЛЯЦИЯ j Н е ИЛИ Ни ни Продоллсеные Способ и форма 1 записи А Алгебраиче ская запись логического отношения аргументов с функцией Двоичная форма запи си связи воздействия с результа- |том Основные встречаю щиеся в литературе названия логической функции (операции. фактора) Логический аргумент Б 0 1 1 0 0 Первое логиче ское воз действие. Первая логиче ская пе ременная. Первый логиче ский аргумент В _ 1 ' 0 1 0 Второе логиче ское воз действие. Вторая логиче ская пе ременная. Второй логиче ский элемент 10~~~] ~^ a/ti' аг\Ь алЬ а-Ь ахЬ а&Ь 0 1 1 1 Функция Шеффера. Операция Шеффера. Штрих Шеффера. Отрицание конъюнк ции. Обратная конъюнкция Логическая операция (функция, фактор, отношение) 11 ' ^ а^Ь а^Ь а®Ь а^ b а Ab 0 1 1 0 Отрицание равнознач ности. Функция разноимен- ности. Функция сложения по модулю. Неравно значность. 12 ^ а<Ь 1 aczb a<r-b i 1 0 1 Обратная импликация. Обратное следование. Обратная селекция. Обратная специфика ция. Обратная детерми нация 13 f ^ -.fl а -а =d =са 0 0 1 I Отрицание первого аргумента. Инвертация первого аргумента (перемен ного). Дополнение к первому переменно му. 14 ^и-Ь -пЬ b ~b =cb 0 1 0 1 Отрицание второго аргумента. Инвертация второго аргумента (перемен ного). Дополнение ко второму переменно му. 15 1 ~^ а\Ь a-z>b az)b a-^b _ _ 1 0 0 Отрицание материаль ной импли кации. Материаль ная импли кация. Антисовпа дение. 16 ' ^ a<zb aab a<r-b - 0 1 0 Отрицание обратной имплика ции. Обратная антиимпли кация (не имплика ция). Неконъ юнкция. Обратное логическое произведе ние. Обратное совпадение. Альтерна тивное отрицание. Несовмес тимость. Общеотри цательное суждение Ней Или не Строгая дизъюнк ция. Исклю чающая дизъюнк ция. Раздели тельная дизъюнк ция. Отрицание взаимоза висимости Не как Или или Или не Профазис Ша Обратный ситифазис Не А Раздели тельное суждение. Отрицание селекции. Антиселек ция. Антиспе цификация. Антидетер минация Но не Обратное раздели тельное суждение. Обратное антисовпа дение. Не но Число простейших логических функций в конкретной алгебре логики зависит от числа значений истинности п: N=2^". (1) Для двузначной булевой алгебры логики Л^ определяется чис лом возможных двоичных наборов (/? -2)\ N - 16. При п = 3 мож но образовать Л^ = 256 логических функций. Кроме логических функций в логике предикатов имеются еще операции квантификации - кванторы. Это специальные опера ции, которые служат для выражения общности суждений и свя занных с ними понятий (табл. 2) и позволяют на формальном язы ке исчисления предикатов говорить не об одном объекте, а о целом классе объектов. Полную систему логических функций называют логическим базисом. Чтобы система функций представляла собой базис, она должна обладать определенными свойствами. Чтобы система функций была полной, необходимо и доста точно, чтобы она содержала хотя бы одну функцию: не сохраня ющую константу «единица», не сохраняющую константу «нуль», нелинейную, немонотонную, несамодвойственную. Полный логический базис содержит избыточное число функ ций. Такая система функций может остаться базисом при исклю чении из нее некоторых функций. Исключение функций можно производить до тех пор, пока система не станет такой, что удале ние из нее хотя бы одной из функций, ее образующих, будет при водить к невыполнению перечисленных требований к базису. Такую систему называют минимальным базисом. Минимальными базисами бинарной алгебры логики являют ся базисы, включающие только по две функции {>, U} и {>, П}. Функция отрицания не сохраняет константы «ноль» и «едини ца» и не является монотонной; функции дизъюнкции U и конъюнк ции П обеспечивают нелинейность и не являются самодвойствен ными (в силу приведенных в табл. 3 теорем де-Моргана). В этой связи существуют понятия дизъюнктивно-нормальной и конъюнктивнО'Нормалъной формы, всегда удовлетворяющие тре бованиям базиса. В условиях выполнения требований к базису в алгебре логи ки доказывают теоремы, демонстрирующие свойства операций над высказываниями. Применяя эти теоремы, формально можно 366 Т а б л и ц а 2 Обозначение (Е! а) b Наименовсшие Квантор общности Квантор существования Квантор единственности Смысл Для любого а будет Ь Есть хотя бы одно а, такое, что будет b Есть только одно а, такое, что будет b получить правильный результат, не вникая в смысл проводимых исследований. Примеры этих теорем, или логических законов, при ведены в табл. 3. Из элементарных функций алгебры логики формируют пос ледовательности действий, отображающие процессы в системе от входа до выхода, т.е. логические алгоритмы. Т а б л и ц а 3 Название свойства (закона) и его формулировка Замкнутость Множество R содержит дизъюнкцию и конъ юнкцию всех входящих в него элементов 1 Коммутативность Изменение последовательности элементов не изменяет значения дизъюнкции и конъюнкции Ассоциативность Группировка внуфи конъюнкции и дизъюнкции не меняет их значений Дистрибутивность Прибавление элемента к произведению равно сильно прибавлению этого элемента к сомно жителям; умножение суммы на элемент равно сильно умножению слагаемых на этот элемент Идемпотентность {закон тавтологии) Повторение элемента (прибавление или умно жение) не изменяет истинности элемента Дополнительность \ Для каждого элемента а множества R существу ет дополнение -г а или R — а Законы поглощения (абсорбции) Дизъюнкция произведения и одного из ее чле нов эквивалентна этому члену. Конъюнкция суммы и одного из ее членов эквивалентна это му члену Символическая запись an b е R \ an b е R a^j b = b\j а an b = bn a (an b) n c= an(bnc) (a u b)u c — a\j (bKj c) a и (bn c)= = (oj b) n (au c) a n (bu c)= = (an b) u (an c) a и a = a a n a = a Частный случай 1 a^ ^ a=^ R -. Л = 0 au (an b)s a an(au b)= a 367 Продоллсепие Название свойства (закона) 1 и его формулировка 1 Законы двойственности {теоремы Л. де-Моргана) Дополнение к пересечению аи b эквивалентно объединению их дополнений. Дополнение к объединению элементов (мно жеств) равно пересечению их дополнений Инволюция {закон удвоенного отрицания) 1 Законы противоположности Если элемент а эквивалентен дополнению эле мента Ь, то элемент b эквивалентен дополнению элемента а Множестю содержит элементы /? = i и 0 = 0, такие, что для всякого элемента а объединение или пересесение его с пустым множеством рав но д^, а объединение или пересечение его с эле- 1 ментом R = 1 равно R Умножение одного из элементов на дополнение второго элемента не меняет дизъюнкции элементов Символическая запись an b = аи b аи b ^ а r\ b -.{-. d)^ а а=Ъ => b= а аи 0 = а аи R = R \ а г\ R ~ R ап0 = а а * {-^ Ь) = а+ b an {-^ b) ^ аи b На рис. 2 и 3 проиллюстрирована разная запись одного и того же алгоритма (соответствие обозначений рис. 2 и 3 приведено на рис. 4). Этот же алгоритм может быть записан следующим образом: (2) Существует много форм записи логических алгоритмов: в виде функций алгебры логики (2), в форме таблиц или матриц, «машин Тьюринга», логических схем по А.А. Ляпунову, с помощью рекур сивных функций, на языке нормальных алгоритмов А.А. Марко ва, в виде программ для вычислительных машин на одном из язы ков программирования, в форме диаграмм Насси-Шнайдермана. С основными способами представления алгоритмов можно познакомиться в [7, 9, 10 и др.]. Логические алгоритмы могут преобразовываться с использо ванием логических законов. Пример применения одного из зако нов (теоремы А. де-Моргана) приведен на рис. 5. 368 Рис.2 ^1 Ч и I I I f НЕ-И 3^1 И/ИЛИ Т1 I и/или Рис.3 НЕ ^ и/или "~Г~ а Ь а Ь НЕ ~1Г И аГЛЬ а Ь а b И/ИЛИ а и Ь а->Ь Рис.4 а Ь НЕ-И -а/Ь а b I I li НЕ-ИЛИ "Т" а и Ь а ^ Ь = аиЪ Рис.5 369 На базе логических представлений возникли и развиваются теории логического анализа и логического синтеза. Они основаны на применении средств алгебры логики к задачам анализа и син теза структур исследуемых систем, а также к задачам принятия решений в сложных проблемных ситуациях, возникающих в сис темах или при взаимодействии систем. Задача логического анализа состоит в описании поведения си стемы с известной структурой набора системно-логических урав нений (функций алгебры логики - ФАЛ) и исследовании полу ченного логического выражения с целью его минимизации, т.е. выяснении, нельзя ли получить более простую структуру (схему), содержащую меньшее число элементов (состояний), но осуществ ляющую требуемые преобразования. Такие задачи возникают, например, при создании автоматических систем контроля неисп равностей, систем автоматического резервирования, обеспечения надежности и т.д. Задача логического синтеза заключается в том, чтобы по из вестному поведению системы определить ее структуру (в случа ях, если она неизвестна или не полностью известна), т.е. сопоста вить системе некоторый «автомат» - «черный ящик» с известными входными и выходными воздействиями. Таким образом, при логическом анализе задача сводится к минимизации ФАЛ, т.е. к оптимизации в некотором смысле ло гического алгоритма. Задача логического синтеза сложнее, она обычно решается с помощью последовательных приближений, и на промежуточных этапах здесь также может быть полезна ми нимизация ФАЛ. Минимизация осуществляется в результае применения зако нов алгебры логики, приведенных в табл. 3. Наиболее известны ми методами минимизации ФАЛ являются: метод минимизирую щих карт или таблиц (конъюнктивных или дизъюнктивных, импликатных); метод неопределенных коэффициентов; геометри ческие методы; метод Блека - Порецкого (с обзором методов ми нимизации ФАЛ можно познакомиться в [10], где даны ссылки на соответствующие первоисточники). При возрастании числа переменных для минимизации ФАЛ применяют ЭВМ. При этом логический алгоритм нужно перевес ти на один из языков программирования или при логическом ана лизе сложных ситуаций разработать промежуточные языки про ектирования или моделирования процессов управления (например, 370 язык БИТ Э.Ф. Скороходько [11], логический язык ЛЯПАС пред ставления алгоритмов синтеза А.Д. Закревского [5] и др.). Специфические особенности задачи логического синтеза при описании системы логическим автоматом вызвали возникнове ние и развитие самостоятельной научной дисциплины - теории автоматов. Логические методы представления систем возникли как детер министские, но в дальнейшем стали предприниматься попытки их расширения в сторону вероятностных оценок. Они сыграли боль шую роль в развитии теоретической основы алгоритмизации и программирования. В частности, они лежат в основе теории алго рифмов (в дальнейшем - алгоритмов) А.А. Маркова. Логические представления применяют в случаях исследова ний новых структур систем разной природы (технических объек тов, текстов и др.), в которых характер взаимодействия между элементами еще не настолько ясен, чтобы возможно было их пред ставление аналитическими методами, а статистические исследо вания либо затруднены, либо не привели к выявлению устойчи вых закономерностей. В то же время следует иметь в виду, что с помощью логичес ких алгоритмов можно описывать не любые отношения, а лишь те, которые предусмотрены законами алгебры логики. Логические представления широко применяются при иссле довании и разработке автоматов разного рода, автоматических систем контроля, при решении задач распознавания образов. На их основе развивается самостоятельный раздел теории формаль ных языков моделирования проблемных ситуаций и текстов. Смысловыражающие возможности логических методов огра ничены базисом и не всегда позволяют адекватно отобразить ре альную проблемную ситуацию. Поэтому стали предпринимать ся попытки создания вначале тернарной логики [8], а затем - и логик, в которых переменная может принимать не только край ние значения «истинно» - «ложно», но и какие-либо из промежу точных - многозначных логик [12, 14], вплоть до непрерывной. Однако отметим, что даже для тернарной логики В.Т. Кулику [8] так и не удалось создать непротиворечивый логический базис, и он обра тился к созданию информационных языков моделирования на основе лингвистических представлений. Неудача попыток создания многозначных логик объяснима, если учесть, что вся математика, в том числе и математическая логика, чтобы 371 соответствовать принципам строго формальной дедуктивной системы (с учетом, конечно, теоремы Гёделя), базируется на законе исключенного третьего (т.е. на предположении, что всякое событие (положение) может быть истинным или ложным, третьего не дано). Реальная же действительность не подчиняется данному закону, и поэтому для ее моделирования необходимо либо создание подходов, основанных на формализации диалектической логики (см. Информаци онный подход к анализу систем), либо использование лингвистических (см. Математическая лингвистика) и семиотических представлений (см.), которые свободны от требования выполнения закона исключенного тре тьего, что и является иногда основанием для того, чтобы не включать эти направления в математику.
Ви переглядаєте статтю (реферат): «МАТЕМАТИЧЕСКАЯ ЛОГИКА» з дисципліни «Теорія систем і системний аналіз в управлінні організаціями»
