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

Размещено на http://allbest.ru

ВВЕДЕНИЕ

математический логика алгебра

Теоретической основой построения ЭВМ служат специальные математические дисциплины. Одной из них является алгебра логики, или булева алгебра (Дж. Буль - английский математик XIX в., основоположник этой дисциплины). Ее аппарат широко используют для описания схем ЭВМ, их проектирования и оптимизации.

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

Формализация рассуждений восходит к Аристотелю. Современный вид аристотелева (формальная) логика приобрела во второй половине XIX века в сочинении Джорджа Буля “Законы мысли”.

Интенсивно математическая логика начала развиваться в 50-е годы XX века в связи с бурным развитием цифровой техники.

1.ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ

1.1Основные операции алгебры логики

Логическая операция КОНЪЮНКЦИЯ (лат. conjunctio - связываю):

· в естественном языке соответствует союзу и;

· обозначение: &;

· в языках программирования обозначение: and;

· иное название: логическое умножение.

Конъюнкция - это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания истинны.

Таблица истинности конъюнкции:

А	В	А&В
0	0	0
0	1	0
1	0	0
1	1	1

Поскольку таблица истинности для конъюнкции совпадает с таблицей умножения, если истинному высказыванию приписать значение '1', а ложному - '0', то сложное высказывание можно назвать произведением. Функция конъюнкции истинна тогда, когда истинны одновременно оба высказывания. Читается «А и В». Возможно обозначение «&», «», «», «и».

Логическая операция ДИЗЪЮНКЦИЯ (лат. disjunctio - различаю):

· в естественном языке соответствует союзу или;

· обозначение:;

· в языках программирования обозначение: or;

· иное название: логическое сложение.

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

Таблица истинности дизъюнкции:

А	В	АВ
0	0	0
0	1	1
1	0	1
1	1	1

Составное высказывание, образованное в результате дизъюнкции, истинно тогда, когда истинно хотя бы одно из входящих в него простых высказываний. Например: Имеем четыре составных высказывания, образованных с помощью дизъюнкции:1. «2Х2=5 или 3х3=10»; 2. «2х2=5 или 3х3=9»;3. «2х2=4 или 3х3=10» 4. «2х2=4 или 3х3=9».Здесь истинны 2, 3 и 4 высказывания. Итак, составное высказывание истинно тогда, когда истинно хотя бы одно простое высказывание, входящее в него. Читается «А или В». Возможно обозначение «v», «+», «или».

Логическая операция ИНВЕРСИЯ (лат. inversio - переворачиваю):

· в естественном языке соответствует словам "Неверно, что... " и частице не;

· обозначение: не А; .

· в языках программирования обозначение: not;

· иное название: отрицание.

Отрицание - это логическая операция, которая каждому простому высказыванию ставит в соответствие составное высказывание, заключающееся в том, что исходное высказывание отрицается.

Таблицы истинности отрицания:

А	не А
0	1
1	0

Функция логического сложения ИЛИ дает значение TRUE (Истина), только тогда, когда хотя бы один логический аргумент имеют значение TRUE. Функция логического отрицания НЕ дает значение TRUE (Истина), когда логический аргумент имеют значение FALSE (0) и, наоборот, значение FALSE (Ложь), когда логический аргумент имеют значение TRUE. Читается «не А», или «А с чертой», или «отрицание А». Обозначается .

Логическая операция ИМПЛИКАЦИЯ (лат. implicatio - тесно связываю):

· в естественном языке соответствует обороту Если ..., то ...;

· обозначение: ;

· иное название: логическое следование.

Импликация - это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся ложным тогда и только тогда, когда условие (первое высказывание) истинно, а следствие (второе высказывание) ложно.

Таблица истинности импликации:

А	В	АВ
0	0	1
0	1	1
1	0	0
1	1	1

Логическая операция ЭКВИВАЛЕНЦИЯ (лат. аequivalens - равноценное):

· в естественном языке соответствует оборотам речи тогда и только тогда и в том и только в том случае;

· обозначение: ~ ;

· иное название: равнозначность.

Эквиваленция - это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания одновременно истинны или одновременно ложны.

Таблица истинности эквиваленции:

А	В	А~В
0	0	1
0	1	0
1	0	0
1	1	1

Все виды логических операций удобно свести в одну таблицу:

A	B	A&B	AB	AB	AB	A	..
0	0	0	0	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	0	0
1	1	1	1	1	1	0

1.2 Логические выражения (составные высказывания)

Логические операции имеют следующий приоритет: действия в скобках, инверсия , &, v, , ~.

Таблицу, показывающую, какие значения принимает составное высказывание при всех сочетаниях (наборах) значений входящих в него простых высказываний, называют таблицей истинности составного высказывания.

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

Алгоритм построения таблицы истинности:

1. подсчитать количество переменных n в логическом выражении;

2. определить число строк в таблице m = 2ⁿ;

3. подсчитать количество логических операций в формуле;

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

5. определить количество столбцов в таблице: число переменных плюс число операций;

6. выписать наборы входных переменных с учетом того, что они представляют собой натуральный ряд n-разрядных двоичных чисел от 0 до 2ⁿ-1;

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

Наборы входных переменных, во избежание ошибок, рекомендуют перечислять следующим образом:

а) определить количество наборов входных переменных;

б) разделить колонку значений первой переменной пополам и заполнить верхнюю часть колонки 0, а нижнюю -1;

в) разделить колонку значений второй переменной на четыре части и заполнить каждую четверть чередующимися группами 0 или 1, начиная с группы 0;

г) продолжать деление колонок значений последующих переменных на 8, 16 и т.д. частей и заполнение их группами 0 или 1 до тех пор, пока группы 0 и 1 не будут состоять из одного символа.

Пример. Для формулы A&(B v C) построить таблицу истинности алгебраически и с использованием электронных таблиц.

Количество логических переменных 3, следовательно, количество строк в таблице истинности должно быть 2³ = 8.

Количество логических операций в формуле 2, следовательно, количество столбцов в таблице истинности должно быть 2+3 = 5.

А	В	C	В v C	А & (В v C)
0	0	0	1	0
0	0	1	0	0
0	1	0	1	0
0	1	1	1	0
1	0	0	1	1
1	0	1	0	0
1	1	0	1	1
1	1	1	1	1

Логические выражения называются равносильными, если их истинностные значения совпадают при любых значениях, входящих в них логических переменных.

Аппарат алгебры логики можно с успехом использовать для решения содержательных задач. Однако для этого необходимо научиться правильно переводить высказывания с естественного языка на символический язык алгебры логики.

Рассмотрим пример. Перевести на язык алгебры высказываний следующее предложение:

Я поеду в Москву, и если встречу там друзей, то мы интересно проведем время.

Введем следующие простые высказывания:

М -- «я поеду в Москву»;

В -- «встречу там друзей»;

И -- «интересно проведем время».

Формула: М & (В И).

2. ОСНОВНЫЕ ЗАКОНЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ

В алгебре логики имеется ряд законов, позволяющих производить равносильные преобразования логических выражений. Приведем соотношения, отражающие эти законы.

1.Закон двойного отрицания:

не (не А) = A.

Двойное отрицание исключает отрицание.

2.Переместительный (коммутативный) закон:

- для логического сложения:

А v B = B v A;

- для логического умножения:

A & B = B & A.

Результат операции над высказываниями не зависит от того, в каком порядке берутся эти высказывания.

3.Сочетательный (ассоциативный) закон:

- для логического сложения:

(A v B) v C = A v (B v C);

- для логического умножения:

(A & B) & C = A & (B & C).

При одинаковых знаках скобки можно ставить произвольно или вообще опускать.

4.Распределительный (дистрибутивный) закон:

- для логического сложения:

(A B)& C = (A & C)(B& C);

- для логического умножения:

(A & B) v C = (A v C) & (B v C).

Определяет правило выноса общего высказывания за скобку.

5.Законы исключения констант:

- для логического сложения:

A v 1 = 1, A v 0 = A;

- для логического умножения:

A & 1 = A, A & 0 = 0.

6.Закон противоречия:

A & (не A)= 0.

Невозможно, чтобы противоречащие высказывания были одновременно истинными.

7.Закон исключения третьего:

A v (не A) = 1.

Из двух противоречащих высказываний об одном и том же предмете одно всегда истинно, а второе - ложно, третьего не дано.

8.Закон поглощения:

- для логического сложения:

A v (A & B) = A;

- для логического умножения:

A & (A v B) = A.

9.Закон исключения (склеивания):

- для логического сложения:

(A & B) v ( & B) = B;

- для логического умножения:

(A v B) & (v B) = B.

3.СИСТЕМА ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ

3.1Функциональная полнота

Алгебра над множеством логических функций с двумя бинарными операциями и называется алгеброй Жегалкина. В алгебре Жегалкина выполняются следующие соотношения:

а также соотноения булевой алгебры, относящиеся только к конъюнкции и константам (с конъюнкцией).

Отрицание и дизъюнкция в этой алгебре выражаются следующим образом:

Формулы, содержащие знаки называют полиномами.

Полином вида: , где есть либо 1, либо переменная, либо конъюнкция различных переменных, при , называется полиномом Жегалкина.

Теорема.

Любая булева функция может быть представлена полиномом Жегалки- на



где ki - коэффициенты, принимающие значения 0 или 1: .

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

Например, суперпозицию функций f1, f2, f3 можно задать формулой

.

Если f1 обозначает дизъюнцию, f2 - конъюнкцию, а f3 - сложение по mod 2, то последняя формула примет вид:

.

Если рассматривается произвольная система функций, то возникает вопрос: всякая ли логическая функция из этой системы представима формулой, содержащей символы только этой системы функций.

Система функций алгебры логики (ФАЛ) называется функционально полной, если любая функция алгебры логики может быть реализована формулой, содержащей лишь символы функций из этой системы ФАЛ, т.е. является суперпозицией функций из этой системы.

Следовательно, система функций должна быть функционально полной.

