Муниципальное общеобразовательное учреждение – средняя школа №2

Вид материала

Документы

Содержание Что такое вывод? Окончательный вывод) Отрицание и конъюнкция Алгебра логических значений Некоторые другие логические операции

Подобный материал:

• Публичный доклад Муниципальное общеобразовательное учреждение средняя общеобразовательная, 590.51kb.
• Российская Федерация Орловская область Муниципальное общеобразовательное учреждение, 1393.13kb.
• Никулина Ольга Сергеевна, учитель биологии, муниципальное общеобразовательное учреждение, 186.62kb.
• Муниципальное общеобразовательное учреждение средняя общеобразовательная школа, 144.11kb.
• Сергеева Лидия Алексеевна 2010 Муниципальное общеобразовательное учреждение «Средняя, 246.41kb.
• Приказ № от 2011г. Рабочая программа учебного предмета Муниципальное общеобразовательное, 767.15kb.
• Публичный доклад 2007 Муниципальное общеобразовательное учреждение средняя общеобразовательная, 618.02kb.
• Муниципальное общеобразовательное учреждение средняя общеобразовательная школа, 23.73kb.
• О. В. Раннева Муниципальное общеобразовательное учреждение «Средняя общеобразовательная, 121.07kb.
• Муниципальное общеобразовательное учреждение, 999.25kb.

иррациональное число рассматривали как корень n -ой степени из целого или дробного числа, когда результат извлечения корня нельзя выразить “точно” целым или дробным числом;

иррациональное число трактовали как границу, к которой его рациональные приближения могут подойти как угодно близко;

число рассматривали как отношение одной величины к другой величине того же самого рода, взятой за единицу; когда величина несоизмерима с единицей, число называли иррациональным.

Позднее Эйлер, Ламберт показали, что иррациональные числа можно представить бесконечными непериодическими десятичными дробями (например, π = 3,141592…). Свое дальнейшее развитие теория иррациональных чисел получила во второй половине XIX века в трудах Дедекинда, Кантора и Вейерштрасе в связи с потребностями математического анализа.

Рациональные и иррациональные числа на 3-ем уровне обобщения образовали действительные числа.

Мнимые числа

Еще более странными, чем иррациональные, оказались числа новой природы, открытые итальянским ученым Кардано в 1545 году. Он показал, что система уравнений , не имеющая решений во множестве действительных чисел, имеет решения вида , . Нужно только условиться действовать над такими выражениями по правилам обычной алгебры и считать, что · = - . Кардано называл такие величины “чисто отрицательными” и даже “софистически отрицательными”, считал их бесполезными и старался не употреблять. Долгое время эти числа считали невозможными, несуществующими, воображаемыми. Декарт назвал их мнимыми, Лейбниц – “уродом из мира идей, сущностью, находящейся между бытием и небытием”. В самом деле, с помощью таких чисел нельзя выразить ни результат измерения какой-нибудь величины, ни изменение какой-нибудь величины. Мнимым числам не было места на координатной оси. Однако ученые заметили, что если взять действительное число b на положительной части координатной оси и умножить его на , то получим мнимое число b , неизвестно где расположенное. Но если это число еще раз умножить на , то получим -b , то есть первоначальное число, но уже на отрицательной части координатной оси. Итак, двумя умножениями на мы перебросили число b с положительного в отрицательные, и ровно на середине этого броска число было мнимым. Так нашли место мнимым числам в точках на мнимой координатной оси, перпендикулярной к середине действительной координатной оси. Точки плоскости между мнимой и действительной осями изображают числа, найденные Кардано, которые в общем виде a + b·i содержат действительные числа а и мнимые b·i в одном комплексе (составе), поэтому называются комплексными числами. Это был 4-ый уровень обобщения чисел.

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

.

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

Леонард Эйлер вывел в 1748 году замечательную формулу:

,

которая связывала воедино показательную функцию с тригонометрической. С помощью формулы Эйлера можно было возводить число е в любую комплексную степень. Любопытно, например, что . Можно находить sin и cos комплексных чисел, вычислять логарифмы таких чисел и т.д

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

Геометрическое истолкование комплексных чисел

Около 1800-го года сразу несколько математиков (Вессель, Арган, Гаусс) поняли, что комплексными числами можно моделировать векторные величины на плоскости. Если действительные числа (состоящие из одного элемента) одномерны – они размещаются на одной координатной оси. Комплексные числа состоят из двух элементов, для их представления необходима уже плоскость и две координатные оси. Это значит, что они двумерны. Оказалось, что комплексное число z = a + b · i можно изобразить точкой М(a,b) на координатной плоскости. Позднее выяснили, что удобнее всего изображать число не самой точкой М , а в виде вектора , идущего из начала координат в точку с координатами а и b. Вектор можно задавать не только его координатами a и b , но также длиной r и углом φ , который он образует с положительным направлением оси абсцисс. При этом a = r · cos φ , b = r · sin φ и число z принимает вид z = r ·(cos φ + i · sin φ) , который называется тригонометрической формой комплексного числа. Число r называют модулем комплексного числа z и обозначают . Число φ называют аргументом z и обозначают Arg Z . Заметим, что если z = 0, значение Arg Z не определено, а при z ≠ 0 оно определено с точностью до кратного 2π. Упомянутая ранее, формула Эйлера позволяет записать число z в виде z = r · e ^{iּ φ} (показательная форма комплексного числа). Геометрическое истолкование комплексных чисел позволило определить многие понятия, связанные с функцией комплексного переменного, расширило область их применения.


Векторные числа

В дальнейшем стали разыскивать некие трехмерные числа, которые моделировали бы векторные величины в пространстве с его тремя координатными осями. Бился над этой задачей и ирландский ученый Гамильтон. После 15-ти лет работы в 1843 году Гамильтон придумал таки трехмерные числа a + bi + cj + dk , где i = j = k = и откладываются каждый на своей оси. Такие числа - комплексные a + bi и мнимые cj и dk по двум дополнительным осям – Гамильтон назвал кватернионами (quaterni в переводе с латыни – четыре). Позже, в 1853 году, как вариант кватернионов, Гамильтон предложил более удобные числа bi + cj + dk и назвал их векторными числами. Они и обобщили все предыдущие числа на 5-ом уровне обобщения.

Матричные числа

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

Векторные числа + тензорные величины породили матричные числа. Это был 6-ой уровень обобщения чисел.

Выделим особенность всех сложных ( комплексных, векторных, матричных ) чисел : они моделируют сразу два свойства – количество и направление моделируемых величин.

Трансфинитные числа

Наконец, в 1883 году немецкий ученый Георг Кантор, по-видимому, оценив многовековую историю последовательного обобщения чисел, в которой натуральные числа были обобщены с рациональными, а те в свою очередь – с действительными, те – с комплексными, те – с векторными, те – с матричными, создал на этом материале свою теорию трансфинитных (бесконечных, запредельных) чисел.

Для этого он назвал множеством всякий набор элементов, который можно сопоставить с частью самого себя, как например, целые числа сопоставляются с четными числами: Кантор заметил, что такое множество должно содержать бесконечное число элементов. А если эти элементы сопоставимы с множеством натуральных чисел, то их количество образует первое трансфинитное число א ₀ (алеф-нуль – с иврита). Но множество א ₀ тоже бесконечно много, и они вместе, как количество элементов нового множества, образуют следующее трансфинитное число א ₁ . И так далее…

Такой красивой теорией Кантор завершил обобщение чисел на 7-ом уровне. И до настоящего времени абстрактнее ее нет: пока ничто не поглотило трансфинитные числа . Однако правда и то, что трансфинитные числа не нашли еще применения за пределами самой математики. История с нулем и комплексными числами снова повторяется для трансфинитных чисел : что ими можно моделировать? Уже больше века не знают. Может, Кантор породил красивую, но мертвую теорию? Кантор долго анализировал трансфинитные числа и установил, что они могут моделировать либо просто количество (тогда это количественные, кардинальные трансфинитные числа, например – множество учеников в классе), либо количество и направление (тогда это порядковые, ординальные трансфинитные числа, например – то же множество учеников, но упорядоченное по успеваемости). Но эти свойства (количество и направление) успешно моделируются числа меньших уровней обобщения. А таблица чисел подсказывает закономерность: чтобы стать абстрактнее, новые числа должны моделировать больше, развиваясь от уровня к уровню либо экстенсивно, меняясь количественно (например, в учете моделирующих элементов числами уровней 1, 2, 3: натуральные + ноль + отрицательные + иррациональные ; или в учете моделируемых направлений числами уровней 3, 4, 5, 6: одномерно-двумерные-трехмерные-многомерные и т.п).

Функции = функциональные числа?

Наш земляк С.Ф.Клюйков утверждает, что принятые во всем мире и представленные в таблице 1 уровни обобщения чисел не совсем полны, они включает не все уже известные числа.

Функциональная зависимость

Так, система координат была предложена в 1637 году Рене Декартом не для изображения комплексных чисел , а для представления функций, уравнений, описывающих различные кривые линии, поверхности, объемы тел – моделирующих аналитически любые геометрические формы. Но не только один Декарт, много других ученых до и после него приложило немало усилий в формирование нового общего понятия – функциональная зависимость. Для этого пришлось перейти от конкретных чисел к их буквенным символам, которые могли принимать то одно, то другое количественное значение, могли меняться, были переменными. Эти переменные величины назвали аргументами и функциями, а выражения, связывающие их, - уравнениями, формулами, функциональными зависимостями. И так увлеклись этими названиями, отражающими только одно из свойств чисел, что забыли: аргументы и функции первоначально все-таки числа, но уже иные – функциональные числа. Это такие же математические модели, как и предыдущие ( натуральные, рациональные, действительные ) числа, но с новым свойством – способностью моделировать не только количество, но и его функциональную зависимость от других количеств . Это позволило моделировать не только “стада баранов”, но и изменяющиеся процессы, движение, саму жизнь…

С.Ф.Клюйков выделяет функциональные числа как 8-ой уровень обобщения чисел. И.Бернулли (1718 г) и Л.Эйлер (1748 г) называли функцией “количество”, образованное переменными и постоянными величинами, зависящее от них. П.Дирихле (1837 г) называл то же “количество” - “значение”, которому соответствует определенное значение аргумента. Н.И.Лобачевскмй (1834 г) назвал функцией “число”, зависящее от аргумента. БСЭ (1978 г) называет функцией “зависимость” двух переменных величин.

Таким образом, разные авторы дают разное определение функции: “количество”, “число”, “зависимость”, акцентируясь на разных гранях этого сложного понятия, так как функция одновременно и “количество”, и “число”, и “зависимость”, а именно: функция – это число, моделирующее количество и зависимость.

Развитие функциональных чисел

История зарождения и развития функциональных чисел чрезвычайно длительна и богата. Их совершенствовали уже ученые Древнего Востока (Х в. до н. э.), находя объемы сосудов для зерна, сдаваемого в виде налога; античные греки (III в. до н.э.), исследуя конические сечения; Галилей (1638 г.), проверяя опытом свои формулы движения тел. Впервые ясно и отчетливо функциональные числа были представлены Лагранжем (1797 г.) в теории функций действительного переменного и ее приложении к разнообразным задачам алгебры и геометрии. Однако в наши дни функциональные числа продолжают совершенствовать, несмотря на громадный накопленный опыт: весь математический анализ с его бесконечными рядами, пределами, минимумами и максимумами, с дифференциальным, интегральным и вариационным исчислением, уравнениями и методами их решения. Но еще более значительными были успехи математики при добавлении способности моделировать функциональную зависимость комплексным числам (Даламбер, 1746 г.). Так возникли комплексно-функциональные числа (9-ый уровень обобщения) в форме функций комплексного переменного, с помощью которых были построены многие полезные математические модели сложных процессов, упрощенно доказательство многих теорем, выполнено описание двухмерных векторов, скалярных и векторных полей, отображение одной плоскости на другую и т.д.

Благодаря соединению способности моделировать функциональную зависимость с векторными числами (Гамильтон, 1853 г.), возникли векторно-функциональные числа (10-ый уровень обобщения). А это – векторный анализ, векторные функции, моделирование переменных полей в сплошных средах и многие достижения теоретической физики…

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

Если добавить трансфинитным числам Кантора способность моделировать функциональную зависимость, то возникнут новые, трансфинитно-функциональные числа (12-ый уровень обобщения), функции трансфинитного переменного, которые, благодаря максимальному на сегодняшний день обобщению, позволят с большей простотой и стандартностью промоделировать все доступное предыдущим числам и откроют новые перспективы в моделировании еще более сложных задач.

Алгебра Дж. Буля

