Чем занимается математическая логика? Логика как искусство рассуждений зародилась в глубокой древности. Начало науки о законах и формах мышления связывают с именем Аристотеля. Лейбниц предложил ввести в логику математическую символику и использовать ее для общих логических построений. Эту идею последовательно реализовал Джордж Буль и тем самым заложил основы математической (символической) логики.[6]
4.1. Высказывание — это повествовательное предложение, о котором можно точно сказать, истинно оно или ложно. Например, предложение «Множество 
всех ненулевых чисел не является пустым» является высказыванием, так как это предложение — повествовательное и о нем точно можно сказать, что оно истинно. Другой пример, предложение «Железо — диэлектрик» является высказыванием, причем ложным. Вопросительные и восклицательные предложения не являются высказываниями. Предложение «На Марсе есть жизнь» также не является высказыванием, так как мы не знаем точно, имеется ли жизнь на Марсе.
Строго говоря, понятие «высказывание» является в математической логике неопределяемым, а первое предложение настоящего пункта — всего лишь пояснение на бытовом языке. Но даже из этого пояснения следует, что если L — множество всех высказываний, то определено отображение
x: L ¾® Z2,
такое, что для любого А Î L определим x(А) = 1, если А — истинное высказывание, или x(А) = 0, если А — ложное высказывание.
4.2. Отрицание. Из высказывания А = «Сегодня — четверг» можно построить новое высказывание 
(читается: «не А»), с помощью универсального приема: = «Неверно, что А» = «Неверно, что сегодня — четверг». Высказывание называется отрицанием высказывания А. Логическая операция получения из А называется отрицанием. Другими словами, отрицание — это автоморфизм множества L всех высказываний, при этом если А — истина, то Ā — ложь, а если А — ложь, то Ā — истина. Сказанное отражает следующая таблица истинности, которая фактически является определением операции отрицания высказываний.
А | Ā |
1 | 0 |
0 | 1 |
4.3. Следующие четыре операции называются и обозначаются конъюнкция Ù, дизъюнкция Ú, импликация Þ, эквиваленция Û; они определяются с помощью таблиц истинности:
А | В | А Ù В | А Ú В | А Þ В | А Û В |
1 | 1 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 1 | 0 | 0 |
0 | 1 | 0 | 1 | 1 | 0 |
0 | 0 | 0 | 0 | 1 | 1 |
Каждая из этих операций является двуместной (бинарной), т.е. каждая из них отображает L ´ L на L. Это немедленно приводит нас к булевым функциям.
4.4. Булевы функции. Объекты с двумя возможными состояниями характеризуются булевыми переменными, которые способны принимать лишь два различных значения 0 и 1. Отношения между булевыми переменными представляются булевыми функциями вида
f: 
¾® Z2,
которые подобно числовым функциям могут зависеть от одной, двух и, вообще, п переменных (аргументов). Запись Y = f (X1, X2, ..., Xп) означает, что Y — функция аргументов X1, X2, ..., Xn. Важнейшая особенность булевых функций состоит в том, что они, как и их аргументы, принимают свои значения из двухэлементного множества Z2, т. е. характеризуются одним из двух возможных состояний.
Функции небольшого числа переменных можно задавать с помощью таблиц истинности. Для этого нужно только указать значения функции для каждой комбинации значений ее аргументов.
4.5. Логические операции и формулы. Булевы функции можно рассматривать как логические операции над величинами, принимающими значения 0 или 1. Отрицание — это одноместная операция, а конъюнкция, дизъюнкция, импликация и эквиваленция — двухместные операции. При этом выражения X, Y, 
, X Ù Y, X Ú В, А Þ В, А Û В являются логическими формулами.
Более сложные формулы получаются замещением входящих в них переменных другими логическими формулами, которые обычно заключаются в скобки. Например, положив 
и 
, из формулы 
получаем формулу 
. Каждая формула определяет булеву функцию. Ее значения при различных значениях переменных А, В, С определяются по таблице истинности, построенной на основании таблиц истинности, приведенных в п. 4.2 и п. 4.3.
A | B | C |
|
|
|
1 | 1 | 1 | 0 | 1 | 1 |
1 | 1 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 0 | 0 | 0 |
1 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 1 | 1 | 1 | 1 |
0 | 1 | 0 | 1 | 0 | 1 |
0 | 0 | 1 | 1 | 0 | 1 |
0 | 0 | 0 | 1 | 0 | 1 |
Равносильность функций (и определяющих их формул) понимается в смысле равносильности отображений (см. п. 3.2).
4.6. Булева алгебра — это тройка B = [F Å Z2 Å W], где F — множество всех булевых функций, W = {¯, Ù, Ú} — множество трех логических операций: отрицание, конъюнкция, дизъюнкция. Из определения логических операций легко следует справедливость тождеств (свойств) булевой алгебры:
коммутативность
= 
, 
= 
;
ассоциативность
= 
, 
= 
;
дистрибутивность
= 
, 
= 
;
поглощение нуля
;
умножение на единицу
;
свойства отрицания
, 
.
4.7. Тождественные преобразования. Приведенные свойства позволяют получить ряд других важных законов и тождеств уже без обращения к таблицам истинности:
, 
(законы де Моргана),
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 |
