 |
Факультатив . Введение в основы формальной логики
|
|
|
|
Формальная логика (математическая логика) является важнейшей основой функционирования современных компьютеров. когда делаем запрос на поиск информации в Интернете или базе данных или когда анализируем правильность математического вывода. Многие элементы компьютеров проектируются и работают на основе законов формальной логики. Её общепризнанным создателем является английский математик Джордж Буль (1815 – 1864). До работ Буля логика всегда считалась одним из разделов философии. Основы логики, как науки о законах и формах мышления, были заложены ещё в работах Аристотеля в 384 г. до н.э. Аристотель ввёл понятие силлогизма, сделав важный шаг в разработке логической дедукции и формализации логических рассуждений. Когда мы говорим о формальной логике, то имеем в виду, что анализируется правильность формы высказываний и умозаключений, а не их конкретное содержание.
Достижения Аристотеля в области логики не претерпели существенных изменений вплоть до XVII века. Впервые идеи обоснования логики на основе вычислений, подобно тому как мы оперируем символами в алгебре, были высказаны ещё в XVII веке Готфридом Лейбницем. Идеи Лейбница реализовал в своих работах Дж. Буль. В 1847 г. он опубликовал работу "Математический анализ логики", в которой высказал идею, что логика более близка к математике, чем к философии. Эта работа была чрезвычайно высоко оценена английским математиком Августом Де Морганом, который преподавал математику для Ады Лавлейс. В 1854 году Буль опубликовал работу "Исследование законов мышления, базирующихся на математической логике и теории вероятностей". Эти исследования Буля заложили основы алгебры логики или булевой алгебры. Ученый первым показал, что существует аналогия между алгебраическими и логическими действиями. Буль придумал систему обозначений и правил, пользуясь которыми, можно было закодировать любые высказывания, а затем манипулировать ими как обычными алгебраическими выражениями. Именно поэтому логику Буля часто называют математической логикой или Булевой алгеброй.
|
|
|
Рассмотрим основные понятия логики: суждение, понятие, простые и сложные высказывания. С помощью понятий мы раскрываем значение естественных или искусственных знаков, указываем классы, к которым принадлежат или не принадлежат мыслимые нами вещи. Умственное развитие – это способность переосмысливать старые и конструировать новые понятия. Только понятия делают нашу речь осмысленной. Мы имеем понятие о некоторой вещи, если знаем и можем словесно выразить, какие условия необходимы и достаточны для её однозначного определения.
Условие, определяющие некоторый класс вещей, называется необходимым, если все вещи из этого класса и, возможно, некоторые вещи из его дополнения удовлетворяют этому условию. Условие, определяющее некоторый класс вещей, называется достаточным, если некоторые (может быть и все) вещи из этого класса удовлетворяют этому условию, но ни одна вещь из дополнения класса не удовлетворяет ему.
В терминах свойств можно определить необходимость некоторого условия следующим образом: если некоторая вещь не может существовать без данного свойства, то это свойство необходимо для её существования. Если же из существования некоторого свойства можно сделать вывод о существовании некоторой вещи, то это свойство достаточно для этой вещи.
Суждения позволяют нам выразить разнообразные отношения между мыслимыми вещами. Мы имеем суждение о некоторой вещи, если можем выразить словесно её отношение к другой вещи или к себе самой.
|
|
|
Основная языковая форма суждения – повествовательное предложение.
Суждение может быть истинным, ложным или неопределённым. Суждение (высказывание) является простым, если ни одна его часть не может рассматриваться как суждение. Простые суждения принято обозначать буквами: А, B, C, D
Любое простое суждение состоит из 4-х функционально различимых
частей:
1) субъекта суждения (S) – класс вещей, о котором нечто утверждается;
2) предиката суждения (P) – класс вещей, который утверждается относительно субъекта; предикат выражает то, что утверждается относительно S;
3) утвердительной или отрицательной связки «есть» или «не есть», которая ставится между S и P;
4) слов «все», «некоторые», «ни один», которые ставятся перед субъектом.
| все некоторые S ниодин | есть неесть | P (8.1) |
Если простое суждение имеет форму, отличную от (1), то его можно преобразовать к этой форме.
Все простые суждения классифицируются как утвердительные и отрицательные, которые, в свою очередь, делятся на общие и частные: «Все студенты ходят на лекции», «Некоторые преподаватели читают детективы», «Ни один человек не хочет быть несчастливым», «Некоторые фрукты не растут в России».
Суждение истинно, если в нём утверждается связь между объектом и признаком, имеющая место в действительности, или отрицается связь, не имеющая места в действительности. Суждение ложно, если в нём утверждается связь между объектом и признаком, не имеющая места в действительности, или отрицается связь, которая имеет место в действительности. Истину и ложь обозначают по–разному: 1 или 0, T или F (от английского True и False), И или Л. Мы будем пользоваться обозначением 1, если суждение истинно: A =1. Ложное суждение
обозначим нулём: B =0.
Сложные суждения состоят из нескольких простых, соединённых различными логическими союзами: «неверно, что A», «B и C», «A или D», «если B, то C», «или А или В». Например, «сегодня тихо и пасмурно».
Сложные суждения можно выразить через простые, но не наоборот.
Связка «не А» или «неверно, что A» называется отрицанием.
Отрицание суждения А является истинным, если А ложно, и ложным, если
А истинно. Обозначают отрицание суждения А как «не А» или A, или not(A). Правила вычисления логической операции «отрицание» можно задать с помощью таблицы:
|
|
|
| A | не А |
Связка «и» называется конъюнкцией высказываний A и B и принимает значений истина, только когда оба высказывания истинны, в других случаях конъюнкция принимает значение ложь. Обозначают конъюнкцию суждений A и B как A&B, A and B (в программировании), A ⁄ B (в учебниках по логике). Правила вычисления конъюнкции зададим с помощью таблицы истинности:
| A | B | A ⁄ B |
Конъюнкцию иногда называют логическим умножением: результат в третьем столбце формально можно получить как произведение чисел из 1ого и 2-ого столбцов.
Логически связка «или» называется дизъюнкцией. Дизъюнкция двух высказываний А и В принимает значение «истина», если хотя бы одно из высказываний истинно, и значение «ложь», если оба высказывания ложны. Для дизъюнкции используют обозначение A ¤ B, в программировании используют обозначение A or B. Таблица истинности для дизъюнкции имеет вид:
| A | B | A ¤ B |
Дизъюнкцию иногда называют логическим сложением. Связка «или» в дизъюнкции не имеет исключающего характера. В логике используется так называемая сильная дизъюнкция (исключающее или), которая на русском языке выражается с помощью связки «или А, или В». Она носит исключающий характер, т.к. принимает значение истина, когда операнды имеют разное логическое значение. Обозначается в программировании как A xor B; таблица истинности имеет вид:
| A | B | A xor B |
Очевидно, что конъюнкция, дизъюнкция и сильная дизъюнкция являются коммутативными операциями, т.е.
A⁄B = B⁄A; A¤B = B¤A; A xor B = B xor A.
Справедливость этих формул следует из таблиц истинности: при перестановке первых двух столбцов таблицы мы получим в третьем столбце значения, совпадающие со значениями третьего столбца исходной таблицы. Сложные суждения эквивалентны, если они принимают одинаковые логические значения при одинаковых значения простых высказываний, входящих в них.
|
|
|
Логическая связка «если…, то ….» называется импликацией. Импликация высказываний «если A, то В» принимает значение ложь только в одном случае, когда А истинно, а В ложно. Импликация обозначается как AØB. Суждение А называется посылкой, В следствием. Иногда употребляются термины антецедент для посылки А и консеквент – для заключения В. Таблица истинности для импликации имеет вид:
| A | B | A ØB |
Импликация не обладает свойством коммутативности. Это следует из таблицы истинности: если переставить столбцы 1 и 2, то значения в третьем столбце изменятся. Многие теоремы в математике имеют форму импликации. При доказательстве теорем вида A ØB мы доказываем, что ситуация, в которой из верной посылки А можно вывести ложное заключение В, невозможна. Например, «Если числовой ряд сходится, то его n–ый член стремится к нулю». Если теорема A ØB имеет место, то говорят, что В является логическим следствием А.
Эквиваленция – это логическая связка, которая выражается словами «А тогда и только тогда, когда В», «для А необходимо и достаточно В». Эквиваленция обозначается как А¨В и выражается через импликацию и
конъюнкцию:
А¨В = (АØВ) ⁄ (BØA)
Эквиваленция принимает значение истина в случае, когда оба высказывания имеют одинаковые значения. Таблица истинности для
эквиваленции имеет вид:
| A | B | A ¨ B |
Многие теоремы в математике имеют форму эквиваленции. Такие теоремы называются критериям. Например, «Скалярное произведение ненулевых векторов P и Q равно нулю тогда и только тогда, когда эти векторы перпендикулярны».
Из нескольких простых высказываний с помощью логических операций можно составить более сложные высказывания. Для указания порядка выполнения логических действий можно использовать круглые скобки. Для однозначного прочтения логических выражений принят следующий приоритет выполнения операций (перечислены в порядке убывания приоритета): отрицание, конъюнкция, дизъюнкция, сильная дизъюнкция, импликация, эквиваленция. Отрицание – самая «сильная» операция. Например,
А ⁄ В ¤ С = (А ⁄ В) ¤ С; A ¤ В Ø С = ((A) ¤ В) Ø С;
С помощью знака = (равно) будем обозначать равносильные высказывания – высказывания, которые принимают одинаковые логические значения при одинаковых значения простых высказываний, входящих в них. Логическое значение сложного высказывания определяется логическими значениями входящих в него простых высказываний. Например, требуется вычислить логическое значение сложного высказывания «не (А ⁄ В) ¤ (не С)» в случае, если А = 1, В = 1, С=0. Подставим на место простых высказываний их значения. Тогда А ⁄ В
|
|
|
= 1, не (А ⁄ В) = 0, (не С) = 1, дизъюнкция 0 ¤ 1 = 1. Заданное высказывание истинно при заданных значениях А, В, С.
Для определения всех возможных значений сложного высказывания, в зависимости от всевозможных значений входящих в него элементарных высказываний, можно построить таблицу истинности. В этой таблице для каждого простого высказывания, входящего в заданное сложное высказывание, надо создать отдельный столбец. Затем нужно заполнить строки таблицы для простых высказываний всевозможными комбинациями их логических значений. Если число простых
высказываний равно n, то таких комбинаций будет 2n. Затем надо представить сложное высказывание в виде комбинации более простых, но также сложных высказываний и завести для каждого из них свой столбец. Один столбец (обычно последний) заводим для заданного высказывания. Заполняем все строки полученной таблицы. Например, пусть задано
высказывание (формула)
не А ¤ В Ø А ⁄ не В.
Требуется составить для данного высказывания таблицу истинности.
Запишем данную формулу с применением скобок: ((не А) ¤ В) Ø (А ⁄ (не
В)). В таблице будет четыре строки, т.к. простых высказываний два: А и В.
| А | В | не А | не В | не А ¤ В | А ⁄ не В | (не А ¤ В) Ø (А ⁄ не В) |
Отметим, что заданная формула эквивалентна формуле «не (А Ø В)» (см. таблицу истинности для импликации), так как принимает одинаковые с ней логические значения при одинаковых значениях простых суждений, входящих в эти формулы.
Перечислим основные правила преобразования логических выражений. Эти правила используются для упрощения заданных формул с целью получения из них более простых и эквивалентных им выражений.
1) A = А (закон двойного отрицания).
2) А ¤ A = 1 (закон исключённого третьего)
3) А ⁄ А = А
4) А ⁄ 1 = А
5) А ⁄ 0 = 0
6) А ¤ А = А
7) А ¤ 1 = 1
8) А ¤ 0 = А
9) А ⁄ A = 0
10) А ⁄ (В ¤ А) = А
11) А ¤ (В ⁄ А) = А
Правила выражения одних логических операций через другие:
1) А Ø В = A ¤ В
2) A B A B∧ = ∨ (закон де Моргана)
3) A B A B∨ = ∧ (закон де Моргана)
4) А¨В = (АØВ) ⁄ (BØA)
В логике доказывается теорема, в которой утверждается, что все логические операции можно выразить через отрицание, конъюнкцию и дизъюнкцию. Говорят, что эти операции образуют полную систему логических операций.
Для операций конъюнкции и дизъюнкции имеют место свойства коммутативности, ассоциативности и дистрибутивности:
1) А ⁄ В = В ⁄ А; - коммутативность.
2) А ¤ В = В ¤ А; - коммутативность.
3) А ⁄ (В ⁄ С) = (А ⁄ В) ⁄ С;- ассоциативность.
4) А ¤ (В ¤ С) = (А ¤ В) ¤ С; - ассоциативность.
5) А ⁄ (В ¤ С) = (А ⁄ В) ¤ (А ⁄ С); - дистрибутивность.
6) А ¤ (В ⁄ С) = (А ¤ В) ⁄ (А ¤ С); - дистрибутивность.
Рассмотрим пример равносильных преобразований. Упростить формулу, используя перечисленные выше свойства и правила
преобразования логических выражений:
(A ∨ → ∨ ∧B A B) B
Выполним цепочку равносильных преобразований:
(A ∨ ∨ ∨ ∧B A B) B = (A ∨ ∨ ∨ ∧B A B) B=(A ∨ ∧B) B= B.
В XX веке в математической логике произошли важные изменения: впервые со времен своего возникновения логика стала многозначной. В многозначной логике высказывания могут иметь более двух истинностных значений. В 1920 г. Ян Лукасевич разработал трёхзначную логику. В ней высказывания могут принимать три значения: «истина», «ложь» и «может быть» или «неопределено». В такой логике не действует закон исключенного третьего. В 1921 г. Э. Пост выдвинул идею многозначной логики. В k – значной логике высказывания могут принимать значения от
0 до к-1, где k=3,4, 5… и т.д.
В
.
.
Список рекомендуемой литературы.
1. Арбиб, М. Мозг, машина и математика / М. Арбиб. - М.: Наука, 1968.
– 224 c.
2. Винер, Н. Кибернетика, или Управление и связь в животном и машине /
Н. Винер. - 2-е изд. - М.: Советское радио, 1968. -328 с.
3. История информатики и философия информационной реальности: учеб. пособие для вузов / под ред. Р. М. Юсупова, В. П. Котенко. – М.:
Академический Проект, 2007. - 429 с.
4. Лихтарников, Л. М., Математическая логика / Л. М. Лихтарников, Т. Г.
Сукачёва. – СПб.: Лань, 1998. – 228 с.
5. Пенроуз, Р. Новый ум короля. - М.: УРСС, 2003. - 384 с.
6. Соболева, Т. С. Дискретная математика / Т. С. Соболева, А. В. Чечкин. –
М.: Издательский центр «Академия», 2006. – 256 с.
7. Уэбстер, Ф. Теории информационного общества / Ф. Уэбстер. - М.:
Аспект Пресс, 2004. – 400 с.
8. Чернавский, Д. С. Синергетика и информация / Д. С. Чернавский. - М.:
УРСС, 2004. – 288 c.
9. Эшби, У. Введение в кибернетику: пер. с англ. / У. Эшби; под ред. В. А. Успенского. - Изд. 3-е, стереотип. – М.: КомКнига, 2006. – 432 с.
[1] НОД двух чисел это наибольшее натуральное число, на которое делится каждое из этих чисел нацело.
|
|
|