Информация, с которой имеют дело различного рода автоматизированные информационные системы, обычно называется данными., а сами такие системы — автоматизированными системами обработки данных (АСОД). Различают исходные (входные), промежуточные и выходные данные. Данные разбиваются на отдельные составляющие, называемые элементарными данными или элементами данных. Употребляются элементы данных различных типов. Тип данных (элементарных) зависит от значений, которые эти данные могут принимать. В современной безбумажной информатике среди различных типов элементарных данных наиболее употребительными являются целые и вещественные числа, слова (в некотором подалфавите байтового алфавита) и так называемые булевы величины. Первые два типа величин нуждаются в пояснении только в связи с конкретными особенностями их представления в современных ЭВМ. Прежде всего различают двоичное и двоично-десятичное представления чисел. В двоичном представлении используется двоичная система счисления с фиксированным числом двоичных разрядов (чаще всего 32 или, для малых ЭВМ, 16 разрядов, включая разряд для представления знака числа). Если нулем обозначать плюс, а единицей — минус, то 00001010 означает целое число +(2 ³ +2 ^l )= + l0, а 10001100— число— (2 ³ + 2 ² ) = —12 (для простоты взято 8-разрядное представление). Заметим, что знак числа в машинном представлении часто оказывается удобным ставить не в начале, а в конце числа. В случае вещественных чисел (а фактически, с учетом ограниченной разрядности, дробных двоичных чисел) употребляются две формы представления: с фиксированной и с плавающей запятой. В первом случае просто заранее уславливаются о месте нахождения занятой, не указывая ее фактически в коде числа. Например, если условиться, что запятая стоит между 3-м и 4-м разрядами справа, то код 00001010 будет означать число 00001,010= (1 + 0 • 2 ^-1 + 1 • 2 ^-2 + 0 • 2 ^-3 ) = 1,25. Во втором случае код числа разбивается на два кода в соответствии с представлением числа в виде х = а • ^2b . При этом число а (со знаком) называется мантиссой, а число b (со знаком) — характеристикой числа х. О положении кода характеристики и мантиссы (вместе с их знаками) в общем коде числа также устанавливаются заранее. Для экономии числа разрядов в характеристике b ее часто представляют в виде b = ^2k b ₁ , где k — фиксированная константа (обычно k =2). Вводя еще одну константу m и полагая b = 2 ^k b ₂ — m , можно избежать также использования в коде характеристики знака (при малых b ₂ > 0 число b отрицательно, а при больших — положительно). В двоично-десятичном представлении обычные десятичные цифры (а также запятая и знак) кодируются двоичными цифрами. При этом для экономии места часто используется так называемый упакованный код, когда с помощью одного байта кодируется не одна, а две десятичные цифры. Подобное представление позволяет в принципе кодировать числа любой значности. На практике обычно все же ограничивают эту значность, хотя и столь большими пределами, что можно считать их неограниченными. Тип данных “произвольное слово во входном алфавите” не нуждается в специальных пояснениях. Единственное условие — необходимость различать границы отдельных слов. Это достигается использованием специальных ограничителей и указателей длины слов.Тип булева переменная присваивается элементарным данным, способным принимать лишь два значения: “истина” (и) и “ложь” (л). Для представления булевых величин обычно используется двоичный алфавит с условием и = 1, p = 0. Как известно, моделью в математике принято называть любое множество объектов, на которых определены те или иные предикаты. Под предикатом здесь и далее понимается функция у = f(x _i , ..., x _n ), аргументы ( x _i , ..., x _n ) которой принадлежат данному множеству М, а значение (у) может являться либо истиной, либо ложью. Иными словами, предикат представляет собой переменное (зависящее от параметров ( Xi, ..., Хn} высказывание. Оно описывает некоторое свойство, которым может обладать или не обладать набор элементов (Xi, ..., Xn) множества М. Число п элементов этого набора может быть любым. При л = 2 возникает особо распространенный тип предиката, который носит наименование бинарного отношения или просто отношения. Наиболее употребительными видами отношений являются отношения равенства (=) и неравенства ( ¹ ). Эти отношения естественно вводятся для элементарных данных любого данного типа. Тем самым соответствующий тип данных превращается в модель. Применительно к числам (целым или вещественным) естественным образом вводятся также отношения порядка >, <, >, £ , ³ . Тем самым для соответствующих типов данных определяются более богатые модели.Любое множество М, как известно, превращается в алгебру, если на нем задано некоторое конечное множество операций. Под операцией понимается функция у = f (Xi, . .., Хп), аргументы н значение которой являются элементами множества М. При л = 1 операция называется унарной, а при п = 2 — бинарной. Наиболее распространенными являются бинарные операции. Для целых чисел естественным образом вводятся бинарные операции сложения, вычитания и умножения, а также унарная операция перемены знака числа. В случае вещественных чисел к ним добавляется бинарная операция деления и (если необходимо) унарная операция взятия обратной величины. Разумеется, при необходимости могут быть введены и другие операции. Особое место в машинной информатике занимает булева алгебра, вводимая на множестве величин типа булевых. Ее основу составляют две бинарные операции: конъюнкция (“и”), дизъюнкция (“или”) и одна унарная операция: отрицание (“не”). Конъюнкция обозначается символом /\ и задается правилами 0 /\ 0 = 0, 0 /\ 1=0, 1 /\ 0 = 0 , 1 /\ 1=1. Для дизъюнкции используются символ V и правила 0 V 0 = 0, 0 V 1 == 1, 1 V 0=1, 1 V 1 = 1. Наконец, отрицание ù меняет значение булевой величины на противоположное: ù 0=1, ù 1=0. Последовательность выполнения операций производится в порядке убывания приоритетов от ù к /\ и далее к V (если специальной расстановкой скобок не оговорено противное). Например, порядок действий в формуле ù a /\ b \/ c /\ ù d соответствует прямо указанному скобками порядку:

(( ù a) /\ b) V (с /\ ù a)).

В принципе могут быть введены и другие операции, однако оказывается, что любую такую операцию можно выразить в виде формулы, использующей только конъюнкции, дизъюнкции и отрицания. Таким образом, введенный набор операций является для булевой алгебры универсальным. Поскольку любая алфавитная (буквенно-цифровая) информация может быть закодирована в двоичной форме, то подобным образом могут быть закодированы условия и решения задач ил любой области знаний. Если число таких задач конечно (хотя, может быть, и очень велико), то существуют максимальная длина т кода условий этих задач и максимальная длина n кода nх решений. В таком случае решения всех данных задач (в двоичном коде) могут быть получены из их условий с помощью некоторой системы булевых функций y _i =f _i (x _i , х ₂ , ... ..., x _m ) (i == 1, ..., n). В свою очередь все эти функции могут быть выражены через элементарные булевы операции конъюнкции, дизъюнкции и отрицания. Существуют различные способы представления булевых величин (двоичных цифр) в виде тех или иных физических (обычно электрических) сигналов (высокое и низкое напряжение, импульсы тока разной полярности и т. п.). Выбрав форму представления (двоичных) сигналов, можно построить элементарные устройства, называемые обычно логическими вентилями (или логическими элементами), которые реализуют элементарные булевы операции. Иными словами, выходные сигналы этих устройств представляют собой элементарные булевы функции (результат выполнения элементарных булевых операций) от входных сигналов, как это показано на рис. 1

Имея запас таких элементов, можно строить более сложные схемы, подсоединяя выходы одних элементов к входам других. Если при таких соединениях избегать возникновения замкнутых контуров (например, подсоединения выхода элемента на один из его собственных входов), то возникает класс схем, называемых обычно комбинационными схемами. Такие схемы находятся в однозначном соответствии с формулами булевой алгебры, так что с их помощью может быть выражена любая система булевых функций. Например, схема, изображенная на рис. 2, реализует систему булевых функций

u = x /\ y \/ ù z и v = ù (x V y V z).

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



Из сказанного ясно, что можно построить комбинационную схему для решения любого конечного множества задач, решения которых однозначно определяются их условиями (подаваемыми на вход схемы). В частности, если ограничиться какой-либо фиксированной точностью представления вещественных чисел (разрядностью), то можно в принципе построить комбинационную схему, вычисляющую любую заданную вещественную функцию у = f(x _i , ..., x _n ) (в двоичных кодах). На практике, однако, оказывается, что уже схема умножителя (вычисляющая функцию у = X ₁ • Х ₂ ) при разрядности (двоичной) 32 и более оказывается столь сложной, что умножение в современных ЭВМ предпочитают реализовать другим, так называемым алгоритмическим способом, о котором речь пойдет ниже. В то же время многие, более простые функции, например функции сложения двух чисел, реализуются комбинационными схемами приемлемой сложности. Соответствующая схема носит наименование параллельного сумматора. Следует заметить, что успехи микроэлектроники делают возможным построение все более сложных схем. Если еще в 60-е годы каждый логический элемент собирался из нескольких физических элементов (транзисторов, диодов, сопротивлений и др.), то уже к началу 80-х годов промышленностью выпускаются так называемые интегральные схемы, содержащие многие сотни и даже тысячи логических вентилей. При этом важно подчеркнуть, что не только сами логические элементы, но и соединения между ними (т. е. вся схема в целом) изготовляются одновременно в едином технологическом процессе на тонких пластинках химически чистого кремния и других веществ размерами в доли квадратного сантиметра. Благодаря этому резко уменьшилась стоимость изготовления схем и повысилась их надежность. Обладая возможностью реализовать любые ф и к с и р о в а н н ы е зависимости между входными и выходными сигналами” комбинационные схемы неспособны обучаться, адаптироваться к изменяющимся условиям. На первый взгляд кажется, что такая адаптация обязательно требует структурных изменений в схеме,. т. е. изменения связей между ее элементами, а возможно, и состава этих элементов. Подобные изменения нетрудно реализовать путем механических переключении. Однако такой путь практически неприемлем из-за резкого ухудшения практически всех параметров схемы (быстродействия, габаритов, надежности и др.). Существует гораздо более эффективный путь решения указанной проблемы, основанный па введении в схему в дополнение к уже перечисленным логическим элементам так называемых элементов памяти. Помимо своих входных и выходных сигналов, элемент памяти характеризуется еще третьим информационным параметром—так называемым состоянием этого элемента. Состояние элемента памяти может меняться (но не обязательно) лишь в заданные дискретные моменты времени t _1, t ₂ , ... под влиянием сигналов, появляющихся на его входах в эти моменты. Наиболее употребительна так называемая синхронная организация работы элементов памяти, при которой моменты их возможных переключении (изменении состояния) следуют друг за другом через один и тот же фиксированный промежуток времени D t = const, называемый тактом. Эти моменты определяются обычно с помощью импульсов, вырабатываемых специальным тактирующим синхрогенератором. Количество тактовых импульсов, выдаваемых им в течение одной секунды, называется тактовой частотой. В современной электронике употребляются в основном двоичные элементы памяти, состояние которых представляет собой булеву величину. Иными словами, элемент памяти способен запомнить всего лишь один бит информации. При необходимости запоминания большего количества информации используется составная память (запоминающее устройство), состоящая из некоторого множества элементов. В реальных условиях это множество, разумеется, всегда конечно, хотя в теоретических исследованиях бывает удобно рассматривать и бесконечную память (по крайней мере потенциально).В простейшем случае множество элементов памяти организуется в так называемый регистр, т. е. в (конечную) линейно упорядоченную последовательность элементов, называемых разрядами (ячейками) регистра. Разряды нумеруются последовательными натуральными числами 1, 2, ..., п. Число п этих разрядов называется длиной регистра. Состояния в, отдельных разрядов составляют (булев) вектор о, называемый состоянием регистра. Входные и выходные сигналы отдельных разрядов рассматриваемого регистра (также предполагаемые булевыми) составляют соответственно входной х и выходной у (векторные) сигналы данного регистра. Заметим еще раз, что в подавляющем большинстве случаев у = а. Обычная последовательностная схема, называемая также конечным автоматом, составляется из регистра памяти и двух комбинационных схем. Условность подобного представления заключается прежде всего в том, что в схеме с чисто двоичными сигналами нельзя переключить сигнал и на один из выходов, а на других выходах де иметь ничего (это был бы третий вид сигнала, отличный как от 0, так и от 1). Кроме того, в подавляющем большинстве случаев схемы нецелесообразно строить отдельно одну от Другой, так как при этом, вообще говоря, возрастает общее число используемых логических элементов. Однако эти условности не меняют главного — сделанных оценок для числа различных комбинационных схем, реализуемых конечным автоматом. Кроме того, при некоторых реализациях двоичных сигналов (например, импульсами различной полярности) в электронных схемах естественным образом реализуется и третий вид сигнала, а именно, отсутствие каких-либо импульсов. В этом случае предложенная интерпретация фактически теряет свою условность и может быть реализована практически.

Математическая логика

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

Простейшие закономерности выводов открывались человечеством эмпирическим путем в ходе общественного производства (например, простейшие соотношения арифметики и геометрии). Открытие более сложных законов связано с результатами науки формальной логики. Первое крупное обобщение формальной логики принадлежит Аристотелю. В формальной логике с самого начала применялись (в единичных случаях) математические методы, но развитие логики не успевало за применением таких методов по сравнению с другими областями математики. Поэтому формальная логика отстала от потребностей науки (в первую очередь от требований математики); отставание оказалось особенно очевидным в новую эру. Главными недостатками формальной логики являлись следующие .1. Она не сумела привести законы выводов к небольшому количеству надежных логических законов; поэтому подтвердила правильность некоторых выводов на основе экспериментов, которые позже были опровергнуты примерами, доказывающими обратное.2. Она была неспособна анализировать значительную часть выводов, применяемых в повседневной и научной жизни; доказать правильность или неправильность таких выводов. (Например, не могла доказать, что из правильности предложения “Каждая трапеция является четырехугольником” вытекает правильность предложения “Кто рисует трапецию, тот рисует четырехугольник).Задача математизации формальной логики была поставлена и осуществлена Лейбницем. Его работу продолжили математики XIX века. На рубеже столетия с открытием противоречий в теории множеств (см. гл. “Теория множеств”) развитие математической логики получило широкий размах. В настоящее время результаты математической логики используются во всех традиционных областях формальной логики; открыты совершенно новые области. В настоящее время “традиционная” формальная логика по сравнению с математической логикой имеет значение только для истории науки.Математическая логика не претендует на открытие законов мышления вообще, или еще в меньшей степени на анализ философских проблем, связанных с человеческим мышлением. Эти вопросы больше относятся к “логике” (в более общем смысле слова) и к философии. (В дальнейшем под словом “логика” будем подразумевать математическую логику.)

^ ЧТО ТАКОЕ ВЫВОД?

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

1. ( Предпосылки) Если будет раздача премии, то мы выполнили план.
   

