Алгебра логики решение задач

Алгебра логики — это один из основных разделов символической логики, в основе которого лежит применение алгебраических методов к логике. Информация на этой странице периодически обновляется см. Описание Алгебра логики — это один из основных разделов символической логики, в основе которого лежит применение алгебраических методов к логике см. Алгебра логики — исторически первая форма символической логики см. К её созданию привела аналогия между решением алгебраических уравнений и выводом следствий из посылок, а также то, что алгебраические уравнения применимы при решении задач из различных областей знания. Поначалу алгебра логики имела своим предметом классы как объёмы понятийсоотношения между классиками по объёму и связанные с этим операции над. Позднее, в связи с появлением в 70-х годах XIX века теории множеств, взявшей на себя часть этих задач, предмет алгебры логики значительно изменился. Основным её предметом стали высказывания суждения, предложениярассматриваемые со стороны их логических значений истина, ложь, бессмыслица и другиеи логические операции над. Попытки сведéния логики к алгебре предпринимались ещё в XVII—XVIII веках: среди тех, кто занимался перестройкой логики на алгебраической основе, следует назвать Лейбница и особенно Ламберта, который, по-видимому, первым использовал термины «алгебра логики», «логическая алгебра». В то время основным предметом алгебры считали решение уравнений, и Ламберт стремился к тому, чтобы представить логические связи уравнениями, а логические выводы — решением соответствующих уравнений. При этом он стремился сохранить в «алгебраической логике», которую он называл знаковым искусством, все операции обычной алгебры В XIX веке поиск способов решения логических задач алгебраическими методами продолжился. Были введены чёткие представления об операциях над объектами логики, что стало возможным, прежде всего, благодаря трактовке понятий по их объёму. Кроме того, было введено понятие универсума — предметной области логики, а в качестве объектов, на которых задаются операции, стали выступать подклассы универсума, суждения же получили представление в виде равенств. Принципиальный прорыв в алгебраизации логики совершили Буль; «Формальная логика» де Моргана и «Математический анализ логики» Буля вышли в 1847 году. В построениях обоих учёных содержалось то, что ныне называется «булевой алгеброй». Де Морган кроме этого развил исторически первую систему алгебры отношений. Система Буля, называемая «алгеброй логики» а иногда «алгеброй классов»получила более широкую известность, чем построения Де Моргана. Порецкого и других исследователей методы алгебры логики получили дальнейшее усовершенствование. В основе обычной, так называемой классической алгебры логики лежит абстракция высказывания как величины, имеющей одно и только одно из двух значений: «истина» или «ложь» короче: И, Лили могущей принимать оба эти значения но не одновременно. В первом из этих случаев имеем индивидуальное высказывание высказывание в узком, наиболее принятом смысле этого словаво втором — высказывание-функцию. Первые три высказывания имеют значение И то есть истинны4-е и 5-е — значение Л то есть ложны6-е, 7-е, 8-е — высказывания-функции если, например, значениями буквенных переменных x и у могут быть целые числа, а переменной z — живые существа9-е и 10-е имеют значение И при всех возможных значениях переменных x и y. Последние три из этих высказываний являются сложными, в отличие от предшествующих им простых. Абстракция в алгебре логики идёт. Все истинные высказывания отождествляются между собой, так как истинное высказывание не отличается от другого истинного высказывания по значению от других сторон высказываний в алгебре логики отвлекаются. Ложные высказывания тоже отождествляются. При рассмотрении же высказываний-функций в алгебре логики обычно отвлекаются от рассмотрения зависимости их от иных переменных, кроме таких, значениями которых тоже являются высказывания, вводя для их рассмотрения буквенные переменные, которые называют переменными высказываниями. Таковыми являются буквы A, B, C, … Α 1, A 2, A 3, … и так далее при этом выбор букв — вопрос не существа, а соглашения при условии, что они играют роль переменных, значениями которых могут быть всевозможные индивидуальные высказывания, то есть, в силу упомянутых абстракций, «константы» И и Кроме простых высказываний, обозначаемых отдельными буквами A, B… или И, Л, рассматриваются также сложные высказывания — результат соединения высказываний связками или отрицания их соответствующего частице «не». Сложные высказывания рассматривают как функции от входящих в них буквенных переменных A, B, C и так далее. Так появляется понятие функции алгебры логики — функции от аргументов, являющихся переменными высказываниями, то есть принимающих значения И, Л, которая функция может принимать тоже лишь эти значения. Одной из важных сторон формализации, принимаемой в алгебре логики, является то, что знаками этих операций то есть по смыслу, соответствующими им связками можно соединять любые высказывания, без ограничения, в том числе и те, которые сами являются сложными. При этом удаётся точно и строго описать класс всех рассматриваемых выражений алгебры логики. Это связано с требованием, чтобы операции задавались таблично как функции и значение сложного высказывания зависело только от значений составляющих его простых высказываний. Основная суть алгебры логики как системы методов состоит в использовании преобразований высказываний на основе алгебраических законов, которые имеют место для операций над высказываниями. Эти законы чаще всего имеют вид тождеств см. Важную роль играют следующие тождества: Эти тождества, устанавливаемые, например, с помощью таблиц, позволяют получать другие тождества. Тождеств I—VI достаточно для того, чтобы из них по методу тождественных преобразований можно было вывести всякое верное, конечно тождество, левая и правая части которого — выражения алгебры логики, состоящие из переменных A, B, констант И, Л и знаков «×», «ν» «-» не обязательно включая все из. Тождества V, VI, VII показывают, что константы И и Л, импликацию и эквиваленцию, рассматривая их как функции, можно выразить через конъюнкцию, дизъюнкцию и отрицание. Имеет место теорема, гласящая, что всякая функция алгебры логики может быть представлена через эти три операции, то есть записана в виде выражения, содержащего лишь знаки этих операций и буквенные переменные. ДНФ называется совершенной, если она есть И или Л или в каждом члене содержит ровно по одному разу все имеющиеся в ней буквы переменные и не имеет одинаковых членов. Всякое выражение алгебры логики можно привести к ДНФ. Важную роль играет так называемая сокращенная ДНФ. Последнюю можно определить как такую ДНФ, в которой 1 нет повторений букв ни в одном члене; 2 нет таких пар членов А i, и A j, что всякий множитель из А i, имеется и в А j, и 3 для всяких двух таких членов, из которых один содержит множителем некоторую букву, а другой — отрицание той же буквы при условии, что другой буквы, для которой это имеет место, в данной паре членов нетимеется в этой же ДНФ член, равный конъюнкции остальных множителей этих двух членов. Кроме ДНФ, употребляются также конъюнктивные нормальные формы КНФ. Преобразованием двойственности называется такое преобразование выражения алгебры логики, при котором в этом выражении знаки всех операций заменяются на знаки двойственных им операций, а константы: И на Л, Л на И; причём операция или функция Φ называется двойственной для операции Ψ, если таблица, задающая Φ, получается из таблицы, задающей Ψ, путём замены в ней всюду И на Л, а Л на И имеется в виду одновременная замена и значений функции, и значений её аргументов. Например, конъюнкция и дизъюнкция двойственны между собой, отрицание двойственно самому себе, константа И как функция двойственна константе Совершенную КНФ и сокращенную КНФ можно определить как такие КНФ, что двойственные им выражения есть соответственно совершенная ДНФ и сокращенная ДНФ. Совершенные и сокращенные ДНФ и КНФ можно использовать для решения задачи обзора всех гипотез и всех следствий данного выражения алгебры логики. Ещё один, часто употребляемый в алгебре логики шаг абстракции, состоит в отождествлении И с числом 1, а Л — с числом 0. Она называется сложением точнее сложением по модулю 2; другое название: разделительная дизъюнкция; читается: « A плюс B», или A не эквивалентно B», или «либо A, либо B». Всякую функцию алгебры логики можно представить через умножение то есть конъюнкциюсложение и константу 1 теорема Жегалкина. В частности, верны следующие тождества: VIII. Обратные представления имеют вид: Тождества VIII позволяют «переводить» выражения «языка» конъюнкции, дизъюнкции и отрицания КДО на «язык» умножения, сложения и единицы УСЕа тождества X — осуществлять обратный «перевод». Тождественные преобразования можно производить и на «языке» УСЕ. В основе их лежат следующие законы: XI. Этих тождеств достаточно для того, чтобы из них можно было вывести любое верное тождество, обе части которого суть выражения «языка» УСЕ. А добавив к ним тождества VIII, мы сможем выводить и все тождества «языка» КДО. Выражение «языка» УСЕ называется приведённым полиномом, если оно есть 1 + 1 то есть нуль или имеет вид A 1 + A 2 + … + А s где каждый член A, есть либо 1, либо буквенная переменная, либо произведение последних, причём ни в одном члене нет никаких повторений букв, никакие два члена не одинаковы в том же смысле, что и вышеa s не обязательно больше 1 то есть знаков «+» может не. Всякое выражение алгебры логики можно привести к приведённому полиному теорема Жегалкина. Кроме «языков» КДО и УСЕ существуют и другие «языки», обладающие тем свойством, что через операции и константы этих «языков» можно представить всякую функцию алгебры логики. Такие системы называются функционально полными. Иногда совершают ещё один важный дальнейший шаг абстракции. Отвлекаются от табличного задания операций и от того, что значениями буквенных переменных являются высказывания. Вместо этого допускаются различные интерпретации рассматриваемого «языка», состоящие из той или иной совокупности объектов служащих значениями буквенных переменных и системы операций над объектами этого множества, удовлетворяющих тождествам из полной системы тождеств этого «языка». «Язык» КДО в результате такого шага абстракции превращается в «язык» так называемой булевой алгебры, «язык» УСЕ — в «язык» так называемого булева кольца с единицей«язык» конъюнкции и дизьюнкции — в «язык» так называемой дистрибутивной структуры. Вернее, при таком переходе от алгебры классов к алгебре предикатов получается алгебра одноместных предикатов. Другим важным случаем является алгебра двуместных предикатов, называемых чаще отношениями. С ней тесно связана алгебра отношений, отличающаяся от неё только тем, что в последней, кроме трёх операций булевой алгебры, имеются ещё две. Например, в случае алгебры множеств роль A + B играет так называемая симметрическая разность множеств A и B состоящая из всех тех элементов универсума, которые принадлежат одному и только одному из множеств A или Обратно, всякое булево кольцо с единицей можно «переделать» в булеву алгебру. Понятия булевой алгебры и булева кольца связываются с именем Дж. Однако оформились эти понятия не говоря уже о терминах значительно позже. Первые работы по алгебре логики были посвящены задачам: выражения логических соотношений между объёмами понятий соответственно высказываниями в виде уравнений равенств ; построения алгоритмов решения логических уравнений и систем уравнений с целью автоматизировать способы извлечения из данных посылок содержащейся в них неявно информации того или иного рода. В настоящее время алгебра логики развивается главным образом под влиянием задач, встающих в области её приложений. Она находит широкое применение в технике, и наоборот, развивается сама под влиянием запросов техники и задач программирования. Вопросы, касающиеся понятий самой алгебры логики, приводят к проникновению в алгебру логики неалгебраических методов таких как табличные, топологические, дескриптивные и вследствие этого к постепенному выделению из алгебры логики самостоятельной области — теории функций алгебры логики или иначе, теории булевых функций. Другие тенденции возможного дальнейшего развития алгебры логики связаны с успехами теории алгоритмов и попытках алгебраизации последней, то есть построения алгебраической теории алгоритмов. Всё большее прикладное значение приобретает теория булевых функций как самостоятельная область, выделившаяся из алгебры логики. В результате пришли к понятию функциональной системы Р n, Cгде Р n есть множество всех функций n-значной логики или множество всех функций счётнозначной логики Р ω с заданной на нем операцией суперпозиции CР n обычно рассматривается как обобщение множества всех булевых функций Р 2. Известна содержательная трактовка понятия функциональной системы Р n, C выступает её частным случаемв основе которой лежит рассмотрение таких пар Ρ, Ωв которых Ρ есть множество отображений, реализуемых управляющими системами из некоторого класса, a Ω состоит из операции, используемой при построении новых управляющих систем из заданных. В свою очередь Р 2, Q есть эквивалент алгебры логики. Таким образом, от алгебры формул, изучаемой в алгебре логики, перешли к алгебре функций. И хотя именно алгебра логики, то есть классическая логика высказываний см. Другим направлением современного развития алгебры логики является алгебраическая логика. Она интересна тем, что выдвигает и частично решает задачу построения алгебр неклассических логик см. В этой области существенным является вопрос о построении алгебраической семантики, под которой понимается класс всех моделей некоторой алгебры, соответствующей логике L, поскольку посредством алгебраической семантики решаются такие металогические проблемы, как полнота L относительно общезначимости в классе всех моделейразрешимость L и. В итоге пришли к общему вопросу о том, какая логика алгебраически представима, то есть имеет алгебраическую семантику, а какая. Ответ на этот вопрос дан в работе Пигоцци Blok, Pigozzi, 1989. Существенно, что современное развитие алгебраической логики представляет собой систематическое применение методов и, главное, аппарата универсальной алгебры к символической логике. На сегодняшний день речь уже идёт об алгебраическом охвате всей символической логики, и результаты здесь весьма значительны. К примеру, если Alg L обозначает класс алгебр, который соотносится с некоторой логикой L если L есть классическая логика высказываний, то Alg L есть класс булевых алгебрможно формулировать теоремы, утверждающие, что L имеет определённое логическое свойство тогда и только тогда, когда Alg L имеет определённое алгебраическое свойство. Это позволяет дать алгебраическую характеризацию таких логических свойств, как полнота, наличие теоремы дедукции, компактность, разрешимость, интерполяционность Крейга, истинность формул в модели и так далее. Основания математики и математическая логика. Математическая логика и основания математики. Сборник статей по математической логике и её приложениям к некоторым вопросам кибернетики. Метод упрощения форм выражения функций истинности. Алгоритмы как операции в алгебраических системах. Опыт математического изложения логики. Физико-математические науки в их настоящем и прошедшем. Алгебра логики, в задачах. О способах решения логических равенств и об обратном способе математической логики. Функции алгебры логики и классы Поста. Булева алгебра и её применение в задачах электроники: учебное пособие. Algebraic logic and the methodology of applying it. The mathematical analysis of logic. A general algebraic semantics for sentential logics. Handbook of Boolean algebras, Ed. Monk with the coop. General algebraic logic: a perspective on «What is logic». Formal logic, or calculus of inference, necessary and probable. An algebraic approach to non-classical logics. Der Operationskreis des Logikkalkuls. Подготовка электронной публикации и общая редакция: Центр гуманитарных технологий. Публикация охраняется в соответствии с законодательством Российской Федерации об авторском праве. Воспроизведение и распространение текста не допускается без разрешения правообладателя. Информационно-аналитический портал по основным направлениям и рынкам гуманитарных технологий: интеллектуальные индустрии, общественное развитие, государственные, корпоративные и коммуникационные стратегии, управление, образование, институты и фабрики мысли. Новости, исследования, рейтинги, прогнозы, гуманитарная энциклопедия и библиотека. Всё для изучения и проектирования гуманитарного развития. © 2002—2015 ИАА Центр гуманитарных технологий Centre for Human Technologies 125171, Москва, Ленинградское шоссе, дом 18, офис 815 Телефон: +7 495 974—80—63 E-mail: ISSN 2310-1792 Online Edition.