Виталий Сигорский - Математический аппарат инженера

32. Покажите, что следующие свойства дерева Т равносильны:

а) Т связно и не содержит циклов;

б) Т не содержит циклов и имеет p — 1 ребер, где p — число вершин;

в) Т связно и имеет p — 1 ребер;

г) Т не содержит циклов, но добавление ребра между любыми двумя несмежными вершинами приводит к появлению цикла;

д) Т связно, но утрачивает это свойство при удалении любого ребра;

е) всякая пара вершин в Т соединена цепью и притом только одной.

1. Чем занимается математическая логика?Логика как искусство рассуждении зародилась в глубокой древности. Начало науки о законах и формах мышления связывают с именем Аристотеля. Прошло два тысячелетия, прежде чем Лейбниц предложил ввести в логику математическую символику и использовать ее для общих логических построений. Эту идею последовательно реализовал в прошлом столетии Джордж Буль и тем самым заложил основы математической (символической) логики .

- 61 -

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

Бурное развитие математической логики связано, прежде всего, с задачами обоснования математики, где она используется для доказательства непротиворечивости исходных понятий и правильности рассуждении и выводов математических теорий. Некоторые ученые даже склонны рассматривать логику как одну из наиболее общих наук, частью которой является сама математика.

В последние десятилетия логика находит все более широкое применение в технике при исследовании и разработке релейно-контактных схем, вычислительных машин, дискретных автоматов. Ее методы используются в теории преобразования и передачи информации, теории вероятностей и комбинаторном анализе. Математическая логика начинает внедряться в такие нематематические области, как экономика, биология, медицина, психология, языкознание, право. Интенсивно развиваются специальные разделы математической логики, призванные обслуживать конкретные области науки и техники.

Столь энергичный выход математической логики за пределы математики объясняется тем, что ее аппарат легко распространяется на объекты самой общей природы, лишь бы только они характеризовались конечным числом состояний.

Двузначная логика имеет дело с такими объектами, которые принимают одно из двух возможных значений (истинное или ложное высказывание, высокое или низкое напряжение, наличие или отсутствие заданного признака у объекта и т. п.). Объекты, которые могут принимать значения из конечного множества, содержащего больше двух элементов, называют многозначными. Они либо сводятся каким-нибудь способом к двузначным объектам, либо обслуживаются аппаратом многозначной логики .

Устоявшееся представление о математической логике как науке, изучающей законы мышления с применением аппарата математики, главным образом, для нужд самой математики, в современных условиях становится слишком узким. С расширением областей применения и дальнейшим развитием математической логики изменяется и взгляд на нее. Объектами математической логики являются любые дискретные конечные системы, а ее главная задача – структурное моделирование таких систем.

2. Булевы функции.Объекты с двумя возможными состояниями характеризуются булевыми переменными , которые способны принимать лишь два различных значения. Для обозначения этих двух значений обычно используются цифры 0 и 1 или буквы Л (ложно) и И (истинно).

- 62 -

Отношения между булевыми переменными представляются булевыми функциями , которые подобно числовым функциям могут зависеть от одной, двух и, вообще, n переменных (аргументов). Запись у = f(x 1, x 2, …,x N) означает , что у - функция аргументов x 1, x 2, …,x N. Важнейшая особенность булевых функций состоит в том, что они, как и их аргументы, принимают свои значения из двухэлементного множества {0,1}, или (И, Л}, т. е. характеризуются одним из двух возможных состояний.

Функции небольшого числа переменных можно задавать с помощью таблиц, подобных таблицам сложения и умножения одноразрядных чисел. Для этого нужно только указать значения функции для каждой комбинации значений ее аргументов. Основными в двузначной логике являются следующие три функции.

Отрицание - функция у = f(х), принимающая значения 1, когда х = 0, и значение 0, когда х = 1; она обозначается у = x̅ (читается «не х»).

Дизъюнкция — функция у = f(x 1, x 2), принимающая значение 0 тогда и только тогда, когда оба аргумента имеют значение 0; она обозначается у = x 1∨ x 2(читается «у = x 1или x 2»).

Конъюнкция —функция у = f(x 1, x 2), принимающая значение 1 тогда и только тогда, когда оба аргумента имеют значение 1; она обозначается у = x 1∧ x 2(«у = x 1и x 2»).

Таблицы для этих функций имеют вид:

3. Логические операции и формулы.Булевы функции можно рассматривать как логические операции над величинами, принимающими два значения - 0 и 1. Отрицание - это одноместная операция, а дизъюнкция и конъюнкция — двухместные операции. При этом выражения x̅ , x 1∨ x 2, x 1∧ x 2являются логическими формулами.

Более сложные формулы получаются замещением входящих в них переменных другими логическими формулами, которые обычно заключаются в скобки. Например, положив x 1= a̅ и x 2= b ∧ c из x 1∨ x 2,имеем ( a̅ ) ∨ (b ∧ c).

- 63 -

Каждая формула определяет некоторую булеву функцию. Ее значение при различных значениях переменных определяется на основании таблиц функций, приведенных в (2). Так, при а = 0, b = 1 и с = 0 имеем:

x 1= a̅ = 0̅ =1, x 2= b ∧ с = 1 ∧ 0 = 0 и x 1∨ x 2= a̅ ∨ (b ∨ c) = 1 ∨ 0 = 1. Аналогично получаем значения функции и при других комбинациях значений аргументов.

Две функции (как и определяющие их формулы) считаются равносильными,если при любых значениях аргументов эти функции (формулы) принимают одинаковые значения. Равносильные функции соединяются знаком равенства, например: (х ∧ у) ∨ z̅ = ( ) ∧ z или ((х ∨ x̅ ) ∧ у) ∨ (у ∨ х) == х ∨ у. Равносильность функций проверяется по таблицам основных операций, причем необходимо сравнить их значения для всех комбинаций значений переменных.

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

На основе определения основных операций нетрудно убедиться в справедливости следующих тождеств (свойств) булевой алгебры: