Математическая логика (стр. 1 из 7)
Введение
Тема контрольной работы «Математическая логика».
БУЛЬ или БУЛ, а также БУУЛ, Джордж (1815-1864) – английский математик, который считается основоположником математической логики.
Математическая логика – это раздел математики, посвященный анализу методов рассуждений, при этом в первую очередь исследуются формы рассуждений, а не их содержание, т.е. исследуется формализация рассуждений.
Формализация рассуждений восходит к Аристотелю. Современный вид аристотелева (формальная) логика приобрела во второй половине XIX века в сочинении Джорджа Буля “Законы мысли”.
Интенсивно математическая логика начала развиваться в 50-е годы XX века в связи с бурным развитием цифровой техники.
1. Элементы математической логика
Основными разделами математической логики являются исчисление высказываний и исчисление предикатов.
Высказывание – есть предложение, которое может быть либо истинно, либо ложно.
Исчисление высказываний – вступительный раздел математической логики, в котором рассматриваются логические операции над высказываниями.
Предикат – логическая функция от п переменных, которая принимает значения истинности или ложности.
Исчисление предикатов – раздел математической логики, объектом которого является дальнейшее изучение и обобщение исчисления высказываний.
Теория булевых алгебр (булевых функций) положена в основу точных методов анализа и синтеза в теории переключательных схем при проектировании компьютерных систем.
1.1 Основные понятия алгебры логики
Алгебра логики – раздел математической логики, изучающий логические операции над высказываниями.
В алгебре логики интересуются лишь истинностным значением высказываний. Истинностные значения принято обозначать:
1 (истина) 0 (ложь).
Каждой логической операции соответствует функция, принимающая значения 1 или 0, аргументы которой также принимают значения 1 или 0.
Такие функции называются логическими или булевыми, или функциями алгебры логики (ФАЛ). При этом логическая (булева) переменная x может принимать только два значения:
.Таким образом,
- логическая функция, у которой логи-ческие переменные 
являются высказываниями. Тогда сама логическая функция является сложным высказыванием.В этом случае алгебру логики можно определить, как совокупность множества логических функций с заданными в нем всевозможными логическими операциями. Таким логическим операциям, как конъюнкция (читается И), дизъюнкция (ИЛИ), импликация, эквивалентность, отрицание (НЕ), соответствуют логические функции, для которых приняты обозначения
(&, ·), 
~, – ( 
), и имеет место таблица истинности:  |  |  |  |  |  | x~y |
| 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | 0 | 1 |
Это табличный способ задания ФАЛ. Наряду с ними применяется задание функций с помощью формул в языке, содержащем переменные x, y, …, z (возможно индексированные) и символы некоторых конкретных функций – аналитический способ задания ФАЛ.
Наиболее употребительным является язык,содержащий логические символы
~, –. Формулы этого языка определяются следующим образом:1) все переменные есть формулы;
2) если P и Q – формулы, то
P ~ Q, 
- фор-мулы.Например, выражение
~ 
- формула. Если переменным x, y, z придать значения из двоичного набора 0, 1 и провести вычисления в соответствии с операциями, указанными в формуле, то получим значение 0 или 1.Говорят, что формула реализует функцию. Так формула
~ реализует функцию h(x, y, z):| x | y | z | h(x, y, z) |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
Пусть P и Q – формулы, которые реализуют функции f (x1, x2, …, xn) и g (x1, x2, …, xn). Формулы равны: P = Q, если функции f и g совпадают, т.е. совпадают их таблицы истинности. Алгебра, основным множеством которой является все множество логических функций, а операциями – дизъюнкция, конъюнкция и отрицание, называется булевой алгеброй логических функций.
Приведем законы и тождества, определяющие операции
– и их связь с операциями 
, ~:1. Идемпотентность конъюнкции и дизъюнкции:
.2. Коммутативность конъюнкции и дизъюнкции:
.3. Ассоциативность конъюнкции и дизъюнкции:
.4. Дистрибутивность конъюнкции относительно дизъюнкции и дизъюнкции относительно конъюнкции:
.5. Двойное отрицание:
.6. Законы де Моргана:
= 
, 
= 
.7. Склеивание:
.8. Поглощение
.9. Действия с константами 0 и 1:
.10. Законы Блейка-Порецкого:
.11. Связь импликации
с отрицанием – и дизъюнкцией 
: 
.12. Связь эквивалентности ~ с дизъюнкцией
, конъюнкцией и отрицанием: 
~ y = 
.Всякая функция алгебры логики может быть реализована некоторой формулой языка с символами
~, –.1.2 Дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ)
ДНФ и КНФ играют особую роль в алгебре логики и ее приложениях. Введем обозначение:
Так определенная переменная или ее отрицание называется первичным термом.
Формула вида
, где 
- двоичный набор, а среди переменных нет одинаковых, называется элементарной конъюнкцией.Всякая дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ):