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

Введение

Тема контрольной работы «Математическая логика».

БУЛЬ или БУЛ, а также БУУЛ, Джордж (1815-1864) – английский математик, который считается основоположником математической логики.

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

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

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

1. Элементы математической логика

Основными разделами математической логики являются исчисление высказываний и исчисление предикатов.

Высказывание – есть предложение, которое может быть либо истинно, либо ложно.

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

Предикат – логическая функция от п переменных, которая принимает значения истинности или ложности.

Исчисление предикатов – раздел математической логики, объектом которого является дальнейшее изучение и обобщение исчисления высказываний.

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

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

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

В алгебре логики интересуются лишь истинностным значением высказываний. Истинностные значения принято обозначать:

1 (истина) 0 (ложь).

Каждой логической операции соответствует функция, принимающая значения 1 или 0, аргументы которой также принимают значения 1 или 0.

Такие функции называются логическими или булевыми, или функциями алгебры логики (ФАЛ). При этом логическая (булева) переменная x может принимать только два значения: .

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

В этом случае алгебру логики можно определить, как совокупность множества логических функций с заданными в нем всевозможными логическими операциями. Таким логическим операциям, как конъюнкция (читается И), дизъюнкция (ИЛИ), импликация, эквивалентность, отрицание (НЕ), соответствуют логические функции, для которых приняты обозначения (&, ·), ~, – (), и имеет место таблица истинности:

Это табличный способ задания ФАЛ. Наряду с ними применяется задание функций с помощью формул в языке, содержащем переменные x, y, …, z (возможно индексированные) и символы некоторых конкретных функций – аналитический способ задания ФАЛ.

Наиболее употребительным является язык,содержащий логические символы  ~, –. Формулы этого языка определяются следующим образом:

1) все переменные есть формулы;

2) если P и Q – формулы, то  P ~ Q,  - фор-мулы.

Например, выражение ~ - формула. Если переменным x, y, z придать значения из двоичного набора 0, 1 и провести вычисления в соответствии с операциями, указанными в формуле, то получим значение 0 или 1.

Говорят, что формула реализует функцию. Так формула ~ реализует функцию h(x, y, z):

Пусть P и Q – формулы, которые реализуют функции f (x₁, x₂, …, x_n) и g (x₁, x₂, …, x_n). Формулы равны: P = Q, если функции f и g совпадают, т.е. совпадают их таблицы истинности. Алгебра, основным множеством которой является все множество логических функций, а операциями – дизъюнкция, конъюнкция и отрицание, называется булевой алгеброй логических функций.

Приведем законы и тождества, определяющие операции – и их связь с операциями , ~:

1. Идемпотентность конъюнкции и дизъюнкции:

.

2. Коммутативность конъюнкции и дизъюнкции:

.

3. Ассоциативность конъюнкции и дизъюнкции:

.

4. Дистрибутивность конъюнкции относительно дизъюнкции и дизъюнкции относительно конъюнкции:

.

5. Двойное отрицание:

.

6. Законы де Моргана:

=, =.

7. Склеивание:

.

8. Поглощение

.

9. Действия с константами 0 и 1:

.

10. Законы Блейка-Порецкого:

.

11. Связь импликации  с отрицанием – и дизъюнкцией :

.

12. Связь эквивалентности ~ с дизъюнкцией , конъюнкцией  и отрицанием:

~ y =.

Всякая функция алгебры логики может быть реализована некоторой формулой языка с символами ~, –.

1.2 Дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ)

ДНФ и КНФ играют особую роль в алгебре логики и ее приложениях. Введем обозначение:

Так определенная переменная или ее отрицание называется первичным термом.

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

Всякая дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ):

.

Формула вида  называется элементарной дизъюнкцией.

Всякая конъюнкция элементарных дизъюнкций называется конъюктивной нормальной формой (КНФ):

.

Пример.

Привести формулу ~z к ДНФ и КНФ.

1) Приведем формулу к ДНФ (последовательно: на основании определений операций импликации и эквивалентности, законов де Моргана и дистрибутивности):

~ ~(()=

.

2) Применив закон дистрибутивности к последнему выражению, получим КНФ:

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

Совершенная КНФ (СКНФ) определяется как такая КНФ, в которой нет одинаковых сомножителей; все сомножители содержат одни и те же переменные, причем каждую переменную – только один раз.

Для каждой ФАЛ  можно построить реализующую ее СДНФ:

,

где дизъюнкция берется по тем двоичным наборам, на которых f = 1.

Каждая функция алгебры логики  реализуется следующей СКНФ:

Пример.

Функция h(x, y, z), рассмотренная ранее, имеет следующую СДНФ (выписывается по единичным значениям) и СКНФ (выписывается по нулевым значениям):

1

0

;

Пример.

Построить СДНФ и СКНФ будевой функции f(x₁, x₂, x₃), заданной таблицей истинности

.

Разложение булевой функции  по k переменным x₁, x₂,…, x_k называется разложением Шеннона.