Будет раздача премии.( ^ Окончательный вывод) Мы выполнили план. Если принять правильность предпосылок, то следует принять и правильность окончательного вывода. Другой, аналогичный пример :Если мне выпадет туз, то я иду ва-банк. Мне выпал туз.Я иду ва-банк.Обычно вместо предложений (мне выпал туз) и (я иду ва-банк) могут быть записаны любые такие изъявительные предложения, значения которых может быть правильно или ложно; следует оставить неизменными только расположение слов “если” и “то” и расположение предположений, то есть структуру вывода. Пусть А и В обозначает любые заменяющие предложения. Структуру вывода можно выразить следующей схемой;Если А, то В АВПод определением, что данная схема представляет собой (логически правильную) схему выводов, подразумевается следующее. Если вместо А и В подставить такие предложения, что предпосылки, полученные в результате замены, будут правильными, то и окончательный вывод будет правильным. Любой человек, который понимает значение союзов “если . . . то”, поймет, что это правильная схема вывода. В схеме вывода фигурируют несколько слов с постоянным значением, далее несколько символов (букв) с меняющимся значением. Символы с меняющимся значением могут быть переменными разных типов. В соответствии с их типом вместо символов могут быть подставлены разные грамматические формации (например : изъявительные предложения, слова, выражающие свойства, названия предметов и т. д.). В предыдущем примере переменные А и В заменяются только изъявительными предложениями. На основе “регулярной” замены переменных некоторой (правильной) схемы вывода должен возникать правильный вывод.Но определение “регулярной замены” означает не только соблюдение грамматических правил. В предыдущей схеме А и В могут означать только такие изъявительные предложения, правильность или ложность которых может быть решена однозначно. Такие изъявительные предложения будем называть высказываниями. На основе любой схемы вывода может быть получен правильный вывод только при соблюдении условий подобного характера. Путем изменения условий могут быть построены различные теории логики. Важнейшими главами математической логики являются калькуляция высказываний и калькуляция предикатов. В рамках данных глав может быть исследована схема вывода в самом общем случае при наименьшем числе условий. В других главах логики рассматриваются специальные схемы вывода, являющиеся менее общими.

Калькуляция высказываний

  ВЫСКАЗЫВАНИЕ.

Предметом калькуляции высказываний является анализ таких схем вывода, при которых с заменой переменных на высказывания, получаются правильные выводы. Под термином высказывания подразумевается такое изъявительное предложение, которое является однозначно или правильным, или ложным ; итак: а) оно не может одновременно быть и правильным, и ложным (принцип непротиворечивости);б) исключено, чтобы оно было и неправильным, и неложным (принцип исключения третьей возможности).Свойства “правильное” и “ложное” подразумеваются в их обычном смысле; они не нуждаются в дальнейшем анализе. При данных обстоятельствах приведенные выше изъявительные предложения удовлетворяют (с “хорошим приближением”) этим двум условиям; их можно считать высказываниями. Поэтому логика, построенная на этих двух условиях, может получить весьма широкое применение. Естественно, существуют такие “тонкие обстоятельства”, при которых некоторых изъявительных предложений нельзя считать высказываниями (например, если дано предложение : “Иван просыпается”, вряд ли можно сомневаться в правильности или ложности предложения “Иван спит”). Математические термины определяются таким образом, что предложения, выражающие соотношения между ними, всегда считаются высказываниями; такое положение существует во всех точных науках. Понятие “высказывание” иногда обозначается словами “утверждение”, “суждение”.В выводах могут фигурировать высказывания (либо в виде предпосылок, либо как окончательный вывод), возникшие из одного или нескольких высказываний, путем применения некоторого грамматического метода; они называются сложными высказываниями. Во многих случаях правильность вывода зависит от вида формирования сложного высказывания. Поэтому необходимо заниматься видом формирования сложных высказываний некоторых типов. Под термином калькуляции высказываний подразумевается такой метод, с помощью которого из одного или нескольких высказываний (членов операции калькуляции высказываний) получается такое высказывание (результат операции), правильность или ложность которого однозначно определяется правильностью или ложностью членов.

^ ОТРИЦАНИЕ И КОНЪЮНКЦИЯ.

