<< Пред. стр. 1 (из 7) След. >>
Список литературы по разделу
РАЗДЕЛ 2. ОСНОВЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ
Возникновение науки, как обобщенного понятия, было таким фактом истории человечества, которому невозможно найти что-либо равное по значимости, как для самих людей, так и для окружающей их природы. Что именно позволяет нам говорить, что с такого-то времени донаучное познание уступило свой приоритет научному? Какие качественные изменения форм мышления и познания можно считать собственно "рождением" науки?
Академик В.И. Вернадский датирует возникновение науки открытием знаменитого музея в Александрии. Однако этому предшествовало исключительно важное дело, начатое греческими мыслителями и успешно завершенное Аристотелем. Начало науки о законах и формах мышления связывают с именем Аристотеля, который впервые выделил и систематизировал общезначимые (универсальные для человеческого мышления) способы рассуждений. Именно идея возможности выявления общезначимых способов рассуждений явилась необходимой предпосылкой формирования научного мышления.
Любопытно отметить, что после падения античной цивилизации первое, что было восстановлено из античной науки, — это логика Аристотеля. Известно, что христианство сначала отрицательно относилось ко всей античной науке, и признание ее началось именно с первых семи глав аристотелевских "Аналитик". В эпоху Возрождения, в истоках науки нового времени, также первыми восстанавливались и использовались именно разработанные в античности логические методы. С этого начиналась философия Декарта и других мыслителей, формировалась вся новая наука. Таким образом, вопрос об общезначимых, правильных способах рассуждений является исключительно важным, одним из центральных вопросов, связанных с возникновением, развитием и функционированием любого научного знания. Это, в свою очередь, определило и задачи дальнейшего развития самой логики.
2.1 Основные понятия алгебры логики
Считают, что Аристотелю принадлежит открытие формального характера логического вывода. Одни предложения выводятся из других в силу определенной связи между их формой и структурой, независимо от их конкретного содержания. В каждом из рассуждений, состоящих из двух предложений (посылок), выводится третье (заключение), записанное после слова "следовательно".
Например, существует предание, что Александрийскую библиотеку сжег калиф Омар. Он обосновал свое деяние с помощью следующего рассуждения:
"Если ваши книги согласны с Кораном, то они излишни. Если они не согласны с Кораном, то они вредны. Но вредные или излишние книги следует уничтожить. Значит ваши книги следует уничтожить." Такое рассуждение с логической точки зрения совершенно правильно. Первые три предложения в примере являются посылками, четвертое — заключением. Другое дело, что не истинны посылки, которые в нем используются, но интерес представляет только правильность самого рассуждения, независимо от истинности посылок и заключения.
Правильность вывода заключения из посылок определяется не конкретным содержанием рассуждения, а формой посылок и заключения. Формальная логика изучает формы человеческих рассуждений, отвлекаясь от их конкретного содержания.
Прошло два тысячелетия, прежде чем немецкий математик и логик Лейбниц предложил ввести в формальную логику математическую символику и использовать её для общих логических построений. Эту идею последовательно реализовал в XIX столетии Джордж Буль и тем самым заложил основы математической (символьной) логики. В трудах Буля и шотландского математика Огастеса де Моргана формальная логика оформляется в математическую логику, которая стала представлять собой своеобразную алгебру — алгебру логики. Главная цель применения в логике математической символики заключалась в том, чтобы свести операции с логическими заключениями к формальным действиям над символами. При этом исходные положения записываются формулами, которые преобразуются по определённым законам, а полученные результаты истолковываются в соответствующих понятиях.
Современный аппарат математической логики в значительной степени сложился под влиянием прикладных программ, в рамках которых развивались его специфические особенности. Пробным камнем среди технических приложений была задача анализа и синтеза контактных схем. Успехи в этой области послужили стимулом для применения аппарата математической логики и в других областях. Триумфом сотрудничества математики и техники явилось создание вычислительных машин с программным управлением. Дальнейшие обобщения привели к развитию теории автоматов, основной задачей которой является математическое моделирование физических и абстрактных процессов, технических устройств и некоторых сторон поведения живых организмов. Автоматы используются в качестве универсальной модели в самых разнообразных областях, в том числе и при проектировании вычислительных машин.
Краткая характеристика ученых в области математической логики
ДЖОРДЖ БУЛЬ
(1815 — 1864)
Английский математик. Родился в Линкольне. Самоучка; самостоятельно изучил греческий, латинский, немецкий, французский и итальянский языки, затем математику. С 16 лет работал помощником учителя в школе. В 1849-1864гг. — профессор математики в Куине — колледже в Корке (Ирландия).
Научные интересы Буля достаточно широки: философия, логика, математический анализ, теория вероятностей. Развил свою систему и изложил её в труде "Исследование законов мышления" (1854г.), в котором, свел логику к алгебраической форме, установив систему аксиом символической логики, т.е. операции исследования и решения "логических" уравнений. Логическое исчисление Буля получило название булевой алгебры. В 40 — 50-х гг. ХХ в. булева алгебра получила особенное значение в связи с развитием вычислительной техники.
Член-корреспондент Петербургской АН (с 1837г.), член многих академий наук и научных обществ.
ОГАСТЕС де МОРГАН
(1806-1871)
Шотландский математик и логик, член Лондонского королевского общества.
Родился в Мадуре (Индия). С 1823г. учился в Кембриджском университете. В 1828 1831гг. и 1836 — 1866гг. — профессор Университетского колледжа в Лондоне.
Работы посвящены основаниям алгебры, математическому анализу, теории вероятностей и логике. Был инициатором применения логических исчислений к обоснованию тeoрем теории вероятностей. Работал над созданием символического исчисления и в области истории математики.
Основатель Лондонского математического общества и его первый президент (с 1866г,), член Королевского астрономического общества.
Методы математической логики находят все более широкое применение в теории преобразования и передачи информации, теории вероятностей и комбинаторном анализе. Интенсивно развиваются специальные разделы математической логики для решения вопросов и проблем в таких конкретных областях как экономика, биология, медицина, психология, языкознание, право и другие.
Логика высказываний
В основе всех видов математической логики лежит простейший раздел—
логика высказываний.
Под высказываниями понимают повествовательные предложения, утверждающие тот или иной факт. Такие предложения называют простыми высказываниями.
Отличительным признаком любого высказывания является его свойство быть истинным (верным) или ложным (неверным). Например, рассмотрим высказывания:
1.Снег белый.
2.Железо растворяется в воде.
З.Поезд прибыл на станцию.
Содержанию высказываний не придают значения. Высказывание может рассматриваться лишь в отношении того, истинно оно или ложно. Относительно третьего высказывания можно предположить, что оно либо истинно, либо ложно в зависимости от обстоятельств, которыми руководствуются при его истолковании (поезд уже прибыл на станцию, или еще не пришел). Побудительные и вопросительные предложения не являются высказываниями.
Таким образом, каждое высказывание может быть истинным или ложным (закон исключения третьего), но не может быть одновременно и истинным и ложным (закон противоречия). Принятие закона исключения третьего позволяет полностью использовать в логике высказываний аппарат двузначной логики. Значения "истина" (TRUE) и "ложь" (FALSE) в логике высказываний обозначают через "И" и "Л", а в двузначной логике соответственно "1" и "0".
Так как логика высказываний не рассматривает конкретного смысла простых высказываний, то каждое из высказываний можно обозначить, например, прописными латинскими буквами А, В, С,...без индексов или с индексами А1, А2 ,.... Буквы, обозначающие высказывания, называют пропозициональными, и они соответственно могут принимать истинностные значения — И (истина) и Л (ложь), или "1" и "0".
В обычном языке из простых предложений образуют сложные предложения с помощью синтенциональных связок "не", "и", "или", "если....,то" и "если и только если". Формальная логика перечисленным синтенциональным связкам ставит в соответствие символы логических операций ?,~ &, V, ?, которые называют пропозициональными знаками (логическими связками). Таким образом, всякое сложное предложение, которое состоит из простых высказываний, связанных пропозициональными знаками, можно представить в символической форме. В результате получают высказывательную формулу. С другой стороны, если имеется некоторая высказывательная формула, то можно построить соответствующее сложное предложение (высказывание), заменяя буквы простыми высказываниями. Полученное таким путем предложение называют подстановкой в данную формулу.
Сентенциональные связки в разговорном языке допускают различные варианты. Поэтому при записи сложного высказывания в виде формулы алгебры логики важно выяснить характер логической связи между простыми высказываниями, не вдаваясь в смысл самих предложений. На каждом наборе значений истинности букв (простых высказываний) формула принимает некоторое значение (истинно или ложно). Следовательно, всякую формулу логики высказываний можно рассматривать как истинностную функцию, которую удобно представлять таблицей истинности (таблицей соответствия).
При первом знакомстве с логикой высказываний часто полученные сложные высказывания с точки зрения "здравого смысла" кажутся нелепыми. Однако необходимо преодолеть психологический барьер и понять, что ограничения, основанные на "здравом смысле" и причинной связи, в логике высказываний не только невозможны, но и нежелательны из-за относительности того или иного высказывания. Например, человеку, который никогда не видел снега и не слышал о нем, фраза "идет снег" покажется бессмысленной, а высказывание "слоны зеленые" может иметь определенный смысл, если речь идет о выборе цвета для игрушечных слонов. Аналогичные соображения можно привести и в пользу допущения логической связи между любыми высказываниями без учета видимой причинной зависимости между ними. Поэтому логика высказываний, отвлекаясь от конкретного содержания высказываний, по существу, занимается анализом и синтезом высказывательных формул, изучением отношений между высказываниями, дает общие принципы логических рассуждений и доказательств. Что же касается "здравого смысла", то он должен проявляться при использовании законов логики высказываний в ее конкретных приложениях, где смысл высказываний должны истолковывать лица, компетентные в соответствующей области.
Логические функции и операции
Отличительная особенность логических функций состоит в том, что они принимают значения в конечных множествах. Иначе говоря, область значений логической функции всегда представляет собой конечную совокупность чисел, символов, понятий, свойств и, вообще, любых объектов. Если любая из независимых переменных (простых высказываний) и высказывательная формула (сложное высказывание) принимают значения из одного и того же множества М, то осуществляется отображение этого множества самого на себя. Соответствующую этому отображению логическую функцию называют однородной . Алгебра, образованная множеством М вместе со всеми возможными операциями на нем, называется алгеброй логики. Если имеют дело с объектами, которые принимают одно из двух возможных значений (И или Л, событие наступило или не наступило, наличие или отсутствие заданного признака у объекта и т. д.), то имеют дело с двухэлементным (двоичным) множеством, например М = {0,1}. Здесь элементы "0" и "1" рассматриваются как формальные символы, не имеющие арифметического смысла.
Алгебра, образованная двухэлементным множеством М вместе со всеми операциями на нем, называется двузначной алгеброй логики.
Будем рассматривать только двузначную логику, на которую, с одной стороны, опираются все построения математической логики; с другой стороны, именно этот аппарат имеет в настоящее время наибольшее прикладное значение.
Функцией алгебры логики (или логической функцией) от n переменных называется n-арная операция на множестве М.
Всякая логическая функция и переменных (аргументов) может быть задана в виде таблицы истинности 2.1, в левой части которой перечислен и все наборов значений переменных (при М = {0,1}), а в правой части — значения 2:n функций на этих наборах. Число различных функций от n переменных может быть равно 2^(2^2).
Таблица 2.1 .- Таблица истинности
X1 X2 … Xn-1 Xn F
0
0
…
1
1 0
0
…
1
1 …
…
…
…
… 0
0
…
0
1 0
1
…
1
1 1
0
…
1
0
В таблице наборы символов "0" и "1" расположены в определенном порядке — лексико-графическом, который совпадает с порядком возрастания наборов, рассматриваемых как двоичные числа. В таблице F =-{f1,f2,…,fm}-
множество логических функций.
Рассмотрим одиннадцать функций, которые играют большую роль в построении теории функций алгебры логики и ее приложениях. Эти функции называют элементарными.
Рассмотрение множества элементарных функций алгебры логики начнем со случая n = О. В этом случае имеются только две функции, совпадающие с константами "0" и "1":
f1 =0; f2 =1.
Обе эти функции считают элементарными.
В случае л =1 имеются две функции, существенно зависящие от аргумента х1. Эти две функции определяются следующей таблицей:
Таблица 2.2 — Функции одного аргумента
X1 f3 f4
0
1 0
1 1
0
Эти две функции также причисляют к элементарным и записывают их следующим образом:
f3 = х (читается "как х ");
f4 = х (читается "не х" ).
Функцию f4 называют функцией отрицания или просто отрицанием.
В случае n = 2имеет место 16-ть однородных функций, из которых только десять различных, существенно зависящих от аргументов х1 и х2. Из этик
десяти функций к элементарным относятся семь функций, представленных таблицей 2.3.
Таблица 2.3 — Функции двух аргументов
х1 х2 f5 f6 f7 f8 f9 f10 f11
0
0
1
1 0
1
0
1 0
1
1
1 0
0
0
1 1
0
0
1 1
1
0
1 1
0
0
0 1
1
1
0 0
1
1
0
Функция , определяемая таблицей, носит название дизъюнкции х1 и x2 или логического сложения. Бинарная операция соединения двух высказываний х1 иx2 в одно с помощью союза ИЛИ (употребляемого в неразделительном смысле — "хотя бы один из двух"), называется логическим сложением (дизъюнкцией), а новое (составное) высказывание — логической суммой. Дизъюнкция — это функция f5 (таблица 2.3), принимающая значение "0" тогда и только тогда, когда обе переменные имеют значение "0". Она обозначается символом v (или+), читается "x1 или х2".
f5 (x1, х2)= x1 v х2
Здесь х1 и x2 называются дизъюнктивными членами логической суммы.
Функция f6 (таблица 2.3) носит название конъюнкции х1 и x2. Бинарная операция соединения двух высказываний х1 и x2 в одно с помощью союза И называется конъюнкцией (логическим умножением), а полученное составное высказывание — логическим произведением. Конъюнкция — функция f6, принимающая значение "1" тогда и только тогда, когда обе переменные имеют значение "1". Конъюнкция обозначается символом & (или ^, -) и читается " х1 и x2"
f6 (x1, х2)= x1 & х2 = x1,^ х2= x1 * х2
Здесь х1 и x2 называются конъюнктивными членами логического произведения. Функция f7 носит название функции эквивалентности (или равнозначности). Эквиваленция (равнозначность) — бинарная операция, обозначаемая символом ~ ( ?, ? ). Высказывание х1 ~ x2 истинно тогда и только тогда, когда х1 и x2 , либо оба истинны, либо оба ложны. Эквиваленция соответствует функции f7 (таблица 2.3), которая равна "1", когда значения ее аргументов равны, и равна "0", когда они различны. Эквиваленция примерно соответствует употреблению в обычной речи связок "х, тогда и только тогда, когда x2", или " х1, если и только если х2". Запись х1 ~ x2 следует читать " х1 эквиваленция x2".
f7 = х1 ~ x2 = х1 ? x2 = х1 ? x2
Функция f8 носит название Импликации х1 в x2. Импликация (следование) — бинарная операция, образующая из двух высказываний х1 и x2 сложное высказывание, которое истинно всегда, кроме того случая, когда х1 истинно, а x2 ложно. Импликация соответствует функции f8, принимающей значение "0" тогда и только тогда, когда х1 (называемое посылкой — антецедентом) равно "1", а x2 (называемое следствием — консеквентом) имеет значение "0". Импликацию обозначают символом ?, она близка по смыслу к союзу "если ..., то ...", но не всегда передает смысл логического следования. Поэтому сложное высказывание х1 ? x2 следует читать "х, имплицирует х2" и понимать эту операцию только так, как это определено функцией f8 (таблица 2.3).
f8(х, x2) = х1 ? x2
Функция f9 носит название функции Вебба или стрелки Пирса. Стрелка Пирса (логическое НЕ — ИЛИ) — бинарная операция, обозначаемая символом "?", образующая сложное высказывание х1 ? x2, которое ложно всегда, кроме того случая, когда х1 ложно и x2, ложно. Соответствует функции f9 (таблица 2.3) и читается " х1 стрелка Пирса x2" или "ни х1, ни x2".
f9(х, x2) = х1 ? x2
Функция f10 называется функцией Шеффера или "штрих Шеффера". Штрих Шеффера (логическое НЕ — И) — бинарная операция, обозначаемая символом "?", образующая сложное высказывание х1 ? x2,которое истинно
всегда, кроме того случая, когда х1 истинно, и x2 истинно. Логическая операция штрих Шеффера соответствует функции f10 (таблица 2.3) и читается " х1 штрих Шеффера x2" или "не x1, или не x2".
f10(х, x2) = х1 ? x2
Функция f11, называется функцией сложения по модулю 2 или неравнозначностью, обозначается символом ?. Высказывание х1 ? x2 истинно тогда и только тогда, когда х1 и x2 различны по значению истинности. Неравнозначность соответствует функции f11 (таблица 2.3), она равна "1", когда значения ее аргументов различны, и равна "0", когда они равны. Операция неравнозначности соответствует связкам " х1 не как x2" или "или х1 или x2".
f11(х, x2) = х1 ? x2
Для удобства пользования символы перечисленных операций приведены
в перечне условных обозначений (с. 5 — 6).
Рассмотренные одиннадцать функций позволяют строить новые функции алгебры логики путем подстановки в функцию новых функций вместо аргументов.
Формулы и тождества алгебры логики
Всякое сложное высказывание, составленное из некоторых простых высказываний посредством логических операций, называют формулой алгебры логики или пропозициональной формой.
Символы переменных А, В,..., х1,x2,... считают формулами глубины ноль. Формулами являются и выражения вида:
А, А*В, A v B, А?В, А~В, А ? В; A?B, А ? В, или
х, х1 * x2 ,х1 v x2 ,х1 ? x2 , y ~ z, x ? z и др.
Как указывалось ранее, значения независимых переменных (простых высказываний), а также функций (сложных высказываний) могут быть представлены различными символами. Условимся в логике высказываний применять прописные латинские буквы А, В, С,...без индексов или А1, А2,... с индексами. При аналитическом задании формул алгебры логики (булевой алгебры) примем обозначения строчными буквами: аргументов x1, x2,..., xm, то есть входной алфавит Х={хi}, i=1,m, хi =( x1, x2,..., xm) или, x,у,z,...;а,b,с,..., а
для функций F = {f1,f2,…,fk}.
Рассмотренные ранее логические функции f1,f2,…,f11 позволяют строить новые функции с помощью обобщенной операции, называемой операцией суперпозиции. Суперпозицией функций F1,…,Fm называется функция F, полученная с помощью подстановок этих функций друг в друга и переименования переменных, а формулой является выражение, описывающее эту суперпозицию. Фактически операция суперпозиции заключается в подстановке вместо аргументов других логических функций или аргументов.
Формулы, наряду с пропозициональными буквами (высказываниями) и знаками (символами логических операций), могут содержать открывающиеся и закрывающиеся скобки, которые служат для указания последовательности выполнения операций. Конкретные логические формулы, как правило, имеют
привычный вид, при котором символы операций стоят между аргументами. Например:
А*В, ((A v В) ~ С) (((А ? В) ? С)*С).
Операция суперпозиции позволяет увидеть качественный переход от числа аргументов n = 1 к n = 2. Действительно, суперпозиция функций одного аргумента порождает функцию одного аргумента. Суперпозиция функций двух аргументов дает возможность строить функции любого числа аргументов. Итак, суперпозиция логических функций представляется в виде логических формул, при этом следует отметить следующее:
одна и та же функция может быть представлена разными формулами;
каждой формуле соответствует своя суперпозиция и, следовательно, своя схема соединения реальных логических элементов, реализующих логические функции;
между формулами представления логических функций и схемами, их реализующими, существует взаимно однозначное соответствие;
всякая формула, выражающая логическую функцию как суперпозицию других функций, задает способ ее вычисления при условии, что известно, как вычислить исходные функции.
Каждая формула задает истинностную функцию, которая может быть представлена таблицей истинности. Например, формуле
((А*В) ~ С) v ((В ? С) ? А)
соответствует таблица истинности:
A B C A*B (A*B) ~C B?C (B?C) ?A ((А*В) v С) v
((В ? С) ? А)
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
0
0
0
0
0
1
1 1
0
1
0
1
0
0
1 1
1
0
1
1
1
0
1 0
0
1
0
1
1
1
1 1
0
1
0
1
1
1
1
Для формулы А v С таблица истинности имеет вид:
A C C А v С
0
0
1
1 0
1
0
1 1
0
1
0 1
0
1
1
Первая из рассматриваемых формул выражает функцию трех переменных F(A,В,С), вторая — двух аргументов F(A,С). Значения истинности F(A,С) обоих формул совпадают. Это означает, что две рассматриваемые формулы представляют одну и ту же логическую функцию F(A, С), а значение истинности той формулы, в которую переменная В не входит, не зависит от значений истинности, придаваемых этой переменной.
Две различные формулы, задающие одну и ту же истинностную функцию, называются равносильными. Отношение равносильности обозначают символом "?".Для данного случая
((А*В) ~ С) v ((В ? С) ? А) ? А v С
Таким образом, формулы равносильны, если их значения истинности, при любом наборе значений истинности входящих в них переменных, совпадают. Отношение равносильности обладает свойствами рефлексивности, симметричности и транзитивности.
Имея, например, элементарные функции отрицания, дизъюнкции, эквивалентности и импликации, можно составить следующие новые функции алгебры логики, являющиеся суперпозициями этих функций:
x2? x1; x1v x2;(x1 v x2)? (x1 v x3);
[(x2~ x3) v x1]? (x2? x1) и т.д.
Используя таблицы, определяющие элементарные функции, можно задавать любую функцию алгебры логики, являющуюся суперпозицией этих
функций.
Пример 2.1 Пусть требуется представить в виде таблицы следующую функцию:
f(x1,x2,x3) = {[(x1~x3)v(x1 ? x2)](x1 ? x2)}?x3
Таблица истинности имеет вид:
x1 x2 x3 x1 x1~x3 x1 ? x2 [] x1 ? x2 {} f(x1,x2,x3)
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
1
0
0
0
0 0
1
<< Пред. стр. 1 (из 7) След. >>
Список литературы по разделу