Булева функция называется двойственной для функции , если таблицу истинности для функции можно получить из таблицы для функции f, заменив в значениях аргумента функции 0 на 1 и 1 на 0, т.е. имеет место равенство

Например, конъюнкция и дизюнкция двойственны друг другу, отрицание двойственно самому себе.

Функция, совпадающая со своей двойственной, называется самодвойственной.

Самодвойственная функция на противоположных наборах и принимает противоположные значения. Противоположными являются наборы, сумма десятичных эквивалентов которых равна 2n - 1, где п - количество переменных, от которых зависит функция.

3.2Минимизация булевых функций. Метод Квайна

Импликантой функции называют некоторую логическую функцию, которая обращается в ноль на том же наборе переменных, на котором равна нулю сама функция.

Любой конъюнктивный терм (элементарная конъюнкция) или группа термов, соединенных знаками дизъюнкции, входящие в СДНФ, являются импликантами исходной функции.

Элементарная конъюнкция (конъюнктивный терм), в которой удален один или несколько первичных термов, называется простой импликантой.

Методов минимизации булевых функций в настоящее время существует довольно много. Все они, как правило, состоят из двух этапов. На первом этапе получают список всех простых импликант, т.е. сокращенную ДНФ. На втором этапе, используя таблицу покрытий, удаляют “лишние” импликанты, покрывемые другими импликантами. В результате получают ДНФ, из которой нельзя удалить ни одной импликанты. Такую ДНФ называют тупиковой.

На первом этапе в методе Квайна попарно сравнивают все импликанты, входящие в СДНФ, в целях выявления возможности поглощения какой-то переменной на основе закона склеивания:

.

Процедура продолжается до тех пор, пока не останется ни одного члена, допускающего поглощение с другим термом. В результате получают некоторое количество простых импликант. Дизъюнкция этих импликант является сокращенной ДНФ.

На втором этапе строится таблица покрытий.В строках этой таблицы указываются найденные простые импликанты, а в столбцах - термы исходного выражения функции. Клетки таблицы отмечаются, если простая импликанта входит в состав какого-либо терма. В итоге минимизация булевой функции сводится к тому, чтобы найти такое минимальное количество простых импликант, которые покрывают все столбцы. В результате получают тупиковую ДНФ.

Недостаток метода-необходимость попарного сравнении всех конъюнктивных термов на первом этапе при нахождении простых импликант. С ростом числа исходных термов увеличивается количество попарных сравнений, что усложняет решение задачи минимизации.

Метод Квайна - Мак-Класки представляет собой предыдущий метод, но без геометрического построения п - мерных кубов: кубы присутствуют, но абстрактно.

Метод основан на кубическом представлении конъюнктивных термов ДНФ с предварительным разбиением кубов на подгруппы, определяемые одинаковым числом единиц. Разбиение дает возможность сравнивать кубы только соседних по числу единиц групп для уменьшения количества переборов.

В итеративной процедуре минимизации попарное сравнение можно производить только между соседними группами.

Нахождение простых импликат на первом этапе:

1. Все исходные конъюнктивные термы записываются в виде их двоичных наборов.

2. Все наборы разбиваются на непересекающиеся группы по числу единиц. Условие образования r-куба - наличие расхождения в (r-1)-кубах только по одной координате в одном двоичном разряде и наличие общих независимых координат.

3. В i-группу включают все двоичные наборы, имеющие в своей записи i единиц.

4. Попарное сравнение производится только между соседними по номеру группами. Группы, которые различаются в двух разрядах и более, не имеет смысла сравнивать.

ЗАКЛЮЧЕНИЕ

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

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

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

1. Абачиев С.К. Формальная логика с элементами теории познания: учебник для вузов / С. К. Абачиев. - Ростов-на-Дону: Феникс, 2012. - 635 с.

2. Гетманова А. Д. Логика / А.Д. Гетманова. - М.: КноРус, 2012. - 416 с.

3. Гринченков Д.В.: Математическая логика и теория алгоритмов для программистов. - М.: КноРус, 2010. -206 с.

4. Демидов И.В. Логика: учебник / И. В. Демидов. - 8-е изд. - М.: Дашков и К, 2013. -347 с.

5. Дмитревская И.В. Логика / И.В. Дмитревская. -М.: Флинта, 2013. -384 с.

6. Михайлов К.А. Логика. Практикум: учебное пособие для бакалавров / К. А. Михайлов, В. В. Горбатов. - М.: Юрайт, 2012. - 509 с.

7. Сковиков А.К. Логика: учебник и практикум для бакалавров / А.К. Сковиков. - Москва: Юрайт, 2013. - 575 с.

8. Судоплатов С. В. Математическая логика и теория алгоритмов: учебник / Судоплатов С. В., Овчинникова Е. В. - М.: НГТУ, 2012. - 254 с.

9. Триумфгородских М. В. Дискретная математика и математическая логика для информатиков, экономистов и менеджеров: учебное пособие / Триумфгородских М. В - М.: Диалог-МИФИ,2011. - 180 с.

Размещено на Allbest.ru

...