Двумя простейшими примерами вышеприведенной операции являются отрицание и конъюнкция. (Операция и результат операции здесь обозначается одним и тем же названием.)Под отрицанием высказывания А подразумевается высказывание “Неправильно, что А” (или некоторая грамматически преобразованная форма данного высказывания).По значению выражения “неправильно” отрицание А правильно тогда и только тогда, если самое А неправильно; следовательно, отрицание действительно есть операция калькуляции высказываний (в соответствии с вышеприведенным определением). Пример: Отрицанием предложения “мотор работает” является предложение “неправда, что мотор работает” или, иначе: “мотор не работает”.Отрицание является одночленной операцией. Отрицание “А” обозначается символом “~А” (читается : “не А”). Применяются также и обозначения “~ А”, “— А”, “А”.Под конъюнкцией двух высказываний А и В подразумевается высказывание “А и В” (или некоторая грамматически измененная форма данного высказывания). По значению союза “и” конъюнкция является правильной тогда и только тогда, если оба ее члена правильны. Таким образом, конъюнкция также является операцией калькуляции высказываний. Операция конъюнкции “А и В” представляет собой двучленную операцию; ее обозначают, “А & В”, “АВ”. При возникновении конъюнкции союз “и” иногда заменяется другим союзом (например, “Анатолий здесь, но Бориса нет” или “Анатолий здесь, хотя Борис ушел” и т. д.). Это не влияет на правильность или ложность результата, имеет только эмоциональное значение. Иногда союз вообще пропускается. Если сказуемые двух предложений, связанных между собой путем конъюнкции, совпадают, то общее сказуемое представлено только в одном из предложений. Например, конъюнкция “я питаюсь хлебом и питаюсь водой” после преобразования имеет следующий вид: “я питаюсь хлебом и водой”. Изучение остальных операций калькуляции высказываний уточняется и облегчается с помощью следующего рассуждения. Пусть свойства высказываний “правильное” и “ложное” называются логическими значениями и обозначаются знаками пил. Правильность (или ложность) некоторого высказывания А выражается и в такой форме, что логическим значением высказывания А является п (или л).Если задаются логические значения отдельных членов в некоторой операции калькуляции высказываний, то данной операцией логическое значение результата определяется однозначно. Это позволяет определение таких операций для логических значений (кроме вышеприведенного определения для высказываний) следующим образом: На место и членов и результата подставляются логические значения; причем, вместо результата подставляется логическое значение высказывания, образующееся данной операцией из высказываний с соответствующими членам логическими значениями. Например, отрицания логических значений определяются так: (так как отрицание правильного высказывания является ложным), (так как отрицание ложного высказывания является правильным);а конъюнкции логических значений так:(так как конъюнкция двух правильных высказываний является правильной), (так как если одно или оба из двух высказываний являются ложными, то и их конъюнкция будет ложной)На основе вышеприведенного рассуждения изучение операций, проведенных на высказываниях, может быть заменено изучением операций, проведенных на логических значениях. Этого достаточно для исследования выводов (на уровне калькуляции высказываний). 

^ АЛГЕБРА ЛОГИЧЕСКИХ ЗНАЧЕНИЙ

Операции, проводимые на логических значениях, называются логическими операциями. Для выражения любых логических значении вводятся логические переменные; они обозначаются символами p, q, r, ..., р, р, … Итак, логические переменные могут принимать два “значения”: п или л .При использовании нескольких операций последовательно порядок выполнения отдельных операции обозначается скобками; например, ~(р) А q) (иногда скобки опускаются). Например, вместо выражения (7p)/\q пишется 7р /\ q при предварительном пояснении, что в случае появления выражения без скобок знак относится только к следующему знаку. В общем смысле слова n -членной логической операцией называется каждая такая функция, областью существования которой является упорядоченное множество всех выражений, образуемых из логических значений пиле длиной выражения n , а значением ее является одно из двух логических значений п и л. Любая логическая операция может быть выражена через операции отрицания и конъюнкции.

^ НЕКОТОРЫЕ ДРУГИЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ.

В области операций на логических переменных помимо отрицания и конъюнкции оказываются полезными некоторые другие операции. В области одномерных логических операций фактический интерес представляет только отрицание. Дизъюнкция. Операция называется дизъюнкцией и обозначается символом “p\/q” (иначе ее называют альтернацией, адъюнкцией, логическим сложением), или “р + q”. Дизъюнкция выражается с помощью операций конъюнкции и отрицания. Связь, созданная между двумя высказываниями при помощи уступительного союза “или”, является такой операцией, которой в области логических значений соответствует операция дизъюнкции: высказывание является ложным тогда и только тогда, если оба высказывания ложны.(Союз “или” в таком случае применяется в значении допущения, если допускается правильность обоих высказываний). Например: “выпал дождь или полили парк”. Поэтому такое соединение двух высказываний также называется дизъюнкцией. (Символ “V” читается также как “или”). Операция конъюнкция выражается с помощью операций дизъюнкции. Таким образом, руководствуясь теоремой, что каждая логическая операция может быть выражена с помощью только операций дизъюнкции и отрицания“ни-ни”